随着微处理器技术的不断发展,传统的依靠提高主频和开发指令级并行来提高微处理器性能的方法已经不再可行,取而代之的是开发线程级并行的方法。目前多核多线程体系结构已经成为微处理器设计的主流,单芯片的并行度迅速提高,并行程序设计已经成为发挥微处理器性能的关键。然而,并行编程模型和并发控制模型的发展没有跟上微处理器高并行度的发展,并行程序设计依然是一项极具挑战性的工作。在这样的背景下,事务存储技术的提出为并行编程模型和并发控制模型的发展带来了新的机遇。事务存储技术借用数据库领域中“事务”的概念,将线程对共享资源的访问封装在事务之中,由事务存储系统确保事务执行的原子性和隔离性。基于事务的并行编程模型及并发控制模型具有无死锁、可组合、简单易用等优点,大大降低了并行程序设计的难度。因此,事务存储技术近年来受到学术界的广泛关注,已经成为并行计算领域的研究热点。本文以事务存储系统为研究对象,重点研究如何支持事务的充分并行以及影响事务并行的主要因素。本文的研究从以下四个方面展开:首先,本文将可能的事务并行模式划分为三个等级:线程间事务并行、线程内事务并行和嵌套事务并行。针对每个等级的事务并行模式,本文使用形式化方法对其进行描述,并在此基础上寻找支持该种并行模式下事务正确执行的充分必要条件。经过形式化的分析和证明本文得出如下结论:在仅支持线程间事务并行的事务存储系统上,事务正确并行执行的充要条件为其冲突图为无环图;在支持线程内事务并行的事务存储系统上,事务正确并行执行的充要条件为其含序冲突图为无环图;在支持嵌套事务并行的事务存储系统上,事务正确并行执行的充要条件为其嵌套冲突图为无环图。其次,本文提出了基于事务冲突图的事务处理协议,并在此基础上给出了基于冲突图的事务存储系统的设计。基于冲突图的事务存储系统支持线程间及线程内事务并行模式,它能够动态的维护活跃事务间的含序冲突图,并在事务提交时检测含序冲突图中是否包含环来决定其是否可以正常提交,从而确保事务执行的正确性。与现有的事务存储系统相比,基于冲突图的事务存储系统能够最大限度的开发事务应用程序线程内及线程间的事务并行性,从而充分发挥多核处理器的并行处理能力。再次,本文选取了三个真实的应用程序,以事务存储技术为基础对其进行并行化,包括实时视频人脸识别程序、基于Push-Relabel最大网络流求解程序以及面向人脸检测的Adaboost机器学习程序。一方面研究基于事务存储技术的程序并行化方法,探索面向事务存储系统的程序设计及优化方法;另一方面以实际的应用程序为测试用例对事务存储系统的性能进行测试,对比不同事务存储系统实现的优缺点。经过对三个应用程序的对比分析,本文发现,粗粒度的事务并行程序的性能优于基于粗粒度锁的并行程序,但依然不如基于细粒度锁的并行程序,要获得超越基于细粒度锁的并行程序的性能,仍然需要对事务并行程序进行精细的优化。此外,由于软件事务存储系统会引入较大的额外开销,要充分发挥事务并行程序的性能,开发具备硬件支持的事务存储系统是十分必要的。最后,本文建立了基于马尔科夫链的硬件事务存储系统模型,该模型将硬件事务的动态执行过程抽象为一个马尔科夫过程,并通过不动点迭代的方法求解硬件事务存储系统的主要性能指标,如平均事务重启次数,事务平均执行时间等。通过对比该模型的求解结果与模拟器的模拟结果,本文验证了该分析模型的有效性(误差在7%以内)。以该分析模型为基础,本文对现有的硬件事务存储系统的实现方法进行了对比分析,主要包括采用Eager型冲突处理策略的硬件事务存储系统,采用Lazy型冲突处理策略的硬件事务存储系统,以及采用混合型冲突处理策略的硬件事务存储系统。分析结果表明,采用混合型冲突处理策略的硬件事务存储系统与其他事务存储系统实现方案相比具有更好的性能和可扩展性。此外,事务存储系统内包含的处理器核数一般不应超过230个,否则事务存储系统运行效率将迅速下降。
