您好、欢迎来到现金彩票网!
当前位置:双彩网 > 向量流水线 >

第3章流水线技术祥解ppt

发布时间:2019-05-27 07:10 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  * * 例:要进行向量运算 D=A×(B+C) 设向量长度≤64,且B和C已由存储器取至V0和V1,则完成运算的向量指令为: LD V3,A ;V3←A ADDV V2,V0,V1 ;V2←V0+V1 MULTV V4,V2,V3 ;V4←V2×V3 第一、二条指令因既无向量寄存器使用冲突,也无功能部件使用冲突,因而可并行执行。 第三条指令与第一、二条指令均存在先写后读相关冲突,因而可将第三条指令与第一、二条指令链接执行。 * * * * 设:把向量数据元素送往向量功能部件以及把结果存入向量寄存器需要1拍时间。 从存储器中把数据送入访存功能部件需要1 拍时间。 * * 若这三条指令全部用串行方法则所需时间为: [(1+6+1)+N-1)+[(1+6+1)+N-1]+[(1+7+1)+N-1)=3N+22拍 若前两条指令并行执行,第三条指令串行执行,则所需时间为: [(1+6+1)+N-1)+[(1+7+1)+N-1) =2N+15拍 采用并行和链接加速技术后,当被加工向量长度为N时,执行所需时间为: (1+6+1)+(1+7+1)+(N-1) =17+N-1 =N+16拍 建立时间 * * 实现链接的时间上的要求 ① 只有当前一指令的第一个结果分量送入结果向量寄存器的那一个时钟周期方可链接,若错过该时刻就无法进行链接,只有等前一向量指令全部执行完毕,释放向量寄存器资源后才能执行后面指令。 在上面的例子中,当一条向量指令的两个源操作数分别是两条先行指令的结果寄存器时,要求先行的两条指令产生运算结果的时间必须相等,即要求有关功能部件的延迟时间相等(如上例中的访存和浮点加功能部件延时均为6个时间单位)。 ②进行链接的向量指令的向量长度必须相等,否则就不可能链接。 * * 例:在CRAY-1机中,浮点功能部件中各功能段的执行时间为: 浮点加法:6拍;浮点乘法:7拍;求倒数:14拍;存储器存/取:6拍;启动功能部件: 1拍;打入结果: 1拍。 分析任务数为50时,下列指令段的完成时间: ① V0←存储器 ② V3←V1+V2 ③ V4←V0×V3 ④ V0←V4+V5 * * 分析: ①与②无功能和寄存器冲突,可并行。 ②与③先写后读数据相关,可以链接。 ④与②有功能冲突,必须在①与②执行完后,才能启动④,即④只能串行工作 。 ① V0←存储器 ② V3←V1+V2 ③ V4←V0×V3 ④ V0←V4+V5 执行时间: (1+6+1)+(1+7+1)+(50-1)+(1+6+1)+(50-1) =123拍 并行 链接 串行 * * 例:分析在CRAY-1机中,任务数为50时,下列指令段的完成时间。 ① V0←存储器 ② V1←V2+V3 ③ V6←V4×V5 分析:三条指令均无功能冲突,可采用全并行的方式,指令段的完成时间为: (1+7+1)+(50-1)=58拍 * * 例:分析在CRAY-1机中,任务数为50时,下列指令段的完成时间,设浮点求倒数的执行时间为14拍。 ① V2← V0×V1 ② V3←存储器 ③ V4←V2+V3 ④ V5←1/V4 分析: ①与②无功能和寄存器冲突,可并行。 ①与②节拍不一致, ③不能与①、②链接,只能串行执行。 ③与④先写后读数据相关,可以链接。 执行时间: (1+7+1)+(50-1)+ (1+6+1)+(1+14+1)+(50-1)=131拍 并行 链接 串行 * * 3.6.6.3 分段开采技术 1. 向量操作长度控制 ⑴ 实际程序中的向量长度往往并不与向量机的自然向量长度相同。 自然向量长度:向量寄存器型的向量机中,每个向量寄存器可存放的向量元素个数。 ⑵ 程序中一个具体的向量操作长度在编译时经常是未知的,因为在一个代码段中可能需要不同的向量长度。 * * 如果向量的长度大于向量寄存器的长度,则需要采用分段开采技术。 分段开采技术(向量循环) 当向量的长度大于向量寄存器的长度时,必须把长向量分成长度固定的段,然后循环分段处理,每一次循环只处理一个向量段。 分段开采由系统硬件和软件控制完成,对程序员是透明的。 * * 将向量长度按向量寄存器的长度(MVL)分段,分段后的向量长度即是每次向量操作的长度,它必须等于或小于向量寄存器长度。 向量长度小于向量寄存器长度时,均可放入向量寄存器。 向量长度大于向量寄存器长度时,需采用分段开采技术(向量循环)。 分段开采的实现 * * 向量寄存器 MVL 向量 向量长度 分段开采 * * 例: 设A和B是长度为N的向量,需要在Cray-1向量处理器上实现以下的循环操作: DO 10 I = 1,N 10 A(I)= 5.0 * B(I) + 1.0 * * 当N ≤64时 S1 ← 5.0 ;将常数5.0送入标量寄存器S1 S2 ← 1.0 ;将常数1.0送入标量寄存器S2 VL ← N ;在向量长度寄存器VL中设置向量长度N V0 ← B ;从存储器中将向量B读入向量寄存器V0 V1 ← S1 × V0 ;向量B中的每个元素分别和常数S1相乘 V2 ← S2 + V1 ;向量V1中的每个元素分别和常数S2相加 A ← V2 ;将计算结果从向量寄存器V2存入 存储器的向量A * * 当N >64时,需要进行分段开采 分段数K (循环次数) : 余数L: * * S1 ← 5.0 ;将常数5.0送入标量寄存器S1 S2 ← 1.0 ;将常数1.0送入标量寄存器S2 VL ← L ;在向量长度寄存器VL中设置向量长度L V0 ← B ;从存储器中将向量B[0..L-1],读入向量 ;寄存器V0 V1 ← S1×V0 ;向量B中的每个元素分别和常数S1相乘 V2 ← S2 + V1 ;向量V1中的每个元素分别和常数S2相加 A ← V2 ;将计算结果从向量寄存器V2存入存储器 ;的向量A[0..L-1] 处理余数部分, 计算L个元素 * * VL ← 64 For (I=0 to K-1) { V0 ← B ;从存储器中将向量B[L+I*64..L+I*64+63] ;读入向量寄存器V0 V1 ← S1 * V0 ;向量B中的每个元素分别和常数S1相乘 V2 ← S2 + V1 ;向量V1中的每个元素分别和常数S2相加 A ← V2 ;将计算结果V2存入存储器的向量 ; A[L+I*64… L+I*64+63] } 循环 K次, 分段 处理 * * 2. 向量访问步长 存储器是一维线性空间,当需要在其中存放二维或多维数组时,必须将其各元素映射到一维线性空间中。 以行为主的存储方式: 当按行进行元素访问时,要访问的元素的地址是相邻连续的。 当按列进行元素访问时,要访问的元素的地址是不连续的,需要采用向量跨步方式进行访问。 * * 1. 横向加工方式 横向加工方式:逐个求出结果向量的各个元素。 例:设A、B、C和D都是长度为N的向量,需进行向量运算 D=A×(B+C),采用横向加工方式时是按向量顺序计算的。 d1=a1×(b1+c1) d2=a2×(b2+c2) … dN=aN×(bN+cN) * * 处理过程:逐个求D中的N个分量 k←b1+c1 :其中k为暂存单元 d1←k×a1 k←b2+c2 d2←k×a2 …… 横向(水平)处理方式 * * 在每个向量元素的加乘运算中,都会发生数据相关。 当采用静态流水线次乘和加功能的转换。 共出现N次相关,2N次功能转换。 横向加工方式只适合于标量循环算法,不适合于向量流水处理。 * * 2.纵向(垂直)加工方式 纵向(垂直)加工方式:先对所有元素执行一种相同的运算,再对所有元素执行另一种相同的运算。 如上例中,先纵向加工所有B和C向量中元素对的相加操作,中间结果暂存到k1~kN中,然后再纵向加工所有对应元素的乘法操作。 * * 先算: k1=b1+c1 k2=b2+c2 … kN=bN+cN 再算: d1=a1×k1 d2=a2×k2 … dN=aN×kN 纵向(垂直)处理方式 * * 用向量指令形式表示为: K=B+C D=K×A 在两条向量指令间有1次数据相关, 1次流水线功能切换。 * * ⑴ 纵向加工方式可获得较高的吞吐率。 由于元素个数N不受限制,且需要有一个暂存中间向量K(由k1~kN个分量组成),所以纵向加工方式适合于存储器 — 存储器工作方式的向量机。 ⑵ 纵向加工方式对主存带宽要求高。 为减轻主存的负担,可在主存与流水部件之间设置缓冲器。 主存 先行读数缓冲器 后行写数缓冲器 流水功能部件 纵向加工方式的特点 * * 3.纵横向加工方式 纵横向加工方式: 将向量元素分成长度为某个固定值的若干组,每个组内采用纵向加工方式,组之间采用横向加工方式。 纵横向加工方式适合于采用寄存器 — 寄存器方式工作的向量机。 注意:因向量寄存器的长度有限,当向量长度超过向量寄存器可表示的最大限度n时,必须分组加以处理。 * * 设向量长度为N, s为组数,r为余数(余下的部分也作为一组处理) 则:N=s×n+r 其中n≤N,r<n,n、s、r均为正整数。 第一组计算: k1~n=b1~n+c1~n d1~n=a1~n×k1~n 第二组计算: kn+1~2n=bn+1~2n+cn+1~2n dn+1~2n=an+1~2n×kn+1~2n … 纵横(分组)处理方式 * * 每组内各有两条向量指令,各组内有一次数据相关,需2次流水功能切换,需n个中间向量寄存器单元。 采用纵横向加工方式,组内的元素计算均在寄存器中完成,可大大减少访存次数,降低了对主存带宽的要求,减少了因存储器冲突而引起的等待。提高了处理速度。 * * 美国Cray公司于1976年提供的巨型机产品。 运算速度每秒亿次浮点运算。 主频:80MHz 字长:64位 其速度高的原因之一是采用了层次结构的存储器系统。 3.6.4 Cray-1向量机 * * Cray-1 处理机结构图 * * * * (1)主存与流水结构运算器之间有一级或两级的中间存储器。 向量运算: 8个64个分量的向量寄存器组V:V0 ~ V7 每个分量为一个64位寄存器。 向量指令能对向量寄存器的分量进行连续的重复处理。 * * (2)执行向量指令时,流水结构运算器在一个时钟周期内从两个V寄存器得到一对操作数,完成某种操作后用一个时钟周期的时间把结果送入另一个V寄存器。 (3)主存储器与V寄存器之间的数据传送以成组传送的方式进行。 向量流水线是从向量寄存器而不是从主存储器取数据。同样,从流水线输出的结果向量也是送回向量寄存器。 * * 存储器和工作寄存器之间的数据通路可以看成是具有固定时间延迟的数据传送流水线。 * * Cray-1 处理机的4类向量指令 第一类向量指令 Vi ← Vj op Vk 从一个或二个向量寄存器取得操作数并把结果回送到另一个向量寄存器中去。 * * 第二类向量指令 Vi ← Sj op Vk 从Sj寄存器取得一个标量操作数,又从Vk寄存器取得一个向量操作数,并且把向量结果回送给另一个向量寄存器Vi 。 * * 第三类向量指令 Vi ← 主存 把数据从存储器传送到一个向量寄存器中 * * 第四类向量指令 主存 ← Vi 把数据从向量寄存器传送到存储器中。 * * CRAY-1向量处理的特点 每个向量寄存器Vi都有连到6个向量功能部件的单独总线。 每个向量功能部件也都有把运算结果送回向量寄存器组的总线。 只要不出现向量寄存器冲突(Vi冲突)和功能部件冲突,各Vi之间和各功能部件之间都能并行工作,大大加快了向量指令的处理。 * * Vi冲突:并行工作的各向量指令的源向量或结果向量使用了相同的Vi。 例:源向量相同 V3←V1+V2 V5←V4∧V1 功能部件冲突:并行工作的各向量指令要使用同一个功能部件。 例:都需使用乘法功能部件 V3←V1×V2 V5←V4×V6 * * 3.6.5 增强向量处理性能的方法 1. 多功能部件的并行操作 在向量机中采用独立的多个功能部件并行工作。 并行约束条件: ① 不存在向量寄存器使用冲突。 向量寄存器使用冲突是指并行工作的向量指令中的源向量或结果向量使用相同的向量寄存器。 ② 不存在功能部件使用冲突。 功能部件冲突是指同一功能部件为多条并行工作向量指令所使用。 * * 例1: ① V0←V1+V2 无冲突情况,可以并行处理 V5←V3×V4 例2: ② V0←V1+V2 运算时发生向量寄存器使用 V3←V1×V4 冲突,不可以并行处理 两条指令不能同时执行,必须在第一条指令执行完,将V1释放后,第二条指令方可开始执行。 因为两条指令中使用V1时的首元素下标可能不同,向量长度也可能不同,从而难以由V1同时向两条指令提供所需的源向量。 * * ③ V3←V1+V2 运算时发生功能部件冲突, V6←V4+V5 不可以并行处理 在理想情况下,若有m个部件并行工作,可使运算速度提高m倍,但实际上由于程序本身并行度有限和可能发生上述的冲突情况,因此能完全并行工作的功能部件数总是小于m的。 * * 3.6.6 提高向量处理机性能的方法 设置多个功能部件,使它们并行工作。 采用链接技术,加快一串向量指令的执行。 采用循环开采技术,加快循环的处理。 采用多处理机系统,进一步提高性能。 * * 3.6.6.1 设置多个功能部件 设置的多个独立功能部件能并行工作,并各自按流水方式工作,从而形成了多条并行工作的运算操作流水线个单功能流水部件: 向量部件:向量加,移位,逻辑运算 浮点部件:浮点加,浮点乘,浮点求倒数 标量部件:标量加,移位,逻辑运算,数“1”/计数 地址运算部件:整数加,整数乘 * * 3.6.6.2 链接技术 链接特性: 当相邻两条指令存在先写后读相关时,只要前一条指令的结果向量的第一个元素产生并存入结果向量寄存器,就可以将它作为下一条指令的源操作数,启动下一条指令的运算,从而将两个或两个以上的功能部件链接起来。 链接技术: 当从一个流水线部件得到的结果直接送入另一个功能流水线的操作数寄存器时所发生的连接过程。即中间结果不必送回存储器或寄存器,并在向量操作完成以前就使用它。 * * 在寄存器 — 寄存器系统结构中,所有的向量操作数在把它们送入流水线之前,都要预先装入向量寄存器中。中间和最后结果(流水线输出)在把它们存入主存储器以前,也要把它们装入向量寄存器中。 ★ 链接技术是利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术。 ★ 链接技术的实质是标量流水定向传送方法在向量寄存器中的应用。 * * 例:向量加和向量乘的操作: ADDV V1,V2,V3 ;V1←V2+V3 MULTV V4,V1,V5 ;V4←V1×V5 * * V1←V2+V3 V4←V1×V5 V2 V3 V1 V1 V5 V4 V1←V2+V3 V4←V1×V5 V2 V3 V1 V5 V4 链接过程 * * 这两条指令间对V1向量寄存器存在先写后读相关,如果使向量寄存器V1在同一时钟周期内,既接收一个功能部件送来的运算结果,又可把这一结果作为下一个向量指令运算所需的源操作数送给另一个功能部件,就可使这两个部件链接起来进行操作。通常把这种链接称为超级向量操作。 当链接进入充分流水操作状态后,在一个时钟周期内就可同时获取两个操作结果。 * * 按照状态图得出如下的各种调度组合。 ( 3) 最佳启动循环为(1,7)和(3,5), 平均启动距离为 4。 (4) 启动距离最小的恒定循环为(5) * * 根据所选择的调度策略,可以得到如下的流水线工作状态表 * * (这些工作状态表也可以用时空图方式描述。) * * 3.5.3 采用非计算延迟功能段进行优化调度 无冲突调度的问题 当采用最小启动循环启动非线性流水线,流水线中的许多流水段还有空闲。反映在预约表中还有空白的格子。即使是最繁忙的流水段也还有空闲,因此,按照上一节介绍的调度方法得到的最小启动循环,实际上并不能使非线性流水线充分发挥效率。 * * L.E.Shar于1972年提出了流水线最小平均启动距离的限制范围。 对于一条静态可重构的流水线,通过预约表可以得到其最小平均启动距离的范围。 ⑴ 最小平均启动距离的下限是预约表中任意一行里“×”的最多个数。实际上也就是同一个任务通过流水线中任意一个流水段的最多次数。 ⑵ 最小平均启动距离应小于或等于状态图中任意一个简单循环的平均启动距离。 ⑶ 最小平均启动距离的上限是冲突向量中1的个数再加上1。 这个限制在许多情况下是相当宽松的。 最小平均启动距离的范围 * * 优化调度的基本思想: 让流水线瓶颈段的功能充分发挥,不要空闲,使非线性流水线得到最好的吞吐率、加速比和效率且平均延迟时间最短。 1. 确定最小平均启动距离 最小平均启动距离是预约表中任意一行中“×”的最大个数。 2. 选择按最小平均启动距离等间隔输入作为最佳调度方案。 3. 运用预留算法在流水线中插入非计算延迟功能段,实现优化调度。 * * 预留算法 将预约表中任意一行中与前一个“×”的距离为最小平均启动距离的整数倍的“×”所在的时钟周期通过延迟的方法预留出来。 采用预留算法来调度非线性流水线,可以达到最优调度。 这是一种改变流水线结构的调度方法 * * 前例中非线 t7 t8 t9 t10 t11 S1 × × × S2 × × × × × S3 × S4 × × S5 × D1 × D2 × * * 根据预留算法在S5→S2功能段之间加入非计算延迟功能段D1和D2。 S1 输入 输出 S2 S3 S4 S5 1 9 2 3 4 5 6 7 8 D2 D1 * * 例:流水线的逻辑图和预约表如下,求流水线的最佳调度方案和优化调度方案。 S1 输入 输出 S2 S3 S4 1 2 6 7 4 5 3 时间 段 t1 t2 t3 t4 t5 t6 t7 S1 × × S2 × × S3 × S4 × × * * 解:禁止表:F={2,4,6} 原始冲突向量:C=(101010) 状态图: 101010 000001 101010 101011 + 000101 101010 101111 + 010101 101010 111111 + 7 7 7 5 7 3 1 5 5 3 * * 调度方案可选:1,7; 3,5; 5,3 启动距离最小的恒定循环调度方案为:5 调度方案 平均延迟时间 1,7 4 3,5 4 5,3 4 3,7 5 5 5 5,7 6 7 7 * * 优化调度方案 最小平均启动距离:2 采用预留算法: 时间 段 t1 t2 t3 t4 t5 t6 t7 t8 S1 × × × S2 × × × S3 × S4 × × × D × * * S1 输入 输出 S2 S3 S4 1 2 6 7 4 5 3 D * * 完成5个任务时,两种调度方案的性能比较: ① 采用3,5 最佳调度方案 实际吞吐率:Tp=5/23Δt 效率:E=(10+10+5+10) Δt/(4×23)Δt =35/92≈0.38=38% 最大吞吐率:Tpmax=1/平均延迟=1/ 4Δt S4 1 1 2 2 3 3 4 4 5 5 S3 1 2 3 4 5 S2 1 2 1 2 3 4 3 4 5 5 S1 1 2 1 3 2 4 3 5 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 t S * * ②采用优化调度方案,最小平均启动距离为2 实际吞吐率:Tp=5/16Δt 效率:E=(10+10+5+10) Δt/(4×16)Δt =35/64 ≈0.55=55% 最大吞吐率:Tpmax=1/平均延迟=1/ 2Δt D 1 2 3 4 5 S4 1 2 1 3 2 4 3 5 4 5 S3 1 2 3 4 5 S2 1 2 3 1 4 2 5 3 4 5 S1 1 2 3 4 1 5 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 t S * * 3.6 向量处理机 在流水线处理机中,设置向量数据表示和相应的向量指令,称为向量处理机。 不具有向量数据表示和相应的向量指令的流水线处理机,称为标量处理机。 * * 标量流水机的性能提高的制约 (1) 流水线工作的时钟周期不可能取得很短。 流水深度的增加会使时钟周期缩短,但也增加了流水线中出现相关性的可能性,将造成较大比例的断流,而为等待相关消除就需要更多的时钟周期,这导致每条指令执行所需的时钟周期数的增加。 当时钟周期减小时,将加剧时钟在流水线入口和出口处的扭斜错位程度,使级间锁定变得困难,导致不能可靠工作。 * * (2) 取指令及译码的速率受限。 即在一个时钟周期内最多只能启动一条指令,通常称为Flynn瓶颈。 * * 3.6.1 向量流水处理的主要特点 (1) 在向量操作中,每个当前结果向量元素的计算与以前结果向量元素的计算是相互独立的,有利于发挥流水线的性能,允许向量流水线) 一条向量指令相当于一个标量循环,可降低对指令访问带宽的要求,也消除了由循环转移可能引起的控制相关。 (3) 若向量指令所要访问的向量元素均相邻,则可利用多模块、交叉存取的方法加快向量元素的存取速度,减少访存等待时间的开销。 * * 在对相同数量的数据项进行操作时,向量操作要比一串标量指令操作更快。 向量流水机可使访存和有效地址计算流水化。 高档的向量机允许多个向量操作同时进行,从而可开发对不同元素进行多个向量操作的并行性。 * * 3.6.2 向量机的基本系统结构 向量机系统结构的分类 ① 存储器 — 存储器工作方式向量机 向量操作的源向量和目的向量都取自或存放到主存中。 * * ② 寄存器 — 寄存器工作方式向量机 向量操作的源向量和目的向量都取自或存放到向量寄存器中。 向量寄存器 * * 典型的向量机基本系统结构 向量机主要由标量流水部件和向量流水部件组成: 向量功能部件 向量取存部件 向量寄存器或向量缓冲部件 向量控制器 标量寄存器 标量处理部件等 * * 向量处理机的典型结构图 * * * * 例:一个典型向量求解问题: Y=a×X+Y 其中X和Y为向量,初始值存放在存储器中,a为标量。 采用双精度运算时的算法:a乘X后再加Y。 * * (1) 用标量机运算 用标量机运算,采用循环程序: 用标量指令对向量中的每个元素进行一次乘、加和存储操作。 为了实现循环操作,每次必须指明对X和Y中元素位置的下标变量并进行增量,同时使操作次数减1,判别循环是否结束。 设X和Y向量的首地址分别存放在Rx和Ry中,向量元素长度为64。 * * LD F0,a ;标量a装入F0 ADDI R4,Rx,#512 ;将向量元素的末地址装 ;入R4中 LOOP:LD F2,0(Rx) ;取向量元素X(i) MULD F2,F0,F2 ;a与X(i)相乘 LD F4,0(Ry) ;取向量元素Y(i) ADDD F4,F2,F4 ;aX(i)与Y(i)相加 SD 0(Ry),F4 ;存结果向量元素 ADDI Rx,Rx,#8 ;增量向量元素X下标 ADDI Ry,Ry,#8 ;增量向量元素Y下标 SUB R20,R4,Rx ;R4-Rx→R20,计算是 ;否到达限界值 BNZ R20,LOOP ;若循环未结束,转LOOP * * LD F0,a ;标量a装入F0 LV V1,Rx ;装入向量X,LV为向量取指令 MULTV V2,F0,V1 ;向量X与标量a相乘 LV V3,Ry ;装入向量Y ADDV V4,V2,V3 ;向量加aX+Y SV Ry,V4 ;存结果向量, ;SV为向量存指令 (2) 用向量机运算 * * 标量机与向量机计算Y=a×X+Y的比较 标量机 向量机 编程方式 采用标量指令,循环程序 采用向量指令 指令条数 9×64+2=578 6 联锁频率 高 低 对指令带宽的要求 高 不高 因为向量指令是对64个元素进行操作,且没有对元素下标变量增量和判循环是否结束的指令,所以向量机只需执行6条指令即可完成操作,从而大大降低了对指令带宽的要求。 * * 3.6.3 向量处理方法 向量机中对向量的加工方式的要求: 尽量避免出现数据相关和尽量减少对向量操作功能的转换。 * * ⑶ 延迟分支 从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成,不管分支是否成功,都要按顺序执行延迟槽中的指令。 延迟分支以及指令的执行顺序 具有一个分支延迟槽的流水线的执行过程 分 支 失 败 分支指令i IF ID EX MEM WB 延迟槽指令 i+1 IF ID EX MEM WB 指令 i+2 IF ID EX MEM WB 指令 i+3 IF ID EX MEM WB 指令 i+4 IF ID EX MEM WB 分支延迟槽中的指令“掩盖”了流水线原来必须插入的暂停周期。 分 支 成 功 分支指令i IF ID EX MEM WB 延迟槽指令 i+1 IF ID EX MEM WB 分支目标指令j IF ID EX MEM WB 分支目标指令j+1 IF ID EX MEM WB 分支目标指令j+2 IF ID EX MEM WB * * 分支延迟指令的调度 任务:在延迟槽中放入有用的指令。 调度工作由编译器完成。能否带来好处,取决于编译器能否把有用的指令调度到延迟槽中。 三种调度方法 从前调度 从目标处调度 从失败处调度 * * 调度前后的代码 * * 三种方法的要求及效果 调度策略 对调度的要求 什么情况下起作用 从前调度 被调度的指令必须与分支无关。 任何情况 从目标处调度 必须保证在分支失败时执行被调度的指令不会导致错误。有可能需要复制指令。 分支成功时 (但由于复制指令,有可能会增大程序空间) 从失败处调度 必须保证在分支成功时执行被调度的指令不会导致错误。 分支失败时 * * 分支延迟受到两个方面的限制 可以被放入延迟槽中的指令要满足一定的条件。 编译器预测分支转移方向的能力。 进一步改进:分支取消机制(取消分支) 分支延迟槽中存放预测指令。当分支的实际执行方向和事先所预测的一样时,执行分支延迟槽中的指令,否则就将分支延迟槽中的指令转化成一个空操作。 “预测成功-取消”分支的执行过程 分 支 失 败 分支指令i IF ID EX MEM WB 延迟槽指令 i+1 IF idle idle idle idle 指令 i+2 IF ID EX MEM WB 指令 i+3 IF ID EX MEM WB 指令 i+4 IF ID EX MEM WB 分 支 成 功 分支指令i IF ID EX MEM WB 延迟槽指令 i+1 IF ID EX MEM WB 分支目标指令j IF ID EX MEM WB 分支目标指令j+1 IF ID EX MEM WB 分支目标指令j+2 IF ID EX MEM WB 预测分支成功的情况下,分支取消机制的执行情况 * * ⑷ 加快短循环程序的处理 循环操作是一种特殊的条件转移。循环操作是否结束,主要根据循环操作次数是否已达到原来规定次数。 短循环程序:循环段中的指令数目少于指令缓冲器长度。 若将短循环程序段全部放入指令缓冲器中,就可在整个短循环程序段执行过程中不必再访问主存,而只需重复执行这一循环段,从而可加快执行速度。 * * 2.动态转移预测 动态转移预测:根据转移历史预测转移方向。 动态转移预测用于提高转移方向的猜准率。 静态转移预测方法不考虑转移历史,动态转移预测方法考虑了转移历史,因而有较高的猜准率。 一种具有较高猜准率的动态方法是考虑以前两次转移的历史。 * * * * TT:00; TN:10 NT:01 ; NN:00 这种方法仅当两次连续猜错时,预测状态才会发生改变。如从11状态变为10,再变为00。 经在RISC机上实际测试,这种方法的猜准率可高达83%。 * * 3.5 非线性流水线的调度 例:分析以下非线 Δt0 S4 1 2 1 2 3 4 3 4 5 5 … S3 1 2 1 2 3 4 3 4 5 5 S2 1 2 3 4 5 S1 1 2 3 4 5 … 1 2 3 4 5 6 7 8 9 10 11 12 13 14 t S * * 吞吐率: 加速比: 效率: * * 3.5.1 功能段的使用冲突 功能段的使用冲突:几个任务在同一时刻争用同一流水功能段。 为了避免冲突,需要延迟输入新任务进入流水线。 非线性流水线的调度: 找出一个最小的循环周期,按此周期向流水线输入任务,使流水线既不产生功能冲突,又可以获得最高的吞吐率和效率。 非线性流水线主要依据“预约表”来规划调度方案 * * 非线 Δt0 时间 段 t1 t2 t3 t4 t5 t6 S1 × S2 × S3 × × S4 × × * * 一张预约表可能与多个流水线连接图相对应 一个流水线连接图可能对应与多张预约表 * * 3.5.2 非线 7 8 * * 时间 段 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 S1 × × S2 × × × S3 × S4 × × S5 × ● 1. 根据流水线的连接图和一个任务通过流水线的顺序列出预约表。 * * 时间 段 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 S1 × ● ● ● ● × ● S2 × × ● ● ● × ● S3 × ● S4 × × ● ● S5 × ● 预约表中的冲突情况 * * 用预约表描述冲突的另一种方法 * * ⑴ 启动距离(等待延迟时间) 向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离(Initiation Interval)或等待时间(Latency)。 启动距离通常用时钟周期数来表示,它是一个正整数。若启动距离是n,表示两次输入之间需隔n个时钟周期。 2. 根据预约表建立禁止表 * * ⑵ 禁止启动距离 引起功能部件冲突的启动距离。 即预约表中同一行中两个“×”之间的距离。 禁止表:所有禁止启动距离构成的集合。 上图中, F={1,5,6,8} 即要想避免冲突,相邻两个任务进入流水线的间隔拍数就一定不能为1,5,6,8拍。 ⑶允许启动距离 在非线性流水线中的所有功能段,任何时刻都不会引起部件功能冲突的启动距离。 * * (4)启动循环 使非线性流水线的任何一个流水段在任何一个时钟周期都不发生冲突的循环数列称为非线性流水线的启动循环。只有一个启动距离的启动循环又称为恒定循环。 * * 3. 由禁止表形成原始冲突向量 冲突向量:一个n位的位向量 C=(Cn,Cn-1、…、C2、C1) Ci=0:允许输入; Ci =1:禁止输入 n:最止启动距离(所有启动距离中的最大值) 原始冲突向量:由禁止表直接形成的冲突向量。 如根据禁止表 F={1,5,6,8}得到的原始冲突向量为:C=(10110001) 注意:Cn总为1 因为冲突向量中的C2、C3、C4和C7均为0,所以第二个任务可距第一个任务2拍、3拍、4拍或7拍后流入流水线。 * * 根据原始冲突向量,按允许启动距离输入下一任务,当该任务进入流水线后,将形成新的冲突向量。再根据新的冲突向量中按允许启动距离输入下一任务,就可以形成新的冲突向量,以便确定后续任务何时可输入。 新的冲突向量的形成方法: 根据现行冲突向量,选择允许启动距离 i,将现行冲突向量右移 i 位,再与原始冲突向量相或,即可得到新的冲突向量。( i 的值可以大于最止距离 ) 4. 形成新的冲突向量 * * 流水线状态图 按新冲突向量的形成方法依次重复,一直进行到不再产生新的冲突向量,并形成闭合回路为止,即可得到流水线状态图。 例:按原始冲突向量 C=(10110001)形成的流水线 00001011 10110001 10111011 00101111 10110001 10111111 00000001 10110001 10110001 7 7 7 7 7 3 3 3 4 4 2 + + + + + 2 7 * * 5. 根据流水线状态图选择调度方案 流水线状态图中的每一个闭合回路都是一种调度方案,其中平均延迟时间最小者为最佳调度方案(最小启动循环)。 最佳调度方案:3,4,3,4, … 或 4,3,4,3, … 调度方案 平均延迟时间 2,2,7 3.67 (2+2+7)/3 2,7 4.5 (2+7)/2 3,4 3.5 (3+4)/2 4,3 3.5 (4+3)/2 4,7 5.5 (4+7)/2 7 7 闭合回路尽量选择简单循环构造。 简单循环:状态图中各种冲突向量最多只经过一次的循环。 * * 采用最佳调度方案:3,4,… 完成5个任务时,流水线的性能评价。 实际吞吐率:Tp=5/23Δt 效率:E=(10+15+5+10+5) Δt/(5×23)Δt=9/23 最大吞吐率:Tpmax=1/平均延迟=1/ 3.5Δt S5 1 2 3 4 5 S4 1 1 2 2 3 3 4 4 5 5 S3 1 2 3 4 5 S2 1 1 2 2 1 3 3 2 4 4 3 5 5 4 5 S1 1 2 3 1 4 2 5 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 t S * * 不等间隔的调度方案平均延迟时间短,但控制复杂。 为了简化控制,可采用间隔为7 的调度方案,成为等间隔(恒定循环)调度方案,但平均延迟时间增加了。 上述调度方法是一种无冲突调度,它是一种不改变流水线结构的调度方法。 这种调度方法的关键在于合理安排时序与控制部件。 这些理论最早是由E.S.Davidson及其学生们于1971年提出来的。 * * 例:一条4功能段的非线性流水线,每个功能段的延迟时间都相等,它的预约表如下: (1)写出流水线的禁止向量和初始冲突向量。 (2)画出调度流水线)求最佳启动循环和最佳平均启动距离(平均延迟时间)。 (4)求平均启动距离最小的恒定循环。 * * 解: (1)禁止向量为:(2,4,6) 初始冲突向量:C= (101010) (2)构造状态图 * * 2. 写后写冲突(WAW) 例: i MUL R0,R1,R4 ; R1×R4→R0 i+1 ADD R6,R5,1 ; R5+1→R6 i+2 MUL R2,R0,R3 ; R0×R3→R2 i+3 SUB R3,R4,1 ; R4-1→R3 i+4 MOV R2,R5 ; R5 →R2 写后写冲突 最后写入的结果是i+2 的。错误! * * 写后写冲突(WAW ):指令j对某单元或寄存器的写入先于i指令对同一单元或寄存器的写入。 写后写冲突由输出相关引起。 可能发生写后写冲突的流水线: 乱序流水线。 流水线中不只一个段可以进行写操作。 当先前某条指令停顿时,允许其后续指令继续前进。 写后写冲突也称写写相关、WW相关、WAW相关、写后再写相关等。 * * 3. 读后写冲突(WAR) 例: i MUL R0,R1,R4 ; R1×R4→R0 i+1 ADD R6,R5,1 ; R5+1→R6 i+2 MUL R2,R0,R3 ; R0×R3→R2 i+3 SUB R3,R4,1 ; R4-1→R3 i+4 MOV R2,R5 ; R5 →R2 读后写冲突 最后是i+2读入的数据是i+3的。错误! * * 读后写冲突(WAR ):指令j对某单元或寄存器的写入先于i指令对同一单元或寄存器的读出。 读后写冲突由反相关引起。 可能发生读后写冲突的流水线: 乱序流水线。 有些指令的写结果操作提前了,而且有些指令的读操作滞后了。 指令被重新排序。 读后写冲突也称先读后写相关、变量名相关、反相关、RW相关、WAR相关等。 * * 不同类型的数据相关 数据相关的分类 * * 3.4.3.3 解决数据相关的办法 ⑴ 时间后推法 遇到数据相关时,就停顿后继指令的运行,直至前面指令的结果生成并写入寄存器。 时间后推法将使流水线有较长的停顿。 * * ⑵ 采用定向技术 定向技术也称旁路技术或相关专用通路技术 定向技术的关键思想: 在某条指令产生计算结果之前,其他指令并不真正立即需要该计算结果,如果能够将该计算结果从其产生的地方直接送到其他指令需要它的地方,那么就可以避免停顿。 定向技术的实现: 在执行过程中建立直接的专用通道,将执行结果直接送往需要的执行部件。 * * 采用定向技术消除数据冲突 工作过程 * * 采用定向技术后的流水线数据通路 * * ALU 运算结果 写RF RF RF 读RF ALU 操作数寄存器 专用通路(旁路) 寄存器堆RF 多路开关 多路开关 ALU R4 R1 缓冲寄存器(R1,R4) 旁路 旁路 采用定向技术后的数据通路情况 * * 当定向硬件检测到前面某条指令的结果寄存器就是当前指令的源寄存器时,控制逻辑会将前面那条指令的结果直接从其产生的地方定向到当前指令所需的位置。 结果数据不仅可以从某一功能部件的输出定向到其自身的输入,而且还可以定向到其他功能部件的输入。 * * 到数据存储器和ALU的定向路径 例 DSUB R1,R2,R3 LD R5,0(R1) SD R5,12(R1) * * 需要停顿的数据冲突 并不是所有的数据冲突都可以用定向技术来解决。 例: LD R1,0(R2) DADD R4,R1,R5 AND R6,R1,R7 XOR R8,R1,R9 * * 无法将LD指令的结果定向到DADD指令 * * 装入延迟的解决方法 无法将LD指令的结果定向后续指令的情况也称为RISC机流水线中的装入延迟。 解决方法:设置流水线互锁机制。 作用:检测发现数据冲突,并使流水线停顿,直至冲突消失。 实现方法:增加流水线互锁硬件,实现插入“停顿”的功能。 * * 插入停顿的过程 * * 插入停顿前后的时空图 LD R1,0(R2) IF ID EX MEM WB DADD R4,R1,R5 IF ID EX MEM WB AND R6,R1,R7 IF ID EX MEM WB XOR R8,R1,R9 IF ID EX MEM WB LD R1,0(R2) IF ID EX MEM WB DADD R4,R1,R5 IF ID stall EX MEM WB AND R6,R1,R7 IF stall ID EX MEM WB XOR R8,R1,R9 stall IF ID EX MEM * * 减少定向传送次数的方法 在ID段中,将读寄存器堆的操作安排在ID段的后半部分,在WB段中,将写寄存器堆操作安排在WB段的前半部分,以减少定向传输操作。 IF EX MEM ID R WB W IF EX MEM ID R WB W IF EX MEM ID R WB W IF EX MEM ID R WB W IF EX MEM ID R WB W ADD R1,R2,R3 SUB R4,R1,R5 AND R6,R1,R7 OR R8,R1,R9 XOR R10,R1,R11 定向传递R1值 * * ⑶ 依靠优化编译解决数据冲突 让编译器重新组织指令顺序来消除冲突 这种技术称为指令调度或流水线调度。 例: 执行A=B+C时的装入延迟导致的暂停 LD Rb,B IF ID EX MEM WB LD Rc,C IF ID EX MEM WB DADD Ra,Rb,Rc IF ID stall EX MEM WB SD Ra ,A IF stall ID EX MEM WB * * 指令调度技术 由于LOAD的执行时间不确定,所以优化编译不能从根本上解决问题。 调度前的代码 调度后的代码 LD Rb,B LD Rc,C DADD Ra,Rb,Rc SD Ra,A LD Re,E LD Rf,F DSUB Rd,Re,Rf SD Rd,D LD Rb,B LD Rc,C LD Re,E DADD Ra,Rb,Rc LD Rf,F SD Ra,A DSUB Rd,Re,Rf SD Rd,D * * 3.4.3.3 控制冲突 控制冲突即控制相关,主要是由转移指令引起的,是一种全局性的相关。 当转移发生时,将使流水线的连续流动受到破坏。因此比起数据相关来,控制相关会使流水线丧失更多的性能,使流水线的吞吐率和效率严重下降。 * * 执行分支指令的结果 分支成功: PC值改变为分支转移的目标地址。在条件判定和转移地址计算都完成后,才改变PC值。 不成功或者失败: PC的值保持正常递增,指向顺序的下一条指令。 * * 处理分支指令最简单的方法 “冻结”或者“排空”流水线 。 优点:简单。 前述5段流水线中,改变PC值是在MEM段进行的,给流水线个时钟周期的延迟。 * * 简单处理分支指令:分支成功的情况 分支指令 IF ID EX MEM WB 分支目标指令 IF stall stall IF ID EX MEM WB 分支目标指令+1 IF ID EX MEM WB 分支目标指令+2 IF ID EX MEM 分支目标指令+3 IF ID EX * * 简单处理分支指令:分支失败的情况 当分支失败时,实际上分支后第一条指令已经正确取出,再重复IF周期已无必要,这时流水线空等不是一种好的选择。 分支指令 IF ID EX MEM WB 分支后继指令 IF stall stall IF ID EX MEM WB 分支后继指令+1 IF ID EX MEM WB 分支后继指令+2 IF ID EX MEM 分支后继指令+3 IF ID EX * * 由分支指令引起的延迟称为分支延迟。 分支指令在目标代码中出现的频度:每3~4条指令就有一条是分支指令。 设:流水线,分支指令出现的频度为30% 则:流水线 * * 正常程序的流水线吞吐率: 有转移程序时的流水线吞吐率: 使流水线的性能降低 * * 减少分支延迟的方法 在流水线中尽早判断出分支转移是否成功。 尽早计算出分支目标地址。 后续的讨论假设: 判断工作被提前到ID段完成,即分支指令是在ID段的末尾执行完成,所带来的分支延迟为一个时钟周期。 * * 1. 静态转移预测 当流水线译码出某指令为条件转移指令时,在其所需的条件码建立之前,先将一个方向猜测为成功路径,通常是选取发生概率较高的路径,并在转移条件码生成之前只对这个方向上的若干条指令进行预取、译码和取操作数,按该方向继续流动。 若猜测失败,必须返回原分支点重新执行另一分支方向。 * * ⑴ 预测分支失败 允许分支指令后的指令继续在流水线中流动,就好象什么都没发生似的。 若确定分支失败,将分支指令看作是一条普通指令,流水线正常流动。 若确定分支成功,流水线就把在分支指令之后取出的所有指令转化为空操作,并按分支目地重新取指令执行。 要保证:分支结果出来之前不会改变处理机的状态,以便一旦猜错时,处理机能够回退到原先的状态。 * * ⑵ 预测分支成功 假设分支转移成功,并从分支目标地址处取指令执行。 起作用的前提:先知道分支目标地址,后知道分支是否成功。 在前述的5段流水线中,因为判断分支成功和分支目标地址的计算均在EX段完成,所以这种方法对减少该流水线的分支延迟没有任何好处。 若判断分支成功和分支目标地址的计算在后续功能段中实现,则此方法可以减少的分支延迟。 预测分支流水线的处理过程 * * * * 存储器访问/分支完成周期(MEM) 该周期处理的指令只有load、store和分支指令。其他类型的指令在此周期不做任何操作。 load指令:用上一个周期计算出的有效地址从存储器中读出相应的数据。 store指令:把指定的数据写入这个有效地址所指出的存储器单元。 分支指令:分支“成功”,就把转移目标地址送入PC。分支指令执行完成。 * * 写回周期(WB) ALU运算指令和load指令在这个周期把结果数据写入通用寄存器组。 ALU运算指令:结果数据来自ALU。 load指令:结果数据来自存储器系统。 * * 不同类型指令在各功能段中完成的操作 ALU LOAD/STORE BRANCH IF 取指 取指 取指 ID 译码、读 寄存器堆 译码、读 寄存器堆 译码、读 寄存器堆 EX 执行 计算访存有效地址 计算转移目标地址,置条件码 MEM -- 访存(读或写) 条件成立,则转移目标地址?PC WB 结果写回寄存器堆 将读出的数据写入寄存器堆 -- 指 令 流水段 * * 在上述实现方案中: 分支指令需要 4 个时钟周期(如果把分支指令的执行提前到ID周期,则只需要 2 个周期)。 store指令需要 4 个周期。 其他指令需要 5 个周期完成。 * * 指令执行过程的流水线实现 每一个周期作为一个流水段。 在各段之间加上流水寄存器(锁存器)。 * * 5段流水线的两种描述方式 ⑴类时空图描述 时钟周期 指令 1 2 3 4 5 6 7 8 9 指令k IF ID EX MEM WB 指令k+1 IF ID EX MEM WB 指令k+2 IF ID EX MEM WB 指令k+3 IF ID EX MEM WB 指令k+4 IF ID EX MEM WB * * ⑵ 数据通路形式描述 * * 采用流水线方式实现时需解决的问题 ⑴ 保证不会在同一时钟周期要求同一个功能段做两件不同的工作。 例如,不能要求ALU同时做有效地址计算和算术运算。 ⑵ 避免IF段的访存(取指令)与MEM段的访存(读/写数据)发生冲突。 可以采用分离的指令存储器和数据存储器; 一般采用分离的指令Cache和数据Cache。 * * ⑶ 因为ID段和WB段可能要访问同一寄存器,即: ID段:读;WB段:写,为了防止寄存器冲突,可将写操作安排在时钟周期的前半拍完成,将读操作安排在时钟周期的后半拍完成。 读操作 写操作 * * ⑷ 考虑PC的问题 流水线为了能够每个时钟周期启动一条新的指令,就必须在每个时钟周期进行PC值的增量操作,并保留新的PC值。这种操作必须在IF段完成,以便为取下一条指令做好准备。 (需设置一个专门的加法器) 但分支指令也可能需要改变PC的值,而且是在MEM段进行,这会导致冲突。 * * 3.4.2 相关 要使流水线具有良好的性能,必须设法使流水线能畅通流动,即必须能做到充分流水,不发生断流。 相关:两条指令之间存在某种依赖关系。 如果两条指令相关,则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行。 * * 使流水线断流的相关问题 局部相关:指令执行过程中的资源冲突、数据相关。 全局相关:控制相关,如转移指令、中断的处理 B0 B1 B2 块間存在分支,是全局相关 基本块内无分支,是局部相关 * * 相关的三种类型 数据相关(也称真数据相关) 名相关 控制相关 * * 1. 数据相关 数据相关:相邻指令的数据存在一定的关系。 对于两条指令 i(在前)和 j(在后),如果下述条件之一成立,则称指令j与指令i数据相关。 指令j使用指令i产生的结果; 指令j与指令k数据相关,而指令k又与指令i数据相关。 数据相关具有传递性。 数据相关反映了数据的流动关系,即如何从其产生者流动到其消费者。 * * 例:下面这一段代码存在数据相关。 Loop: L.D F0,0(R1) // F0为数组元素 ADD.D F4,F0,F2 // 加上F2中的值 S.D F4,0(R1) // 保存结果 DADDIU R1,R1,-8 // 数组指针递减8个字节 BNE R1,R2,Loop // 如果R1≠R2,则分支 * * 当数据的流动是经过寄存器时,相关的检测比较直观和容易。 当数据的流动是经过存储器时,相关的检测比较复杂。 原因: 相同形式的地址其有效地址未必相同。 形式不同的地址其有效地址却可能相同。 * * 2. 名相关 名:指令所访问的寄存器或存储器单元的名称。 如果两条指令使用相同的名,但是它们之间并没有数据流动,则称这两条指令存在名相关。 指令j 与指令i 之间的两种名相关 反相关:如果指令j写的名与指令i读的名相同,则称指令i和j发生了反相关。 指令j 写的名=指令i 读的名 输出相关:如果指令j和指令i写相同的名,则称指令i和j发生了输出相关。 指令j写的名=指令i写的名 * * 名相关的两条指令之间并没有数据的传送。 如果一条指令中的名改变了,并不影响另外一条指令的执行。 可以通过换名技术改变指令中操作数的名来消除名相关。 * * 换名技术 换名技术:通过改变指令中操作数的名来消除名相关的技术。 寄存器换名:对寄存器操作数进行换名。 寄存器换名既可以用编译器静态实现,也可以用硬件动态完成。 * * 例:下述代码中存在名相关 DIV.D F2,F6,F4 ;F2←F6/F4 ADD.D F6,F0,F12 ;F6 ←F0+F12 SUB.D F8,F6,F14 ;F8 ←F6-F14 DIV.D和ADD.D在F6存在反相关。 进行寄存器换名(F6换成S)后,变成: DIV.D F2,F6,F4 ADD.D S,F0,F12 SUB.D F8,S,F14 * * 3. 控制相关 控制相关:指由分支指令引起的相关。 为了保证程序应有的执行顺序,必须严格按控制相关确定的顺序执行。 典型控制相关是“if-then”结构,例如: if p1 { S1; }; S; if p2 { S2; }; * * 控制相关带来的两个限制 与一条分支指令控制相关的指令不能被移到该分支之前,否则这些指令就不受该分支控制了。 如上例中,then 部分中的指令不能移到if语句之前。 如果一条指令与某分支指令不存在控制相关,就不能把该指令移到该分支之后。 如上例中, 不能把S移到if语句的then部分中。 * * 3.4.3 流水线冲突 流水线冲突:由于相关的存在,使得流水线中的下一条指令不能在指定的时钟周期执行。 三种流水线冲突: ① 结构冲突:因硬件资源满足不了指令重叠执行的要求而发生的冲突,也称为资源冲突。 ② 数据冲突:当指令在流水线中重叠执行时,因数据相关而发生的冲突。 ③ 控制冲突:流水线遇到分支指令和其他会改变PC值的指令所引起的冲突。 ①、②由局部相关引起,③由全局相关引起。 * * 流水线冲突带来的问题 导致错误的执行结果。 流水线可能会出现停顿,从而降低流水线的效率和实际的加速比。 约定 当一条指令被暂停时,在该暂停指令之后流出的所有指令都要被暂停,而在该暂停指令之前流出的指令则继续进行(否则就永远无法消除冲突)。 * * 3.4.3.1 结构冲突 当有多条指令进入流水线后在同一机器周期内争用同一功能部件所发生的冲突。 (资源冲突、资源相关) 当发生结构冲突时,流水线中某种指令组合将因为争用资源而不能正常执行。 导致结构相关的常见原因: 功能部件不是完全流水 资源份数不够 * * 例:访存冲突 有些流水线处理机只有一个存储器,将数据和指令放在一起,访存指令会导致访存冲突。 解决办法一: 插入暂停周期, 即 “流水线气泡”或“气泡”。引入暂停后的时空图 * * 引入暂停后的时空图 指令 编号 时钟周期 1 2 3 4 5 6 7 8 9 10 指令i IF ID EX MEM WB 指令i+1 IF ID EX MEM WB 指令i+2 IF ID EX MEM WB 指令i+3 stall IF ID EX MEM WB 指令i+4 IF ID EX MEM WB 指令i+5 IF ID EX MEM * * 解决方法二 设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache。 * * 为了减少硬件成本,有时流水线设计者允许结构冲突的存在 主要原因: 如果把流水线中的所有功能单元完全流水化,或者重复设置足够份数,那么所花费的成本将相当高。 * * 3.4.3.2 数据冲突 数据冲突 当相关的指令靠得足够近时,它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序,使之不同于它们非流水实现时的顺序,则发生了数据冲突。 根据指令读访问和写访问的顺序,可以将数据冲突分为三种类型。 * * 1. 写后读冲突(RAW) 例: i MUL R0,R1,R4 ; R1×R4→R0 i+1 ADD R6,R5,1 ; R5+1→R6 i+2 MUL R2,R0,R3 ; R0×R3→R2 i+3 SUB R3,R4,1 ; R4-1→R3 i+4 MOV R2,R5 ; R5 →R2 写后读冲突 * * 设有指令 i 和 j ,i 在 j 之前进入流水线。 写后读冲突:指令j对某单元或寄存器的读出先于i指令对同一单元或寄存器的写入。 即先后进入流水线的指令i与指令j之间关于同一操作数相关。 写后读冲突也称为先写后读相关、流相关、WR相关、RAW相关等。 RAW是最常见的数据冲突,对应于线 效率 E 效率:流水线中的各功能段的利用率。 由于流水线有建立和排空时间,因此各功能段的设备不可能一直处于工作状态,总有一段空闲时间。一般用流水线各段处于工作时间的时空区与流水线中各段总的时空区之比来衡量流水线 n-1 n S2 1 2 3 4 5 n-1 n S1 1 2 3 4 5 6 … n mΔt Tm (n-1) Δt S t * * 流水线的最大效率 当n→∞时,流水线的效率最高。 若流水线各段的延迟时间不同,则效率为: * * 吞吐率、加速比和效率的关系 E=Tp·Δt=Sp/m=Sp/Spmax 效率是实际加速比和最大加速比之比。 只有E=1时,才能达到Sp=m 当Δt不变时,效率与吞吐率成正比。所以为提高效率所采用的方法,对提高吞吐率也有好处。 * * 例:设有浮点加法器流水线,试分析算式 Z=A+B+C+D+E+F+G+H 在流水线中执行时的流水线的性能。 为提高运算速度,可采用算法: Z={[(A+B)+(C+D)]+[(E+F)+(G+H)] } = [(1)+(2)]+[(3)+(4)] = [一]+[二] 求阶差 对阶 尾数加 规格化 被加数 输出和 Δt0 Δt0 Δt0 Δt0 加数 * * t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 规格化 1 2 3 4 一 二 Z 尾数加 1 2 3 4 一 二 Z 对阶 1 2 3 4 一 二 Z 求阶差 1 2 3 4 一 二 Z t S A + B C + D E + F G + H 1 + 2 3 + 4 一 + 二 和 * * 吞吐率: 加速比: 效率: * * 例:设有静态加、乘双功能流水线段组成加减流水线段组成乘法流水线,各段的延迟时间均为Δt,流水线的输出可直接返回输入端或暂存到相应的缓冲寄存器中。 * * 现有A、B两个向量,每个向量有四个元素,要求在此流水线上计算: 请适当安排操作顺序,在最短时间内完成计算工作,并求出流水线工作时的实际吞吐率、加速比和效率。 * * 解: (1)选择适合于流水线+B1)×(A2+B2)和(A3+B3)×(A4+B4); 然后求总的乘积结果。 * * 实际工作的时空图 * * 从图中可见,在总共18Δt时间内输出7个结果,因此该流水线的实际吞吐率为: Tp=7/18Δt 流水线%。 若用串行方法完成上述的加乘操作,则需要做4次加法和3次乘法,求一次和需6Δt,求一次积需4Δt,总共需要时间: Tl=4×6Δt+3×4Δt=36Δt 加速比: Sp=Tl/Tm=36Δt/18Δt=2 * * 流水线效率较低的原因 ⑴ 多功能流水线在按某种功能流水时,总有一些当前功能不需要的段处于空闲状态。 ⑵ 静态流水线在功能切换时,要等待前一种运算全部排空,才能重新连接、切换功能,需要有排空和建立两种不同功能流水的额外开销。 ⑶ 经常发生下一步要等待上一步计算结果反馈的情况,即出现数据相关问题。 ⑷ 任务数少时,建立和排空时间所占的比例大。 * * 流水线较适合于求解的操作相同,且输入、输出间相互独立的连串运算。 当任务充足时,流水线的吞吐率可接近于最大吞吐率,流水线,而加速比也可接近于流水线的段数值。 * * 例:有一条由5段组成的动态多功能流水线△t,其余各段时间均为△t,而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。若在该流水线上计算: 试计算其吞吐率、加速比和效率。 * * (1) 选择适合于流水线工作的算法 应先计算A1×B1、A2×B2、A3×B3、A4×B4; 再计算 (A1×B1)+(A2×B2)、 (A3×B3)+(A4×B4); 最后求总的累加结果。 * * 实际工作的时空图 * * 性能计算 吞吐率: 加速比: 效率: * * 3.3.5 流水线. 瓶颈问题 理想情况下,流水线在工作时,其中的任务是同步地每一个时钟周期往前流动一段。 当流水线各段不均匀时,机器的时钟周期取决于瓶颈段的延迟时间。 在设计流水线时,要尽可能使各段时间相等。 * * 2. 流水线的额外开销 ⑴ 流水寄存器延迟 ⑵ 时钟偏移开销 时钟 S1 L S2 L S1 L Sk L L S3 L … 输入 输出 Δti ΔtS ΔtL L:锁存器 * * ⑴ 流水寄存器延迟 流水寄存器需要建立时间和传输延迟 建立时间:在触发写操作的时钟信号到达之前,寄存器输入必须保持稳定的时间。 传输延迟:时钟信号到达后到寄存器输出可用的时间。 ⑵ 时钟偏移开销 流水线中,时钟到达各流水寄存器的最大差值时间。(时钟到达各流水寄存器的时间不是完全相同) * * 流水线段数的选择 如果流水线段数过多,时钟周期很小,以至于与时钟偏移和流水寄存器的附加开销相当,会导致在一个时钟周期内没有足够时间用于有效工作,流水线也就失去了作用。 设在非流水线部件上完成一个任务所需的时间为t;在同等速度的m段带锁存器的流水线上完成同样任务的时间为: t/m+d d为锁存器的延迟时间。 流水线的最大吞吐率: * * 由于流水寄存器延迟和时钟偏移开销对流水线的性能有较大的影响,特别是当流水深度比较大、时钟周期比较小时,其影响更为突出,所以计算机系统的设计人员必须选用高性能的锁存器作为流水线寄存器。 * * 设流水线的总造价为:C总=C+mh C:流水线各功能段总成本,h:锁存器成本 根据son对流水线的性能价格比PCR的定义,得流水线的性能价格比为: 流水线的段数与成本 * * 为得到最佳PCR,即PCR的最大值,对m求导,得到性能价格比PCR的极值,由于大于零的极值只有一个,因此,这个极值就是最大值。 当性能价格比PCR取得最大值时,它所对应的流水线 最佳流水线段数为: t为流水线的总延迟时间。 * * 性价比与流水线的段数 * * 在设计一条流水线的时候,可以根据极限公式,在流水线的总延迟时间t一定的情况下,通过调整流水线本身的价格C,锁存器的延迟时间d和锁存器的价格h来选取最佳的流水线。 一般流水线段以上的流水线段以上的流水线的处理机称为超流水线处理机。 注:早期规定5段之内为普通流水。 * * 关于流水线的几个问题 流水线并不能减少(而且一般是增加)单条指令的执行时间,但却能提高吞吐率。 增加流水线的深度(段数)可以提高流水线的性能。 流水线的深度受限于流水线的额外开销。 当时钟周期小到与额外开销相同时,流水已没意义。因为这时在每一个时钟周期中已没有时间来做有用的工作。 * * 3. 流水线的冲突问题 如果流水线中的任务之间存在关联,则可能需要任务之间的相互等待,形成流水线的冲突,引起流水线的停顿,从而影响流水线的性能。 解决流水线的冲突问题是流水线设计中要解决的重要问题之一。 * * 3.4 流水线段流水线 取指 译码 执行 访存 写回 输入 输出 s1 s2 s3 s4 s5 IF ID EX MEM WB * * 一条指令的执行过程: IF→ID→EX→MEM→WB 取指令周期(IF) IR ← Mem[PC] ;指令寄存器IR ←指令 PC值加4 ;(假设每条指令占4个字节) 指令译码/读寄存器周期(ID) 译码 用IR中的寄存器编号去访问通用寄存器组,读出所需的操作数。 * * 执行/有效地址计算周期(EX) 不同指令所进行的操作不同: 存储器访问指令:ALU把所指定的寄存器的内容与偏移量相加,形成用于访存的有效地址。 寄存器-寄存器ALU指令:ALU按照操作码指定的操作对从通用寄存器组中读取的数据进行运算。 寄存器-立即数ALU指令:ALU按照操作码指定的操作对从通用寄存器组中读取的第一操作数和立即数进行运算。 分支指令:ALU把偏移量与PC值相加,形成转移目标的地址。同时,对在前一个周期读出的操作数进行判断,确定分支是否成功。 * * 浮点加法器流水线的时空图 * * ⑵ 处理机级——指令流水线 把一条指令解释过程分成多个子过程组成流水工作方式。 如前面所提到的将指令执行过程分为取指、译码、执行、访存及写回五个子过程。 取指 译码 执行 访存 写回 输入 输出 s1 s2 s3 s4 s5 IF ID EX MEM WB * * ⑶ 系统级——处理机间流水线(宏流水线) 将系统中多个处理机串联起来,对同一数据流进行不同的处理,每个处理机完成整个任务中的一部分专门任务。 处理机1 存储 器1 处理机2 处理机n 存储 器2 存储 器n 任务1 任务2 任务n 输入 输出 * * 2.按功能分 ⑴ 单功能流水线 只完成一种固定功能的流水线。 如浮点加法或乘法流水线。 ⑵ 多功能流水线 同一流水线的各功能段可进行不同的连接,使流水线在不同时间或同一时间内完成不同的功能。 * * 多功能流水线 ASC的多功能流水线 * * ⑴ 静态流水线 在同一时间内,流水线只能以一种功能方式工作。 静态流水线可以是单功能流水线,也可以是多功能流水线。 当是多功能流水线时,则从一种功能方式变为另一种功能方式时,必须先排空流水线,然后为另一种功能设置初始条件后方可使用。 对于静态多功能流水线来说,只有当输入的是一串相同的运算任务时,流水线的效率才能得到充分的发挥。 3. 按工作方式分 * * 静态流水线时空图 静态流水线 * * ⑵ 动态流水线 在同一时间内,可以将流水线中的不同功能段连接成不同的功能子集(前提条件是功能部件的使用不发生冲突),以完成不同的运算功能。 动态流水线必是多功能流水线 单功能流水线必是静态流水线 * * 动态流水线时空图 动态流水线 静态、动态流水线.按连接方式分 ⑴ 线性流水线 从流水线的输入到输出,每个功能段只允许经过一次,流水线中不存在反馈回路。 一般的流水线均属于线性流水线。 ⑵ 非线性流水线 流水线各功能段之间除了串行连接外,还存在反馈回路,因此从流水线的输入到输出过程中,某些功能段将被数次通过。 非线性流水线适合于进行线性递归的运算。 * * 非线 →S1 →S2 反馈回路 非线 输入 输出 * * 为了防止两条或两条以上的指令对同一功能段的争用,非线性流水线需要对输入流水线的指令进行比较复杂的控制。 非线性流水线通常使用预约表来进行分析。 预约表 1 2 3 4 5 6 7 8 9 s1 1 1 s2 1 1 1 s3 1 1 s4 1 * * 5.按任务流动方式分 ⑴ 顺序流动流水线 输出端的任务流出与输入端的任务流入顺序完全相同。 ⑵ 乱序流动流水线 输出端的任务流出与输入端的任务流入顺序不完全相同。 在乱序流动流水线中,当某任务阻塞时,后面的任务可绕过它继续流动。 例如有的指令需要读数据,有的不需要,在不冲突的情况下,只要执行部件有空闲,不读数的指令可先在执行部件中执行。 * * 6. 标量处理机与向量流水处理机 流水线处理机 指令执行部件中采用了流水线的处理机。 标量处理机 处理机不具有向量数据表示和向量指令,仅对标量数据进行流水处理。 向量流水处理机 具有向量数据表示和向量指令的处理机。 向量流水处理机是向量数据表示和流水技术的结合。 * * 3.3 流水线 吞吐率Tp 单位时间内流水线能处理的任务数量或输出的结果数。 设任务数为n,流水线段数为m,完成n个任务的时间为Tm,则吞吐率Tp * * ⑴ 最大吞吐率Tpmax 流水线达到稳定状态后可获得的吞吐率。 * * 流水线实际工作时的吞吐率。

http://bluecaleel.com/xiangliangliushuixian/28.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有