资源描述
单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,幻灯片,264,/264,Computer ArchitectureV3,同济大学.电子与信息工程学院.计算机科学与工程系,流水处理和指令级并行,流水线基本概念,相关性分析技术,多指令放射技术,流水线基本概念,引入,流水线工作原理,流水线的分类,流水线的性能分析,非线性流水线的调度技术,本章内容,引 入,本章内容,流水线基本概念,标量处理机,具有标量数据表示和标量指令系统的处理机称为标量处理机。,提高指令执行速度的主要途径,提高处理机的工作主频；,接受更好的算法和设计更好的功能部件；,接受指令级并行（ILP）技术（本章介绍）。,流水线工作原理,本章内容,流水线基本概念,基本思想,表示方法,主要特点,流水线基本思想,本章内容,流水线基本概念,流水线工作原理,基本思想：,以,指令流水线,为例进行介绍：,取指,分析,执行,通过将一个重复的过程分解为若干子过程，每个子过程可以与其它子过程同时进行。,t,t,t,5 之 1,流水线基本思想,本章内容,流水线基本概念,流水线工作原理,依次执行,取指,k,分析,k,执行,k,取指,k+1,分析,k+1,执行,k+1,优点：,限制简洁，节约设备。,缺点：,处理器执行指令的速度慢,功能部件的利用率很低,n,条指令的执行时间为：,5 之 2,n,条指令的执行时间为：,流水线基本思想,本章内容,流水线基本概念,流水线工作原理,一次重叠,取指,k,分析,k,执行,k,取指,k+1,分析,k+1,执行,k+1,取指,k+2,分析,k+2,执行,k+2,优点：,执行指令的速度较快,功能部件的利用率较高,缺点：,限制较困难，需增加设备,5 之 3,n,条指令的执行时间为：,流水线基本思想,本章内容,流水线基本概念,流水线工作原理,二次重叠,优点：,执行指令的速度更快,功能部件的利用率更高,缺点：,限制更困难，需增加设备,取指,k+2,分析,k+2,执行,k+2,取指,k+1,分析,k+1,执行,k+1,取指,k,分析,k,执行,k,5 之 4,流水线基本思想,本章内容,流水线基本概念,流水线工作原理,流水线利用并行性实现：,空间并行性,设置多个独立的操作部件。,时间并行性,分时运用同一个部件的不同部分。,5 之 5,流水线表示方法,本章内容,流水线基本概念,流水线工作原理,流水线的表示方法通常有三种：,连接图,时空图,预约表,连接图,本章内容,流水线基本概念,流水线工作原理,流水线表示方法,分析器,分析,k+1,流水锁存器,执行部件,执行,k,流水锁存器,输,入,输,出,t,1,t,2,Stage 1,latch,输,入,输,出,t,1,t,2,Stage 2,latch,Stage 3,latch,t,3,2 之 1,连接图,功能段,流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、流水级、流水节拍等。,流水寄存器,在每一个流水段的末尾或开头必需设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门寄存器等。加入流水寄存器，会增加指令的执行时间。在一般流水线中不画出流水寄存器。,本章内容,流水线基本概念,流水线工作原理,流水线表示方法,2 之 2,时空图,1,时间,空间,0,t,1,t,2,t,3,t,4,t,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,t,6,t,7,t,8,求阶差,对阶,尾数加,规格化,求阶差,对阶,尾数加,规格化,t,t,t,t,本章内容,流水线基本概念,流水线工作原理,流水线表示方法,流水线主要特点,本章内容,流水线基本概念,流水线工作原理,只有连续供应同类任务才能发挥流水线效率,尽量削减因条件分支造成的“断流”，可通过编译技术供应连续的相同类型操作。,每个流水线段都要设置一个流水寄存器,用于保存本流水线段的执行结果，会使流水线的执行时间加长，是流水线中须要增加的主要硬件。,各流水段的时间应尽量相等,流水线处理机的基本时钟周期等于时间最长的流水段的时间长度。,流水线须要有“装入时间”和“排空时间”,流水线的分类,本章内容,流水线基本概念,从不同的角度，依据不同的观点，可以将流水线分成多种不同的种类。,分类一,分类二,分类三,分类四,其它,分类一,单功能流水线,只能完成一种固定功能的流水线。例如：,Cray-1,计算机中有12条；,YH-1,计算机有18条；,Pentium,有一条5段定点和一条8段浮点流水线；,Pentium,有两条定点和一条浮点指令流水线。,多功能流水线,流水线的各段通过不同连接实现不同功能。例如：,Texas,公司的,ASC,机，8段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。,本章内容,流水线基本概念,流水线的分类,按流水线具有功能的多少来分，可分为：,2 之 1,Texas,公司,ASC,机上的8段多功能流水线,2 之 2,分类二,本章内容,流水线基本概念,流水线的分类,在多功能流水线中，依据在同一时间内是否能够连接成多种方式，同时执行多种功能，可以将多功能流水线分为：,静态流水线,动态流水线,静态流水线,本章内容,流水线基本概念,流水线的分类,分类二,同一段时间内，各个功能段只能依据一种方式连接，实现一种固定的功能。,1,时间,空间,0,2,3,n,1,2,3,n,1,2,3,n,1,2,3,n,1,2,3,n,1,2,3,n,1,2,3,4,1,2,3,1,2,1,输入,求阶差,对阶,尾数加,规格化,尾数乘,累加,输出,浮点加法,定点乘法,动态流水线,在同一段时间内，各段可以依据不同的方式连接，同时执行多种功能。,1,时间,空间,0,2,3,n,1,2,3,n,1,2,3,n,1,2,3,n,1,2,3,n,1,2,3,n,输入,求阶差,对阶,尾数加,规格化,尾数乘,累加,输出,1,2,3,5,4,6,1,2,3,5,4,1,2,3,4,1,2,3,浮点加法,定点乘法,本章内容,流水线基本概念,流水线的分类,分类二,分类三,本章内容,流水线基本概念,流水线的分类,依据流水线的各个功能段之间是否有反馈信号，可以将流水线分为：,线性流水线,是指流水线内各功能段串行连接，没有反馈回路，各个功能段只经过一次。一条线性流水线通常只完成一种固定的功能。例子：指令流水线、浮点加法器流水线等。,非线性流水线,是指流水线内除有串行连接的通路外，还有某种反馈回路，使得一次流水过程中，某些段会多次通过。非线性流水线常常用于递归调用，或构成多功能流水线等。,3 之 1,非线性流水线,S,1,输入,S,2,S,3,输出,前馈回路,反馈回路,一种简洁的非线性流水线,对应的两种预约表,S3,S2,S1,4,3,2,1,S3,S2,S1,4,3,2,1,5,3 之 2,本章内容,流水线基本概念,流水线的分类,提 示,线性流水线能够用连接图唯一表示，非线性流水线必需用连接图和预约表共同表示。,一条非线性流水线可以对应有很多张预约表，同样，一张预约表事实上仅表示了一条非线性流水线的一种工作方式,线性流水线事实上也有预约表，只不过它的预约表是固定的（一张对角线为的正方形的表格）,3 之 3,本章内容,流水线基本概念,流水线的分类,分类四,依据流水线运用的不同级别，可以将流水线分为：,部件级流水线,处理机级流水线,系统级流水线,本章内容,流水线基本概念,流水线的分类,部件级流水线,本章内容,流水线基本概念,流水线的分类,分类四,是指构成部件内的各子部件之间的流水。例如：浮点加法器流水线。,求阶差,输入,输出,t,1,对阶,尾数加,规格化,t,2,t,3,t,4,处理机级流水线,又称为指令流水线 ，例如：在接受先行限制器的处理机中，各功能部件之间的流水线。,先行指令缓冲栈,输入,先行控制方式中的指令流水线,先行指令分析器,先行读数栈先行操作栈,取指,译码,取操作数,指令执,行部件,后行,写数栈,输出,执行,写结果,本章内容,流水线基本概念,流水线的分类,分类四,系统级流水线,也称为宏流水线，是处理机之间的流水线 。例如：每个处理机对同一个数据流的不同部分分别进行处理。,P1,输,入,任务1,M,M,P2,任务2,M,P3,任务3,输,出,本章内容,流水线基本概念,流水线的分类,分类四,其 它,依据不同的数据表示方式分：,标量流水线,对标量数据进行处理。,向量流水线,对向量数据进行处理。,依据流水线中信息流淌依次的限制方式分：,依次流水线,流水线输出端的任务流出依次与输入端的任务流入依次完全相同。,异步流水线,流水线输出端的任务流出依次与输入端的任务流入依次可以不一样。,本章内容,流水线基本概念,流水线的分类,流水线的性能分析,本章内容,流水线基本概念,吞吐率,加速比,效 率,流水线最佳段数的选择,性能分析举例,吞吐率,定义,单位时间内能流出的任务数或能流出的结果数。,公式,n ：,任务数；,T,m,：,处理完成,n,个任务所用的时间。,本章内容,流水线基本概念,流水线的性能分析,8 之 1,案例1：志向状况(1),假设在流水线各段的执行时间均相等，输入到流水线中的任务是连续的志向状况下，一条单功能m段线性流水线能够在m+n-1个时钟周期内完成n个任务。,本章内容,流水线基本概念,流水线的性能分析,8 之 2,1,时间,空间,S,1,2,3,n-1,n,S,2,S,m,1,2,3,n-1,n,1,2,3,n-1,n,m,t,(n-1) t,nt,(,m,-1)t,T,m,案例1：志向状况(2),本章内容,流水线基本概念,流水线的性能分析,8 之 3,实际吞吐率,最大吞吐率,两者之间的关系,案例2：实际状况,假设在流水线各段的执行时间不相等，输入到流水线中的任务是连续的志向状况下。,实际吞吐率,最大吞吐率,本章内容,流水线基本概念,流水线的性能分析,8 之 4,问题及解决,本章内容,流水线基本概念,流水线的性能分析,8 之 5,问题,流水线的TP和TPmax主要由流水线中执行时间最长的那个功能段来确定，这个功能段就成了整个流水线的“瓶颈”。,解决,将流水线中的“瓶颈”再细分；,通过重复设置多套瓶颈功能段，让多个瓶颈功能段并行工作。,举 例-,瓶颈,本章内容,流水线基本概念,流水线的性能分析,8 之 6,S,1,t,1,=,t,S,2,t,2,=3,t,S,3,t,3,=,t,S,4,t,4,=,t,输,出,1,时间,空间,S,1,S,2,S,3,S,4,t,i,(n-1)t,2,T,m,2,3,n,1,2,3,n,1,2,3,n,1,2,3,n,输,入,举 例-,瓶颈解决,本章内容,流水线基本概念,流水线的性能分析,8 之 7,S,1,输入,输出,t,S,2-1,t,S,2-2,t,S,2-3,t,S,3,t,S,4,t,S,2,(3,t),S,1,输入,输出,t,1,=,t,S,2-3,S,2-2,S,2-1,S,3,S,4,t,3,=,t,t,4,=,t,t,2,=3,t,瓶颈细分,多套瓶颈,举 例-,多套瓶颈时空图,本章内容,流水线基本概念,流水线的性能分析,8 之 8,1,时间,空间,2,3,n,S,1,S,2-1,4,5,6,1,4,n,-2,n,-1,n,-2,2,5,n-1,3,6,n,1,2,3,n,4,5,6,n,-2,n,-1,1,2,3,n,4,5,6,n,-2,n,-1,S,2-2,S,2-3,S,3,S,4,加速比,本章内容,流水线基本概念,流水线的性能分析,定义,完成同样一批任务，不运用流水线所用的时间与运用流水线所用的时间之比。,公式,T0：依次执行所用的时间；,Tm：运用流水线所用的时间。,3 之 1,案例1：志向状况,假设在流水线各段的执行时间都相等，输入到流水线中的任务是连续的志向状况下。,实际加速比,最大加速比,本章内容,流水线基本概念,流水线的性能分析,3 之 2,案例2：实际状况,假设在流水线各段的执行时间不相等，输入到流水线中的任务是连续的志向状况下。,实际加速比,本章内容,流水线基本概念,流水线的性能分析,3 之 3,效 率,本章内容,流水线基本概念,流水线的性能分析,定义,是指流水线的设备利用率。在时空图上，流水线的效率定义为,n,个任务占用的时空区与,m,个功能段总的时空区之比。,公式,1,时间,空间,S,1,n,S,2,S,m,1,n,1,n,4 之 1,案例1：志向状况,假设在流水线各段的执行时间都相等，输入到流水线中的任务是连续的志向状况下。,实际效率,最大效率,本章内容,流水线基本概念,流水线的性能分析,4 之 2,案例2：实际状况(1),假设在流水线各段的执行时间不相等，输入到流水线中的任务是连续的志向状况下。,实际效率（功能段等权值）,本章内容,流水线基本概念,流水线的性能分析,4 之 3,案例2：实际状况(2),实际效率（功能段权值不同）,其中，,i,为,i,段的权值，,i,流水线基本概念,流水线的性能分析,4 之 4,流水线最佳段数的选择,本章内容,流水线基本概念,流水线的性能分析,问题提出,功能段数量的增加能提高流水线的吞吐率和加速比，但使流水线价格增加（锁存器数量的增加），一条指令执行的总时间增加（锁存器的总延迟时间增加）。所以从性价比角度动身流水线存在着最佳段数。,2 之 1,流水线最佳段数的选择,问题解决,对自变量,m,求导，求,PCR,的最大值，得到最佳段数为：,本章内容,流水线基本概念,流水线的性能分析,t：任务总时间,d：锁存器时间,m：功能段数,a：全部功能段价格,b：锁存器价格,2 之 2,性能分析举例,本章内容,流水线基本概念,流水线的性能分析,问：用一条4段浮点加法器流水线求8个浮点数的和，要求所用时间最短，求流水线的吞吐率、加速比和效率。,ZABCDEFGH,答：由于存在着数据相关，假如干脆交与流水线处理，效果与依次执行完全一样，因此先作一个简洁变换，然后交与流水线处理。,Z=(A+B)+(C+D)+(E+F)+(G+H),3 之 1,性能分析举例,本章内容,流水线基本概念,流水线的性能分析,3 之 2,1,时间,空间,2,3,求阶差,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,对阶,尾数加,规格化,加数,A,C,E,G,A+B,E+F,B,D,F,H,C+D,G+H,A+B+C+D,E+F+G+H,结果,A+B,C+D,E+F,G+H,A+B+C+D,E+F+G+H,Z,被,加数,性能分析举例,流水线的吞吐率为：,流水线的加速比为：,流水线的效率为：,本章内容,流水线基本概念,流水线的性能分析,3 之 3,非线性流水线的调度技术,本章内容,流水线基本概念,调度目的,非线性流水线的冲突,无冲突调度方法,优化调度方法,调度目的,本章内容,流水线基本概念,非线性流水线的调度技术,非线性流水线的调度目的是要找出一个最小的循环周期，依据这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。,非线性流水线的冲突,本章内容,流水线基本概念,非线性流水线的调度技术,启动距离,向一条非线性流水线的输入端依次输入两个任务之间的时间间隔称为启动距离/等待时间。,冲突,几个任务同时争用同一个流水线功能段的状况称为非线性流水线的冲突。,禁止启动距离,引起非线性流水线冲突的启动距离称为禁止启动距离。,5 之 1,举 例-,非线性流水线,本章内容,流水线基本概念,非线性流水线的调度技术,5 之 2,输出,S1,S2,S3,S4,输入,S4,S3,S2,S1,7,6,5,4,3,2,1,时间,流水段,举 例-,流水线冲突,本章内容,流水线基本概念,非线性流水线的调度技术,5 之 3,举 例-,流水线不冲突,本章内容,流水线基本概念,非线性流水线的调度技术,5 之 4,不发生冲突的启动距离一般是一个循环数列，称为非线性流水线的,启动循环,，记作（1，7）。,举 例-,流水线不冲突,启动距离5也可以认为是一个循环数列，称为非线性流水线的,恒定循环,，记作（5）。,本章内容,流水线基本概念,非线性流水线的调度技术,5 之 5,无冲突调度方法-,例子,本章内容,流水线基本概念,非线性流水线的调度技术,S4,S3,S2,S1,7,6,5,4,3,2,1,时间,流水段,12 之 1,S,1,S,2,S,3,S,4,输入,输出,无冲突调度方法-,步骤,本章内容,流水线基本概念,非线性流水线的调度技术,由预约表得到禁止向量,由禁止向量得到冲突向量,由冲突向量构造调度流水线的状态图,在状态图中找出可用启动距离，并计算平均启动距离,找出平均启动距离最小的启动循环或恒定循环,12 之 2,步骤一,本章内容,流水线基本概念,非线性流水线的调度技术,无冲突调度方法,由预约表得到禁止向量,定义：将一条非线性流水线的全部各功能段禁止启动距离组合在一起形成的数列。,计算：将预约表中的每一行中随意两个“”之间的距离都计算出来，去掉重复的，由这些数形成禁止向量。,例子：上例所示非线性流水线的禁止向量为（2，4，6）。,12 之 3,步骤二,本章内容,流水线基本概念,非线性流水线的调度技术,无冲突调度方法,由禁止向量得到冲突向量,概念：冲突向量用一个m位的二进制数表示（其中m是禁止向量中的最大值），一般格式为C=（CmCm-1CiC2C1），若i在禁止向量中，则Ci =1，否则Ci =0，其中Cm确定为1。,例子：上例所示非线性流水线的冲突向量为C=（101010）。,12 之 4,步骤三（1）,本章内容,流水线基本概念,非线性流水线的调度技术,无冲突调度方法,由冲突向量构造调度流水线的状态图,将冲突向量C作为初始冲突向量送入一个m位逻辑右移移位器，移位m次；,若移出的是“0”，用移位器中的值与初始冲突向量作“按位或”运算，得到一个新的冲突向量；,若移出的是“1”，不作任何处理。,将中间形成的每一个新的冲突向量同样处理；,画出状态图。,在初始冲突向量和全部的新形成的冲突向量之间用带箭头的线连接，表示各种状态之间的转换关系。,12 之 5,步骤三（2）,本章内容,流水线基本概念,非线性流水线的调度技术,无冲突调度方法,12 之 6,步骤四（1）,本章内容,流水线基本概念,非线性流水线的调度技术,无冲突调度方法,在状态图中找出可用启动距离，并计算平均启动距离,在状态图中从初始状态动身，能构成一种间隔拍数呈周期性重复的方案就是可用启动距离。即：找出全部的简洁循环（是指在状态图中各种冲突向量只经过一次的启动循环）。,12 之 7,步骤四（2）,本章内容,流水线基本概念,非线性流水线的调度技术,无冲突调度方法,简单循环,平均启动距离,1，7,4,3，7,5,5，7,6,3，5，7,5,5，3，7,5,3，5,4,5,5,7,7,12 之 8,步骤五（1）,本章内容,流水线基本概念,非线性流水线的调度技术,无冲突调度方法,找出平均启动距离最小的启动循环或恒定循环,启动循环,（1，7）和（3，5）,恒定循环,（5）,12 之 9,步骤五（2）,本章内容,流水线基本概念,非线性流水线的调度技术,无冲突调度方法,12 之 10,S3,S2,S1,4,3,2,1,5,S4,6,7,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,S1,X1,X2,X1,X2,X3,X4,X3,X4,X5,X6,S2,X1,X2,X1,X2,X3,X4,X3,X4,X5,X6,S3,X1,X2,X1,X2,X3,X4,X3,X4,X5,X6,S4,X1,X2,X3,X4,X5,最小启动循环（,1,，,7,）的流水线工作状态,启动周期,重复启动周期,步骤五（3）,本章内容,流水线基本概念,非线性流水线的调度技术,无冲突调度方法,12 之 11,S3,S2,S1,4,3,2,1,5,S4,6,7,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,S1,X1,X2,X1,X3,X2,X4,X3,X5,X4,X6,S2,X1,X2,X1,X2,X3,X4,X3,X4,X5,S3,X1,X1,X2,X2,X3,X3,X4,X4,X5,S4,X1,X2,X3,X4,X5,最小启动循环（,3,，,5,）的流水线工作状态,启动周期,重复启动周期,步骤五（4）,本章内容,流水线基本概念,非线性流水线的调度技术,无冲突调度方法,12 之 12,S3,S2,S1,4,3,2,1,5,S4,6,7,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,S1,X1,X2,X1,X3,X2,X4,X3,S2,X1,X1,X2,X2,X3,X3,X4,S3,X1,X1,X2,X2,X3,X3,X4,X4,S4,X1,X2,X3,X4,最小恒定循环（,5,）的流水线工作状态,启动周期,重复启动周期,优化调度方法,本章内容,流水线基本概念,非线性流水线的调度技术,问题,当接受最小启动循环启动非线性流水线时，没有充分发挥非线性流水线的效率，因为流水线中的很多流水段还有空闲，即使最繁忙的流水段也有空闲。,解决,接受非线性流水线的优化调度方法（预留算法），可以使流水线的工作效率最高。,7 之 1,理论基础,本章内容,流水线基本概念,非线性流水线的调度技术,L.E.Shar于1972年提出流水线最小平均启动距离的限制范围并于1992年进行了证明：,最小平均启动距离的下限是预约表中随意一行里“”的最多个数。,最小平均启动距离小于等于状态图中随意一个简洁循环的平均启动距离。,最小平均启动距离的上限是冲突向量中1的个数再加上1。,7 之 2,预留算法,本章内容,流水线基本概念,非线性流水线的调度技术,确定流水线的最小启动距离,最小启动距离等于预约表中随意一行中“”的最大个数。,确定最小启动循环,为简化流水线的限制逻辑，一般接受恒定循环作为最小启动循环。,插入延迟进行预留,对预约表中随意一行中随意两个“”之间的距离是最小启动距离整数倍的通过插入延迟进行预留。,7 之 3,举例-,优化前（前例）,本章内容,流水线基本概念,非线性流水线的调度技术,S4,S3,S2,S1,7,6,5,4,3,2,1,时间,流水段,S,1,S,2,S,3,S,4,输入,输出,7 之 4,举例-,优化后,本章内容,流水线基本概念,非线性流水线的调度技术,S,1,S,2,S,3,S,4,输入,输出,D1,时间,1,2,3,4,5,6,7,8,功,能,段,S1,S2,S3,S4,延迟,D1,7 之 5,举例-,优化后,从状态图中很简洁可以看出：流水线的最小启动循环是（2）。,本章内容,流水线基本概念,非线性流水线的调度技术,7 之 6,举例-,优化后,在非线性流水线中，“”最多的流水段确定是“瓶颈”流水段。实现最优调度的目标是使“瓶颈”流水段处于劳碌状态，没有空闲周期。,本章内容,流水线基本概念,非线性流水线的调度技术,7 之 7,相关性分析技术,基本概念,资源相关,数据相关,限制相关,综合应用,循环处理,本章内容,基本概念,本章内容,相关性分析技术,概念,相关（Correlation or Dependency）也称为冲突（Hazard）是指邻近指令之间存在着某种关系，影响指令的重叠执行或流水线的正常运行。,内容,有三种类型的相关：,资源相关：争用部件。,数据相关：变更操作数的读写依次，使得依次执行与流水执行时结果不同。,限制相关：分支、转子程序、中断。,2,之,1,示例环境说明,本章内容,相关性分析技术,在介绍相关性分析技术时，我们以一个典型的,RISC,指令流水线（,MIPS64,指令集）为例进行介绍：,MIPS,基本流水线,MIPS,扩展流水线,2,之,2,MIPS,基本流水线,本章内容,相关性分析技术,示例环境说明,RISC指令集,接受MIPS64（MIPS的64位版本）的整数子集：ALU指令（5个时钟周期）、 load（5个时钟周期）/store（4个时钟周期）指令和分支指令（2个时钟周期）。,RISC指令的实现,每一条RISC指令的执行至多须要5个时钟周期：取指令周期（IF）、指令译码/读寄存器周期（ID）、执行/有效地址周期（EX）、访问存储器周期（MEM）和写回周期（WB）。,13,之 1,取指令周期（,IF）,本章内容,相关性分析技术,示例环境说明,IR MemPC,NPC PC+4,说明：,依据PC指示的地址从存储器中取指令并装入指令寄存器（IR），同时PC加4以获得下一条指令的地址。IR中保存下一个时钟周期须要的指令，NPC中保存下一条指令的PC。,13,之,2,图示IF,本章内容,相关性分析技术,示例环境说明,13,之,3,指令译码/读寄存器周期（,ID）,本章内容,相关性分析技术,示例环境说明,A Regsrs,B Regsrt,Imm IR的马上数字段进行符号扩展,ALUOutput NPC+(Imm,相关性分析技术,示例环境说明,13,之,5,执行/有效地址周期（,EX）,访问存储器,ALUOutputA+Imm,寄存器-寄存器ALU,ALUOutputA func B,寄存器-马上数ALU,ALUOutputA op Imm,说明：,Load/Store指令在本周期形成有效地址。ALU指令完成相应的ALU操作。,本章内容,相关性分析技术,示例环境说明,13,之,6,图示EX,本章内容,相关性分析技术,示例环境说明,13,之,7,访问存储器周期（,MEM）,本章内容,相关性分析技术,示例环境说明,LMD MemALUOutput or,MemALUOutput B,说明：,Load指令从存储器中读出数据并装入LMD（装入存储器数据）寄存器，Store指令将寄存器B中的数据写入存储器。,13,之,8,图示MEM,本章内容,相关性分析技术,示例环境说明,13,之,9,写回周期（,WB）,Load指令,RegsrtLMD,寄存器-寄存器ALU,Regsrd ALUOutput,寄存器-马上数ALU,Regsrt ALUOutput,说明：,将结果写入寄存器堆。寄存器的写入端口在两个目标中选择一个（rt or rd），具体选择哪一个要由操作码确定。,本章内容,相关性分析技术,示例环境说明,13,之 1,0,图示WB,本章内容,相关性分析技术,示例环境说明,13,之 1,1,时空图,本章内容,相关性分析技术,示例环境说明,指,令,时钟,1,2,3,4,5,6,7,8,9,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,13,之,12,MIPS,基本流水线的数据通路,13,之,13,IM ：,指令存储器,DM：,数据存储器,CC,：,时钟周期,写操作,（前半周期进行）,读操作,（后半周期进行）,MIPS,基本流水线的实现,9 之 9,MIPS,扩展流水线,本章内容,相关性分析技术,示例环境说明,3 之 1,在MIPS基本流水线中引入浮点操作功能。,主定点操作部件,负责load/store、定点ALU操作和分支操作（功能同MIPS基本流水线）。,浮点/定点乘法部件,负责浮点/定点乘法，接受流水设计。,浮点加法部件,负责处理浮点加、减法及定点数/浮点数之间的转换，接受流水设计。,浮点/定点除法部件,负责浮点/定点除法，不接受流水设计。,连接图,本章内容,相关性分析技术,示例环境说明,3 之 2,一组独立的浮点操作流水线时序,蓝色斜体的流水段须要数据，红色的流水段已经得到结果。,本章内容,相关性分析技术,示例环境说明,3 之 3,MUL.D,IF,ID,M1,M2,M3,M4,M5,M6,M7,MEM,WB,ADD.D,IF,ID,A1,A2,A3,A4,MEM,WB,L.D,IF,ID,EX,MEM,WB,S.D,IF,ID,EX,MEM,WB,资源相关,本章内容,相关性分析技术,因为资源冲突而导致流水线断流。,例1: 指重叠指令或流水线中的指令同时要用同一个功能部件，事实上是一种冲突。非线性流水线的调度就是为了尽量避开资源运用上的冲突。,例2: 后面介绍的RISC指令流水线当指令和数据共享同一个存储器时，也会出现资源冲突（见后图）。,4 之 1,MIPS,基本流水线当指令和数据共享同一个存储器时会出现资源冲突,4 之 2,IF,段,ID,段,EX,段,MEM,段,WB,段,资源相关,本章内容,相关性分析技术,缘由分析,主要有：,部分功能部件没有充分流水,资源没有充分重复设置,解决方法,可以接受推后处理法来解决：暂停相关指令的执行，直到所需的功能单元能够运用为止。,4 之 3,例 子,本章内容,相关性分析技术,指,令,时钟,1,2,3,4,5,6,7,8,9,load,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,4 之 4,时空图的另一种画法,数据相关,本章内容,相关性分析技术,数据相关类型,数据相关解决,动态调度技术,数据相关类型,本章内容,相关性分析技术,数据相关,“先写后读”相关,“先读后写”相关,“写写”相关,“先写后读”相关,（,RAW）,本章内容,相关性分析技术,数据相关,数据相关类型,概念,有两条相邻指令i和j， i在j之前执行，指令i将结果写入某个存储单元，而指令j从相同存储单元中读取该数据。假如指令j想在指令i写之前去读数据，则会发生“先写后读”相关，也称为写读相关、数据相关、 RAW相关、 WR相关等。,2 之 1,“先写后读”相关,（,RAW）,本章内容,相关性分析技术,数据相关,数据相关类型,例子,i：DADD,R1,R2,R3,;(R2)(R3)(R1),j：DSUB R4,R1,R5,;(R1)(R5)(R4),2 之 2,IF,段,ID,段,EX,段,MEM,段,WB,段,流水寄存器,“先读后写”相关,（,WAR）,本章内容,相关性分析技术,数据相关,数据相关类型,概念,有两条相邻指令i和j， i在j之前执行，指令i从某个存储单元中读取数据，而指令j将结果写入相同存储单元。假如指令j想在指令i读之前去写数据，则会发生“先读后写”相关，也称为读写相关、反相关、 WAR相关、 RW相关等。,2 之 1,“先读后写”相关,（,WAR）,本章内容,相关性分析技术,数据相关,数据相关类型,例子,i：DSUB,R4,R1,R5,;(R1)(R5)(R4),j：DADD,R1,R2,R3,;(R2)(R3)(R1),2 之 2,“写写,”,相关,（,WAW）,本章内容,相关性分析技术,数据相关,数据相关类型,概念,有两条相邻指令i和j， i在j之前执行，指令i将结果写入某个存储单元，而指令j也将结果写入相同存储单元。假如指令j想在指令i写之前去写该数据，则会发生“写写”相关，也称为写写相关、输出相关、 WAW相关、 WW相关等。,3 之 1,“写写,”,相关,（,WAW）,本章内容,相关性分析技术,数据相关,数据相关类型,3 之 2,例子,i：DSUB,R1,R4,R5,;(R4)(R5)(R1),j：DADD,R1,R2,R3,;(R2)(R3)(R1),“先写后读”相关在流水线依次执行和乱序执行时都可能发生，“先读后写”相关和“写写”相关只有在流水线乱序执行时才可能发生，而“读读”相关无需处理。,提 示,本章内容,相关性分析技术,数据相关,数据相关类型,3 之 3,数据相关解决,本章内容,相关性分析技术,数据相关,“先读后写”相关,“写写”相关,设置专用路径,推后处理,“先写后读”相关,寄存器换名,设置专用路径,思想,将结果干脆送到须要它的功能部件，即：一个结果能够从一个部件的输出干脆送到另一个部件的输入。,程序段,DADD,R1,R2,R3,DSUBR4,R1,R5,ANDR6,R1,R7,ORR8,R1,R9,XORR10,R1,R11,本章内容,相关性分析技术,数据相关,数据相关解决,3 之 1,“先写后读”数据相关,3 之 2,通过设置专用路径解决“先写后读”数据相关,3 之 3,推后处理,思想,对于接受设置专用路径无法解决的数据相关只有推后处理相关指令，直至数据就绪。,程序段,LD,R1,0(R2),DSUBR4,R1,R5,ANDR6,R1,R7,ORR8,R1,R9,本章内容,相关性分析技术,数据相关,数据相关解决,3 之 1,通过设置专用路径解决数据相关（,失败,）,3 之 2,失败,通过推后处理解决数据相关,3 之 3,指,令,时 钟,1,2,3,4,5,6,7,8,9,LD R1,0(R2),IF,ID,EX,MEM,WB,DSUB R4,R1,R5,IF,ID,EX,MEM,WB,AND R6,R1,R7,IF,ID,EX,MEM,WB,OR R8,R1,R9,IF,ID,EX,MEM,WB,指,令,时 钟,1,2,3,4,5,6,7,8,9,LD R1,0(R2),IF,ID,EX,MEM,WB,DSUB R4,R1,R5,IF,ID,stall,EX,MEM,WB,AND R6,R1,R7,IF,stall,ID,EX,MEM,WB,OR R8,R1,R9,stall,IF,ID,EX,MEM,WB,推后处理前的数据相关,寄存器换名,WAR,相关,WAW,相关,本章内容,相关性分析技术,数据相关,数据相关解决,2 之 1,A,C,A,C,B,B,B,i,j,i,j,A,C,A,C,B,B,B,i,j,i,j,寄存器换名举例,换名前,DIV.DF0,F2,F4,ADD.D,F6,F0,F8,S.DF6,0(R1),SUB.D,F8,F10,F14,MUL.D,F6,F10,F8,换名后,DIV.DF0,F2,F4,ADD.D,S,F0,F8,S.D,S,0(R1),SUB.D,T,F10,F14,MUL.D,F6,F10,T,本章内容,相关性分析技术,数据相关,数据相关解决,2 之 2,动态调度技术,本章内容,相关性分析技术,数据相关,引入,思想,方法,CDC,计分牌法,Tomasulo,算法,引 入,本章内容,相关性分析技术,数据相关,动态调度技术,DIV.D,F0,F2,F4,ADD.DF10,F0,F8,SUB.DF12,F8,F14,时间,1,2,3,4,26,27,28,29,30,DIV.D,IF,ID,DIV,MEM,WB,ADD.D,IF,ID,暂停,暂停,EX,MEM,WB,SUB.D,IF,ID,暂停,暂停,EX,MEM,WB,2 之 1,问题,在MIPS扩展流水线中，指令按序放射、按序执行和按序完成，RAW相关使ADD.D及后续指令在流水线中被暂停，即使后续指令与DIV.D、ADD.D指令没有冲突，这限制流水线的性能。,解决,假如指令按序放射、乱序执行和乱序完成，则可以削减暂停所带来的影响。,引 入,本章内容,相关性分析技术,数据相关,动态调度技术,2 之 2,思 想,本章内容,相关性分析技术,数据相关,动态调度技术,记录和检测指令相关，当指令的操作数就绪时就执行该指令（即：指令按序放射、乱序执行和乱序完成）以降低RAW相关的影响，接受寄存器换名技术来避开WAR、WAW相关的影响。,Tomasulo,算法,本章内容,相关性分析技术,数据相关,动态调度技术,概述,实现,举例,概 述,本章内容,相关性分析技术,数据相关,动态调度技术,Tomasulo,算法,Tomasulo算法是由R.M.Tomasulo于1967年首先提出，并最早在大型机IBM 360/91处理机的浮点处理部件中运用。 Tomasulo算法也称为公共数据总线（CDB）法、令牌法等，它接受乱序方式来提高流水线的性能，并通过分散限制的方法处理数据相关。,基于,Tomasulo,算法的,MIPS,浮点部件的基本结构,6,之 1,FP adders,Add1,Add2,Add3,FP multipliers,Mult1,Mult2,From Mem,FP Registers,Reservation,Stations,Common Data Bus (CDB),To Mem,FP Op,Queue,Load,Buffers,Store,Buffers,Load1,Load2,Load3,Load4,Load5,Load6,保留站,Op,操作类型。,Vj,和,Vk,存放两个源操作数的值。,Qj,和,Qk,存放产生相应源操作数的保留站。,对每个源操作数，,V,字段或,Q,字段中只有一个是有效的。,A,用于保存load/store操作的存储器地址信息。最初指令中的马上数存放于此，在地址计算后有效地址也存放于此。,Busy,指示该保留站及相关的功能部件是否正在运用。,本章内容,相关性分析技术,数据相关,动态调度技术,Tomasulo,算法,寄存器换名是通过保留站实现的，保留站的数据结构为：,6,之 2,存储设备,读数/写数缓冲器,每个缓冲器也都是保留站，字段同前。,浮点寄存器堆,每个寄存器都需设置Qi字段，用于保存保留站号。在该保留站中进行的操作，其结果将存入该寄存器。假如Qi为空，则表示当前不会有运算结果要存到该寄存器。,本章内容,相关性分析技术,数据相关,动态调度技术,Tomasulo,算法,6,之 3,指令执行过程,本章内容,相关性分析技术,数据相关,动态调度技术,Tomasulo,算法,放射,从浮点操作队列中取得一条指令。假如相应保留站空闲（即：没有结构冲突），则可以放射指令和发送数据。寄存器换名工作在本阶段进行。,执行,对操作数进行相应的操作。当指令所须要的源操作数都准备好，就可以执行该运算；否则监视CDB等待源操作数。,写回结果,当计算结果出来之后，送至CDB，进而写回到寄存器中，或被其它保留站读取。,6,之 4,指令格式,浮点运算指令,load,和,store,指令,MUL.D F4,，,F0,，,F2,rs,rd,rt,L.D F2,，,45,（,R3,）,rs,rt,imm,S.D F3,，,40,（,R4,）,rs,rt,imm,本章内容,相关性分析技术,数据相关,动态调度技术,Tomasulo,算法,6,之,5,j,k,j,j,k,A,A,指令执行的具体过程,6,之,6,举 例,程序,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,假设,各指令在“放射”和“写回结果”所花时钟周期数都为1，在“执行”阶段所花时钟周期数分别为：L.D为2，ADD.D和SUB.D为2，MUL.D为10，DIV.D为40。,本章内容,相关性分析技术,数据相关,动态调度技术,Tomasulo,算法,21 之 1,指令,指令状态,发射,执行,写回结果,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,站名,保留站,Busy,Op,Vj,Vk,Qj,Qk,A,Load1,Y,Load,RegsR2,34,Load2,Add1,Add2,Add3,Mult1,Mult2,寄存器状态,字段,F0,F2,F4,F6,F8,F10,F12,F30,Qi,Load1,CLOCK：1,21 之 2,指令,指令状态,发射,执行,写回结果,L.D F6,34(R2),1,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,站名,保留站,Busy,Op,Vj,Vk,Qj,Qk,A,Load1,Y,Load,RegsR2,34,Load2,Y,Load,RegsR3,45,Add1,Add2,Add3,Mult1,Mult2,寄存器状态,字段,F0,F2,F4,F6,F8,F10,F12,F30,Qi,Load2,Load1,CLOCK：2,21 之 3,指令,指令状态,发射,执行,写回结果,L.D F6,34(R2),2,L.D F2,45(R3),1,MUL.D F0,F2,F4,SUB.D F8,F6,F2,DIV.D F10,F0,F6,ADD.D F6,F8,F2,站名,保留站,Busy,Op,Vj,Vk,Qj,Qk,A,Load1,Y,Load,34+RegsR2,Load2,Y,Load,RegsR3,45,Add1,Add2,Add3,Mult1,Y,MUL,RegsF4,Load2,Mult2,寄存器状态,字段,F0,F2,F4,F6,F8,F10,F12,F30,Qi,Mult1,Load2,Load1,CLOCK：3,21 之 4,指令,指令状态,发射,执行,写回结果,L.D F6,34(R2),L.D F2,45(R3),2,MUL.D F0,F2,F4,SUB.D F8,F6,F2,DIV.D F10,F0,F6,ADD.D F6,F8,F2,站名,保留站,Busy,Op,Vj,Vk,Qj,Qk,A,Load1,N,Load2,Y,Load,45+,RegsR3,Add1,Y,SUB,Mem34+RegsR2,Load2,Add2,Add3,Mult1,Y,MUL,RegsF4,Load2,Mult2,寄存器状态,字段,F0,F2,F4,F6,F8
展开阅读全文