第五章--标量流水线技术-《计算机系统结构》课件

*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 标量流水线技术,(,P253),5.1,基本名词术语,(P253),标量处理机,：标量处理机指只能直接进行标量运算的处理机。,提高处理机指令执行速度的主要途径有：,提高主频；,设计更好的算法和功能部件；,指令级并行,主要方法，又可分为：,a,流水线技术和超流水线技术；,b,超标量技术 ；,c,VLIW,；,指令级并行技术,：指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；,流水线处理机,：指用流水作业方式并行解释多条指令的处理机。,本章学习标量计算机上使用的流水加速技术。主要内容有,流水技术的分类,、,流水线性能指标计算,、,非线性流水线的调度算法,。,1,基本名词术语（,P253,）,标量处理机,，,超标量处理机,：,标量处理机指只能进行标量运算的处理机，超标量处理机指能在一个时钟周期内同时发射多条指令的处理机；,流水线处理机,，,超流水线处理机,：流水线处理机指用流水作业方式并行解释多条指令的处理机，超流水线处理机指能在一个时钟周期内分时发射多条指令的处理机；,超长指令字技术,VLIW,：,指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技术。,2,5.1,流水处理的基本思想,3,4,5,流水技术,流水技术,：将一个重复的时序过程分解成为若干个子过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执行。,时空图,从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。,CPU,中的各个部件按流水处理顺序连接起来，就称为一条,流水线,。,6,流水线结构图,(P278),流水线工作时空图,(P278P279),7,5.2,流水处理,顺序方式,是解释完一条指令再开始解释下一条,(P254),；,重叠方式,是一种简单的流水方式，它把指令分成,2,个子过程，每条指令只与下一条指令相重叠,(P255),。,流水方式,是把一个重复的过程分解为若干个子过程，每个子过程可以与其它子过程同时进行，以此提高单位时间内解释指令的数目,(P277),；,流水线是一种通过改进结构来提高程序解释速度的方法。,5.2.1,流水线工作原理,处理机解释程序的方式有,顺序方式,、,重叠方式,、,流水方式,等。,8,重叠方式流水线,当分析部件完成上一条指令的“分析”后，就立即将之送入执行部件，同时分析部件可以开始处理下一条指令。,虽然从执行一条指令的全过程来看，仍需要,2,t,的时间，但从机器的输出端来看，却是每隔一个,t,就能给出一条指令的执行结果。,9,空间,（段号）,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,16,时间,（拍）,(a),顺序方式,空间,（段号）,1,2,3,4,1,2,3,4,10,时间,（拍）,(b),重叠方式,空间,（段号）,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,7,时间,（拍）,t,(c),流水方式,图,3.2 CPU,工作时空图,10,流水过程由多个相联系的子过程组成，每个子过程称为流水线的,级,或,段,，段的数目称为流水线的,深度,。,把一个任务分解为几个有联系的子任务，每个子任务由一个专门的功能部件来实现。,在流水线的每一个功能部件的后面都要有一个缓冲器，用于保存本段的执行结果。,各个功能段所需时间应尽量相等，否则时间长的功能段将成为流水线的“,瓶颈,”，会造成流水线的“,堵塞,”和“,断流,”。这个时间一般为一个时钟周期（节拍）,。,在流水线中处理的必须是连续任务，只有不断的提供任务才能充分发挥流水线的效率。,流水线需要有“装入时间”和“排空时间”。,流水线的特点,11,5.2,流水技术的分类,(P280),线性,/,非线性（,P280,）：,部件级,/,处理机级,/,处理机间级（宏流水线）（,P281,）：,单功能,/,多功能（,P282,）：,静态,/,动态（,P283,）：,标量,/,向量（,P285,）：,同步,/,异步（,P285,）：,顺序,/,乱序（,P285,、,P304,）：,12,2.,部件级,/,处理机级,/,处理机间级（宏流水线）,(P281),功能部件级：运算操作流水线,处理机级：指令流水线,处理机间级：宏流水线,13,1.,线性,/,非线性,(P280),功能段间是否有反馈信号,14,3.,单功能,/,多功能,(P282),单功能流水线：只能完成一种固定功能。,多功能流水线：流水线各段可以进行不同连接，实现不同功能。,P283,图,5.32,15,4.,静态,/,动态,(P283),（对多功能流水）,静态：一段时间内一种固定方式连接，实现一种固定功能；,动态：一段时间内，各段按不同方式连接，同时执行多种功能。,16,5.,标量,/,向量,(P285),-,-,数据表示不同,6.,同步,/,异步,(P285),对线性流水线的控制方式不同,7.,顺序,/,乱序,(P285,、,P304),输出与输入任务的顺序是否相同,17,5.3,逻辑相关,(P263-276),全局性相关,/,局部性相关,(P312,、,P269,/P263,、,P303),；,控制相关,：控制相关是指由条件分支指令、转子程序指令、中断等引起的相关,数据相关,：在执行本条指令过程中，若用到的指令、操作数、变址偏移量等正好是前面指令的执行结果，则须等待前面指令执行完成，并把结果写到内存或通用寄存器之后，本条指令才能开始执行，这种相关称为数据相关。,1,）“先写后读”相关,(p306),（,1,）延迟执行,2,）“先读后写”相关,（,2,）专用路径,3,）“写,-,写”相关,（,3,）,sw,/hw,避免相关,指令相关,/,数相关,(P264/P263),；,主存数相关,/,寄存器数相关,(P265/P266),；,数值相关,/,变址值相关,(P266/P268),。,相关的定义,：,(P263,倒数第4段,),所谓相关（,correlation,）,流水线中的相关是指相邻或相近的指令因存在某种关联，后面的指令不能在原指定的时钟周期开始执行。,相关的分类及其对策：,18,5.4.1,吞吐率,TP(P285),吞吐率（,TP ,ThroughPut,rate,）指流水线在单位时间内执行的任务数，可以用输入任务数或输出任务数表示。,，其中,n,为,任务数，,k,表示流水线划分的段数，,Tk,是处,理完,n,个任务所用时间。,实际吞吐率,/,最大吞吐率,5.4,线性流水线性能分析,(P285)-,吞吐率,TP,19,当满足 且无相关条件时，有,5.4,线性流水线性能分析,实际吞吐率：,最大吞吐率：,20,流水线各段的执行时间不等,21,流水线各段的执行时间不等,实际吞吐率：,最大吞吐率：,22,5.4,线性流水线性能分析,-,细分,“瓶颈”,流水线各段的执行时间不等，则执行时间最长的段就是流水线的,瓶颈,。解决,瓶颈,的方法是：,再细分,“瓶颈”段,将瓶颈设备再细分为下一级流水线,23,5.4,线性流水线性能分析,-,并行设置,并行设置,将瓶颈设备重复设置多套，轮番接受任务,注意两种方法的时空图不同。,24,一般表示：,实际加速比：,最大加速比：,=,流水深度,其中,5.4.2,加速比,(P288),不使用流水线所用的时间与使用流水线所用的时间之比,5.4,线性流水线性能分析,-,加速比,25,Pipeline Illustrated:,5.4,线性流水线性能分析,流水深度,k,26,Performance Model,Starting from an,unpipelined,version with propagation delay,T,and,BW = 1/T,P,pipelined,=,BW,pipelined,= 1 / (T/ k +S ),where,S,= delay through latch,T,S,S,T/k,T/k,k-stage,pipelined,unpipelined,5.4,线性流水线性能分析,流水深度,27,Hardware Cost Model,Starting from an,unpipelined,version with hardware cost,G,Cost,pipelined,=,kL,+ G,where,L,= cost of adding each latch, and,k,= number of stages,G,L,L,G/k,G/k,k-stage,pipelined,unpipelined,5.4,线性流水线性能分析,流水深度,28,Cost/Performance:,C/P = ,Lk,+ G / 1/(T/k + S) = (,Lk,+ G) (T/k + S),= LT + GS +,LSk,+ GT/k,Optimal Cost/Performance: find min. C/P,k,Cost/Performance Trade-off,k,C/P,G,=an,unpipelined,version with hardware cost,T,=,an,unpipelined,version with propagation delay,S,= delay through latch,L,= cost of adding each latch,5.4,线性流水线性能分析,流水深度,29,段效率：，各段平均效率：,其中 表示第,i,段设备量占整条流水线全部设备量的百分比。,当满足 条件,（即,等长,、,等权,）,时，有：,上式指出，,S=Ek,，,就是说当效率达到,100%,时，流水方式（一个任务,/,t,）,吞吐率,为顺序方式（一个任务,/,(k,t),）的,k,倍。,5.4.3,效率（设备利用率，,P289,）,5.4,线性流水线性能分析,-,效率,30,31,例,5.1(P292),分析：已知下列表达式，有相关，单功能，,k = 4,，,n = 7,。要求最少相关，用,“,二叉树算法,”,以减少相关。,Z = A + B + C + D + E + F + G + H, , ,5.4.4,性能分析实例,(P292),32,例,5.2(P293),分析：已知下列表达式，二功能，有切换，有相关，,k = 8,，,n = 7,。要求用最少切换、最少相关算法。,Z = A,B + C,D + E,F + G,H,乘法： ,加法： ,加法： ,33,5.5,非线性流水线调度技术,(P294),调度问题的提出,：,一个任务在通过非线性流水线时对有些功能段要,通过多次,（非线性定义），所以容易与紧跟而来的后继任务发生,设备争用,。,调度机构的作用就是合理安排前后任务进入流水线的,相差时间,，既要,避免争用,，又要使,相差时间尽可能少,，以提高吞吐率。,34,1.,非线性流水线的表示,S1,S2,S3,S4,一条非线性流水线一般需要一个各功能段间的连接图和一张预约表共同表示。,下图是一条,4,个功能段组成的非线性流水线，它有从,S1,到,S4,的单方向传输线。但它有两条反馈线和一条前馈线；输出端不一定在最后一个功能段，而可能从任意一个功能段输出。,输出,输入,35,2.,非线性流水线的预约表,S4,S3,S2,S1,7,6,5,4,3,2,1,时间,功能段,36,3.,对于非线性流水线的表示,预约表的横坐标表示流水线的,时钟周期,，纵坐标表示流水线的,功能,段,，中间有“, ”,的表示该功能段在这一个时钟周期处于工作状态，即在这个时钟周期有任务通过这个功能段；空白的表示该功能段在这一个时钟周期不处于工作状态。,预约表行数是非线性流水线的,段数,；而列数是一个任务从进入流水,线到从流水线中输出所经历的,时钟周期数,。,一张非线性流水线的预约表可能与,多个,非线性流水线连接图相对,应；同样，一个非线性流水线的连接图也可能对应有,多张,预约表。,37,4.,非线性流水线的冲突,非线性流水线的启动距离,：,向一条非线性流水线的输入端连续输入,两个任务之间的时间间隔,。,非线性流水线的冲突,：,当以某一个启动距离向一条非线性流水线连,续输入任务时，可能在某一个功能段或某几个,功能段中发生有几个任务同时争用同一个功能,段的情况。,5.,无冲突调度方法,目标：,找出具有最小平均启动时间的启动循环，按照这样的启动循,环向非线性流水线的输入端输入任务，流水线的工作速度最,快，而且所有功能段在任何时间都没有冲突。,38,算法,：共,5,个步骤,第,1,步,.,分析,预约表,R,（,P295,图,5.44,）,描述非线性流水线有,2,种图形：,(a),连接图,，仅给出各段之间的静态,空间连接关系；,(b),预约表,，就是一个任务通过流水,线的时空图，能全面反映该流水线,的动态特性,。,要检验2个任务相距,k,拍是否冲突，可将它们的预约表错位,k,列重叠（上图）。,第,2,步,.,作,禁止表,F,（,P297,倒数第,2,段）,F,是,1-N,之间可冲突拍数的集合，,N,是预约表的列数减1。,具体操作是将同一行中任意,2,个标记之间的拍数差记下来，再将各行的这类数字汇成一个集合，即为禁止表。本例中,F = 3,，,4,，,6 ,5.5.1,不改变流水线结构的调度方法,(P295),时间,段,1,2,3,4,5,6,7,S1,1,1,1,S2,1,1,S3,1,1,S4,1,时间,段,1,2,3,4,5,6,7,S1,2,2,2,S2,2,2,S3,2,2,S4,2,39,第,3,步,.,作,原始,冲突向量,C,（,P298,倒数第3,段）,为了设计调度机构，需将禁止表转化为,原始冲突向量,C,。,C,是含,N,个分量的布尔向量，一般形式为,C = (,c,N,.c,1,),，,其中,N,是预约表的列数减1，也可以是,禁止表中的最大元素。第,i,个分量取值原则为：,本例中,C = (101100),40,动态冲突向量 （初值,000000,）,右移寄存器,：0 010110右移出,0,“或”运算器：,按位,“,或,”,0接通,1,断开,常量发生器,： 101100,原始冲突向量,时钟输入,流水线任务排队,1.每个时钟脉冲使流水线中现有任务前进一步，也使右移寄存器移出一位；,2.,如果新任务进入，则用它的原始冲突向量与,右移寄存器内容相,“,或,”,。,使用,冲突向量,C,实现调度的原理图,41,第,4,步,.,作,状态转移图,（,P299,图,5.51,）,这是为了研究,无穷多个任务时任务之间可能存在的合法间隔情况,。从表达方便考虑，用,动态冲突向量作为状态变量。,具体作图方法是：,(1),先画,“,根结点,”,，它就是第一个任务进入后的,右移寄存器状态,，数值等于,原始冲突向量；,(2),分析当前结点的,各位,，如果,c,i,=0,则,发出一个旁标,i,值的箭头，,c,i,=1,则不能,发出箭头，因为,1,表示,“,禁止,”,。此外还发出一个旁标,“,N+1,”,的,箭头，,“,N+1,”,意为,“,N+1,”,；,(3),每个箭头末端产生一个新的结点，其,状态等于原结点状态右移,i,位后与,原始冲,突向量,相,“,或,”,；,(4),如果新结点状态与已有的结点重复，,则取消它，箭头指向已有的那个结点。,000000,初态,1 7*,101100,7* 7* 1 5 2 7* 7*,111110 101111,1 5 2,111111 101101,5,42,第,5,步,.,作平均延迟拍数表,（,P300,表,5.1,）,(1),在状态转移图中寻找全部简单循,环填入右表第,1,栏。,所谓简单循环是,指其中各结点仅通过一次的闭合路,径。,注意它不一定要通过根结点,；,(2),计算各简单循环的平均间隔拍数,填入右表第,2,栏。,平均间隔拍数等于,该简单循环中所有数字之和除以数,字个数；,(3),取,平均延迟拍数最少的方案作为最优方案。本例为,(1,1,7),；,(4),调度机构实现：,计数器加译码电路,。本例可用模,9,计数器，译码条件是计数值等于,0,、,1,、,2,时允许进入流水线。,简单循环,平均启动距离,（,1,7,）,4,（,1,1,7,）,3,（,2,7,）,4.5,（,2,5,）,3.5,（,2,5,7,）,7,（,5,7,）,6,（,5,）,5,（,7,）,7,（,5,2,7,）,4.7,43,时间,功能段,1,S1,S2,S3,S4,2,3,4,5,6,7,8,9,10,11,1,1,1,1,1,2,1,2,1,1,2,3,2,2,2,2,2,3,3,3,3,3,4,4,4,44,5.5.2,改变流水线结构的优化调度方法, 预留算法,(P301),目的,：等间隔的最小延迟调度方案,方法,：插入延迟器件,第,1,步，,确定,相邻任务间隔拍数：,因为最小间隔拍数是一行内,“,”,的最大数目（第,11,行），取最小间隔拍数,。,第,2,步，,确定插入延迟器件位置的原则（,P302,第,2,行,）,：从第一个,“,”,开始，凡是相距,最小间隔,拍数整倍数位置的,“,”,都要向后推迟。,实例（,P301,倒数第,7,行）：,1.,确定间隔拍数（最多,3,个,“,”,，所以是,3,拍,）；,2.,插入延迟器件（使各行,“,”,的间距不为,3,的倍数,）；,3.,修改预约表（,P,302,图,5.53(a),）；,4.,写调度方案（,3,）。,（示意图见下页）,45,46,47,5.6,超标量,/,超流水,/,超长指令字技术（,P320,）,本节学习其它指令级并行技术。主要内容有,超标量技术,、,超流水技术,、,多操作部件技术,、,超长指令字技术,。,下面是一些相关的名词术语（,P253,）,标量处理机，超标量处理机,：标量处理机指只能进行标量运算的处理机，超标量处理机指能在一个时钟周期内同时发射多条指令的处理机；,指令级并行技术,：指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；,流水线处理机，超流水线处理机,：流水线处理机指用流水作业方式并行解释多条指令的处理机，超流水线处理机指能在一个时钟周期内分时发射多条指令的处理机；,超长指令字技术,VLIW,：,指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技术。,48,一、超标量处理机,1,普通标量处理机,-,只有一条流水线，每个时钟周期只有一条指令流入流水线。,分为两种类型。,（,1,）单操作部件流水线处理机,ILP1,49,（,2,）,多操作部件流水线处理机,ILP1,50,2,单发射与多发射处理机,（,1,）单发射处理机,只有一套指令部件（取指部件和译码部件），并且每个时钟周期只取一条指令，只对一条指令进行译码。,51,单发射处理机,，,ILPILP1,54,二。超标量处理机：,通常，把,一个时钟周期内能够,同时,发射多条指令,的处理机称为,超标量处理机,。,（,P,324,倒,2,行）,超标量处理机最基本的要求是必须有,两套或两条以上完整的指令执行部件,。为了能够在一个时钟周期内同时发射多条指令，超标量处理机必须有两条或两条以上能够同时工作的指令流水线。,超标量处理机指令调度要解决的问题,数据相关,控制相关,功能部件冲突,(,指令序列要求）,55,超标量技术：,时空图见,P323,图,5.71,（,b,）。,56,超流水技术：（,P,333,第1,行）,在一个基本时钟周期内能够,分时,发射多条指令的处理机称为超流水线处理机,。在有些资料上把指令流水线的级数为,8,级或超过,8,级的流水线处理机称为超流水线处理机。,时空图见,P333,图,5.79,。,57,超流水线处理机工作方式与超标量处理机不同,，,超标量处理机是通过重复设置多个“取指令”部件，设置多个“译码”、“执行”和“写回结果”部件，并且让这些功能部件同时工作来提高指令的执行速度，实际上是以增加硬件资源为代价来换取处理机性能的；,超流水线处理机则只需要,增加少量硬件,，是,通过各部分硬件的充分重叠工作来提高处理机性能,的。,从流水线时空图上看，超标量处理机采用的是空间并行性，而超流水线处理机采用的是时间并行性。,58,3,典型结构,在早期生产计算机，巨型计算机,CRAY-1,和大型计算机,CDC,7600,属于超流水线处理机，,ILP=3,。,在目前大量使用的微处理器中，只有,SGI,公司,MIPS,（,microprocessor without Interlocked piped stages,）,系列属超流水线处理机。,（,MIPS,是除,Intel,公司,X86,系列微处理器外，生产量最大的一种微处理器）,MIPS,系列微处理器主要有,R2000,、,R3000,、,R4000,、,R5000,和最近刚投放市场的,R10000,几种。,R4000,的指令流水线有,8,级，如下图。采用超流水线结构，取指令和访问数据都要跨越两个流水级；每个时钟周期包含两个流水级，处理器取第一条指令,（,IF,）,和取第二条指令（,IS,）,59,两个,流水级都要访问指令,Cache,，,这两个流水级为一个时钟周期。,60,四超标量与超流水处理机,超标量超流水线处理机,在一个时钟周期内要发射指令,n,次，每次发射指令,m,条,，因此，超标量超流水线处理机,每个时钟周期总共要发射指令,mn,条,。,61,m,n,图中每一时钟周期分为,3,个流水线周期，每一流水线周期发射,3,条指令。每个时钟周期能够发射并执行完成,9,条指令。因此，理想情况下，超标量超流水线处理机执行程序速度应该是超标量处理机和超流水线处理机执行程序速度的乘积。,62,超标量,/,超流水线,/,超标量超流水线处理机,机器类型,K,段流水线基准标量处理机,M,度超标量处理机,N,度超,流水线处理机,（,M,，,N,）,超标量超流水线处理机,机器流水线周期,1,个,时钟周期,1,1/N,1/N,同时发射指令条数,1条,M,1,M,指令发射等待时间,1,个,时钟周期,1,1/N,1/N,指令级并行度,1,M,N,M*N,63,主要特点：,（,1,）单一的控制流。只有一个控制器，每个周期启动一条指令。,（,2,）超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件。,（,3,）含有大量的数据通路和功能部件，由于编译器在编译时间已考虑可能出现的数据相关和资源相关，故控制硬件较简单。,（,4,）在编译阶段完成超长指令中多个可并行执行操作的调度。,超长指令字技术,VLIW,指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技术。,64,VLIW hardware is simple and straightforward, like SIMD machines.,While SIMD broadcasts one instruction, VLIW separately directs each functionalunit,add r1,r2,r3,FU,FU,FU,FU,add r1,r2,r3,FU,FU,FU,FU,load r4,r5+4,mov r6,r2,mul r7,r8,r9,SIMD,Instruction,Execution,VLIW,Instruction,Execution,65,0,1,2,3,4,5,6,T,3,个操作,每拍启动一条长指令，执行,3,个操作，相当于,3,条指令，要求并行度,=3,超长指令字计算机（,VLIW,）,的原理结构,66,5.7,精简指令系统（,RISC,）技术,(P111),什么是,RISC,？（,P107,）,CISC,和,RISC,是指令系统设计的两种思路，,前者注重功能多，后者注重速度快。,双方各自发展了很多特色技术。,RISC,主要用于工作站和其它高性能计算机，以,UNIX,操作系统为主。,IBM-PC,个人计算机以,CISC,为主，吸收了,RISC,若干适宜技术。,20%,与,80%,规律,（,P112,）：,统计表明，,CISC,中,20%,常用指令使用率高达,80%,，其它为非常用指令。,RISC,定义与特点,（,P115,）,一个周期；一种访存寻址方式；硬联译码；简化指令；固定指令格式；优化译码。,减少,CPI,是,RISC,思想的精华,（,P116,）,分析公式：,T = IC,CPI,CYCLE,，,RISC,使,IC,增加，其它两项减少。,67,RISC,的关键技术,(P118),1,.,延时转移技术：,将转移指令与它前面的不相关指令对调位置，以利用计算目的地址的时间。,2.,指令取消技术：,在条件转移指令解释期间提前启动最有可能的一个分支的后继指令，如果,“,猜,”,错则及时取消，,“,猜,”,对则赢得了时间。,3.,重叠寄存器窗口技术：,用寄存器组代替堆栈传递参数，减少访问主存。,4.,指令流调整技术：,用换名消除相关，消除不了的相关就调整顺序。,5.,少数复杂指令用微程序实现：,不常用的复杂指令用微程序实现，避免专设电路，对平均速度影响也不大。,68,69,本章小结,(1),流水处理与相关的概念；,(2),时空图画法及其应用；,(3) 7,种流水线分类方法；,(4) 3,个流水线性能指标；,(5) 2,种,“,瓶颈,”,解决方法,；,(6) 2,种非线性流水线调度方法,；,(7),超标量与超流水技术的概念,；,(8),精简指令系统（,RISC,）技术。,习题：,P34,3,，题,9,，题,15,。,70,