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

发布时间：2021-12-09 19:03

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

【文章来源】：国防科技大学湖南省 211工程院校 985工程院校

【文章页数】：57 页

【学位级别】：硕士

【文章目录】：
摘要
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 算法
    5.1 PGHB_s 算法
    5.2 PGHB_e 算法
    5.3 性能评估
    5.4 本章小结
第六章 结束语
    6.1 全文工作总结
    6.2 未来工作展望
致谢
参考文献
作者在学期间取得的学术成果


【参考文献】：
博士论文
[1]多核处理器的访存模拟与优化技术研究[D]. 高翔.中国科学技术大学 2007



本文编号：3531147