.png){kind=icon}
返回
Practical parallel list ranking
.png){kind=icon}
PRE
AI
DOI：10.1006/jpdc.1998.1508.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Parallel list ranking is a hard problem due to its extreme degree of irregularity. Also, because of its linear sequential complexity, it requires considerable effort just to reach speed-up one (break even). In this paper, we address the question of how to solve the list-ranking problem for lists of length up to 2x10(8) in practice: we consider implementations on the Intel Paragon, whose PUs are laid out as a grid. It turns out that pointer jumping, independent-set removal, and sparse ruling sets all have practical importance for current systems. For the sparse-ruling-set algorithm the speed-up strongly increases with the number ii of nodes per PU, finally reaching 27 with 100 PUs, for k = 2 x 10(6). (C) 1999 Academic Press.
Keyword:
algorithms
parallel list ranking
implementations
routing operations
speed-up
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
机构
暂无机构信息
.png){kind=icon}
没有更多内容