计算机系统结构的基本概念

1. 注意每一章的名词解释，计算机体系结构的概念、分类、定义及其性价比，CPI的计算 2. Amdahl定律的应用

计算机体系结构的概念：建筑物的设计或式样, 通常指一个系统的外貌；从外部来研究计算机系统；

使用者所看到的物理计算机的抽象； 编写出能够在机器上正确运行的程序所必须了解到的计算机属性。 计算机系统结构定义：程序员所看到的计算机系统的属性, 即概念性结构和功能特性

功能特性 指令系统及其执行模式

• 数据表示：硬件能够直接认别和处理的数据类型； • 寻址技术：编址方式、寻址方式和定位方式等；

• 寄存器组织：操作数寄存器、变址寄存器、控制寄存器及专用寄存器的定义、数量和使用规则等； • 指令系统：操作类型、格式，指令间的排序控制等； • 中断系统：中断类型、中断级别和中断响应方式等； • 存储系统：寻址空间、虚拟存储器、Cache存储器等； • 处理机工作状态：定义和切换方式，如管态和目态等； • 输入输出系统：数据交换方式、交换过程的控制等； • 信息保护：信息保护方式和硬件对信息保护的支持等。

<计算机组成技术：从内部研究计算机系统，计算机组成是指计算机系统结构的逻辑实现。>

性价比: 是一个性能与价格之间的比例关系，具体公式：性价比=性能/价格。通常不会在同一性能基础上比较或比较的机会较少。性价比应该建立在你对产品性能要求的基 础上，也就是说，先满足性能要求，再谈价格是否合适，由于性价比是一个比例关系，它存在其适用范围和特殊性，不能一概而论。

价格与性能的关系：

• 摩尔定理：速度每10年左右提高100倍，但价格基本维持不变 • 用当前同样的价格，在5年之后能买到性能高出10倍的计算机

硬件与软件的价格比例：

• 硬件在整个计算机系统价格中所占的比例在下降，软件所占的比例在上升 • 目前软件价格已经超过硬件价格

软件与硬件实现的特点:

• 硬件实现：速度快、成本高；灵活性差、占用内存少 • 软件实现：速度低、复制费用低；灵活性好、占用内存多 计算机系统的分类

按处理机性能分类: 1. 按大小划分

种类：巨型、大型、中型、小型、微型机 划分原则：以性能为特征，按价格来划分

存在问题：划分的标准是随时间而变化，每５年左右降低一个等级

设计方法：最高性能 特殊用途 ; 最佳性能价格比 一般商用计算机

最低价格 家用计算机等

2. 按用途划分

种类：科学计算、事务处理、实时控制、工作站、服务器、家用计算机等。 划分原则：科学计算：浮点计算速度; 事务处理：字符处理、十进制运算

实时控制：中断响应速度、I/0能力; 工作站：图形处理能力

服务器：数据处理速度，数据存储能力; 家用计算机：价格便宜，软件丰富

发展方向：具备上述所有功能的通用处理机;各种专用处理机、协处理器、嵌入式处理机 3. 按数据类型划分

定点计算机、浮点计算机、向量计算机、堆栈计算机等 4. 按处理机个数和种类划分

单处理机 并行处理机、多处理机、分布处理机 关联处理机 超标量处理机, 超流水线处理机, VLIW处理机

SMP(对称多处理机)、MPP(大规模并行处理机)、机群(Cluster)系统等

5. 按所使用的器件划分 按使用的器件划分计算机系统的时代

第一代：电子管(Valve)计算机

第二代：晶体管(Transistor)计算机 第三代：集成电路(LSI)计算机

第四代：大规模集成电路(VLSI)计算机 第五代：智能计算机？

目前的绝大部分计算机系统是VLSI计算机

佛林分类法: 1966年由Michael.J. Flynn 提出,按照指令流和数据流的多倍性特征进行分类 指令流：机器执行的指令序列 数据流：由指令流调用的数据序列

