系统结构第二次实验:设计实现 Tomasulo 调度算法

实验原理

Tomasulo 算法以硬件方式实现了寄存器重命名,允许指令乱序执行,这是提高流水线的吞吐率和效率的一种有效方式。该算法首先出现在 IBM360/91 处理机的浮点处理部件中,后广泛应用于现代处理器设计中。

假设浮点处理部件结构如下图所示。浮点处理部件从取指单元接收指令,存入浮点操作队列。浮点操作队列每拍最多发射1条指令给浮点加法器或浮点乘除法器。 浮点处理部件包含一个浮点加法器和一个浮点乘除法器。浮点加法器为两段流水线,输入端有三个保留站A1、A2、A3,浮点乘除法器为六段流水线,输入端有两个保留站M1,M2。当任意一个保留站中的两个源操作数到齐后,如果对应的操作部件空闲,可以把两个操作数立即送到浮点操作部件中执行。Load Buffer和Store Buffer各缓存三条访存操作。

实现要求

设计实现 Tomasulo 算法模拟器,要求:

  • Tomasulo 算法模拟器能够执行浮点加、减、乘、除运算及 LOAD 和 STORE 操作。为了保持一致性,我们小组采用了【教科书上的指令格式】

    指令格式指令说明指令执行周期保留站/缓冲队列项数
    ADDD F1,F2,F3F1,F2,F3为浮点寄存器,寄存器至少支持F0~F102个周期3
    SUBD F1,F2,F3同上2个周期3
    MULD F1,F2,F3同上10个周期2
    DIVD F1,F2,F3同上40个周期2
    LD F1, NUM, R1F1为寄存器,NUM 为偏移量,R1为基地址2个周期3
    ST F1, NUM, R1同上2个周期3
  • 支持单步执行及连续执行(n 条指令),实时显示算法的运行状况,包括各条指令的运行状态、各寄存器以及内存的值、保留站(Reservation Stations)状态、Load Buffer 和 Store Buffer 缓存的值等;

  • 程序执行完毕后,能够显示指令执行周期数等信息;

  • 为了简化设计,建议模拟器 供编辑内存值功能,以便实现数据输入;浮点除法可不做除 0 判断;

  • 能够以文本方式输入指令序列。

  • 显示界面自由设计,下图仅供参考:

完成内容

  • 能够以文件方式导入指令
  • 能够以文本框编辑方式编辑指令
  • 能够设置FU,RU寄存器的初始值
  • 能够编辑内存值
  • 能够设置实时显示内存内容的起始内存地址(5个)
  • 支持单步和多步连续执行
  • 程序执行完毕后,能够显示指令执行周期数等信息

实现设计思路

后台 算法框架和基本流程

模拟环境:

我们用一次循环来代表一次始终周期,每次循环始终加一.

对于每个时钟周期(一个节拍),一条指令最多只能被执行发射,执行,或者写入中的一种操作(若所需运算数据未就绪,所需运算器件未就绪均会阻塞).即对于一条需要2个周期来执行运算的加法指令,共需要至少1+2+1=4个周期,其运算结果才会被写入目的寄存器.

我们将Load/Store缓冲区和保留站统一处理,即缓冲区和保留站均有Qi,Qj,Vi,Vj,A等数据信息.对于Load保留站,其Qi始终为0,即Vi始终就绪,Vj为计算所得的地址;对于Store缓冲区,其Vi为所要存储的数据,Vj为通过整数寄存器计算所得的地址.

算法流程:

系统在完成初始化后,会将指令按给定的序列加入指令队列,即在UI界面点击开始后,程序会根据给定的指令序列自动初始化指定队列。接下来,对于每一个时钟周期会进行如下操作

(1)发射指令

对于位于指令队列队首的指令,我们先寻找其对应的空闲保留站,若存在,则发射该指令到对应的保留站,更新该保留站的数据信息(包括busy,Vi,Vj,Qi,Qj,A),并更新要写入寄存器的状态.若不存在空闲站,则队首指令将无法流出,该指令会停留在队首等待下个周期。当指令队列清空时,说明所有指令已经流出,不再发射指令.

(2)执行流水线

我们共提供了三条流水线分别处理访存(根据课件认为是一个2段流水线,每段1周期)、加减法、乘除法指令,每条流水线有自己的流水段和相应的各段周期。每条位于保留站的指令必须在其所需数据均准备好才能进入对应的流水线进行执行.(对于Load指令来说,所需数据为整型寄存器所表示的基址,对于Store指令来说,所需数据出了基址还有要存储的数据)

