Communication-Efficient Parallel Sorting
Communication-Efficient Parallel Sorting
复制标题
高效通信的并行排序
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
M. Goodrich
中科院分区：
文献类型：
--
作者：
M. Goodrich
我们研究了在P处理器批量同步平行（BSP）计算机上对N数字进行排序的问题，该计算机是一个平行的多计算机，允许每种处理器在任何HOM中发送和接收到任何HO圆形的。我们提供了使用内部计算时间的并行排序方法，即$ o（{n \ log n \ fos p}）$和许多通信回合，即$ o（{\ log n \ fos \ log \ log（h+1） }）$ for $ h = \ theta（n/p）$。内部计算结合对于任何基于比较的分类算法都是最佳的。此外，当$ p \ le n^{1- {1/c}} $对于常数$ c \ ge 1 $时，通信回合的数量受（实际）情况的常数为界。实际上，我们表明，我们对通信循环的界限对于P的全范围值是渐近的，因为我们表明，仅计算均匀分布到第一个O（N/H）的N位的“或”位的“或”。 BSP计算机中任意数量的处理器需要$ \ omega（\ log n/\ log（h+1））$通信回合。
We study the problem of sorting n numbers on a p-processor bulk-synchronous parallel (BSP) computer, which is a parallel multicomputer that allows for general processor-to-processor communication rounds provided each processor sends and receives at most h items in any round. We provide parallel sorting methods that use internal computation time that is $O({n\log n \over p})$ and a number of communication rounds that is $O({\log n \over \log (h+1)})$ for $h=\Theta(n/p)$. The internal computation bound is optimal for any comparison-based sorting algorithm. Moreover, the number of communication rounds is bounded by a constant for the (practical) situations when $p\le n^{1-{1/c}}$ for a constant $c\ge 1$. In fact, we show that our bound on the number of communication rounds is asymptotically optimal for the full range of values for p, for we show that just computing the "or" of n bits distributed evenly to the first O(n/h) of an arbitrary number of processors in a BSP computer requires $\Omega(\log n/\log (h+1))$ communication rounds.