计算机系统结构05标量处理机121105

1、1 第第5 5章章 标量处理机标量处理机 5.1 5.1 流水线技术流水线技术 5.2 5.2 相关性分析相关性分析 5.3 5.3 动态调度技术动态调度技术 5.4 5.4 超标量处理机超标量处理机 5.5 5.5 超流水处理机超流水处理机 5.6 5.6 超标量超流水处理机超标量超流水处理机 习题习题: :3 3、5 5、6 6、7 7、8 8、1515、1616 2 5.1 流水线技术流水线技术 空间并行性：空间并行性：设置多个独立的操作部件设置多个独立的操作部件 时间并行性：时间并行性：分时使用同一个部件的不同部分分时使用同一个部件的不同部分 5.1.1 指令的重叠执行指令的重叠执行

2、5.1.2 流水线工作原理流水线工作原理 5.1.3 流水线的性能分析流水线的性能分析 5.1.4 非线性流水线调度非线性流水线调度 3 5.1.1 指令的重叠执行指令的重叠执行 1、顺序执行方式。、顺序执行方式。 执行执行n条指令所用的时间为：条指令所用的时间为： 如果每段的时间都为如果每段的时间都为t，则执行，则执行n条指令所用的时间为：条指令所用的时间为： T=3 n t 主要优点主要优点:控制简单，节省设备。控制简单，节省设备。 主要缺点主要缺点:速度慢速度慢,功能部件的利用率很低。功能部件的利用率很低。 取取 指指 令令k k 分分 析析k k 执执 行行k k 取取 指指 令令k

