一种应用于线程级推测并行的限制性值传递方法和装置

摘要

本发明提出了一种应用于线程级推测并行的限制性值传递方法和装置，在冲突发生时可以通过值传递的方法来减少系统的总执行时间。也就是说只有在满足特定的条件，冲突线程才可能会受到需要的数据，否则就只会按原始系统的方式执行。这是一种轻量级的值传递方法，与彻底的值传递和值预测方法相比，具有硬件和协议复杂度低的优点，但是在一般情况下性能可能会不如彻底值传递和值预测。通过实验数据分析，与值预测模型相比，发现限制性值传递模型并没有太大的性能损失。本装置是在LogSPoTM模型上实现与验证的，但是它也适用于其他线程级系统。

说明书

技术领域

本发明属于计算机微处理器结构设计领域，特别涉及一种可有效地提高多线程系统性能 的轻量级值传递方法和装置。

背景技术

推测多线程技术和事务存储技术

随着多核芯片(Chip Multi-Processor，CMP)时代的到来，如何将传统上难以并行化 的串行程序线程化以加速单个程序的执行，同时也为片上越来越多的计算核心提供更多的可 并行执行的计算任务以提高片上资源的利用率，已成为学术界和工业界共同关注的热点研究 问题。

为了开发更多的多核芯片上可利用的线程级并行性，解决并行程序正确性维护给并行编 程带来的复杂性和对性能的制约问题，学术界从不同的角度分别提出了线程级推测 (Thread-Level Speculation，TLS)和事务存储(Transactional Memory，TM)两种技术。 TLS旨在打破线程间依赖对线程并行执行的限制，增加程序并行执行的机会。当编译器或者 程序员无法确定线程候选者间完备的依赖关系时，不需要采用保守的策略放弃并行或是加入 大量冗余的同步保护机制，可以无视可能存在的依赖直接并行化，串行语义的维护由运行时 支持推测执行的硬件机制来保证，从而具有最大程度地挖掘程序中的并行性的技术潜力。TM 旨在为显式的锁同步机制寻找替代方案，通过运行时系统提供的隐式同步机制，实现无锁的 共享存储编程。由于不需要请求锁和解锁，因此这也是一种非阻塞的同步方式，既解决了锁 机制中存在的死锁、优先级倒置等正确性问题，也解决了锁粒度可能对性能造成的影响。TM 由系统自动维护来自多个线程或执行单元的并发操作对共享存储结构状态修改时的语义一 致性。TLS和TM的共同点在于都能够降低并行编程的难度，增加线程并行执行的机会；在硬 件方面也提出了类似的支持推测访问、数据缓存、冲突取消的要求。

为了扩大这两种技术的应用范围，研究者们提出了一些TM和TLS的混合模型，其中比 较典型的有斯坦福大学的TCC，伊利诺伊香槟分校的Bulk，还有中国科学技术大学提出的 LogSPoTM。其中，LogSPoTM是基于LogTM的基础上实现的，给原有的TM系统增加了对TLS 语义的支持。LogSPoTM的执行模式如附图1所示，分成并行(灰线)和串行(黑线)两个部 分。对于串行部分，为了保证程序的正确性，线程必须按照优先级从高到低按序提交。 LogSPoTM是基于网络互连的结构(TCC和Bulk都是基于总线互连)，可扩放性较好。在系统 硬件复杂度方面，LogSPoTM比较适中，适合系统功能的进一步扩展。

推测多线程技术和事务存储技术的存在问题

正如上面提到的，当程序间的数据冲突依赖比例较低的时候，TLS和TM技术在多核平台 上都能够获得比较好的性能。但是当程序中存在较多的数据冲突依赖时，系统性能会变得非 常糟糕。由此看来，TLS和TM系统的程序适用范围是比较有限的，这也是通用处理器制造商 为什么一直都不采用这两种技术进行实际生产的主要原因。

为了缓解这个问题，有一些学者已经提出了一些值传递方法来加速冲突依赖比较多的并 行多线程程序，比如意识依赖事务存储技术(DATM)。这是一种激进的值传递技术；也就是 说，只要一个事务触发了数据依赖，它就可以从上一个事务中接收到所需要的数据并继续执 行。在一些测试程序中虽然DATM取得比较好的加速比，但是它的实用性并不好。首先，DATM 是基于总线一致性协议实现的，对于可扩放性比较好的目录一致性协议并不能直接适用，需 要进行大量的协议改进和验证。其次，DATM对MSI总线一致性协议进行了大规模的修改，把 原来只有3个状态状态机猛增到了13个状态，并伴有复杂状态转换机制。如果想要把这种 思想完整地移植到一般的目录结构中，状态转换图将会变得比总线结构更加复杂，这在现实 的系统基本是不可能实现的。最后，DATM在一般的事务存储系统上添加了比较大的硬件代价， 这也是处理器制造商所不愿意接受的。

