最优并行排序算法

An Optimal Parallel Sorting Algorithm

本文考虑在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.