PSRS算法
维基百科,自由的百科全书
目录 |
[编辑] 问题的初步处理
PSRS算法(Parallel Sorting by Regular Sampling):首先设待处理里序列长n,并行机上有p个处理器。为了使问题简单,我们假设n是p的整倍数。于是将这n个元素划分为p段,每段中有n/p个元素,将这p段分给n个处理器。注意,执行PSRS算法的并行机必须是多指令流多数据流(MIMD)的。
[编辑] 算法描述
- 让各个处理器并行的调用串行排序算法进行局部排序;
- 从每个有序段中选p个样本元素,共p2个样本元素(采样);、
- 对样本元数排序;
- 从样本元素中选p-1作为划分元素,并播送给其余的处理器;
- 各个处理器根据划分元素对局部序列进行划分(分为p段);
- 各个处理器将每一段按段号交换到相应序列号的处理器;
- 在各个处理器中使用串行算法再次进行局部排序。
[编辑] 算法分析
如果注意到一个好的串行排序算法的时间复杂度为O(nlogn)那么,容易证得上述PSRS算法的时间复杂度在n > p3时为。
缺点 我们注意到,在第五步进行主元划分时时可能会引起不均匀性,即位于某两个主元之间的元素可能要多一些(多于个)。我们可以证明,在算法中进行到第六步全局交换时,可能会有某一个处理器中数据达到}-个;这样引起的直接后果是处理器负载不均匀,那么在归并排序中可能会引起排序时间的不均匀。