使用CUDA可以在GPU上創建鏈接列表嗎?
我正在努力做到這一點,我正在爲此遇到一些困難。
如果我不能在CUDA內核中分配動態內存,那我該如何創建一個新節點並將其添加到鏈接列表中?使用CUDA創建鏈接列表
回答
如果你能幫上忙,你真的不想這麼做 - 如果你無法擺脫鏈表,你可以做的最好的事情就是通過數組來模擬它們,並使用數組索引而不是指針鏈接。
我同意Paul的觀點,鏈表是一種非常「連續」的思維方式。忘記你所學到的有關串行操作,只是做的一切在一次:)
在GPU和並行編程中有很多LL的有效使用。我將它們用於哈希,索引,壓縮和搜索算法算法。通過GPU上的LL,每秒可以獲得> 100M插入... – 2013-08-03 14:14:54
看看Thrust做常見的操作
有一些有效的使用情況在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的小鏈表更加平行。我期望內存訪問不合並,除非注意分配相鄰內存位置中的連接節點。
- 1. 使用鏈接創建網格列表
- 2. 列表中創建鏈接
- 3. 創建鏈接列表
- 4. 鏈接列表創建
- 5. 用foreach創建動態鏈接列表
- 6. 創建鏈接表單外部列表
- 7. VBA使用超鏈接創建表格
- 8. 無法創建鏽鏈接列表
- 9. 創建鏈接列表,不傳回主
- 10. 在excel中創建超鏈接列表
- 11. 鏈接列表創建 - 垃圾輸出?
- 12. 創建鏈接字母列表
- 13. 創建節點線性鏈接列表
- 14. 創建多個鏈接列表
- 15. 在AS3中創建鏈接列表
- 16. 創建簡單的鏈接列表
- 17. 使用fgets和strtok讀取數據並創建鏈接列表
- 18. 如何使用Java中的對象創建鏈接列表。
- 19. 如何使用泛型創建鏈接列表
- 20. 僅使用節點創建Java鏈接列表的幫助
- 21. 如何使用JSF2創建鏈接列表
- 22. 使用while循環創建鏈接列表
- 23. 使用沒有無序列表的鏈接創建導航欄
- 24. C# - MCTS - 創建一個通用鏈接列表類創建一個對象鏈
- 25. 這是我如何在鏈接列表中創建鏈接列表?
- 26. 鏈接列表的使用
- 27. 使用裝飾設計模式通過裝飾單個鏈接列表來創建雙向鏈接列表
- 28. CUDA鏈接錯誤
- 29. 使用鏈接表和實體框架創建連接
- 30. 如何使用無序鏈接列表的實現創建優先隊列? (Java)
作者沒有提供證據或解釋爲什麼不使用LL。您可以在GPU上使用指針創建LL。需要這些類型的結構,因爲我們在GPU上執行更復雜的算法。使用數組下標作爲LL的唯一必要條件是您需要將LL存儲在整個存儲空間中。 – 2013-08-03 14:10:15