是否可以使用CUDA來有效計算排序數組內的元素的頻率？

Question

我對Cuda很新，我從書中閱讀了幾章，並在線閱讀了很多教程。我已經對矢量加法和乘法做了我自己的實現。

我想進一步移動一下，所以我們假設我們要實現一個函數，該函數將一個有序的整數數組作爲輸入。

我們的目標是找到數組中每個整數的頻率。

依次我們可以掃描陣列一次以產生輸出。時間複雜度將是O(n)。

由於組別不同，我認爲必須有可能利用CUDA。

假設這是陣列

1 
    1 
    1 
    1 
    2 
    2 
    3 
    3 
    5 
    5 
    6 
    7 

爲了實現完全並行，每個線程必須知道它是爲了找到和掃描陣列的到底是哪一部分。這隻有在我們使用另一個名爲int dataPosPerThread[]的數組時才能實現，該數組對於每個線程標識dataPosPerThread[threadId]將具有值作爲初始數組上的起始位置。所以，這意味着每個線程都會知道從哪裏開始以及在哪裏完成。

然而，這樣我們不會獲得任何收益，因爲它會花費我們O(n)時間才能找到職位。最終總成本將爲O(n) + cost_to_transfer_the_data_to_the_gpu + O(c) + cost_to_transfer_the_results_to_the_gpu 其中O(c)是線程找到最終輸出所需的常量時間，假設當然我們在初始數組內有許多不同的整數。

我想避免額外的O(n)的成本。

什麼我想過到目前爲止，具有尺寸arraySize的數組，我們指定要使用的線程的總量，假設totalAmountOfThreads這意味着每個線程都有掃描totalAmountOfThreads/arraySize值。

第一個線程（id 0）將從位置0開始掃描，直到位置totalAmountOfThreads/arraySize。

第二個線程將從totalAmountOfThreads/arraySize + 1開始依此類推。

問題是，某些線程可能正在使用不同的整數組，或者有一個組有更多的值正在被其他線程處理。比如在上面的例子，如果我們假設，我們將有6個線程，每個線程將採取2個達陣整數，所以我們有這樣的事情：

1  <-------- thread 0 
    1 
    1  <-------- thread 1 
    1 
    2  <-------- thread 2 
    2 
    3  <-------- thread 3 
    3 
    5  <-------- thread 4 
    5 
    6  <-------- thread 5 
    7 

正如你可以看到線程0只1值，但是線程2正在處理其他1值。爲了實現並行性，這些線程必須處理不相關的數據。假設我們將使用這個邏輯，每個線程將計算結果如下：

thread 0 => {value=1, total=2} 
    thread 1 => {value=1, total=2} 
    thread 2 => {value=2, total=2} 
    thread 3 => {value=3, total=2} 
    thread 4 => {value=5, total=2} 
    thread 5 => {{value=6, total=1}, {value=7, total=1}} 

有了這個結果有什麼方法可以進一步實現？有人可能會建議使用額外的hash_map，如unordered_map，它可以有效地更新由單個線程計算的每個值的總變量。然而

1. Unordered_map不被CUDA編譯器

2. 這將意味着線程將不能夠充分利用共享內存，因爲從不同的塊兩個線程可以用相同的價值觀來工作的支持，所以哈希映射必須位於全局內存中。

3. 即使上述兩個問題沒有問題，我們在更新哈希映射時仍然會在線程之間存在競爭條件。

什麼是解決這個問題的好方法？

預先感謝您

Answer 1

正如@tera已經指出的那樣，什麼你所描述的是一個直方圖。

你可能會感興趣thrust histogram sample code。如果我們以dense_histogram()例程爲例，您會注意到第一步是對數據進行排序。

所以，是的，您的數據排序的事實將爲您節省一個步驟。

簡而言之，我們有：

1. 排序數據
2. 數據
3. 計算邊界之間的距離內的標記不同元件的邊界。

如示例代碼所示，推力可以在單個函數中執行上述每個步驟。由於您的數據已排序，因此可以有效地跳過第一步。