摘要
本文考虑在P台机上对n元序列的排序算法。[2]给出了一种效率O(1)的算法(除串行算法外,它是最优的),需O(log n)台处理机和O(n)步。本文给出了一种效率O(1)的并行排序算法,需O(n^(1/2))台处理机和O(n^(1/2)logn)个并行步,显著地改进了[2]的结果。
The problem of sorting a sequence of n elements on a parallel computer with p processors is considered. [2] shows an algorithm of speed-up ratio of p for p≤log n. The algorithms we present can all be run on a single-instruction stream multiple-data stream computer For p≤n^(1/2), each achieves a speed-up ratio of p which is optimal in the number of processors used.
出处
《计算机研究与发展》
EI
CSCD
北大核心
1990年第6期40-42,49,共4页
Journal of Computer Research and Development