Tomasulo算法

1/137▲5.3指令的动态调度1.核心思想记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小(允许乱序)；通过寄存器换名来消除WAR冲突和WAW冲突。5.3.3Tomasulo算法5.3.3.1基本思想2/137▲5.3指令的动态调度2.IBM360/91首先采用了Tomasulo算法IBM360/91的设计目标是基于整个360系列的统一指令系统和编译器来实现高性能，而不是设计和利用专用的编译器来提高性能。需要更多地依赖于硬件。IBM360体系结构只有4个双精度浮点寄存器，限制了编译器调度的有效性。360/91的访存时间和浮点计算时间都很长。（也是Tomasulo算法要解决的问题）5.3.3Tomasulo算法5.3.3.1基本思想3/137▲反相关（F8）导致WAR冲突输出相关（F6）导致WAW冲突3.寄存器换名可以消除WAR冲突和WAW冲突。考虑以下代码：DIV.DF0，F2，F4ADD.DF6，F0，F8S.DF6，0（R1）SUB.DF8，F10，F14MUL.DF6，F10，F85.3指令的动态调度4/137▲消除名相关引入两个临时寄存器S和T把这段代码改写为：DIV.DF0，F2，F4ADD.DS，F0，F8S.DS，0（R1）SUB.DT，F10，F14MUL.DF6，F10，T5.3指令的动态调度两个F6都换名为S两个F8都换名为T5/137▲DIV.DF0，F2，F4ADD.DF6，F0，F8S.DF6，0（R1）SUB.DF8，F10，F14MUL.DF6，F10，F8DIV.DF0，F2，F4ADD.DS，F0，F8S.DS，0（R1）SUB.DT，F10，F14MUL.DF6，F10，T6/137▲5.3指令的动态调度从指令部件来浮点寄存器FPstore缓冲器load缓冲器地址部件load/store操作浮点操作操作数总线操作总线数据11存储部件浮点加法器浮点乘法器指令队列地址2323456公共数据总线（CDB）12保留站标识标识4.基于Tomasulo算法的MIPS处理器浮点部件的基本结构7/137▲5.3指令的动态调度保留站（reservationstation）每个保留站中保存一条已经流出并等待到本功能部件执行的指令（相关信息）。包括：操作码、操作数以及用于检测和解决冲突的信息。在一条指令流出到保留站的时候，如果该指令的源操作数已经在寄存器中就绪，则将之取到该保留站中。如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识。浮点加法器有3个保留站：ADD1，ADD2，ADD3浮点乘法器有两个保留站：MULT1，MULT2每个保留站都有一个标识字段，唯一地标识了该保留站。8/137▲5.3指令的动态调度从指令部件来浮点寄存器FPstore缓冲器load缓冲器地址部件load/store操作浮点操作操作数总线操作总线数据11存储部件浮点加法器浮点乘法器指令队列地址2323456公共数据总线（CDB）12保留站标识标识9/137▲5.3指令的动态调度公共数据总线CDB（一条重要的数据通路）所有功能部件的计算结果都是送到CDB上，由它把这些结果直接送到（播送到）各个需要该结果的地方。在具有多个执行部件且采用多流出（即每个时钟周期流出多条指令）的流水线中，需要采用多条CDB。10/137▲5.3指令的动态调度从指令部件来浮点寄存器FPstore缓冲器load缓冲器地址部件load/store操作浮点操作操作数总线操作总线数据11存储部件浮点加法器浮点乘法器指令队列地址2323456公共数据总线（CDB）12保留站标识标识11/137▲5.3指令的动态调度load缓冲器和store缓冲器存放读/写存储器的数据或地址load缓冲器的作用有3个：存放用于计算有效地址的分量；记录正在进行的load访存，等待存储器的响应；保存已经完成了的load的结果（即从存储器取来的数据），等待CDB传输。store缓冲器的作用有3个：存放用于计算有效地址的分量；保存正在进行的store访存的目标地址，该store正在等待存储数据的到达；保存该store的地址和数据，直到存储部件接收。12/137▲5.3指令的动态调度从指令部件来浮点寄存器FPstore缓冲器load缓冲器地址部件load/store操作浮点操作操作数总线操作总线数据11存储部件浮点加法器浮点乘法器指令队列地址2323456公共数据总线（CDB）12保留站标识标识13/137▲5.3指令的动态调度浮点寄存器FP共有16个浮点寄存器：F0，F2，F4，…，F30。它们通过一对总线连接到功能部件，并通过CDB连接到store缓冲器。指令队列指令部件送来的指令放入指令队列指令队列中的指令按先进先出的顺序流出运算部件浮点加法器完成加法和减法操作浮点乘法器完成乘法和除法操作14/137▲5.3指令的动态调度从指令部件来浮点寄存器FPstore缓冲器load缓冲器地址部件load/store操作浮点操作操作数总线操作总线数据11存储部件浮点加法器浮点乘法器指令队列地址2323456公共数据总线（CDB）12保留站标识标识15/137▲5.3指令的动态调度5.在Tomasulo算法中，寄存器换名是通过保留站和流出逻辑来共同完成的。当指令流出时，如果其操作数还没有计算出来，则将该指令中相应的寄存器号换名为将产生这个操作数的保留站的标识。指令流出到保留站后，其操作数寄存器号或者换成了数据本身（如果该数据已经就绪），或者换成了保留站的标识，不再与寄存器有关系。16/137▲5.3指令的动态调度6.通过一个简单的例子来说明Tomasulo算法的基本思想从指令部件来浮点乘法器M指令队列公共数据总线（CDB）保留站ADD3ADDF2,F0,F6ADD2ADD1MULT2MULT1保留站浮点寄存器F6F4F2F0Qi浮点加法器AMULF0,F2,F4abc…寄存器状态表Qi表明哪个保留站将产生该寄存器的值117/137▲5.3指令的动态调度从指令部件来浮点乘法器M指令队列公共数据总线（CDB）保留站ADD3ADDF2,F0,F6ADD2ADD1MULT2MULT1保留站浮点寄存器F6F4F2F0Qi浮点加法器AabcMULabMULT1…218/137▲5.3指令的动态调度从指令部件来浮点乘法器M指令队列公共数据总线（CDB）保留站ADD3ADD2ADD1MULT2MULT1保留站浮点寄存器F6F4F2F0Qi浮点加法器AabcMULabMULT1ADD1ADDcMULT1319/137▲5.3指令的动态调度从指令部件来浮点乘法器M指令队列公共数据总线（CDB）保留站ADD3ADD2ADD1MULT2MULT1保留站浮点寄存器F6F4F2F0Qi浮点加法器AabceADD1ADDce420/137▲5.3指令的动态调度7.Tomasulo算法具有以下两个特点：冲突检测和指令执行控制是分布的。每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。8.指令执行的步骤使用Tomasulo算法的流水线需3段：流出：从指令队列的头部取一条指令。如果该指令的操作所要求的保留站有空闲的，就把该指令送到该保留站（设为r）。21/137▲5.3指令的动态调度如果其操作数在寄存器中已经就绪，就将这些操作数送入保留站r。如果其操作数还没有就绪，就把将产生该操作数的保留站的标识送入保留站r。一旦被记录的保留站完成计算，它将直接把数据送给保留站r。（寄存器换名和对操作数进行缓冲，消除WAR冲突）完成对目标寄存器的预约工作（消除了WAW冲突）如果没有空闲的保留站，指令就不能流出。（发生了结构冲突）22/137▲5.3指令的动态调度执行当两个操作数都就绪后，本保留站就用相应的功能部件开始执行指令规定的操作。load和store指令的执行需要两个步骤：计算有效地址（要等到基地址寄存器就绪）把有效地址放入load或store缓冲器写结果功能部件计算完毕后，就将计算结果放到CDB上，所有等待该计算结果的寄存器和保留站（包括store缓冲器）都同时从CDB上获得所需要的数据。23/137▲5.3指令的动态调度9.每个保留站有以下7个字段：Op：要对源操作数进行的操作Qj，Qk：将产生源操作数的保留站号等于0表示操作数已经就绪且在Vj或Vk中，或者不需要操作数。Vj，Vk：源操作数的值对于每一个操作数来说，V或Q字段只有一个有效。对于load来说，Vk字段用于保存偏移量。Busy：为“yes”表示本保留站或缓冲单元“忙”A：仅load和store缓冲器有该字段。开始是存放指令中的立即数字段，地址计算后存放有效地址。24/137▲5.3指令的动态调度Qi：寄存器状态表每个寄存器在该表中有对应的一项，用于存放将把结果写入该寄存器的保留站的站号。为0表示当前没有正在执行的指令要写入该寄存器，也即该寄存器中的内容就绪。5.3.3.2举例25/137▲5.3指令的动态调度例5.2对于下述指令序列，给出当第一条指令完成并写入结果时，Tomasulo算法所用的各信息表中的内容。L.DF6,34（R2）L.DF2,45（R3）MUL.DF0,F2,F4SUB.DF8,F2,F6DIV.DF10,F0,F6ADD.DF6,F8,F226/137▲5.3指令的动态调度当采用Tomasulo算法时，在上述给定的时刻，保留站、load缓冲器以及寄存器状态表中的内容。指令指令状态表流出执行写结果L.DF6,34(R2)√√√L.DF2,45(R3)√√MUL.DF0,F2,F4√SUB.DF8,F6,F2√DIV.DF10,F0,F6√ADD.DF6,F8,F2√名称保留站Load1Load2Add1Add2Add3Mult1Mult2BusynoyesyesyesnoyesyesOpLDSUBADDMULDIVVjVkMem[34+Regs[R2]]Reg[F4]Mem[34+Regs[R2]]QjLoad2Add1Load2Mult1QkLoad2A45+Regs[R3]L.DF6,34（R2）L.DF2,45（R3）MUL.DF0,F2,F4SUB.DF8,F2,F6DIV.DF10,F0,F6ADD.DF6,F8,F228/137▲寄存器状态表F0F2F4F6F8F10…F30QiMult1Load2Add2Add1Mult2…L.DF6,34（R2）L.DF2,45（R3）MUL.DF0,F2,F4SUB.DF8,F2,F6DIV.DF10,F0,F6ADD.DF6,F8,F229/137▲5.3指令的动态调度Tomasulo算法具有两个主要的优点：冲突检测逻辑是分布的（通过保留站和CDB实现）如果有多条指令已经获得了一个操作数，并同时在等待同一运算结果，那么这个结果一产生，就可以通过CDB同时播送给所有这些指令，使它们可以同时执行。消除了WAW冲突和WAR冲突导致的停顿使用保留站进行寄存器换名，并且在操作数一旦就绪就将之放入保留站。30/137▲5.3指令的动态调度例5.3对于例5.2中的代码，假设各种操作的延迟为：load：1个时钟周期加法：2个时钟周期乘法：10个时钟周期除法：40个时钟周期给出MUL.D指令准备写结果时各状态表的内容。解MUL.D指令准备写结果时各状态表的内容如下图所示。L.DF6,34（R2）L.DF2,45（R3）MUL.DF0,F2,F4SUB.DF8,F2,F6DIV.DF10,F0,F6ADD.DF6,F8,F231/137▲5.3指令的动态调度指令指令状态表流出执行写结果L.DF6,34(R2)√√√L.DF2,45(R3)√√√MUL.DF0,F2,F4√√SUB.DF8,F6,F2√√√DIV.DF1