北京大学计算机科学技术系计算机系统结构教研室

高等计算机系统结构

Tomasulo算法

（第四讲）

程旭

2004年3月8日

北京大学计算机科学技术系________________________________________________________________计算机系统结构教研室

上一讲小结鎏M

■软件或硬件的指令级并行（ILP）♦

■循环级并行最容易判定

■软件并行性取决于程序，如果硬件不能支持就出现冒险

■软件相关性/编译器复杂性决定编译中是否能展开循环

•存储器相关是最难判定的

硬件开采ILP—动态调度（dynamicscheduling）

•在编译时有些相关情况不能真正判定，可以简化编译器。

•针对某一机器产生的代码可以在另一机器上有效运行

■记分板的核心思想：允许暂停之后的指令提前处理（译

码=>发射指令&读取操作数）

•允许乱序执行=>乱序完成

•ID段检测所有的结构冒险

北京大学计算机科学技术系计算机系统结构教研室

相关和冒险

PipelineCPI=IdealpipelineCPI+Structural

stalls+Datahazardstalls+Controlstalls

■数据相关和冒险

・数据相关(Datadependences)

•名称相关(Namedependences)

/反相关(antidependence)

/输出相关(outputdependence)

•数据冒险

dRAW冒险（由数据相关引起）

dWAR冒险（由反相关引起）

dWAW冒险（由输出相关引起）

•存储器（Memory-included）相关和冒险

■控制相关

dBranch

dExceptionandIinterruption

北京大学计算机科学技术系计算机系统结构教研室

记分板体系结构

FPMult

FPMult-s

t

u

n

o

u

o

.

w

n

L

学计算秋科学技术系计算机系统结构教研室

记分板控制的四级

■发射一指令译码并检测结构冒险（ID1）

•按照程序的次序发射指令（进行冒险检测）

•如果存在结构冒险暂停发射

•如果带发射的指令与已发射但尚未完成的指令

之间存在输出相关，则暂停发射（无WAW冒险）

■读操作数一等待到没有数据冒险，再读取操作

数（ID2）

•由于将等待未完成指令写回其结果，因而在该阶

段，可解决所有的真数据相关（RAW冒险）

•在该模型中，无数据前递！

北京大学计算机科学技术系计算机系统结擅教型E室

记分板控制的四级(续一)

■执行一对操作数进行操作(EX)

•接收到操作数之后，功能部件开始执行。当产生

结果之后，它通报记分板：已经完成执行。

■写结果一完成执行(WB)

•暂停直到与以前的指令没有WAR冒险：

示例:DIVDFO,F2,F4

ADDDF10,F0,F8

SUBDF8,F8,F14

CDC6600的记分板将暂停SUBD指令，直到ADDD指

令读取了操作数。

北京大学计算机科学技术系计算机系统结构教研室

记分板的三个主要组成部分

1.Instructionstatus-whichof4stepstheinstructionisin

2.Functionalunitstatus-Indicatesthestateofthefunctional

unit(FU).9fieldsforeachfunctionalunit

Busy—Indicateswhethertheunitisbusyornot

Op-Operationtoperformintheunit(e.g.,+or-)

Fi-Destinationregister

Fj,Fk—Source-registernumbers

Qj,Qk—FunctionalunitsproducingsourceregistersFj,Fk

Rj,Rk—FlagsindicatingwhenFj,Fkareready

3.Registerresultstatus-Indicateswhichfunctionalunitwill

writeeachregister,ifoneexists.Blankwhennopending

instructionswillwritethatregister

北京大学计算机科学技术系计算机系统结构教研室

CDC6600的记分板*

■来自编译的加速比1.7；手编代码的加速比

2.5,但是由于存储速度慢（没有Cache）限制

了加速比的提高

■6600记分板的局限性：

•没有前递硬件

•指令调度局限于基本块内（指令窗口小）

•功能部件少（结构冒险），特别是integer/load

store部件

•存在结构冒险，就暂停发射指令

•等待到WAR冒险解决

•防止WAW冒险

:大学计算机科学技术系______________________________________________________________计算机系统结构教研室

记分板流水线控制的细节承N

Instruction

WaituntilBookkeeping

status

Busy(FU)-yes;Op(FU)«-op;

Fi(FU)—D;Fj(FU)<-'S1,;

Notbusy(FU)and

