计算机体系结构----寄存器重命名/Tomasulo算法

发布时间：2024年01月10日

前情提要

计分板算法可看我写的博文计算机体系结构----计分板（scoreboard）算法

Tomasulo算法的核心是寄存器重命名（register renaming）；通过寄存器重命名，可彻底消除WAR/WAW冲突，计分板算法中，WAR/WAW都是通过停顿解决的，当然计分板算法虽然没那么厉害但还是通过动态调度消除了RAW冲突的。

Tomasulo算法如何实现乱序执行

  1. 需要在值的生产者和消费者之间建立通信，这里消费者指的是当前这条指令，生产者指的是在与这条指令相关的指令。
  • 寄存器重命名：给每个值一个tag
  1. 需要给指令提供缓冲区，这个缓冲区称为保留站
  2. 指令需要持续监测值是否可用，当这个值准备好了，就广播自己的tag，消费者匹配tag，如
    果是自己用的，就知道这个值已经准备好了
  3. 当全部的值都准备好，需要分发指令到对应的功能单元上去，即当需要的全部值都准备好，分发指令，出保留站

Tomasulo算法的核心要素

  1. 保留站 Reservation stations (scheduling window)，缓存指令以及指令的操作数
  2. 公共数据总线 Common data bus (CDB)，广播结果给保留站（RS）
  3. 寄存器重命名：消除WAR/WAW相关
  4. 转发/前递：Forwarding，消除RAW相关（注：我们看下面的例子会发现在RAW相关的前一条指令处于write result阶段时，后一条指令就可以进入EXE阶段了）

典型的Tomasulo系统：IBM 360/91

在这里插入图片描述

Tomasulo算法的各个功能区

保留站（发射队列）

  1. 指令顺序发射到保留站
  • 缓存指令及操作数
  • 如果操作数未就绪，保留站监听数据总线
  • 如果操作数已就绪，缓存到保留站
  1. 每个功能部件有独立的保留站（计分板算法里面所有的功能部件共用一个计分板），如果保留站已全部占用，无法发射指令，只能等。

保留站示意图如下。
在这里插入图片描述

保留站结构

  1. Busy字段：表明对应功能部件的保留站已被占用
  2. Op字段：表明具体的操作，如ADD
  3. Vj、Vk字段：保留源操作数的值
  4. Qj、Qk字段
  • Qj：产生源操作数Vj的保留站编号，或者0
  • Qk：产生源操作数Vk的保留站编号，或者0
  • 0表示源操作数已在Vj或Vk
  1. A字段：为load与store指令存放存储器地址计算信息

上述字段的含义和计分板很相似。

重命名映射表Register Alias Table (RAT)

如果设置了“有效位”，则表中的“值”正确。 否则，Tag 指定在何处查找正确的值。 Tag 是要生成的 Value 的唯一名称、
在这里插入图片描述

公共数据总线

Common Data Bus (CDB)：广播已完成 insns 的<RS#, value> 。

Tomasulo算法 – 处理WAR

在这里插入图片描述

Tomasulo算法 – 处理WAW

在这里插入图片描述

Tomasulo算法 – 基本结构

在这里插入图片描述

  1. 每个功能部件有自己的保留站,Load/store buffers和保留站结构基本相同
  2. 保留站中的每一行保存着一条发射到相应功能部件的指令，并缓存了已就绪的操作数，和未就绪操作数的标签（即生 产指令所在的保留站行号）
  3. CDB不仅把结果送到寄存器中，也送到所有正在等待该结果的保留站中
  • 每个结果会附带一个标签（即生产指令所在的保留站行号），用来和保留站中的标签相匹配
  • CDB相当于实现了前送功能

Tomasulo算法 – 三个阶段

每条指令的执行经历三个阶段
在这里插入图片描述

Tomasulo算法 – 算法流程

  1. 如果在重命名之前保留站可用
  • 指令 + 重命名的操作数（源值/标签）插入到保留站中
  • 仅当保留站可用时重命名
  1. 否则停顿
  2. 在保留站时，每条指令：
  • 监视公共数据总线 （CDB） 的源标签
  • 当看到标签时，获取源的值并将其保存在保留站中
  • 当两个操作数都可用时， 指令准备分派
  1. 指令准备就绪时向功能单元发送指令
  2. 指令在功能单元中完成后
  • CDB 仲裁
  • 将标记值放入 CDB 上（标记广播）
  • 寄存器文件已连接到 CDB
    – 寄存器包含一个标签，指示寄存器的最新写入者
    – 如果寄存器文件中的标签与广播标签匹配， 将广播值写入寄存器（并设置有效位）
  • 回收重命名标签
    – 系统中没有标签的有效副本

Tomasulo算法示例

初始化

在这里插入图片描述
注意下面的示例中，W和E阶段是同时发生的，因为Tomasulo算法采用了forwarding技术，其他细节不用过多说明，图中均 详细介绍了，自己推导一边这个过程即可熟练掌握。。

Cycle1

在这里插入图片描述

Cycle2

在这里插入图片描述

Cycle3

在这里插入图片描述

Cycle4

在这里插入图片描述

Cycle5

在这里插入图片描述

Cycle6

在这里插入图片描述

Cycle7

在这里插入图片描述
虽然cycle7中R5被二次标记，但是R5第一次重命名的值仍存在保留站项a中，是要比保留站项d先计算出来并广播的。

Cycle8

在这里插入图片描述

Cycle8

在这里插入图片描述

Cycle8

在这里插入图片描述

Cycle 9

在这里插入图片描述

Cycle 10

在这里插入图片描述

Cycle 11

在这里插入图片描述

Cycle 12

在这里插入图片描述

Cycle 13

在这里插入图片描述

Cycle 14

在这里插入图片描述

Cycle 15

在这里插入图片描述

Cycle 16

在这里插入图片描述

Cycle 17

在这里插入图片描述

Cycle 18

在这里插入图片描述

Cycle 19

在这里插入图片描述

Cycle 20

在这里插入图片描述

Tomasulo算法性能分析

  1. Tomasulo算法完善的处理了数据冲突，与分支预测和猜测执行配合起来后能达到很高的性能，当今处理器仍在广泛采用
  2. 仍没有处理控制冲突，乱序执行仍局限在一个基本块内
  3. 要求高速CDB: 性能受限于Common Data Bus
文章来源:https://blog.csdn.net/Programmer_jzm/article/details/135500350
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章