第三章 流水线技术2

null第三章 流水线技术第三章 流水线技术国防科技大学计算机学院null4.流水技术 将一重复的时序过程分解为若干子过程，每个子过程都可有效地在其专用功能段上与其它子过程同时执行，这种技术称为流水技术。 5.时-空图 从时间和空间两个方面描述流水线的工作过程，横坐标表示时间，纵坐标表示各流水段。null6.流水线的特点 流水过程由多个相关的子过程组成，这些子过程称为流水线的“级”或“段”。段的数目称为流水线的“深度”。 每个子过程由专用的功能段实现，各功能段的时间应基本相等，通常为1个时钟周期（1拍）。 流水线需要经过一定的通过时间才能稳定。 流水技术适合于大量重复的时序过程。null1.单功能流水线和多功能流水线 按流水线所完成的功能分类 单功能流水线，是指只能完成一种固定功能的流水线。 例如：功能单元流水线 多功能流水线，是指各段可以进行不同的连接，从而完成不同的功能。 例如：TI ASC的多功能流水线3.1.2 流水线的分类null2.静态流水线和动态流水线 按同一时间内流水段的连接方式划分 静态流水线，是指在同一时间内，流水线的各段只能按同一种功能的连接方式工作。 例如：TI ASC的流水线 适合于处理一串相同的运算操作 动态流水线，是指在同一时间内，当某些段正在实现某种运算时，另一些段却在实现另一种运算。 图3.6 会使流水线的控制变得很复杂null图3.9给出了实现DLX指令的一种简单数据通路 这是一种非流水方式 将指令执行划分为5个阶段 取指令周期 指令译码/读寄存器周期 执行/有效地址计算周期 存储器访问/分支完成周期 写回周期3.2.1 DLX的一种简单实现null1.取指令周期(IR) 操作为： 根据PC值从存储器中取出指令，并将指令送入指令寄存器IR；PC值增加4，指向顺序的下一条指令，并将下一条指令的地址放入临时寄存器NPC中。 IR←Mem[PC] NPC←PC+4 图示null2.指令译码/读寄存器周期(ID) 操作为： 进行指令译码，读IR寄存器（指令寄存器），并将读出结果放入两个临时寄存器A和B中。同时对IR寄存器中内容的低16位进行符号扩展，然后将符号扩展之后的32位立即值保存在临时寄存器Imm中。 A←Regs[IR6..10] B←Regs[IR11..15] Imm←((IR16)16##IR16..31) DLX的固定字段译码技术:图示null3.执行/有效地址计算周期(EX) 操作为： 存储器访问： ALUoutput←A+Imm 寄存器-寄存器ALU： ALUoutput←A op B 寄存器-立即值ALU: ALUoutput←A op Imm 分支操作： ALUoutput←NPC+Imm Cond←(A op 0) 问题：为什么执行和有效地址计算可以合并？null4.访存/分支操作完成周期(MEM) 操作为： 访存操作： Load： LMD←LMDMEM[ALUoutput] Store： Mem[ALUoutput]←B 分支操作： if (Cond) PC←ALUoutput else PC←NPCnull5.写回周期(WB) 操作为： 寄存器-寄存器型ALU指令： Reg[IR16..20]←ALUoutput 寄存器-立即值型ALU指令： Reg[IR11..15]←ALUoutput Load指令： Reg[IR11..15]←LMD null1.一种简单的DLX流水线 将3.2.1中的数据通路流水化，使得 数据通路中的每一个周期就成为流水线的一段 每个时钟周期启动一条指令 ——得到了一条简单的DLX流水线。 2.简单DLX流水线的流水过程 时-空图 按时间错开的数据通路3.2.2 基本的DLX流水线null3.实现流水技术应解决的一些问题 （1）应保证流水线各段不会在同一时钟周期内使用相同的寄存器通路资源。 例如，不能要求一个ALU既做有效地址计算，又做减法操作 IF与Mem两个阶段都要访问存储器，怎样避免访存冲突？ ID和WB两个阶段都要访问寄存器，是否存在冲突？怎样避免？null （2）PC计算问题 为了能够在每个时钟周期启动一条新的指令，流水线必须在IF段获得下一条指令的地址，并将其保存在PC中。 但是，分支指令会改变PC的值，而且只有在Mem段结束时，这个新值才会被写入PC，出现矛盾。 解决方法： 改变数据通路，在IF段完成PC计算。但分支指令如何处理？null （3）合理划分流水段，每段内的操作都必须在一个时钟周期内完成。 （4）流水线寄存器 为防止寄存器中的值在为流水线中某条指令所用时被流水线中其它的指令所重写，可在流水线各段之间设置流水线寄存器文件，也称锁存器。 流水线寄存器文件的命名 段A与B之间的流水线寄存器文件称为A/B 流水线寄存器的作用 流水线寄存器文件的构成null3.DLX流水线的操作 在任一时刻，流水中的指令仅在流水线中的某一段内执行操作。 因此，只要知道每一流水段在各指令下进行何种操作，就知道了整个流水线的操作。 P89 表3.1给出了DLX流水线中每一段的操作null 三项性能指标：吞吐率、加速比和效率 1.吞吐率 是衡量流水线速度的重要指标 吞吐率是指单位时间内流水线所完成的任务数或输出结果的数量。 最大吞吐率TPmax是指流水线在达到稳定状态后所得到的吞吐率。 设流水线由m段组成，完成n个任务的吞吐率称为实际吞吐率，记作TP。3.2.2 流水线性能分析null（1）最大吞吐率 假设流水线各段的时间相等，均为△t0，则： TPmax = 1/△t0 假设流水线各段时间不等，第i段时间为△ti ，则： TPmax = 1/max{△ti } 最大吞吐率取决于流水线中最慢一段所需的时间，该段成为流水线的瓶颈 消除瓶颈的方法 细分瓶颈段 重复设置瓶颈段 （时空图）null（2）实际吞吐率 若各段时间相等（假设均为△t0），则完成时间 T流水 = m△t0+(n-1)△t0 （说明） 时空图null若各段时间不等（假设第i段为△ti），则完成时间 时空图 T = ∑△ti+(n-1)△tj 这里，△tj=max{△ti }i=1mnull2. 加速比 加速比是指流水线速度与等功能的非流水线速度之比。 根据定义可知，加速比S = T非流水/T流水 若流水线为m段，每段时间均为△t0，则 T非流水 = nm△t0，T流水 = m△t0 + (n-1)△t0 S null3.效率 效率指流水线的设备利用率。 由于流水线有通过时间和排空时间，所以流水线的各段并非一直满负荷工作，E<1 若各段时间相等，则各段效率也相等，即e1 = e2 = e3 =… = n△t0/T流水 (解释) 整个流水线效率当n>>m时，E≈1null3.效率 从时-空图上看，效率就是n个任务所占的时空区与m个段总的时空区之比 根据这个定义，可以计算流水线各段时间不等时的流水线效率　 　n 个任务占用的时空区 E ＝━━━━━━━━━━━ m 个段总的时空区null4. 吞吐率、加速比和效率的关系 E = n△t0/T流水=mn△t0/(T流水m)= S/m 效率是实际加速比S与最大加速比m之比。 E = n△t0/T流水= (n/T流水) ·△t0=TP△t0 当△t0不变时，流水线的效率与吞吐率呈正比。为提高效率而采取的，也有助于提高吞吐率。null1. 什么是相关？ 流水线中的相关是指相邻或相近的两条指令因存在 某种关联，后一条指令不能在原先指定的时钟周期 开始执行。 消除相关的基本方法——暂停 暂停流水线中某条指令及其后面所有指令的执行， 该指令之前的所有指令继续执行。3.3 流水线中的相关null2. 三种不同类型的相关 结构相关：当指令在重叠执行过程中，硬件资源满足不了指令重叠执行的要求，发生资源冲突时将产生“结构相关”。 数据相关：因一条指令需要用到前面指令的结果，而无法与产生结果的指令重叠执行时，就发生了数据相关。 控制相关：当流水线遇到分支指令和其它会改变PC值的指令时就发生控制相关。null避免结构相关的方法： 所有功能单元完全流水化 设置足够多的硬件资源 但是，硬件代价很大！ 有些设计允许结构相关存在 降低成本 减少功能单元的延迟null1. 数据相关简介 实例： ADD R1， R2，R3 SUB R4， R1，R5 AND R6， R1，R7 OR R8， R1，R9 XOR R10，R1，R11 产生原因：当指令在流水线中重叠执行时，流水线有可能改变指令读/写操作数的顺序，使之不同于它们在非流水实现时的顺序，这将导致数据相关。 消除方法：向流水线中插入暂停周期3.3.2 数据相关null2. 通过定向技术减少数据相关带来的暂停 定向(forwarding)，也称为旁路(bypassing) 工作过程 主要思路：将计算结果从其产生的地方直接送到真正需要它的地方，就可以避免暂停。 寄存器文件EX/MEM中的ALU运算结果总是回送到ALU的输入寄存器 从定向通路得到输入数据的ALU操作不必从源寄存器中读取操作数null2. 通过定向技术减少数据相关带来的暂停 进一步推广：一个结果不仅可以从某一功能单元的输出定向到其自身的输入，而且还可以定向到其它功能单元的输入。 (举例) 在DLX中，任何流水寄存器到任何功能单元的输入都可能需要定向路径，将形成复杂的旁路网络。 两条指令访问同一存储单元，也可能引起数据相关，例如访问数据Cache失效时。 本章只讨论寄存器数据相关！null3. 数据相关的分类 两条指令 i 和 j，都会访问同一寄存器R，假设i 先进入流水线，则它们对R有四种不同的访问顺序： (1) 写后读( RAW ) —— i 写j 读 如果j 在i 完成写之前从R 中读出数据，将得到错误的结果！ 最常见的数据相关，严重制约了CPU的性能，是程序最重要的特征之一！null3. 数据相关的分类 (2) 写后写( WAW ) —— i 写j 写 如果j 在i 之前完成写操作，R中将保存错误的结果！ DLX流水线不会出现这种相关！ 当流水线中有多个段可以写回，而且当流水线暂停某条指令的执行时，其后的指令可以继续前进时，可能引起这种类型的相关。 举例null3. 数据相关的分类 (3) 读后写(WAR ) —— i 读j 写 如果j 先将数据写入R，i 将读出错误的结果！ DLX流水线不会出现这种类型的相关！ 当有些指令在流水段后半部分读源操作数，另一些指令在流水线前半部分写结果，可能引起这种类型的相关。 (4) 读后读(RAR ) —— i 读j 读 不引起数据相关！null4. 需要暂停的数据相关 并非所有数据相关都可以通过定向技术解决。 例： LW R1，0（R2） SUB R4，R1，R5 AND R6，R1，R7 OR R8，R1，R9 增加流水线“流水线互锁”部件，当互锁硬件发现这种相关后，就暂停流水线，直到相关消除。 这种情况下，暂停的时钟周期数称为“载入延迟”。 例1 时空图null5. DLX流水线中指令发射的控制 指令发射：指令从流水线的译码段进入执行段的过程称为指令发射。 检测数据相关 ID段可以检测所有数据相关 在使用一个操作数的时钟周期的开始(EX和MEM段的开始)检测相关，并确定必需的定向 流水线相关硬件可以检测到的各种相关情况null5. 对DLX流水线控制的实现 例：Load互锁的检测与实现 在ID段检测是否需要启动Load互锁，必须进行三种比较 一旦检测到相关，控制部件必须在流水线中插入暂停周期，并使IF和ID段中的指令停止前进。 将ID/EX中控制部分清0 保持IF/ID的内容不变null5. 对DLX流水线控制的实现 定向逻辑的实现 所有的定向都是从ALU/DM的输出到ALU、DM或0检测单元的输入 (图示) 形成了一个旁路网络 需要比较哪些信息？ ALU输入端应采用多少个输入的MUX？null1. 分支指令的实现 一旦分支转移成功，正确的地址要在Mem段的末尾才会被写入PC 一旦ID段检测到分支指令，就暂停执行其后的指令，直到分支指令达到Mem段，确定新的PC为止 分支转移成功将导致DLX流水线暂停3个周期3.3.2 控制相关null2. 减少分支开销的途径 两个基本途径：同时采用，缺一不可！ 在流水线中尽早判断分支转移是否成功 转移成功时，尽早计算出转移目标地址 经改进，DLX流水线可以将分支开销减少1拍 将“=0?”测试提前到ID段 在ID段增加一个加法器，计算分支目标地址 表3.6列出了改进后流水线的分支操作 再改进，DLX流水线可以将分支开销再减少1拍 将分支判断结果和目标地址提前到ID/EX站前null4. 减少流水线分支损失的方法 (1) 冻结或排空流水线 思路：在流水线中停住或删除分支后的指令，直到知道转移目标地址 优点：简单 (2) 预测分支转移失败 思路：流水线继续照常流动，如果分支转移成功，将分支指令后的指令转换为空操作，并从分支目标处开始取指令执行；否则照常执行 DLX流水线的处理过程null4. 减少流水线分支损失的方法 (3) 预测分支转移成功 思路：始终假设分支成功，直接从分支目标处取指令执行 对DLX流水线没有任何好处！ (4) 延迟分支（delayed branch） 思路：分支开销为n的分支指令后紧跟有n个延迟槽，流水线遇到分支指令时，按正常方式处理，顺带执行延迟槽中的指令，从而减少分支开销。 延迟分支及指令的执行顺序null A、B、C、D四个向量 1．水平（横向）处理方式 依次计算向量k和d的每个元素 … … ki = bi + ci di = ki * ai … … 循环的每个迭代(iteration)中有1次数据相关，1次控制相关，需要2次功能切换3.5.1 向量处理方式和向量处理机null2．垂直（纵向）处理方式 计算向量k的每个元素之后，再计算向量d的每个元素，需要向量数据类型和向量指令的支持 K = B + C D = K * A 没有分支；仅有1次数据相关；仅需要1次功能切换 需要存储器-存储器型操作的运算流水线null3．分组（纵横）处理方式 将长度为N的向量分为m组，每组有n个元素，组内按纵向方式处理，依次处理各组。 需要m次迭代；每次迭代执行两条向量指令，有1次数据相关，需要2次功能切换 需要寄存器-寄存器型操作的运算流水线 这种技术称为向量循环或分段开采null实例：Cray-I 1. 性能指标 1GFLOPS、主频80M、向量长度64位 2. 基本结构 向量运算部件 向量寄存器组（V0-V7） 向量长度寄存器 向量屏蔽寄存器3.5.2 提高向量处理机性能的主要技术null3. 向量指令类型 Vk ← Vi op Vj Vk ← Si op Vj Vk ← Mem Mem ← Vk 功能部件冲突：同一功能部件被一条以上的并行工作向量指令所使用。 Vi冲突：并行工作的各向量指令具有相同的源向量或结果向量。null4. CRAY-I体系结构特点 向量寄存器与功能单元的连接通路 每个Vi块都有单独总线可连到所有向量功能部件，而每个向量功能部件也各自都有把运算结果送回向量寄存器组的总线。 向量链接技术 一个向量功能部件得到的结果直接送入另一个向量功能部件的操作数寄存器时所发生的连接过程称为链接。null 当两条指令出现“写后读”相关时，若它们不存在功能部件冲突和向量寄存器(源或目的) 冲突，就有可能把它们所用的功能部件头尾相接，形成一个链接流水线，进行流水处理。 链接特性实质上是把流水线“定向”的思想引入到向量执行过程的结果。null例3.7：对向量运算D=A*(B+C)，若向量长度N≤64， 向量元素为浮点数，则在B、C取到V0、V1后， 就可用以下三条向量指令求解： V3←存储器 (访存，载入A) V2←V0＋V1 (浮点加) V4←V2*V3 (浮点乘，将D存入V4) 5. 向量链接技术实例分析null假设：向量处理机将元素从Vi送往功能部件及把结果存 入Vi都需要1拍；浮点加法和访存操作都需要6 拍；浮点乘操作需要7拍。 这样，第一个结果被存入V4需要经过： 1(送)+ 6(浮加) +1(入)+1(送)+7(浮乘)+1(入)=17(拍) 此后，每拍将得到一个结果送入V4。 总的完成时间为：17+（N-1）拍null1. 向量指令的处理时间Tvp Tvp = Ts + Tvf + (n-1)Tc Ts为向量处理单元流水线的建立时间，包括：向量起始地址的设置、计数器加1、条件转移指令执行等。 Tvf为向量处理单元流水线的流过时间，它是从向量指令开始执行到得到第一个计算结果（向量元素）所需的时间。 Tc为向量处理单元流水线“瓶颈”段的执行时间。3.5.3 向量处理机性能评价null1. 向量指令的处理时间Tvp 也可以表示为： Tvp =[s+e+(n-1)]Tclk=(Tstart+n)Tclk 这里， Tclk表示时钟周期时间 s为向量处理单元流水线建立所需的时钟周期数 e为向量流水线流过所需的时钟周期数； Tstart为向量功能部件启动所需的时钟周期数 null1. 向量指令处理时间Tvp 对于一组向量指令而言，其执行时间主要取决于三个 因素： 向量操作之间是否链接 向量的长度 向量功能部件的冲突和数据的相关性 把几条能在同一个时钟周期内一起开始执行的向量指 令集合称为一个编队。 null例： 假设每种向量功能部件只有一个，那么下面的一 组向量指令能分成几个编队？ LV V1，Rx MULTSV V2，R0，V1 LV V3，Ry ADDV V4，V2，V3 SV Ry，V4LV V1,Rx MULTSV V2,R0,V1 LV V3，Ry ADDV V4,V2,V3 SV Ry,V4null1. 向量指令处理时间Tvp 同一个编队中的向量指令之间一定不存在流水向量 功能部件的冲突和数据的相关性 其执行时间为： 若代码段可分为m个编队，总执行时间为：null1. 向量指令处理时间Tvp 如果采用分段开采技术，即向量长度MVL