论文部分内容阅读
多核体系结构为多线程程序提供了高效的运行平台,程序内部依靠类似于锁和栅栏的机制(例如:临界区、互斥量、信号量和事件等)来实现多线程之间的同步,灵活方便,但同时也存在一定的缺陷。当我们使用栅栏来控制多线程同步时,线程到达栅栏有先后,先到达栅栏的线程需要等待后续线程,这样就因程序内部多线程同步等待而造成了一定的运行时间浪费;经实验测试,这部分时间占整个程序执行时间的35%,如果能够将这一部分时间加以利用,无疑可以提升程序的运行性能。 为了减少多核同步多线程因同步等待所带来的时间浪费的问题,本文提出了基于数据容错的多线程投机方法,让先到达栅栏的线程投机执行,以便利用前面所述的时间浪费。本文针对该机制进行了细致的分析与设计,具体工作如下: 1、本文根据多线程栅栏同步的特点提出了容错数据和容错投机线程的概念。容错数据指的是各个线程到达某一栅栏处携带的数据版本;容错投机线程指的是,携带容错数据进行投机执行的线程。 2、本文提出了容错多线程投机的回滚机制。容错多线程回滚机制方面的研究,本文主要涉及到引发容错多线程回滚的触发条件,容错多线程投机成功的条件(即容错多线程投机无需回滚的条件),以及容错多线程回滚的代价和投机成功无需回滚取得的投机收益。 3、本文提出了容错多线程投机的风险控制策略。由于线程投机执行是一种不可靠的、不确定的、有风险的线程运行行为,为了更好地控制线程的投机执行,我们提出了两种投机风险控制策略,分别是投机风险的栅栏控制策略和投机风险的阈值控制策略;投机风险的栅栏控制策略,是以栅栏为基本单位进行投机监管,允许容错投机线程向前投机到一个或几个栅栏处;投机风险的阈值控制策略,是利用投机线程内部污染数据的个数来衡量投机的风险,当投机风险到达设定的阈值时就不再向前投机。在处理容错投机线程到达最后一个栅栏处或者到达投机风险阈值时,我们又提出了两种处理方法,原地等待法和回滚重投机法。我们详细阐述了这些策略和方法的原理和实现细节,并设计了相应的实验进行数据验证。 本文通过软件模拟的方法来测试上述提出的策略和方法。我们主要考虑了多核多线程程序的任务量均衡性、共享数据量大小以及数据依赖性的特点,经交叉组合设计了8组测试程序以供实验所用。对于栅栏控制策略,我们设置了栅栏投机深度N=1,2,3,实验结果显示,栅栏控制策略-原地等待法和栅栏控制-回滚重投机法都是在N=1时获得最好性能提升,平均分别到达了5.7%和6.3%。对于阈值控制策略,我们将污染数据缓存池容量分别设置为K=2,4,8,16,实验结果显示,在K=8时获得最大性能提升,阈值控制策略-原地等待法和阈值控制策略-回滚重投机法在K=8时分别获得了6.35%和6.6%的性能提升。在多线程投机带来的开销方面,栅栏控制策略的时间开销平均为0.92%,阈值控制策略的原地等待法和回滚重投机法的时间开销分别为1.26%和2.14%,这些时间开销都在可接受的范围之内。 综上所述,本文提出了容错数据和容错投机线程,并在此基础上进一步提出了容错多线程投机机制,使得多核多线程程序的性能有明显的提升。