-
题名基于低冲突帮助机制的快速无等待哈希表算法
被引量：4
- 1
-
-
作者
李鹏飞
张坤龙
康超凡
-
机构
天津大学计算机科学与技术学院
-
出处
《计算机工程》
CAS
CSCD
北大核心
2015年第11期52-58,共7页
-
基金
国家自然科学基金资助项目(61303021)
水利部公益性行业科研专项基金资助项目(201401033)
-
文摘
针对现有无等待哈希表算法未充分利用哈希表的固有并行性,造成线程之间存在高冲突和高冗余的问题,提出一种快速无等待哈希表算法。利用可冻结集合思想简化哈希表操作,采用CAS原子指令保证插入、删除与查找操作均为无等待。根据哈希表结构改进帮助机制,使得哈希桶的实现为无等待,只有在扩展哈希表时哈希桶之间才提供帮助。实验结果表明,该算法能降低线程操作间的冲突,提高帮助操作的并行度,当查找率为0、键值范围为0~256且线程数为8时,其吞吐率是现有无等待哈希表算法的2.5倍。
-
关键词
并发数据结构
哈希表
无等待
可线性化
可扩展
-
Keywords
concurrent data structure
hash table
wait-free
linearizability
extensibility
-
分类号
TP311.1
[自动化与计算机技术—计算机软件与理论]
-
-
题名并发多播队列的实现框架及其多种实现的性能分析
- 2
-
-
作者
张其良
张昱
-
机构
中国科学技术大学计算机科学与技术学院
-
出处
《小型微型计算机系统》
CSCD
北大核心
2017年第6期1237-1242,共6页
-
基金
国家自然科学基金项目(61229201)资助
国家"八六三"高技术研究发展计划项目(2012AA010901)资助
-
文摘
开发易用且高效的并发数据结构对降低并行编程的难度和有效利用并行资源非常重要.针对所提出的易于编程的确定性消息传递多线程编程模型DetMP,除可以基于所提出的单生产多播共享虚拟内存模型(SPMC)实现以外,还可以基于传统的多线程共享虚拟内存模型来实现.为了分析消息通道的实现机制(如数据的存储组织、并发访问的同步控制)对DetMP程序性能的影响,提出一个并发多播队列的框架CMQue,并基于Pthreads实现了6种并发多播队列.我们评估了6种并发多播队列和SPMC通道,结果表明消息通道的实现机制对程序性能影响很大,SPMC通道在CPU核资源充足时具有很好的可伸缩性.
-
关键词
多播队列
并发数据结构
同步控制
多线程编程模型
生产-消费
-
Keywords
multicast queue
concurrent data structure
synchronization control
multithreaded programming model
produce-consume
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
-
题名基于帮助机制的无界无等待通用构造算法
- 3
-
-
作者
苏浩
张坤龙
李鹏飞
-
机构
天津大学计算机科学与技术学院
-
出处
《计算机工程》
CAS
CSCD
北大核心
2017年第11期22-26,共5页
-
基金
国家自然科学基金(61303021)
水利部公益性行业科研专项基金(201401033)
-
文摘
已有的无等待通用构造算法大多只考虑有界无等待的情况,并不适用于无界无等待并发模型。为此,提出一种新的无等待通用构造算法——UWUC。该算法使用Fetch&Add对象和列地址选通脉冲对象,给出新的排队方法,利用任意一段时间内到达的线程数有限的特性,实现无界无等待的通用构造。实验结果证明了该算法的无等待特性。
-
关键词
并发数据结构
无等待
通用构造
无界无等待
非阻塞
列地址选通脉冲
-
Keywords
concurrent data structure
wait-free
universal construction
unbounded wait-free
non-blocking
Column Address Strobe（ CAS ）
-
分类号
TP309
[自动化与计算机技术—计算机系统结构]
-
