（什麼時候）是平行排序實用的，你如何編寫一個高效的排序？

我正在研究D編程語言的並行化庫。現在我對基本原語（並行foreach，map，reduce和tasks/futures）非常滿意，我開始考慮一些更高級別的並行算法。並行化的更明顯的候選者是排序。（什麼時候）是平行排序實用的，你如何編寫一個高效的排序？

我的第一個問題是，排序算法的並行化版本是否適用於真實世界，還是他們主要是學術？如果它們有用，它們在哪裏有用？我個人很少在我的工作中使用它們，僅僅是因爲我通常使用比單個sort（）調用更粗糙的並行度級別將所有內核全部綁定到100％。其次，似乎快速排序對於大型陣列來說幾乎是尷尬的平行，但我不能得到我認爲我應該得到的近線性加速。對於快速排序，唯一固有的串行部分是第一個分區。我試着在每個分區後並行排序兩個子陣列，並行化快速排序。在簡化的僞代碼：

// I tweaked this number a bunch. Anything smaller than this and the 
// overhead is smaller than the parallelization gains. 
const smallestToParallelize = 500; 

void quickSort(T)(T[] array) { 
    if(array.length < someConstant) { 
     insertionSort(array); 
     return; 
    } 

    size_t pivotPosition = partition(array); 

    if(array.length >= smallestToParallelize) { 
     // Sort left subarray in a task pool thread. 
     auto myTask = taskPool.execute(quickSort(array[0..pivotPosition])); 
     quickSort(array[pivotPosition + 1..$]); 
     myTask.workWait(); 
    } else { 
     // Regular serial quick sort. 
     quickSort(array[0..pivotPosition]); 
     quickSort(array[pivotPosition + 1..$]); 
    } 
}

即使對於非常大的陣列，其中第一個分區佔用的時間可以忽略不計，我只能得到大約在雙核30％的增速相比，該算法的純串行版本。我猜測瓶頸是共享內存訪問。任何關於如何消除這個瓶頸或其他瓶頸可能的見解？

編輯：我的任務池有固定數量的線程，等於系統中的核心數減1（因爲主線程也工作）。此外，我正在使用的等待類型是工作等待，即如果任務已啓動但未完成，調用workWait()的線程會將其他作業從池中取走並執行，直至完成等待。如果任務未啓動，則在當前線程中完成。這意味着等待不是低效的。只要有工作要做，所有的線程都會保持忙碌。

來源

2010-02-13 dsimcha

我不知道如何讓自己快速排序並行較好，但有一個叫samplesort變體，它天生就比一個香草快速排序快得多，而據我所看到的，應該同樣可並行化。 –

請記住我不是並行排序的專家，讓鄉親們研究事業進行並行排序的，但...

1）是他們在現實世界中是有用的。

當然他們是，如果你需要排序昂貴的東西（如字符串或更糟糕的），而你不是釘住所有的核心。

認爲，你需要根據上下文來排序字符串的大動態一覽UI代碼
覺得有點像巴恩斯小屋正體卡，你需要的粒子進行排序

2）Quicksort好像會提供線性加速，但事實並非如此。分區步驟是一個連續的瓶頸，如果你是個人資料，你會看到這一點，它會在四核心上2-3倍。

如果你想在較小的系統上獲得很好的加速性能，你需要確保你的每個任務的開銷非常小，理想情況下，你會希望確保你沒有太多的線程運行，也就是說， 2在雙核上。線程池可能不是正確的抽象。

如果你想在一個更大的系統上獲得很好的加速，你需要看看基於掃描的並行排序，這裏有一些論文。雙音排序也很容易並行排列。並行基數排序也很有用，PPL中有一個（如果您不反對Visual Studio 11）。

來源

2010-02-13 23:24:14 Rick

我不是專家，但 ...這裏是我想看看是什麼在：作爲一個經驗法則，算法，看看小位

首先，我聽說過從一開始就存在的問題往往會更好地用作並行算法。看看你的實現，嘗試使並行/串行開關轉向另一種方式：對數組進行分區並排序，直到你有N段，然後進入串行。如果您或多或少地爲每個並行案例抓取新線程，那麼N應該是您的核心數量。 OTOH如果你的線程池的大小是固定的，並且作爲一個短命的代理隊列，那麼我會使用你核心數量的N〜2 +倍（這樣核心就不會閒置，因爲一個分區完成得更快）。