3、k+ +1 1 分分 析析k k+ +1 1 执执 行行k k+ +1 1 Ttttiii i n ( 取指令分析执行） 1 4 2、一次重叠执行方式、一次重叠执行方式。 如果两个过程的时间均相等，则执行如果两个过程的时间均相等，则执行n条指令所条指令所 用的时间为：用的时间为： T(12n）t 主要优点：主要优点： 一是指令的执行时间缩短，二是功能部件的一是指令的执行时间缩短，二是功能部件的 利用利用率率明显提高。明显提高。 主要缺点：主要缺点： 需要增加一些硬件，控制过程也要复杂一些需要增加一些硬件，控制过程也要复杂一些 取指令取指令 k k分析分析 k k执行执行 k k 取取指指令令

4、k k+ +1 1分析分析 k+1k+1执行执行 k+1k+1 取指令取指令 k+2k+2 分析分析 k+2k+2执行执行 k+2k+2 5 3、二次重叠执行方式、二次重叠执行方式 如果执行三如果执行三个个过程的时间相等，则执行过程的时间相等，则执行n条指令所用的时条指令所用的时 间为：间为： T(2n）t 在理想情况下，处理机中同时有三条指令在执行。在理想情况下，处理机中同时有三条指令在执行。 处理机的结构要比较大的改变，需要采用流水线技术处理机的结构要比较大的改变，需要采用流水线技术 和缓存技术。和缓存技术。 取指令取指令 k k分析分析 k k执行执行 k k 取指令取指令 k+1k+1

5、分析分析 k+1k+1执行执行 k+1k+1 取指令取指令 k+2k+2分析分析 k+2k+2执行执行 k+2k+2 二次重叠执行方式二次重叠执行方式 6 5.1.2 流水线工作原理流水线工作原理 1.流水线寄存器流水线寄存器 流水线的每一个阶段称为流水线的每一个阶段称为流水步流水步、流水、流水 步骤、流水段、流水线阶段、流水功能、步骤、流水段、流水线阶段、流水功能、功功 能段、流水级能段、流水级、流水节拍等。、流水节拍等。 在每一个流水段的末断或开头必须设置在每一个流水段的末断或开头必须设置 一个寄存器，称为一个寄存器，称为流水线寄存器、流水锁存流水线寄存器、流水锁存 存器、流水寄存器等。存

6、器、流水寄存器等。 加入流水线寄存器，会增加指令执行时间。加入流水线寄存器，会增加指令执行时间。 在一般流水线时空图中不画出流水线寄存在一般流水线时空图中不画出流水线寄存 器。器。 7 2.一种指令流水线一种指令流水线 一般一般4至至20个流水段，大于等于个流水段，大于等于8个流水段称个流水段称 为为超流水线超流水线。 3.流水线时空图流水线时空图 输入输入 输出输出 取指令取指令 i 分析分析 i 执行执行 i 流水线流水线 寄存器寄存器 流水线流水线 寄存器寄存器 t 空间空间 执行部件执行部件 执行执行 k k 执行执行 k+1k+1 执行执行 k+2k+2 执行执行 k+3k+3 分析

7、分析部件部件 分析分析 k k 分析分析 k+1k+1 分析分析 k+2k+2 分析分析 k+3k+3 取指令部件取指令部件 取指令取指令 k k 取指令取指令 k+1k+1 取指令取指令 k+2k+2 取指令取指令 k+3k+3 0 t1 t2 t3 t4 t5 时间时间 8 一个浮点加法器流水线的一个浮点加法器流水线的时空图例时空图例 空空间间 规规格格化化 规规格格化化1 1 规规格格化化2 2 规规格格化化3 3 规规格格化化4 4 规规格格化化5 5 尾尾数数加加 尾尾数数加加1 1 尾尾数数加加2 2 尾尾数数加加3 3 尾尾数数加加4 4 尾尾数数加加5 5 对对 阶阶 对对阶阶

8、1 1 对对阶阶2 2 对对阶阶3 3 对对阶阶4 4 对对阶阶5 5 求求阶阶差差 求求阶阶差差1 1 求求阶阶差差2 2 求求阶阶差差3 3 求求阶阶差差4 4 求求阶阶差差5 5 0 t1 t2 t3 t4 t5 t6 t7 t8 时时间间 9 4.流水线的主要特点：流水线的主要特点： （1）只有连续提供同类任务才能发挥流水线效只有连续提供同类任务才能发挥流水线效 率率，尽量减少因条件分支造成的，尽量减少因条件分支造成的“断流断流”，通，通 过编译技术提供连续的相同类型操作。过编译技术提供连续的相同类型操作。 （2）每个流水段都要设置一个流水寄存器每个流水段都要设置一个流水寄存器，增，增

9、 加时间开销：流水线的执行时间加长；增加硬加时间开销：流水线的执行时间加长；增加硬 件开销：每段需要增加一个寄存器。件开销：每段需要增加一个寄存器。 （3）各流水段的时间应尽量相等各流水段的时间应尽量相等，流水线处理，流水线处理 机的基本时钟周期等于时间最长的流水段的时机的基本时钟周期等于时间最长的流水段的时 间长度。间长度。 （4）流水线需要有流水线需要有“装入时间装入时间”和和“排空时排空时 间间”。 10 5.1.3 流水线的性能分析流水线的性能分析 主要指标：主要指标：吞吐率、加速比和效率吞吐率、加速比和效率 1.吞吐率吞吐率(Thought put) 流水线吞吐率的最基本公式：流水线

10、吞吐率的最基本公式： 其中：其中：n为任务数，为任务数，Tk为完成为完成n个任务所个任务所 用时间。各段执行时间相等，输入连续任务用时间。各段执行时间相等，输入连续任务 情况下，完成情况下，完成n个任务需要的总的时间为：个任务需要的总的时间为： 其中：其中：k为流水线的段数，为流水线的段数， 为时钟周期。为时钟周期。 k T n Tp tnkT k )1( t 11 吞吐率为：吞吐率为： 最大吞吐率为最大吞吐率为： tnktntkTk) 1() 1( tnk n Tp )1( ttnk n Tp n 1 )1( lim max 空间空间 S4123n-1n S3123n-1n S2123n-1

11、n S11 12 23 3n-1n-1n n时间时间 kt(n1)t nt(k1)t T 12 各段时间不等，完成各段时间不等，完成n个连续任务：个连续任务： 吞吐率吞吐率： 最大吞吐率最大吞吐率： 流水线个段执行时间不相等的解决办法：流水线个段执行时间不相等的解决办法： ),max()1( 21 1 k k i i tttnt n Tp ),max( 1 21k ttt Tp s s1 1s s3 3s s4 4s s2 2 t t1 1= = t t t t2 2= 3= 3t t t t3 3= = t t t t4 4= = t t 输出输出输入输入 13 (1)将将“瓶颈瓶颈”部分再

12、细分部分再细分(如果可分的话）如果可分的话） 输输入入 S1S2-1S2-2S2-3S3S4 输输出出 t t t t t t “瓶瓶颈颈”流流水水段段再再次次细细分分 S2 (3 t) 空空间间 S4123n S3123n S2123n S1123n时时间间 k i it 1 （n1） t2 Tk 各段执行时间不相等的流水线及其时空图 14 (2)“瓶颈瓶颈”流水段重复设置流水段重复设置：增加分配器和收集器：增加分配器和收集器 15 2.加速比加速比(Speedup) 计算加速比的基本公式：计算加速比的基本公式： 各段执行时间相等，输入连续任务情况下，各段执行时间相等，输入连续任务情况下，

13、加速比：加速比： 最大加速比：最大加速比： 各段时间不等，输入连续任务情况下，实际加速各段时间不等，输入连续任务情况下，实际加速 比为：比为： S T Tk 顺序执行时间 流水线执行时间 0 S k nt knt k n kn () 11 SLim k n kn k n max 1 S nt tnttt i i k i i k k 1 1 121() m ax(,） 16 当流水线段数增加时，需要连续输入的任务也必当流水线段数增加时，需要连续输入的任务也必 须增加。须增加。 加速比加速比 S 10 加加 k=10 段段 8 速速 6 比比 k=6 段段 4 2 1 1 2 4 8 16 32

14、64 128 n 任任 务务 个个 数数 17 3.效率效率(Efficiency) 计算流水线效率的一般公式：计算流水线效率的一般公式： 各流水段时间相等，输入各流水段时间相等，输入n个连续任务，流水线个连续任务，流水线 的效率为：的效率为： 最高效率最高效率为：为： 各流水段时间不等，输入各流水段时间不等，输入n个连续任务，流水线个连续任务，流水线 效率为：效率为： E n k T k Tk 个任务占用的时空区 个流水段的总的时空区 0 E k nt kknt n kn () 11 ELim n kn n max 1 1 E nt ktnttt i i k i i k k 1 1 121)

15、m a x (,)（ 18 各段设备量或价格不等时，流水线的效率为：各段设备量或价格不等时，流水线的效率为： 即：即： 其中其中, ，aik，且k。 流水线的吞吐率、加速比与效率的关系：流水线的吞吐率、加速比与效率的关系： 因为因为 因此：因此： tnk n Tp )1( 1 nk nk S 1 nk n E EkStTPE, 空区个流水段的总的加权时 区个任务占用的加权时空 k n E ), ,max()121 11 1 n k i ii ki I i k i ii tttntaa tan E （ 19 4.流水线性能分析举例流水线性能分析举例 对于输入连续任务的情况，通过上面对于输入连续任

16、务的情况，通过上面 给出的公式很容易计算出流水线的吞吐给出的公式很容易计算出流水线的吞吐 率、加速比和效率。率、加速比和效率。 对于输入不连续任务等情况，通常采对于输入不连续任务等情况，通常采 用基本公式计算。用基本公式计算。 例：例：用一条用一条4段浮点加法器流水线求段浮点加法器流水线求8个浮个浮 点数的和：点数的和：Z=A+B+C+D+E+F+G+H 20 解解：Z=(A+B)+(C+D)+(E+F)+(G+H) 空空 间间 周周 期期 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

17、 规规 格格 化化 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 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+

18、 +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个个 数数 之之 和和 的的 流流 水水 线线 时时 空空 图图 21 解： 7个浮点加法共用了15个时钟周期。 流水线的流水线的吞吐率吞吐率为：为： 流水线的流水线的加速比加速比为：为： 流水线的流水线的效率效率为为： ttT n Tp k 1 47.0 15 7 87.1 15 74 0 t t T T S k 47.0 154 74 0 t t Tk T E

19、 k 22 5.1.4 非线性流水线调度非线性流水线调度 1.线性流水线与非线性流水线线性流水线与非线性流水线 流水线的各个流水段之间是否有反反馈信号流水线的各个流水段之间是否有反反馈信号 线性流水线线性流水线(Linear Pipelining): 每个流水段都流过一次，而且仅流过一次线性每个流水段都流过一次，而且仅流过一次线性 流水线能够用流水线连接图唯一表示流水线能够用流水线连接图唯一表示 非线性流水线非线性流水线(Nonliner Pipelining): 某些流水段之间有反馈回路或前馈回路。非某些流水段之间有反馈回路或前馈回路。非 线性流水线必须用流水线连接图和流水线预约表线性流水线

20、必须用流水线连接图和流水线预约表 共同表示。共同表示。 23 非线性流水线调度的任务：非线性流水线调度的任务： 找出一个最小的启动循环周期，按照这周期流水找出一个最小的启动循环周期，按照这周期流水 线输入新任务，流水线的各个功能段不会发生冲线输入新任务，流水线的各个功能段不会发生冲 突，而且流水线的吞吐率和效率最高。突，而且流水线的吞吐率和效率最高。 前前馈馈回回路路 输输入入S S1 1S S2 2S S3 3 输输出出 反反馈馈回回路路 一一种种简简单单的的非非线线性性流流水水线线 24 非线性流水线的连接图和预约表非线性流水线的连接图和预约表 输输出出 输输入入 S1S2S3S4 前馈线

21、 反馈线 时时间间 功功能能段段 1234567 S1 S2 S3 S4 25 一张预约表可能与多个流水线连接土相对应：一张预约表可能与多个流水线连接土相对应： 时时 间间 功功 能能 段段 1 2 3 4 5 6 7 S1 S2 S3 S4 输输出出 S4 输输入入S1S2S3 前前馈馈线线 反反馈馈线线 26 一个流水线连接图对应与多张预约表：一个流水线连接图对应与多张预约表： 2.非线性流水线的冲突非线性流水线的冲突 启动距离：连续输入两个任务之间的时间间隔。启动距离：连续输入两个任务之间的时间间隔。 流水线冲突：几个任务争同一个流水段。流水线冲突：几个任务争同一个流水段。 时时间间 功

22、功能能段段 1 2 3 4 5 6 7 S1 S2 S3 S4 时时间间 功功能能段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 S1 S2 S3 S4 27 28 启启动动距距离离为为 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 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

23、 2 S S4 4 X X1 1 X X2 2 启启动动周周期期 重重复复启启动动周周期期 启启动动距距离离为为( (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 1 16 6 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

24、 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 启启动动周周期期 重重复复启启动动周周期期 29 3.无冲突调度方法无冲突调度方法 由由E.S.Davidson及学生于及学生于1971年提出年提出 例：一条例：一条4功能段的非线性流水线，每个功能的延迟功能段的非线性流水线，每个功能的延迟 时间都相等，它的预约表如下：时间都相等，它的预约表如下： (1)写出流水线的

25、禁止向量和初始冲突向量。写出流水线的禁止向量和初始冲突向量。 (2)画出调度流水线的状态图。画出调度流水线的状态图。 (3)求最小启动循环和最小平均启动距离。求最小启动循环和最小平均启动距离。 (4)求平均启动距离最小的恒定循环。求平均启动距离最小的恒定循环。 时 间 功能段 1 2 3 4 5 6 7 S1 X X S2 X X S3 X X S4 X 30 解解: (1)禁止向量禁止向量：预约表中每一行任意两个：预约表中每一行任意两个“X”之之 间距离集合。本例中为间距离集合。本例中为(2,4,6). (2)冲突向量冲突向量：C=(CmCjC2C1) 其中：其中：m是禁止向量中的最大值。如

26、果是禁止向量中的最大值。如果j在禁止在禁止 向量中，则向量中，则Cj=1,否则否则Cj =0. 本例中本例中 C=(101010) (3)构造状态图构造状态图 S逻辑右移逻辑右移2、4、6位时，不作任何处理，位时，不作任何处理， 逻辑右移逻辑右移1、3、5和大于等于时：和大于等于时： S右移右移1位之后：位之后：010101V101010=111111 S右移右移3位之后：位之后：000101V101010=101111 S右移右移5位之后：位之后：000001V101010=101011 31 S右移右移7位或大于位或大于7位后：还原到本身位后：还原到本身 101111右移右移5位之后：位之

27、后：000001V101010=101011 101011右移右移3位之后：位之后：000101V101010=101111 101011右移右移5位之后：位之后：000001V101010=101011 32 简单循环：简单循环：状态图中各种冲突向量只经过一次启动循状态图中各种冲突向量只经过一次启动循 环。环。 (2)最小的启动循环最小的启动循环为为(1,7)和（和（3，5）,平均距离为平均距离为4。 (5)启动距离最小的恒定循环为启动距离最小的恒定循环为(5) 简简 单单 循循 环环平平 均均 启启 动动 距距 离离 （ 1 1， 7 7）4 4 （ 3 3， 7 7）5 5 （ 5 5，

28、 7 7）6 6 （ 3 3， 5 5， 7 7）5 5 （ 5 5， 3 3， 7 7）5 5 （ 3 3， 5 5）4 4 （ 5 5）5 5 （ 7 7）7 7 33 最最小小启启动动循循环环( (3 3, ,5 5) )的的流流水水线线工工作作状状态态 时时间间 功功能能段段 1 12 23 34 45 56 67 78 89 91 10 0 1 11 1 1 12 2 1 13 3 1 14 4 1 15 5 S S1 1X X1 1X X2 2X X1 1X X3 3X X2 2X X4 4X X3 3 S S2 2X X1 1X X2 2X X1 1X X2 2X X3 3X X

29、4 4X X3 3 S S3 3X X1 1X X1 1X X2 2X X2 2X X3 3X X3 3X X4 4 S 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

30、 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 启启动动周周期期 重重复复启启动动周周期期 34 恒恒定定启启动动循循环环( (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

31、 1 14 4 1 15 5 S S1 1 X X1 1 X X2 2 X 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 启启动动周周期期 重重复复启启动动周周期期 35 4.优化调度方法优化调度方法 L.E.Shar于于1972年提出流水线最小平均启动年提出流水线最小平均启动 距离的限制范围：距离的限制范围： (1)最小平均启动距离的下限是预约表中任意一行里最小平均

32、启动距离的下限是预约表中任意一行里 “X”的最多个数。的最多个数。 (2)最小平均距离小于等于状态图中任意一个简单循最小平均距离小于等于状态图中任意一个简单循 环的平均启动距离。环的平均启动距离。 (3)最小平均启动距离的上限是冲突向量中最小平均启动距离的上限是冲突向量中1的个数的个数 再加上再加上1。 注注:A、1992年，年， L.E.Shar又证明了上述限制范围。又证明了上述限制范围。 B、最有用的是第一条。预约表中、最有用的是第一条。预约表中“X”最多的行最多的行 一定是一定是瓶颈流水段。瓶颈流水段。 36 对于上例的预约表，在同一行中对于上例的预约表，在同一行中“X”最多的最多的 为

33、为2个，因此，个，因此，最小平均距离可以达到最小平均距离可以达到2。 最小启动循环可以是最小启动循环可以是(2)、(1,3)、(1,1,4)、 (1,2,3).。现取恒定循环。现取恒定循环(2)。 每一行中与第每一行中与第1个个“X”的距离为的距离为2的倍数的位的倍数的位 置都要预留出来。置都要预留出来。 S3行的第行的第2个个“X”从周期延迟到周期从周期延迟到周期6。为此，。为此， S2行的第行的第2个个“X”从周期延迟到周期从周期延迟到周期7； S1行的第行的第2个个“X”从周期延迟到周期从周期延迟到周期8。 实际上，只要在流水线段实际上，只要在流水线段S4的输出端到流水的输出端到流水S3

34、 的输入端中间插入一个的输入端中间插入一个非计算延迟非计算延迟D1。 37 采采用用预预留留调调度度算算法法的的预预约约表表 时时 间间12345678 S1 S2 S3 功功 能能 段段 S4 延延迟迟 D1 注注：表表示示由由D D1 1延延迟迟一一个个时时钟钟周周期期 38 有有 非非 计计 算算 延延 迟迟 的的 流流 水水 线线 状状 态态 图图 8 8* * 0 0 0 0 8 8* * 8 8* *1 1 2 2 4 4 6 6 8 8* * 0 0 0 0 0 0 1 1 2 2 4 4 6 6 39 在非线性流水线中，在非线性流水线中，“X”最多的流水段一最多的流水段一 定是

35、定是“瓶颈瓶颈”流水段。流水段。 实现最优调度的目标是使实现最优调度的目标是使“瓶颈瓶颈”流水段流水段 处于忙碌状态，没有空闲周期处于忙碌状态，没有空闲周期。 最优调度方法能够使非线性流水的吞吐率，最优调度方法能够使非线性流水的吞吐率， 加速比和效率达到最优。加速比和效率达到最优。 按按照照最最小小启启动动循循环环（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 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

36、 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 5 延延 D D1 1 X X1 1 X X2 2 X X3 3 X X4 4 40 5.2 相关性分析技术相关性分析技术 5.2.1 数据相关数据相关 5.2.2 控制相关控制相关 5.2.3

37、 条件分支对流水线的影响条件分支对流水线的影响 5.2.4 静态分支预测技术静态分支预测技术 5.2.5 动态分支预测技术动态分支预测技术 5.2.6 精确断点与不精确断点精确断点与不精确断点 41 5.2.1 数据相关数据相关 数据相关：数据相关： 在执行本条指令的过程中，如果用到的指在执行本条指令的过程中，如果用到的指 令、操作数、变址量等是前面指令的执行结果，令、操作数、变址量等是前面指令的执行结果， 这种相关称为数据相关。这种相关称为数据相关。 控制相关：控制相关： 由条件分支指令、转子程序指令、中断等由条件分支指令、转子程序指令、中断等 引起的相关。引起的相关。 解决数据相关的方法有

38、两种：解决数据相关的方法有两种： 推后处理推后处理 设置专用路径设置专用路径。 42 1.指令相关指令相关 发生指令相关的情况：发生指令相关的情况： n: STORE R1，n+1 n+1:. 满足关系：满足关系：结果地址结果地址(n)=指令地址指令地址(n+1) 当第当第n条指令还没有把执行结果写到主条指令还没有把执行结果写到主 存之前，取出的第存之前，取出的第n+1指令显然是错误的。指令显然是错误的。 在第在第k个流水段的流水线处理机中，第个流水段的流水线处理机中，第 n条指令要修改从条指令要修改从n+1 到第到第n+k指令中任意指令中任意 一条指令，都可能造成程序执行结果发生一条指令，都

39、可能造成程序执行结果发生 错误。错误。 43 解决指令相关的根本办法是：解决指令相关的根本办法是： 在程序执行过程中不允许修改指令。在程序执行过程中不允许修改指令。 现代程序设计方法要求程序具有载入性，可以现代程序设计方法要求程序具有载入性，可以 被递归调用等，也要求不修改指令。被递归调用等，也要求不修改指令。 在在IBM370系列机中，用系列机中，用“执行指令执行指令”来解决：来解决： 在程序执行过程中既能修改指令，程序又具有载入在程序执行过程中既能修改指令，程序又具有载入 性。性。 “执行指令执行指令”执行由第二地址执行由第二地址(X2)+(B2)+D2) 决定的主存数据区中的指令。决定的

40、主存数据区中的指令。 44 2.通用寄存器数据相关通用寄存器数据相关 发生寄存器数据相关的可能性很大，影发生寄存器数据相关的可能性很大，影 响面也很大。响面也很大。 例如：例如： n:OP R1,A2 ;R1=(R1)OP（A2） n+1:OP R1,R2 ;R1=(R1)OP（R2） 发生发生R1(n)=R1(n+1)称为称为R1数据相关数据相关。 发生发生R1(n)=R2(n+1)称为称为R2数据相关数据相关。 解决通用寄存器数据相关的办法：解决通用寄存器数据相关的办法： 45 方法一方法一：把读操作数、写运算结果与指令执行把读操作数、写运算结果与指令执行 合在一个节拍。合在一个节拍。 从

41、数据从通用寄存器读出，在运算器中从数据从通用寄存器读出，在运算器中 完成运算，结果写回通用寄存器的整个回路完成运算，结果写回通用寄存器的整个回路 中，只有通用寄存器是时序逻辑。中，只有通用寄存器是时序逻辑。 当发生下述情况时，不能采用这种方法：当发生下述情况时，不能采用这种方法： (1) 当寄存器个数多时，读写寄存器的时间当寄存器个数多时，读写寄存器的时间 长。长。 (2)当功能部件数量多时，寄存器的读写端当功能部件数量多时，寄存器的读写端 口多。口多。 (3)当功能部件的执行时间比较长，或要求当功能部件的执行时间比较长，或要求 指令的执行时间短时。指令的执行时间短时。 46 方法二方法二：建

42、立相关专用通路建立相关专用通路(ByPass) 由于发生寄存器数据相关的情况很普遍，一般计由于发生寄存器数据相关的情况很普遍，一般计 算机系统都采用专用数据通路。算机系统都采用专用数据通路。 把读通用寄存器、执行操作和写结果分为把读通用寄存器、执行操作和写结果分为3个周个周 期，或期，或2个周期。个周期。 采用专用数据通路能够缩短采用专用数据通路能够缩短1至至2个周期。个周期。 通通用用寄寄存存器器堆堆 多多路路选选择择器器多多路路选选择择器器 运运算算器器 一一种种典典型型的的运运算算器器结结构构 通通用用寄寄存存器器堆堆 相相关关专专用用通通路路 锁锁存存器器锁锁存存器器 运运算算器器 设

43、设置置专专用用数数据据通通路路解解决决通通用用寄寄存存器器数数据据相相关关 47 变址相关：变址相关： 在采用变址寻址方式的处理机中，由在采用变址寻址方式的处理机中，由 于变址量放在寄存器中，因此，可能发生与于变址量放在寄存器中，因此，可能发生与 通用寄存器数据相关类似变址相关。通用寄存器数据相关类似变址相关。 3.LOAD相关相关 LOAD操作的执行时间可能比较长操作的执行时间可能比较长 n: LOAD R1, A ;R1=(A) n+1: ADD R1, R2 ;R1=(R1)OP(R2) 如果如果R1(n)=R2(n+1),或或R1(n)=R1(n+1)，则发，则发 生生LOAD数据相关

44、。数据相关。 解决方法：解决方法： 48 方法一：方法一：由编译器在由编译器在LOAD之后插入不发生数据相之后插入不发生数据相 关的指令，由于关的指令，由于LOAD的执行时间不确定，不能的执行时间不确定，不能 根本解决问题。根本解决问题。 方法二：方法二：由硬件自动插入空操作，直到由硬件自动插入空操作，直到LOAD操作操作 完成。完成。 在单条流水线处理机中，也可以停止节拍发在单条流水线处理机中，也可以停止节拍发 生器生器 ，直到数据从存储器中读出为止。，直到数据从存储器中读出为止。 49 5.2.2 控制相关 因程序的执行方向可能被改变而引起的相因程序的执行方向可能被改变而引起的相 关，也称

45、为关，也称为全局相关全局相关。 主要包括：无条件转移、一般条件转移、主要包括：无条件转移、一般条件转移、 复合条件转移、中断等。复合条件转移、中断等。 1.无条件转移无条件转移 在流水线处理机中，无条件转移指令不进在流水线处理机中，无条件转移指令不进 入流水段，一般在指令译码阶段就实际完成。入流水段，一般在指令译码阶段就实际完成。 如果在处理机中设置有指令先行缓冲栈，如果在处理机中设置有指令先行缓冲栈， 则要全部或部分作废先行指令缓冲栈中指令。则要全部或部分作废先行指令缓冲栈中指令。 50 如果转移目标指令如果转移目标指令L不在先行指令缓冲不在先行指令缓冲 站中，站中，则要将先行指令缓冲栈中所

46、有指令全则要将先行指令缓冲栈中所有指令全 部作废，并等待取出转移目标指令部作废，并等待取出转移目标指令L。 如果转移目标指令如果转移目标指令L在先行指令缓冲栈在先行指令缓冲栈 中，中，只要作废先行指令缓冲栈中的部分指令。只要作废先行指令缓冲栈中的部分指令。 无条件转移指令一般对指令执行部件的无条件转移指令一般对指令执行部件的 工作不会造成影响。工作不会造成影响。 为进一步减少无条件转移指令造成的影为进一步减少无条件转移指令造成的影 响，响，在先行指令缓冲栈的入口处增设一个专在先行指令缓冲栈的入口处增设一个专 门处理无条件转移指令的指令分析器。门处理无条件转移指令的指令分析器。 51 2.一般条

47、件转移一般条件转移 k: ;设置条件码设置条件码CC k+1: JMP(CC)L ;如果如果CC为真转向为真转向L L: . 当条件码是上一条指令产生时，相关最严重。当条件码是上一条指令产生时，相关最严重。 52 无论转移是否成功，条件转移指令都在无论转移是否成功，条件转移指令都在 指令分析阶段就已经执行完成。指令分析阶段就已经执行完成。 无论转移不成功或成功，指令分析器要无论转移不成功或成功，指令分析器要 停顿一段时间，等待条件码产生。停顿一段时间，等待条件码产生。 53 如果转移成功：指令如果转移成功：指令L已经在先行指令已经在先行指令 缓冲栈，指令分析器接着缓冲栈，指令分析器接着“分析分

48、析L”,如果指如果指 令令L不在先行指令缓冲栈，指令分析器要等不在先行指令缓冲栈，指令分析器要等 待一个周期。待一个周期。 转移不成功，对程序执行影响不大，转移不成功，对程序执行影响不大， 当转移成功时，不仅指令执行过程变成当转移成功时，不仅指令执行过程变成 完全串行，而且要作废先行指令缓冲栈中大完全串行，而且要作废先行指令缓冲栈中大 量指令。量指令。 在采用流水线方式的处理机中，要通过在采用流水线方式的处理机中，要通过 软件与硬件的多种手段来尽可能地降低转移软件与硬件的多种手段来尽可能地降低转移 成功的概率，减少转移成功造成影响。成功的概率，减少转移成功造成影响。 54 5.2.3 条件分支

49、对流水线的影响条件分支对流水线的影响 处理好条件转移和中断的关键问题有两个：处理好条件转移和中断的关键问题有两个： 要确保流水线能够正常工作要确保流水线能够正常工作,减少因减少因“断流断流” 引起的吞吐率和效率的下降。引起的吞吐率和效率的下降。 1.条件分支在流水线中执行过程条件分支在流水线中执行过程 55 因为第因为第i条指令所需要的条件码由条指令所需要的条件码由i-1 条指令给出：在一条由条指令给出：在一条由k个功能段的流水个功能段的流水 线中，第线中，第i-1条指令要等到第条指令要等到第I+k-2条指令条指令 进入流水线时才能形成条件码。进入流水线时才能形成条件码。 转移不成功转移不成功

50、，猜测正确，流水线的，猜测正确，流水线的 吞吐率和效率没有降低。吞吐率和效率没有降低。 转移成功转移成功，猜测错误，要先作废流，猜测错误，要先作废流 水线中已经执行的水线中已经执行的i+1、i+2、.、i+k-2 指令；然后再从分支点开始执行第指令；然后再从分支点开始执行第P、 P+1、指令。一条指令。一条k段流水线有段流水线有k-2个功个功 能段是浪费的。能段是浪费的。 56 2.条件分支对流水线性能的影响条件分支对流水线性能的影响 假设条件转移指令在一般程序中所占的比例为假设条件转移指令在一般程序中所占的比例为p,转移转移 成功的概率为成功的概率为q。 N条指令的总的执行时间是：条指令的总

51、的执行时间是： TK-IF(n+k-1)t + npq(k-1)t 有条件转移影响的流水线吞吐率为：有条件转移影响的流水线吞吐率为： 有条件转移影响的流水线最大吞吐率为：有条件转移影响的流水线最大吞吐率为： TP n nktnpq kt IF （11)() tkpq )1(1 1 TPIFMAX （ 57 流水线吞吐率下降的百分比为： 在典型程序中，转移指令占的比例为p=20%， 转移成功概率为q=60%。 对于一条8功能段的指令流水线，由于条件转 移指令的影响，流水线的最大吞吐率要下降： 如果指令流水线的功能段数为10，由于条件 转移指令的影响，流水线的最大吞吐率将要下降 一半以下： ) 1

52、(1 ) 1( kpq kpq TP TPTP D MAX IFMAXMAX %46 ) 18(60. 020. 01 ) 18(60. 020. 0 8 D %53 ) 110(60. 020. 01 ) 110(60. 020. 0 D10 58 5.2.4 静态分支预测技术静态分支预测技术 静态分支预测：静态分支预测： 在程序执行过程中转移预测方向不能改变在程序执行过程中转移预测方向不能改变 动态分支预测：动态分支预测： 在程序执行过程中能够改变转移预测方向在程序执行过程中能够改变转移预测方向 本节讲述静态预测技术，下节讲述动态预测。本节讲述静态预测技术，下节讲述动态预测。 1.软件软件

53、“猜测法猜测法” 目标：目标：通过编译器尽量降低转移成功概率。通过编译器尽量降低转移成功概率。 例如：对于循环程序，普通编译器生成的目标代码，例如：对于循环程序，普通编译器生成的目标代码， 转换成功的概率很高，不成功的只有一次。这种转换成功的概率很高，不成功的只有一次。这种 编译结果对流水线极为不利。编译结果对流水线极为不利。 59 软件软件“猜测法猜测法” 通过编译器降低转移成功概率通过编译器降低转移成功概率。 60 2.硬件硬件“猜测法猜测法” 方法：方法：通过改变硬件结构来降低转移指令对流通过改变硬件结构来降低转移指令对流 水线的影响。水线的影响。 在指令缓冲栈的入口处设置一个简单的指在

54、指令缓冲栈的入口处设置一个简单的指 令分析器，当检测到转移指令时，就从转移目令分析器，当检测到转移指令时，就从转移目 标地址开始起占领，同时保留当前标地址开始起占领，同时保留当前PC中内容，中内容， 以便猜测错误时恢复。转移成功，猜测正确以便猜测错误时恢复。转移成功，猜测正确,对对 转移指令对流水线不造成影响。转移不成功，转移指令对流水线不造成影响。转移不成功， 用保存下来的地址恢复用保存下来的地址恢复PC。 软硬件共同配合，都往一个方向去猜测。软硬件共同配合，都往一个方向去猜测。 61 3.两个先行指令缓冲栈两个先行指令缓冲栈 在先行指令缓冲栈中在先行指令缓冲栈中增加一个先行目标增加一个先行

55、目标 缓冲栈。缓冲栈。 按照转移成功的方向预取指令到先行目标按照转移成功的方向预取指令到先行目标 缓冲栈中。缓冲栈中。 先行指令缓冲栈仍然按照转移不成功的先行指令缓冲栈仍然按照转移不成功的 方向继续预取指令。方向继续预取指令。 如果转移不成功，则继续分析原来先行如果转移不成功，则继续分析原来先行 指令缓冲中指令。指令缓冲中指令。 如果转移成功，则分析新增设的先行目如果转移成功，则分析新增设的先行目 标缓冲栈中的指令。标缓冲栈中的指令。 62 两个先行指令缓冲栈两个先行指令缓冲栈 63 5.2.5 动态分支预测技术动态分支预测技术 动态转移预测技术的两个关键问题：动态转移预测技术的两个关键问题：

56、 如何记录转移历史信息，如何根据记录如何记录转移历史信息，如何根据记录 的转移历史信息预测转移方向。的转移历史信息预测转移方向。 记录转移历史信息的方法有三种：记录转移历史信息的方法有三种： (1)最近一次或几次转移是否成功的信息记录在最近一次或几次转移是否成功的信息记录在 转移指令中。转移指令中。 (2)用一个高速缓冲栈保存条件转移指令的转移用一个高速缓冲栈保存条件转移指令的转移 目标地址。目标地址。 (3)用用Cache保存转移目标地址之后的保存转移目标地址之后的n条指令。条指令。 64 1.在指令在指令Cache中记录转移历史信息中记录转移历史信息 在指令在指令Cache中专门设置一个字

57、段，中专门设置一个字段， 称为称为“转移历史表转移历史表”。 在执行转移指令时，把转移成功或不在执行转移指令时，把转移成功或不 成功的信息记录在这个表中。成功的信息记录在这个表中。 当下次再执行到这条指令时，转移预当下次再执行到这条指令时，转移预 测逻辑根据测逻辑根据“转移历史表转移历史表”中记录的信息中记录的信息 预测转移成功或不成功。预测转移成功或不成功。 65 只记录最近一次转移是否成功的历史信息只记录最近一次转移是否成功的历史信息 如果如果“转移历史表转移历史表”中记录的内容是中记录的内容是“T”，则，则 预测转移成功，如果记录的是预测转移成功，如果记录的是“N”，则按照转移，则按照转

58、移 不成功的方向继续取指令。不成功的方向继续取指令。 并用实际转移是否成功的信息来修改并用实际转移是否成功的信息来修改“转移历转移历 史表史表”。 T T T：转移成功，N：转移不成功 N N T N 66 只记录最近两次转移是否成功的历史信息只记录最近两次转移是否成功的历史信息 图中采用图中采用偏向成功的预测策略偏向成功的预测策略：只有历史上：只有历史上 最近两次执行这条转移指令时，转移都没有成功，最近两次执行这条转移指令时，转移都没有成功， 本次才预测转移不成功。本次才预测转移不成功。 也可以采用其他预测策略。也可以采用其他预测策略。 TT：最最近近两两次次转转移移都都成成功功 NT：最最

59、近近一一次次转转移移成成功功，前前一一次次转转移移不不成成功功 TN：最最近近一一次次转转移移不不成成功功，前前一一次次转转移移成成功功 NN：最最近近两两次次转转移移都都不不成成功功 t：本本次次预预测测转转移移成成功功 n：本本次次预预测测转转移移不不成成功功 T：本本次次实实际际转转移移成成功功 N：本本次次实实际际转转移移不不成成功功 TT t TN t NT t NN n T N N T T TN N 67 当当“转移历史表转移历史表”是空白时，是空白时，可以有两种方法：可以有两种方法： (1)在在“转移历史表转移历史表”中预置转移历史信息。中预置转移历史信息。 (2)根据指令本身的

60、偏移字段的符号来预测转根据指令本身的偏移字段的符号来预测转 移的方向，如果偏移字段为负，则预测转移移的方向，如果偏移字段为负，则预测转移 成功，否则预测转移不成功。成功，否则预测转移不成功。 主要优点：主要优点： 不必专门设置转移缓冲栈，所有记录的转移不必专门设置转移缓冲栈，所有记录的转移 历史信息比较少。历史信息比较少。 例如例如:DEC公司的公司的Alpha 21064处理机就处理机就 采用了这种转移预测方法，在它的一级指令采用了这种转移预测方法，在它的一级指令 Cache中有一个专门的中有一个专门的“转移历史表转移历史表”字段。字段。 68 指指 令令 Cache（ 8KB） 转转 移移