search

gunrock / gunrock

Programmable CUDA/C++ GPU Graph Analytics
https://gunrock.github.io/gunrock/
Apache License 2.0
976 stars 200 forks source link

Weighted label propagation algorithm #671

Open dimlichmanov opened 4 years ago

dimlichmanov commented 4 years ago

Hello. Is LP permanently deleted from gunrock examples? Unable to find it, though it is present in the list of test applications and primitives(

neoblizz commented 4 years ago

@Herceg00 it is in v0.5.x version, and is still available. All you have to do is switch to that branch and use it. It will eventually be ported to the latest API.

achalagarwal commented 4 years ago

I will try porting lp to v1.x

  1. It's one of the algorithms required by graphalytics -> https://github.com/gunrock/gunrock/issues/651
  2. It involves a basic communication pattern (that of iterative neighborhood aggregation) which I will require for graph neural networks.
jowens commented 4 years ago

Super. There's a porting guide but mostly I want to make sure that you make lots of comments along the way about what we can do better in terms of writing apps / porting apps. Very useful feedback for the team.

achalagarwal commented 4 years ago

I am using this issue to maintain my notes/todos for the implementation of LP, @neoblizz feel free to butt in on any of my doubts/assumptions, I will also be personally trying and confirming/figuring out things in the meanwhile.

The flow for the simple label propagation iterative BSP model that I imagine would be as follows :- (I will later upgrade this to an optimized push pull model as done in BFS)

  1. Compute -- Vertex Frontier (To populate an array Y with the "number of neighbors" each vertex in the frontier has) There needs to be a quick mapping available i.e. given vertex id, get the corresponding index in array Y

  2. Compute -- Edge Frontier (To populate an array X with the label of each dest vertex): This needs to in sync with the segment heads. So if a vertex v_x has a segment head = 7, the third neighbor of v_x has to store its label in the index 9 of array X. Optimisation for later: Here if no dest_vertex has a new label (detected by a dirty flag), then we can filter out the corresponding source vertex.

Here X and Y are related, X is a segmented array with Y holding the segment information (segment heads).

My assumption: I presume that a frontier might not always contain all the vertices in the subgraph corresponding to the data slice. If so, then there are two problems:

My doubt: If the above doubt isn't true, I would still need to map vertex_id to a slot in the array Y. This would be easy if each data_slice has a relative id for the vertices in the subgraph (which I believe should be there)

  1. Run Segmented Mode on the array X (array Y also needed here)

My doubt: What is the best way to link my code for computing segmented mode with gunrock?

  1. Compute -- Same Vertex Frontier (From the output of the segmented mode, save the new labels for each vertex in the frontier) Also update the dirty flag if the label changed.

  2. Advance -- Same Vertex Frontier (Advance to the neighbors of the vertices that changed their labels)

  3. Stopping Condition, if there was no label change for the whole frontier, then we have converged for that subgraph.

Goto 1.

achalagarwal commented 4 years ago

Doubt: Can we have dynamic sizes for Array1D? Currently, there is the Init function in {app}_problem.cuh for static (one time) allocation

neoblizz commented 4 years ago

Doubt: Can we have dynamic sizes for Array1D? Currently, there is the Init function in _problem.cuh for static (one time) allocation

Not as of yet, this is something I discussed with @maawad for dynamic problems. But for static problems, it is ok to allocate for the worst case for the GPU because the cost of reallocating is much more (cudaMemxxx calls are slow).

I don't know the specifics of the algorithm, but if you want to discuss this over zoom or something, I'd be more than happy to learn about it and give you feedback.

achalagarwal commented 4 years ago

if you want to discuss this over zoom or something, I'd be more than happy to learn about it and give you feedback.

@neoblizz yeah that will be great! pinged you on slack!