第5章标量处理机

1、兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤第第5章章 标量处理机标量处理机5.1 先行控制技术先行控制技术5.2 流水线技术流水线技术5.3 相关性分析技术相关性分析技术5.4 超标量处理机超标量处理机5.5 超流水线处理机超流水线处理机5.6 超标量超流水线处理机超标量超流水线处理机兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤5.1 5.1 先行控制技术先行控制技术5.1.1 指令的重叠执行方式指令的重叠执行方式5.1.2 先行控制方式的原理先行控制方式的原理5.1.3 处理机结构处理机结构5.1.4 指令执行序列指令执行序列5.1.5 先行缓冲栈先行缓冲栈兰州理工

2、大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤5.1.1 5.1.1 指令的重叠执行方式指令的重叠执行方式1.1.顺序执行方式顺序执行方式执行执行n n条指令所用的时间为：条指令所用的时间为： 如果每段时间都为t，则执行n条指令所用的时间为：T3 n t3 n t主要优点：主要优点：控制简单，节省设备控制简单，节省设备主要缺点：主要缺点：速度慢，功能部件的利用率低速度慢，功能部件的利用率低Ttttiiiin(取指令分析执行）1 取取指指令令k k 分分析析k k 执执行行k k 取取指指令令k k+ +1 1 分分析析k k+ +1 1 执执行行k k+ +1 1 兰州理工大学兰州理工大学兰

3、州理工大学 包仲贤包仲贤包仲贤2.2.一次重叠执行方式一次重叠执行方式如果两个过程的时间相等，则执行n条指令的时间为：T(1+2n)t1+2n)t主要优点：主要优点： 指令的执行时间缩短，指令的执行时间缩短， 功能部件的利用率明显提高。功能部件的利用率明显提高。主要缺点：主要缺点： 需要增加一些硬件，需要增加一些硬件， 控制过程稍复杂。控制过程稍复杂。取指令取指令 k k分析分析 k k执行执行 k k取取指指令令 k k+ +1 1分析分析 k+1k+1执行执行 k+1k+1取指令取指令k+2k+2分析分析 k+2k+2执行执行 k+2k+2兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤

