🔖 Solving the Edge ID issue for GPMA

[JoelMathewC]

This discussion will focus on solving the edge ID issue for GPMA. This can be seen as a sub-discussion of #53.

[JoelMathewC]

Sorting Approach

So here we would need some way to efficiently label the forward graph. To obtain the edge IDs for the reverse graph we could use counting sort on the column indices as key and the edge IDs as values. Once the sort is completed this along with an out_degree aggregation (possible efficiently in CUDA) should allow us to wrap up the edge IDs issue.

There is a chance that to get a proper CSR for backward graph from the forward graph, if we can modify the counting sort implementation. Refer this video. The offsets they calculate here is essentially the row_offset of the reverse graph for us.

[JoelMathewC]

Edge IDs for backward graph

1. Let fwd_row_offset, fwd_column_indices, fwd_eids represent the row offset, column indices and edge ids of the forward graph.
2. Note that fwd_column_indices and fwd_eids will contain spaces due to their role in GPMA.
3. Additonally, assume fwd_in_degrees to be an array of in degrees of the forward graph

Pseudocode
-------------

Step 1: Allocate space for bwd_row_offset with size total number of nodes
Step 2: Find the cumulative sum array for fwd_in_degrees (using efficient CUDA cummulative) and store the result in bwd_row_offset
Step 3: Allocate space for bwd_column_indices and bwd_eids with size total number of edges
Step 4: Perform count sort on fwd_column_indices and fwd_eids using the last 32 bits of elements in fwd_column_indices as key and bwd_row_offset as the offset vector. Store the result in bwd_column_indices and bwd_eids.
Step 5: Append 0 at the start of the bwd_row_offset vector to fix the row_offsets that were shifted during count sort.

The resulting bwd_row_offset, bwd_column_indices and bwd_eids is the CSR for backward graph. Note there are no spaces in between elements here.

Results

T=9  | total_time: 0.0025091171264648438 | (edge_update_t) : 0.0014948844909667969  | graph_mod: 12415  | update_gpma_time: 0.0010815509594976902 | node_degrees_time: 2.0172999938949943e-05 | label_edges: 9.703636169433594e-05 | build_reverse_csr: 0.0009162425994873047 | (reverse_alloc): 2.509499972802587e-05 | (reverse_cum): 3.766300142160617e-05 | (reverse_count): 8.401300146942958e-05
T=8  | total_time: 0.0025725364685058594 | (edge_update_t) : 0.0022585391998291016  | graph_mod: 11390  | update_gpma_time: 0.0019348879577592015 | node_degrees_time: 2.2578000425710343e-05 | label_edges: 0.00013589859008789062 | build_reverse_csr: 0.0001766681671142578 | (reverse_alloc): 2.475300061632879e-05 | (reverse_cum): 4.7076999180717394e-05 | (reverse_count): 8.001900278031826e-05
T=7  | total_time: 0.002994537353515625 | (edge_update_t) : 0.002550840377807617  | graph_mod: 10450  | update_gpma_time: 0.0022359229624271393 | node_degrees_time: 2.3803000658517703e-05 | label_edges: 0.00013256072998046875 | build_reverse_csr: 0.00030994415283203125 | (reverse_alloc): 0.00016467500245198607 | (reverse_cum): 4.745000114780851e-05 | (reverse_count): 7.477799954358488e-05
T=6  | total_time: 0.001711130142211914 | (edge_update_t) : 0.0013616085052490234  | graph_mod: 9587  | update_gpma_time: 0.0011598470155149698 | node_degrees_time: 1.751200034050271e-05 | label_edges: 0.00010251998901367188 | build_reverse_csr: 0.0002465248107910156 | (reverse_alloc): 0.00012263900134712458 | (reverse_cum): 3.886199920088984e-05 | (reverse_count): 7.067599653964862e-05
T=5  | total_time: 0.0017185211181640625 | (edge_update_t) : 0.0015215873718261719  | graph_mod: 8795  | update_gpma_time: 0.0013253670185804367 | node_degrees_time: 1.7742999261827208e-05 | label_edges: 7.987022399902344e-05 | build_reverse_csr: 0.00011610984802246094 | (reverse_alloc): 1.2665999747696333e-05 | (reverse_cum): 2.9445000109262764e-05 | (reverse_count): 6.570100231328979e-05
T=4  | total_time: 0.0017838478088378906 | (edge_update_t) : 0.0015003681182861328  | graph_mod: 8069  | update_gpma_time: 0.0013012950075790286 | node_degrees_time: 1.7918999219546095e-05 | label_edges: 8.20159912109375e-05 | build_reverse_csr: 0.00020074844360351562 | (reverse_alloc): 9.451700316276401e-05 | (reverse_cum): 3.357999958097935e-05 | (reverse_count): 6.236499757505953e-05
T=3  | total_time: 0.0016067028045654297 | (edge_update_t) : 0.0013041496276855469  | graph_mod: 7403  | update_gpma_time: 0.00110587605740875 | node_degrees_time: 1.7207999917445704e-05 | label_edges: 7.891654968261719e-05 | build_reverse_csr: 0.00022292137145996094 | (reverse_alloc): 0.000113927002530545 | (reverse_cum): 3.5797998862108216e-05 | (reverse_count): 6.18819976807572e-05
T=2  | total_time: 0.0014882087707519531 | (edge_update_t) : 0.0012972354888916016  | graph_mod: 6791  | update_gpma_time: 0.0010969809954985976 | node_degrees_time: 1.732199962134473e-05 | label_edges: 7.843971252441406e-05 | build_reverse_csr: 0.00011205673217773438 | (reverse_alloc): 1.2706999768852256e-05 | (reverse_cum): 2.9848999474779703e-05 | (reverse_count): 6.142100028228015e-05
T=1  | total_time: 0.001476287841796875 | (edge_update_t) : 0.001291513442993164  | graph_mod: 6231  | update_gpma_time: 0.00110078405123204 | node_degrees_time: 1.7075000869226642e-05 | label_edges: 7.915496826171875e-05 | build_reverse_csr: 0.0001049041748046875 | (reverse_alloc): 1.1576000360946637e-05 | (reverse_cum): 2.879800013033673e-05 | (reverse_count): 5.677599983755499e-05

