我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:2019跑狗图高清彩图 > 指令级并行 >

第章指令级并行精要

归档日期:07-27       文本归类:指令级并行      文章编辑:爱尚语录

  4.1指令级并行 –理想流水线的CPI加上各类停顿的时钟周期数: CPI 流水线 CPI理想 停顿结构冲突 停顿数据冲突 停顿控制冲突 理想CPI是衡量流水线最高性能的一个指标。–IPC:Instructions Per Cycle (每个时钟周期完成的指令条数) 2016-4-28 基本程序块:一段除了入口和出口以外不包含其他分支的线性代码段。 –程序平均每5~7条指令就会有一个分支。 循环级并行:使一个循环中的不同循环体 并行执行。 是指令级并行研究的重点之一2016-4-28 流水线冲突是指对于具体的流水线来说,由于相关的存在,使得指令流中的下一条 指令不能在指定的时钟周期执行。 流水线冲突有三种类型:结构冲突、数 据冲突、控制冲突 相关是程序固有的一种属性,它反映了程序中指令之间的相互依赖关系。 具体的一次相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿,则是流 水线 对于正确地执行程序来说,必须保持的最关键的两个属性是:数据流和异常行为。 保持异常行为是指:无论怎么改变指令的执行顺序,都不能改变程序中异常的发生情况。 即原来程序中是怎么发生的,改变执行顺序后还是怎么发生。 弱化为:指令执行顺序的改变不能导致程序中发生新的异常。 如果我们能做到保持程序的数据相关和控制相关,就能保持程序的数据流和异常行为。 2016-4-28 10 2016-4-2811 2016-4-2812 利用状态记录控制器(或记分牌ScoreBoard)在程 序执行过程中,对流水线中的各个功能部件的工 作状态、进入流水线中的各条指令的工作状态、 指令所使用的寄存器情况等进行集中的统一记录 和调度。 集中式动态调度依靠硬件在程序运行过程中对可能出现的相关情况加以检测,从而保证流水线中 的各个功能部件能最大限度地重叠工作。 集中式动态调度常用于解决乱序方式流水线 ID整数部分 浮点加 浮点乘 浮点除 RF 记录控制器 EX MEM WB 指令 控制/状态 控制/状态 集中式动态调度 寄存器堆 2016-4-28 14 尽可能早地执行无关指令,在没有数据相关的情况下,达到每个时钟周期执行一条指令。 记分牌电路全盘负责指令的流出、执行以及相关检测。 要发挥指令乱序执行的好处,必须有多条指令同时处于执行阶段,这就要求有多个功能部件或功 能部件流水化或两者兼有。 一般,采用多个功能部件。2016-4-28 15 4个浮点部件、5个存储器访问部件、7个整数操作部件。 对于DLX,记分牌技术主要用于浮点部件,因为其他部件的操作延迟很小,可以不计。 DLX的部件是:1个浮点乘法器、1个浮点加法器、1个浮点除法部件和1个整数部件,其中整数部件 用于处理所有的存储器访问、分支处理和整数操 RISC的超标量机也可以采用类似的方法。2016-4-28 16 2016-4-2817 DLX 将每条指令的执行按4步处理(主要考虑浮点等功能的操作,忽略MEM): 1.指令流出(Issue,记为IS):如果指令所需的功 能部件空闲,并且其他正在执行的指令使用的目 的寄存器与该指令的不同,记分牌就向相应的功 能部件发射该指令,并改变记分牌内部的数据结 构。这一步代替了ID的一部分。 解决了结构相关和WAW相关。2016-4-28 18 2.读操作数(ReadOperand, 记RO):如果前面 已流出的正在运行的指令不对本指令的源操作数 寄存器进行写操作,或者一个正在工作的功能部 件已经完成了对这个寄存器的写操作,那么此操 作数有效。整个检测工作由记分牌完成。当操作 数有效后,记分牌告诉功能部件读操作数并开始 执行。 解决RAW相关,代替ID的一部分工作。(与1.合成,就是ID的工作) 2016-4-28 19 执行(Execution,记EX):取到操作数后就开始执行指令。 这一步相当于DLX流水线的EXE阶段,并且在流水线中要占用多个时钟周期。 写结果(WriteResult,记WR):记分牌知道 指令执行完毕后,如果目标寄存器空闲,就将结 果写到该目标寄存器中,然后释放本指令使用的 所有资源。 此步可解决WAR相关。这一步代替了流水线/91中,采用公共数据总线 CDB来实现某些相关专用通路连接,并通过给每 个浮点数寄存器FLR设置一个“忙”标志来判别指 令间所用的数据是否发生数据相关,只要某些FLR 正在使用,就将“忙”位置“1”表示存在数据相 关,一旦使用完成,就将“忙”位置成“0”。 以下面的一段程序为例说明Tomasulo算法。 LOADF1, k+1:FADDF1, F2 k+2:FMUL F1, F3 k+3:STORE F1, 2016-4-2822 存储器总线 指令分析部件 CDB 先行读数站控制 先行操作站 F7 (FLB)(FLOS) F6 (FLR) F3FLB1 F2 F1 10/8控制 后行写数站F0 A312 控制M2 控制A2 11 M1 10(F3) A1 10 (FLB1) (F2) 乘/除法器 加法器 级流水线 处理机的浮点执行部件 控制总线)加法器和乘法器分别设置了3个和2个保存站,减小了资源使用冲突的机会。 (2)调度算法使用保存站,通过对寄存器重新命名(改写站号)自然地消除了WAR和WAW相关 的可能性。 (3)通过对FLR寄存器忙位状态的判别,来检测是否存在RAW相关。 (4)借助CDB公共数据总线作为专用相关通路,将有关数据直接送到所有需要它的功能部件。 2016-4-28 24 从指令部件来 浮点寄存器FP store缓冲器 load缓冲器 地址部件 load/store操作 浮点操作 操作数总线 操作总线 数据 存储部件浮点加法器 浮点乘法器 标识标识 2016-4-28 25 –保留站(reservation station) 每个保留站中保存一条已经流出并等待到本功能部 件执行的指令(相关信息)。包括:操作码、操 作数以及用于检测和解决冲突的信息。 –在一条指令流出到保留站的时候,如果该指令 的源操作数已经在寄存器中就绪,则将之取到 该保留站中。 –如果操作数还没有计算出来,则在该保留站中 记录将产生这个操作数的保留站的标识。 •浮点加法器有3个保留站:ADD1,ADD2,ADD3 •浮点乘法器有两个保留站:MULT1,MULT2 每个保留站都有一个标识字段,唯一地标识了该保留站。 2016-4-28 26 –公共数据总线CDB (一条重要的数据通路) •所有功能部件的计算结果都是送到CDB上,由 它把这些结果直接送到(播送到)各个需要 该结果的地方。 •在具有多个执行部件且采用多流出(即每个 时钟周期流出多条指令)的流水线中,需要 采用多条CDB。 2016-4-28 27 –load缓冲器和store缓冲器 存放读/写存储器的数据或地址•load缓冲器的作用有3个: –存放用于计算有效地址的分量; –记录正在进行的load访存,等待存储器的 响应; –保存已经完成了的load的结果(即从存储 器取来的数据),等待CDB传输。 2016-4-28 28 •store缓冲器的作用有3个: –存放用于计算有效地址的分量; –保存正在进行的store访存的目标地址, 该store正在等待存储数据的到达; –保存该store的地址和数据,直到存储部 件接收。 2016-4-28 29 –浮点寄存器FP 它们通过一对总线连接到功能部件,并通过CDB连接到store缓冲器。 浮点乘法器完成乘法和除法操作2016-4-28 30 在Tomasulo算法中,寄存器换名是通过保留站和流 出逻辑来共同完成的。 –当指令流出时,如果其操作数还没有计算出来, 则将该指令中相应的寄存器号换名为将产生这 个操作数的保留站的标识。 –指令流出到保留站后,其操作数寄存器号或者 换成了数据本身(如果该数据已经就绪),或 者换成了保留站的标识,不再与寄存器有关系。 2016-4-28 31 Tomasulo算法具有以下两个特点: –冲突检测和指令执行控制是分布的。 每个功能部件的保留站中的信息决定了什 么时候 指令可以在该功能部件开始执行。 –计算结果通过CDB直接从产生它的保留站传送 到所有需要它的功能部件,而不用经过寄存器。 2016-4-28 32 Tomasulo使用Tomasulo算法的流水线段: 流出:从指令队列的头部取一条指令。•如果该指令的操作所要求的保留站有空闲的, 就把该指令送到该保留站(设为r)。 –如果其操作数在寄存器中已经就绪,就将 这些操作数送入保留站r。 2016-4-28 33 –如果其操作数还没有就绪,就把将产生该 操作数的保留站的标识送入保留站r。 –一旦被记录的保留站完成计算,它将直接 把数据送给保留站r。 (寄存器换名和对操作数进行缓冲,消除 WAR冲突) 完成对目标寄存器的预约工作(消除了WAW冲突) 如果没有空闲的保留站,指令就不能流出。(发生了结构冲突) 2016-4-28 34 当两个操作数都就绪后,本保留站就用相应的功能部件开始执行指令规定的操作。 •load和store指令的执行需要两个步骤: –计算有效地址(要等到基地址寄存器就绪) –把有效地址放入load或store缓冲器 写结果•功能部件计算完毕后,就将计算结果放到CDB上, 所有等待该计算结果的寄存器和保留站(包括 store缓冲器)都同时从CDB上获得所需要的数据。 2016-4-28 35 –Op:要对源操作数进行的操作。 –Qj,Qk:将产生源操作数的保留站号。 •等于0表示操作数已经就绪且在Vj或Vk中,或 者不需要操作数。 –Vj,Vk:源操作数的值。 •对于每一个操作数来说,V或Q字段只有一个 有效。 •对于load来说,Vk字段用于保存偏移量。 2016-4-28 36 –Busy:为“yes”表示本保留站或缓冲单元 –A:仅load和store缓冲器有该字段。开始是存放指令中的立即数字段,地址计算后存放有效 地址。 –Qi:寄存器状态表。 •每个寄存器在该表中有对应的一项,用于存 放将把结果写入该寄存器的保留站的站号。 •为0表示当前没有正在执行的指令要写入该寄 存器,也即该寄存器中的内容就绪。 2016-4-28 37 *Tomasulo算法举例 例4.1 对于下述指令序列,给出当第一条指令完成并写入结 果时,Tomasulo算法所用的各信息表中的内容。 L.D F6,34(R2) L.D F2,45(R3) MUL.D F0,F2,F4 SUB.D F8,F2,F6 DIV.D F10,F0,F6 ADD.D F6,F8,F2 2016-4-28 38 指令状态表流出 执行 写结果 L.D F6 L.DF2 MUL.DF0 SUB.DF8 DIV.DF10 ADD.DF6 2016-4-2839 名称 保留站 Load1 Load2 Add1 Add2 Add3 Mult1 Mult2 Busy yesyes yes yesyes Op LD SUB ADD MUL DIV Vj Vk Mem[34+Regs[R2]] Reg[F4] Mem[34+Regs[R2]] Qj Load2 Add1 Load2 Mult1 Qk Load2 45+Regs[R3]寄存器状态表 F0 F2 F4 F6 F8 F10 F30Qi Mult1 Load2 Add2 Add1 Mult2 2016-4-2840 例4.2 对于例4.1中的代码,假设各种操作的延迟为: load:1个时钟周期 加法:2个时钟周期 乘法:10个时钟周期 除法:40个时钟周期 给出MUL.D指令准备写结果时各状态表的内容。 2016-4-2841 指令状态表流出 执行 写结果 L.D F6 L.DF2 MUL.DF0 SUB.DF8 DIV.DF10, F0, F6 ADD.DF6 2016-4-2842 具体算法(略,P123)名称 保留站 Load1 Load2 Add1 Add2 Add3 Mult1 Mult2 Busy yesyes yes yesyes Op Mul DIV Vj Mem[45+Regs[R3]] Vk Reg[F4] Mem[34+Regs[R2]] Qj Mult1 Qk 寄存器状态表F0 F2 F4 F6 F8 F10 F30Qi Mult1 Mult2 2016-4-2843 4.3.1BHT (分支历史表,略) 4.3.2转移目标缓冲器 将过去发生过的转移指令地址以及它的转移目标地址存入一个转移目标缓冲器(BTB)中,利用转 移指令地址作为检测标志,以便尽早生成转移目 标地址。 2016-4-28 44 预取指令的PC 查找预测PC值 转移发生 预测PC值应 送入PC中 预测转移发生或不发生 转移不发生,按正常 顺序进行 (2位状态位) 2016-4-28 45 方法一:在指令Cache中记录转移历史信息在指令Cache中专门设置一个字段,称为“转移 历史表”。在执行转移指令时,把转移成功或不 成功的信息记录在这个“转移历史表”中。可以 只用一个二进制位来记录最近一次转移是否成功 的信息,也可以用多个二进制位来记录最近几次 转移是否成功的信息。当下次再执行到这条指令 时,转移预测逻辑根据“转移历史表”中记录的 信息预测转移成功或不成功。 2016-4-28 46 方法二,转移目标地址缓冲栈用一个小容量的高速缓冲栈保存最近执行的k条 转移指令的“转移历史表”和转移目标地址。 “转移指令地址”字段采用全相联方式访问。当 程序中执行到一条转移指令时,把当前指令地址 与转移目标缓冲栈中的所有转移指令地址进行比 较;如果发现有相等的,则根据同一行中的“转 移历史表”所记录的历史信息预测本次转移的方 向,同时用转移目标地址预取指令。在实际转移 条件形成之后,可以根据某一种规则修改“转移 历史表”。 2016-4-28 47 k-1转移指令地址 转移历史表 转移目标地址 2016-4-28 48 方法三,转移目标指令缓冲栈当转移指令在指令分析部件中译码时,转移不 成功方向上的指令已经被预取到先行指令缓冲栈 中,或者已经存放在指令Cache中,为了能够在转 移成功方向上也预取一部分指令,可以把转移目 标地址部分改为存放转移目标地址之后的n条指令。 设置转移目标指令缓冲栈的转移预测方法的工作 原理,预测转移方向的规则和修改“转移历史表” 的方法与方法二相同。 2016-4-28 49 k-1,n-1 转移指令地址 转移历史表 转移目标地址之后的n 条指令 2016-4-28 50 4.3.3 基于硬件的前瞻执行 前瞻执行(speculation)的基本思想: 对分支指令的结果进行猜测,并假设 这个猜测总是对的,然后按这个猜测结果 继续取、流出和执行后续的指令。只是执 行指令的结果不是写回到寄存器或存储器, 而是放到一个称为ROB(ReOrder Buffer) 的缓冲器中。等到相应的指令得到“确认” (commit)(即确实是应该执行的)之后, 才将结果写入寄存器或存储器。 2016-4-28 51 把Tomasulo算法的写结果和指令完成加以区分,分成两个不同的段: 写结果,指令确认 2016-4-28 52 通过CDB在指令之间传送结果,供需要用到这些结果的指令使用。 指令确认段在分支指令的结果出来后,对相应指令的前瞻执 行给予确认。 如果前面所做的猜测是对的,把在ROB中的结果写到寄存器或存储器。 如果发现前面对分支结果的猜测是错误的,那就不予以确认,并从那条分支指令的另一条路径开始重新执 2016-4-2853 实现前瞻的关键思想:允许指令乱序执行,但必须顺序确认。 支持前瞻执行的浮点部件的结构2016-4-28 54 从指令部件来 浮点寄存器FP 地址部件 load/store操作 浮点操作 操作数总线 操作总线 store数据 存储部件浮点加法器 浮点乘法器 ROB数据 寄存器号 loadstore地址 load数据2016-4-28 55 指令类型指出该指令是分支指令、store指令或寄存器操作指令。 目标地址给出指令执行结果应写入的目标寄存器号(如果是 load和ALU指令)或存储器单元的地址(如果是store指 数据值字段用来保存指令前瞻执行的结果,直到指令得到确认。 就绪字段指出指令是否已经完成执行并且数据已就绪。 2016-4-2856 如果有空闲的保留站(设为r)且有空闲的ROB项(设为b),就流出该指令,并把相应的信息放入保留站r 和ROB项b。 如果保留站或ROB全满,便停止流出指令,直到它们都有空闲的项。 如果有操作数尚未就绪,就等待,并不断地监测CDB。(检测RAW冲突) 当两个操作数都已在保留站中就绪后,就可以执行该指令的操作。 2016-4-28 57 当结果产生后,将该结果连同本指令在流出段所分配到的ROB项的编号放到CDB上,经CDB写到ROB以及所 有等待该结果的保留站。 store指令在本阶段完成,其操作为:–如果要写入存储器的数据已经就绪,就把该数据 写入分配给该store指令的ROB项。 –否则,就监测CDB,直到那个数据在CDB上播送出 来,这时才将之写入分配给该store指令的ROB项。 2016-4-28 58 确认对分支指令、store指令以及其他指令的处理不同: •其他指令(除分支指令和store指令) 当该指令到达ROB队列的头部而且其结果 已经就绪时,就把该结果写入该指令的目标 寄存器,并从ROB中删除该指令。 2016-4-28 59 •store指令 处理与上面类似,只是它把结果写入存储 分支指令–当预测错误的分支指令到达ROB队列的头 部时,清空ROB,并从分支指令的另一个 分支重新开始执行。(错误的前瞻执行) –当预测正确的分支指令到达ROB队列的头 部时,该指令执行完毕。 2016-4-28 60 例4.3 假设浮点功能部件的延迟时间为:加法2个时钟周期, 乘法10个时钟周期,除法40个时钟周期。对于下面的代码 段,给出当指令MUL.D即将确认时的状态表内容。 L.D F6,34(R2) L.D F2,45(R3) MUL.D F0,F2,F4 SUB.D F8,F6,F2 DIV.D F10,F0,F6 ADD.D F6,F8,F2 2016-4-28 61 前瞻执行中MUL.D确认前,保留站和ROB 的状态 名称 保留站 Busy Op Vj Vk Qj Qk Dest MULMem[45+ Regs[R2]] Regs[F4] Mult2yes DIV Mem[34+Regs[R2]] 2016-4-2862 ROBBusy 指令 状态 目的 Value L.DF6, 34(R2) 确认 F6 Mem[34+Regs[R2]] L.DF2, 45(R3) 确认 F2 Mem[45+Regs[R3]] yesMUL.D F0, F2, F4 写结果 F0 #2Regs[F4] yesSUB.D F8, F6, F2 写结果 F8 yesDIV.D F10, F0, F6 执行 F10 yesADD.D F6,F8,F2 写结果 F6 字段浮点寄存器状态 F0 F2 F4 F6 F8 F10 F30ROB项编号 Busyyes yesyes yes 2016-4-2863 前瞻执行–通过ROB实现了指令的顺序完成。 主要缺点:所需的硬件太复杂。2016-4-28 64 //X浮点向量,S浮点标量编译成:(RISC型机器指令) 2016-4-28 65 loop:load f0, 0(r1); f0 Mem[r1+0] faddf0, f0, f1; f0 f0+f1 ,S预先存入f1 storef0, 0(r1); Mem[r1+0] f0 addir1, r1, r1r1+4 subiccr2, r2, bnezloop 下面以不同的处理技术讨论该循环及展开的执行时间。 2016-4-2866 IDEX Mem WB faddstall IDEX1 EX2 EX3 Mem WB storestall IDEX Mem WB IDEX Mem WB IDEX Mem WB bnezstall IDEX Mem loadstall ID一次循环时间为10个周期 时间槽n=1 冲突 冲突 2016-4-28 67 loop:load f0, 0(r1); subiccr2, r2, faddf0, f0, f1; addir1, r1, bnezloop storef0, -4(r1); 2016-4-2868 IDEX Mem WB IDEX Mem WB IDEX1 EX2 EX3 Mem WB IDEX Mem WB IDEX Mem IDEX Mem WB IDEX Mem WB 冲突,可通 过缓冲或 预取消除 一次循环为6, 7个周期 2016-4-28 69 有用的指令为load, fadd, store 展开有用的指令在循环体中增加有用指令 下列程序为循环体展开4次的情况2016-4-28 70 loop:load f0, 0(r1); faddf0, f0, f1; storef0, 0(r1); loadf0, 4(r1); faddf0, f0, f1; storef0, 4(r1); loadf0, 8(r1); faddf0, f0, f1; storef0, 8(r1); loadf0, 12(r1); faddf0, f0, f1; subiccr2, r2, storef0, 12(r1); bnezloop addir1, r1, 16; (3)时间: (3+2)*4-1+3=22个周期 平均单个循环时间为 22/4=5.5 个周期 应考虑RAW数据相关问题 2016-4-28 71 E1E2 E3 E1E2 E3 E1E2 E3 E1E2 E3 2016-4-2872 在编译时,重新分配寄存器(充分利用RISC多寄存器的特点,即静态分配),以消除循环体展开 而引起的数据相关。 重新分配寄存器后,上一个程序段改编为如下的程序段(见下页)。 4次展开的时间为3*4+3=15个周期 平均单个循环时间:15/4=3.75个周期2016-4-28 73 loop:load f0, 0(r1); loadf2, 4(r1); loadf4, 8(r1); loadf6, 12(r1); faddf0, f0, f1; faddf2, f2, f1; faddf4, f4, f1; faddf6, f6, f1; storef0, 0(r1); storef2, 4(r1); storef4, 8(r1); subiccr2, r2, storef6, 12(r1); bnezloop addir1, r1, 16; 2016-4-28 74 借用硬件流水线的技术,使得循环体程序段能够重复执行,即:使得循环体迭代重叠运行。 如下列的程序段,进入流水线部件,便可完成向量 流水处理。 2016-4-28 75 loadf0, 0(r1 loop:store f2 faddf2 f0,f1 subiccr2, r2, loadf0, 4(r1) bnezloop addir1, r1, 在数据安排上,预先空出最前面一、两个单元的数据空间。(多安排数据空间) 2016-4-28 76 E1E2 E3 E1E2 E3 2016-4-2877 流水中指令级并行性的开发属于细粒度并行性的开发。开发目标是使计算机的平均指令周期CPI能 够小于等于1,即在一个时钟周期中内能够完成多 条指令。 并行度(ILP--InstructionLevel Parallelism 不存在相关、可同时并行执行的指令数。2016-4-28 78 2016-4-28 79 2016-4-2880 三种主流处理机 超标量处理机 超流水线处理机 超标量超流水线处理机 以一台k 段流水线的普通标量处理机为基准 超标量处理机、超流水线处理机和超标量超流水线处理机的主要性能: 机器类型 段流水线标量处理机 超流水线处理机(m,n)度超标量 超流水线处理机 机器流水线 在处理机内设置多个可并行操作的功能部件和多条流水线,在一个时钟周期内启动多条指令进行 并行处理,使得CPI<1。 超级标量机主要是借助对硬件资源重复来实现空间的并行操作。 2016-4-28 82 发射:处理机从指令存储单元取得指令的过程 单发射:处理机在单时钟周期内只能取出一条指令供执行。 处理机只有一个IF 和ID部件,但可以有多个运 算部件。 多发射:处理机在单时钟周期内可取出多条指令供执行。 处理机必须设置多个IF 、ID 、WR等部件。 2016-4-28 83 单发射处理机的指令流水线时空图 IDEX WR 时钟周期 IDEX WR IDEX WR 指令 多发射处理机的指令流水线时空图 IDEX WR 时钟周期 IDEX WR IDEX WR IDEX WR IDEX WR IDEX WR IDEX WR IDEX WR IDEX WR 指令 2016-4-28 84 单发射处理机的指令流水线 取指令 指令译码 执行指令EX 写回结果

本文链接:http://f-taiken.net/zhilingjibingxing/496.html