清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授 2005年5月 计算机科学与技术系研究生课程 高等计算机系统结构 清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授 2005年5月

高等计算机系统结构 第一章 高等计算机的核心技术——并行处理 第二章 加速比性能模型与可扩展性分析 第三章 互连与通信 第四章 划分与调度 第一章 高等计算机的核心技术——并行处理 第二章 加速比性能模型与可扩展性分析 第三章 互连与通信 第四章 划分与调度 第五章 并行存储器系统 第六章 Cache Coherence 第七章 Memory Consistency 第八章 指令级并行处理

第八章 指令级并行处理 8.1 指令级并行概述 8.2 多发射结构 8.3 指令级并行的编译技术 8.1.1 指令级并行处理 8.1.2 减少每条指令执行的平均周期数 8.1.3 改进CPI的途径 8.2 多发射结构 8.3 指令级并行的编译技术

8.1 指令级并行概述 8.1.1 指令级并行处理 过去25年，微机性能差不多每年以50%的速度提高： （1）由于电路速度的改进，占年增长率一半不到。 （2）8位16位32位64位，CISC RISC； （3）片上cache，FLP H/W，图形加速H/W；

（4）采用流水技术 （5）电路的集成度也以每年40%的比例增长 10年来： 微处理器的周期从100200ns 少于4ns，大约降低了25倍； DRAM的访问时间从150 180ns 60 80ns，大约3倍，需要用cache来弥补。

指令级并行处理（ILPP，Instruction Level Parallel Processing）是实行低层机器操作的并行执行，如存、取、整数加和浮点乘等。

8.1.2 减少每条指令执行的平均周期数 RISC比CISC机器的CPI（Cycles per Instruction，平均周期数）要小。 CISC一般用微码技术，一条指令往往要用好几个周期才能实现，复杂指令所需的周期数则更多，CISC机器CPI一般为4-6； RISC一般指令一个周期完成，所以CPI=1，但LOAD、STORE等指令要长些，所以RISC机器的CPI 约大于1。

RISC技术未来发展的方向是进一步减少CPI； CISC机器也在减少CPI； 一些新型的微处理器的CPI（不论是RISC还是CISC），都在逐渐趋向于2和1之间。 例： Intel的5MHz的80286（1986），CPI=5 10MHz的68010（1983），CPI=12 22MHz的68030（1988），CPI=5 SUN SPARC（1987），CPI=1-2

8.1.3 改进CPI的途径 给定的工作频率下，要进一步减小CPI，必须进一步提高RISC内部的并行性。 （1）哈佛结构：即设计分开的指令cache和数据cache，可以并行工作。 （2）多端口的寄存器堆。如果一个寄存器堆有两个源操作数端口和一个目的操作数端口，那么两个源操作数可以同时取出，还可以写入或取出另一条指令的目的操作数。

（3）流水线的级分得更细。 （4）编译优化技术。充分利用硬件资源、优化分配寄存器。 （5）超标量（super scalar）结构。即设置多个执行部件。 （6）超流水线（superpipeline）结构。 （7）VLIW（Very Long Instruction Word）

第八章 指令级并行处理 8.1 指令级并行概述 8.2 多发射结构 8.3 指令级并行的编译技术 8.2.1 流水线结构 8.2.2 超标量机的典型结构 8.2.3 VLIW机的结构框图 8.3 指令级并行的编译技术

8.2 多发射结构 单发射结构：每个周期只发射一条指令； 多发射结构：在流水线结构基础上，每个周期可以发射多条指令。比如： 超标量 超流水线 VLIW 数据流

8.2.1 流水线结构 1.一般流水线结构 IPC（Instruction Per Cycle）=1，但由于数据相关、转移相关和资源相关使得IPC<1。 n IF ID EX WR IF ID EX WR n+1 IF ID EX WR n+2

2.超标量结构 主要特点： （1）配置多个处理部件，采用多条流水线并行处理； （2）能同时对若干条指令进行译码，将可并行执行的指令送往不同的执行部件，从而达到每个周期启动多条指令的目的。 （3）在程序运行期间由硬件完成指令调度。 下图中，一个周期内同时发出三条指令，有多个执行部件，三条指令发到三个独立的执行部件去分别执行。

IF ID EX WR IF ID EX WR IF ID EX WR 每拍启动3条指令，要求并行度=3

3.超流水线结构 下图中，一个流水段（一个周期）分成三个子段，每个子段取出的仍只有一条指令，但总体来看，一个周期内取出了三条指令，执行部件可以一套，每个部件在一个子段时间内完成。

