事务存储系统中冲突检测算法的研究与改进

论文摘要

随着传统单核处理器的局限性越来越突出,人们将目光逐渐转向多核体系结构,通过多核技术来开发线程级并行。然而,传统的基于互斥锁的并行编程模式存在死锁等各种缺陷,使得并行程序的开发变得非常低效。在这种情况下,事务存储系统应运而生,为并行程序设计提供了一个简洁高效的编程环境。冲突检测作为事务存储系统的三大功能之一,其检测算法的优劣对事务存储系统的整体性能有着重要的影响。基于Signature的冲突检测算法能利用有限的位数组表示无限的地址集合,是事务存储系统中一种很有前景的冲突检测方案,而误判率的大小又直接影响着该类算法的性能,本文主要针对如何降低Signature误判率的问题进行研究。文章首先对现有的基于Signature的冲突检测算法进行深入的分析,并改进了Hash-Bloom算法,删减了该算法中一个冗余的步骤,从而缩短了插入和查询地址信息的时间;然后基于改进后的Hash-Bloom算法提出了两个新的算法——VHB算法和GHB算法,并通过蒙特卡罗方法进行验证。实验结果表明,VHB算法在地址数量较少的时候的误判率较Hash-Bloom算法有了明显的降低,GHB在地址数量较多和较少的时候相对于其他算法的误判率都较低;最后,文章从硬件开销的角度对GHB算法进行优化,提出了两种PGHB算法,并使用HP的CACTI对硅片占用面积进行了定量的评估。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 传统体系结构的局限
• 1.2 单芯片多核处理器
• 1.3 传统并行编程模式的局限
• 1.4 事务存储系统
• 1.4.1 TM 的定义
• 1.4.2 TM 研究现状
• 1.4.3 TM 的优势
• 1.5 论文工作
• 1.6 论文结构
• 第二章 冲突检测算法研究
• 2.1 Bloom Filter
• 2.1.1 基本原理
• 2.1.2 误判率分析
• 2.2 基于 Signature 的冲突检测算法
• 2.2.1 True-Bloom
• 2.2.2 Cuckoo-Bloom
• 2.2.3 Adaptive-Bloom
• 2.2.4 Hash-Bloom
• 2.3 本章小结
• 第三章 VERTICAL-HASH-BLOOM 算法
• 3.1 算法设计
• 3.2 硬件实现
• 3.3 性能评测方法
• 3.3.1 Hash 函数的选择
• 3.3.2 Hash-Bloom 的改进
• 3.3.3 实验设计
• 3.4 测试结果
• 3.5 结果评价
• 3.6 本章小结
• 第四章 GREEDY-HASH-BLOOM 算法
• 4.1 算法设计
• 4.2 硬件实现
• 4.3 测试结果
• 4.4 结果评价
• 4.5 本章小结
• 第五章 PARALLEL-GREEDY-HASH-BLOOM 算法
• s 算法'>5.1 PGHB_s算法
• e 算法'>5.2 PGHB_e算法
• 5.3 性能评估
• 5.4 本章小结
• 第六章 结束语
• 6.1 全文工作总结
• 6.2 未来工作展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果