使用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的小链表更加平行。我期望内存访问不合并，除非注意分配相邻内存位置中的连接节点。