CN103761073A - 一种面向ARMv7的基于推测的指令动态调度方法 - Google Patents

Abstract

本发明公开了一种面向ARMv7的基于推测的指令动态调度方法，在影响当前指令条件码的指令提交前，推测当前指令的系统状态值，推测执行当前指令，使得指令不会因为等待前面能够更改系统状态的指令的结果而堵塞流水线，提高了流水线的并行处理能力。本发明实现容易，尤其适合硬件实现，具有较大的实用价值。

Description

一种面向ARMv7的基于推测的指令动态调度方法

技术领域

本发明涉及微处理器体系结构领域，尤其涉及一种面向ARMv7的基于推测的指令动态调度方法。

背景技术

微处理器体系结构中，由于当前指令需要前面的指令产生的结果作为源操作数，该结果还未产生时，当前指令会等待结果产生，此时，会发生堵塞后面可以执行的指令继续执行的情况，指令动态调度技术的核心是就是避免出现这种情况。

在动态调度的流水线结构中，指令的取指阶段和译码阶段都是按照程序顺序执行的，但是执行阶段是可以乱序执行的，只要保证指令间没有各种相关关系就可以执行，在有足够资源的流水线结构中多条指令也可以同时执行。指令执行结束后，可以有序提交结果也可以乱序提交。但是为了简化操作系统对于例外的处理，现代的处理器都是按照程序表述的指令的顺序有序的结束。

乱序执行处理器的指令动态调度是指令在流水线中执行过程中，由硬件自动的调度指令的执行顺序，不必一定要按照取指令的顺序执行，从而避免由于各种数据相关导致的流水线堵塞。为了保证程序最终运行提交的结果与原始的程序结果一致也即是保证程序执行结果的一致，硬件在动态调度时候要有确保有能力自动够判并且确保遵循指令之间的相关关系。

ARM的32位架构是移动设备中最广泛使用的架构，也是32位嵌入式系统中最广泛使用的架构。根据ARM Holdings的数据：在2005年，98%的手机至少使用了一个ARM处理器；在2010年，ARM架构的处理器出货量达到了61亿片，这占据了智能手机95%的份额，占据了数字电视和机顶盒市场的35%；在2013年，生成了大约100亿颗ARM芯片。本发明提出的动态调度的优化方法，正是面向采用32位ARMv7指令集架构的乱序执行处理器的。

相对于其它RISC指令集架构，ARMv7指令集一个不寻常的特性是每条指令的编码中都有条件码，每条指令的执行与否都要由其条件码决定，这个特性虽然在某种程度上可以减少编译后代码的数量，但是若是使用通常的指令调度方法，由于指令间的控制相关严重，所以这个特性将会显著的降低了处理器执行该指令集时，处理器并行处理的能力，从而直接降低处理器性能。

发明内容

本发明所要解决的技术问题是针对背景技术中的缺陷，提供一种指令集控制相关不大、并行能力较强的面向ARMv7的基于推测的指令动态调度方法。

本发明为解决上述技术问题采用以下技术方案：

一种面向ARMv7的基于推测的指令动态调度方法，具体调度方法如下：

步骤1），根据上一条指令执行产生的实际系统状态值推测得到当前指令的系统状态推测值，并判断当前指令是有条件执行还是无条件执行，如果是无条件执行，则送到发射队列，正常发射执行后提交，然后执行步骤6）；如果是有条件执行，则执行步骤2）；

步骤2），判断当前指令的系统状态推测值是否等于当前指令的实际系统状态值，如果等于，执行步骤3）；如果不等于，则判断当前指令的实际系统状态值是否满足当前指令的执行条件，若满足执行步骤4），若不满足则执行步骤5）；

步骤3），判断当前指令的执行条件是否满足，如果不满足，将当前指令执行的结果正常提交，然后执行步骤6）；如果满足，将当前指令在发射队列中的发射状态更改为已被发射，同时取消执行当前指令；

步骤4），判断当前指令的执行条件是否满足，如果满足，则将该指令正常发射执行后提交，然后执行步骤6）；如果不满足，将当前指令的执行条件状态更改为满足，然后将该指令正常发射执行后提交，并且执行步骤6）；

步骤5），判断当前指令的执行条件是否满足，如果满足，则判断当前指令是否已经执行完在等待提交，如果是，则置该指令为无效，取消该指令的提交；如果不满足，将当前指令在发射队列中的发射状态更改为已被发射，同时取消该指令的发射；

步骤6），判断等待被提交的指令是否可以修改cpu的系统状态字段，如果不可以修改，则提交后执行结束；如果可以修改，则依序找到下一个可以修改cpu的系统状态值的指令，将该指令与前一个可以修改cpu的系统状态值的指令之间的所有指令、以及该指令的实际系统状态值修改为当前指令执行产生的实际系统状态值。

本发明采用以上技术方案与现有技术相比，具有以下技术效果：

1. 通过对指令条件码所使用的系统状态值进行预测，使得指令不会因为等待前面能够更改系统状态的指令的结果而堵塞流水线，提高了流水线的并行处理能力；