多倍性(multiplicity)：在系统性能瓶颈部件上同时处于同一执行阶段的指令或数据的最大可能个数

(1)单指令流单数据流 SISD

单功能部件处理机;多功能部件处理机;流水线处理机: 指标量流水线处理机 (2)单指令流多数据流 SIMD

并行处理机、阵列处理机、向量处理机、相联处理机、超标量处理机、超流水线处理机

多个PU按一定方式互连，在同一个CU控制下，对各自的数据完成同一条指令规定的操作；从CU看指令顺序执行，从PU看数据并行执行。 (3)多指令流单数据流 MISD

几条指令对同一个数据进行不同的处理，实际上不存在 (4)多指令流多数据流 MIMS 紧密偶合: 松散偶合： 主要缺点： (1)分类太粗

在SIMD中包括有多种处理机;对流水线处理机的划分不明确，标量流水线为SISD，向量流水线为SIMD (2)根本问题是把两个不同等级的功能并列对待,数据流受指令流控制，造成MISD不存在 (3)非冯计算机的分类？其他新型计算机的分类

库克分类法:1978年由 D. J. Kuck提出,按控制流和执行流分类，四种类型

(1)单指令流单执行流SISE(Single Instruction Single Executionstream) 典型的单处理机

(2)单指令流多执行流SIME(Single Instruction Multiple Executionstream) 多功能部件处理机、相联处

理机、向量处理机、流水线处理机、超流水线处理机、超标量处理 机、SIMD并行处理机

(3)多指令流单执行流MISE(Multiple Instruction Single Executionstream) 多道程序系统 (4)多指令流多执行流MIME(Multiple Instruction Multiple Executionstream) 典型的多处理机 主要缺点: 有些系统，如分布处理机等，没有总控制器; 分类级别太低，没有处理机级和机器级 分类太粗，如SIME中包含了多种处理机

冯泽云分类法1972年美籍华人冯泽云提出，用最大并行度对计算机系统进行分类 单位时间内能处理的最大二进制位数

例如：同时处理的字宽为n，位宽为m，则最大并行度定义为：Pm ＝ m  ｎ

平均并行度：假设每个时钟周期 ti 内能同时处理的二进位数为Bi，则n个时钟周期内的平均并行度为：

表示方法：处理机名(m，ｎ)

(1)字串位串WSBS(Word Serial and Bit Serial) 串行计算机； m＝1,ｎ＝1；如：EDVAC(1, 1)

(2)字并位串WPBS(Word Parallel and Bit Serial) 传统单处理机； m＝1,ｎ > 1；如：Pentium(32, 1) (3)字串位并WSBP(Word Serial and Bit Parallel) 并行计算机、MPP、相联计算机；m > 1,ｎ＝1； 如：MPP(1, 16384), STARAN(1, 256)，DAP

(4)字并位并WPBP(Word Parallel and Bit Parallel) 全并行计算机；m > 1, ｎ > 1；如：ASC(64, 32)， IILIAC IV(64, 64) , PEPE(32, 288)，Cmmp(16, 16) 主要缺点：

仅考虑数据并行，没有考虑指令, 任务, 作业的并行

汉德勒分类法: 由Wolfgan Handler于1977年提出,又称为ESC(Erlange Classification Scheme)分类法

根据并行度和流水线分类,把计算机硬件结构分成三个层次， 并分别考虑它们的可并行性和流水处理程度。 (1)程序级k：程序控制部件(PCU)的个数；

(2)操作级d：算术逻辑部件(ALU)或处理部件（PU）的个数； (3)逻辑级w：每个算术逻辑部件包含的逻辑线路(ELC)的套数。 表示方法：t(系统型号)＝(k，d，w) 第二章 指令系统

1.操作码的优化（掌握） Huffman编码法 扩展编码法 掌握2-4 ，2-4-8扩展编码法 2.精简指令系统（RISC）的特点及所用到的关键技术

