周期与多周期的比较指令流水线

第一讲 流水线数据通路和控制逻辑 第二讲 流水线冒险处理 第三讲 高级流水线技术 Ch7: Instruction Pipeline 指令流水线 Pipeline.2 2021年 2月 20日星期六 第一讲 流水线数据通路和控制 日常生活中的流水线处理例子：洗衣服 单周期处理器模型和流水线性能比较 什么样的指令集适合于流水线方式执行 如何设计流水线数据通路 以 MIPS指令子集来说明 详细设计取指令部件 详细设计执行部件 分析每条指令在流水线中的执行过程，遇到各种问题： - 资源冲突 - 寄存器和存储器的信号竞争 - 分支指令的延迟 - 指令间数据相关 如何设计流水线控制逻辑 分析每条指令执行过程中的控制信号 给出控制器设计过程 流水线冒险的概念 主 要 内 容 Pipeline.3 2021年 2月 20日星期六 复习： A Single Cycle Processor 32 ALUctr Clk busW RegWr 32 32 busA 32 busB 5 5 5 Rw Ra Rb 32 32-bit Registers Rs Rt Rt Rd RegDst Ex tender M ux Mux 32 16 imm16 ALUSrc ExtOp M ux MemtoReg Clk Data In WrEn 32 Adr Data Memory 32 MemWr ALU Zero 0 1 0 1 0 1 Instruction Fetch Unit Clk Instruction Jump Branch Imm16 Rd Main Control op ALU Control func ALUop 3 RegDst ALUSrc : Instr Zero 3 Pipeline.4 2021年 2月 20日星期六 复习： Multiple Cycle Processor MCP: 一个功能部件在一个指令周期中可以被使用多次。 Ideal Memory WrAdr Din RAdr 32 32 32 Dout MemWr 32 ALU 32 32 ALUOp ALU Control Ins truct ion Reg 32 IRWr 32 Reg File Ra Rw busW Rb 5 5 32 busA 32 busB RegWr Rs Rt M ux 0 1 Rt Rd PCWr ALUSelA Mux 0 1 RegDst M ux 0 1 32 PC MemtoReg Extend ExtOp M ux 0 1 32 0 1 2 3 4 16 Imm 32 2 ALUSelB M ux 1 0 Target 32 Zero Zero PCWrCond PCSrc BrWr 32 IorD Pipeline.5 2021年 2月 20日星期六 复习： Timing Diagram of a Load Instruction Clk PC Rs, Rt, Rd, Op, Func Clk-to-Q ALUctr Instruction Memory Access Time Old Value New Value RegWr Old Value New Value Delay through Control Logic busA Register File Access Time Old Value New Value busB ALU Delay Old Value New Value Old Value New Value New Value Old Value ExtOp Old Value New Value ALUSrc Old Value New Value Address Old Value New Value busW Old Value New Delay through Extender d = e f; 假定 a, b, c, d ,e, f 在内存 方案 3：编译器进行指令顺序调整来解决 load-use Fast code: lw $2, b lw $3, c lw $5, e add $1, $2, $3 lw $6, f sw a, $1 sub $4, $5, $6 sw d, $4 Slow code: lw $2, b lw $3, c add $1, $2, $3 sw a, $1 lw $5, e lw $6, f sub $4, $5, $6 sw d, $4 调整后 编译器的优化很重要！ Pipeline.60 2021年 2月 20日星期六 编译器优化以避免阻塞的情况调查 : % lo ad s sta ll in g pi pe li ne 0% 20 % 40 % 60 % 80 % tex spice gcc 25 % 14 % 31 % 65 % 42 % 54 % sc h e d ul ed unschedul e d 由此可见，优化调度后 load阻塞现象大约降低了 1/21/3 Pipeline.61 2021年 2月 20日星期六 数据冒险的解决方法 方法 1：硬件阻塞（ stall） 方法 2：软件插入“ NOP指令 方法 3：编译优化：调整指令顺序，能解决所有数据冒险吗？ 方法 4：合理实现寄存器堆的读 /写操作，能解决所有数据冒险吗？ 前半时钟周期写，后半时钟周期读 若同一个时钟内前面指令写入的数据正好是后面指令所读数据，则不会发生 数据冒险 方法 5：转发（ Forwarding或 Bypassing 旁路）技术，能解决所有数据冒险吗？ - 若相关数据是 ALU结果，则如何？ 可通过转发解决 - 若相关数据是上条指令 DM读出内容，则如何？ 不能通过转发解决，随后指令需被阻塞一个时钟 或 加 NOP指令 实现 “转发” 和 “阻塞” 要修改数据通路： （ 1）检测何时需要“转发” ，并控制实现“转发” （ 2）检测何时需要“阻塞”，并控制实现“阻塞” 称为 Load-use数据冒险！ Pipeline.62 2021年 2月 20日星期六 RAW（写后读）数据冒险的“转发”条件 后面指令需用 ALU输出结果 C1: 目寄是后一条指令的源寄 C2: 目寄是后第二条指令的源寄 (例如： R-Type后跟 R- / lw / sw / beq等 ) 后面指令需用从 DM读出的结果 C3: 目寄是后第二指令的源寄 (例如： load指令后跟 R-Type / beq等 ) 用流水段寄存器来表示转发条件（ C3以后考虑） C1(a): EX/MEM. RegisterRd=ID/EX. RegisterRs C1(b): EX/MEM. RegisterRd=ID/EX. RegisterRt C2(a): MEM/WB. RegisterRd=ID/EX. RegisterRs C2(b): MEM/WB. RegisterRd=ID/EX. RegisterRt 这里的 RegisterRd是指 目的寄存器 实际上是 R-type的 Rd 或 I-Type的 rt ori r3, r2, 100 sub r5, r3, r4 C1 add r3, r2, r1 or r6, r2, r1 sub r5, r3, r4 C2 lw r3, 100(r1) or r6, r2, r1 sub r5, r3, r4 C3 Ex Mem Pipeline.63 2021年 2月 20日星期六 指令的回写（ Write Back）阶段 IF/ID: ID/E x Regis ter Ex /M em Reg ister M em /W r Reg ister PC Data Mem WA Di RA Do IUnit A I RFile Di Ra Rb Rw MemWr RegWr=1 ExtOp Exec Unit busA busB Imm16 ALUOp ALUSrc M ux 1 0 MemtoReg=1/0 1 0 RegDst Rt Rd Imm16 PC+4 PC+4 Rs Rt PC+4 Zero Branch 1 0 Clk Ifetch Reg/Dec Exec Mem Wr Rd还是 Rt取决于是 R-型 指令，还是 I-型指令！ 若是 beq指令会怎样 ？ beq r3, r2, 100 sub r5, r3, r2 因为 beq指令没有写结果，不能进行转发！ Pipeline.64 2021年 2月 20日星期六 转发条件的进一步完善 以下两种情况下，根据前面的转发条件转发会发生错误 指令的结果不写入目的寄存器 Rd时 - 例如， Beq指令只对 rs和 rt相减，不写结果到目的寄存器 - 即： EX / MEM 或 MEM / WB 流水段寄存器的 RegWrite信号为 0 Rd等于 $0时 - 例如，指令 sll $0, $1, 2 的转发结果为 (R$1PC 清除 IF段中取出的指令，即：将 IF/ID中的指令字清 0，转变为 nop指令 原来要清除三条指令，调整后只需要清除一条指令，因而只延迟一个时钟周期 ，每次预测错误减少了两个周期的代价！ Pipeline.77 2021年 2月 20日星期六 带静态分支预测处理的数据通路 IF.Flush=Branch and Zero 40#指令 beq $1,$3, 7的 ID阶段 若 $1或 $3和前面指令数据相关，会怎么样？ 上上条指令的 EXE段结果可转发回来进行判断 上条指令的 EXE段结果来不及转发回来，引起 1次阻塞 ! 将 IF/ID中指令字清 0，变为 nop指令 控制转移 目标地址 -PC 转移目标地址 (72)-PC 需重新改“转发”条件和转发线路 ！ 作业中有相应的练习 sub $3, $5, $1 add $1, $5, $2 beq $1, $3, 7 BACK Pipeline.78 2021年 2月 20日星期六 动态分支预测方法 简单的静态分支预测方法的预测成功率不高，应考虑动态预测 动态预测基本思想： 利用最近转移发生的情况，来预测下一次可能发生的转移 预测后，在实际发生时验证并调整预测 转移发生的历史情况记录在 BHT中（有多个不同的名称） - 分支历史记录表 BHT（ Branch History Table） - 分支预测缓冲 BPB（ Branch Prediction Buffer） - 分支目标缓冲 BTB（ Branch Target Buffer） 每个表项由分支指令地址的低位索引，故在 IF阶段就可以取到预测位 - 低位地址相同的分支指令共享一个表项，所以，可能取的是其他分支 指令的预测位。会不会有问题？ - 由于仅用于预测，所以不影响执行结果 现在几乎所有的处理器都采用动态预测（ dynamic predictor） Pipeline.79 2021年 2月 20日星期六 分支历史记录表 BHT（或 BTB、 BPB） 指令预取器 分支指令地址 转移目标地址 预测位 分支 指令 地址 控制逻辑 指令执行 实际执行情况 命中与否 加入新项 顺序取 转移取 分支历史记录表 BHT =？ 查找 选择 预测 修正 查找时发现都不相 等，则“未命中” 未命中说明什么？ 说明以前没有执 行过该分支指令 命中时： 根据预测位，选择“转移取”还是“顺序取” 未命中时： 加入新项，并填入指令地址和转移目标地址、初始化预测位 Pipeline.80 2021年 2月 20日星期六 动态预测基本方法 采用一位预测位：总是按上次实际发生的情况来预测下次 1表示最近一次发生过转移（ taken）， 0表示未发生（ not taken） 预测时，若为 1，则预测下次 taken，若为 0，则预测下次 not taken 实际执行时，若预测错，则该位取反，否则，该位不变 可用一个简单的 预测状态图 表示 缺点：当连续两次的分支情况发生改变时，预测错误 - 例如，循环迭代分支时，第一次和最后一次会发生预测错误，因为 循环的第一次和最后一次都会改变分支情况，而在循环中间的各次 总是会发生分支，按上次的实际情况预测时，都不会错。 采用二位预测位 用 2位组合四种情况来表示预测和实际转移情况 按照 预测状态图 进行预测和调整 在连续两次分支发生不同时，只会有一次预测错误 采用比较多的是二位预测位，也有采用二位以上预测位。 如： Pentium 4 的 BTB2采用 4位预测位 BACK Pipeline.81 2021年 2月 20日星期六 一位预测状态图 指令预取时，按照预测读取相应分支的指令 预测发生时，选择“转移取” 预测不发生时，选择“顺序取” 指令执行时，按实际执行结果修改预测位 对照状态转换图来进行修改 例如：对于一个循环分支 若初始状态为 0(再次循环时为 0)，则第一次和 最后一次都错 若初始状态为 1，则只有最后一次会错 预测发生 发 生 不发生 预测不发生 不发生 发生 1 0 正确 错误 错误 正确 Loop: add $7, $3, $3 ; i*2 add $7, $7, $7 ; i*4 add $7, $7, $5 lw $6, 0($7) ; $6=Ai add $1, $1, $6 ; g= g+Ai add $3, $3, $4 bne $3, $2, Loop Loop: g = g +Ai; i = i+ j; if (i != h) go to Loop: Assuming variables g, h, i, j $1, $2, $3, $4 and base address of array is in $5 即：只要本次和上次的发生情况不同，就会出现一次预测错误。 BACK Pipeline.82 2021年 2月 20日星期六 两位预测状态图 基本思想：只有两次预测错误才改变预测方向 00状态时预测发生（强转移），实际不发生时，转到状态 01（弱转移），下次仍预测 为发生，如果再次预测错误（实际不发生），才使下次预测调整为不发生 11 好处：连续两次发生不同的分支情况时，可能会预测正确 例如，对于循环分支的预测 - 第一次：初始态为 00（再次循环时状态为 01），预测发生，实际也发生，正确 - 中间：状态为“ 00，预测发生，实际也发生，正确 - 最后一次：状态为“ 00，预测发生，但实际不发生，错 BACK 预测发生 发生 预测不发生 不发生 预测发生 预测不发生 发生 不发生 发生 不发生 发生 不发生 00 01 10 11 正确 错误 正确 错误 正确 正确 错误 错误 预测发生时，选择“转移取” 预测不发生时，选择“顺序取 ” Loop: add $7, $3, $3 ; i*2 add $7, $7, $7 ; i*4 add $7, $7, $5 lw $6, 0($7) ; $6=Ai add $1, $1, $6 ; g= g+Ai add $3, $3, $4 bne $3, $2, Loop Pipeline.83 2021年 2月 20日星期六 分支延迟时间片的调度 属于静态调度技术，由编译程序重排指令顺序来实现 基本思想： 把分支指令前面的与分支指令无关的指令调到分支指令后面执行，以填充延 迟时间片 （也称分支延迟槽 Branch Delay slot） ，不够时用 nop操作填充 举例：如何对以下程序段进行分支延迟调度？ （假定时间片为 2） 调度后，降低了分支延迟损失 lw $3, 0($2) add $6, $4, $2 beq $3, $5, 2 lw $1, 0($2) add $3, $3,$2 sw $1, 0($2) lw $1, 0($2) lw $3, 0($2) add $6, $4, $2 beq $3, $5, 2 add $3, $3,$2 sw $1, 0($2) 调度后可能带来其他问题：产生新的 load-use数据 冒险 BACK 若分支条件判断和目标地址计算提前到 ID阶段，则分支延迟时间片减少为 1 调度后 lw $3, 0($2) add $6, $4, $2 beq $3, $5, 2 lw $1, 0($2) nop add $3, $3,$2 sw $1, 0($2) Pipeline.84 2021年 2月 20日星期六 另一种控制冒险：异常和中断 异常和中断会改变程序的执行流程 某条指令发现异常时，后面多条指令已被取到流水线中正在执行 例如 ALU指令发现“溢出”时，已经到 EX阶段结束了，此时，它后 面已有两条指令进入流水线了 流水线数据通路如何处理异常 ? (举例说明 ) 假设指令 add r1,r2,r3产生了溢出 （记住： MIPS异常处理程序的首地址为 0 x8000 0180） 处理思路： 清除 add指令以及后面的所有已在流水线中的指令 保存 PC或 PC+4 到 EPC 从 0 x8000 0180处开始取指令 Pipeline.85 2021年 2月 20日星期六 异常的处理 异常（溢出）在第一条指令的 EXE阶段被检出 I n s t r. O r d e r Time (clock cycles) add r1,r2,r3 sub r4,r2,r3 and r6,r1,r4 I F ID/R F E X ME M W B ALU Im Reg Im Reg Dm Reg ALU bubble bubble bubble Im bubble bubble bubble bubble Im Im 异常处理程序首指令 Reg 阻塞点 Reg AL U Dm bubble bubble bubble 异常处理： IF.Flush使 IF段指令在 IF/ID寄存器中清为 0，变成 nop指令 ID.Flush与数据冒险阻塞检测信号相或 (or)后，使 ID段指令的控制信号清 0 EX.Flush使 EX段指令的控制信号清 0 将 0 x8000 0180作为 PC的一个输入，并控制 PC输入端的多路选择器 将断点（可能是 PC、可能是 PC+4）保存到 EPC中 即： 0 x80000180处指令 会发生将溢出结果写到寄 存器 r1中去的情况吗？ 不会！ EX.Flush使 EXE段指令的控制 信号清 0（主要保证 RegWr清 0），避 免了在 WB阶段写寄存器 r1的情况。 Pipeline.86 2021年 2月 20日星期六 带异常处理的流水线数据通路 Overflow 80000180H Pipeline.87 2021年 2月 20日星期六 流水线方式下的异常处理的难点问题 流水线中有 5条指令，到底是哪一条发生异常？ 根据异常发生的流水段可确定是哪条指令，因为各类异常发生的流水段不同 “溢出”在 EXE段检出 “无效指令”在 ID段检出 “除数为 0在 ID段段检出 “无效指令地址”在 IF段检出 “无效数据地址”在 Load/Store指令的 EXE段检出 外部中断与特定指令无关，如何确定处理点？ 可在 IF段或 WB段中进行中断查询，需要保证当前 WB段的指令能正确完成，并在有 中断发生时，确保下个时钟开始执行中断服务程序 检测到异常时，指令已经取出多条，当前 PC的值已不是断点，怎么办？ 指令地址（哪条？）存放在流水段 R，可把这个地址送到 EPC保存，以实现精确中断 （非精确中断不能提供准确的断点，而由操作系统来确定哪条指令发生了异常） 一个时钟周期内可能有多个异常，该先处理哪个？ 异常：检出异常存到专门寄存器， （前面指令优先级高？） 中断：在中断查询程序或中断优先级排队电路中按顺序查询 系统中只有一个 EPC，多个中断发生时，一个 EPC不够放多个断点，怎么办？ 总是把优先级最高的送到 EPC中 在异常处理过程中，又发生了新的异常或中断，怎么办？ 利用中断屏蔽和中断嵌套机制来处理 后面三个问题在第九章中详细介绍！ Pipeline.88 2021年 2月 20日星期六 复习： Cache 的操作过程 如果被访问的信息 不在 cache中，称 为失效 (miss) 如果被 访问的 信息在 cache 中，称 为命中 (hit) 缺失处理 硬件如何进行缺失处理？ Pipeline.89 2021年 2月 20日星期六 Cache缺失处理会引起流水线阻塞（停顿） 在使用 Cache的系统中，数据通路中的 IM和 DM分别是 Code Cache和 Data Cache CPU执行指令过程中，取指令或取数据时，如果发生缺失，则指令执行被阻塞 Cache缺失的检测 （如何进行的？记得吗？） Cache中有相应的检测线路（地址高位与 Cache标志比较） 阻塞处理过程 冻结所有临时寄存器和程序员可见寄存器的内容（即：使整个计算机阻塞） 由一个单独的控制器处理 Cache缺失， 其过程 (假定是指令缺失 ) 还记得吗？ ： - 把发生缺失的指令地址 （ PC- 4） 所在的主存块首址送到主存 - 启动一次“主存块读”操作，并等待主存完成一个主存块 (Cache行 )的读操作 - 把读出的一个主存块写到 Cache对应表项的数据区 （若对应表项全满的话，还要考虑淘汰掉一个已在 Cache中的主存块） - 把地址高位部分（标记）写到 Cache的“ tag字段，并置“有效位” - 重新执行指令的第一步：“取指令” 若是读数据缺失，其处理过程和指令缺失类似 - 从主存读出数据后，从“取数”那一步开始重新执行就可以了 若是写数据缺失，则要考虑用哪种 写策略”解决“一致性”问题 比数据相关或分支指令引起的流水线阻塞简单：只要保持所有寄存器不变 与中断引起的阻塞处理不同：不需要程序切换 Pipeline.90 2021年 2月 20日星期六 TLB缺失和缺页也会引起流水线阻塞 TLB缺失处理 当 TLB中没有一项的虚页号与要找的虚页号相等时，发生 TLB miss TLB miss说明可能发生以下两种情况之一： - 页在内存中： 只要把主存中的页表项装载到 TLB中 - 页不在内存中 (缺页 )： OS从磁盘调入一页，并更新主存页表和 TLB 缺页（ page fault）处理 当主存页表的页表项中“ valid位为“ 0时，发生 page fault Page fault是一种“故障”异常，按以下过程处理（ MIPS异常处理） - 在 Cause寄存器置相应位为“ 1 - 发生缺页的指令地址 （ PC- 4） 送 EPC - 0 x8000 0180(异常查询程序入口 )送 PC 执行 OS的异常查询程序，取出 Cause寄存器中相应的位分析，得知发生了“缺 页”，转到“缺页处理程序”执行 page fault一定要在发生缺失的存储器操作时钟周期内捕获到，并在下个时钟转到异常 处理，否则，会发生错误。 - 例： lw $1, 0($1) ，若没有及时捕获“异常”而使 $1改变，则再重新执行该指令时 ，所读的内存单元地址被改变，发生严重错误！ 处理 Cache缺失和缺页的不同之处在哪里？ 哪种要进行程序切换？ Pipeline.91 2021年 2月 20日星期六 （缺页）异常处理时要考虑的一些细节 缺页异常结束后，回到哪里继续执行？ 指令缺页：重新执行发生缺页的指令 数据缺页： - 简单指令（仅一次访存）： 强迫指令结束，重新执行缺页指令 - 复杂指令（多次访存）： 可能会发生多次缺页，指令被中止在中间某 个阶段，缺页处理后，从中间阶段继续执行；因而，需要能够保存和 恢复中间机器状态 异常发生后，又发生新的异常，怎么办？ 在发现异常、转到异常处理程序中，若在保存正在运行进程的状态时又发 生新的异常，则因为要处理新的异常，会把原来进程的状态和保存的返回 断点破坏掉，所以，应该有一种机制来“禁止”响应新的异常处理（？） 通过“中断 /异常允许”状态位（或“中断 /异常允许”触发器）来实现？ “中断 /异常允许”状态位置 1，则“开中断”（允许异常），清 0则“关 中断 ”（ 禁止异常）？ OS通过管态指令来设置该位的状态？ Pipeline.92 2021年 2月 20日星期六 三种处理器实现方式的比较 单周期、多周期、流水线三种方式比较 假设各主要功能单元的操作时间为： 存储单元： 200ps ALU和加法器： 100ps 寄存器堆（读 / 写）： 50ps 假设 MUX、控制单元、 PC、扩展器和传输线路都没有延迟，指令组成为： 25%取数、 10%存数、 52%ALU、 11%分支、 2%跳转 则下面实现方式中，哪个更快？快多少？ （ 1）单周期方式：每条指令在一个固定长度的时钟周期内完成 （ 2）多周期方式：每类指令时钟数 :取数 -5，存数 -4， ALU-4，分支 -3，跳转 -3 （ 3）流水线方式：每条指令分取指令、取数 /译码、执行、存储器存取、写回五阶段 （假定没有结构冒险，数据冒险采用转发处理，分支延迟槽为 1，预测准确率 为 75%；不考虑异常、中断和访问缺失引起的流水线冒险） Pipeline.93 2021年 2月 20日星期六 三种处理器实现方式的比较 解： CPU执行时间 =指令条数 x CPI x 时钟周期长度 三种方式的指令条数都一样，所以只要比较 CPI和时钟周期长度即可。 各指令类型要求的时间长度为： Pipeline.94 2021年 2月 20日星期六 三种处理器实现方式的比较 对于单周期方式： 时钟周期将由最长指令来决定，应该是 load指令，为 600ps 所以， N条指令的执行时间为 600N(ps) 对于多周期方式： 时钟周期将取功能部件最长所需时间，应该是存取操作，为 200ps 根据各类指令的频度，计算平均时钟周期数为： CPU时钟周期 =5x25%+4x10%+4x52%+3x11%+3x2%=4.12 所以， N条指令的执行时间为 4.12x200 xN=824N(ps) 对于流水线方式： Load指令：当发生 Load-use依赖时，执行时间为 2个时钟，否则 1个时钟，故平均 执行时间为 1.5个时钟； Store、 ALU指令： 1个时钟； Branch指令：预测成功时， 1个时钟，预测错误时， 2个时钟， 所以：平均约为： .75x1+.25x2=1.25个； Jump指令： 2个时钟（总要等到译码阶段结束才能得到转移地址） 平均 CPI为： 1.5x25%+1x10%+1x52%+1.25x11%+2x2%=1.17 所以， N条指令的执行时间为 1.17x200 xN=234N(ps) Pipeline.95 2021年 2月 20日星期六 流水线冒险对程序性能的影响 结构冒险对浮点运算的性能影响较大，因为浮点运算单元不能有效被流水 化，可能造成运算单元的资源冲突 控制冒险更多出现在整数运算程序中，因为分支指令对应于循环或选择结 构，大多由整数运算结果决定分支 数据冒险在整数运算程序和浮点运算程序中都一样 浮点程序中的数据冒险容易通过编译器优化调度来解决 - 分支指令少 - 数据访问模式较规则 整数程序的数据冒险不容易通过编译优化调度解决 - 分支指令多 - 数据访问模式不规则 - 过多使用指针 Pipeline.96 2021年 2月 20日星期六 第二讲小结 流水线冒险的几种类型： 资源冲突、数据相关、控制相关（改变指令流的执行方向） 数据冒险的现象和对策 数据冒险的种类 - 相关的数据是 ALU结果，可以通过转发解决 - 相关的数据是 DM读出的内容，随后的指令需被阻塞一个时钟 数据冒险和转发 - 转发检测 / 转发控制 数据冒险和阻塞 - 阻塞检测 / 阻塞控制 控制冒险的现象和对策 静态分支预测技术 缩短分支延迟技术 动态分支预测技术 异常和中断是一种特殊的控制冒险 访存缺失（ Cache缺失、 TLB缺失、缺页）会引起流水线阻塞 Pipeline.97 2021年 2月 20日星期六 第三讲 高级流水线技术 高性能流水线 - 指令级并行 (ILP)技术 超流水线 多发射流水线 - 静态多发射（ VLIW处理器 +编译器静态调度） - 动态多发射（超标量处理器 +动态流水线调度） 静态多发射（ VLIW-超长指令字） 编译器静态推测完成“指令打包”和“冒险处理” MIPS 2-发射流水线数据通路 循环展开指令调度 IA-64的 EPIC技术 动态多发射 动态多发射流水线的通用模型 动态多发射流水线的执行模式 - 按序发射、按序完成 - 按序发射、无序完成 - 无序发射、无序完成 Pentium 4 动态多发射流水线 - 超流水、超标量、动态调度、无序发射、无序完成 Pipeline.98 2021年 2月 20日星期六 提高性能措施 实现指令级并行 流水线实现了指令流内部的并行，这种并行称为指令级并行（ ILP） 有两种指令级并行策略 超流水线（ Super- pipelining） - 级数更多的流水线 - 理想情况下，流水线的加速比与流水段的数目成正比 （即：理想情况下，流水段越多，时钟周期越短，指令吞吐率越高） 但是，它是有极限的！可以怎样突破极限呢？ 多发射流水线（ Multiple issue pipelining ） - 多条指令 (如整数运算、浮点运算、装入 /存储等 ) 同时启动并独立运行 - 前提： 有多个执行部件。如：定点、浮点、乘 /除、取数 /存数部件等 - 结果： 能达到小于 1的 CPI，定义 CPI的倒数为 IPC （例如：四路多发射流水线的理想 IPC为 4） - 需要实现以下两个主要任务 指令打包：分析每个周期发射多少条？哪些指令可以同时发射？ 冒险处理：由编译器静态调整指令或在运行时由硬件处理 - 实现上述两个主要任务的基础 推测技术 - 两种实现方法 静态多发射 ：由编译器在编译时静态完成指令打包或冒险处理 动态多发射 ：由硬件在执行时动态完成指令打包或冒险处理 CPI=？ CPI=1 Pipeline.99 2021年 2月 20日星期六 实现多发射技术的基础 推测 推测技术：由编译器或处理器猜测指令执行结果，并以此来调整指令执行顺序， 使指令的执行能达到最大可能的并行 指令打包的决策依赖于“推测”的结果 - 可根据指令间的相关性来进行推测 与前面指令不相关的指令可以提前执行 - 可对分支指令进行推测 可提前执行分支目标处的指令 - 预测仅是“猜测”，有可能推测错误，故需有推测错误检测和回滚机制 - 推测错误时，会增加额外开销 有“软件推测”和“硬件推测”两种 - 软件推测：编译器通过推测来静态重排指令（一定要正确！） - 硬件推测：处理器在运行时通过推测来动态调度指令 BACK Pipeline.100 2021年 2月 20日星期六 静态多发射处理器 由编译器在编译时， 进行相关性分析 和 静态分支预测， 以静态完成“指令打包”或“冒险处 理” 指令打包（将同时发射的多条指令合并到一个长指令中） - 将一个周期内发射的多个指令看成一条多个操作的长指令，称为一个 发射包” - “静态多发射”最初被称为“超长指令字”（ VLIW-Very Long Instruction Word），采用这种技术的处理器被称为 VLIW处理器 - 在同一个周期内发射的指令类型是受限制的 （例如，只能是一条 ALU指令 /分支指令、一条 Load/Store指令） - IA-64采用这种方法， Intel称其为 EPIC（ Explicitly Parallel Instruction Computer显式并行指令计算机） 冒险处理（主要是数据冒险和控制冒险） - 做法 1： 完全由编译器通过代码调度和插入 nop指令来消除所有冒险，无需硬件 实现冒险检测和流水线阻塞 - 做法 2： 由编译器通过静态分支预测和代码调度来消除同时发射指令间内部依赖 ，由硬件检测数据冒险并进行流水线阻塞 即：保证打包指令内部不会出现冒险！ Pipeline.101 2021年 2月 20日星期六 静态多发射处理器实例 实例： MIPS ISA 指令集的静态多发射 -2发射处理器 要使原来的 MIPS处理器能够同时处理两条流水线，数据通路需要做哪些改进？ 1. 同时要能取并译码两条指令，怎么办？ 将两条指令打包成 64位长指令，前面为 ALU/Branch，后面为 lw/sw 没有配对指令时，就用 nop指令代替 将 64位长指令中的两个操作码同时送到控制器（指令译码器）进行译码 2. 两条指令同时要读两个寄 存器（和 sw配对时）或写寄存器（和 lw配对时） ，怎么办？ 增加一个读口和一个写口 3. 两条指令同时 要使用 ALU进行运算 ，怎么办？ 增加一个 ALU（包括 2组输入总线和 1组输出总线） BACK Pipeline.102 2021年 2月 20日星期六 2发射流水线数据通路（蓝色是增加部分） 同时需为 ALU和 Store操作读两 个寄存器，同时需为 ALU运算 和 Load结果写一个寄存器 需增加额外加法器或 ALU ALU/分支指令进行 ALU运算时， Load/Store指令要计算地址 指令成对放在 64位对齐内 存区域，前面是 ALU/分支 指令。如果不能成对，则 用 nop指令代替缺失指令， 每次取两条指令，同时对 两条指令译码 控制器和控制信号会要求数据通路怎样改呢？ 流水段寄存器要增宽，控制信号分别传送。 Pipeline.103 2021年 2月 20日星期六 2发射流水线的特点 优点：潜在性能将提高大约 2倍 (实际上达不到！ ) 缺点： 为消除结构冒险，需增加额外部件 增加潜在的由数据冒险和控制冒险导致的性能损失 - 例 1：对于 Load-use数据冒险 单发射流水线： 只有一条指令延迟 2发射流水线： 有一个周期（ 2条指令）延迟 - 例 2：对于 ALU-Load/Store数据冒险 单发射流水线： 可用“转发”技术使 ALU结果直接转发到 Load/Store指 令的 EXE阶段 2发射流水线： 两条指令同时进行， ALU的结果不能直接转发，因而不能 提供给与其配对的 Load/Store指令使用，只能延迟一个周期 为了更有效地利用多发射处理器的并行性，必须有更强大的编译器， 能够充分消除指令间的依赖关系，使指令序列达到最大的并行性！ Pipeline.104 2021年 2月 20日星期六 例： 2发射 MIPS指令调度 以下是一个循环代码段 Loop: lw $t0, 0($s1) addu $t0, $t0, $s2 sw $t0, 0($s1) addi $s1, $s1, -4 bne $s1, $zero, Loop (能看出这段程序的功能吗？ ) 为了能在 2发射 MIPS流水线中有效执行，该怎样重新排列指令 调度方案如下： 没有指令配对时，用 nop指令代替 一个循环内，五条指令在四个时钟内完成，实际 CPI为 0.8，即 : IPC=1.25 在循环中访问数组的更好的调度技术是“循环展开” 前三条和后两条各具有相关性 可把第四条指令调到第一条后面 sw指令是否有问题？怎么办？ 循环内进行的是数组访问！ 冒险！同时对同一个寄存器读，且 读后要写，取决于寄存器如何设计 能否把 addi和 lw配成一对？ $s1被减 4，故 sw指令偏移改为 4 Pipeline.105 2021年 2月 20日星期六 用“循环展开”技术进行指令调度 基本思想：展开循环体，生成多个副本，在展开的指令中统筹调度 上例采用“循环展开”后的指令序列是什么？ 为简化起见，假定循环执行次数是 4的倍数 “循环展开” 4次后循环内每条指令（ lw, addu, sw，与数组访问相关 ）有 4条 再加上 1条 addi和 1条 bne, 共 14条指令 指令最佳调度序列如下： 14条指令用了 8个时钟， CPI达到 8/14=0.57。 需要用到 “重命名寄存器”技术 ，多用了三个临时寄存器 $t1,$t2,$t3，消除了 名字依赖关系（非真实依赖，只是寄存器名相同而已） 代价是什么？ 多用了三个临时寄存器，并增加了代码大小（存储空间变大） 为何第一条指令将 $s1减 16？与 $t0关联的指令偏移为何不同？ 好处：充分利用并行，并消除部分循环分支！ Pipeline.106 2021年 2月 20日星期六 循环展开后的偏移量 第一条指令将 $s1减 16，使指令执行后， $s1的值变成了循环结束时 $s1的值 所以循环体内各数组元素的访问指令的偏移量依次为： 16 - 数组元素 1， 12 - 数组元素 2 ， 8 - 数组元素 3， 4 - 数组元素 4 $s1 $s1-16 数组元素 1 数组元素 2 数组元素 3 数组元素 4 为什么第一个周期中的 lw指令的偏移量为 0? 因为第一个周期中的 lw指令进行地址计算时， addi指令的执行结果还没有写到 $s1中，所以， 此时 $s1中还是原来的值 ? 为什么第一条 addu指令不放在第二周期 ? 为了避免 load-use数据冒险！ 当循环次数不是 4的倍数时，这样做就有问题！ 可见：编译器和机器结构密切相关！系统程序员必须非常 了解机器结构！编译器的好坏直接影响机器的性能！ Pipeline.107 2021年 2月 20日星期六 实例： Intel IA-64架构 IA-64类似于 64位 MIPS架构，是 Register-Register型的 RISC风格指令集 但有独特性：要求编译器显式地给出指令级的并行性， Intel称其为 EPIC Explicitly Parallel Instruction Computer显式并行指令计算机 与 MIPS-64架构的区别 更多寄存器： 128个整数、 128个浮点数、 8个专用分支、 64个 1位谓词 支持 寄存器窗口重叠技术 同时发射的指令组织在指令包（ bundle）中 引入特殊的谓词化技术，以支持推测执行和消除分支，提高指令级并行度 EPIC的实现技术 指令组（ Instruction Group）：相互间没有寄存器级数据依赖的指令序列 - 指令组长度任意，用“停止标记”在指令组之间明显标识 - 指令组内部的所有指令可并行执行，只要有足够硬件且无内存操作依赖 指令包：同时发射的指令重新编码并形成指令包 - 长度为 128，由 5位长的模板字段、三个 41位长的指令组成 - 模板字段对应于以下五类功能部件中的三条指令 整数 ALU、非整数 ALU（移位和多媒体）、访存、浮点、分支 谓词化 ：将指令的执行与谓词相关联，而不是与分支指令关联 Intel IA-64是 ?-发射流水线？ 3-发射流水线！ BACK Pipeline.108 2021年 2月 20日星期六 RISC的通用寄存器 RISC机采用大量寄存器 其目的： 减少程序访问存储器的次数 RISC机寄存器的组织方式有两种： 重叠寄存器窗口技术 ORW（硬件方法） - 执行过程调用和返回时，利用寄存器组而不是存储器来完成参数传递 - 通过重叠窗口技术，使得不再需要保存和恢复寄存器内容 - 可大大提高了程序执行的速度 优化寄存器分配技术（软件方法） - 规定一套寄存器分配算法 - 通过编译程序的优化处理来充分利用寄存器资源 - 编译器为那些在一定的时间内使用最多的变量分配寄存器 BACK Pipeline.109 2021年 2月 20日星期六 重叠寄存器窗口技术（ Overlapped Register Window ） 用于保存 局部数据 与调用自己的 父过程的输出 寄存器重叠 与被调用子 过程的输入 寄存器重叠 A调用 B时，由于各自使用不同的局部寄存器，所以 不需保存现场 A过程的输出寄存器可直接把参数送给 B 从 B返回时， B将返回结果送到其输入寄存器， A可 直接得到 B返回的结果 寄存器分为两类： 全局寄存器：所有过程共享 窗口寄存器：用于过程调用 BACK Pipeline.110 2021年 2月 20日星期六 Intel IA-64架构的谓词和推测执行技术 谓词和谓词寄存器 分支指令中的条件称为谓词 每个谓词与一个谓词寄存器相关联 每条指令都可与最后 6位标识（ 64个一位谓词，故谓词寄存器的标号用 6 位表示）的谓词寄存器相关联，反映条件是否满足 可消除循环内 if-then-else分支（循环分支可由循环展开部分消除） 例： if (p) Statement1 else Statement2 被编译成： (p) Statement1 (p) Statement2 括号中的条件为 1时，执行后面的代码，否则，转化为 nop指令 条件分支指令被转化为由谓词寄存器关联的指令，消除了分支 通过谓词寄存器可实现指令的推测执行 IA-64是采用静态多发射机制的最复杂指令集，对编译器的要求极高 BACK Pipeline.111 2021年 2月 20日星期六 动态多发射处理器 由硬件在执行时动态完成指令打包或冒险处理 通常被称为超标量处理器（ Superscalar） 在一个周期内执行一条以上指令 与 VLIW处理器的不同点： VLIW处理器： 编译结果与机器结构密切相关，结构有差异的机器上要重新编译 超标量处理器： 编译器仅进行指令顺序调整，但不进行指令打包，由硬件根据 机器的结构来决定一个周期发射哪几条指令。因此，编译后的代码能够被不同 结构的机器正确执行 多数超标量处理器都结合动态流水线调度 （ Dynamic pipeline scheduling）技术 通过指令相关性检测和动态分支预测等手段，投机性地不按指令顺序执行，当 发生流水线阻塞时，可以到后面找指令来执行 举例说明动态流水线调度技术： sub指令可以提前执行，不需等 lw和 addu指令执行完 如果不将 sub调到前面，可能要等很长时间（ lw指令 的访存操作耗时较长！），从而影响 slti指令的执行 左边指令序列中，哪条指令可以提前执行？ 最佳的方案是什么？ SKIP Pipeline.112 2021年 2月 20日星期六 动态流水线调度的通用模型 动态流水线的一个重要的思想：在等待解决阻塞时，到后面找指令提前执行！ 动态流水线的通用模型： 一个指令预取和译码单元： 有序发射 多个并列执行的功能单元： 乱序执行 一个提交单元： 有序提交 每个功能单元有各自的 保留站 用于保存操作数和操作命令 功能单元 一旦完成 ，则将结果同时送 其他等待该结果的 保留站和提交单元 提交单元 缓存所有完成的指令结果，直 到该结果能安全写回到寄存器或存储器 ， 称为 Reorder Buffer 指令的结果也可 在 Reorder Buffer中被“转发” Pipeline.113 2021年 2月 20日星期六 功能单元的性能 功能：用来执行特定类型的操作 性能：每个功能单元具有基本的操作性能，用两个周期数来刻画 执行周期（ Latency）：完成特定操作所花的周期数 发射时间（ Issue Time）：连续、独立操作之间的最短周期数 以下是 Pentium III 算术功能部件的性能 从上述图中看出，哪些功能部件是流水化的？哪些是非流水化的？ 整数加、整数乘、浮点加、装入、存储这五种部件是流水化的 浮点乘部件是部分流水化 整数除和浮点除是完全没有流水化 CPU设计的一个原则：有限的芯片空间应该在各功能部件之间进行平衡！尽量让大多数资源用 于最关键的操作 （对大量基准程序进行评估） 从上述图中能否看出：哪些是最重要的操作？哪些是不常用的？ 整数加法和乘法、浮点数加法和乘法是重要的操作 除法相对来说不太常用，而且本身难以实现流水线 Pipeline.114 2021年 2月 20日星期六 动态流水线的几种执行模式 根据动态流水线指令发射和完成顺序，可分为三种执行模式： 按序发射按序完成（ Pentium） 按序发射无序完成（ Pentium II和 Pentium III） 无序发射无序完成（ Pentium 4） 保留站：存放操作数和操作命令 最保守的方案是顺序完成，好处： (1) 简化异常检测和异常处理 (2) 能在被推测指令完成前得知推测 结果的正确性 指令发射时，其操作数可能在寄存器堆或 ROB中，可 立即复制到保留站中，故源操作数寄存器可被覆盖 若操作数不在寄存器堆或 ROB中，则一定在某个时刻 被一个功能单元计算出来，硬件将定位该功能单元，并 将结果从旁路寄存器复制到保留站 ReOrder Buffer 重排序缓冲 : 用于保存已完成的指令结果， 等待 在可能时 写回寄存器堆 写回条件： 与前面的所 有指令结果不相关、并 预测正确 SKIP Pipeline.115 2021年 2月 20日星期六 按序发射按序完成 举例： 2发射超标量，分为取指（ F）、译码（ D）、执行（ E）、写回（ W）。 F 、 D、 W段在一个时钟周期内完成（可同时有两条指令在这三个阶段）； E段有三 个执行部件： Load/Store部件完成数据 Cache访问需要 1个时钟，整数 ALU完成 简单 ALU操作需 2个时钟，整数乘法器完成乘法运算需要 3个时钟。执行部件采用 流水化方式。 按序发射按序完成的过程如下： i1 lw $1, A i2 add $2, $2, $1 i3 add $3, $3, $4 i4 mul $4, $5, $4 i5 lw $6, B i6 mul $6, $6, $7 为了按序完成，虽然 i5在时钟 6已经完成， 但一直推迟到 i4写回后的第 9时钟才写回 译码段 执行段 写回段 i1 i2 2 时钟 3 4 5 6 7 8 9 10 i2 ALU L/S Mul i1 i2 i2 i3 i3 i4 i4 i4 i3 i4 i5 i6 i5 i6 i6 i6 i5 i5 i1 i2 i3 i4 i5 i6 i6 i1、 i2间 RAW; i5、 i6间 RAW和 WAW，需 阻塞一个时钟周期，并一定要按序完成！ 指令被阻塞在“译码器” 中 如果还有一条乘法指令，则最多可有三条乘法指令同时在执行 BACK Pipeline.116 2021年 2月 20日星期六 按序发射无序完成 举例： 2发射超标量，分为取指（ F）、译码（ D）、执行（ E）、写回（ W）。 F 、 D、 W段在一个时钟周期内完成（可同时有两条指令在这三个阶段）； E段有三 个执行部件： Load/Store部件完成数据 Cache访问需要 1个时钟，整数 ALU完成 简单 ALU操作只需 2个时钟，整数乘法器完成乘法运算需要 3个时钟。执行部件采 用流水化方式。 按序发射无序完成的过程如下： i1 lw $1, A i2 add $2, $2, $1 i3 add $3, $3, $4 i4 mul $4, $5, $4 i5 lw $6, B i6 mul $6, $6, $7 译码段 执行段 写回段 i1 i2 2 时钟 3 4 5 6 7 8 9 10 i2 ALU L/S Mul i1 i2 i2 i3 i3 i4 i4 i4 i3 i4 i5 i6 i5 i6 i6 i6 i5 i5 i1 i2 i3 i4 i5 i6 i6 无序完成时， 因为 i5在时钟 6已经完成，和 i3、 i4没有相关性，可以不需要等 i3、 i4写 回后再写回，所以可先于 i4完成。 BACK Pipeline.117 2021年 2月 20日星期六 无序发射无序完成 举例： 2发射超标量，分为取指（ F）、译码（ D）、执行（ E）、写回（ W）。 F 、 D、 W段在一个时钟周期内完成（可同时有两条指令在这三个阶段）； E段有三 个执行部件： Load/Store部件完成数据 Cache访问需要 1个时钟，整数 ALU完成 简单 ALU操作只需 2个时钟，整数乘法器完成乘法运算需要 3个时钟。执行部件采 用流水化方式。 无序发射无序完成的过程如下： i1 lw $1, A i2 add $2,