跳转至

第5课

约 1628 个字 29 张图片 预计阅读时间 5 分钟

Dynamic Scheduling

1. 模型概述

  • Method: out of order execution(乱序执行)
  • 如下是比较早的模型:image-20230315131054190
    • scoreboard用来记录一些指令的状态信息和控制信号,比如功能部件的busy与否、指令所在的状态、寄存器(什么寄存器要被写,什么寄存器要被读入);
    • register寄存器存放变量;
    • 右边的是一些部件,两个乘法一个除法一个加法(这些都是浮点数的)和一个整数部件(load和store指令都要通过整数部件);

2. 整体实现

  • 把ID段的功能再进行细分,去检查结构冲突和数据冲突;
  • 即把ID段分成两个段:
    • IS(Issue):解码指令,检查是否有结构(运算部件)冲突;(in-order issue)
    • RO(Read Operands):(检查数据冲突)等待直到没有数据冲突,然后读操作数 (out of order execution),相当于之前的ID;
      • 乱序在RO段就已经发生了,如果后面的指令和前面的指令元操作数没有冲突,而且没有结构冲突,那就直接先执行了;
  • 对于顺序执行来说,WAR和WAW不会有任何问题,但是一旦有乱序,那么结果就会出现问题;image-20230315132715720

3. Scoreboard Algorithm

3.1 概况

  • 这是一种调度指令的算法;
  • 把一个指令执行过程分成四个阶段:

    • IS:检测是否有结构冲突,如果没有,则IS段完成;
    • RO:检测操作数(相当于原来流水线的ID),如果乱序从RO开始就是乱的;
  • 加法周期短,所以一个就够了,而乘法比较慢,而且相对除法出现的概率较高;image-20230315133314584

3.2 Example

image-20230315134547438

3.2.1 第一阶段
  • 指令状态表image-20230315133632899
    • 前面两个都可以执行没有问题;
    • 第三到第五条因为数据有依赖,所以在RO卡住了;
    • 而第六条,因为ADD部件被SUB占了,结构有冲突,所以在IS就卡住了;
  • 寄存器状态表(存放结果寄存器的状态)image-20230315134435620

  • 功能部件状态表image-20230315134342616

    • 目前有四条指令在执行,所以有四个部件是处于忙碌状态;
    • Op记录当前的操作;
    • F代表源操作数和目的操作数(Fi是目的操作数,其实就是对应着寄存器状态表);
    • Q表示从哪个功能部件来,比如第二行Mult1,F2就从Integer里来,可以表示等待的关系;
    • R表示源操作数在哪,yes表示要等另一个源操作数ready;image-20230315135921665
3.2.2 第二阶段
  • 指令状态表(假设乘法需要很多拍,还没有写结果)image-20230315140713092
    • FUML卡住了FDIV,而FDIV没有读F6,导致FADD无法写回F6;
  • 寄存器状态image-20230315140739896
  • 功能部件状态image-20230315140803562
3.2.3 第三阶段
  • 指令状态表(假设除法还没有写结果)image-20230315144213777
  • 寄存器状态、功能部件状态image-20230315144303556

4. Tomasulo

4.1 作用

  • 解决问题image-20230315144743687
    • 反相关;
    • 输出相关;

4.2 基本结构

对于load和store指令有六个buffer,对于mult指令有两个,对于add指令有三个,运算完后的数据线连到所有部件,给所有需要运用到这个数据的地方分别送过去;

保留栈就是实现乱序的主要结构,什么时候所有源操作数都ready了,先ready先计算,那么就可以从保留栈里面出来进入到运算部件中进行运算;

检测结构冲突就相当于变成了检测保留栈是否有空位,只要进了保留栈,就相当于过了结构冲突的检测,相当于功能部件扩容了,以前只有一条,现在是可以同时拥有保留栈大小的指令(虽然还是只能有一条指令执行);

重命名也是在保留栈完成的,只要之前没有真实的数据依赖,那么进入了保留栈就相当于重命名。

image-20230315145110353

4.3 主要思想

  • 它跟踪指令操作数何时可用,以减少RAW危害;

  • 它在硬件中引入了寄存器重命名,以最小化WAW和WAR的危害;

4.4 过程

把一条指令的执行过程分成三步:

  • Issue(可以重命名寄存器,消除WAR和WAW的影响)
    • 从指令队列拿出指令(FIFO);
    • 如果保留栈有空位,那么将指令放进去;
    • 如果没空位,则结构冲突,等待知道有空位;
    • 如果操作数不在寄存器里,就要追踪那些会产生这些操作数的功能部件;
  • Execute
    • 当所有的操作数都有了,就可以在对应的功能部件进行执行了;
    • PS:load和store需要两个步骤
      • 首先判断base register是否就绪,并计算地址;
      • 把计算后的有效地址放到loadstore的buffer里;
  • Write results
    • 当结果计算出来后,就通过CDB总线传输到所有需要这个结果的保留栈(包括store buffer)和寄存器中;
    • store指令在store buffer中等待,直到要存储的值和存储地址都可用,然后在内存单元可用时立即写入结果

4.5 Example

  • image-20230315152933134

  • 分析:MUL指令的F2和ADD的F2没有关系,F0有关系;

  • MUL进入保留栈,结果是MULT1(通过结果寄存器识别)image-20230315153248389

  • ADD的MULT1直接从运算部件里来,而不是从F0里来image-20230315153514629

  • 当MUL的WB写完了之后,F0和ADD里同步变成了e;image-20230315153653667

  • 现代计算机中会增加多条CDB来改善性能;

4.6 三张表记录信息

  • 指令状态表

  • 保留栈状态表(对应于scoreboard中的功能部件表)

    • Op:当前的操作;
    • Qj, Qk:表示从哪个功能部件来;
    • Vj, Vk:源操作数的value;
    • Busy:保留栈位置是否被占用;
    • A:对于load和store,记录memory的地址;
  • 结果寄存器状态表(Field Qi)

4.6‘ 一个例子
  • 假设第一条指令已经执行完,第二条指令还没写回;

    • 指令状态表:image-20230315154847089三四六要等F2,五要等F0;
    • 保留栈状态表:image-20230315155132893
    • 寄存器状态表:image-20230315155141338
  • 假设第二条指令load已经执行完了,乘法指令还没有写结果,除法要等F0;

    • 指令状态表:image-20230315160109337
    • 保留栈状态表:image-20230315160137244
    • 寄存器状态表:image-20230315160149353

5. 总结

  • Tomasula算法优点:

    • Dynamic scheduling;
    • Register renaming---eliminatining WAW and WAR hazards;
    • Load/store disambiguation;
    • Better than Scoreboard Algorithm;
  • 缺点:

    • 结构比较复杂;
    • Its performance is limited by Common Data Bus;
    • image-20230315160917149
  • ILP方法的局限性直接导致了多核技术的发展;

6. Homework

  • image-20230315161207027

  • image-20230316082813100

  • image-20230316082956153

本文总阅读量