冲突预测实现方法及所用冲突预测处理装置事务存储器

摘要

本发明公开了一种事务存储器的冲突预测处理装置，包括处理器、硬件事务存储器和内部总线；硬件事务存储器内设有投机型高速缓存(201)、写地址缓冲单元(202)、预测恢复高速缓存(203)、冲突预测地址单元(204)和冲突预测寄存器保存单元(205)；写地址缓冲单元(202)分别与处理器和内部总线相连，投机型高速缓存(201)分别与预测恢复高速缓存(203)、冲突预测地址单元(204)和处理器相连，冲突预测寄存器保存单元(205)与内部总线相连。本发明还同时公开了一种事务冲突预测实现方法。采用本发明的事务冲突预测实现方法，能减少事务处理中的冲突损耗。

说明书

技术领域

本发明涉及硬件事务存储器实现，通过微处理器硬件系统与添加的硬件结构相互配合，实现了一种硬件事务存储器中数据冲突预测方法的设计，属于计算机体系结构设计领域。

背景技术

为了提高计算的性能，现代微处理器多采用单片多处理器结构，如图1所示，该结构中一般由多个处理器(处理器Ⅰ101、处理器Ⅱ102、处理器Ⅲ103、处理器Ⅳ104)组成，每个处理器配有各自的缓存(高速缓存105、高速缓存106、高速缓存107、高速缓存108)，多个处理器通过网络或总线(网络或总线109)连接。在多处理器系统中，存在一个全局的共享存储器(全局存储器110)和计数器(111)，分别为各个处理器提供共享资源以及为各个处理器上的事务分配序号。在每个处理器上，分别运行不同的应用线程，这种并发性有效地提高了计算效率和系统性能。但是，多个线程在访问全局的共享存储器中的共享资源时会发生资源冲突，采用加锁机制，使产生数据访问冲突的程序段串行运行。锁机制的缺陷在于：优先级反转、死锁及避免死锁的算法复杂。

为了消除锁机制所带来的系统性能的降低，解决全局共享存储器的资源冲突，斯坦福大学所提出的Transactional Coherence and Consistency的事务存储结构，实现了事务存储机制(如图2所示)。

事务存储技术将数据库技术中的事务思想应用到多个线程并发的访问共享存储资源中，利用事务存储器的原子性替换加锁机制，解决了多处理器共享资源冲突问题。该技术以事务作为并行处理和调度的基本单位，这里事务指一段连续的指令流。系统记录了每个事务对共享存储空间的读写操作，并允许多个事务并行执行，从而提高了系统效率。在事务结束时，系统记录的读写操作被连续提交到共享存储空间上，因此实现了与其他事务对存储资源的互斥访问。

采用事务存储机制能够减少程序员并行编程的复杂性，使程序实现最大限度并行。在事务存储模型中，事务由四个阶段组成：

·事务初始化阶段：识别事务开始执行的指令，保存上下文等信息。

·事务执行阶段：记录事务中的读写操作，并与其他事务进行数据冲突检测，当发生冲突时，重启事务。

·事务等待提交阶段：根据事务出现的时间顺序判断该事务是否可以被提交。

·事务提交阶段：将读写操作提交到共享存储区。

事务型存储机制需要实现的特性包括：原子性，即该事务的执行不可被中断；隔离性，即事务具有一定的执行顺序；一致性，即事务之间数据保证一致。

典型的事务存储器硬件结构一般通过事务写缓冲区、数据高速缓存(cache)以及提交控制单元的设计实现，由投机性高速缓存(201)、写缓冲地址缓存单元(202)和提交控制单元(203)组成，以硬件代替软件复杂度，提高系统效率。基于上述硬件结构，配合不同的冲突检测策略和版本管理方法，从而实现事务存储机制。该机制在在事务起始点保存上下文信息和相应寄存器内容，并将事务读写操作保存在各自的缓存空间。当事务之间发生数据冲突时，无法确定数据冲突发生位置，因此需要清空缓存中的所有操作记录，恢复上下文信息和寄存器内容，重启事务，这样会增加系统开销，牺牲了系统性能。