指令格式的优化设计: 主要目标：节省程序的存储空间指令格式尽量规整，便于译码

一般的指令主要由两部分组成：操作码和地址码 操作码(OPC) 地址码(A) 地址码通常包括三部分内容：

地址：地址码、立即数、寄存器、变址寄存器 地址的附加信息：偏移量、块长度、跳距

寻址方式：直接寻址、间接寻址、立即数寻址、变址寻址、相对寻址、寄存器寻址 操作码主要包括两部分内容：

操作种类：加、减、乘、除、数据传送、移位、转移、输入输出、程序控制、处理机控制等 操作数描述：数据的类型：定点数、浮点数、复数、字符、字符串、逻辑数、向量 进位制：2进制、10进制、16进制 ; 数据字长：字、半字、双字、字节 操作码的优化表示:

操作码的三种编码方法：固定长度、Huffman编码、扩展编码 优化操作码编码的目的：节省程序存储空间

1. 固定长操作码 定长定域：IBM公司的大中型机：最左边8位为操作码;Intel公司的Intanium处理机：14

位定长操作码;许多RISC处理机采用定长操作码

主要优点：规整 , 译码简单

主要缺点：浪费信息量（操作码的总长位数增加）

2. Huffman编码法 1952年由Huffman首先提出 , 操作码的最短平均长度可通过如下公式计算：H=

nn pi表示第i种操作码在程序中出现的概率

pilog2piHpilog2pi固定长编码相对于Huffman编码的信息冗余量R： i1i1R1必须知道每种操作码在程序中出现的概率

log2n

例2.16：假设一台模型计算机共有7种不同的操作码，如果采用固定长操作码需要3位。已知各种操作码在程序中出现的概率如下表，计算采用Huffman编码法的操作码平均长度，并计算固定长操作码和Huffman操作码的信息冗 余量。

指令序号 I1 I2 I3 I4 I5 I6 I7 解答：利用Huffman树进行操作码编码

（又称最小概率合并法） 出现的概率 0.45 0.30 0.15 0.05 0.03 0.01 0.01 • 把所有指令按照操作码在程序中出现的概率大小，自左向右顺序排列。 • 选取两个概率最小的结点合并成一个概率值是二者之和的新结点，并把这个新结点与其它还没有合并的结点

一起形成一个新的结点集合。

• 在新结点集合中选取两个概率最小的结点进行合并，如此继续进行下去，直至全部结点合并完毕。 • 最后得到的根结点的概率值为1。

• 每个新结点都有两个分支，分别用带有箭头的线表示，并分别用一位代码“0”和“1”标注。 • 从根结点开始，沿尖头所指方向寻找到达属于该指令概率结点的最短路径，把沿线所经过的代码排列起来就

得到了这条指令的操作码编码。

利用Huffman树进行操作码编码： Huffman操作码编码 0.45 0.30 0.15 0.05 0.03 0.01 0.01 指令序号 出现的概率 Huffman编码法 操作码长度 0 1 0.05 0.45 0 1位 I1 0 1 0.30 1 0 2位 I2 0.10 0.15 1 1 0 3位 0 1 I3 0.25 0.05 1 1 1 0 4位 0 1 I4 0.55 0.03 1 1 1 1 0 5位 I5 0 1 0.01 1 1 1 1 1 0 6位 I6 1.00 0.01 1 1 1 1 1 1 6位 I7 7采用Huffman编码法的操作码平均长度为： Hpili＝0.45×1＋0.30×2＋0.15×3＋0.05×4＋0.03×5＋

i10.01×6＋0.01×6＝1.97（位） 7操作码的最短平均长度为： Hpilog2pi＝0.45×1.152＋0.30×1.737＋0.15×2.737＋0.05×4.322＋

