homework6

Tomasulo是一种计算机硬件架构的算法，用于动态调度指令的指令，允许乱序执行以及更有效率的使用多个执行单元。它由IBM公司在1967年提出，首次应用是在IBM system 360上。第一节花那么大功夫讲解数据冒险和寄存器重命名，是因为Tomasulo最大的特点就是通过借助重命名的思想消除了假数据冒险，从而提高了机器的乱序性能。 首先是FP OP Queue，这里是浮点指令队列，指令在这里等待发射； 青绿色模块是加法单元和乘法单元的保留站（保留站是什么？保留站保留已经发射的指令的信息和缓冲下来的数据。关于保留站，后文会有更多介绍）； 蓝绿色的Address Unit是地址计算单元，在这个算法中存储指令在执行前会先计算好存储地址； Memory Unit则是存储单元； CDB是数据广播总线（在记分牌一文提到过），它可以直达寄存器堆（用来更新通用寄存器）、加法乘法存储单元的保留站（输送保留站中指令需要的数据）。 要解读Tomasulo算法，就要搞清楚这个算法运用了哪些信息来调度指令，然后要分清楚算法的调度步骤。接下来首先解释Tomasulo算法利用了哪些信息，然后讲解算法的调度步骤。

1、保留站和寄存器结果状态表 保留站是Tomasulo算法提出的新结构，有点类似记分牌中每一个配置通路前面的译码信息流水段寄存器，但是记分牌中每一条配置通路只能存放一条指令，而Tomasulo算法则为每一条通路配置了一组缓冲，就像图4中的绿色模块，其中浮点加法单元拥有能够缓冲三条指令的保留站。保留站存储的信息和记分牌有点类似。保留站的结构有点像cache，可能有多行数据，每一行都对应一条被发射到保留站的指令。保留站每一行都有Busy位，指示这一行是否现存有指令；Vj和Vk与记分牌不同，记分牌的Vj和Vk会记录源寄存器的编号，而保留站则直接把能读取的数据直接拷贝到保留站中，可想而知，一旦数据进入保留站，那对应的寄存器就和这条指令没瓜葛了；Qj和Qk的信息和记分牌一样，记录尚不能读取的数据将由哪条指令算出；A是存储指令的地址，用于存放立即数和计算得到的地址数据。

看上去保留站和记分牌非常相似，但是两者其实有很大的不同。以图5的Add为例，保留站中有三行Add信息，这三行数据对应的是同一个加法单元，而在记分牌中这代表着三个加法单元。记分牌那样的一条通路只对应一条信息的做法容易造成指令堵塞、无法发射，而保留站则为每条通路预留了缓冲区，指令可以在加法单元忙碌的时候发射到保留站的缓冲区待命。

其次，保留站会直接把读取的数据缓冲下来，而不像记分牌一样只记录一个寄存器编号，只记录编号的话会造成读后写阻塞，因为一条指令在正式执行前一直在监控着它的源寄存器，源寄存器的值是不能改变的，因此后续指令无法写回，只能阻塞流水，而保留站则贯彻了“数据一旦准备完毕，就立马执行指令”的思想，指令一旦发现有数据可读，就立马读下来，读下来之后，那个源寄存器的写与不写就不关己事了。

记分牌和保留站相同的地方是都记录了Qj和Qk，即一旦需要的数据被算出来，就通过Qj和Qk捕捉广播数据，这样的做法其实就是重命名，即用保留站的编号而不是寄存器编号来标记数据源。

除了保留站数据结构之外，Tomasulo同样要记录寄存器结果状态，记录信息如图6.和记分牌一样，Tomasulo也会记录寄存器将被哪条指令更新，这个信息在指令寻找源数据时被使用。

2、调度流程 为方便，把图4的架构图粘贴到这里。Tomasulo算法的调度分为三个步骤：发射、执行、写回。相比记分牌少了读数这个环节，因为在Tomasulo中指令在发射时就会读数。 Tomasulo架构 发射：Tomasulo算法是顺序发射的，即指令按照程序中的顺序一条接一条被发射到保留站。判断能否发射的唯一标准是指令对应通路的保留站是否有空余位置，只要保留站有空余，就可以把指令发射到保留站中。周期结束时会更新保留站和寄存器结果状态表，如果指令有可以读取的数据，就会立刻拷贝到保留站中；寄存器结果状态表中总是存有最新的值，即如果后序指令的目的寄存器和前序指令的目的寄存器重合，那就只保留后序指令的写信息。 执行：指令通过拷贝数据和监听CDB获得源数据，然后开始执行，执行可能是多周期的，在执行过程中不改变处理器状态。 写回：指令在写回阶段通过CDB总线将数据直通到寄存器堆和各个保留站；周期结束时，根据寄存器结果状态表来更新寄存器堆，并且清除保留站和寄存器结果状态表的信息。