上述的硬件事务存储机制，在事务执行的过程中，保证了数据一致性，但没有考虑冲突预测的机制，因此事务会由于数据冲突进行回退操作而增加了大量开销，降低了系统效率。

发明内容

本发明要解决的技术问题是提供一种能减少事务处理中的冲突损耗的事务冲突预测实现方法及所用的冲突预测处理装置。

为了解决上述技术问题，本发明提供一种事务存储器的冲突预测处理装置，包括处理器、硬件事务存储器(HTM)和内部总线，硬件事务存储器(HTM)内设有投机型高速缓存、写地址缓冲单元、预测恢复高速缓存、冲突预测地址单元和冲突预测寄存器保存单元；写地址缓冲单元分别与处理器和内部总线相连，投机型高速缓存分别与预测恢复高速缓存、冲突预测地址单元和处理器相连，冲突预测寄存器保存单元与内部总线相连。

本装置是应用于多处理器系统，每个处理器都需要有上述的结构，使用本装置可以完成事务冲突预测。

作为本发明的冲突预测处理装置进行的事务冲突预测实现方法的改进：包括硬件结构和事务执行；

硬件结构相关实现步骤为：

步骤1：冲突预测地址单元的实现；

步骤2：预测恢复高速缓存的实现；

步骤3：冲突预测寄存器保存单元的实现；

事务执行相关实现步骤为：

步骤1：初始化阶段的实现；

步骤2：执行阶段的实现；

步骤3：提交阶段的实现。

作为本发明的事务冲突预测实现方法，其特征是：冲突预测单元用于保存预测的冲突地址表，该表记录了事务发生数据冲突的地址；预测恢复高速缓存用来保存冲突预测之前投机型高速缓存中的数据，用来恢复投机型告诉缓存的数据；冲突预测单元用来保存冲突预测位置处通用寄存器值、状态寄存器值和预测位置地址信息。

作为本发明的冲突预测处理装置进行的事务冲突预测实现方法的进一步改进：事务执行的实现分为3个阶段：初始化阶段的实现，执行阶段的实现，提交阶段的实现；

事务执行初始化阶段是对冲突预测寄存器保存单元进行初始化；

事务执行阶段实现了事务执行时的冲突预测方法，用来判断冲突预测地址单元是否为空时，确定系统是否需要建立一个预测冲突地址表。若冲突预测地址单元非空，判断事务中读指令地址是否与冲突预测地址匹配；若不匹配，则继续执行后续指令；若匹配，则认为读指令发生了数据冲突，对预测位置地址信息进行保存；冲突预测寄存器保存单元及预测恢复高速缓存需要保存相应寄存器和高速缓存中的数据；若冲突预测地址单元为空，则该事务进入执行阶段，发生冲突时，在冲突预测地址单元中保存发生冲突的地址，建立一个预测冲突地址表，以便于后续事务进行冲突预测；

事务提交阶段实现了本地事务提交，其余事务冲突检测及根据预测信息而进行的重启操作。识别到事务进入提交阶段后，清空提交事务对应的预测恢复高速缓存中的数据，广播投机性高速缓存中的数据，其余事务检测是否发生事务读写地址冲突，在发生冲突时，根据记录事务中冲突发生位置，判断冲突预测是否成功。若预测成功，则执行a中操作。若预测失败，则执行b中操作；

a)恢复投机型缓存和相应寄存器的内容，并且根据冲突预测寄存器中预测成功地址信息，进行回退，执行后续指令操作；

b)回退到事务起始点，重启事务。

在现有的硬件事务存储机制中，在事务起始点保存上下文信息和相应寄存器内容，并将事务读写操作保存在各自的缓存空间，当事务之间发生数据冲突时，无法确定数据冲突发生位置，因此需要清空缓存中的所有操作记录，恢复上下文信息和寄存器内容，重启事务，这样会增加系统开销，牺牲了系统性能。而本发明是在原有的硬件结构(投机型高速缓存和写地址缓冲单元)中增加冲突预测地址单元，预测恢复高速缓存和冲突预测寄存器保存单元，如图3所示，实现了一种冲突预测机制，减少了事务处理中的冲突损耗。