2. 通过给发射队列中的项添加额外的字段，使得指令本身的信息和外部添加到该指令的信息更加清晰；

3. 通过使用由两位状态编码构成四个状态的状态机来进行系统状态实际值字段预测，在不显著提高硬件复杂度的情况下，提高了预测的准确率；

4. 对每条指令都是分两个阶段进行执行条件满足字段的判断，使得每个阶段的逻辑比较简单，有利于提高时钟频率；

5. 算法复杂度不高，条理清晰，适合硬件实现，对于乱序执行结构来说资源的消耗比较合理。

附图说明

图1是系统状态推测值字段状态机状态转换图；

图2是推测执行的流程图；

图3是发射队列中的项的组成；

图4是重排序缓存中的项中新增加的域。

具体实施方式

下面结合附图对本发明的技术方案做进一步的详细说明：

本发明公开了一种面向ARMv7的基于推测的指令动态调度方法，具体调度方法如下：

步骤1），根据上一条指令执行产生的实际系统状态值推测得到当前指令的系统状态推测值，并判断当前指令是有条件执行还是无条件执行，如果是无条件执行，则送到发射队列，正常发射执行后提交，然后执行步骤6）；如果是有条件执行，则执行步骤2）；

步骤2），判断当前指令的系统状态推测值是否等于当前指令的实际系统状态值，如果等于，执行步骤3）；如果不等于，则判断当前指令的实际系统状态值是否满足当前指令的执行条件，若满足执行步骤4），若不满足则执行步骤5）；

步骤3），判断当前指令的执行条件是否满足，如果不满足，将当前指令执行的结果正常提交，然后执行步骤6）；如果满足，将当前指令在发射队列中的发射状态更改为已被发射，同时取消执行当前指令；

步骤4），判断当前指令的执行条件是否满足，如果满足，则将该指令正常发射执行后提交，然后执行步骤6）；如果不满足，将当前指令的执行条件状态更改为满足，然后将该指令正常发射执行后提交，并且执行步骤6）；

步骤5），判断当前指令的执行条件是否满足，如果满足，则判断当前指令是否已经执行完在等待提交，如果是，则置该指令为无效，取消该指令的提交；如果不满足，将当前指令在发射队列中的发射状态更改为已被发射，同时取消该指令的发射；

步骤6），判断等待被提交的指令是否可以修改cpu的系统状态字段，如果不可以修改，则提交后执行结束；如果可以修改，则依序找到下一个可以修改cpu的系统状态值的指令，将该指令与前一个可以修改cpu的系统状态值的指令之间的所有指令、以及该指令的实际系统状态值修改为当前指令执行产生的实际系统状态值。

系统状态推测值状态机将当前最新的系统状态值作为状态机输入，产生指令的系统状态推测值字段，并与指令条件码字段进行比较得出该指令的执行条件满足字段。发射队列接受指令信息包括来自状态机的系统状态推测值和执行条件满足值，将可以执行的指令送去读寄存器，进而执行。重排序缓存中提交已经执行完，并且可以提交的指令，对于能够更改系统状态的指令，还要更新后续指令的系统状态实际值字段，更新指令有效性同时将更新指令的系统状态推测值与系统状态实际值比较结果、系统状态实际值与指令条件码字段的比较结果和指令的重排序缓存编号一起送到发射队列。

指令进入寄存器重命名阶段后，如图1所示，系统状态推测值字段的每一位，都用一个独立的有四个状态的有限状态机来根据系统状态实际值字段的相应位的变化来对其进行更改。只有连续两次该值都是向与原始值相反的方向变化，该值才会发生翻转。每个周期，系统状态推测值状态机将当前周期的系统状态实际值作为输入，得到指令的系统状态推测值字段值。根据系统状态推测值字段与该指令的指令条件码字段进行比较，得出指令的执行条件满足的值。该指令的系统状态推测值字段，执行条件满足字段和指令条件码字段同时被存入重排序缓存，重排序缓存分配给该指令的重排序缓存编号字段随该指令进入发射队列。

发射队列中发射状态字段为1的指令可以被覆盖掉。发射队列逻辑在其第一个周期对执行条件满足字段为无效但是实际重排序缓存表明是有效的指令的执行条件满足字段置为有效。发射队列逻辑在其第二个周期对执行条件满足字段为无效并且实际重排序缓存表明其确实无效的指令的发射状态字段置为1。

发射队列在其第一个周期读入指令，同时读入来自重排序缓存的指令的执行条件满足字段信息，更新执行条件满足字段原来为0，然而重排序缓存表明其执行条件满足字段为1的指令的执行条件满足字段为1。并且将没有被发射的指令向队列底部移动，将顶部由于移动产生的旧项除了新读入的指令之外的项置为无效。

