.png){kind=icon}
.png){kind=icon}
Return
An Efficient Parallel List Ranking Algorithm for Graph Concatenation on BSP Graph System
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0695-8_22.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We proposed a practical non-recursive parallel list ranking algorithm, NR-Ranking. NR-Ranking adopts an independent set to avoid potential operation contention between neighbor nodes. In each communication round, every node in an independent set bridges its left neighbor and right neighbor by adding edges with new distance; then all nodes in this independent set are excluded from previous linked lists. The probability of one node being selected into the independent set is about 1/3. According to the stop criterion of selecting an independent set, the number of communication rounds of NR-Ranking is different. It is bounded by log(p) if the selection step stops when the number of nodes in the reminder lists is less than n/p, where n is the number of nodes in the linked lists and p is the number of processors, or O(logw) if all nodes in the remaining lists are end nodes, where w is the length of the longest linked list. The complexity of computation and communication on both stop criteria is bounded by O(n). Experimental results confirm the above complexity analysis, and the implementation of NR-Ranking in GPS has achieved a speed increase of 4X when the number of workers increases from 8 to 48.
Keywords:
list ranking
independent set
non-recursive
parallel algorithm
Journal
B
IF:
0
Papers:
32
Citations:
0
Organization
View more organizations