使用CUDA創建鏈接列表

Question

使用CUDA可以在GPU上創建鏈接列表嗎？
我正在努力做到這一點，我正在爲此遇到一些困難。
如果我不能在CUDA內核中分配動態內存，那我該如何創建一個新節點並將其添加到鏈接列表中？

Answer 1

如果你能幫上忙，你真的不想這麼做 - 如果你無法擺脫鏈表，你可以做的最好的事情就是通過數組來模擬它們，並使用數組索引而不是指針鏈接。

Answer 2

我同意Paul的觀點，鏈表是一種非常「連續」的思維方式。忘記你所學到的有關串行操作，只是做的一切在一次：）

Answer 3

看看Thrust做常見的操作

Answer 4

有一些有效的使用情況在GPU上鍊表的方式。考慮使用跳過列表作爲替代，因爲它們提供更快的操作。有幾個高度併發的跳過列表算法可以通過Google搜索獲得。

看看這個鏈接http://www.cse.iitk.ac.in/users/mainakc/lockfree.html/ 爲CUDA代碼一個PDF和PPT演示在一些無鎖的CUDA數據結構。

鏈接列表可以使用簡化算法方法並行構建。這假定所有成員在施工時已知。每個線程從連接2個節點開始。然後有一半線程將2個節點段連接在一起，等等，每次迭代減少2個線程數。這將在log2 N時間內建立一個列表。

內存分配是一個約束。預分配主機上陣列中的所有節點。然後你可以使用數組下標代替指針。這具有列表遍歷在GPU和主機上有效的優點。

對於併發性，您需要使用CUDA原子操作。通過原子添加/增加來計算從節點陣列中使用的節點以及比較和交換以設置節點之間的鏈接。

再次仔細考慮用例和訪問模式。使用一個大的鏈表是非常連續的。使用100-100的小鏈表更加平行。我期望內存訪問不合並，除非注意分配相鄰內存位置中的連接節點。