i10.03×5.059＋0.01×6.644＋0.01×6.644＝1.95（位） 1.95H1.97采用3位固定长操作码的信息冗余量为（左）： R11.0%R1135%Huffman编码法的信息冗余量仅为（右）： 1.9737log2与3位固定长操作码的信息冗余量35％相比要小得多 3. 扩展编码法

Huffman操作码的主要缺点：操作码长度很不规整，硬件译码困难；与地址码共同组成固定长的指令比较困难 扩展编码法：由固定长操作码与Huffman编码法相结合形成

例2.18：将例2.16改为1-2-3-5扩展编码法，操作码最短平均长度为：

H＝0.45×1＋0.30×2＋0.15×3＋(0.05＋0.03＋0.01＋0.01)×5＝2.00

信息冗余量为： 1.95R12.5% 2.00例2.19：将例2.17改为2-4等长扩展编码法，操作码最短平均长度为： H＝(0.45＋0.30＋0.15)×2＋(0.05＋0.03＋0.01＋0.01)×4＝2.20

1.952-4等长扩展编码法信息冗余量为

R111.4% 2.20

RISC：(Reduced Instruction Set Computer）精简指令系统，70年代后期至现在

只保留功能简单的指令,功能较复杂的指令用软件实现，提高流水线效率 <在CISC中，大约20％的指令占据了80％的处理机执行时间。> VLSI工艺要求规整性，RISC正好适应了VLSI工艺的要求 卡内基梅隆(Carnegie Mellon)大学论述RISC的特点如下：

(1)大多数指令在单周期内完成 (2)LOAD/STORE结构 (3)硬布线控制逻辑 (4)减少指令和寻址方式的种类 (5)固定的指令格式 (6)注重编译的优化

90年代初, IEEE的Michael Slater对RISC描述： (1)RISC为提高流水线效率, 应具有下述特征：

简单而统一格式的指令译码 大部分指令可以单周期执行完成 只有LOAD和STORE指令可以访问存储器 简单的寻址方式 采用延迟转移技术 采用LOAD延迟技术 (2)为使编译器便于生成优化代码，应具有：

三地址指令格式， 较多的寄存器，对称的指令格式 RISC思想的精华

减少CPI是RISC思想的精华 程序执行时间的计算公式：Ｐ＝Ｉ· CPI · Ｔ

其中: Ｐ是执行这个程序所使用的总的时间；Ｉ是这个程序所需执行的总的指令条数；

CPI(Cycles Per Instruction)是每条指令执行的平均周期数 Ｔ是一个周期的时间长度。

0 1 0.02 硬件方面： 采用硬布线控制逻辑 减少指令和寻址方式的种类 使用固定的指令格式

采用LOAD/STORE结构 指令执行过程中设置多级流水线等

软件方面：十分强调优化编译技术的作用。 RISC的关键技术 1. 延时转移技术

为了使指令流水线不断流，在转移指令之后插入一条没有数据相关和控制相关的有效指令，而转移指令被延迟执行，这种技术称为延迟转移技术。采用指令延迟转移技术时，指令序列的调整由编译器自动进行，用户不必干预。读采用延迟转移的程序，必须十分小心。

采用延迟转移技术的两个限制条件:

• 被移动指令在移动过程中与所经过的指令之间没有数据相关 • 被移动指令不破坏条件码，至少不影响后面的指令使用条件码

如果找不到符合上述条件的指令，必须在条件转移指令后面插入空操作；如果指令的执行过程分为多个流水段，则要插入多条指令；插入1条指令成功的概率比较大，插入2条或2条以上指令成功的概率明显下降 2. 指令取消技术

采用指令延时技术，经常找不到可以用来调整的指令，可考虑采用另一种方法：指令取消技术 分为两种情况：

(1)向后转移（适用于循环程序）

实现方法：循环体的第一条指令安放在两个位置，分别在循环体的前面和后面。

如果转移成功，则执行循环体后面的指令，然后返回到循环体开始；否则取消循环体后面的指令

效果：能够使指令流水线在绝大多数情况下不断流。对于循环程序，由于绝大多数情况下，转移是成功的。 只有最后一次出循环时，转移不成功。 (2)向前转移(IF THEN )

实现方法：如果转移不成功，执行转移指令之后的下条指令，否则取消下条指令。

效果：转移成功与不成功的概率, 通常各50％。主要优点：不必进行指令流调整

3. 重叠寄存器窗口技术（Overlapping Register Window）美国加洲大学伯克利分校的F Baskett提出 原因：在RISC中，子程序比CISC中多，因为传送参数而访问存储器的信息量很大

实现方法：设置一个数量比较大的寄存器堆，并把它划分成很多个窗口。在每个过程使用的几个窗口中：

有一个窗口是与前一个过程共用，有个窗口是与下一个过程共用

效果：可以减少大量的访存操作。另外，要在主存中开辟一个堆栈，当调用层数超过规定层数（寄存器溢出）

时，把益出部分的寄存器中内容压入堆栈。 4. 指令流调整技术

目标：通过变量重新命名消除数据相关，提高流水线效率 5. 以硬件为主 固件为辅

固件的主要缺点是：执行速度低。目前，ROM的速度低于SRAM， 一条机器指令通常要多条微指令解释执行 固件的主要优点是：便于实现复杂指令，便于修改指令系统

以硬联逻辑为主来实现指令系统， 对于少数复杂的指令，目前的许多处理机也用微程序技术实现。 RISC优化编译技术

RISC对编译器带来的方便主要有：

(1)指令系统比较简单、对称、均匀，指令选择工作简单。 (2)选择寻址方式的工作简单，

(3)因为采用LOAD/STORE方式，省去了是否生成访问存储器指令的选择工作。

(4)由于大多数指令在一个周期内执行完成，为编译器调整指令序列提供了极大的方便。 RISC对编译器造成的困难主要有：

(1)必须精心安排每一个寄存器的用法，以便充分发挥每一个通用寄存器的效率，尽量减少访问主存储器的次数。 (2)做数据和控制相关性分析，要调整指令的执行序列，并与硬件相配合实现指令延迟技术和指令取消技术等。 (3)要设计复杂的子程序库，RISC的子程序库通常要比CISC的子程序库大得多。

第五章 标量处理机

1.线性流水线的性能分析和计算 2.数据相关的解决方法 解决冲突的方法 3.对于非线性根据预约表进行无冲突调度 4.非线性流水线的无冲突的优化调度实现

5.非线性延迟 6.线性指令窗口怎么回事？ 7.知道超标量处理机和超流水线处理机及其加速比如何计算？ 8.静态流水线、以及动态流水线的吞吐率（性能） 先行控制技术

指令的重叠执行方式

n1.顺序执行方式 T(取指令i分析i执行i）执行n条指令所用的时间为： i1如果每段时间都为t，则执行n条指令所用的时间为：T＝3 n t 主要优点：控制简单，节省设备 主要缺点：速度慢， 取指令k 分析k 执行k 取指令k+1 分析k+1 执行k+1 功能部件的利用率低 2.一次重叠执行方式

如果两个过程的时间相等，则执行n条指令的时间为：T＝(1+2n)t 取指令k 分析k 执行k

取指令k+1 分析k+1 执行k+1 主要优点：

取指令分析k+2 执行k+2 指令的执行时间缩短，功能部件的利用率明显提高。 k+2 主要缺点：需要增加一些硬件，控制过程稍复杂。

3.二次重叠执行方式

如果三个过程的时间相等，执行n条指令的时间为：T＝(2＋n）t ， 在理想情况下，处理机中同时有三条指

令在执行。处理机的结构要作比较大的改变，需要采用先行控制技术。

取指令k 分析k 执行k

取指令k+1 分析k+1 执行k+1

取指令k+2 分析k+2 执行k+2

二次重叠执行方式 先行控制方式的原理

1.采用二次重叠执行方式必须解决两个问题：

(1)有独立的取指令部件、指令分析部件和指令执行部件

把一个集中的指令控制器，分解成三个独立的控制器：存储控制器、指令控制器、运算控制器

(2)要解决访问主存储器的冲突问题 取指令、分析指令、执行指令都可能要访问存储器 2.解决访存冲突的方法：

(1)采用低位交叉存取方式：

这种方法不能根本解决冲突问题。 指令、读操作数、写结果。

(2)两个独立的存储器：独立的指令存储器和数据存储器。

如果再规定，执行指令所需要的操作数和执行结果只写到通用寄存器，则取指令、分析指令和执行指令就可以同时进行。在许多高性能处理机中，有独立的指令Cache和数据Cache。这种结构被称为哈佛结构。 (3)采用先行控制技术 采用先行控制技术的关键是缓冲技术和预处理技术。

缓冲技术通常用在工作速度不固定的两个功能部件之间。设置缓冲栈的目的是用来以平滑功能部件之间的工作速度。

在采用了缓冲技术和预处理技术之后，运算器能够专心于数据的运算，从而大幅度提高程序的执行速度。

流水线技术 空间并行性：设置多个独立的操作部件 时间并行性：分时使用同一个部件的不同部分 流水线工作原理

1. 流水寄存器 流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流

水级、流水节拍等。在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门寄存器等。加入流水寄存器，会增加指令的执行时间。在一般流水线时空图中不画出流水寄存器。 2.一种指令流水线 一般4至12个流水段，≥8个流水段的称为超流水线处理机

ttt 输入 流水线 流水线 输出 取指令i 分析i 执行i 寄存器 寄存器 △t 3.流水线时空图 空间 执行部件 执行k 执行k+1 执行k+2 执行k+3

分析部件 分析k 分析k+1 分析k+2 分析k+3

取指令部件 取指令k 取指令k+1 取指令k+2 取指令k+3

0 t1 t2 t3 t4 t5 时间 4.流水线的主要特点 只有连续提供同类任务才能发挥流水线效率：尽量减少因条件分支造成的“断流”， 通过编译技术提供连续的相同类型操作。

每个流水线段都要设置一个流水寄存器。时间开销：流水线的执行时间加长 是流水线中需要增加的主要硬件

各流水段的时间应尽量相等：流水线处理机的基本时钟周期等于时间最长的流水段的时间长度。 流水线需要有“装入时间”和“排空时间” 流水线的分类

1.线性流水线与非线性流水线 ——流水线的各个流水段之间是否有反馈信号 线性流水线（Linear Pipelining）：每一个流水段都流过一次，而且仅流过一次 非线性流水线（Nonlinear Pipelining）： 某些流水段之间有反馈回路或前馈回路。

线性流水线能够用流水线连接图唯一表示，非线性流水线必须用流水线连接图和流水线预约表共同表示 2.按照流水线的级别来分

处理机级流水线，又称为指令流水线。例如：在采用先行控制器的处理机中，各功能部件之间的流水线

部件级流水线(操作流水线) 如浮点加法器流水线 宏流水线(Macro Pipelining) 处理机之间的流水线称，每个处理机对同一个数据流的不同部分分别进行处理。 3.单功能流水线与多功能流水线

单功能流水线：只能完成一种固定功能的流水线。多功能流水线：流水线的各段通过不同连接实现不同功能 4.静态流水线与动态流水线

静态流水线：同一段时间内，各个功能段只能按照一种方式连接，实现一种固定的功能。 动态流水线：在同一段时间内，各段可以按照不同的方式连接，同时执行多种功能。 5.流水线的其他分类方法

按照数据表示方式：标量流水线和向量流水线 按照控制方式：同步流水线和异步流水线 顺序流水线与乱序流水线，乱序流水线又称为无序流水线、错序流水线或异步流水线等。 线性流水线的性能分析

主要指标：吞吐率、加速比和效率

n1.吞吐率（Though Put）

TP流水线吞吐率的最基本公式： Tk其中：n为任务数，Ｔk为完成n个任务所用的时间。 各段执行时间相等，输入连续任务情况下，完成n个任务需要的总时间为： Tk＝(k＋n－1)t 其中：k 为流水线的段数，t为时钟周期。 Tk= k · Δt + (n-1) Δt = (k+n-1)t

nn1吞吐率为（左）：

TPTPmaxLim 最大吞吐率为（右）： 　　　　　n(kn1)t(kn1)tt各段时间不等，完成n个连续任务： n 吞吐率(左)： 1TPkTP 最大吞吐率（右）：

max(t1,t2,,tk)ti(n1)max(t1,t2,,tk) i1

流水线各段执行时间不相等的解决办法 S1 S2 输入 t1＝t t2＝3t (1)将“瓶颈”部分再细分（如果可分的话）

S3 t3＝t S4 t4＝t 输出 (2)“瓶颈“流水段重复设置：增加分配器和收集器

2.加速比（Speedup） 计算加速比的基本公式： 顺序执行时间T0S 各段执行时间相等，输入连续任务情况下, 流水线执行时间Tk 加速比：（左） kntknknSSmaxLimk 最大加速比：（右） 　　　　nkn1(kn1)tkn1k 各段时间不等，输入连续任务情况下, 实际加速比为： nti当流水线段数增加时，需要连续输入的任务数也必须增加 i1Sk3.效率（Efficiency） ti(n1)max(t1,t2,,tk）n个任务占用的时空区T0i1计算流水线效率的一般公式： Ek个流水段的总的时空区kTk

kntnn各流水段时间相等，输入n个连续任务，流水线的效率为：E EmaxLim1　　　　nkn1k(kn1)tkn1最高效率为：（右） k各流水段时间不等，输入n个连续任务，流水线效率为： nti各段设备量或价格不等时，流水线的效率为：（下）

i1Ek n个任务占用的加权时空区Ek[ti（n1)max(t1,t2,,tk)] k个流水段的总的加权时空区i1k

naiti 即： i1Eikk

ai[aiti（n1)max(t1,t2,,tn)] 其中，ai＜k，且＝k。 I1i1流水线的吞吐率、加速比与效率的关系： nnknTPES因为： 因此：E＝TP·t，S＝k·E (kn1)tkn1kn1

流水线性能分析举例

对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。 对于输入不连续任务，或多功能流水线，通常采用基本公式计算。

例5.2： 用一条4段浮点加法器流水线求8个浮点数的和：Z＝A＋B＋C＋D＋E＋F＋G＋H 解：Z＝[(A＋B)＋(C＋D)]＋[(E＋F)＋(G＋H)] 空间 周期 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

规格化 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 A+B+C+D

加数 B D F H C+D G+H E+F+G+H

结果 A+B C+D E+F g+H A+B+C+D Z E+F+G+H 用一条4段浮点加法器流水线求8个数之和的流水线时空图

解：7个浮点加法共用了15个时钟周期。

n71T047tTP047S187Tk15tt Tk15t流水线的吞吐率TP为：

流水线的加速比S为：

E流水线的效率E为：

T047t047kTk415t

非线性流水线的调度 非线性流水线调度的任务是要找出一个最小的循环周期，按照这周期向流水线输入新任务，

流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。

1.非线性流水线的表示 线性流水线能够用流水线连接图唯一表示

对于非线形流水线，连接图不能唯一表示工作流程，因此，引入流水线预约表 例如：非线形流水线的连接图和预约表

输出 前馈线 反馈线

输入 S1 S2 S3 S4

时间 1 2 3 4 5 6 7 功能段 × × × S1 × × S2

× × S3

× S4

一张预约表可能与多个流水线连接图相对应 一个流水线连接图对应于多张预约表 2.非线性流水线的冲突

启动距离：连续输入两个任务之间的时间间隔 流水线冲突：几个任务争用同一个流水段

3.无冲突调度方法 由E.S.Davidson及其学生于1971年提出

禁止向量：预约表中每一行任意两个“×”之间距离的集合。上例中为（3，4，6） 冲突向量：C＝（CmCm-1…C2C1） 其中：m是禁止向量中的最大值。

如果i在禁止向量中，则Ci＝1，否则Ci＝0。上例中C＝(101100) （课件中例5.3） 4.优化调度方法 L.E.Shar于1972年提出流水线最小平均启动距离的限制范围： (1)最小平均启动距离的下限是预约表中任意一行里“×”的最多个数。 (2)最小平均启动距离小于等于状态图中任意一个简单循环的平均启动距离。 (3)最小平均启动距离的上限是冲突向量中1的个数再加上1。

1992年，L.E.Shar又证明了上述限制范围。最有用的是第1条。预约表中“×”最多的行一定是瓶颈流水段 （见课件中示例） 相关性分析技术

资源相关：资源相关是指多条指令进入流水线后在同一机器时钟周期内争用同一个功能部件所发生的冲突。假定一条指令流水线由五段组成。（课件中示例）

数据相关：在一个程序中，如果必须等前一条指令执行完毕后，才能执行后一条指令，那么这两条指令就是数据相关的。

控制相关：控制相关冲突是由转移指令引起的。当执行转移指令时，依据转移条件的产生结果，可能为顺序取下条指令；也可能转移到新的目标地址取指令，从而使流水线发生断流。

数据相关

在一个程序中，如果必须等前一条指令执行完毕后，才能执行后一条指令，那么这两条指令就是数据相关的。 解决数据相关冲突的办法：

在流水CPU的运算器中设置若干运算结果缓冲寄存器，暂时保留运算结果，以便于后继指令直接使用，这称为“向前”或定向传送技术。

1.解决指令相关的根本办法是：在程序执行过程中不允许修改指令。

现代程序设计方法要求程序具有再入性，可以被递归调用等，也要求不修改指令。 2.主存操作数相关 发生主存操作数相关的指令序列： n：OP A1，A2，A3 ；A1＝(A2) OP (A3)

n+1：OP A1，A2，A3 ；A1＝(A2) OP (A3)

出现下列情况之一，就发生主存操作数相关： A1（n）＝ A2（n＋1） A1（n）＝ A3（n＋1） 解决办法：运算结果写到通用寄存器，而不写到主存

对于访问主存储器的请求，写结果的优先级高于读操作数。

3. 通用寄存器数据相关

发生寄存器数据相关的可能性很大，影响面也很大。解决通用寄存器数据相关的方法：

方法一：把读操作数、写运算结果与指令执行合在一个节拍。从数据从通用寄存器读出，在运算器中完成运算，结果写回通用寄存器的整个回路中，只有通用寄存器是时序逻辑。 当发生下述情况时，不能采用这种方法：

当寄存器个数多时，读写寄存器的时间长；当功能部件数量多时，寄存器的读写端口多； 当功能部件的执行时间比较长，或要求指令的执行时间短时 。

方法二：建立相关专用通路(ByPass)由于发生寄存器数据相关的情况很普遍，一般计算机系统都采用专用数据通路。把读通用寄存器、执行操作和写结果分为3个周期，或2个周期。采用专用数据通路能够缩短1至2个周期。

变址相关：在采用变址寻址方式的处理机中，由于变址量放在寄存器中，因此，可能发生与通用寄存器数据相关类似变址相关

4. 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数据相关。 解决方法：

方法一：由编译器在LOAD之后插入不发生数据相关的指令，由于LOAD的执行时间不确定，不能根本解决问题 方法二：由硬件自动插入空操作，直到LOAD操作完成

在单条流水线处理机中，也可以停止节拍发生器，直到数据从存储器中读出为止。