sca*_*man 5 cuda gpu linked-list
是否可以使用CUDA在GPU上创建链接列表？
我正在努力做到这一点,我正在困扰一些困难.
如果我无法在CUDA内核中分配动态内存,那么如何创建新节点并将其添加到链表？
如果你可以提供帮助,你真的不想这样做 - 如果你无法摆脱链接列表,你可以做的最好的事情是通过数组模拟它们并使用数组索引而不是链接的指针.
GPU上的链表有一些有效的用例.考虑使用跳过列表作为替代,因为它们提供更快的操作.通过Google搜索可以获得高度并发的跳过列表算法的示例.
查看此链接http://www.cse.iitk.ac.in/users/mainakc/lockfree.html/ 获取CUDA代码,以及关于许多无锁CUDA数据结构的PDF和PPT演示.
链接列表可以使用缩减算法方法并行构建.这假设所有成员在施工时都是已知的.每个线程通过连接2个节点开始.然后,一半的线程将2个节点段连接在一起,依此类推,每次迭代将线程数减少2个.这将在log2 N时间内构建一个列表.
内存分配是一种约束.预分配主机上阵列中的所有节点.然后你可以使用数组下标代替指针.这具有以下优点:列表遍历在GPU和主机上有效.
对于并发性,您需要使用CUDA原子操作.原子添加/增量以计算从节点阵列使用的节点,并比较和交换以设置节点之间的链接.
再次仔细考虑用例和访问模式.使用一个大的链表非常连贯.使用100 - 100的小链接列表更加平行.我希望内存访问不被合并,除非注意在相邻的内存位置分配连接的节点.