【作者】 刘莹；

【导师】 王义； 高福祥；

【作者基本信息】 东北大学 ， 计算机应用技术， 2013， 博士

【摘要】 针对计算资源日益增加的需求,单纯提高处理器主频的方式,已经不再能够提升计算机的性能了。因此,工业界引入了“多核”的概念,即在一个芯片上集成两个或多个独立的处理器,处理器之间共享内存。在多核系统中,同样的时钟频率,由于片上处理器个数的增加,每秒钟执行的指令数也随着翻倍,这为解决处理器性能的瓶颈问题提供了新的思路。与此同时,多核系统也给并行处理提出了新的问题,如何能够更好地利用多核的资源对程序进行并行处理,成为当今并行处理方面研究的一个热点方向。事务的概念来源于数据库,实践证明了其是一种有效的并发控制手段。因此,将事务引入并行程序设计领域,形成了事务存储的理论。事务存储中的事务,指的是被某个线程执行的对内存的一系列有序读写操作序列。这些序列或者全部被执行并提交,或者一个也不执行并恢复到执行该序列之前的状态。本文首先对现有的各类事务存储系统进行了分析,重点研究了基于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】 To meet the increasing requirement of computing power, it is no longer possible to improve the performance of uniprocessor systems by increasing the clock frequency of the processor. This leads to the introduction of multicore in industry, on which multiple processors are integrated on a single chip, sharing the same off-chip memory. In multicore systems, with the same clock frequency, the number of instructions executed per second may be multiplied by increasing number of processors on chip. This provides a new solution for the bottleneck problem of improving performance. Meanwhile, multicore has brought us a number of new challenges in parallel programming. A key challenge is to make better use of the computing resources on multicore systems for parallel processing.The concept of transaction comes from database, which has proved to be an effective means of concurrency control. It is introduced into parallel programming, which has formed the theory of transactional memory. Transaction in transactional memory is an atomic read/write operation sequence executed by a thread. The sequence of operations is either completely executed and committed or aborted and recovered back to the state before executing the sequence. This dissertation first provides a survey on existing transactional memory systems, especially systems based on Signature. Then three fundamental functions for software transactional memory systems are studied and improved by novel optimization schemes. Finally the optimized functions are integrated into a Signature-based software transactional memory system. The main research contributions in this dissertation are as follows.(1) A conflict detection algorithm called VHB is studied. Then a new Signature-based conflict detection algorithm named VHTB is presented, with dynamic transformation between lines in Signature, where when addresses are less used, True Bloom mapping information for hash function is stored in the unused memory space. The parallel implementation enables parallel search among lines in the block and thus reduces both latency and the rate of false positives. Using simulation, it is shown that the false positives rate and abort rate in VHTB are reduced significantly compared with VHB.(2) True Bloom and Hash Bloom are two common conflict detection algorithms for transactional memory, with different features. To combine the advantages of both algorithms, the Signature data structure used for conflict detection is divided into two equal-size regions one of which is mapped using True Bloom and the other is mapped using Hash Bloom. This gives rise to a new conflict detection algorithm (named Mix Bloom). Experiments results show that Mix Bloom has lower false positives rate and abort rate than algorithm Hash Bloom.(3) For data version management in software transactional memory, a hybrid data version management strategy is proposed, combining the advantages of existing eager and lazy strategies. The hybrid data version manager allows switching dynamically between the two according to the number of conflicts detected in order to use the data version management most suitable for the current state. Experiment results show that the hybrid data management outperforms the eager and lazy strategies as expected.(4) Based on the existing conflict detection algorithms, an integrated conflict resolution strategy called Synthesized is proposed, which takes the advantages of several conflict resolution strategies including random exponential backoff of Polite, priority of Karma, inheritance priority of Eruption and weight of Justice. Experiments have proved that this strategy has larger amount of transactions committed.(5) A conflict resolution strategy called Comprehensive is proposed. When a conflict occurs between two transactions, one of the transactions will be discarded according to factors including discard cost, retry times and start time. Experiments demonstrate that Comprehensive outperforms existing strategies.(6) Finally a transactional memory system with conflict detection algorithms based on Signature named RingSS (Ring Support Signature) is designed and implemented to study the proposed solutions presented in this dissertation.To summarize, this dissertation presents several novel solutions for conflict detection, data version management and conflict resolution implementing software transactional memory on multicore architectures. Theoretical analysis and extensive experiments have been conducted to demonstrate their effectiveness.更多还原