使用Pthreads並行化Quicksort無法獲得任何加速

我在使用Pthreads爲列表分割成右側和左側一半（小於和大於數據透視表）之後爲每個分區創建一個新的階段。我遞歸地做這件事，直到我達到允許線程的最大數量。使用Pthreads並行化Quicksort無法獲得任何加速

當我使用printfs來跟蹤程序中發生的事情時，我清楚地看到每個線程都在並行執行委派的工作。但是使用單個進程總是最快的。只要我嘗試使用更多的線程，完成幾乎雙打所花費的時間，並隨着線程數的增加而增加。

我被允許在服務器上運行多達16個處理器。

該算法如下所示：將元素與主元素進行比較，將數組分割爲左和右。爲左側和右側開始一個新線程，並等待線程返回。如果有更多的可用線程，他們可以創建更多的遞歸。每個線程都等待其子加入。

一切都對我有意義，而且排序工作完美，但更多的線程使其非常緩慢。

我試着爲每個分區設置一個最小數量的元素來啓動線程（例如50000）。

我嘗試了一種方法，當一個線程完成時，它允許啓動另一個線程，從而導致數百個線程開始和完成整個過程。我認爲開銷太大了。所以我擺脫了這一點，如果一個線程完成執行，則不會創建新線程。我有更多的加速，但仍然比單個進程慢很多。

我使用的代碼如下。

http://pastebin.com/UaGsjcq2

沒有任何人有任何線索，以什麼我可以做錯了什麼？

來源

2010-06-07 Murat Ayfer

嘗試將'num_processes'設置爲2並查看會發生什麼。 – Brian 2010-06-07 14:18:23

啓動一個線程有相當多的開銷。你最好創建一個具有固定數量線程的線程池，以及一個線程安全隊列，以便爲線程排隊工作。線程等待隊列中的項目，處理該項目，然後等待另一個項目。如果你想真正做到這一點，這應該是一個優先級隊列，其排序基於分區的大小（所以你總是先排序最小的分區，以防止隊列大小過大）。

這至少可以減少啓動線程的開銷 - 但這仍然無法保證您的性能會比單線程版本高。特別是，快速排序對CPU本身的工作量不夠，可能幾乎完全受到內存帶寬的限制。一次處理多個分區可能會傷害緩存局部性，以至於在任何情況下都會失去速度。

來源

2010-06-07 13:57:03

+1 - 雖然我懷疑緩存局部性問題。基本上，只要每個線程處理一個實質性的分區，大多數訪問都是順序的，所以緩存處理不好的範圍應該很小。也就是說，50,000個整數在小方面稍微有點（很容易放入CPU緩存中，太小而不能充分利用緩存的外層），但頁面大小可能是真正的問題，但我不知道它有多大這些天。儘管如此，如果您的內存帶寬得到充分利用，多線程並不能提供幫助 - 並且可能意味着更多的代碼浪費了緩存空間。 – Steve314 2010-06-07 14:09:21

+1 - 聽起來不錯 - 好像它是從多年的經驗中產生的。 – Jacob 2010-06-07 14:24:52

@Jacob：好的，無論如何，我一直在做這些東西 - 我只是希望這真的是多年的經驗，而不是一年的經驗重複了一堆...... – 2010-06-07 14:29:34

首先猜測是創建，銷燬，特別是同步你的線程將吃掉並且可能獲得的收益取決於你正在排序的元素數量。我實際上猜測，彌補開銷需要相當長的一段時間，而且可能無法彌補。

因爲你有你的排序方式，你有1個線程在等待另一個等待另一個...你並沒有真正得到那麼多的並行性開始。你最好使用更線性的排序方式，或許就像一個Radix，它將線程分割爲更多的數據。這仍然有一個線程等待其他線程，但至少線程可以在同一時間做更多的工作。但是，即使這樣，我也不認爲線程會有太多幫助。

來源

2010-06-07 13:57:12

我只是看看你的代碼。我得到了一個評論。你爲什麼使用鎖定。如果我明白你正在做的是一樣的東西：

quickSort(array) 
{ 
    left, right = partition(array); 
    newThread(quickSort(left)); 
    newThread(quickSort(right)); 
}

你不應該需要鎖。通常，每次調用快速排序都不會訪問數組的其他部分。所以不涉及共享。

來源

2010-06-07 14:08:28 mathk

也許他正在返回索引到一個現有的數組而不是創建一個新的子數組。 – Jacob 2010-06-07 14:23:09

該鎖用於遞增全局變量，用於跟蹤使用多少個線程。 – 2010-06-07 15:04:26

我敢打賭，只要將遞歸級別參數添加到算法並創建新線程，當且僅當遞歸級別不太深時纔會更好。這樣你就不會伴隨鎖的每一個遞歸調用......在較低的級別意味着你的所有線程都爭用讀取你的thread_count變量。我會盡量嘗試1級遞歸，儘管這隻會產生2個線程而不是最大值。 – Brian 2010-06-07 21:48:50

除非每個線程運行在單獨的處理器或核心上，否則它們不會真正併發運行，並且上下文切換時間會很長。線程的數量應限制在可用執行單元的數量上，即使這樣你也必須相信操作系統會將它們分配給單獨的處理器/內核，如果它們也被用於其他進程，它們可能不會這樣做。

另外，您應該使用靜態線程池，而不是動態創建和銷燬線程。創建/銷燬線程包括從堆中分配/釋放堆棧，這是非確定性的並且可能非常耗時。

最後是服務器真正的或虛擬機上的16個處理器？它們是否專門分配給您的流程？

來源

2010-06-07 21:43:10 Clifford

使用Pthreads並行化Quicksort無法獲得任何加速

回答

相關問題