我正在研究GPU上的动态分支粒子系统。我需要一个具有以下属性的并行数据结构:
基本的同步原语(互斥、信号量)以及可以使用它们实现的任何东西都是可用的。
我曾经尝试过使用链接列表的想法,但这违反了条件2(因为对m个线程添加将是O(m),因为必须考虑锁定)。我不确定这样的数据结构是否存在--但我想我会问。
发布于 2013-01-18 17:08:30
不知道更多关于你想要如何组织你的数据(排序?FIFO?LIFO?)我很确定我能不能给你一个确切的答案。然而,您所描述的听起来就像是无锁结构的定义。栈和队列的无锁实现是存在的,它们支持O(1)插入和删除,即使有很多线程同时修改结构。它们通常是基于原子测试和设置操作。
如果锁没有问题,而且您只是想要一个高度并发的数据结构,那么可以考虑查看并发跳过列表,它提供了O(log )排序的插入和删除以及多个活动线程。
希望这能有所帮助!
https://stackoverflow.com/questions/14403275
复制相似问题