本发明是以提高系统性能为目标，在程序数据冲突依赖严重时，通过限制性值传递的方 法来缓解性能差的矛盾。在改进的过程中还要重点考虑硬件代价的问题，尽量少去修改硬件 结构。另外还可以借助值传递技术来解决一些TLS&TM混合模型(如LogSPoTM)的假共享问 题，可以进一步提高系统性能。

发明内容

本发明的核心问题是采用尽量少的硬件代价来缓解TM和TLS性能矛盾，因此我们提 出了一种应用于线程级推测并行的限制性值传递方法和装置。它是原始系统与激进值传递系 统的一种折中。从实验平均结果来看，限制性值传递方法也能取得比较吸引人的性能，而且 硬件复杂度相对较低，一致性协议改动小，具有很好的移植性。我们在LogSPoTM模型为平 台实现了这种限制性值传递技术。我们选取LogSPoTM系统主要是因为其硬件复杂度比现有 的其他TM&TLS混合系统低，而且是基于目录结构，具有较好的扩放性。但是限制性值传递 技术同样适用于其他TM和TLS系统。

LogSPoTM支持TM和TLS两种语义，在本说明书中，我们仅以TLS作为例子说明。为了 减少数据冲突依赖所带来的系统性能损失，我们可以采用增加值传递机制来缓解。附图2(a) 中的是原始LogSPoTM模型的冲突依赖处理方式，冲突发生时，优先级低的线程只有在等待 优先级高的线程提交完成后才能继续执行。图2(b)采用了值传递的方法，在发生数据冲突 依赖时，优先级高的线程会给优先级低的线程发送所需要的数据，让优先级低的后续线程继 续执行，并按序提交，从而节省总的系统执行时间。但是如果发送线程对传递的数据做了修 改，必须及时通知接受线程。为了保证系统的正确性，接收线程必须回滚并重新执行。

上面提到的关于激进值传递(DATM)的缺点，所以本发明提出一种限制性值传递的方法。 附图3(b)给出了限制性值传递的执行模式。图中线程的优先级如下：T1＞T2＞T3。共享数据 X被T1占有。当T2向还没有提交的T1请求数据X时，T1会向T2传递这个数据，不像原始 LogSPoTM一样直接发送NACK让T2空等待，这时T2可以继续执行。当T3也向T1请求数据 X时，限制性值传递系统会和原始的LogSPoTM一样，让T1给T3发送NACK，而不像激进值 传递系统那样给T3发送数据X。也就是说，系统只要在满足一定的约定条件下才会给请求的 线程发送相应的数据，否则只会按照原始的LogSPoTM模式来执行。限制性值传递技术必须 同时满足如下规则才允许传递数据：

(1)数据所有者线程必须没有给其他线程发送过任何数据。

(2)数据所有者线程必须没有接收过其他任何线程发送过来的数据。

(3)数据所有者线程只会给优先级比它低的线程发送数据(如果线程是有序的)。

对于限制性值传递技术的硬件代价，我们只在原始的LogSPoTM系统上作了微量的修改。 我们给每个处理器增加了两个寄存器组：数据发送寄存器组和数据接受寄存器组。根据上面 提到的数据限制性传递规则，每个处理器上面的两个寄存器组是不会同时被使用的。附图4 给出了具体字段说明。RID和SID分别记录了接收数据的处理器编号和发送数据的处理器编 号。ADD保存的是该传递数据的地址。DATA保存的是该数据的值。值得说明的是，接收线程 接收到数据以后，对该数据的修改操作只在接收寄存器中进行，最后在该线程提交时才会写 回cache中。BITS是用来解决假共享问题的，BITS的位数与cache行的字节数相同并一一 对应。假共享问题是由于cache的组织结构和冲突检测机制的共同作用引起的。在当前主流 的计算机系统中，cache结构都是以行为单位来组织的，即每一个行对应多个连续的地址空 间。而当LogSPoTM进行数据的冲突检测时，是以cache行为单位进行检测的。也就是说， 如果两个线程访问的是同一个cache行的不同地址单元，系统也会把它当成数据冲突来处理， 虽然事实上并没有发送冲突，这就是所谓的假共享问题。在一些TM&TLS混合系统中(如TCC)， 假共享问题得到了比较好的解决。但是这些方法并不适用于LogSPoTM模型，假共享问题在 LogSPoTM中一直没有得到很好的解决，并在很多时候成为性能的瓶颈。本发明通过引入了值 传递机制，只需要增加一个BITS寄存器组就可以很大程度地缓解假共享带来的性能损失， 进一步提高系统性能，通过8个基准程序的测试，平均来看，在4线程的配置中获得了25.8％ 的性能提升。

概括来说，本发明是一种限制性值传递的方法和系统，以事物存储和线程级推测混合 模型为基础。在线程之间发生冲突依赖时，优先级高的线程在满足条件的情况下会给优先级 低的线程发送数据，让它停止等待，继续执行程序。如果不满足发送条件，就和一般的推测 系统一样，优先级低的线程会进行等待。为了保证程序结构的正确性，还通过发送修改数据 的方法建立了一套发送数据的验证机制。

