SIM-DEREW模型上的最优并行排序算法

OPTIMAL SIMD-EREW PARALLEL SORTING ALGORITHMS

给出两种在 SIMD EREW计算模型上的最优并行排序算法 .为了避免存储访问冲突 ,算法采用了基于并行归并的并行排序方法 .对于长度为 n的序列 ,在 nε 个处理单元上 ,算法的排序时间为O( n1-εlb n) ,成本为 O( n lb n) ,已达到了最优 。

Optimal parallel sorting algorithms on SIMDEREW are presented. To avoid memory access conflict, the algorithms are based on a parallel merge algorithm. For a sequence with n elements, the time complexity of the algorithms is O(n 1-ε lb n) if processed on n ε processors. The cost is O(n lb n) which is optimal for sorting and the parallel algorithm is self-adapting.