计算机系统结构 第四章(流水处理和ILP)

1、幻灯片 1/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系w流水线基本概念流水线基本概念w相关性分析技术相关性分析技术w多指令发射技术多指令发射技术幻灯片 2/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系w 引入引入w 流水线工作原理流水线工作原理w 流水线的分类流水线的分类w 流水线的性能分析流水线的性能分析w 非线性流水线的调度技术非线性流水线的调度技术本章内容幻灯片 3/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流

2、水线基本概念 具有标量数据表示和标量指令系统的处理机称具有标量数据表示和标量指令系统的处理机称为标量处理机。为标量处理机。提高处理机的工作主频；提高处理机的工作主频；采用更好的算法和设计更好的功能部件；采用更好的算法和设计更好的功能部件；采用指令级并行（采用指令级并行（ILP）技术（技术（）。）。幻灯片 4/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念w 基本思想基本思想w 表示方法表示方法w 主要特点主要特点幻灯片 5/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工

3、程系本章内容流水线基本概念流水线工作原理以以为例进行介绍：为例进行介绍：取指取指分析分析执行执行通过将一个重复的过程分解为若通过将一个重复的过程分解为若干子过程，每个子过程可以与其干子过程，每个子过程可以与其它子过程同时进行。它子过程同时进行。ttt5 之 1幻灯片 6/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线工作原理取指取指k分析分析k执行执行k取指取指k+1分析分析k+1执行执行k+1 控制简单，节省设备。控制简单，节省设备。 处理器执行指令的速度慢处理器执行指令的速度慢 功能部件的利用率很低功能部件的

