国防科大计算机体系结构公开课_03流水线 🗯

国防科大计算机体系结构公开课学习笔记。

第三章:流水线技术。这节课讲得不错耶!~( •̀ ω •́ )~

这一节持续性懵逼脸,好难QAQ

划重点 🗒

一定要将指令执行中五个过程分别发生了什么烂熟于心!!!!!

流水线基本概念

流水过程由多个相关的子过程组成,这些子过程称为流水线的“级”或“段”。段的数目称为流水线的 “深度”。每个子过程由专用的功能段实现。各功能段的时间应基本相等,流水线需经过一定的 通过时间方可稳定。

分类

  • 单功能流水线和多功能流水线
    • 多功能流水线:各段可进行不同的连接,从而完成不同的功能。i.e. TIASC 多功能流水线

  • 静态流水线和动态流水线:按同一时间内流水段的连接方式划分
    • 静态流水线:同一时间内,流水线的各段只能按同一种功能的连接方式工作,适合于处理一串相同的运算操作(A B 功能分隔);
    • 动态流水线:同一时间内,当某些段正在实现某种运算时,另一些段在实现另一种运算(A B 功能重叠实现)。
  • 部件级、处理机级及处理机间流水线
    • 部件级流水线,又叫运算操作流水线,是把处理机的运算逻辑部件分段,使得各种数据类型的操作能够流水;
    • 处理机级流水线,又叫指令流水线,是把 解释指令的过程按照流水方式处理;
    • 处理机间流水线,又叫宏流水线,是由两个以上的处理机串行地对同一数据流进行处理,每个处理机完成一项任务。
  • 标量流水处理机和向量流水处理机:按照数据表示来进行分类
  • 线性流水线和非线性流水线:按照是否有反馈回路进行分类
    • 非线性流水线有反馈回路,故而存在流水线调度问题————确定什么时候向流水线引进新的输入,从而使新输入的数据和先前操作的反馈数据在流水线中不产生冲突(资源冲突、时间冲突),此即流水线调度问题。

MIPS 基本流水线

