Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[ENH] Graph primitives performance improvement #1442

Closed
3 tasks
seunghwak opened this issue Mar 8, 2021 · 1 comment
Closed
3 tasks

[ENH] Graph primitives performance improvement #1442

seunghwak opened this issue Mar 8, 2021 · 1 comment
Assignees
@seunghwak
Milestone
21.06

Comments

@seunghwak
Copy link
Contributor

Describe the solution you'd like
Performance optimize graph primitives.

In short term, we need to

  • Update graph partitioning scheme to allow simpler/faster communication patterns and control trade-offs between memory footprint and parallelism
  • Address thread-divergence issue when vertices have widely varying numbers of neighbors (e.g. Power-law graphs)
  • Specialize update_frontier_v_push_if_out_nbr for pure function reduction operations (this will improve performance/memory footprint of BFS & SSSP)
@seunghwak seunghwak added the ? - Needs Triage Need team to review and classify label Mar 8, 2021
@seunghwak seunghwak mentioned this issue Mar 8, 2021
Merged
@BradReesWork BradReesWork removed the ? - Needs Triage Need team to review and classify label Mar 10, 2021
@BradReesWork BradReesWork added this to the 0.20 milestone Mar 10, 2021
@seunghwak seunghwak mentioned this issue Mar 11, 2021
Merged
rapids-bot bot pushed a commit that referenced this issue Apr 6, 2021
@seunghwak
Update graph partitioning scheme (#1443)
9a1ab09 
Partially addresses Issue #1442

Update graph partitioning scheme to better control memory footprint vs concurrency trade-offs for large-scale graph processing in large clusters. This new partitioning scheme also simplifies communication patterns among GPUs which can potentially improve scalability.

Authors:
  - Seunghwa Kang (https://github.com/seunghwak)

Approvers:
  - Chuck Hastings (https://github.com/ChuckHastings)
  - Alex Fender (https://github.com/afender)
  - Andrei Schaffer (https://github.com/aschaffer)

URL: #1443
rapids-bot bot pushed a commit that referenced this issue Apr 7, 2021
@seunghwak
Improve graph primitives performance on graphs with widely varying ve…
1b34e26 
…rtex degrees (#1447)

Partially addresses Issue #1442

Update graph primitives used by PageRank, Katz Centrality, BFS, and SSSP to launch 3 different kernels based on vertex degrees to address thread divergence issue. In addition, cut memory footprint of the VertexFrontier class used by BFS & SSSP.

The following highlights performance improvement with this optimization.

R-mat 2^25 vertices 2^25 * 32 edges
PageRank: 7.66, 7.42, 8.83, 8.83 seconds (the first two unweighted, the last two weighted, first & third without personalization)=> 1.07, 1.08, 1.36, 1.39 seconds
Katz: 1.08, 1.94 seconds (unweighted, weighted)=> 0.243, 0.275
BFS: 1.32 seconds=> 0.251
R-mat 2^25 vertices 2^25 * 16 edges
SSSP: 1.89 seconds (memory allocation fails with the edge factor of 32)=> 0.317

And now SSSP also works with 2^25 vertices 2^25 * 32 edges with the memory footprint improvement and it took 0.514 sec.

Still needs additional optimizations to reach the target performance

1. add BFS & SSSP specific optimizations (the current implementation assumes general reduction operations while BFS can pick any source vertex if a vertex is discovered by multiple source vertices and SSSP picks the one with the minimum edge weight, these pure function reduction operations allow additional optimizations).
2. Launch 3 different kernels in multiple streams to recover parallelism when the frontier size is relatively small (currently three kernels are queued in a single stream, and this leads to up to 3x decrease in parallelism)

Authors:
  - Seunghwa Kang (https://github.com/seunghwak)

Approvers:
  - Alex Fender (https://github.com/afender)
  - Chuck Hastings (https://github.com/ChuckHastings)
  - Brad Rees (https://github.com/BradReesWork)

URL: #1447
@github-actions
Copy link

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@seunghwak seunghwak

Labels
None yet
Projects
None yet
Milestone
21.06
Development

No branches or pull requests
2 participants
@BradReesWork @seunghwak