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

李鹏飞; 张坤龙; 康超凡

首页> 中文期刊> 《计算机工程》 >基于低冲突帮助机制的快速无等待哈希表算法

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

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《计算机工程》 |2015年第11期|52-58|共7页
作者
李鹏飞; 张坤龙; 康超凡;
展开▼
作者单位

天津大学计算机科学与技术学院;

天津300072;

天津大学计算机科学与技术学院;

天津300072;

天津大学计算机科学与技术学院;

天津300072;

展开▼
原文格式 PDF
正文语种 chi
中图分类程序设计;
关键词
并发数据结构; 哈希表; 无等待; 可线性化; 可扩展;

相似文献

中文文献
外文文献
专利

1. 基于帮助机制的无界无等待通用构造算法 [J] . 苏浩 ,张坤龙 ,李鹏飞 . 计算机工程 . 2017,第011期
2. 基于无冲突哈希表和多比特树的两级IPv6路由查找算法 [J] . 杜飞 ,董治国 ,苗琳 . 计算机应用 . 2013,第005期
3. 基于目标增量的无等待流水调度快速迭代贪婪算法 [J] . 朱夏 ,李小平 ,王茜 . 计算机学报 . 2009,第001期
4. 基于哈希表的STL文件拓扑关系快速重建算法 [J] . 钱乘 ,李震 ,江本赤 . 新乡学院学报（自然科学版） . 2018,第006期
5. 基于哈希表的STL文件拓扑关系快速重建算法 [J] . 钱乘 ,李震 ,江本赤 . 新乡学院学报：自然科学版 . 2018,第006期
6. Hash-Search:基于哈希表的快速XML关键字检索算法 [C] . . 第二十五届中国数据库学术会议(NDBC2008) . 2008
7. 基于Kinect V2深度图像流的快速体素哈希表面重建算法 [A] . 王浩 . 2019

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

摘要

著录项

相似文献

相关主题

期刊订阅