首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >数据结构并行添加串行删除所需

问数据结构并行添加串行删除所需
EN

Stack Overflow用户
提问于 2013-01-18 16:30:30
回答 1查看 122关注 0票数 1

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

  1. 一个线程必须能够在固定时间内逐个删除元素。返回的元素对算法并不重要--只要某个元素在非空时返回即可。为了获得额外的惊艳,可以换到任意数量的线程。
  2. 任何数量的线程都必须能够在恒定时间内向数据结构添加元素。请注意,允许进行某种锁定(并且是必要的),但是它仍然必须扩展,而与线程数没有关系。也就是说,更多的线程不应该拖慢它。

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

我曾经尝试过使用链接列表的想法,但这违反了条件2(因为对m个线程添加将是O(m),因为必须考虑锁定)。我不确定这样的数据结构是否存在--但我想我会问。

EN

回答 1

Stack Overflow用户

发布于 2013-01-18 17:08:30

不知道更多关于你想要如何组织你的数据(排序?FIFO?LIFO?)我很确定我能不能给你一个确切的答案。然而,您所描述的听起来就像是无锁结构的定义。栈和队列的无锁实现是存在的,它们支持O(1)插入和删除,即使有很多线程同时修改结构。它们通常是基于原子测试和设置操作。

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

希望这能有所帮助!

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/14403275

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档