指令进入流水线后,我们通过如下两个过程来模拟流水线运行流程:

  1. 新指令进入流水线
    当保留站中缓存的指令要进入对应的流水线时必须满足两个条件:一,流水线当前进行的运算能够执行该指令(即乘法指令要进入乘除法器的流水线时,必须保证没有除法指令在执行,我们认为加减法和访存不需要改变运算器的功能逻辑,因此加法和减法进入加法器流水线以及访存指令进入访存流水线时没有该要求);二,对应流水线首段空闲,即流水线首段没有指令在占用。
  2. 更新流水线上各个段的指令
    对于每个段的指令,我们会递减其需要的执行周期。当剩余周期为0时,说明该段运算完成,需要进入下一流水段继续运算,此时若下一流水段空闲,则直接进入下一流水段,否则阻塞等待直到其空闲为止,在此期间会持续占用原有流水段。若当前完成段为流水线最后一段,则进行结果运算,并记录结果到对应的保留站,等待写入(对于Store指令我们在此时更新相应的内存)同时释放对流水段的占有。

(3)写入数据:

对于每条完成的指令(除了Store指令),我们会将其结果写入对应的寄存器并更新相应的订阅的保留站的等待数据。我们假设总线在一个周期内可以完成多次数据传输,即对于同一个周期内要进行多条指令的写回时,我们按照顺序将其结果更新到对应的位置,Tomasulo算法保证了该过程不会触发数据相关的错误。

算法状态显示:

在指令的每个时期(发射,执行完毕,写回完毕)完成后,我们会记录对应指令的完成时间,并更新到前台。
在完成每个周期的操作后,我们将保留站和寄存器以及指令的执行信息更新到前台,以供观察。

主要数据结构:

我们通过4个主要的数据结构来执行该算法.

  1. 寄存器class Register:维护了寄存器的数据和状态信息Qi
  2. 指令class Inst: 维护了指令的操作码,操作数,目的地址,指令的运行状态,指令发射,运算完毕,写回的时间
  3. 保留站class ReservationStation: 保留站是关键的数据结构,它维护了保留站的基本数据信息(op,busy,vj,vk,qj,qk,A,result).此外还维护了便于观察保留站状态的各种数据:
    1. execover//保留站所缓存的指令是否已经运算完成
    2. status//保留栈所缓存指令的状态,包括(发射,等待数据,等待运算器相应的流水段空闲,正在运算,运算完毕,保留站空闲)
    3. times: 所缓存的指令还需要在运算器运算的总周期数(不包括等待流水段的时间)
  4. 流水线模拟器class Pipeline: 流水线模拟器维护了各个流水段需要的运行周期,各个流水段正在运行的指令和其所需的剩余的运算时间.我们设计实现的流水线有以下性质:
    1. 对于n段流水线,最多同时支持n条指令在其中运行
    2. 当第i条指令完成第k段流水段运算后,若第i-1条指令还占据第k+1段流水段,则第i条指令会阻塞并持续占用第k段流水段.
    3. 当第i条指令未完成第k段流水段运算时,其不会受其他段指令的影响,即第i+1条指令或者i-1条指令阻塞时,第i条指令能继续进行第k段的运算.
    4. 流水线支持功能切换,即可以切换流水段数量和每段的周期数,以此支持乘除法周期数不一致的要求.但功能切换必须在流水线中所有指令全部流出时才能进行.即若一条除法指令想进入流水线,必须在流水线处理完所有的乘法运算后切换成除法模式后才能进入.
    5. 对于系统默认的参数,我们将访存处理和加法减法处理设计为了2段流水线,每段1周期. 对于乘法为6段流水线.分别为1,1,2,4,1,1周期. 对于除法为6,6,6,6,6,10周期(参数可以在代码中重新自由设置,如设置为Firgure.A31所示的流水线)

前端

程序运行时主窗口如下图所示

程序主界面

如【图 程序主界面】所示,前端的实现中界面采用GridBagLayout()布局模式,顶部是10个操作按钮,点击即可完成对应的设置和执行功能。

其下方依次是指令队列状态展示区,当前周期展示区,内存展示区,保留站状态信息,浮点寄存器状态信息,整型寄存器展示区。

下面一次展示其各个部分的运行方式

从文件导入指令

点击【导入指令文件】按钮,即可进入指令文件选择界面,点击open按钮,默认打开当前工作目录,选择示例代码文件example.txt,点击导入即可导入指令,指令队列展示区会做出对应的更新。

从文件导入指令

文本框方式编辑指令

点击【编辑指令】按钮,即可进入指令编辑界面。指令编辑完成后点击确认即可导入编辑的指令,指令队列展示区会做出对应的更新。