Verification

Performed verification by returning the edge along with the edge id and then comparing it with the graph from the dataset.

T=9  | total_time: NA | Correct: True
T=8  | total_time: 0.0018725395202636719 | Correct: True
T=7  | total_time: 0.002201557159423828 | Correct: True
T=6  | total_time: 0.004839420318603516 | Correct: True
T=5  | total_time: 0.0021767616271972656 | Correct: True
T=4  | total_time: 0.004418849945068359 | Correct: True
T=3  | total_time: 0.0023453235626220703 | Correct: True
T=2  | total_time: 0.0031099319458007812 | Correct: True
T=1  | total_time: 0.0029735565185546875 | Correct: True
T=0  | total_time: 0.002040386199951172 | Correct: True

[JoelMathewC]

Edge IDs for forward graph

We can run a parallel program such that each thread maps to one node and labels all the edges associated with that node. We can get the offset to be added to each label by using the cumulative sum of the out_degrees.

Results

T=0  | total_time: 0.014916419982910156 | (edge_update_t) : 0.01482701301574707  | graph_mod: 56650  | update_gpma_time: 0.014565997757017612 | node_degrees_time: 2.9226999686216004e-05 | label_edges: 8.893013000488281e-05
T=1  | total_time: 0.0018074512481689453 | (edge_update_t) : 0.0017271041870117188  | graph_mod: 6231  | update_gpma_time: 0.0015174379805102944 | node_degrees_time: 1.6682999557815492e-05 | label_edges: 8.0108642578125e-05
T=2  | total_time: 0.001795053482055664 | (edge_update_t) : 0.0017158985137939453  | graph_mod: 6791  | update_gpma_time: 0.0015155120054259896 | node_degrees_time: 1.6059999325079843e-05 | label_edges: 7.891654968261719e-05
T=3  | total_time: 0.001985311508178711 | (edge_update_t) : 0.0019078254699707031  | graph_mod: 7403  | update_gpma_time: 0.001715551014058292 | node_degrees_time: 1.7098000171245076e-05 | label_edges: 7.724761962890625e-05
T=4  | total_time: 0.002022266387939453 | (edge_update_t) : 0.0019443035125732422  | graph_mod: 8069  | update_gpma_time: 0.0017521439585834742 | node_degrees_time: 2.1376999939093366e-05 | label_edges: 7.772445678710938e-05
T=5  | total_time: 0.002086162567138672 | (edge_update_t) : 0.002009153366088867  | graph_mod: 8795  | update_gpma_time: 0.0018087630160152912 | node_degrees_time: 1.7031999959726818e-05 | label_edges: 7.677078247070312e-05
T=6  | total_time: 0.0022847652435302734 | (edge_update_t) : 0.002208232879638672  | graph_mod: 9587  | update_gpma_time: 0.002014285884797573 | node_degrees_time: 1.7491000107838772e-05 | label_edges: 7.62939453125e-05
T=7  | total_time: 0.0025124549865722656 | (edge_update_t) : 0.002434253692626953  | graph_mod: 10450  | update_gpma_time: 0.002241535112261772 | node_degrees_time: 1.751200034050271e-05 | label_edges: 7.796287536621094e-05
T=8  | total_time: 0.002752065658569336 | (edge_update_t) : 0.0026738643646240234  | graph_mod: 11390  | update_gpma_time: 0.0024721610825508833 | node_degrees_time: 1.786599932529498e-05 | label_edges: 7.796287536621094e-05
T=9  | total_time: 0.0027801990509033203 | (edge_update_t) : 0.002704620361328125  | graph_mod: 12415  | update_gpma_time: 0.0025077329482883215 | node_degrees_time: 1.7840999134932645e-05 | label_edges: 7.510185241699219e-05

I printed the output and it seems to be labeled correctly. However as stated in #57 the labeling of node 0 is causing edges with destination 0 to be ignored. That problem can be resolved at a later stage and will not affect the performance being evaluated in this discussion.

Verification

Performed verification by returning the edge along with the edge id and then comparing it with the graph from the dataset.

T=0  | total_time: 0.01624464988708496 | Correct: True
T=1  | total_time: 0.0031821727752685547 | Correct: True
T=2  | total_time: 0.002405405044555664 | Correct: True
T=3  | total_time: 0.0022933483123779297 | Correct: True
T=4  | total_time: 0.0032057762145996094 | Correct: True
T=5  | total_time: 0.0023849010467529297 | Correct: True
T=6  | total_time: 0.0035223960876464844 | Correct: True
T=7  | total_time: 0.0035665035247802734 | Correct: True
T=8  | total_time: 0.004163026809692383 | Correct: True
T=9  | total_time: 0.0031626224517822266 | Correct: True

[JoelMathewC]

Closing off

We have found quite an efficient solution. It may be noted that when we get time we must evaluate as to whether a node parallel or edge parallel approach is better for the count_sort logic. For all other purposes this discussion is closed.