多核结构上软件事务存储的研究
发布时间：2018-07-16 16:17
【摘要】：针对计算资源日益增加的需求,单纯提高处理器主频的方式,已经不再能够提升计算机的性能了。因此,工业界引入了“多核”的概念,即在一个芯片上集成两个或多个独立的处理器,处理器之间共享内存。在多核系统中,同样的时钟频率,由于片上处理器个数的增加,每秒钟执行的指令数也随着翻倍,这为解决处理器性能的瓶颈问题提供了新的思路。与此同时,多核系统也给并行处理提出了新的问题,如何能够更好地利用多核的资源对程序进行并行处理,成为当今并行处理方面研究的一个热点方向。事务的概念来源于数据库,实践证明了其是一种有效的并发控制手段。因此,将事务引入并行程序设计领域,形成了事务存储的理论。事务存储中的事务,指的是被某个线程执行的对内存的一系列有序读写操作序列。这些序列或者全部被执行并提交,或者一个也不执行并恢复到执行该序列之前的状态。本文首先对现有的各类事务存储系统进行了分析,重点研究了基于Signature数据结构的软件事务存储系统。然后针对软件事务存储系统中的三大基本功能分别进行了研究,提出了新的优化方案,并对这些方案进行了仿真实验。最后,将改进后的功能整合起来构成一个基于Signature的软件事务存储系统。本文的主要研究成果如下：(1)在研究了冲突检测算法VHB的基础之上,提出了一种基于Signature的新的冲突检测算法VHTB。该算法不但对Signature的行与行之间进行动态变换,而且对地址数据相对较少的情况采用了尚未使用的存储空间来存储哈希函数的True Bloom映射信息。这种并行实现的方式既可以对块内的行与行之间进行并行搜索,降低延时,同时也可以降低误判率。经实验测试VHTB算法的误判率和中止率较VHB算法有了明显的降低。(2) True Bloom和Hash Bloom是事务存储中常用的冲突检测算法,而这两种算法各有其特点,在此基础之上将Signature区域划分为两个区域,对其中一个区域进行True Bloom映射,对另一个区域进行Hash Bloom映射,由此提出了一种冲突检测算法Mix Bloom。实验证明该算法较Hash Bloom算法有着较低的误判率和中止率。(3)针对软件事务存储中数据版本管理的问题,提出了一种结合急切版本管理和惰性版本管理于一身的混合数据版本管理机制。在该机制中,混合数据版本管理器能够根据冲突的数量进行动态地双向切换,从而选取最适合当前状态的数据版本管理策略。实验证明混合数据版本管理策略在整体上取得了较好的性能,达到了预期的效果。(4)在现有的冲突解决策略的基础上,结合各个冲突解决策略的优点,提出了一种冲突解决策略Synthesized。该策略综合了若干因素,包括Polite的随机指数回退、Karma的优先级、Eruption的继承优先级以及Justice的权重等,形成一个综合的冲突解决策略。实验证明了该冲突解决策略与现有策略相比,有较高的事务提交数量。(5) Rochester STM是一种常用的软件事务存储系统,该系统仅采用单一冲突解决策略来处理冲突。为解决这一问题,提出了一种复合型冲突解决策略Comprehensive。该策略在两个事务发生冲突时根据两个事务的丢弃成本、尝试次数以及起始时间等因素来决定丢弃哪个事务。实验证明了该冲突解决策略性能较其他冲突解决策略有显著的提高。(6)设计并实现了一个支持多种基于Signature的冲突检测算法的事务存储系统RingSS (Ring Support Signature),并在RingSS中对本文中提出的改进策略进行了评测。结果表明,在该事务存储系统中,通过使用新的策略,使系统的性能得到了提升。本文研究了多核环境下软件事务存储系统中的冲突检测、数据版本和冲突解决等的相关问题,提出了新颖的解决方法,能够有效地解决多核结构上并行程序设计的关键问题。理论分析和大量的实验结果证明了这些方法的有效性。这些方法和技术对于这一领域的研究工作具有参考价值。
[Abstract]:In view of the increasing demand for computing resources, the way to improve the primary frequency of the processor is no longer able to improve the performance of the computer. Therefore, the industry has introduced the concept of "multi core", that is, to integrate two or more independent processors on a single chip, shared memory between the processors. In a multi-core system, the same clock frequency. With the increase of the number of processors on the chip, the number of instructions executed per second doubles, which provides a new way of thinking to solve the bottleneck problem of processor performance. At the same time, the multi-core system also presents a new problem for parallel processing, how to make better use of multi core resources for parallel processing of programs and become today parallel. The concept of transaction is a hot topic. The concept of transaction comes from the database, and it has proved that it is an effective means of concurrency control. Therefore, the transaction is introduced into the domain of parallel programming to form the theory of transaction storage. Transactions in transaction storage refer to a series of read and write to memory executed by a thread. The sequence of operations. These sequences are or are all executed and submitted, or a state that is not executed and restored to the execution of the sequence. This article first analyzes the existing transaction storage systems and focuses on the software transaction storage system based on the Signature data structure. Then, it is aimed at the software transaction storage system. Three basic functions are studied, new optimization schemes are proposed and simulation experiments are carried out. Finally, the improved functions are integrated to form a software transaction storage system based on Signature. The main research results of this paper are as follows: (1) on the basis of the study of the conflict detection algorithm VHB A new conflict detection algorithm based on Signature VHTB., the algorithm not only dynamically transforms between the rows and rows of Signature, but also uses unused storage space to store the True Bloom mapping information of the Hashi function with relatively little address data. The parallel search between lines can reduce the delay and also reduce the misjudgment rate. The error rate and the abort rate of the VHTB algorithm are obviously lower than that of the VHB algorithm. (2) the True Bloom and Hash Bloom are the common conflict detection algorithms in the transaction storage, and the two algorithms have their own characteristics, and the Signature region is on the basis of this. Two regions are divided into two regions, and one region is mapped with True Bloom, and the other region is mapped by Hash Bloom. A conflict detection algorithm is proposed, Mix Bloom. experiment proves that the algorithm has a lower error rate and abort rate than Hash Bloom algorithm. (3) the problem of data version management in the storage of soft parts is proposed. A hybrid data version management mechanism combined with urgent version management and lazy version management. In this mechanism, the hybrid data version manager can dynamically switch two direction according to the number of conflicts to select the most suitable data version management strategy for the current state. The experiment proves the mixed data version management strategy. A better performance is achieved on the whole. (4) on the basis of the existing conflict resolution strategy and combining the advantages of each conflict resolution strategy, a conflict resolution strategy, Synthesized., is proposed to synthesize several factors, including Polite's exponential regression, the priority of Karma and the inheritance priority of Eruption. A comprehensive conflict resolution strategy is formed by the weight of the level and Justice. The experiment proves that the conflict resolution strategy has a higher number of transaction submissions compared with the existing strategy. (5) the Rochester STM is a common software transaction storage system, which only uses a single impulse solution decision to deal with the conflict. A complex conflict resolution strategy, Comprehensive., is proposed to decide which transaction is discarded according to the discarding cost of two transactions, the number of attempts and the starting time during the two transaction conflicts. The experiment proves that the performance of the conflict resolution strategy is significantly higher than that of other conflict resolution strategies. (6) design and implement the strategy. A transaction storage system RingSS (Ring Support Signature) supporting multiple Signature based conflict detection algorithms is presented, and the improved strategy proposed in this paper is evaluated in RingSS. The results show that the performance of the system is improved by using the new strategy in the transaction storage system. In the environment of software transaction storage system, such as conflict detection, data version and conflict resolution, a novel solution is proposed, which can effectively solve the key problems of parallel programming in multi-core structure. Theoretical analysis and a large number of experimental results prove the effectiveness of these methods. The research work in one field is of reference value.
【学位授予单位】：东北大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：TP333
[Abstract]:In view of the increasing demand for computing resources, the way to improve the primary frequency of the processor is no longer able to improve the performance of the computer. Therefore, the industry has introduced the concept of "multi core", that is, to integrate two or more independent processors on a single chip, shared memory between the processors. In a multi-core system, the same clock frequency. With the increase of the number of processors on the chip, the number of instructions executed per second doubles, which provides a new way of thinking to solve the bottleneck problem of processor performance. At the same time, the multi-core system also presents a new problem for parallel processing, how to make better use of multi core resources for parallel processing of programs and become today parallel. The concept of transaction is a hot topic. The concept of transaction comes from the database, and it has proved that it is an effective means of concurrency control. Therefore, the transaction is introduced into the domain of parallel programming to form the theory of transaction storage. Transactions in transaction storage refer to a series of read and write to memory executed by a thread. The sequence of operations. These sequences are or are all executed and submitted, or a state that is not executed and restored to the execution of the sequence. This article first analyzes the existing transaction storage systems and focuses on the software transaction storage system based on the Signature data structure. Then, it is aimed at the software transaction storage system. Three basic functions are studied, new optimization schemes are proposed and simulation experiments are carried out. Finally, the improved functions are integrated to form a software transaction storage system based on Signature. The main research results of this paper are as follows: (1) on the basis of the study of the conflict detection algorithm VHB A new conflict detection algorithm based on Signature VHTB., the algorithm not only dynamically transforms between the rows and rows of Signature, but also uses unused storage space to store the True Bloom mapping information of the Hashi function with relatively little address data. The parallel search between lines can reduce the delay and also reduce the misjudgment rate. The error rate and the abort rate of the VHTB algorithm are obviously lower than that of the VHB algorithm. (2) the True Bloom and Hash Bloom are the common conflict detection algorithms in the transaction storage, and the two algorithms have their own characteristics, and the Signature region is on the basis of this. Two regions are divided into two regions, and one region is mapped with True Bloom, and the other region is mapped by Hash Bloom. A conflict detection algorithm is proposed, Mix Bloom. experiment proves that the algorithm has a lower error rate and abort rate than Hash Bloom algorithm. (3) the problem of data version management in the storage of soft parts is proposed. A hybrid data version management mechanism combined with urgent version management and lazy version management. In this mechanism, the hybrid data version manager can dynamically switch two direction according to the number of conflicts to select the most suitable data version management strategy for the current state. The experiment proves the mixed data version management strategy. A better performance is achieved on the whole. (4) on the basis of the existing conflict resolution strategy and combining the advantages of each conflict resolution strategy, a conflict resolution strategy, Synthesized., is proposed to synthesize several factors, including Polite's exponential regression, the priority of Karma and the inheritance priority of Eruption. A comprehensive conflict resolution strategy is formed by the weight of the level and Justice. The experiment proves that the conflict resolution strategy has a higher number of transaction submissions compared with the existing strategy. (5) the Rochester STM is a common software transaction storage system, which only uses a single impulse solution decision to deal with the conflict. A complex conflict resolution strategy, Comprehensive., is proposed to decide which transaction is discarded according to the discarding cost of two transactions, the number of attempts and the starting time during the two transaction conflicts. The experiment proves that the performance of the conflict resolution strategy is significantly higher than that of other conflict resolution strategies. (6) design and implement the strategy. A transaction storage system RingSS (Ring Support Signature) supporting multiple Signature based conflict detection algorithms is presented, and the improved strategy proposed in this paper is evaluated in RingSS. The results show that the performance of the system is improved by using the new strategy in the transaction storage system. In the environment of software transaction storage system, such as conflict detection, data version and conflict resolution, a novel solution is proposed, which can effectively solve the key problems of parallel programming in multi-core structure. Theoretical analysis and a large number of experimental results prove the effectiveness of these methods. The research work in one field is of reference value.
【学位授予单位】：东北大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：TP333
【相似文献】
相关期刊论文 前10条
1 肖明忠;代亚非;;Bloom Filter及其应用综述[J];计算机科学;2004年04期
2 池静;倪健;王华;邢秀娥;;Bloom Filter和Weighted Bloom Filter的比较与研究[J];河北师范大学学报;2006年04期
3 李s，
本文编号：2126931
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/2126931.html
