如何在多GPU上實現基數排序？

Question

如何在多GPU上實現基數排序 - 與在單GPU上相同的方式，即分割數據，然後在單獨的GPU上構建直方圖，然後使用合併數據（如一堆卡片）？

Answer 1

該方法可行，但我認爲這不是最快的方法。具體來說，爲每K位（K = 4當前最好）合併直方圖將需要在GPU 32/K = 8次之間交換密鑰以對32位整數進行排序。由於GPU之間的內存帶寬（〜5GB/s）遠低於GPU上的內存帶寬（〜150GB/s），因此會導致性能下降。

較好的策略是將數據拆分成多個部分，在不同的GPU並聯每個部分進行排序，並且然後在最後一次合併的部件。這種方法只需要一次GPU間傳輸（與上面的8相比），因此速度會更快。

Answer 2

不幸的是，這個問題沒有充分提出。它取決於元素大小，元素在內存中的開始位置，以及希望排序元素最終駐留的位置。

有時有可能通過存儲組中的元素共享同一個共同的前綴壓縮排序列表，或者你可以在飛行中的獨特元素，在排序列表一旦存儲每個元件都具有相關的計數。例如，您可以將32位整數的大量列表分類到64位不同的16位值列表中，將您的內存需求減半。

總的原則是，你想最少數量越過數據越好，你的吞吐量將幾乎總是對應於帶寬，存儲策略相關聯的約束。

如果您的數據集超過了快速存儲器的大小，你可能想用合併傳球來完成，而不是繼續那種板藍根，另一個人已經回答了。

我剛剛進入GPU架構，我不明白上面的K = 4註釋。我從來沒有見過一個體繫結構，但是這樣一個小K會證明是最優的。

我懷疑合併直方圖也是錯誤的方法。我可能會讓元素在內存中碎片而不是合併直方圖。 GPU架構中的中尺度分散/收集列表難以管理嗎？我當然不希望。最後，很難想象爲什麼你會想要讓這個任務涉及多個GPU的原因。假設你的卡有2GB的內存和60GB/s的寫入帶寬（這就是我的中檔卡所顯示的）。三遍基數排序（11位直方圖）需要6GB的寫入帶寬（可能是您的速率限制因子），或者需要大約100ms來排序2GB的32位整數列表。太棒了，他們已經排序了，現在呢？如果您需要將它們運送到其他地方而沒有進行某種預處理或壓縮，分揀時間將會是小魚。

無論如何，今天剛編好我的第一個例子程序。還有很多東西需要學習。我的目標應用程序是排列密集型的，這與排序密切相關。我相信我將來會再次考慮這個問題。