quicksort算法超速超線性

Question

我已經實現了快速排序的順序版本和並行版本。

我用來驗證加速快速排序的最壞情況爲我實現：源陣列已經排序，並在我的情況樞軸始終是數組的第一個元素。

因此，分區會生成兩個集合，其中一個包含比pivot更小的元素，另一個包含高於pivot的元素，即n-1個元素，其中n是作爲快速排序參數傳遞的數組的元素數功能。遞歸深度的大小爲N -1，其中N是作爲快速排序函數參數傳遞的原始數組的元素數。

觀測值：該組由含有初始和correspondends陣列部分的最終位置的兩個變量實際上表示任一元素比樞軸小，元素比樞軸更高。整個部門正在發生，意味着在過程中不會創建新陣列。並行版本中並行順序的差異在多個數組之間被平均劃分（按照順序情況排序）的情況下創建多個數組。對於並行情況下元素的交點，使用算法合併。

獲得的加速比理論值要高，這意味着兩個線程的加速比順序版本要多2倍（3倍更精確），4個線程的加速比是10倍。

，我跑了線程計算機運行的是Ubuntu Linux操作系統的10.04，爲64位，如果我沒看錯的4個核機器（羿龍II X4）。編譯器是gcc 4.4，沒有爲編譯器傳遞標誌，除了包含用於並行實現的庫pthread;

那麼，有人知道超線性加速的原因達到了嗎？有人可以給我一些指針嗎？

Answer 1

這真的是最好使用一些性能分析器鑽研 對此進行了更詳細，但我的第一個猜測是，這種超級 線性加速通過的事實，你得到更多的緩存空間 如果造成你添加線程。這樣，將從緩存中讀取更多數據。 由於內存傳輸的成本非常高，因此可以很容易地提高性能。

你使用Amdahl's law來評估你的最大加速？

希望這會有所幫助。

Answer 2

如果你看到兩個線程相對於一個線程的3倍速度提升，以及四個線程相對於一個線程的10倍速度提升，那麼可怕的事情正在發生。 Amdahl定律指出加速比爲1 /（1-P + P/S），其中P是算法的平行部分，S是並行部分的加速因子。假設四個核心的S = 4（最好的結果），我們發現P = 2.5，這是不可能的（它必須在0和1之間）。

換句話說，如果你能得到提高了10倍，4個核，那麼你可以簡單地用一個內核來模擬四個核心，仍然可以得到2.5倍的改善（或左右）。換句話說，在一秒鐘內，四個核心在十秒鐘內執行的操作比一個核心少。因此，並行版本實際上執行的操作較少，如果是這種情況，沒有理由說明串行版本無法執行較少的操作。

可能的結論：

• 東西可能是錯了你的串行版本。也許它是優化不佳。

• 你的平行版本可能有問題。他們可能是不正確的。

• 測量結果可能不正確。這很常見。

不可能的結論：

• 該算法超線性縮放。