本发明通过在事务初始化阶段对冲突预测寄存器保存单元进行初始化操作；在事务执行阶段以及事务提交阶段中添加冲突预测地址匹配操作及预测恢复缓存中数据的缓存操作，来预测事务执行过程中的数据冲突发生位置。

本发明的方法通过对事务执行中数据冲突位置的预测，而确定发生冲突的事务重启位置，从而减少事务由于数据冲突，清空缓存中所有记录以及重新执行而造成的数据损失，提高系统效率，提高了系统性能。

附图说明

下面结合附图对本发明的具体实施方式作进一步详细说明。

图1为多处理器系统结构示意图。

图2典型的硬件事务存储器结构示意图。

图3为本发明的用于支持冲突预测方法的硬件事务存储器结构示意图。

图4为本发明的冲突预测方法中事务执行阶段流程示意图。

图5为本发明的冲突预测方法中事务提交阶段改流程示意图。

具体实施方式

实施例1、一种事务存储器的冲突预测处理装置，包括处理器、硬件事务型存储器(HTM)和内部总线，处理器内设有通用寄存器308和处理器状态寄存器309；该硬件事务型存储器(HTM)内设有投机型高速缓存301、写地址缓冲单元302、预测恢复高速缓存303、冲突预测地址单元304和冲突预测寄存器保存单元305；所述写地址缓冲单元302分别与处理器和内部总线相连，投机型高速缓存301分别与预测恢复高速缓存303、冲突预测地址单元304和处理器相连，冲突预测寄存器保存单元305与内部总线相连。

冲突预测地址单元304保存了一个预测冲突地址表，该地址表是通过系统记录事务发生数据冲突地址而建立的，硬件上可以通过寄存器实现。冲突预测地址单元304所包含的各个部分及其功能如表1所示：

表1

  名称  功能  有效位(V)  指示相应块是否包含有效地址数据  LRF位  说明该块是否可以被替换  数据  保存冲突预测地址值

预测恢复高速缓存303保存了在冲突预测之前投机型高速缓存301中的数据，冲突预测成功后，用来恢复投机型高速缓存301中的数据，在结构上要与投机型高速缓存301结构相一致。该预测恢复高速缓存303结构中所包含的部分及其功能如表2所示：

表2

  名称  功能  有效位(V)  指示相应块是否包含有效数据  投机写标志位(SW)  标识该cache line是否被投机修改。  投机读标志位(SR)  标识该cache line是否被投机读。  标记位(Tag)  判断该cache line是否命中  数据(Data)  存储所使用数据

冲突预测寄存器保存单元205保存冲突预测位置处通用寄存器值308和处理器状态寄存器值309以及预测位置地址信息。

实施例2、一种事务冲突预测实现方法，利用实施例1的冲突预测处理装置，主要通过对事务执行的三个阶段，即事务开始初始化段，事务执行阶段以及事务提交阶段进行改进，来完成事务存储器的冲突预测设计；依次进行步骤：

1、事务初始化阶段中的改进(如图4所示)

a)、事务开始执行401：

事务存储机制通常采用一条特殊指令标志事务的起始，当硬件系统识别出该指令后，事务进入开始初始化阶段。这时需要进行如下操作：清空投机型高速缓存301中的数据，清空冲突预测寄存器保存单元305中的数据。通过总线或网络109仲裁，由硬件实现的计数器111为该事务分配一个序号，该事务序号被保存在提交控制单元306，用来保证事务提交顺序。

b)、硬件保存事务上下文信息402：通过处理器中相应的硬件结构记录通用寄存器信息以及处理器状态寄存器等信息，也就是事务上下文信息。

2、事务执行阶段中的改进(如图4所示)

a)、执行指令403：在处理器307中，运行事务中的指令。投机性高速缓存301会保存读写数据访存信息包括：有效位(V)、投机写标志位(SW)、投机读标志位(SR)的置位，标记位(Tag)、数据(Data)的保存。

b)、判断冲突预测地址单元是否为空404：当冲突预测地址单元304为空时，系统需要在冲突预测地址单元304中建立一个预测冲突地址表(405)，执行步骤c)中的操作。当冲突预测地址单元304为非空时，执行步骤d)中的操作。

