algorithm - 需要数据结构并行添加串行删除

Question

我正在研究 GPU 上的动态分支粒子系统。我需要一个具有以下属性的并行数据结构：

1. 一个线程必须能够在恒定时间内一个一个地删除元素。返回的元素对算法并不重要——只要一些在非空时返回为了更棒，更改为任意数量的线程。
2. 任意数量的线程必须能够在恒定时间内向数据结构添加元素。请注意，某些锁定是允许的（并且是必要的），但它仍然必须与线程数无关地扩展。即，更多线程不应该减慢它。

基本的同步原语（互斥体、信号量）以及可以使用它们实现的任何东西都是可用的。

我曾经玩弄过链表的想法，但这违反了条件二（因为对于 m 个线程，添加将是 O(m)，因为必须考虑锁定）。我不确定这样的数据结构是否存在——但我想我会问。

Answer 1

在不了解您希望如何组织数据（排序？先进先出？后进先出？）的更多信息的情况下，我是。或者确定我是否可以给你一个确切的答案。但是，您所描述的内容听起来像是无锁结构的定义。存在堆栈和队列的无锁实现，即使有大量线程同时修改结构，它们也支持 O(1) 插入和删除。它们通常基于原子测试和设置操作。

如果锁没问题，并且您只想要一个排序的高并发数据结构，请考虑查看并发跳过列表，它提供 O(log n) 排序的插入和删除以及多个活动线程。

希望这可以帮助！