每1/3个周期启动一条指令，要求并行度=3 IF ID EX WR IF ID EX WR IF ID EX WR IF ID EX WR

超标量和超流水线的比较 超标量：工作部件多，晶体管数目也多， 每个部件的工作速度相对的可以低一些。以空间换取时间。 超流水线：工作部件少，晶体管数目少了，每一个部件必须在一个子周期内执行，工作速度较高。以时间换取了空间。 大部分新一代的RISC都属于超标量结构，比如：i860，i960 ，Motorola 88110 ，IBM Power 6000 ，SUN/TI的Super SPARC。 MIPS的R4000属于超流水线结构。

如DEC的Alpha和Intel Pentium。 4.超流水线超标量RISC 如DEC的Alpha和Intel Pentium。 IF ID EX WR IF ID EX WR IF ID EX WR 每拍启动9条指令，要求并行度=9

5.VLIW（超长指令字） 1983年，Yale大学Fisher教授首先提出。 一条长指令来实现多个操作的并行执行，以减少对存储器的访问，这种长指令往往达上百位，甚至上千位。 如下面的图。每拍启动一条长指令，执行3个操作，相当于3条指令，要求并行度为3。

IF ID EX WR EX EX IF ID EX WR EX EX IF ID EX WR EX EX 每拍启动1条指令，要求并行度=3

主要特点： 单一的控制流。只有一个控制器，每个周期启动一条长指令。 超长指令字被分成多个控制字段，每个字段直接独立的控制每个功能部件。 含有大量的数据通路和功能部件，由于编译器在编译时间已经考虑可能出现的数据相关和资源相关，故控制硬件比较简单。 在编译阶段完成超长指令中多个可并行执行操作的调度（超长指令字的生成是由编译器完成）。

区分一条指令和一个操作： 一个操作是指一个计算单位，如加、取、转移等。这在顺序结构中就是一条指令。而一条VLIW指令是包含一组同时发出的操作。编译器的任务就是要确定哪些操作可以组合在一条指令中。组合在一条VLIW指令中的所有操作是同时开始执行的。

8.2.2 超标量的典型结构 D-cache 主 存 存储器操作部件 指 RF 令 寄存器 1 调 堆 I-cache 度 ALU 2 转移控制部件 2条指令并行 取出并同时译码 状态 记录部件

指令的执行部件： 存储器操作部件：执行Load、Store指令 ALU：整数运算 转移控制部件：执行转移指令

状态记录部件（调度部件）： 进行流水动态调度。依靠硬件在程序运行过程中对可能出现的相关情况加以检测，从而保证流水线中的各个功能部件能最大限度的重叠工作。 它对流水线中的各个功能部件的工作状态、进入流水线中的各条指令的工作状态、它们所使用的源寄存器和目的寄存器情况等进行集中的统一记录和调度。 在译码阶段，状态记录部件根据所记录的状态决定是否将译码后的指令发送给有关功能部件进行处理。

状态记录部件主要检查： 该指令要使用的功能部件是否已被流水线中的其它指令占用（资源冲突）； 该指令的源操作数寄存器是否为其它指令的目的寄存器，或者它所要写入的目的寄存器又正好是前面其它指令所要读出的操作数，或是要写入的目的寄存器。即检查是否存在RAW、WAR、WAW的数据相关。

RAW（Read After Write）： 指令j试图在指令i写入寄存器前就读出该寄存器的内容； WAR（Write After Read）： 指令j试图在指令i读出寄存器前就写入该寄存器的内容； WAW（Write After Write）： 指令j试图在指令i写入寄存器前就写入该寄存器的内容；

8.2.3 VLIW机的结构框图 主 存 RF（寄存器堆） LD/ST1 LD/ST2 FADD FMUL LD/ST1 LD/ST2 存/取1 存/取2 浮点加 浮点乘

例：要执行以下赋值语句。 C = A + B K = I + J L = M - K Q = C  K 假设LOAD/STORE，FADD一个周期完成， FMUL二个周期完成。 若按串行操作进行，则其所用的指令序列如下图所示。共需14个周期。

源代码 源代码 所需周期 C=A+B LOAD A LOAD B C=A+B STORE C 1 K=I+J LOAD I LOAD J K=I+J STORE K 1 L=M-K LOAD M L=M-K STORE L 1 Q=C*K Q=C*K STORE Q 2 1 共需14个周期

