论文部分内容阅读
针对计算资源日益增加的需求,单纯提高处理器主频的方式,已经不再能够提升计算机的性能了。因此,工业界引入了“多核”的概念,即在一个芯片上集成两个或多个独立的处理器,处理器之间共享内存。在多核系统中,同样的时钟频率,由于片上处理器个数的增加,每秒钟执行的指令数也随着翻倍,这为解决处理器性能的瓶颈问题提供了新的思路。与此同时,多核系统也给并行处理提出了新的问题,如何能够更好地利用多核的资源对程序进行并行处理,成为当今并行处理方面研究的一个热点方向。事务的概念来源于数据库,实践证明了其是一种有效的并发控制手段。因此,将事务引入并行程序设计领域,形成了事务存储的理论。事务存储中的事务,指的是被某个线程执行的对内存的一系列有序读写操作序列。这些序列或者全部被执行并提交,或者一个也不执行并恢复到执行该序列之前的状态。本文首先对现有的各类事务存储系统进行了分析,重点研究了基于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中对本文中提出的改进策略进行了评测。结果表明,在该事务存储系统中,通过使用新的策略,使系统的性能得到了提升。本文研究了多核环境下软件事务存储系统中的冲突检测、数据版本和冲突解决等的相关问题,提出了新颖的解决方法,能够有效地解决多核结构上并行程序设计的关键问题。理论分析和大量的实验结果证明了这些方法的有效性。这些方法和技术对于这一领域的研究工作具有参考价值。