基于低冲突帮助机制的快速无等待哈希表算法

doi:10.3969/j.issn.1000-3428.2015.11.010

计算机工程

基于低冲突帮助机制的快速无等待哈希表算法

李鹏飞,张坤龙,康超凡

(天津大学计算机科学与技术学院,天津 300072)

收稿日期:2014-10-05 出版日期:2015-11-15 发布日期:2015-11-13
作者简介:李鹏飞(1990－),男,硕士研究生,主研方向:并发数据结构,数据库技术;张坤龙,副教授、博士;康超凡,硕士研究生。
基金资助:
国家自然科学基金资助项目(61303021);水利部公益性行业科研专项基金资助项目(201401033)。

ast Wait-free Hash Table Algorithm Based on Low-conflict Help Mechanism

LI Pengfei,ZHANG Kunlong,KANG Chaofan

(School of Computer Science and Technology,Tianjin University,Tianjin 300072,China)

Received:2014-10-05 Online:2015-11-15 Published:2015-11-13

摘要/Abstract

摘要： 针对现有无等待哈希表算法未充分利用哈希表的固有并行性,造成线程之间存在高冲突和高冗余的问题,提出一种快速无等待哈希表算法。利用可冻结集合思想简化哈希表操作,采用CAS原子指令保证插入、删除与查找操作均为无等待。根据哈希表结构改进帮助机制 ,使得哈希桶的实现为无等待,只有在扩展哈希表时哈希桶之间才提供帮助。实验结果表明,该算法能降低线程操作间的冲突,提高帮助操作的并行度,当查找率为0、键值范围为0~256且线程数为8时,其吞吐率是现有无等待哈希表算法的2.5倍。

关键词: 并发数据结构, 哈希表, 无等待, 可线性化, 可扩展

Abstract: Existing wait-free hash table algorithms do not take full advantage of the inherent parallelism of hash table,which results in the high redundancy and conflict between threads.In order to solve the problem,this paper proposes a fast wait-free hash table algorithm.It makes use of the freezable set to simplify the operations of hash table.And the Compare and Swap(CAS) primitive is applied to realize the wait-free of insertion,deletion and search operations.It improves the help mechanism based on the structure of hash table to realize the wait-free of hash buckets.In order to avoid the conflics between the operations on different buckets,the help is given only when the hash table extends.Experimental results show that the algorithm can reduce the conflict between thread operation,and improve the parallelism of help operation.When the percentage of lookup is 0,the data range is 0~256 and the thread number reaches 8,throughput of the proposed algorithm is 2.5 times than the existing wait-free hash table algorithm.

Key words: concurrent data structure, hash table, wait-free, linearizability, extensibility

中图分类号:

TP311.1

李鹏飞,张坤龙,康超凡. 基于低冲突帮助机制的快速无等待哈希表算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2015.11.010.