4、包仲贤3.3.二次重叠执行方式二次重叠执行方式如果三个过程的时间相等，执行n条指令的时间为：T(2 2n n）t t在理想情况下，处理机中同时有三条指令在执行。处理机的结构要作比较大的改变，需要采用先行处理机的结构要作比较大的改变，需要采用先行控制技术。控制技术。 取取指指令令k k分分析析k k执执行行k k取取指指令令k k+ +1 1分分析析k k+ +1 1执执行行k k+ +1 1取取指指令令k k+ +2 2分分析析k k+ +2 2执执行行k k+ +2 2二二次次重重叠叠执执行行方方式式兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤5.1.2 5.1.2 先行控制方式

5、的原理先行控制方式的原理1.1.采用二次重叠执行方式必须解决两个问题：采用二次重叠执行方式必须解决两个问题：(1)(1)有独立的取指令部件、指令分析部件和指令执有独立的取指令部件、指令分析部件和指令执行部件行部件 把一个集中的指令控制器，分解成三个独立的控制器： 存储控制器、指令控制器、运算控制器存储控制器、指令控制器、运算控制器(2)(2)要解决访问主存储器的冲突问题要解决访问主存储器的冲突问题 取指令、分析指令、执行指令都可能要访问存储器兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤2.2.解决访存冲突的方法：解决访存冲突的方法：(1)(1)采用低位交叉存取方式采用低位交叉存取方

6、式： 这种方法不能根本解决冲突问题。指令、读操作数、写结果。(2)(2)两个独立的存储器两个独立的存储器：独立的指令存储器和数据独立的指令存储器和数据存储器。存储器。如果再规定，执行指令所需要的操作数和执行结果只写到通用寄存器，则取指令、分析指令和执行指令就可以同时进行。在许多高性能处理机中，有独立的指令Cache和数据Cache。这种结构被称为哈佛结构。兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤(3)(3)采用先行控制技术采用先行控制技术 采用先行控制技术的关键是缓冲技术和预处理采用先行控制技术的关键是缓冲技术和预处理技术。技术。缓冲技术通常用在工作速度不固定的两个功能部件之间

7、。设置缓冲栈的目的是用来以平滑功能部件之间的工作速度。在采用了缓冲技术和预处理技术之后，运算器能够专心于数据的运算，从而大幅度提高程序的执行速度。兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤 空间并行性空间并行性：设置多个独立的操作部件设置多个独立的操作部件 时间并行性时间并行性：分时使用同一个部件的不同部分分时使用同一个部件的不同部分 5.2.1 流水线工作原理流水线工作原理 5.2.2 流水线的分类流水线的分类 5.2.3 线性流水线的性能分析线性流水线的性能分析 5.2.4 非线性流水线的调度非线性流水线的调度5.2 5.2 流水线技术流水线技术兰州理工大学兰州理工大学兰州理

8、工大学 包仲贤包仲贤包仲贤5.2.1 5.2.1 流水线工作原理流水线工作原理1. 1. 流水寄存器流水寄存器流水线的每一个阶段称为流水步流水步、流水步骤、流流水段水段、流水线阶段、流水功能段、功能段功能段、流流水级水级、流水节拍等。在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门流水寄存器、流水锁存器、流水闸门寄存器等寄存器等。加入流水寄存器，会增加指令的执行时间。在一般流水线时空图中不画出流水寄存器。兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤2.2.一种指令流水线一种指令流水线一般4至12个流水段，8个流水段的称为超流水线处理机3.3.流水线

9、时空图流水线时空图 空空间间 执执行行部部件件 执执行行k k 执执行行k k+ +1 1 执执行行k k+ +2 2 执执行行k k+ +3 3 分分析析部部件件 分分析析k k 分分析析k k+ +1 1 分分析析k k+ +2 2 分分析析k k+ +3 3 取取指指令令部部件件 取取指指令令k k 取取指指令令k k+ +1 1 取取指指令令k k+ +2 2 取取指指令令k k+ +3 3 0 t1 t2 t3 t4 t5 时时间间 输输入入 输输出出 取取指指令令 i 分分析析 i 执执行行 i 流流水水线线 寄寄存存器器 流流水水线线 寄寄存存器器 t 兰州理工大学兰州理工大学兰

10、州理工大学 包仲贤包仲贤包仲贤 一个浮点加法器流水线的时空图一个浮点加法器流水线的时空图 空空 间间 规规 格格 化化 规规 格格 化化 1 1 规规 格格 化化 2 2 规规 格格 化化 3 3 规规 格格 化化 4 4 规规 格格 化化 5 5 尾尾 数数 加加 尾尾 数数 加加 1 1 尾尾 数数 加加 2 2 尾尾 数数 加加 3 3 尾尾 数数 加加 4 4 尾尾 数数 加加 5 5 对对 阶阶 对对 阶阶 1 1 对对 阶阶 2 2 对对 阶阶 3 3 对对 阶阶 4 4 对对 阶阶 5 5 求求 阶阶 差差 求求 阶阶 差差 1 1 求求 阶阶 差差 2 2 求求 阶阶 差差 3

11、 3 求求 阶阶 差差 4 4 求求 阶阶 差差 5 5 0 t1 t2 t3 t4 t5 t6 t7 t8 时时 间间 兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤4.4.流水线的主要特点流水线的主要特点只有连续提供同类任务才能发挥流水线效率只有连续提供同类任务才能发挥流水线效率尽量减少因条件分支造成的“断流”通过编译技术提供连续的相同类型操作每个流水线段都要设置一个流水寄存器每个流水线段都要设置一个流水寄存器时间开销：流水线的执行时间加长是流水线中需要增加的主要硬件各流水段的时间应尽量相等各流水段的时间应尽量相等 流水线处理机的基本时钟周期等于时间最长的流水段的时间长度。流水线

12、需要有流水线需要有“装入时间装入时间”和和“排空时间排空时间” 兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤5.2.2 5.2.2 流水线的分类流水线的分类1.1.线性流水线与非线性流水线线性流水线与非线性流水线 流水线的各个流水段之间是否有反馈信号线性流水线线性流水线（Linear Pipelining）： 每一个流水段都流过一次，而且仅流过一次非线性流水线非线性流水线（Nonlinear Pipelining）： 某些流水段之间有反馈回路或前馈回路。线性流水线能够用流水线连接图唯一表示非线性流水线必须用流水线连接图和流水线预约表共同表示兰州理工大学兰州理工大学兰州理工大学 包仲

13、贤包仲贤包仲贤2.2.按照流水线的级别来分按照流水线的级别来分 处理机级流水线处理机级流水线，又称为指令流水线指令流水线。 例如：在采用先行控制器的处理机中，各功能部件之间的流水线 输入 先行指令 缓冲栈 先行指令 分析器 先行读数栈 先行操作栈 指令 执行部件 后行 写数栈 输出 功能: 取指令 指令译码, 形成操作数地址 取操作数 形成RR*指令 执行算术 逻辑运算 向存储器 写结果 先行控制方式中的指令流水线 前馈回路前馈回路 输入输入S S1 1S S2 2S S3 3 输出输出反馈回路反馈回路一种简单的非线性流水线一种简单的非线性流水线兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲

14、贤包仲贤 部件级流水线部件级流水线(操作流水线操作流水线) 如浮点加法器流水线 宏流水线宏流水线(Macro Pipelining) 处理机之间的流水线称，每个处理机对同一个数据流的不同部分分别进行处理。 输输 入入 求求 阶阶 差差 对对 阶阶 尾尾 数数 加加 规规 格格 化化 输输 出出 t t1 t t2 t t3 t t4 输输 入入 处处理理机机 1 1 处处理理机机 2 2 处处理理机机 n n 输输 出出 功功能能: : 任任务务1 1 任任务务2 2 任任务务n n 存储器 存储器 存储器 兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤3. 3. 单功能流水线与多功

15、能流水线单功能流水线与多功能流水线 单功能流水线：单功能流水线： 只能完成一种固定功能的流水线。只能完成一种固定功能的流水线。 Cray-1计算机种有12条，YH-1计算机有18条 Pentium有一条5段定点和一条8段浮点流水线。 Pentium有两条定点和一条浮点指令流水线。 多功能流水线：多功能流水线： 流水线的各段通过不同连接实现不同功能流水线的各段通过不同连接实现不同功能 Texas公司的ASC机，8段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤 A B A B A B

16、A B输 入输 入输 入输 入求 阶 差求 阶 差求 阶 差求 阶 差对 阶对 阶对 阶对 阶尾 数 加尾 数 加尾 数 加尾 数 加规 格 化规 格 化规 格 化规 格 化尾 数 乘尾 数 乘尾 数 乘尾 数 乘累 加累 加累 加累 加输 出输 出输 出输 出g=f(A,B)定 点 乘浮 点 加浮 点 点 积(a)功 能 段 间 的 互 连 (b)定 点 乘 法 (c)浮 点 加 法 (d)浮 点 点 积兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤4.4.静态流水线与动态流水线静态流水线与动态流水线静态流水线静态流水线：同一段时间内，各个功能段只能按：同一段时间内，各个功能段只能

17、按照一种方式连接，实现一种固定的功能。照一种方式连接，实现一种固定的功能。空空间间浮浮点点加加法法定定点点乘乘法法输出1 12 23 3 n n- -1 1 n n1 1累加1 12 2尾数乘1 12 23 3规格化1 12 23 3 n n- -1 1 n n尾数加1 12 23 3 n n- -1 1 n n对阶1 12 23 3 n n- -1 1 n n求阶差1 12 23 3 n n- -1 1 n n输入1 12 23 3 n n- -1 1 n n1 12 23 34 4时时间间静静态态流流水水线线时时空空图图兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤动态流水线动态

18、流水线：在同一段时间内，各段可以按照不：在同一段时间内，各段可以按照不同的方式连接，同时执行多种功能。同的方式连接，同时执行多种功能。 空空间间 浮浮点点加加法法 定定点点乘乘法法 输输入入 1 1 2 2 3 3 n n- -1 1 n n 1 1 2 2 3 3 求求阶阶差差 1 1 2 2 3 3 4 4 对对阶阶 1 1 2 2 3 3 4 4 5 5 尾尾数数加加 1 1 2 2 3 3 n n- -1 1 n n 规规格格化化 1 1 2 2 3 3 n n- -1 1 n n 尾尾数数乘乘 1 1 2 2 3 3 n n- -1 1 n n 累累加加 1 1 2 2 3 3 n

19、n- -1 1 n n 输输入入 1 1 2 2 3 3 n n- -1 1 n n 1 1 2 2 3 3 4 4 5 5 6 6 时时间间 动动态态流流水水线线时时空空图图 兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤5.5.流水线的其他分类方法流水线的其他分类方法按照数据表示方式：标量流水线和向量流水线标量流水线和向量流水线按照控制方式：同步流水线和异步流水线同步流水线和异步流水线顺序流水线与乱序流水线顺序流水线与乱序流水线，乱序流水线又称为无序流水线、错序流水线或异步流水线等。 输输入入 就就绪绪 回回答答 S1 就就绪绪 回回答答 S2 就就绪绪 回回答答 Sn 输输出出

20、 就就绪绪 回回答答 一种异步流水线 兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤5.2.3 5.2.3 线性流水线的性能分析线性流水线的性能分析 主要指标：吞吐率、加速比和效率吞吐率、加速比和效率1.1.吞吐率（吞吐率（Though PutThough Put）流水线吞吐率的最基本公式：流水线吞吐率的最基本公式： 其中：n为任务数， k为完成n个任务所用的时间。各段执行时间相等，输入连续任务情况下，完成n个任务需要的总时间为： Tk(kn1) t 其中：k 为流水线的段数，t为时钟周期。T PnTk兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤 Tk= k t + (n

21、-1) t = (k+n-1) t 空空间间S4123n-1nS3123n-1nS2123n-1nS11 12 23 3n n- -1 1n n时时间间kt(n1)tnt(k1)tT 吞吐率为：吞吐率为： 最大吞吐率为：最大吞吐率为：TPnknt()1 nTPLimnknttmax() 11兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤 各段时间不等，完成各段时间不等，完成n n个连续任务：个连续任务： 吞吐率：吞吐率： 最大吞吐率：最大吞吐率： 流水线各段执行时间不相等的解决办法流水线各段执行时间不相等的解决办法TPntntttiikk1121() max(,),max(121kt

22、ttTP 输输入入S1S2S3S4输输出出 t1 t t23 t t3 t t4 t兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤(1)(1)将将“瓶颈瓶颈”部分再细分部分再细分（如果可分的话）（如果可分的话）空空间间S4123nS3123nS2123nS1123n时时间间 kiit1（n1） t2Tk各段执行时间不相等的流水线及其时空图输输入入S1S2-1S2-2S2-3S3S4输输出出 t t t t t t“瓶瓶颈颈”流流水水段段再再次次细细分分 S2 (3 t)兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤 空空间间 S4 1 2 3 4 5 6 n-2 n-1 n

23、 S3 1 2 3 4 5 6 n-2 n-1 n S2-3 3 6 n S2-2 2 5 n-1 S2-1 1 4 n-2 S1 1 2 3 4 5 6 n-2 n-1 n 时时间间 流流水水段段重重复复设设置置的的流流水水线线 ( (2 2) )“瓶瓶颈颈“流流水水段段重重复复设设置置：增加分配器和收集器 S2-3 输输入入 S1 S2-2 S3 S4 输输出出 t1 t t3 t t4 t S2-1 t23 t 兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤2.2.加速比（加速比（SpeedupSpeedup） 计算加速比的基本公式：计算加速比的基本公式： 各段执行时间相等，输

24、入连续任务情况下, 加速比： 最大加速比： 各段时间不等，输入连续任务情况下, 实际加 速比为：STTk顺序执行时间流水线执行时间0Sk ntkntk nkn () 11SLimk nknknmax1Snttntttiikiikk 11121() m ax(,）兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤 当流水线段数增加时，需要连续输入的任务 数也必须增加 加加速速比比 S 10 加加 k=10 段段 8 速速 6 比比 k=6 段段 4 2 1 1 2 4 8 16 32 64 128 n 任任 务务 个个 数数兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤3.3.效

25、率（效率（EfficiencyEfficiency）计算流水线效率的一般公式：计算流水线效率的一般公式：各流水段时间相等，输入n个连续任务，流水线的效率为：最高效率为：各流水段时间不等，输入n个连续任务，流水 线效率为： EnkTk Tk个任务占用的时空区个流水段的总的时空区0Ek ntkkntnkn () 11ELimnknnmax11Entktntttiikiikk 11121)m ax(,)（兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤各段设备量或价格不等时，流水线的效率为：流水线的效率为： 即： 其中，aik，且k。流水线的吞吐率、流水线的吞吐率、加速比与效率的关系：加速比

26、与效率的关系：因为：因此：ETPt，SkE空区个流水段的总的加权时区个任务占用的加权时空knE EnataatntttiiikiIikiiikn111121) max(,)（TPnknt() 1 Sknkn 1Enkn1兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤4. 4. 流水线最佳段数的选择流水线最佳段数的选择采用顺序执行方式完成一个任务的时间为t在同等速度的 k 段流水线上执行一个任务的时间为：tkd (d为流水锁存器的延迟时间)流水线的最大吞吐率为：P=1(tkd)流水线的总价格估计为：Cab k， 其中：a为功能段身的总价格， b为每个锁存器的价格 A.G.Larson把

27、流水线的性能价格比PCR定义为：PCRPCt kd abk11/兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤 求PCR的最大值为：ktadb000)()()(0)(1)(0)1/1(2kbdatdktbkbkadkbkadktbkadktkbkadkt 性能价格比PCR 峰值 最佳值(k0) 流水线段数k兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤5. 5. 流水线性能分析举例流水线性能分析举例对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。对于输入不连续任务，或多功能流水线，通常采用基本公式计算。例例5.2： 用一

28、条4段浮点加法器流水线求8个浮点数的和：ZABCDEFGH兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤解：解： Z(AB)(CD)(EF)(GH) 空空间间 周周期期 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 1 11 1 1 12 2 1 13 3 1 14 4 1 15 5 规规格格化化 1 1 2 2 3 3 4 4 5 5 6 6 7 7 尾尾数数加加 1 1 2 2 3 3 4 4 5 5 6 6 7 7 对对阶阶 1 1 2 2 3 3 4 4 5 5 6 6 7 7 求求阶阶差差 1 1 2 2 3 3 4 4 5 5 6

29、6 7 7 时时间间 加加数数 A A C C E E G G A A+ +B B E E+ +F F A A+ +B B+ +C C+ +D D 加加数数 B B D D F F H H C C+ +D D G G+ +H H E E+ +F F+ +G G+ +H H 结结果果 A A+ +B B C C+ +D D E E+ +F F g g+ +H H A A+ +B B+ +C C+ +D D Z Z E E+ +F F+ +G G+ +H H 用用一一条条4 4段段浮浮点点加加法法器器流流水水线线求求8 8个个数数之之和和的的流流水水线线时时空空图图 兰州理工大学兰州理工大学兰州理

30、工大学 包仲贤包仲贤包仲贤解：解： 7 个个浮浮点点加加法法共共用用了了 15 个个时时钟钟周周期期。 流流水水线线的的吞吞吐吐率率为为：TPnTttk7150 471 流流水水线线的的加加速速比比为为：STTttk 047151 87 流流水水线线的的效效率率为为：ETk Tttk 0474 150 47 3636/206/206Computer architectureComputer architecture 例例 设在下图所示的静态流水线上计算：设在下图所示的静态流水线上计算： 流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中，流水线的输出可以直接返回输入端或暂存于相应的流水寄

31、存器中，试计算其吞吐率、加速比和效率。试计算其吞吐率、加速比和效率。)(41iiiBA 1 2 3 4 5 乘法乘法 加减法加减法 6 7 8 ( (每段的时间都为每段的时间都为t t) ) 时间 段 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 输 入 A1 B1 A2 B2 A3 B3 A4 B4 A B C D A B C D AB CD AB CD ABCD A=A1+B1 B=A2+B2 C=A3+B3 D=A4+B4 tTP18721836ttS25. 01884364E3838/206/206Comp

32、uter architectureComputer architecturep在在1818个个t t时间中，给出了时间中，给出了7 7个个结果。吞吐率为：结果。吞吐率为： tTP187p 不用流水线，由于一次求和需不用流水线，由于一次求和需6 6t t，一次求积需一次求积需4 4t t， 则产生上述则产生上述7 7个结果共需个结果共需（4 46+36+34 4）t t = 36 = 36t t 加速比为加速比为（3 3）计算性能）计算性能21836ttS3939/206/206Computer architectureComputer architecturep 流水线的效率流水线的效率 25

33、. 01884364E可以看出，在求解此问题时，该流水线的效率不高。 为什么？段时间4040/206/206Computer architectureComputer architecture主要原因q多功能流水线在做某一种运算时，总有一些段是空多功能流水线在做某一种运算时，总有一些段是空闲的。闲的。q静态流水线在进行功能切换时，要等前一种运算全静态流水线在进行功能切换时，要等前一种运算全部流出流水线后才能进行后面的运算。部流出流水线后才能进行后面的运算。q运算之间存在关联，后面有些运算要用到前面运算运算之间存在关联，后面有些运算要用到前面运算的结果。的结果。q流水线的工作过程有建立与排空部分

34、。流水线的工作过程有建立与排空部分。 4141/206/206Computer architectureComputer architecture 例例 有一条动态多功能流水线由有一条动态多功能流水线由5 5段组成，加法用段组成，加法用1 1、3 3、4 4、5 5段，乘法用段，乘法用1 1、2 2、5 5段，第段，第2 2段的时间为段的时间为2 2t t，其余各段时间均，其余各段时间均为为t t，而且流水线的输出可以直接返回输入端或暂存于相应的，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。若在该流水线上计算流水寄存器中。若在该流水线上计算: : 试计算其吞吐率、加速比和效率

35、。试计算其吞吐率、加速比和效率。)(41iiiBA 1 2 3 4 5 乘法乘法 加法加法 t 2t t t t 4242/206/206Computer architectureComputer architecture解解: : (1) (1) 选择适合于流水线工作的算法选择适合于流水线工作的算法p应先计算应先计算A A1 1B B1 1、A A2 2B B2 2、A A3 3B B3 3和和A A4 4B B4 4；p再计算再计算( (A A1 1B B1)1)( (A A2 2B B2)2) ( (A A3 3B B3)3)( (A A4 4B B4)4)；p然后求总的累加结果。然后求

36、总的累加结果。(2) (2) 画出时空图画出时空图(3) (3) 计算性能计算性能4343/206/206Computer architectureComputer architecture3.3 流水线的性能指标 时间 段 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 输 入 A1 B1 A2 B2 A3 B3 A4 B4 A B C D A B C D AB CD AB CD ABCD A=A1B1 B=A2B2 C=A3B3 D=A4B4 18 56. 11828ttStTP18731. 01854344E兰州理工大学兰州理工

37、大学兰州理工大学 包仲贤包仲贤包仲贤5.2.4 5.2.4 非线性流水线的调度非线性流水线的调度非线性流水线调度的任务是要找出一个最小的循环周期，非线性流水线调度的任务是要找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各个功能段按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。都不会发生冲突，而且流水线的吞吐率和效率最高。1.1.非线性流水线的表示非线性流水线的表示线性流水线能够用流水线连接图唯一表示对于非线形流水线，连接图不能唯一表示工作流程，因此，引入流水线预约表例如：兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤 输输

38、出出输输入入S1S2S3S4前馈线反馈线 非线形流水线的连接图和预约表非线形流水线的连接图和预约表时时间间功功能能段段1234567S1S2S3S4兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤 时时 间间 功功 能能 段段 1 2 3 4 5 6 7 S1 S2 S3 S4 输输出出S4输输入入S1S2S3前前馈馈线线反反馈馈线线 输输出出输输入入S1S2S3S4前馈线反馈线 一张预约表可能与多个流水线连接图一张预约表可能与多个流水线连接图相对应相对应兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤 时时 间间 功功 能能 段段 1 2 3 4 5 6 7 S1 S2 S3

39、 S4 输输 出出输输 入入S1S2S3S4前 馈 线反 馈 线 一个流水线连接图对应与多张预约一个流水线连接图对应与多张预约表表 时时 间间 功功 能能 段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 S1 S2 S3 S4 兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤2.2.非线性流水线的冲突非线性流水线的冲突 启动距离：启动距离：连续输入两个任务之间的时间间隔 流水线冲突：流水线冲突：几个任务争用同一个流水段启启动动距距离离为为 3 3 的的流流水水线线冲冲突突情情况况 时时间间 功功能能段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9

40、9 1 10 0 1 11 1 S1 X X1 1 X X1 1X X2 2 X X1 1X X2 2X X3 3 X X2 2X X3 3X X4 4 S2 X X1 1 X X1 1X X2 2 X X2 2X X3 3 X X3 3X X4 4 S3 X X1 1 X X2 2 X X1 1 X X3 3 X X2 2 X X4 4 S4 X X1 1 X X2 2 X X3 3 启启动动距距离离为为 2 2 的的流流水水线线冲冲突突情情况况 时时间间 功功能能段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 1 11 1 S S1 1 X X1

41、 1 X X2 2 X X1 1 X X3 3 X X2 2 X X1 1X X4 4 X X3 3 X X2 2X X5 5 X X4 4 X X3 3X X6 6 S S2 2 X X1 1 X X2 2 X X1 1 X X3 3 X X2 2 X X4 4 X X3 3 X X5 5 X X4 4 S S3 3 X X1 1 X X2 2 X X1 1X X3 3 X X2 2X X4 4 X X3 3X X5 5 S S4 4 X X1 1 X X2 2 X X3 3 X X4 4 X X5 5 启启动动距距离离为为 5 5 时时的的流流水水线线不不冲冲突突 时时间间 功功能能段段

42、1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 1 11 1 S S1 1 X X1 1 X X1 1 X X2 2 X X1 1 X X2 2 X X3 3 S S2 2 X X1 1 X X1 1 X X2 2 X X2 2 S S3 3 X X1 1 X X1 1 X X2 2 X X2 2 S S4 4 X X1 1 X X2 2 启启动动周周期期 重重复复启启动动周周期期 启动距离为启动距离为(1,7)(1,7)循环时的流水线预约表循环时的流水线预约表 时间时间 功能段功能段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

43、 1010 1111 1212 1313 1414 1515 1616 S S1 1 X X1 1 X X2 2 X X1 1 X X2 2 X X1 1 X X2 2 X X3 3 X X4 4 X X3 3 X X4 4 X X3 3 X X4 4 S S2 2 X X1 1 X X2 2 X X1 1 X X2 2 X X3 3 X X4 4 X X3 3 X X4 4 S S3 3 X X1 1 X X2 2 X X1 1 X X2 2 X X3 3 X X4 4 X X3 3 X X4 4 S S4 4 X X1 1 X X2 2 X X3 3 X X4 4 启动周期启动周期 重复启

44、动周期重复启动周期 兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤3.3.无冲突调度方法无冲突调度方法由E.S.Davidson及其学生于1971年提出禁止向量禁止向量：预约表中每一行任意两个“”之间距离的集合。上例中为（3 3，4 4，6 6）冲突向量冲突向量：C（CmCm-1C2C1） 其中：m是禁止向量中的最大值。 如果i在禁止向量中，则Ci1，否则Ci0。 上例中C C(101100)(101100)时时 间间 功功 能能 段段 1 2 3 4 5 6 7 S1 S2 S3 S4 兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤例例5.35.3：一条4功能段的非线性流

45、水线，每个功能段的延迟时间都相等，它的预约表如下： (1)写出流水线的禁止向量和初始冲突向量。 (2)画出调度流水线的状态图。 (3)求最小启动循环和最小平均启动距离。 (4)求平均启动距离最小的恒定循环。时 间 功能段 1 2 3 4 5 6 7 S1 X X S2 X X S3 X X S4 X 兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤解解：(1)(1)禁止向量为：禁止向量为：(2，4，6) 初始冲突向量：初始冲突向量：S = 101010S = 101010(2)(2)构造状态图构造状态图 S S逻辑右移逻辑右移2 2、4 4、6 6位时，不作任何处理，位时，不作任何处理

46、， 逻辑右移逻辑右移1 1、3 3、5 5和大于等于和大于等于7 7时：时： S右移1位之后：010101101010111111111111， S右移3位之后：000101101010101111101111， S右移5位之后：000001101010101011101011， S右移7位或大于7位后：还原到它本身。兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤101111右移5位之后：000001101010101011101011，101011右移3位之后：000101101010101111101111，101011右移5位之后：00000110101010101110101

47、1。7*07*153 7*7*15 305非非线线性性流流水水线线的的状状态态图图兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤简单循环：简单循环：状态图中各种冲突向量只经过一次的状态图中各种冲突向量只经过一次的启动循环。启动循环。(3)(3)最小的启动循环最小的启动循环为为（1，7）和（3，5）, 平均启动距离为平均启动距离为 4 4。(4)(4)启动距离最小的恒定循环为（启动距离最小的恒定循环为（5 5）简简 单单 循循 环环平平 均均 启启 动动 距距 离离（ 1 1， 7 7）4 4（ 3 3， 7 7）5 5（ 5 5， 7 7）6 6（ 3 3， 5 5， 7 7）5 5

48、（ 5 5， 3 3， 7 7）5 5（ 3 3， 5 5）4 4（ 5 5）5 5（ 7 7）7 7兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤最小启动循环最小启动循环(3,5)(3,5)的流水线工作状态的流水线工作状态时间时间功能段功能段1 12 23 34 45 56 67 78 89 91010 1111 1212 1313 1414 1515S S1 1X X1 1X X2 2X X1 1X X3 3X X2 2X X4 4X X3 3S S2 2X X1 1X X2 2X X1 1X X2 2X X3 3X X4 4X X3 3S S3 3X X1 1X X1 1X X

49、2 2X X2 2X X3 3X X3 3X X4 4S S4 4X X1 1X X2 2X X3 3X X4 4启动周期启动周期重复启动周期重复启动周期最最小小启启动动循循环环( (1 1, ,7 7) )的的流流水水线线工工作作状状态态 时时间间 功功能能段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 1 11 1 1 12 2 1 13 3 1 14 4 1 15 5 S S1 1 X X1 1 X X2 2 X X1 1 X X2 2 X X3 3 X X4 4 X X3 3 S S2 2 X X1 1 X X2 2 X X1 1 X X2

50、2 X X3 3 X X4 4 X X3 3 X X4 4 S S3 3 X X1 1 X X2 2 X X1 1 X X2 2 X X3 3 X X4 4 X X3 3 X X4 4 S S4 4 X X1 1 X X2 2 X X3 3 X X4 4 启启动动周周期期 重重复复启启动动周周期期 恒恒定定启启动动循循环环( (5 5) )的的流流水水线线工工作作状状态态 时时间间 功功能能段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 1 11 1 1 12 2 1 13 3 1 14 4 1 15 5 S S1 1 X X1 1 X X2 2 X

51、 X1 1 X X3 3 X X2 2 S S2 2 X X1 1 X X1 1 X X2 2 X X2 2 X X3 3 S S3 3 X X1 1 X X1 1 X X2 2 X X2 2 X X3 3 X X3 3 S S4 4 X X1 1 X X2 2 X X3 3 启启动动周周期期 重重复复启启动动周周期期 兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤4.4.优化调度方法优化调度方法L.E.Shar于1972年提出流水线最小平均启动距离的限制范围： (1) (1)最小平均启动距离的下限是预约表中任意一最小平均启动距离的下限是预约表中任意一行里行里“”的最多个数。的最多个

52、数。 (2) (2)最小平均启动距离小于等于状态图中任意一最小平均启动距离小于等于状态图中任意一个简单循环的平均启动距离。个简单循环的平均启动距离。 (3) (3)最小平均启动距离的上限是冲突向量中最小平均启动距离的上限是冲突向量中1 1的的个数再加上个数再加上1 1。1992年，L.E.Shar又证明了上述限制范围。最有用的是第1条。预约表中“”最多的行一定是瓶颈流水段瓶颈流水段兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤对于例5.3的预约表，在同一行中“”最多的为2个，因此，最小平均距离可以达到最小平均距离可以达到2。最小启动循环可以是(2)、(1,3)、(1,1,4)、(1,

53、2,3)、。现取恒定循环恒定循环(2)(2)。每一行中与第每一行中与第1 1个个“”的距离为的距离为2 2的倍数的位置的倍数的位置都要预留出来。都要预留出来。 S3行的第2个“”从周期5延迟到周期6。为此， S2行的第2个“”从周期6延迟到周期7； S1行的第2个“”从周期7延迟到周期8。实际上，只要在流水段S4的输出端到流水段S3的输入端中间插入一个非计算延迟非计算延迟D1。兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤采采用用预预留留调调度度算算法法的的预预约约表表时时 间间12345678S1S2S3功功能能段段S4延延迟迟 D1注注：表表示示由由D D1 1延延迟迟一一个个时

54、时钟钟周周期期兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤有有 非非 计计 算算 延延 迟迟 的的 流流 水水 线线 状状 态态 图图8 8* * 0 0 0 08 8* * 8 8* *1 1 2 2 4 4 6 6 8 8* * 0 0 0 0 0 0 1 12 2 4 4 6 6 增增加加了了一一个个非非计计算算延延迟迟流流水水段段 D1的的流流水水线线连连接接图图 输输出出输输入入S1S2S3S4D1兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤按按照照最最小小启启动动循循环环（2 2）工工作作的的流流水水线线预预约约表表 时时间间 1 1 2 2 3 3 4 4

55、 5 5 6 6 7 7 8 8 9 9 1 10 0 1 11 1 1 12 2 功功 S S1 1 X X1 1 X X2 2 X X3 3 X X4 4 X X1 1 X X5 5 X X2 2 X X6 6 X X3 3 能能 S S2 2 X X1 1 X X2 2 X X3 3 X X1 1 X X4 4 X X2 2 X X5 5 X X3 3 X X6 6 段段 S S3 3 X X1 1 X X2 2 X X1 1 X X3 3 X X2 2 X X4 4 X X3 3 X X5 5 X X4 4 S S4 4 X X1 1 X X2 2 X X3 3 X X4 4 X X5

56、 5 延延 D D1 1 X X1 1 X X2 2 X X3 3 X X4 4 在非线性流水线中，“”最多的流水段一定是“瓶颈“流水段。实现最优调度的目标是使“瓶颈瓶颈”流水段处于忙碌流水段处于忙碌状态，没有空闲周期。状态，没有空闲周期。最优调度方法能够使非线性流水线的吞吐率、加速比和效率达到最优。兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤5.3 5.3 相关性分析技术相关性分析技术资源相关：资源相关：资源相关是指多条指令进入流水线后在资源相关是指多条指令进入流水线后在同一机器时钟周期内争用同一个功能部件所发生的同一机器时钟周期内争用同一个功能部件所发生的冲突。假定一条指令流水

57、线由冲突。假定一条指令流水线由五段组成五段组成。数据相关：数据相关：在一个程序中，如果必须等前一条指令在一个程序中，如果必须等前一条指令执行完毕后，才能执行后一条指令，那么这两条指执行完毕后，才能执行后一条指令，那么这两条指令就是数据相关的。令就是数据相关的。控制相关：控制相关：控制相关冲突是由转移指令引起的。当控制相关冲突是由转移指令引起的。当执行转移指令时，依据转移条件的产生结果，可能执行转移指令时，依据转移条件的产生结果，可能为顺序取下条指令；也可能转移到新的目标地址取为顺序取下条指令；也可能转移到新的目标地址取指令，从而使流水线发生断流。指令，从而使流水线发生断流。兰州理工大学兰州理工

58、大学兰州理工大学 包仲贤包仲贤包仲贤解决资源相关冲突的办法解决资源相关冲突的办法：第第I4I4条指令停顿一拍后再启动；条指令停顿一拍后再启动；增设一个存储器，将指令和数据分别放在两个存储器中。增设一个存储器，将指令和数据分别放在两个存储器中。 如果数据和指令放在同一个如果数据和指令放在同一个存储器中且只有一个访问口时，存储器中且只有一个访问口时，便发生两条指令争用存储资源的便发生两条指令争用存储资源的相关冲突。相关冲突。5.3.1 资源相关资源相关n 先行指令缓冲栈作为主存储器与指令分析器之间的一个缓冲部件，用它来平滑主存储器和指令分析器的工作。当指令分析器分析某一条指令所需要的时间比较长，或

59、者主存储器有空闲时，就从主存储器中多取出几条指令存放在先行指令缓冲栈中。而当指令分析器分析指令很快，或者主存储器比较忙时，指令分析器也能够从先行指令缓冲栈中得到所需要的指令。兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤2.2.解决访存冲突的方法：解决访存冲突的方法：(1)(1)采用低位交叉存取方式采用低位交叉存取方式： 这种方法不能根本解决冲突问题。指令、读操作数、写结果。(2)(2)两个独立的存储器两个独立的存储器：独立的指令存储器和数据独立的指令存储器和数据存储器。存储器。如果再规定，执行指令所需要的操作数和执行结果只写到通用寄存器，则取指令、分析指令和执行指令就可以同时进行。

60、在许多高性能处理机中，有独立的指令Cache和数据Cache。这种结构被称为哈佛结构。兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤(3)(3)采用先行控制技术采用先行控制技术 采用先行控制技术的关键是缓冲技术和预处理采用先行控制技术的关键是缓冲技术和预处理技术。技术。缓冲技术通常用在工作速度不固定的两个功能部件之间。设置缓冲栈的目的是用来以平滑功能部件之间的工作速度。在采用了缓冲技术和预处理技术之后，运算器能够专心于数据的运算，从而大幅度提高程序的执行速度。兰州理工大学兰州理工大学兰州理工大学 包仲贤包仲贤包仲贤先先行行指指令令缓缓冲冲栈栈指指令令分分析析器器主主存存存存储储先先行