MIPS 指令执行过程

  1. 取指令周期(IF)
  • IR <– Mem[ PC ]
  • NPC <– PC + 4(遇到跳转之类的,NPC 可能还会改变)
  1. 指令译码/读寄存器周期(ID)
  • 进行指令译码,读 IR 寄存器(指令寄存器),按照相应寄存器号读寄存器文件,并将读出结果放入两个临时寄存器 A 和 B 中。同时对 IR 寄存器中内容的低 16 位进行符号扩展,然后将符号扩展之后的 32 位立即值保存在临时寄存器 Imm 中。
  • $A <– Regs[IR_{6..10}]$
  • $B <– Regs[IR_{11..15}]$
  • $Imm <–$ $((IR_{16})^{16}$ ## $IR_{16..31})$
  1. 执行/有效地址计算周期(EX)
  • 不同指令类型,计算操作不同
    • 存储器访问型:ALUoutput <– A + Imm(立即值存放在 Imm 中)
    • 寄存器-寄存器型 ALU:ALUoutput <– A op B
    • 寄存器-立即值型 ALU:ALUoutput <– A op Imm
    • 分支操作:ALUoutput <– NPC + Imm, Cond <– (A op 0)//形成新的跳转地址后,进行判断(将 A 寄存器中的值与 0 进行比较,看是否符合条件)
  • 为什么执行和有效地址计算可以合并?
    • MIPS 每条指令要么执行,要么进行访存操作,要么做条件判断,这几个不会同时执行,因此可以合并在同一周期内。
  1. 访存/分支操作完成周期(MEM)
  • 分支操作:if(Cond) PC <– ALUoutput; else PC <– NPC
  1. 写回(WB)

但是这五个阶段的时间消耗是不同的。由此带来一些问题:

  • 要保证流水线中,各段不会同时使用相同的寄存器资源。如何避免访存冲突?
    • 存储器资源隔离
  • PC 计算问题。为了能在每个时钟周期启动一条新的指令,流水线必须在 IF 段获得下一条指令的地址,并将其保存在 PC 中;但是,分支指令会改变 PC 的值,并只有在 Mem 段结束时,新值才会被写入 PC,出现矛盾。
    • 改变数据通路。分支指令的输出做为反馈输入到 IF 段。
  • 流水线寄存器的设计(实现各段之间的屏蔽)
    • 在流水线各段之间设置流水线寄存器文件,又称锁存器。当指令在流水线中流动时,其数据和控制信息也在同步地向前流动。
    • 需要用高速锁存器作为流水线寄存器:Earle 锁存器。Earle 对时钟扭曲不敏感。

MIPS 流水线的每个流水段的操作:

流水线性能分析 🗯

三项性能指标:吞吐率、加速比、效率

  • 吞吐率指单位时间内流水线所完成的任务数 或 输出结果的数量。
    • 最大吞吐率 $TP_{max}$ 是指流水线在达到稳定状态后得到的吞吐率。设第 i 段流水线时间为 $\Delta{x_i}$,那么 $TP_{max} = 1 / max(\Delta{x_i})$ –> 流水线中最慢的一段称为瓶颈。消除瓶颈的方法:细分瓶颈段、重复设置瓶颈段。
    • 设流水线由 m 段组成,完成 n 个任务的吞吐率称为实际吞吐率,记作 TP。
      • 若隔段时间相等,均为 $\Delta{t_0}$,那么完成时间 $T_{task} = m\Delta{t_0} + (n-1)\Delta{t_0}$,实际吞吐率 $TP = \frac{n}{T_{task}} = \frac{n}{m\Delta{t_0} + (n-1)\Delta{t_0}} = \frac{1}{(1 + \frac{m-1}{n})\Delta{t_0}} = \frac{TP_{max}}{1 + \frac{m-1}{n}}$。
      • 若各段时间不等,则完成时间 $T = \sum_{i=1}^{n}\Delta{t_i} + (n-1)max(\Delta{t_i})$,实际吞吐率 $TP = \frac{n}{\sum_{i=1}^{n}\Delta{t_i} + (n-1)max(\Delta{t_i})}$

  • 加速比指流水线速度与等功能的非流水线速度之比,用 S 表示。若隔段时间相等,均为 $\Delta{t_0}$,则 $T_{nonlinear} = nm\Delta{t_0}$,$T_{linear} = m\Delta{t_0} + (n-1)\Delta{t_0}$,$S = \frac{mn}{m+n-1} = \frac{m}{1+\frac{m-1}{n}}$
  • 效率指流水线的设备利用率,用 E 表示。由于流水线有通过时间和排空时间,所以流水线各段并非一直满负荷工作,E < 1。若各段时间相等,$E = \frac{n\Delta{t_0}}{T} = \frac{n}{m+n-1} = \frac{1}{1+\frac{m-1}{n}}$。当 n>>m 时,E ≈ 1。
  • 三者关系
    • $E = \frac{n\Delta{t_0}}{T} = \frac{mn\Delta{t_0}}{mT} = \frac{S}{m}$。加速比最大为 m,故效率是实际加速比 S 与最大加速比 m 之比。
    • $E = \frac{n\Delta{t_0}}{T} = \frac{n}{T}\Delta{t_0} = TP\Delta{t_0}$。当$\Delta{t_0}$不变时,流水线效率与吞吐率成正比。

增加流水线的深度可以提高流水线性能,而流水线深度受限于流水线的延迟和额外开销。指令之间存在的相关,也限制了流水线的性能。

流水线中的相关 🗯

  • 结构相关:当指令在重叠执行过程中,硬件资源满足不了指令重叠执行的要求,发生资源冲突时将产生“结构相关”。
  • 数据相关:因一条指令需要用到前面指令的结果,而无法与产生结果的指令重叠执行时,就发生了数据相关。
  • 控制相关:当流水线遇到分支指令和其它会改变 PC 值的指令时就发生控制相关。
    消除相关的基本方法:暂停流水线中某条指令及其之后的所有指令的执行。(很低效)

结构相关

导致结构相关的常见原因:

  • 功能部件不是全流水
  • 重复设置的资源数量不足
    例:当数据和指令存在同一存储器中时,访存指令会引起存储器访问冲突。
  • 解决方法:
  • 插入暂停周期
  • 将指令存储器和数据存储器分离

数据相关 🤔💭(木有吃透)

数据相关的分类:

  • 写后读(最常见的数据相关)
  • 读后写(MIPS 由硬件控制,不会出现这种相关):当有些指令在流水段后半部分读源操作数,另一些指令在流水线前半部分写结果,可能引起这种类型的相关。
  • 写后写(MIPS 由硬件控制,不会出现这种相关):当流水线中有多个段可以写回,而且当流水线暂停某条指令的执行,其后的指令可以继续前进时,可能引起这种类型的相关。

解决办法:

  • 插入暂停周期
  • 通过定向技术 (bypassing/forwarding) 减少数据相关带来的暂停
    • 主要思路:将计算结果从其产生的地方直接送到真正需要它的地方。
      定向技术不能解决所有的数据相关问题,那么:流水线互锁。当互锁硬件发现这种相关后,就暂停流水线,直到相关消除。这种情况下,暂停的时钟周期数称为“载入延迟”。
      对数据相关的编译调度方法:编译器可以通过重新排列代码的顺序来消除 这种暂停,将不相关的指令提前,这种技术就是“流水线调度”或“指令调度”。

对 MIPS 流水线控制的实现:

  • 指令发射:指令从流水线的译码段进入执行段的过程称为指令发射。
  • 检测数据相关
    • ID 段(指令译码)可以检测所有数据相关
    • 在使用一个操作数的时钟周期的开始(EX 和 MEM 段的开始)检测相关,并确定必需的定向
    • 流水线相关硬件可以检测到的各种相关情况

在插入暂停的情况下,流水线时空图如下所示:

LW R1, 0 (R2) IF ID EX MEM WB
SUB R4, R1, R5 IF ID Stall EX MEM WB
AND R6, R1, R7 IF Stall ID EX MEM WB
OR R8, R1, R9 Stall IF ID EX MEM WB

控制相关

分支指令:一旦分支转移成功,正确的地址要在 Mem 段的末尾才会被写入 PC;一旦 ID 段检测到分支指令,就暂停执行其后的指令,直到分支指令达到 Mem 段,确定新的 PC 为止。分支转移成功将导致 MIPS 流水线暂停 3 个周期。

减少分支开销的两个基本途径(同时采用,缺一不可!):

  • 流水线中尽早判断分支转移是否成功
  • 转移成功时,尽早计算出转移目标地址
    具体实现如下:
  • 将 “=0?” 测试提前到 ID 段
  • 在 ID 段增加一个加法器,计算分支目标地址

再改进:将分支判断结果和目标地址提前到 ID/EX 站前。

减少流水线分支损失的方法:

  1. 冻结或排空流水线
  • 思路:在流水线中停住或删除分支后的指令,直到知道转移目标地址。
  1. 预测分支转移失败
  • 思路:流水线继续照常流动,如果分支转移成功,将分支指令后的指令转换为空操作,并从分支目标处开始取指令执行;否则照常执行


(前面做的工作全部清空,放弃,转到分支程序)

  1. 预测分支转移成功
  • 思路:始终假设分支成功,直接从分支目标处取指令执行(对 MIPS 流水线无益,故 MIPS 不采取该措施)
  1. 延迟分支(delayed branch)
  • 思路:分支开销为 n 的分支指令后紧跟有 n 个延迟槽,流水线遇到分支指令时,按正常方式处理,顺带执行延迟槽中的指令,从而减少分支开销。
  • 什么样的指令能放入分支延迟槽?
    • 三种调度方法:从前调度;从目标处调度;从失败处调度
      • 编译器预测分支是否成功的能力
      • 放入延迟槽中的指令
    • 取消分支
      • 思路:分支指令中包含预测方向。若预测正确,正常执行延迟槽中的指令,否则将其转换为空操作

各种分支处理方法的性能:
假设理想 CPI = 1,则加速比$S = \frac{D}{1 + C} = \frac{D}{1 + f × p_{分支}}$
D 为流水线深度,$p_{深度}$ 为分支开销,C 为分支引起的流水线暂停时钟周期数(每条指令的平均值),f 为分支的出现频度。

向量处理机

向量流水线处理机:具有向量数据表示及相应向量指令的流水线处理机。—> 另:标量处理机

向量处理方式

  1. 水平(横向)处理方式:依次计算向量 k 和 d 的每个元素,循环迭代,每个迭代中,有 1 次数据相关,1 次控制相关,需要 2 次功能切换;
  2. 垂直(纵向)处理方式:计算完向量 k 的每个元素之后,再计算向量 d 的每个元素。没有分支;仅有一次数据相关,仅需要一次功能切换。—>需要存储器-存储器型操作的运算流水线;
  3. 分组(纵横)处理方式:切 m 片,组内纵向,m 次迭代,每次迭代执行两条向量指令,有一次数据相关,需要两次功能切换 —> 切片后,可以 将各个片放在寄存器上进行处理,借用寄存器处理速度快的优点,大大加快处理速度。—>需要寄存器-寄存器型操作的运算流水线

向量处理机速度评价标准

由于一条指令最多得到一个结果,标量处理机通常用每秒执行多少条指令 (MIPS) 来衡量机器的运算速度。
向量处理机用每秒取得多少浮点运算结果来衡量机器速度,以 MFLOPS 作为测量单位。采用 MFLOPS 可以忽视 Load、Store、分支、测试等类型指令的影响。

其他

向量链接技术