LI Pengfei,ZHANG Kunlong,KANG Chaofan. ast Wait-free Hash Table Algorithm Based on Low-conflict Help Mechanism[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2015.11.010.

https://www.ecice06.com/CN/Y2015/V41/I11/52

参考文献

参考文献［1］Liu Yujie,Zhang Kunlong,Spear M.Dynamic-sized Nonblocking Hash Tables［C］//Proceedings of 2014 ACM Symposium on Principles of Distributed Com-puting.Paris,France:ACM Press,2014:242-251. ［2］Herlihy M.Wait-free Synchronization［J］.ACM Trans-actions on Programming Languages and Systems,1991,13(1):124-149. ［3］Kogan A,Petrank E.A Methodology for Creating Fast Wait-free Data Structures［C］//Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.New York,USA:ACM Press,2012:141-150. ［4］Michael M M.High Performance Dynamic Lock-free Hash Tables and List-based Sets［C］//Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures.New York,USA:ACM Press,2002:73-82. ［5］Harris T L.A Pragmatic Implementation of Non-blocking Linked-lists［C］//Proceedings of the 15th International Conference on Distributed Computing.Berlin,Germany:Springer,2001:300-314. ［6］Greenwald M.Two-handed Emulation:How to Build Non-blocking Implementations of Complex Data-structures Using DCAS［C］//Proceedings of the 21st Annual Sym-posium on Principles of Distributed Computing.New York,USA:ACM Press,2002:260 -269. ［7］Luchangco V,Moir M,Shavit N.Nonblocking k-compare-single-swap［C］//Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures.New York,USA:ACM Press,2003:314-323. ［8］Gao Hui,Groote J F,Hesselink W H.Lock-free Dynamic Hash Tables with Open Addressing［J］.Distributed Computing,2005,18(1):21-42. ［9］Purcell C,Harris T.Non-blocking Hashtables with Open Addressing［C］//Proceedings of the 19th International Conference on Distributed Computing.Berlin,Germany:Springer,2005:108-121. ［10］Shalev O,Shavit N.Split-ordered Lists:Lock-free Extensible Hash Tables［J］.Journal of the ACM,2006,53(3):379-405. ［11］Feldman S,Laborde P,Dechev D.Concurrent Multi-level Arrays:Wait-free Extensible Hash Maps［C］//Proceedings of International Conference on Embedded Computer Systems:Architectures,Modeling,and Simu-lation.Washington D.C.,USA:IEEE Press,2013:155-163. ［12］Nguyen D N,Tsigas P.Lock-free Cuckoo Hashing［C］//Proceedings of the 34th International Conference on Distributed Computing Systems.Washington D.C.,USA:IEEE Computer Society,2014:627-636. ［13］Zhang Kunlong,Zhao Yujiao,Yang Yajun,et al.Practical Non-blocking Unordered Lists［C］//Proceedings of the 27th International Conference on Distributed Computing.Berlin,Germany:Springer,2013:239-253. ［14］Herlihy M,Shavit N.多处理器编程的艺术［M］.金海,胡侃,译.北京:机械工业出版社,2009. ［15］Herlihy M,Luchangco V,Moir M.Obstruction-free Syn-chronization:Double-ended Queues as an Example［C］//Proceedings of the 23rd International Conference on Distributed Computing Systems.Washington D.C.,USA:IEEE Computer Society,2003:522-529. ［16］陈春光,张坤龙,谭龙飞,等.并发非阻塞自组织链表算法［J］.计算机工程,2013,39(8):31-37. ［17］Herlihy M P,Wing J M.Linearizability:A Correctness Condition for Concurrent Objects［J］.ACM Transactions on Programming Languages and Systems,1990,12(3):463-492. 编辑陆燕菲

[1]	苏瑞国, 阳建, 秦继伟, 武晓雄, 贾振红. 基于物联网区块链的轻量级共识算法研究[J]. 计算机工程, 2023, 49(2): 175-180.
[2]	黄华威, 孔伟, 彭肖文, 郑子彬. 区块链分片技术综述[J]. 计算机工程, 2022, 48(6): 1-10.
[3]	郭彪, 唐麒, 文智敏, 傅娟, 王玲, 魏急波. 面向SCA的DPR软件架构设计与调度技术[J]. 计算机工程, 2021, 47(12): 221-229.
[4]	刘旭, 张曦煌, 刘钊, 吕小敬, 朱光辉. 基于神威太湖之光的宇宙学多体模拟[J]. 计算机工程, 2020, 46(9): 35-43.
[5]	冯旭,华庆一,樊攀,王文建. 一种移动设备用户界面描述语言的设计与实现[J]. 计算机工程, 2019, 45(3): 73-77,90.
[6]	孙宁,赵维平,陈美,李超. 一种改进的Philips音频指纹检索算法[J]. 计算机工程, 2018, 44(1): 280-284.
[7]	彭振,吴百锋. 基于数据并行的碰撞检测[J]. 计算机工程, 2017, 43(9): 1-6.
[8]	陈曦,朱建涛,何晓斌. 一种面向高性能计算的分布式对象存储系统[J]. 计算机工程, 2017, 43(8): 69-73.
[9]	张剑,刘梦赤. 面向信息网模型的高可扩展性分布式事务处理机制[J]. 计算机工程, 2017, 43(11): 16-21,26.
[10]	苏浩,张坤龙,李鹏飞. 基于帮助机制的无界无等待通用构造算法[J]. 计算机工程, 2017, 43(11): 22-26.
[11]	马冬冬,衷璐洁,朱敬茹. 基于GPU的LLVM程序分析信息并行提取[J]. 计算机工程, 2017, 43(10): 23-30.
[12]	蒋成. 基于弧形不相交生成树的多链路故障恢复方法[J]. 计算机工程, 2016, 42(7): 65-71.
[13]	周懿,刘航天,戴紫彬,张立朝. 一种可配置与可扩展的USB3.0验证知识产权协议栈设计[J]. 计算机工程, 2016, 42(5): 304-307,312.
[14]	周文剑,靳婷. Blogel-SPINAL:分布式PPI网络比对算法[J]. 计算机工程, 2016, 42(4): 209-214,220.
[15]	高万辰,廖湖声,苏航. 基于部分求值的Twig查询优化[J]. 计算机工程, 2016, 42(3): 53-60,68.

选择文件类型/文献管理软件名称

选择包含的内容

基于低冲突帮助机制的快速无等待哈希表算法

ast Wait-free Hash Table Algorithm Based on Low-conflict Help Mechanism

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于低冲突帮助机制的快速无等待哈希表算法

ast Wait-free Hash Table Algorithm Based on Low-conflict Help Mechanism

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价