Optimal Parallel Lexicographic Sorting using a Fine-Grained Decomposition
Optimal Parallel Lexicographic Sorting using a Fine-Grained Decomposition
复制标题
使用细粒度分解的最佳并行词典排序
DOI：
--
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
P. Varshney
中科院分区：
文献类型：
--
作者：
Ramachandran Vaidyanathan;C. Hartmann;P. Varshney
虽然像基数排序这样的基于非比较的排序技术可以比传统的基于比较的方法做得更少，但它们不用于长键。这是因为即使并行基数排序算法并行处理键，键中的符号也是顺序处理的。在这份报告中，我们给出了一个最佳的算法字典排序，可用于排序n m位的关键EREW模型在8（log n log m）的时间与8（MN）的“工作”。该算法不仅与任何基于非比较的最优算法一样快，而且可以以更少的工作量执行。我们还使用所提出的算法表明，如果n-8（log n）无符号二进制数可以排序最佳的EREW PRAM比n无符号二进制数的长度不受限制的EREW PRAM可以排序最佳。
Though non-comparison based sorting techniques like radix sorting can be done with less "work" than conventional comparison-based methods, they are not used for long keys. This is because even though parallel radix sorting algorithms process the keys in parallel, the symbols in the keys are processed sequentially. In this report, we give an optimal algorithm for lexicographic sorting that can be used to sort n m-bit keys on an EREW model in 8(log n log m) time with 8( mn) "work". This algorithm is not only as fast as any optimal non-comparison based algorithm, but can also be executed with less work. We also use the proposed algorithm to show that if n 8(log n) unsigned binary numbers can be sorted optimally on an EREW PRAM than n unsigned binary numbers of unrestricted length can be sorted optimally on an EREW PRAM.