超标量结构、超流水线结构一般采用指令窗方法，把一段指令（长度为窗口的大小，例为8）取到窗口中，判断这段指令能否并行执行。 压缩技术——表调度法： LOAD A LOAD B LOAD I LOAD J C=A+B LOAD M STORE C K=I+J STORE K L=M-K Q=C*K STORE L STORE Q 只需要6个周期。 超标量结构、超流水线结构一般采用指令窗方法，把一段指令（长度为窗口的大小，例为8）取到窗口中，判断这段指令能否并行执行。

第八章 指令级并行处理 8.1 指令级并行概述 8.2 多发射结构 8.3 指令级并行的编译技术 8.3.1 软件流水方法 8.3.2 循环体展开

8.3 指令级并行的编译技术 8.3.1 软件流水方法 例1：在一台2发射处理机上执行下列程序。 Do I =1，N A(I) = A(I) * B + C End do 假定存储器访问Read(读)Write(写)用一个周期。 每一个算术操作Mul、Add需二个周期，执行一次迭代需要6个周期。如下：

采用流水方法（做4次迭代情况）的情形如下： 周期 指令 注释 1 READ /取A[I]/ 2 MUL /乘B/ 3 4 ADD /加C/ 5 6 WRITE /存A[I]/ 完成N次迭代需要6N个周期。 采用流水方法（做4次迭代情况）的情形如下：

周期 迭代 1 2 3 4 1 read 2 mul 3 read 4 mul 5 add read 6 mul 7 add read 8 write mul 9 add 10 write 11 add 12 write 13 14 write

每次迭代通过流水线需要8个周期，但4次迭代只需要14个时钟周期。与非流水线执行相比，加速比可达到： 用流水线执行N次迭代需要2N+6个周期，加速比为：

8.3.2 循环体展开 例1：一个循环体，对存储器中的一个指定向量（双精度）加上一个标量值： Loop： LD F0, 0(R1) /M[(R1)+0]F0, 读向量元素/ ADDD F4, F0, F2 /(F0)+(F2)F4/ SD 0(R1), F4 /(F4)M[(R1)+0] 存向量元素/ SUB R1, R1, #8 /(R1)-8R1 将指针减去8个字节/ BNEZ R1, Loop /若(R1)0, 则跳转/

假设FP ALU 使用另一个FP ALU指令操作结果需要等待3个周期，STORE指令欲使用由FP ALU指令产生的结果需要等待2个周期，FP ALU指令使用LOAD的结果等待1个周期。 则上面过程的实际执行情况如下：

执行一遍循环体需要9个时钟周期。 Loop： LD F0, 0(R1) STALL /停顿/ ADDD F4, F0, F2 STALL SD 0(R1), F4 SUB R1, R1, #8 BNEZ R1, Loop 执行一遍循环体需要9个时钟周期。

由于SUB和SD交换了先后顺序，因此SD指令中的R1的偏移量需由原来的0变为8。 对上述循环体进行调度，使其变成如下： Loop： LD F0, 0(R1) STALL ADDD F4, F0, F2 SUB R1, R1, #8 BNEZ R1, Loop SD 8(R1), F4 由于SUB和SD交换了先后顺序，因此SD指令中的R1的偏移量需由原来的0变为8。

将循环体展开3次后再进行调度： Loop： LD F0, 0(R1) 2 ADDD F4, F0, F2 3 SD 0(R1), F4 1 周期 Loop： LD F0, 0(R1) 2 ADDD F4, F0, F2 3 SD 0(R1), F4 1 LD F6, -8(R1) 2 ADDD F8, F6, F2 3 SD -8(R1), F8 1 LD F10, -16(R1) 2 ADDD F12, F10, F2 3 SD -16(R1), F1 1

循环展开3次，总计27个周期。对展开后的代码进行调度，如下： LD F14, -24(R1) 2 ADDD F16, F14, F2 3 SD -24(R1), F16 1 SUB R1, R1, #32 1 BNEZ R1, Loop 2 循环展开3次，总计27个周期。对展开后的代码进行调度，如下：

Loop： LD F0, 0(R1) LD F6, -8(R1) LD F10, -16(R1) LD F14, -24(R1) ADDD F4, F0, F2 ADDD F8, F6, F2 ADDD F12, F10, F2 ADDD F16, F14, F2 SD 0(R1), F4 SD -8(R1), F8 SD -16(R1), F1 SUB R1, R1, #32 BNEZ R1, Loop SD -24(R1), F16

调度后的代码每个循环只要14个周期即可。 循环体展开法通过增加源程序代码长度来获得较好的调度效果。