問題的初步處理

編輯

PSRS算法(Parallel Sorting by Regular Sampling):首先設待處理里序列長n,並行機上有p個處理器。為了使問題簡單,我們假設n是p的整倍數。於是將這n個元素劃分為p段,每段中有n/p個元素,將這p段分給p個處理器。注意,執行PSRS算法的並行機必須是多指令流多數據流(MIMD)的。

算法描述

編輯
  1. 讓各個處理器並行的調用串行排序算法進行局部排序;
  2. 從每個有序段中選p個樣本元素,共 個樣本元素(採樣);、
  3. 對樣本元數排序;
  4. 從樣本元素中選p-1作為劃分元素,並播送給其餘的處理器;
  5. 各個處理器根據劃分元素對局部序列進行劃分(分為p段);
  6. 各個處理器將每一段按段號交換到相應序列號的處理器;
  7. 在各個處理器中使用串行算法再次進行局部排序。

算法分析

編輯

如果注意到一個好的串行排序算法的時間複雜度為 那麼,容易證得上述PSRS算法的時間複雜度在 時為 

缺點:我們注意到,在第五步進行主元劃分時時可能會引起不均勻性,即位於某兩個主元之間的元素可能要多一些(多於 個)。我們可以證明,在算法中進行到第六步全局交換時,可能會有某一個處理器中數據達到 個;這樣引起的直接後果是處理器負載不均勻,那麼在歸併排序中可能會引起排序時間的不均勻。

參閱

編輯

並行計算 並行排序