.png){kind=icon}
返回
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}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们提出了一种实用的非递归并行列表排序算法NR-Ranking。NR-Ranking采用独立集来避免邻居节点间的潜在操作冲突。在每个通信轮次中，独立集中的每个节点通过添加新的距离边桥接其左邻居和右邻居，然后该独立集中的所有节点从之前的链表中排除。一个节点被选入独立集的概率约为1/3。根据选择独立集的停止准则，NR-Ranking的通信轮次数不同。如果选择步骤在剩余链表中的节点数少于n/p时停止，则通信轮次数界于log(p)，其中n是链表中的节点数，p是处理器数量；或者如果剩余链表中的所有节点都是端节点，则通信轮次数为O(logw)，其中w是最长链表的长度。在两种停止准则下，计算和通信的复杂度均界于O(n)。实验结果证实了上述复杂度分析，并且NR-Ranking在GPS中的实现当工作线程数从8增加到48时，实现了4倍的加速。
Keyword:
list ranking
independent set
non-recursive
parallel algorithm
期刊
B
IF:
0
论文数:
32
被引数:
0
机构
引用论文
分享收藏
List ranking and list scan on the Cray C-90.png)
Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures - SPAA '94
Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures - SPAA '94IF0
PREAI
分享收藏Better trade-offs for parallel list rankingProceedings of the ninth annual ACM symposium on Parallel algorithms and architectures - SPAA '97
Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures - SPAA '97IF0
PREAI
分享收藏GPSProceedings of the 25th International Conference on Scientific and Statistical Database Management
Proceedings of the 25th International Conference on Scientific and Statistical Database ManagementIF0
PREAI
分享收藏
查看更多内容