4、利用率很低tn3(Tn1iiiittt）执行分析取指5 之 2幻灯片 7/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线工作原理 t)n21 (T取指取指k分析分析k执行执行k取指取指k+1分析分析k+1执行执行k+1取指取指k+2分析分析k+2执行执行k+2 执行指令的速度较快执行指令的速度较快 功能部件的利用率较高功能部件的利用率较高 控制较复杂，需增加设备控制较复杂，需增加设备5 之 3幻灯片 8/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流

5、水线基本概念流水线工作原理 t)n2(T 执行指令的速度更快执行指令的速度更快 功能部件的利用率更高功能部件的利用率更高 控制更复杂，需增加设备控制更复杂，需增加设备取指取指k+2分析分析k+2执行执行k+2取指取指k+1分析分析k+1执行执行k+1取指取指k分析分析k执行执行k5 之 4幻灯片 9/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线工作原理 流水线利用并行性实现：流水线利用并行性实现： 设置多个独立的操作部件。设置多个独立的操作部件。 分时使用同一个部件的不同分时使用同一个部件的不同部分。部分。5

6、之 5幻灯片 10/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线工作原理 流水线的表示方法通常有三种：流水线的表示方法通常有三种：w 连接图连接图w 时空图时空图w 预约表预约表幻灯片 11/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线工作原理流水线表示方法分析器分析器分析分析k+1流水流水锁存器锁存器执行部件执行部件执行执行k流水流水锁存器锁存器输输入入输输出出 t1 t2Stage 1latch输输入入输输出出 t1 t2S

7、tage 2latchStage 3latch t32 之 1幻灯片 12/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 流水线的每一个阶段称为流水步、流水步骤、流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、流水级、流流水段、流水线阶段、流水功能段、流水级、流水节拍等。水节拍等。 在每一个流水段的末尾或开头必须设置一个寄在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门存器，称为流水寄存器、流水锁存器、流水闸门寄存器等。加入流水寄存器，会增加指令的执行寄存器等。加入流水寄存器，会增

8、加指令的执行时间。在一般流水线中不画出流水寄存器。时间。在一般流水线中不画出流水寄存器。本章内容流水线基本概念流水线工作原理流水线表示方法2 之 2幻灯片 13/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系1时间时间空间空间0t1t2t3t4t52345123451234512345t6t7t8求阶差求阶差对阶对阶尾数加尾数加规格化规格化求阶差求阶差对阶对阶尾数加尾数加规格化规格化tttt本章内容流水线基本概念流水线工作原理流水线表示方法幻灯片 14/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机

9、科学与工程系本章内容流水线基本概念流水线工作原理 尽量减少因条件分支造成的尽量减少因条件分支造成的“断流断流”，可通过编译技术，可通过编译技术提供连续的相同类型操作。提供连续的相同类型操作。 用于保存本流水线段的执行结果，会使流水线的执行时用于保存本流水线段的执行结果，会使流水线的执行时间加长，是流水线中需要增加的主要硬件。间加长，是流水线中需要增加的主要硬件。 流水线处理机的基本时钟周期等于时间最长的流水段的流水线处理机的基本时钟周期等于时间最长的流水段的时间长度。时间长度。 幻灯片 15/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本

10、章内容流水线基本概念 从不同的角度，按照不同的观点，可从不同的角度，按照不同的观点，可以将流水线分成多种不同的种类。以将流水线分成多种不同的种类。w 分类一分类一w 分类二分类二 w 分类三分类三w 分类四分类四w 其它其它幻灯片 16/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系w 单功能流水线单功能流水线 只能完成一种固定功能的只能完成一种固定功能的流水线。例如：流水线。例如：Cray-1计算计算机中有机中有12条；条；YH-1计算机计算机有有18条；条；Pentium有一条有一条5段定点和一条段定点和一条8段浮点流水段浮点流水线；线

11、；Pentium有两条定点有两条定点和一条浮点指令流水线。和一条浮点指令流水线。w 多功能流水线多功能流水线 流水线的各段通过不同连流水线的各段通过不同连接实现不同功能。例如：接实现不同功能。例如：Texas公司的公司的ASC机，机，8段段流水线，能够实现：定点加流水线，能够实现：定点加减法、定点乘法、浮点加法、减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位浮点乘法、逻辑运算、移位操作、数据转换、向量运算操作、数据转换、向量运算等。等。本章内容流水线基本概念流水线的分类按流水线具有功能的多少来分，可分为：按流水线具有功能的多少来分，可分为：2 之 1Texas公司公司ASC机上的机上的8段

12、多功能流水线段多功能流水线2 之 2幻灯片 18/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线的分类 在多功能流水线中，按照在同一时间在多功能流水线中，按照在同一时间内是否能够连接成多种方式，同时执行多种内是否能够连接成多种方式，同时执行多种功能，可以将多功能流水线分为：功能，可以将多功能流水线分为：w 静态流水线静态流水线w 动态流水线动态流水线幻灯片 19/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线的分类分类二 同一段同一

13、段时间内，时间内，各个功能各个功能段只能按段只能按照一种方照一种方式连接，式连接，实现一种实现一种固定的功固定的功能。能。1时间时间空间空间02 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 4 1 2 3 1 2 1输入输入求阶差求阶差对阶对阶尾数加尾数加规格化规格化尾数乘尾数乘累加累加输出输出浮点加法浮点加法定点乘法定点乘法幻灯片 20/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 在同一在同一段时间内，段时间内，各段可以各段可以按照不同按照不同的方式连的方式连接，同时接，同时执行多种执行多种

14、功能。功能。1时间时间空间空间02 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 n输入输入求阶差求阶差对阶对阶尾数加尾数加规格化规格化尾数乘尾数乘累加累加输出输出1 2 35461 2 3541 2 3 41 2 3浮点加法浮点加法定点乘法定点乘法本章内容流水线基本概念流水线的分类分类二幻灯片 21/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线的分类 按照流水线的各个功能段之间是否有反馈信号，可以按照流水线的各个功能段之间是否有反馈信号，可以将流水线分为：将流水线分为： 是指流水线

15、内各功能段串是指流水线内各功能段串行连接，没有反馈回路，各行连接，没有反馈回路，各个功能段只经过一次。一条个功能段只经过一次。一条线性流水线通常只完成一种线性流水线通常只完成一种固定的功能。例子：指令流固定的功能。例子：指令流水线、浮点加法器流水线等。水线、浮点加法器流水线等。 是指流水线内除有串行连是指流水线内除有串行连接的通路外，还有某种反馈接的通路外，还有某种反馈回路，使得一次流水过程中，回路，使得一次流水过程中，某些段会多次通过。非线性某些段会多次通过。非线性流水线经常用于递归调用，流水线经常用于递归调用，或构成多功能流水线等。或构成多功能流水线等。3 之 1幻灯片 22/264Com

16、puter ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系S1输入输入S2S3输出输出前馈回路前馈回路反馈回路反馈回路一种简单的非线性流水线一种简单的非线性流水线对应的两种预约表对应的两种预约表S3S2S14321S3S2S1432153 之 2本章内容流水线基本概念流水线的分类幻灯片 23/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系w 线性流水线能够用线性流水线能够用唯一表示，非线性流唯一表示，非线性流水线必须用水线必须用和和共同表示。共同表示。w 一条非线性流水线可以对应有很多张预约表，一条非线性流水线

17、可以对应有很多张预约表，同样，一张预约表实际上仅表示了一条非线性同样，一张预约表实际上仅表示了一条非线性流水线的一种工作方式流水线的一种工作方式w 线性流水线实际上也有预约表，只不过它的预线性流水线实际上也有预约表，只不过它的预约表是固定的（一张对角线为的正方形的表约表是固定的（一张对角线为的正方形的表格）格）3 之 3本章内容流水线基本概念流水线的分类幻灯片 24/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 按照流水线使用的不同级别，可以将按照流水线使用的不同级别，可以将流水线分为：流水线分为：w 部件级流水线部件级流水线w 处理机级

18、流水线处理机级流水线w 系统级流水线系统级流水线本章内容流水线基本概念流水线的分类幻灯片 25/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线的分类分类四 是指构成部件内的各子部件之间的流水。例是指构成部件内的各子部件之间的流水。例如：浮点加法器流水线。如：浮点加法器流水线。求阶差求阶差输入输入输出输出 t1对阶对阶尾数加尾数加规格化规格化 t2 t3 t4幻灯片 26/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 又称为指令流水线又称为指令流水线 ，例如：

19、在采用先行控制，例如：在采用先行控制器的处理机中，各功能部件之间的流水线。器的处理机中，各功能部件之间的流水线。先行指令先行指令缓冲栈缓冲栈输入输入先行控制方式先行控制方式中的指令流水线中的指令流水线先行指令先行指令分析器分析器先行读数栈先行读数栈先行操作栈先行操作栈取指取指译码译码取操作数取操作数指令执指令执行部件行部件后行后行写数栈写数栈输出输出执行执行写结果写结果本章内容流水线基本概念流水线的分类分类四幻灯片 27/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 也称为宏流水线，是处理机之间的流水线也称为宏流水线，是处理机之间的流水线

20、 。例如：每个处理机对同一个数据流的不同部分分例如：每个处理机对同一个数据流的不同部分分别进行处理。别进行处理。P1输输入入任务任务1MMP2任务任务2MP3任务任务3输输出出本章内容流水线基本概念流水线的分类分类四幻灯片 28/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 按照不同的数据表示方式按照不同的数据表示方式分：分： 对标量数据进行处理。对标量数据进行处理。 对向量数据进行处理。对向量数据进行处理。 按照流水线中信息流动顺按照流水线中信息流动顺序的控制方式分：序的控制方式分： 流水线输出端的任务流出流水线输出端的任务流出顺序与输

21、入端的任务流入顺顺序与输入端的任务流入顺序完全相同。序完全相同。 流水线输出端的任务流出流水线输出端的任务流出顺序与输入端的任务流入顺顺序与输入端的任务流入顺序可以不一样。序可以不一样。本章内容流水线基本概念流水线的分类幻灯片 29/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念w 吞吐率吞吐率w 加速比加速比w 效效 率率w 流水线最佳段数的选择流水线最佳段数的选择w 性能分析举例性能分析举例幻灯片 30/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 单位时间内

22、能流出的任务数或能流出的单位时间内能流出的任务数或能流出的结果数。结果数。任务数；任务数；处理完成处理完成n个任务所用的时间。个任务所用的时间。本章内容流水线基本概念流水线的性能分析8 之 1幻灯片 31/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 假设在流水线各段的执行时间均相等，输入到流水线假设在流水线各段的执行时间均相等，输入到流水线中的任务是连续的理想情况下，一条单功能中的任务是连续的理想情况下，一条单功能m段线性流水段线性流水线能够在线能够在m+n-1个时钟周期内完成个时钟周期内完成n个任务。个任务。本章内容流水线基本概念流水

23、线的性能分析8 之 21时间时间空间空间S123 n-1nS2Sm123 n-1n123 n-1nm t(n-1) tn t(m-1) tTm幻灯片 32/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线的性能分析8 之 3幻灯片 33/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 假设在流水线各段的执行时间不相等，输入假设在流水线各段的执行时间不相等，输入到流水线中的任务是连续的理想情况下。到流水线中的任务是连续的理想情况下。w 本章内容流水线基本概念流水线

24、的性能分析8 之 4幻灯片 34/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线的性能分析8 之 5 流水线的流水线的TP和和TPmax主要由流水线中执行时间主要由流水线中执行时间最长的那个功能段来决定，这个功能段就成了整最长的那个功能段来决定，这个功能段就成了整个流水线的个流水线的“瓶颈瓶颈”。将流水线中的将流水线中的“瓶颈瓶颈”再细分；再细分；通过重复设置多套瓶颈功能段，让多个瓶颈通过重复设置多套瓶颈功能段，让多个瓶颈功能段并行工作。功能段并行工作。幻灯片 35/264Computer Architectur

25、eV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线的性能分析8 之 6S1 t1= tS2 t2=3 tS3 t3= tS4 t4= t输输出出1时间时间空间空间S1S2S3S4ti(n-1) t2Tm23n123n123n123n输输入入幻灯片 36/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线的性能分析8 之 7S1输入输入输出输出 tS2-1 tS2-2 tS2-3 tS3 tS4 tS2(3 t)S1输入输入输出输出 t1= tS2-3S2-2S2-1S3S4 t3= t

26、 t4= t t2=3 t幻灯片 37/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线的性能分析8 之 81时间时间空间空间23nS1S2-145614n-2n-1n-225n-136n123n456n-2n-1123n456n-2n-1S2-2S2-3S3S4幻灯片 38/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线的性能分析 完成同样一批任务，不使用流水线所用完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比。

27、的时间与使用流水线所用的时间之比。顺序执行所用的时间；顺序执行所用的时间；使用流水线所用的时间。使用流水线所用的时间。3 之 1幻灯片 39/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 假设在流水线各段的执行时间都相等，输入到假设在流水线各段的执行时间都相等，输入到流水线中的任务是连续的理想情况下。流水线中的任务是连续的理想情况下。w 本章内容流水线基本概念流水线的性能分析3 之 2幻灯片 40/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 假设在流水线各段的执行时间不相等，输入到

28、假设在流水线各段的执行时间不相等，输入到流水线中的任务是连续的理想情况下。流水线中的任务是连续的理想情况下。w 本章内容流水线基本概念流水线的性能分析3 之 3幻灯片 41/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线的性能分析 是指流水线的设备利用率。在时空图上，流水是指流水线的设备利用率。在时空图上，流水线的效率定义为线的效率定义为n个任务占用的时空区与个任务占用的时空区与m个功能个功能段总的时空区之比。段总的时空区之比。1时间时间空间空间S1nS2Sm1n 1n4 之 1幻灯片 42/264Compute

29、r ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 假设在流水线各段的执行时间都相等，输入到假设在流水线各段的执行时间都相等，输入到流水线中的任务是连续的理想情况下。流水线中的任务是连续的理想情况下。w 本章内容流水线基本概念流水线的性能分析4 之 2幻灯片 43/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 假设在流水线各段的执行时间不相等，输入到假设在流水线各段的执行时间不相等，输入到流水线中的任务是连续的理想情况下。流水线中的任务是连续的理想情况下。w 本章内容流水线基本概念流水线的性能分析4 之 3幻

30、灯片 44/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 其中，其中， i为为i段的权值，段的权值， i 流水线基本概念流水线的性能分析4 之 4mm1ii幻灯片 45/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线的性能分析 功能段数量的增加能提高流水线的吞吐率和加功能段数量的增加能提高流水线的吞吐率和加速比，但使流水线价格增加（锁存器数量的增速比，但使流水线价格增加（锁存器数量的增加），一条指令执行的总时间增加（锁存器的总加），一条指令执行的总时间增加（

31、锁存器的总延迟时间增加）。所以从性价比角度出发流水线延迟时间增加）。所以从性价比角度出发流水线存在着最佳段数。存在着最佳段数。2 之 1幻灯片 46/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 对自变量对自变量m求导，求求导，求PCR的最大值，得到最佳段数为：的最大值，得到最佳段数为：本章内容流水线基本概念流水线的性能分析任务总时间任务总时间锁存器时间锁存器时间功能段数功能段数所有功能段价格所有功能段价格锁存器价格锁存器价格2 之 2幻灯片 47/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科

32、学与工程系本章内容流水线基本概念流水线的性能分析用一条用一条4段浮点加法器流水线求段浮点加法器流水线求8个浮点数的个浮点数的和，要求所用时间最短，求流水线的吞吐率、和，要求所用时间最短，求流水线的吞吐率、加速比和效率。加速比和效率。ZABCDEFGH由于存在着数据相关，如果直接交与流水线由于存在着数据相关，如果直接交与流水线处理，效果与顺序执行完全一样，因此先作处理，效果与顺序执行完全一样，因此先作一个简单变换，然后交与流水线处理。一个简单变换，然后交与流水线处理。Z=(A+B)+(C+D)+(E+F)+(G+H)3 之 1幻灯片 48/264Computer ArchitectureV3同济

33、大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念流水线的性能分析3 之 21时间时间空间空间2 3求阶差求阶差45671 2 3 45671 2 3 45671 2 3 4567对阶对阶尾数加尾数加规格化规格化加数加数A C E GA+B E+FB D F HC+D G+HA+B+C+DE+F+G+H结果结果 A+BC+DE+FG+HA+B+C+DE+F+G+HZ被被加数加数幻灯片 49/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系w 流水线的吞吐率为：流水线的吞吐率为：w 流水线的加速比为：流水线的加速比为：w 流水线

34、的效率为：流水线的效率为：本章内容流水线基本概念流水线的性能分析3 之 3幻灯片 50/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念w 调度目的调度目的w 非线性流水线的冲突非线性流水线的冲突w 无冲突调度方法无冲突调度方法w 优化调度方法优化调度方法幻灯片 51/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术 非线性流水线的调度目的是要找出一个非线性流水线的调度目的是要找出一个最小的循环周期，按照这周期向流水线输入最小

35、的循环周期，按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。突，而且流水线的吞吐率和效率最高。幻灯片 52/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术 向一条非线性流水线的输入端顺序输入两个任向一条非线性流水线的输入端顺序输入两个任务之间的时间间隔称为启动距离务之间的时间间隔称为启动距离/等待时间等待时间。 几个任务同时争用同一个流水线功能段的情况几个任务同时争用同一个流水线功能段的情况称为非线性流水线的冲突称

36、为非线性流水线的冲突。 引起非线性流水线冲突的启动距离称为禁止启引起非线性流水线冲突的启动距离称为禁止启动距离。动距离。5 之 1幻灯片 53/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术5 之 2输出输出S1S2S3S4输入输入S4S3S2S17654321 时间时间流水段流水段幻灯片 54/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术5 之 3幻灯片 55/264Computer Archit

37、ectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术5 之 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 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

38、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 启启动动周周期期 重重复复启启动动周周期期 不发生冲突的启动距离一般是一个循环数列，称为非线不发生冲突的启动距离一般是一个循环数列，称为非线性流水线的性流水线的启动循环启动循环，记作（，记作（1，7）。）。幻灯片 56/264Computer ArchitectureV3同济大学.电子与信息

39、工程学院.计算机科学与工程系 启动距离启动距离5也可以认为是一个循环数列，称为非线性流也可以认为是一个循环数列，称为非线性流水线的水线的恒定循环恒定循环，记作（，记作（5）。）。本章内容流水线基本概念非线性流水线的调度技术5 之 5启启动动距距离离为为 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

40、 X X1 1 X X1 1 X X2 2 X X2 2 S S4 4 X X1 1 X X2 2 启启动动周周期期 重重复复启启动动周周期期 幻灯片 57/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术S4S3S2S17654321 时间时间流水段流水段12 之 1S1S2S3S4输入输入输出输出幻灯片 58/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术w 由预约表得到禁止向量由预约表得到禁止向量

41、w 由禁止向量得到冲突向量由禁止向量得到冲突向量w 由冲突向量构造调度流水线的状态图由冲突向量构造调度流水线的状态图w 在状态图中找出可用启动距离，并计算平均启在状态图中找出可用启动距离，并计算平均启动距离动距离w 找出平均启动距离最小的启动循环或恒定循环找出平均启动距离最小的启动循环或恒定循环12 之 2幻灯片 59/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术无冲突调度方法w 由预约表得到禁止向量由预约表得到禁止向量将一条非线性流水线的所有各功能段禁止将一条非线性流水线的所有各功能段禁止启动

42、距离组合在一起形成的数列。启动距离组合在一起形成的数列。将预约表中的每一行中任意两个将预约表中的每一行中任意两个“”之之间的距离都计算出来，去掉重复的，由这间的距离都计算出来，去掉重复的，由这些数形成禁止向量。些数形成禁止向量。上例所示非线性流水线的禁止向量为（上例所示非线性流水线的禁止向量为（2，4，6）。）。12 之 3幻灯片 60/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术无冲突调度方法w 由禁止向量得到冲突向量由禁止向量得到冲突向量冲突向量用一个冲突向量用一个m位的二进制数表示（其位的

43、二进制数表示（其中中m是禁止向量中的最大值），一般格式是禁止向量中的最大值），一般格式为为C=（CmCm-1CiC2C1），），若若i在禁止在禁止向量中，则向量中，则Ci =1，否则否则Ci =0，其中其中Cm一一定为定为1。上例所示非线性流水线的冲突向量为上例所示非线性流水线的冲突向量为C=（101010）。12 之 4幻灯片 61/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术无冲突调度方法w 由冲突向量构造调度流水线的状态图由冲突向量构造调度流水线的状态图1. 将冲突向量将冲突向量C作为初始

44、冲突向量送入一个作为初始冲突向量送入一个m位逻辑右移位逻辑右移移位器，移位移位器，移位m次；次；w若移出的是若移出的是“0”，用移位器中的值与初始冲突向，用移位器中的值与初始冲突向量作量作“按位或按位或”运算，得到一个新的冲突向量；运算，得到一个新的冲突向量；w若移出的是若移出的是“1”，不作任何处理。，不作任何处理。2. 将中间形成的每一个新的冲突向量同样处理；将中间形成的每一个新的冲突向量同样处理；3. 画出状态图。画出状态图。 在初始冲突向量和所有的新形成的冲突向量之间用在初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接，表示各种状态之间的转换关系。带箭头的线连接，表示各种状态之

45、间的转换关系。12 之 5幻灯片 62/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术无冲突调度方法12 之 6幻灯片 63/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术无冲突调度方法w 在状态图中找出可用启动距离，并计算平在状态图中找出可用启动距离，并计算平均启动距离均启动距离 在状态图中从初始状态出发，能构成一种间在状态图中从初始状态出发，能构成一种间隔拍数呈周期性重复的方案就是可用启动距离。隔

46、拍数呈周期性重复的方案就是可用启动距离。即：找出所有的即：找出所有的简单循环简单循环（是指在状态图中各种（是指在状态图中各种冲突向量只经过一次的启动循环）。冲突向量只经过一次的启动循环）。12 之 7幻灯片 64/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术无冲突调度方法简单循环简单循环平均启动距离平均启动距离1，743，755，763，5，755，3，753，54557712 之 8幻灯片 65/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程

47、系本章内容流水线基本概念非线性流水线的调度技术无冲突调度方法w 找出平均启动距离最小的启动循环或恒定找出平均启动距离最小的启动循环或恒定循环循环 （1，7）和（）和（3，5） （5）12 之 9幻灯片 66/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术无冲突调度方法12 之 10S3S2S143215S46712345678910 11 12 13 14 15 16 17 18 19 20 S1 X1 X2X1 X2 X3 X4X3 X4 X5 X6S2X1 X2X1 X2X3 X4X3 X4X

48、5 X6S3X1 X2 X1 X2X3 X4 X3 X4X5 X6S4X1 X2X3 X4X5最小启动循环（最小启动循环（1，7）的流水线工作状态）的流水线工作状态启动周期启动周期重复启动周期重复启动周期幻灯片 67/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术无冲突调度方法12 之 11S3S2S143215S46712345678910 11 12 13 14 15 16 17 18 19 20 S1 X1X2X1X3 X2X4X3X5 X4X6S2X1X2 X1X2 X3X4 X3X4 X

49、5S3X1X1 X2X2X3X3 X4X4X5S4X1X2X3X4X5最小启动循环（最小启动循环（3，5）的流水线工作状态）的流水线工作状态启动周期启动周期重复启动周期重复启动周期幻灯片 68/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术无冲突调度方法12 之 12S3S2S143215S46712345678910 11 12 13 14 15 16 17 18 19 20 S1 X1X2 X1X3 X2X4 X3S2X1X1 X2X2 X3X3 X4S3X1X1X2X2X3X3X4X4S4X

50、1X2X3X4最小恒定循环（最小恒定循环（5）的流水线工作状态）的流水线工作状态启动周期启动周期重复启动周期重复启动周期幻灯片 69/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术 当采用最小启动循环启动非线性流水线时，没当采用最小启动循环启动非线性流水线时，没有充分发挥非线性流水线的效率，因为流水线中有充分发挥非线性流水线的效率，因为流水线中的许多流水段还有空闲，即使最繁忙的流水段也的许多流水段还有空闲，即使最繁忙的流水段也有空闲。有空闲。 采用非线性流水线的优化调度方法（预留算采用非线性流水线

51、的优化调度方法（预留算法），可以使流水线的工作效率最高。法），可以使流水线的工作效率最高。7 之 1幻灯片 70/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术 L.E.Shar于于1972年提出流水线最小平均启年提出流水线最小平均启动距离的限制范围并于动距离的限制范围并于1992年进行了证明：年进行了证明：w 最小平均启动距离小于等于状态图中任意一个最小平均启动距离小于等于状态图中任意一个简单循环的平均启动距离。简单循环的平均启动距离。w 最小平均启动距离的上限是冲突向量中最小平均启动距离的上限

52、是冲突向量中1 1的个数的个数再加上再加上1 1。7 之 2幻灯片 71/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术 最小启动距离等于预约表中任意一行中最小启动距离等于预约表中任意一行中“”的最大个的最大个数。数。 为简化流水线的控制逻辑，一般采用恒定循环作为最小为简化流水线的控制逻辑，一般采用恒定循环作为最小启动循环。启动循环。 对预约表中任意一行中任意两个对预约表中任意一行中任意两个“”之间的距离是最之间的距离是最小启动距离整数倍的通过插入延迟进行预留。小启动距离整数倍的通过插入延迟进行预

53、留。7 之 3幻灯片 72/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术S4S3S2S17654321 时间时间流水段流水段S1S2S3S4输入输入输出输出7 之 4幻灯片 73/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容流水线基本概念非线性流水线的调度技术S1S2S3S4输入输入输出输出D1时间时间12345678功功能能段段S1S2S3S4延迟延迟D17 之 5幻灯片 74/264Computer ArchitectureV3

54、同济大学.电子与信息工程学院.计算机科学与工程系 从状态从状态图中很容易图中很容易可以看出：可以看出：流水线的最流水线的最小启动循环小启动循环是（是（2）。本章内容流水线基本概念非线性流水线的调度技术7 之 6幻灯片 75/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系 在非线性流水线中，在非线性流水线中，“”最多的流水段一定是最多的流水段一定是“瓶瓶颈颈”流水段。实现最优调度的目标流水段。实现最优调度的目标是使是使“瓶颈瓶颈”流水段处流水段处于忙碌状态，没有空闲周期于忙碌状态，没有空闲周期。本章内容流水线基本概念非线性流水线的调度技术按按

55、照照最最小小启启动动循循环环（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 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

56、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 7 之 7幻灯片 76/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系w 基本概念基本概念w 资源相关资源相关w 数据相关数据相关w 控制相关控制相关w 综合应用综合应用w 循环处理循环处理本章内容幻灯片 77/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容相关性分析技术 相关（相关（

57、Correlation or Dependency）也称为冲突也称为冲突（Hazard）是指邻近指令之间存在着某种关系，影响指令是指邻近指令之间存在着某种关系，影响指令的重叠执行或流水线的正常运行。的重叠执行或流水线的正常运行。 有三种类型的相关：有三种类型的相关：争用部件。：争用部件。：改变操作数的读写顺序，使得顺序执行与：改变操作数的读写顺序，使得顺序执行与流水执行时结果不同。流水执行时结果不同。：分支、转子程序、中断。：分支、转子程序、中断。2 之 1幻灯片 78/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容相关性分析技术

58、在介绍相关性分析技术时，我们以一个在介绍相关性分析技术时，我们以一个典型的典型的RISC指令流水线（指令流水线（MIPS64指令集）指令集）为例进行介绍：为例进行介绍：w MIPS基本流水线基本流水线w MIPS扩展流水线扩展流水线2 之 2幻灯片 79/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容相关性分析技术示例环境说明 采用采用MIPS64（MIPS的的64位版本）的整数子集：位版本）的整数子集：ALU指指令（令（）、）、 load（）/store（）指令和分支指令（指令和分支指令（）。）。 每一条每一条RISC指令的执行至

59、多需要指令的执行至多需要5个时钟周期：个时钟周期：、和和。13 之 1幻灯片 80/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容相关性分析技术示例环境说明 根据根据PC指示的地址从存储器中取指令并装入指示的地址从存储器中取指令并装入指令寄存器（指令寄存器（IR），），同时同时PC加加4以获取下一条指以获取下一条指令的地址。令的地址。IR中保存下一个时钟周期需要的指令，中保存下一个时钟周期需要的指令，NPC中保存下一条指令的中保存下一条指令的PC。13 之 2幻灯片 81/264Computer ArchitectureV3同济大学

60、.电子与信息工程学院.计算机科学与工程系 MEM/WB 指 令数据 存储器 通用寄存器组 符号 位 扩展 PC =0? ADD 16 32 4 存储器 M U X 1 M U X 3 IR A B Imm IRrs IRrt MEM/WB.IR NPC IR ALUo B IR LMD ALUo IR EX/MEM ID/EX IF/ID ADD M X 4 U ALU 本章内容相关性分析技术示例环境说明13 之 3幻灯片 82/264Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容相关性分析技术示例环境说明 ，并结束分支指，并结束分支指令