有沒有一種很好的方法在cuda上使用只讀hashmap？

我對編程和Cuda非常陌生，所以很抱歉，如果這非常明顯。基本上我有一個C函數，讀取數據列表，然後檢查每個項目與hashmap（我在C中使用uthash）。它工作的很好，但我想在Cuda中運行這個過程（一旦它獲得了散列鍵的值，然後它做了很多處理），但我不確定創建只讀散列函數的最佳方式，儘可能快在Cuda。有沒有一種很好的方法在cuda上使用只讀hashmap？

背景：

基本上我試圖儘可能快地珍惜一個非常非常大批量的組合。我總是獲得數百萬個投資組合，這些投資組合以兩個名單的形式出現一個有股票名稱，另一個有重量。然後，我使用股票名稱來查找散列表以獲取其他數據（值，％更改等），然後根據權重對其進行處理。在普通C中的CPU上，大約需要8分鐘，所以我在GPU上試用它很有趣。我已經閱讀並完成了cuda by example中的示例，所以我相信我知道除了散列函數之外，大部分內容都是如何做的（附錄中有一個，但它似乎專注於添加到它，而我只是真的希望它作爲參考，因爲它我可能會在cuda for example的邊緣粗糙，所以也許有些東西我錯過了，這對我在這種情況下很有幫助，就像使用文本或某種特殊形式的內存一樣）。我應該如何構建這個最好的結果，如果每個塊都有自己的訪問hashmap，或者應該每個線程或一個足夠好的整個GPU？

任何想法，例子或資源，以更好地理解這一點會很好。

謝謝！

編輯：抱歉只是澄清，我只使用C.最壞的情況，我願意使用另一種語言，但理想情況下，我想我可以只在本地投入GPU一次，並擁有所有未來的線程因爲要處理我的數據，所以我需要在幾個大批量中完成）。

來源

2012-06-08 Lostsoul

從哈希表中讀取數據後，您會執行多少非內存查找處理？ – huon

@dbaupp不是很大，這是一個問題。羅傑能夠幫助我取得有利的結果。 – Lostsoul

很高興聽到:) – huon

這是關於在GPU上使用哈希映射的潛在性能問題的一些想法，以備份我關於在CPU上保留哈希映射的評論。

NVIDIA GPU以32個線程組成的線程運行線程，稱爲warps。爲了獲得良好的性能，變形中的每個線程都必須做基本相同的事情。也就是說，他們必須運行相同的指令，並且他們必須從彼此接近的內存位置讀取數據。

我認爲哈希映射可能會違反這兩條規則，可能會導致GPU速度變慢，導致在GPU上保留哈希映射沒有用處。

時需要考慮32個線程在運行經線發生了什麼：

首先，每個線程創建股票名稱的哈希值。如果這些名稱的長度不同，則對於不同的長度，這將在哈希循環中涉及不同數量的輪次，並且變形中的所有線程必須等待最長名稱的哈希完成。根據散列算法，代碼可以在散列算法中採用不同的路徑。每當warp中的不同線程需要採用不同的路徑時，相同的代碼必須運行多次（每個代碼路徑一次）。這被稱爲經向分歧。
當在每根經所有線程都獲得的散列，每個線程就可以從在減緩全球存儲器（通過散列指定）的不同位置處讀取。當經線中的32個線程中的每一個都以緊密連貫的模式讀取時，GPU運行最佳。但是現在，每個線程都從內存中基本上隨機的位置讀取數據。這可能會導致GPU必須序列化所有線程，可能會將性能降至潛在的1/32。
線程讀取的內存位置是散列桶。每個可能包含不同數量的散列，再次導致warp中的線程必須做不同的事情。然後，他們可能必須再次分支，每個分支到一個隨機位置，以獲得映射的實際結構。

如果不是保持股票的名稱和數據結構的CPU哈希映射，您可以使用CPU放在一起的存儲在精確的圖案信息陣列，該GPU擅長處理。取決於CPU的繁忙程度，您可以在GPU正在處理之前提交的工作時完成此操作。

這也給你一個機會來改變您有CPU到陣列的（SOA）爲GPU的結構上的結構（AOS）的陣列。如果你不熟悉這個概念，實際上，你轉換：

my_struct { 
    int a; 
    int b; 
}; 
my_struct my_array_of_structs[1000];

到：

struct my_struct { 
    int a[1000]; 
    int b[1000]; 
} my_struct_of_arrays;

這使得所有的a彼此相鄰的在內存中，使得32個線程時一個warp得到a的指令，所有的值整齊排列在一起，導致整個warp能夠非常快速地加載值。當然，b也是如此。

來源

2012-06-09 18:42:39

CUDA Thrust在cuda-thrust-extensions庫中有一個hash_map擴展。我沒有嘗試過。

來源

2012-06-08 18:48:57

謝謝羅傑。我不確定是否您或其他人在另一個問題中發佈了這個問題，但我已經看過那個圖書館。問題是我只使用C而不是C++ ..我認爲推力只是C++嗎？ – Lostsoul

Thrust是CUDA C的一部分，它是C++ ... ish :)您可以在.cu文件中使用Thrust。哦，那不是我。 –

你能幫助我，即使答案不是來自你，我仍然將它與你的智慧聯繫在一起。我會給你一個建議，讓你知道。我一般對編程非常陌生，並試圖儘量減少語言集成方面的任何問題，所以我對使用推力猶豫不決，但我將在他們的網站上播放樣本，到目前爲止，它只適用於nvcc {文件名} – Lostsoul

因爲你的散列映射的是如此之大，我認爲它可以通過一個數據庫，MySQL或其他產品來替代都將是好的，他們很可能會比自己哈希表的設計快。我同意Roger的觀點，它不適合將它移動到GPU上，它消耗的設備內存過大（可能無法容納它），而且對於內核函數訪問設備上的全局內存非常緩慢。

更進一步，該程序的一部分，需要8分鐘，發現在重量上散列映射或過程？如果是後者，可能會被GPU加速。

此致敬禮！

來源

2012-06-10 04:09:23 sjiagc

有沒有一種很好的方法在cuda上使用只讀hashmap？

回答

相關問題