uneven_block distribution does not handle empty processes correctly
Nobody has claimed this yet.
Assessment
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Newbie friendliness
- 42/100
- Issue type
- Bug
- Clarity
- Clearly specified
- Activity status
- Stale
- Tech stack
- cpp
- Domain
- distributed-systems
Research direction
Start in include/boost/graph/parallel/distribution.hpp at lines 225-226 and inspect how local_starts determines the owner process. Reproduce the distribution [1, 0, 1], then verify that element ownership skips adjacent empty processes, including the suggested upper_bound behavior.
Written by the indexing model from the issue text.
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.
- Dominant language
- C++
- Stars
- 33
- Forks
- 41
- Avg merge
- 1d 11h
- Merged PRs (30d)
- 1
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from boostorg/graph_parallel
-
boostorg/graph_parallel#43 · 3 comments · 1 assignee ·
-
Difficulty 4/5 3-5 days Newbie friendliness 30/100
boostorg/graph_parallel#39 · 3 comments ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 35/100
boostorg/graph_parallel#37 · 2 comments ·
-
Difficulty 3/5 1-2 days Newbie friendliness 35/100
boostorg/graph_parallel#33 · 2 comments ·
-
Difficulty 3/5 1-2 days Newbie friendliness 35/100
boostorg/graph_parallel#27 ·
All issues in boostorg/graph_parallel
Similar issues
-
Difficulty 1/5 Under an hour Newbie friendliness 90/100
AXERA-TECH/ax-llm#77 ·
-
Difficulty 1/5 Under an hour Newbie friendliness 90/100
games-on-whales/wolf#509 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 74/100
-
bug-unconfirmed
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 74/100
NVIDIA/cuda-samples#453 ·