boostorg / boostorg/graph_parallel

uneven_block distribution does not handle empty processes correctly

Open
#18 2 comments 1 reaction 0 assignees View on GitHub
Dominant language
C++
Stars
33
Forks
41
Avg merge
1d 11h
Merged PRs (30d)
1

Description

When creating an instance of uneven_block with the distribution [1, 0, 1] then the implementation incorrectly returns process id 1 (counting from 0) to be the owner of element id 1 (counting from zero), because the local starts of processes 1 and 2 are identical (local starts would be [0, 1, 1, 2] in this case).

In general, the implementation incorrectly assigns elements belonging to the first owner after one or more adjacent empty owners to the first of those empty ones.

I would suggest to change the implementation from
https://github.com/boostorg/graph_parallel/blob/22385ccb6c35fcb07971f295807519bd031ed57d/include/boost/graph/parallel/distribution.hpp#L225-L226
to
```
size_vector::const_iterator ub = std::upper_bound(local_starts.begin(), local_starts.end(), (std::size_t) i);
return (--ub) - local_starts.begin();
```

Edit: Corrected mistake as pointed out below.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.