在我的 CUDA 项目中，我需要一个类似于“存储”的数据结构(可供 block 中的所有线程使用)。在这个藏匿处有多个空间，可以是空的也可以是满的。我需要这个数据结构在每个线程请求时吐出空白空间。该线程将在 stash 中请求一个空间，放入一些东西，并将该位置标记为已满。我不能使用 fifo，因为从 stash 中获取是随机的。任何位置(和多个位置)都可以标记为空或满。
我的初始版本是用数组来表示空格是否为空。每个线程将循环遍历每个位置空间(使用 atomicCAS)，直到找到一个空位。但是这个算法搜索时间取决于 stash 有多满，这在我的设计中是 Not Acceptable 。
我如何设计一个数据结构，使获取时间和写回时间不取决于存储的满满程度？
这是否让任何人想起任何类似的算法？ 谢谢
最佳答案
您可以使用包含空闲位置列表的 FIFO 来实现这一点。
在启动时，您用所有位置填充 FIFO。
然后每当你想要一个空间时，你就从 FIFO 中取出下一个元素。
当您完成插槽后，您可以再次将地址放回 FIFO。
这应该有 O(1) 的分配和释放时间。
关于c++ - 如何设计一种数据结构，为 CUDA 中的每个线程吐出一个可用空间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23769962/