文本框方式编辑指令

设置内存

点击【内存赋值】按钮,即可进入内存编辑界面,在第一个框中输入内存地址(0~4096), 第二个输入框中输入内存值,点击赋值按钮,若输入合法则会更新对应地址处内存。点击关闭按钮退出内存编辑界面。

设置内存

设置内存显示

点击【内存显示】按钮,即可设置内存展示的起始地址(0~4091),输入合法时点击确认即可更新内存展示区。

内存显示设置

多步执行设置

点击【步数设置】按钮,即可进行多步运行步数设置。

步长设置

寄存器设置

点击【设置寄存器】按钮,即可进入寄存器设置界面,页面中可进行FU0FU10, RU0RU10,共22个寄存器的初始值的设置,设置完成后点击保存若输入合法即可完成更改,输入不合法时保持当前值。

寄存器设置

程序运行

初始或点击【重置】按钮时是初始状态,此时可进行指令的导入,编辑,内存赋值,寄存器赋值,步长设置,内存显示设置等功能,点击执行后,即进入执行状态,此时部分设置按钮不可点击,即不可再进行更改指令,设置内存,设置寄存器等操作。此时若点击【步进】按钮,程序则会运行一步,点击执行n步(n可点击【步数设置】按钮进行设置)即可执行多步(n步), 每一次步进都会更新对应部件状态展示区,程序运行结束后则不可继续点击【步进】,【执行n步】按钮。

运行效果图

程序运行说明:

在项目根目录下运行sh run.sh即可,或者在在命令行中输入如下编译运行指令

1
2
3
mkdir bin
javac -d bin/ src/com/company/UI.java src/com/company/Main.java
java -cp bin/ com.company.UI

项目文件说明

1
2
3
4
5
6
7
8
9
10
11
12
13
.
├── README.md 运行说明
├── Report.md 实验报告(MD版)
├── Tomasulo调度算法实验报告.pdf 实验报告PDF版
├── example_book.txt 教科书中的示例
├── example_阻塞等待指令序列.txt 会在流水线各个段发生阻塞等待指令序列
├── example_RAW相关的ST指令序列.txt 有 RAW 相关的 ST 指令序列
├── run.sh 项目编译运行脚本
└── src
└── com
└── company
├── Main.java 后台代码
└── UI.java 前端代码

运行实例

对于课件中所给的样例指令序列:

1
2
3
4
5
6
LD F6, 34, R2
LD F2, 45, R3
MULD F0, F2, F4
SUBD F8, F6, F2
DIVD F10, F0, F6
ADDD F6, F8, F2

我们得到的指令队列状态与课件中相同:

指令发射指令时间执行完成时间写入结果时间
LD F6,34,R2134
LD F2,45,R3245
MULD F0,F2,F431516
SUBD F8,F6,F2478
DIVD F10,F0,F655657
ADDD F6,F8,F261011

运行结束需要57个周期与课件一致

对于有RAW相关的ST指令序列:

1
2
3
ST F1,0,R2
MULD F0, F2, F4
ST F0,4,R0

也能得到正确结果:

指令发射指令时间执行完成时间写入结果时间
ST F1,0,R2134
MULD F0,F2,F421213
ST F0,4,R031516

对于会在流水线各个段发生阻塞等待指令序列:

1
2
3
4
5
6
DIVD F6, F0, F4
MULD F2, F1, F5
MULD F0, F6, F4
SUBD F8, F6, F2
DIVD F10, F0, F6
ADDD F6, F8, F2

我们也能得到正确的结果:

指令发射指令时间执行完成时间写入结果时间
DIVD F6,F0,F414142
MULD F2,F1,F525152
MULD F0,F6,F4435556
SUBD F8,F6,F2445455
DIVD F10,F0,F6539697
ADDD F6,F8,F2545758

在该例子中前三条指令间存在结构冲突,由于除法在流水线中执行时,新来的乘法指令必须等待除法指令完成才能进入流水线,因此乘法指令完成时的时钟周期为51(42进入首段,51完成最后一段).

另外由于保留站占满,第三条乘法指令等到43周期才被发射.

对于第三条乘法指令,由于乘法流水线各个段的运行周期为(1,1,2,4,1,1),第三条指令会在第三段完成后阻塞等待2个时钟周期,以等待第二条乘法指令完成第4段,因此第三条乘法指令的执行完成时间为55(44进入,55完成,共用12个周期,比第二条慢了2(慢2周期进入)+2(期间等待2周期)=4个周期而不是2个周期,在第48,49会看到对应的保留站状态为WAIT_ALU意为等待处理器)

打赏