其它的改進：

跳過myTask.wait();在地方一級和相當有所有的任務等待的包裝功能。
對函數進行單獨的串行實現，避免進行深度檢查。

來源

2010-02-14 00:50:09 BCS

+1。很好的解釋.. – bragboy

「我的第一個問題是，在現實世界中有用的排序算法的並行版本」 - 取決於您在實際工作中正在處理的數據集的大小。對於小數據集，答案是否定的。對於較大的數據集，它不僅取決於數據集的大小，還取決於系統的特定體系結構。

阻止預期性能提高的限制因素之一是系統的緩存佈局。如果數據可以放入內核的L1緩存中，那麼通過在多個內核之間進行排序幾乎沒有什麼好處，因爲您會在排序算法的每次迭代之間造成L1緩存缺失的懲罰。

相同的推理適用於具有多個L2高速緩存和NUMA（非統一內存訪問）體系結構的芯片。因此，您希望將更多核心分配到整個分區中，因此需要相應地增加smallestToParallelize常量。

您確定的另一個限制因素是共享內存訪問或內存總線上的爭用。由於存儲器總線每秒只能滿足一定數量的存儲器存取，有額外的內核基本上不做任何事情，但是讀寫主內存會給內存系統帶來很大的壓力。

我應該指出的最後一個因素是線程池本身，因爲它可能不如您想象的那麼高效。由於您擁有從共享隊列中竊取和生成工作的線程，因此該隊列需要同步方法;並且取決於如何實現它們，它們可能會在代碼中導致非常長的連續部分。

來源

2010-02-18 01:23:05 Mark

我不知道答案，這裏是適用任何再或者，如果我的建議是適用於D.

反正...

假設d允許的話，總是有提供的可能性對高速緩存預取提示。有問題的核心請求將它很快（不是立即）的數據加載到某個緩存級別。在理想情況下，數據將在覈心開始工作時取回。更有可能的是，預取過程將會或多或少地處於至少會導致較少等待狀態的方式，而不是如果數據被取出爲「冷的」。「

您仍然受到整個緩存到內存吞吐量的限制，因此您需要組織數據，以便核心的獨佔緩存中包含大量數據，以便可以花費相當多的數據需要寫更新後的數據

代碼和數據需要按照高速緩存中最小的單元的高速緩存行（每個64字節的提取單元）的概念進行組織，這應該會導致在這兩個核心的工作需要安排使得存儲系統的工作原理一半每核高達（假設100％的可擴展性），如之前當只有一個核心在工作，工作還沒有組織的。對於四個核的四分之一儘可能多的，這是一個相當大的挑戰，但決不是不可能的，它只是依賴關於你在重組工作方面的想象力。與往常一樣，有些解決方案無法構想...直到有人這樣做！

我不知道WYSIWYG D如何與C語言進行比較 - 但我總體上認爲開發人員在其實際機器代碼生成中影響編譯器的程度可以改善開發可擴展應用程序的過程。對於解釋型語言來說，口譯員會進行如此多的記憶工作，所以你可能無法辨別出一般「背景噪音」的改進。

我曾經寫過一個多線程的希爾排序比對與一個三芯之一，100％跑70％的速度在兩個核心。四個核心運行速度比三個慢。所以我知道你面對的困境。

來源

2012-03-07 14:47:37

我想你指向外部排序[1]面對類似的問題。通常情況下，這類算法大多采用以應對大量的數據，但他們的主要觀點是，他們分手了大塊成更小的和無關的問題，這是因此真正偉大的並行運行。您「只」需要將部分結果之後縫合在一起，這並不完全平行（但與實際分類相比相對便宜）。

外部合併排序也將與線程的數量不明的工作非常好。你可以任意分割工作負載，並且每當有一個空閒的時候，給每個線程分配n個元素，直到你所有的工作單元完成，然後你就可以開始加入它們。

[1] http://en.wikipedia.org/wiki/External_sorting

來源

2012-03-07 15:00:17

（什麼時候）是平行排序實用的，你如何編寫一個高效的排序？

回答

相關問題