本发明提出一种应用于线程级推测并行的限制性值传递装置，包括片上多处理器，事务 存储功能部件，值传递部件，还包括支持推测执行的处理器核，增加时间戳的cache控制器， 增加了读写位的L1数据cache，增加了读写位的L2cache和保证传递正常执行的数据发送寄 存器组和数据接收寄存器组。

本发明还提出一种根据权利要求1的装置进行限制性值传递方法，包括以下步骤：

步骤1，系统检测到数据冲突，优先级高的线程检测是否满足传递数据的条件，满足就 给优先级低的线程发送数据，否则只发送Nack消息，此时优先级低的线程只能等待；

步骤2，优先级低的线程收到传递过来的数据以后，会把它存放在接收数据寄存器中， 然后低优先级线程用这个数据继续执行程序；只要该低优先级线程不发生提交或回退，以后 访问到这个冲突数据块时都直接在接收数据寄存器上操作；

步骤3，如果优先级较高的发送线程重写了发送过的数据块，该高优先级线程就会把修 改的部分发送给接收线程；接收线程会进行验证，看看修改的部分是否已经使用过；如果使 用过，就要进行回退操作。如果没有使用过，就进行数据融合操作。

本发明的优点和积极效果主要表现在：

通过限制性值传递方法缓解TM或TLS系统在数据冲突依赖严重时性能差的矛盾，有效 地减少系统性能表现极差的情况。

有效地解决LogSPoTM的假共享问题，进一步提高系统性能，并拓展LogSPoTM等多线程 系统的应用范围。

硬件复杂度比较低，一致性协议修改不大，具有很好的可移植性。 此处增加附图说明

附图说明

图1.LogSPoTM执行模式示意图；

图2.值传递在LogSPoTM中的应用模式图(a)是原始LogSPoTM系统中发生冲突后的线程 处理方法；图(b)是增加值传递机制的线程处理方法；

图3.多线程环境中的限制性值传递LogSPoTM模型执行模式，图(a)是多线程请求同一 数据块情况下LogSPoTM的处理方法；图(b)是增加值传递机制后的处理方法；

图4.限制性值传递模型在原始LogSPoTM模型基础上所添加的硬件；

图5.一个存在假共享的程序在限制性值传递LogSPoTM模型的执行过程，图(a)是两个 存在假共享的线程代码；图(b)是限制性值传递LogSPoTM系统在执行图(a)代码时寄存 器组的变化情况。

具体实施方式

下面将通过一个带有数据假共享的程序片段来展示两组添加的寄存器的值的变化情况， 以此说明限制性值传递技术在LogSPoTM中的具体工作过程。附图5(a)给出了两个事务， 它们执行各自相应的代码。我们假设事务1的优先级高于事务2，每个cache行有4个字节， 也就是说，地址空间0到3号地址属于同一个cache行。这样，事务1与事务2在冲突检测 时就有可能会触发冲突，虽然事实上它们并没有数据依赖。

附图5(b)给出了事务的执行变化过程。左边的数据发送寄存器组来自事务1所在的处 理器核，右边的数据接收寄存器则是来自运行事务2的处理器核。执行步骤如下：

(1)发送寄存器组和接收寄存器组都是初始值，事务1和事务2都执行事务开始指令。

(2)事务1对地址0进行了写操作。这次写操作是直接对cache操作，并没有其他事务 请求数据。所以事务1的发送数据寄存器组没有变化。

(3)事务2对地址1进行写操作。由于冲突检测机制和cache组织结构的原因，系统触 发了数据冲突。这种情况是符合限制性值传递的条件，所以事务1给事务2发送数据(整个 cache行)。具体操作的是事务1把数据从cache拷贝到发送数据寄存器组中，做好相关的信 息记录。然后再发送给事务2，事务2收到数据后在接收数据寄存器做好记录，并在BITS 位记录好事务2对cache行的操作位(读或写操作都会记录，本例中事务2对地址1进行了 写操作，所以BITS第二位从0变为1)。然后继续执行程序。

(4)事务1对地址2进行写操作。由于地址2所在的cache行和保存在发送寄存器组的 cache相同，所以系统在对事务1的cache进行写操作的同时，还要对发送数据寄存器进行 写操作，并把修改的数据部分(修改的部分，不一定是完整的cache行)发送给事务2。

(5)事务2接收到修改数据信息以后，检测BITS位，发现事务1发送过来的数据自己 并没有使用过，所以只需要把接收到的修改数据合并，无需进行回退操作，有效地避免了假 共享问题。但是如果自己已经使用过刚接收到的修改的数据，那就发生了真的数据冲突，这 时为了保证程序结果的正确性，就必需进行回退操作。这时候事务2已经执行完全部操作， 但是由于优先级更高的事务1还没有提交，所以只能等待。

(6)事务1执行完成并提交，清空发送数据寄存器组。然后事务2才允许提交，并把 接收寄存器的值写回cache中，最后清空接收数据寄存器组。

通过以上例子可以看出，本发明不仅给冲突线程之间提供了值传递的优势，而且还能解 决系统大部分的假共享问题，具有较大的性能提升空间。