IssueFk(FU)—'S2'；Qj—ResultCSV);

notresult(D)

Qk-Result('S2));Rj.notQj;

Rk—notQk;Result('D')—FU;

Read

RjandRkRj—No;Rk—No

operands

ExecutionFunctionalunit

completedone

Vf((Fj(f)WFi(FU)

Vf(ifQj(f)=FUthenRj⑴.Yes);

orRj(f)=No)&

WriteresultVf(ifQk(f)=FUthenRj⑴—Yes);

(Fk(f)WFi(FU)or

Result(Fi(FU))—0;Busy(FU).No

Rk(f)=No))

学计算机科学技术系____________________________计算机系统结构教研室

另一个动态算法：Tomasulo算法

■为IBM360/91设计的、在CDC6600三年之后(1966)

■目标：即使在没有特殊编译支持的情况下，也能取

得高性能

■IBM360和CDC6600指令系统体系结构之间的差异

•IBM的每条指令有两个寄存器描述符(register

specifiers),而CDC6600有三个；

•IBM有四个浮点寄存器，而CDC6600有八个。

■为什么要学习Tomasulo算法？

•由此产生了Alpha21264、HP8000、MIPS10000、

PentiumII、PowerPC604,...

北京大学计算机科学技术系计算机系统结构教研室

Tomasulo算法与记分板

口控制&缓冲器分布于功能部件(FU)与集中于记分板；

•功能部件缓冲器称为“保留站(reservation

stations)”;存放未决的操作数

■指令中的寄存器被数值或者指向保留站的指针代替；

这一过程称为寄存器换名(registerrenaming);

•消除WAR、WAW冒险

・保留站比实际寄存器多，因而可以完成优化编译

器所不能完成的一些工作

结果从RS直接到FU,无需通过寄存器，而是通过公

共数据总线(CommonDataBus)把结果广播到所有FU

装入(Load)和存储(Stores)也象其他功能部件一

样使用保留站

北京大学计算机科学技术系___________________________________________________________计算机系统空想教空富一

Tomasulo的结构

FPOpQueue

From

Memory

Load

Buffer

■1

3Store

Operation2Buffer

CommonBus

Data一

32

Bus21

Mul

FPAddStation

Multers

Res.AddersStation

Station

CommonDataBus(CDB)

北京大学计算机科学技术系计算机系统结构教研室

Tomasulo算法的三段

1.Issue一从FPOpQueue中取出指令

如果保留站空闲（无结构冒险），

控制机制发射指令&发送操作数（对寄存器进行换名）。

2.Execution一对操作数执行操作（EX）

如果两个操作数都已就绪，就执行；

如果没有就绪，就观测公共数据总线等待所需结果

3.Writeresult一完成执行（WB）

通过公共数据总线将结果写入到所有等待的部件；

标记保留站可用

■正常的数据总线：数据+目的（“去向”总线）

■公共数据总线:数据+源（“来源”总线）

・64位数据+4位功能部件遮地址

•如果与期望的功能部件匹配，就“写”（产生结果）

•进行广播

北京大学计算机科学技术系计算机系统结构教研室

保留站的组成

Op—该部件将完成的具体操作(例如，+or-)

Vj,Vk—源操作数的实际数值

•存储缓冲器(Storebuffers)设有V域，存放将存储的结果

Qj,Qk—将产生源寄存器值(将写的值)的保留站

|注意:没有记分板中的就绪(READY)标志；Qj,Qk=Onready

•存储缓冲器(Storebuffers)中只有存放RS产生结果的Qi

Busy—指明保留站或FU处于忙状态

Registerresultstatus一指明哪个功能部件将写到哪

个寄存器(Qi)；如果没有将写入寄存器的未决指令，该

域为空

北京大学计算机科学技术系计算机系统结构教研室

Tomasulo示例第0周期

InstructionstatusExecutionWrite

Instruction/kIssuecompleteResultBusyAddress

LDF634+R2Load1No

LDF245+R3Load2No

MULF0F2F4Load3No

SUBF8F6F2

DIVCF10F0F6

ADDF6F8F2

ReservationStationsS1S2RSforjRSfork

TimeNameBus.OpVjVkQiQkLD:2cycles

0Add1No

0Add2NoADD:2cycles

0Add3NoMult:10cycles

0MultiNo

0Mult2NoDivd:40cycles

Registerresultstatus

ClockF0F2F4F6F8F10F12...F30

oFU

北京大学计算处科学技术系计算机系至结构教研室

Toiuiasulo示例第1周期

InstructionstatusecutionWrite

InstructiorjIssuec(^ipleteResultBusyAddr

LDF634+1d1Yes34+R

LDF245+R30L

MULF0F2F40Load3pMo

SUBF8F6F2

DIVCF10FOF6

ADDF6F8F2

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQjQk

0Add1No

0Add2No

Add3No

0MultiNo

0Mult2No

Registerresultstatus

ClockFOF2F48F10F12...F30

1FU\Loadl

北京大学计算机科学技术系计算机系统结构教研室

-Tom曾厢所第2周期

Instructorjk/§s烤completeResultBusyAddress

LDF634+R'

LDF245+24Load2Yes45+R3

MULFOF2F4

SUBF8F6F2

DIVCF1OF0F6

ADDF6F8F2

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQjQk

0Add1No

0Add2No

Add3No

0MultiNo

0Mult2No

Registerresultstatus、八/

Clock独修F6F8F10F12…F30

2FULoad2Loach

注意：与CDC660i神［仪陵有多个loads被发射；记分板能否改进？

北竟大学在算机科学技术系\77二音算权索线结构薮矫豪―

Tomasulo^W^3Ml期

InstructionstatusExecutionWrite

InstructiorjkIssuecompleteResultBusyAddress

LDF634+R2130LoadlYes34+R2

LDF245+R321Load2Yes45+R3

MULFOF2F430Load3No

SUBF8F6F2

DIVCF10FOF6

ADDF6F8F2

ReservationStationsS1S2FISforjFISfork

TimeNameBusOpVjVkQjQk

0Add1No

0Add2No

Add3No

0MultiYesMULTDR(F4)Load2

0Mult2No

Registerresultstatus

ClockFOF2F4F6F8F10F12…F30

3FU〔MultiLoad2Loadl

•注意：保留站中寄存器名被“换名”；MULT可发射（与记分板比较）

•北卜9邨1烷脂技吼曜指令在等待Loadl?计算机系统空想教空富

Tomasulo示例第4周期

InstructionstatusExecutionWrite

InstructiorjkIssuecompleteResultBusyAddress

LDF634+R21340LoadlNo

LDF245+R3240Load2Yes45+R3

MULFOF2F430Load3No_______

SUBF8F6F24

DIVCF10FOF6

ADDF6F8F2

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQjQk

0Add1YesSUBCM(34+R2)Load2

0Add2No

Add3No

0MultiYesMULTDR(F4)Load2

0Mult2No

Registerresultstatus

ClockFOF2F4F6F8F10F12...F30

4FU|MultiLoad2M(34+R2)Add1

•Load2将完成；哪些指令在等待Load2?

北京大学计算机科学技术系_____________________________________________计算机系统结构教研室_

Tomasulo示例第5周期

InstructionstatusExecutionWrite

InstructiorjkIssuecompleteResultBusyAddress

LDF634+R2134LoadlNo

LDF245+R3245Load2No

MULF0F2F43Load3No_______

SUBF8F6F24

DIVCF10F0F65

ADDF6F8F2

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQjQk

2Add1YesSUB匚M(34+R2)M(45+R3)

0Add2No

Add3No

10MultiYesMULTM(45+R3)R(F4)

0Mult2YesDIVDM(34+R2)Multi

Reciisterresultstatus

ClockF0F2F4F6F8F10F12…F30

5F(；|Mult1M(45+R3)M(34+R2)Add1Mult2

北京大学计算机科学技术系计算机系至结构教研室

Tomasulo示例第6周期

InstructionstatusExecutionWrite

InstructionjkIssuecompleteResultBusyAddress

LDF634+R2134Loadl

LDF245+R3245Load2

MULFOF2F43Load3

SUBF8F6F24

DIVCF10FOF65

ADDF6F8F26

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQjQk

1Add1YesSUBDM(34+R2)M(45+R3)

0Add2YesADDDM(45+R3)Add1

Add3No

9MultiYesMULTM(45+R3)R(F4)

0Mult2YesDIVDM(34+R2)Multi

Registerresultstatus

ClockFOF2F4F6F8F10F12...F30

6FU|MultiM(45+R3)Add2Add1Mult2-

•发射ADDD

北京大学计算机科学技术系_____________________________________________计算机系统结构教研室_

Tomasulo示例第7周期

Instructio。statusExecutionWrite

InstructionjkIssuecompleteResultBusyAddress

LDF634+R2134Loadlo

LDF245+R3245Load2

MULFOF2F43Load3

SUBF8F6F247

DIV匚F10FOF65

ADDF6F8F26

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQjQk

0Add1YesSUBCM(34+R2)M(45+R3)

0Add2YesADDDM(45+R3)Add1

Add3No

8MultiYesMULTM(45+R3)R(F4)

0Mult2YesDIVDM(34+R2)Multi

Reeisterresultstatus

ClockFOF2F4F6F8F10F12…F30

7FU|MultiM(45+R3)Add2Add1Mult2

i•Add1完成;哪些指令在等待Add1?

1北京大学计算处科学技术系__计算机系婪结构教研室

Tomasulo示例第8周期

InstructionstatusExecutionWrite

InstructiorjkIssuecompleteResultBusyAddress

LDF634+R2134Loadl

LDF245+R3245Load2

MULFOF2F43Load3IN。|

SUBF8F6F2478

DIVCF10FOF65

ADDF6F8F26

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQjQk

0Add1No

2Add2YesADDCM()-M()M(45+R3)

Add3No

7MultiYesMULTM(45+R3)R(F4)

0Mult2YesDIVDM(34+R2)Multi

Registerresultstatus

ClockFOF2F4F6F8F10F12...F30

8FO|MultiM(45+R3)Add2Mult2

北京大学计算处科学技术系_计算机系统结构教研室

Tomasulo示例第9周期

InstructiorjkIssuecompleteResultBus、Address

LDF634+R2134LoadlNo

LDF245+R3245Load2No

MULFOF2F43Load3No

SUBF8F6F2478

DIVCF10FOF65

ADDF6F8F26

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQjQk

0Add1No

1Add2YesADDCM(}-M()M(45+R3)

Add3No

6MultiYesMULTM(45+R3)R(F4)

0Mult2YesDIVDM(34+R2)Multi

Registerresultstatus

ClockFOF2F4F6F8F10F12…F30

9F(7|Mult1M(45+R3)Add2MQ-MQMult2

北京大学计算机科学技术系计算机系统结构教研室

Tomasulo示例第10周期

InstructionstatusExecutionWrite

InstructiorjkIssuecompleteResultBusyAddress

LDF634+R2134LoacHNo

LDF245+R3245Load2No

MULFOF2F43Load3No_______

SUBF8F6F2478

DIVEF10FOF65

ADDF6F8F2610

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQjQk

0Add1No

0Add2YesADDCM()-M()M(45+R3)

Add3No

5MultiYesMULTM(45+R3)R(F4)

0Mult2YesDIVDM(34+R2)Multi

Registerresultstatus

ClockFOF2F4F6F8F10F12…F30

10FU|MultiM(45+R3)Add2M()・M()Mult2

•Add2完成;哪些指令在等待Add2?

北京大学计算机抖学技术系二计算机基婪结构教研室

Tomasulo示例第H周期

InstructionstatusExecutionWrite

InstructorjkIssuecompleteResultBusyAddress

LDF634+R2134LoadlNo

LDF245+R3245Load2No

MULFOF2F43Load3No________

SUBF8F6F2478

DIVCF10FOF65

ADDF6F8F261011

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQjQk

0Add1No

0Add2No

Add3No

4MultiYesMULTM(45+R3)R(F4)

0Mult2YesDIVDM(34+R2)Multi

ClockFOF2F4F6F8F10F12...F30

11FU|MultiM(45+R3)(M-M)+M(；M()-M(Mult2

北京大学计〃PPP在该周期写结果计算如系统结构教研室

Tomasulo示例第12周期

InstructionstatusExecutionWrite

InstructiorjkIssuecompleteResultBusyAddress

LDF634+R2134LoadlINoI

LDF245+R3245Load2No

MULFOF2F43Load3No

SUBF8F6F2467

DIVCF10FOF65

ADDF6F8F261011

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQjQk

0Add1No

0Add2No

Add3No

3MultiYesMULTM(45+R3)R(F4)

0Mult2YesDIVDM(34+R2)Multi

Registerresultstatus

ClockFOF2F4F6F8FWF12…F30

12-“MultiM(45+R3)(M-M)+M()M()-M()Mult2

■注意：所有短周期指令都已经完成

北京大学计算机科学技术系_____________________________________________计算机系统结构教研室

Tomasulo示例第13周期

InstructionstatusExecutionWrite

InstructiorjkIssuecompleteFlesultBusvAddress

LDF634+R2134LoadlNo

LDF245+R3245Load2No

MULF0F2F43Load3No

SUBF8F6F2478

DIVCF10FOF65

ADDF6F8F261011

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQQk

0Add1No

0Add2No

Add3No

2MultiYesMULTM(45+R3)R(F4)

0Mult2YesDIVDM(34+R2)Muk

Registerresultstatus

ClockFOF2F4F6F8F10F12…F30

13F(j|Mult1M(45+R3)(M-M)+M()MQ-M()Mult2

北京大学计算机抖学技术系计算机系统结构教研室_

Tomasulo示例第14周期

InstructionstatusExecutionWrite

InstructiorjkIssuecompleteResultBusyAddress

LDF634+R2134LoadlNo

LDF245+R3245Load2No

MULFOF2F43Load3No_______

SUBF8F6F2478

DIVCF10FOF65

ADDF6F8F261011

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQjQk

0Add1No

0Add2No

Add3No

1MultiYesMULTM(45+R3)R(F4)

0Mult2YesDIVDM(34+R2)Multi

Registerresultstatus

ClockFOF2F4F6F8F10F12…F30

14FU|MultiM(45+R3)(M-M)+M()M()-M(Mult2-

北京大学计算机科学技术系计算机系统结构教研室

Tomasulo示例第15周期

InstructionstatusExecutionWrite

InstructionjkIssuecompleteResultBusyAddress

LDF634+R2134LoadlNo

LDF245+R3245Load2No

MULFOF2F4315Load3No

SUBF8F6F2478

DIVCF10FOF65

ADDF6F8F261011

ReservationStationsS1S2RSforjRSfork

TimeNameBus.OpVjVkQjQk

0Add1No

0Add2No

Add3No

0MultiYesMULTM(45+R3)R(F4)

0Mult2YesDIVDM(34+R2)Multi

Reqisterresultstatus

ClockFOF2F4F6F8F10F12...F30

15FU|Mul5M(45+R3)(M-M)+MCM()-M()Mult2一

•Multicompleting;whatiswaitingforit?

北京大学计算机科学技术系计算机系统声构教研室

Tomasulo示例第16周期

InstructionstatusExecutionWrite

InstructionjkIssuecompleteResultBusyAddress

LDF634+R2134LoadlNo

LDF245+R3245Load2No

MULFOF2F431516Load3No

SUBF8F6F2478

DIVCF10F0F65

ADDF6F8F261011

ReservationStationsS1S2RSforjRSfork

TimeNameBusOpVjVkQjQk

0Add1No

0Add2No

Add3No

0MultiNo

40Mult2YesDIVDM*F4M(34+R2)

Registerresultstatus

ClockF0F2F4F6F8F10F12…F30

16FU|M*F4M(45+R3)(M-M)+M()M()-M()Mult2

北京大学计算机科学技术系•注意：只有修法指令没有完成计算机系统结构教研室

Tomasulo示例第55周期

InstructionstatusExecutionWrite

InstructionjkIssuecompleteResultBusyAddress

LDF634+R2134Loadl

LDF245+R3245Load2

MULFOF2F431516Load3

SUBF8F6F2478o

DIVCF10FOF65

ADDF6F8F261011

ReservationStationsS1S2RSforjRSfork

TimeNameBus.OpVjVkQjQk

0Add1No

0Add2No

Add3No

0MultiNo

1Mult2YesDIVDM*F4M(34+R2)

Registerresultstatus

ClockFOF2F4F6F8F10F12...F30

55FU|MT4M(45+R3)(M-M)+M(；MQ-MQMult2

北京大学计算机科学技术系计算机系统结构教研室

Tomasulo示例第56周期

InstructionstatusExecutionWrite

InstructionjkIssuecompleteResultBusyAddress

LDF634+R2134LoadlNo

LDF245+R3245Load2No

MULFOF2F431516Load3No

SUBF8F6F2478

DIVCF10FOF6556

ADDF6F8F261011

ReservationStations