基于Signature的STM冲突管理的研究

发布时间：2018-01-18 16:05

本文关键词：基于Signature的STM冲突管理的研究　出处：《东北大学》2013年硕士论文　论文类型：学位论文

【摘要】：传统单核处理器中程序只能串行运行,这在很大程度上限制了计算机的性能,于是人们开始将更多的目光放到多核处理器的研究上。在多核处理器中,程序可以更好地并行执行,使并行计算的性能得到进一步的改进。然而,多核处理器提高处理性能,也给程序设计带来了问题和挑战。传统的并行编程模型使用同步变量和锁来实现同步,这会导致死锁、优先级倒置等各种问题。如何提高并行程序的开发效率,为程序员提供更加高效的编程语言和模型,使得多核的资源得到充分的利用成为近些年关注的热点。事务存储系统就是在这种情况下应运而生的,它是一种全新的多核编程模型,把数据库中事务的概念引入到程序设计中,使得在程序中可以将对内存的一系列访问封装成一个原子操作,为并行程序的设计提供简洁高效的编程环境。本文主要针对软件事务存储(STM, Software Transaction Memory)进行研究,设计并实现了Mix Bloom冲突检测算法及Synthesized冲突解决策略。在Mix Bloom冲突检测算法中,将True Bloom和Hash Bloom相结合,利用二者的优势,取长补短,提高了事务整体的并行性,降低了中止率。在冲突解决策略Synthesized中,引入了混合优先级、随机退避等待、标记事务当前状态等思想,增加了成功提交的事务数目,整体上提高了系统的性能。使用RSTM中的基准测试程序对Mix Bloom冲突检测算法及Synthesized冲突解决策略的测试结果显示：对于不同的测试程序,Mix Bloom中止率都比Hash Bloom的中止率低；Synthesized冲突解决策略在大多数情况下都有很好的表现,平均每秒提交的事务个数都很高。由此可以得出结论,Mix Bloom冲突检测算法及Synthesized冲突解决策略可以使系统的性能得到整体的提高。论文首先介绍了研究背景,并给出了论文的结构安排；然后介绍了与研究相关的工作；接下来介绍了现有的基于signature的冲突检测算法；然后提出了Mix Bloom冲突检测算法及Synthesized冲突解决策略,并给出了二者详细的算法设计及测试结果。最后,对本文工作做了总结,并进行了下一步工作展望。
[Abstract]:In traditional single-core processors, programs can only run in serial, which limits the performance of computers to a great extent, so people begin to pay more attention to the research of multi-core processors. Programs can be executed in parallel, and the performance of parallel computing can be further improved. However, multi-core processors can improve processing performance. Traditional parallel programming model uses synchronous variables and locks to achieve synchronization, which will lead to deadlock, priority inversion and other problems. How to improve the efficiency of parallel programming. Providing programmers with more efficient programming languages and models, making the full use of multi-core resources has become a hot topic in recent years. Transaction storage system is born in this situation. It is a new multi-core programming model, which introduces the concept of transaction in database into programming, so that a series of access to memory can be encapsulated into an atomic operation in the program. It provides a concise and efficient programming environment for the design of parallel programs. This paper focuses on the software transaction storage (STM, Software Transaction memory). Design and implement Mix Bloom conflict detection algorithm and Synthesized conflict resolution strategy in Mix Bloom conflict detection algorithm. True Bloom and Hash Bloom are combined to improve the parallelism of the whole transaction. In the conflict resolution strategy Synthesized, the ideas of mixed priority, random Backoff wait, marking the current state of the transaction, and so on are introduced to increase the number of successfully committed transactions. The test results of Mix Bloom collision detection algorithm and Synthesized conflict resolution strategy using the benchmark program in RSTM show that:. For different test programs. The discontinuation rate of Mix Bloom was lower than that of Hash Bloom. The Synthesized conflict resolution strategy performs well in most cases, with a high average number of transactions committed per second. Mix Bloom collision detection algorithm and Synthesized conflict resolution strategy can improve the overall performance of the system. Firstly, the research background is introduced, and the structure of the thesis is given. Then the work related to the research is introduced. Then the existing conflict detection algorithms based on signature are introduced. Then, the Mix Bloom conflict detection algorithm and Synthesized conflict resolution strategy are proposed, and the detailed algorithm design and test results are given. Finally. The work of this paper is summarized and the future work is prospected.
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP332

【参考文献】