c)、建立冲突预测表405：记录正在运行事务发生冲突的地址信息，并将该地址信息保存在冲突预测地址单元304中，后续事务运行时，可根据冲突预测地址单元304中的信息进行冲突预测。需要说明的是，冲突预测地址单元304的大小是固定的，当记录事务发生冲突的地址信息溢出时，采用最近最少使用替换策略进行替换。

d)、判断读指令地址是否和冲突预测地址匹配406：对正在运行事务中的读指令地址与冲突预测地址单元304中的地址进行比较，若匹配，则认为该读指令发生了数据冲突，使用冲突预测寄存器保存单元305将冲突预测地址单元304中匹配地址作为预测位置地址信息add_i(i＝1，2……n)进行保存。同时需要执行步骤g)和h)中的操作；若不匹配，则执行i)步骤中的操作。

g)、保存相应寄存器内容407：冲突预测寄存器保存单元305保存该读指令操作之前的通用寄存器205以及处理器状态寄存器206中的数值(407)，用于冲突预测成功后的恢复操作。

h)、投机性高速缓存的数据拷贝到预测恢复高速缓存408：将投机性高速缓存301的数据拷贝到预测恢复高速缓存303中，当冲突预测成功后，用于投机性高速缓存数据的恢复。

i)、运行后续指令409

3、事务提交阶段的改进(如图4和图5所示)

a)、事务等待提交410：需要对被保存在提交控制单元306中的事务序号进行比较，判断是否符合事务提交顺序要求。当事务满足提交要求时，进入步骤b)。

b)、事务提交411：

清空提交事务所对应的预测恢复高速缓存303中的数据，将提交事务所对应的投机性高速缓存301中的所有写数据通过总线向全局存储器110中提交，并向其余处理器发出提交事务的信号，再将其写地址集合广播到其余处理器。

c)、事务结束412：

事务存储机制在事务提交完成后，通常采用一条特殊指令标志事务的结束，并且清空预测恢复高速缓存303和提交控制单元306。

在此阶段，其余处理器接收到外部提交事务信号503后，需要进行如下的操作：(如图4所示)

Ⅰ)、正在运行的本地事务需要停止执行504，保存上下文信息。

Ⅱ)、判断是否发生数据冲突(505)：将投机性高速缓存301中的读数据地址与广播的写地址集合进行匹配，如果没有匹配，认为没有发生数据冲突，则继续执行指令(502)；否则，执行Ⅲ中的操作。

Ⅲ)、判断预测是否成功(506)：根据冲突预测地址单元304中记录的位置地址信息(add₁，add₂……add_n)判断冲突预测是否成功。当事务中实际发生冲突的最小地址值(conflict₁，conflict₂……conflict_n)小于所有的预测位置地址信息(add₁，add₂……add_n)时，

min(conflict₁，conflict₂……conflict_n)＜min(add₁，add₂……add_n)

认为冲突预测失败，回退到事务起始点，重启事务(501)；否则，执行Ⅳ中操作。

Ⅳ)、在冲突预测方法中，可以根据所面向的不同应用平台，设置允许保存的预测位置地址信息数目n。预测成功的冲突地址(conf_add₁，conf_add₂……conf_add_n)应该属于所保存的预测位置地址信息(add₁，add₂……add_n)的一部分，在执行回退操作时为了保证其正确性，根据冲突预测地址单元304中预测成功地址信息(conf_add₁，conf_add₂……conf_add_n)，选择其中的最小值min(conf_add₁，conf_add₂……conf_add_n)进行回退，执行后续指令(507)。

同时将预测恢复高速缓存303中的数据拷贝到投机型高速缓存301中，并使用冲突预测寄存器保存单元305中的值对寄存器值进行恢复。以最早预测的冲突地址min(conf_add₁，conf_add₂……conf_add_n)为回退位置。

最后，还需要注意的是，以上列举的仅是本发明的一个具体实施例。显然，本发明不限于以上实施例，还可以有许多变形。本领域的普通技术人员能从本发明公开的内容直接导出或联想到的所有变形，均应认为是本发明的保护范围。