发射队列在其第二个周期首先将执行条件满足字段为0，并且重排序缓存表明其确实为0的指令的发射状态字段置为1，表明其可被覆盖掉并且不能被发射。因为现在存放指令的队列中的指令是按时间排列的，比较老的指令存放靠近底部，比较新的指令存放靠近在队列顶部。这样实现最老最先被选择的机制，只要按照位置从队列的底部开始选择预定数数目的指令就可以实现。

如图2所示,相对于传统的发射队列和重排序缓存，指令在进入本发明提出的发射队列和重排序缓存中需要额外进行的逻辑判断。每个周期重排序缓存提交指令的时候，首先判断重排序缓存中的指令条件码字段若其值为4’b1111或是4’b1110表明其是无条件执行指令，一旦执行完成并且处于队列顶部可以提交的位置就提交，并且若可修改系统状态字段为1，则其系统状态实际值字段将被复制给其随后的所有指令的系统状态实际值字段，直到出现另一条可修改系统状态字段为1的指令则停止复制。

在该条指令不是无条件执行的情况下：判断其系统状态推测值字段若与其系统状态实际值字段相等，1：若RaCond为0，则置指令队列中的发射状态字段为1；2：若RaCond为1，则提交该条指令，并且若其可修改系统状态字段为1，则也要复制其系统状态实际值字段给其随后的所有指令的系统状态实际值字段，直到出现另一条可修改系统状态字段为1的指令则停止复制。

若判断其系统状态推测值字段若与其系统状态实际值字段不相等，1：若系统状态实际值字段给出的状态信息满足指令条件码字段，则在执行条件满足字段为1时，该指令被提交，并且在可修改系统状态字段为1时做同样的系统状态实际值字段复制操作；在执行条件满足字段为0时，需要将其在指令队列中的执行条件满足字段置为1，指令将被随后执行。2：若系统状态实际值字段给出的状态信息不满足指令条件码字段，则在执行条件满足字段为1时，该条指令将被取消掉，不会被提交；在执行条件满足字段为0时，则置指令队列中的发射状态字段为1。

如图3所示,在本发明中为发射队列每个项新添加重排序缓存编号字段，执行条件满足字段和发射状态字段三个字段。重排序缓存编号字段用于表明该指令在重排序缓存中的编号，当指令从寄存器重命名阶段被送出时，会送到重排序缓存和发射队列中。重排序缓存会将该指令在重排序缓存中的编号送到该指令在发射队列的重排序缓存编号字段中。执行条件满足字段用于表明该条指令在寄存器重命名阶段时，该指令的执行条件码是否被满足。发射状态字段用于表明该条指令是否被发射出去。

如图4所示, 在本发明的重排序缓存中为每个项新添加系统状态推测值，执行条件满足和系统状态实际值字段3个字段。系统状态推测值字段表明该条指令在执行时所使用的相应的伪系统状态寄存器的值。执行条件满足字段与指令队列中执行条件满足字段含义相同，用于表明该条指令是否满足其执行条件。系统状态实际值字段用于存储能够改变系统状态寄存器的指令所产生的用于更改系统状态寄存器的值。可修改系统状态字段用于表明这条指令是否改变系统状态寄存器的值。另外，从原始指令中复制指令条件码字段用于存储指令中的条件码字段，指令中的条件码字段用于与系统状态寄存器的相应字段进行比较从而决定指令是否可以被执行。

Claims (1)

1.一种面向ARMv7的基于推测的指令动态调度方法，其特征在于，具体调度方法如下：

步骤1），根据上一条指令执行产生的实际系统状态值推测得到当前指令的系统状态推测值，并判断当前指令是有条件执行还是无条件执行，如果是无条件执行，则送到发射队列，正常发射执行后提交，然后执行步骤6）；如果是有条件执行，则执行步骤2）；

步骤2），判断当前指令的系统状态推测值是否等于当前指令的实际系统状态值，如果等于，执行步骤3）；如果不等于，则判断当前指令的实际系统状态值是否满足当前指令的执行条件，若满足执行步骤4），若不满足则执行步骤5）；

步骤3），判断当前指令的执行条件是否满足，如果不满足，将当前指令执行的结果正常提交，然后执行步骤6）；如果满足，将当前指令在发射队列中的发射状态更改为已被发射，同时取消执行当前指令；

步骤4），判断当前指令的执行条件是否满足，如果满足，则将该指令正常发射执行后提交，然后执行步骤6）；如果不满足，将当前指令的执行条件状态更改为满足，然后将该指令正常发射执行后提交，并且执行步骤6）；

步骤5），判断当前指令的执行条件是否满足，如果满足，则判断当前指令是否已经执行完在等待提交，如果是，则置该指令为无效，取消该指令的提交；如果不满足，将当前指令在发射队列中的发射状态更改为已被发射，同时取消该指令的发射；

步骤6），判断等待被提交的指令是否可以修改cpu的系统状态字段，如果不可以修改，则提交后执行结束；如果可以修改，则依序找到下一个可以修改cpu的系统状态值的指令，将该指令与前一个可以修改cpu的系统状态值的指令之间的所有指令、以及该指令的实际系统状态值修改为当前指令执行产生的实际系统状态值。

Images