描述
开 本: 16开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787302496052丛书名: 21世纪大学本科计算机专业系列教材
本书概念清晰，重点难点突出，覆盖面广，题型多样，是一本很有用的学习辅导书。本书可作为计算机系统结构课程（上课或自学）的学习辅导书，也可作为计算机专业硕士研究生入学考试的复习指导书。
目录
第1章计算机系统结构的基础知识
1.1基本要求与难点
1.1.1基本要求
1.1.2难点
1.2知识要点
1.2.1计算机系统结构的基本概念
1.2.2计算机系统的设计
1.2.3计算机系统的性能评测
1.2.4计算机系统结构的发展
1.2.5计算机系统结构中并行性的发展
习题
题解
第2章指令系统的设计
2.1基本要求与难点
2.1.1基本要求
2.1.2难点
2.2知识要点
2.2.1指令系统结构的分类
2.2.2寻址方式
2.2.3指令系统的设计和优化
2.2.4指令系统的发展和改进
2.2.5操作数的类型和大小
2.2.6MIPS指令系统结构
习题
题解
第3章流水线技术
3.1基本要求与难点
3.1.1基本要求
3.1.2难点
3.2知识要点
3.2.1流水线的基本概念
3.2.2流水线的性能指标
3.2.3非线性流水线的调度
3.2.4流水线的相关与冲突
3.2.5流水线的实现
习题
题解
第4章向量处理机
4.1基本要求与难点
4.1.1基本要求
4.1.2难点
4.2知识要点
4.2.1向量的处理方式
4.2.2向量处理机的结构
4.2.3提高向量处理机性能的常用技术
4.2.4向量处理机的性能评价
习题
题解
第5章指令级并行性及其开发——硬件方法
5.1基本要求与难点
5.1.1基本要求
5.1.2难点
5.2知识要点
5.2.1指令级并行的概念
5.2.2相关与指令级并行
5.2.3指令的动态调度
5.2.4动态分支预测技术
5.2.5多指令流出技术
习题
题解
第6章指令级并行的开发——软件方法
6.1基本要求与难点
6.1.1基本要求
6.1.2难点
6.2知识要点
6.2.1基本指令调度和循环展开
6.2.2跨越基本块的静态指令调度
6.2.3静态多指令流出： VLIW技术
6.2.4显式并行指令计算
6.2.5开发更多的指令级并行
习题
题解
第7章存储系统
7.1基本要求与难点
7.1.1基本要求
7.1.2难点
7.2知识要点
7.2.1存储系统的层次结构
7.2.2Cache基本知识
7.2.3降低Cache不命中率
7.2.4减少Cache不命中开销
7.2.5减少命中时间
7.2.6并行主存系统
7.2.7虚拟存储器
习题
题解
第8章输入输出系统
8.1基本要求与难点
8.1.1基本要求
8.1.2难点
8.2知识要点
8.2.1I/O系统的性能
8.2.2I/O系统的可靠性、可用性和可信性
8.2.3廉价磁盘冗余阵列RAID
8.2.4总线
8.2.5通道处理机
8.2.6I/O与操作系统
习题
题解
第9章互连网络
9.1基本要求与难点
9.1.1基本要求
9.1.2难点
9.2知识要点
9.2.1互连函数
9.2.2互连网络的结构参数与性能指标
9.2.3静态互连网络
9.2.4动态互连网络
9.2.5消息传递机制
习题
题解
第10章多处理机
10.1基本要求与难点
10.1.1基本要求
10.1.2难点
10.2知识要点
10.2.1引言
10.2.2对称式共享存储器系统结构
10.2.3分布式共享存储器系统结构
10.2.4同步
10.2.5同时多线程
10.2.6大规模并行处理机MPP
10.2.7多处理机实例1： T1
10.2.8多处理机实例2： Origin 2000
习题
题解
第11章多核架构与编程
11.1基本要求与难点
11.1.1基本要求
11.1.2难点
11.2知识要点
11.2.1多核架构的需求
11.2.2多核架构
11.2.3基于多核的并行程序设计
11.2.4多核编程实例
习题
题解
第12章机群系统
12.1基本要求与难点
12.1.1基本要求
12.1.2难点
12.2知识要点
12.2.1机群的基本结构
12.2.2机群的特点
12.2.3机群的分类
习题
题解
第13章阵列处理机
13.1基本要求与难点
13.1.1基本要求
13.1.2难点
13.2知识要点
13.2.1阵列处理机的操作模型和特点
13.2.2阵列处理机的基本结构
13.2.3阵列处理机实例
13.2.4阵列处理机的并行算法举例
习题
题解
第14章数据流计算机
14.1基本要求与难点
14.1.1基本要求
14.1.2难点
14.2知识要点
14.2.1数据流计算机的基本原理
14.2.2数据流程序图和数据流语言
14.2.3数据流计算机结构
14.2.4数据流计算机的评价
习题
题解
参考文献
作者2017年7月
(1) 掌握有关流水线的基本概念。(2) 掌握流水线的工作原理，了解如何从不同的角度对流水线进行分类。(3) 理解流水线的各项性能指标，能熟练地用时空图或公式计算吞吐率、加速比和效率。能熟练地画出时空图。(4) 掌握消除流水线瓶颈的方法。(5) 熟练掌握单功能非线性流水线的调度方法。能熟练地画出状态转换图，并根据状态转换图写出调度方案。了解双功能非线性流水线的调度方法。(6) 掌握经典5段流水线的结构。(7) 理解3种相关和3种冲突的概念，掌握解决结构冲突、数据冲突和控制冲突的方法，特别是： 如何利用定向技术来解决数据冲突？如何用猜测法和延迟分支来解决控制冲突？(8) 掌握基本的MIPS流水线的组成以及在各流水段完成的操作。掌握对该流水线进行改进后(把分支延迟减少为一个时钟周期)IF段和ID段的操作的变化。3.1.2难点(1) 流水线时空图的画法，如何计算流水线的吞吐率、加速比和效率？(2) 单功能非线性流水线的调度方法。(3) 如何解决结构冲突、数据冲突和控制冲突？(4) 基本的MIPS流水线的各段完成的操作。3.2知识要点3.2.1流水线的基本概念1. 什么是流水线
在计算机中，把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他的子过程并行进行。这就是流水线技术。流水线中的每个子过程及其功能部件称为流水线的级或段，流水线的段数称为流水线的深度。一般采用时空图来描述流水线的工作过程。时空图的横坐标表示时间，纵坐标表示空间，即流水线的段。流水线技术具有以下特点。(1) 流水线实际上是把一个大的处理功能部件分解为多个独立的功能部件，并依靠它们的并行工作来提高吞吐率。(2) 流水线中各段的时间应尽可能相等，否则将引起流水线堵塞和断流。因为时间长的段将成为流水线的瓶颈。(3) 流水线每个段的后面都要有一个缓冲寄存器(锁存器)，称为流水寄存器。(4) 流水技术适合于大量重复的时序过程。(5) 流水线需要有通过时间和排空时间。它们分别是指个任务和后一个任务从进入流水线到流出结果的那个时间段。在这两个时间段中，流水线都不是满负荷工作。2. 流水线的分类流水线可以从不同的角度和观点来分类。下面是几种常见的分类。1) 部件级、处理机级及系统级流水线这是按照流水技术用于计算机系统的等级不同来分的。部件级流水线是把处理机中的部件进行分段，再把这些部件分段相互连接而成。它使得运算操作能够按流水方式进行。这种流水线也称为运算操作流水线。处理机级流水线又称指令流水线。它是把指令的执行过程按照流水方式进行处理，即把一条指令的执行过程分解为若干个子过程，每个子过程在独立的功能部件中执行。系统级流水线是把多个处理机串行连接起来，对同一数据流进行处理，每个处理机完成整个任务中的一部分。前一个处理机的输出结果存入存储器中，作为后一个处理机的输入。这种流水线又称为宏流水线。2) 单功能流水线与多功能流水线单功能流水线是指流水线的各段之间的连接固定不变、只能完成一种固定功能的流水线。多功能流水线是指各段可以进行不同的连接，以实现不同功能的流水线。3) 静态流水线与动态流水线静态流水线是指在同一时间内，多功能流水线中的各段只能按同一种功能的连接方式工作的流水线。当流水线要切换到另一种功能时，必须等前面的任务都流出流水线之后，才能改变连接。动态流水线是指在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能的流水线。一般来说，动态流水线的效率比静态流水线的高。但是，动态流水线的控制要复杂得多。4) 线性流水线与非线性流水线线性流水线是指各段串行连接、没有反馈回路的流水线。数据通过流水线中的各段时，每一个段多只流过一次。非线性流水线是指各段除了有串行的连接外，还有反馈回路的流水线。在非线性流水线中，一个重要的问题是确定什么时候向流水线引进新的任务，才能使该任务不会与流水线中的任务发生争用流水段的冲突。这就是非线性流水线的调度问题。5) 顺序流水线与乱序流水线这是根据流水线中任务流入和流出的顺序是否相同来分的。在顺序流水线中，流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。而在乱序流水线中，流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同，允许后进入流水线的任务先完成。这种流水线又称为无序流水线或错序流水线。通常把指令执行部件中采用了流水线的处理机称为流水线处理机。如果处理机具有向量数据表示和向量指令，则称之为向量流水处理机，简称向量机； 否则就称之为标量流水处理机。3.2.2流水线的性能指标衡量流水线性能的主要指标有吞吐率、加速比和效率。1. 流水线的吞吐率流水线的吞吐率TP(Through Put)是指在单位时间内流水线所完成的任务数量或输出结果的数量。
TP=nTk(3.1)
其中，n为任务数，Tk是处理完成n个任务所用的时间。1) 各段时间均相等的流水线
TP=n（k n-1）Δt(3.2)
其中，Δt为各段的时间，k为段数。2) 各段时间不完全相等的流水线各段时间不等的流水线的实际吞吐率为：
TP=n∑ki=1Δti （n-1）max（Δt1，Δt2,…,Δtk）(3.3)
其中，Δti为第i段的时间，共有k个段。分母中的部分是流水线完成个任务所用的时间，第二部分是完成其余n-1个任务所用的时间。流水线的吞吐率为：
TPmax=1max（Δt1，Δt2，…,Δtk）(3.4)
从式(3.3)和式(3.4)可以看出，当流水线各段的时间不完全相等时，流水线的吞吐率和实际吞吐率由时间长的那个段决定，这个段就成了整条流水线的瓶颈。可以用以下两种方法来消除瓶颈段。(1) 细分瓶颈段。这是把流水线中的瓶颈段切分为几个独立的功能段，从而使流水线各段的处理时间都相等。(2) 重复设置瓶颈段。如果无法把瓶颈段再细分，则可以采用重复设置瓶颈段的方法来解决问题。重复设置的段并行工作，在时间上依次错开处理任务。2. 流水线的加速比流水线的加速比是指使用顺序处理方式处理一批任务所用的时间(设为Ts)与按流水处理方式处理同一批任务所用的时间(设为Tk)之比：
S=TsTk(3.5)
假设流水线各段时间相等，都是Δt，则该流水线的实际加速比为：
S=nkk n-1(3.6)
当流水线的各段时间不完全相等时，一条k段流水线完成n个连续任务的实际加速比为：
S=n∑ki=1Δti∑ki=1Δti （n-1）max（Δt1,Δt2,…,Δtk）(3.7)
3. 流水线的效率流水线的效率即流水线设备的利用率，它是指流水线中的设备实际使用时间与整个运行时间的比值。如果各段时间相等，则各段的效率是相同的，且都等于整条流水线的效率。
E=nk n-1
在各段时间不等的情况下，k段流水线连续处理n个任务的流水线效率为：
E=n·∑ki=1Δtik∑ki=1Δti （n-1）·max（Δt1，Δt2，…，Δtk）(3.8)
计算流水线效率的一般公式可以表示为：
E=n个任务实际占用的时空区的面积k个段总的时空区的面积(3.9)
画出流水线的时空图，然后根据式（3.9）来计算效率，是一种比较直观通用的方法。对于线性流水线、非线性流水线、多功能流水线、任务不连续的情况等都适用。4. 流水线设计中的若干问题1) 瓶颈问题当流水线各段时间不相等时，时间的那个段就成了瓶颈。机器的时钟周期取决于这个瓶颈段的延迟时间。因此，在设计流水线时，要尽可能使各段时间相等。2) 流水线的额外开销流水线的额外开销由两部分构成： 流水寄存器延迟和时钟偏移开销。增加流水线的段数可以提高流水线的性能，但是流水线段数的增加是受到这些额外开销限制的。3) 冲突问题如果流水线中的指令或数据之间存在关联，则它们可能要相互等待，引起访问冲突，造成流水线的停顿。如何处理好冲突问题，是流水线设计中要解决的重要问题之一。3.2.3非线性流水线的调度1. 单功能非线性流水线的调度
向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离。而会引起非线性流水线功能段使用冲突的启动距离则称为禁用启动距离。启动距离和禁用启动距离一般都用时钟周期数来表示，是一个正整数。对流水线的任务进行优化调度和控制的步骤如下。(1) 根据预约表写出禁止表F。(2) 根据禁止表F写出初始冲突向量C0=(cNcN1…ci…c2c1)。(3) 根据初始冲突向量C0画出状态转换图。令Ck=C0，按下式计算新的冲突向量：
SHR(j)(Ck)∨C0(3.10)
其中，SHR(j)表示逻辑右移j位。对于所有允许的时间间隔都按上述步骤求出其新的冲突向量，并且把新的冲突向量作为当前冲突向量，反复使用上述步骤，直到不再产生不同的冲突向量为止。由此可以画出用冲突向量表示的流水线状态转移图。(4) 根据状态转换图写出调度方案。由初始状态出发，任何一个闭合回路即为一种调度方案。为了找到的调度方案，只要列出所有可能的调度方案，计算出每种方案的平均时间间隔，从中找出其小者即可。2. 多功能非线性流水线的调度双功能(设为功能A和B)非线性流水线的调度方法类似于单功能非线性流水线的调度方法。只是其状态转移图中结点状态的表示不同，是由两个冲突向量构成的冲突矩阵。其初始结点有两个，分别对应于个任务是A类和B类的情况。3.2.4流水线的相关与冲突1. 一个经典的5段流水线
先考虑在非流水情况下是如何实现的。我们把一条指令的执行过程分为以下5个时钟周期。1) 取指令周期(IF)以程序计数器PC中的内容作为地址，从存储器中取出指令并放入指令寄存器IR； 同时PC值加4(假设每条指令占4个字节)，指向顺序的下一条指令。2) 指令译码/读寄存器周期(ID)对指令进行译码，并用IR中的寄存器地址去访问通用寄存器组，读出所需的操作数。3) 执行/有效地址计算周期(EX)（1） load和store指令： ALU把指定寄存器的内容与偏移量相加，形成访存有效地址。（2） ALU指令： ALU对从通用寄存器组中读出的数据进行运算。（3） 分支指令： ALU把偏移量与PC值相加，形成转移目标的地址。同时，判断分支是否成功。4) 存储器访问／分支完成周期(MEM)（1） load和store指令： 根据有效地址从存储器中读出相应的数据(load指令)； 或者是把指定的数据写入有效地址所指出的存储器单元(store指令)。（2） 分支指令： 如果分支“成功”，就把在前一个周期中计算好的转移目标地址送入PC。分支指令执行完成。否则，就不进行任何操作。5) 写回周期(WB)把结果写入通用寄存器组。对于ALU运算指令来说，这个结果来自ALU，而对于load指令来说，这个结果是来自存储器。把上述实现方案改造为流水线实现是比较简单的，只要把上面的每一个周期作为一个流水段，并在各段之间加上锁存器，就构成了一个经典的5段流水线，如图3.1所示。这些锁存器称为流水线寄存器。如果在每个时钟周期启动一条指令，则采用流水方式后的性能将是非流水方式的5倍。当然，事情也没这么简单，还要解决好流水处理带来的一些问题。
图3.1一个经典的5段流水线
，要保证不会在同一时钟周期要求同一个功能段做两件不同的工作。第二，为了避免IF段的访存(取指令)与MEM段的访存(读/写数据)发生冲突，必须采用分离的指令存储器和数据存储器，或者是仍采用一个公用的存储器，但要采用分离的指令Cache和数据Cache。一般是采用后者。 第三，ID段要对通用寄存器组进行读操作，而WB段要对通用寄存器组进行写操作，为了解决对同一通用寄存器的访问冲突，我们把写操作安排在时钟周期的前半拍完成，把读操作安排在后半拍完成。第四，没有考虑PC的问题。在每个时钟周期中，都要在IF段把PC值加4，为此需要设置一个专门的加法器。另外，分支指令在MEM段也要修改PC的值。2. 相关与流水线冲突 相关相关是指两条指令之间存在某种依赖关系。如果两条指令相关，那么它们可能就不能在流水线中重叠执行或者只能部分重叠。相关有3种类型： 数据相关(也称真数据相关)，名相关，控制相关。1) 数据相关考虑两条指令i和j，i在j的前面(下同)，如果下述条件之一成立，则称指令j与指令i数据相关： （1） 指令j使用指令i产生的结果； （2） 指令j与指令k数据相关，而指令k又与指令i数据相关。其中第二个条件表明，数据相关具有传递性。两条指令之间如果存在个条件所指出的相关的链，则它们是数据相关的。数据相关反映了数据的流动关系，即如何从其产生者流动到其消费者。2) 名相关这里的名是指指令所访问的寄存器或存储器单元的名称。如果两条指令使用了相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。指令j与指令i之间的名相关有以下两种。（1） 反相关。如果指令j所写的名与指令i所读的名相同，则称指令i和j发生了反相关。反相关指令之间的执行顺序是必须严格遵守的，以保证i读的值是正确的。（2） 输出相关。如果指令j和指令i所写的名相同，则称指令i和j发生了输出相关。输出相关指令的执行顺序是不能颠倒的，以保证后的结果是指令j写进去的。与真数据相关不同，名相关的两条指令之间并没有数据的传送，只是使用了相同的名而已。可以通过改变指令中操作数的名来消除名相关，这就是换名技术。对于寄存器操作数进行换名称为寄存器换名。寄存器换名既可以用编译器静态实现，也可以用硬件动态完成。3) 控制相关控制相关是指由分支指令引起的相关。它需要根据分支指令的执行结果来确定后面该执行哪个分支上的指令。一般来说，为了保证程序应有的执行顺序，必须严格按照控制相关确定的顺序执行。 流水线冲突流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期开始执行。流水线冲突有3种类型： 结构冲突，数据冲突，控制冲突。在后面的讨论中，我们约定： 当一条指令被暂停时，在该暂停指令之后流出的所有指令都要被暂停，而在该暂停指令之前流出的指令则继续进行。显然，在整个暂停期间，流水线不会启动新的指令。1) 结构冲突在流水线处理机中，如果某种指令组合因为资源冲突而不能正常执行，则称该处理机有结构冲突。这种情况发生在功能部件不是完全流水或者资源份数不够时。2) 数据冲突（1） 数据冲突当相关的指令彼此靠得足够近时，它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序，使之不同于它们串行执行时的顺序。这就是发生了数据冲突。按照指令读访问和写访问的先后顺序，可以将数据冲突分为3种类型。习惯上，这些冲突是按照流水线必须保持的访问顺序来命名的。考虑两条指令i和j，且i在j之前进入流水线，可能发生的数据冲突有以下几种。① 写后读冲突(Read After Write，RAW)。指令j用到指令i的计算结果，而且在i将结果写入寄存器之前就去读该寄存器，因而得到的是旧值。这是常见的一种数据冲突，它对应于真数据相关。② 写后写冲突(Write After Write，WAW)。指令j和指令i的结果寄存器相同，而且j在i写入之前就先对该寄存器进行了写入操作，从而导致写入顺序错误。后在结果寄存器中留下的是i写入的值。这种冲突对应于输出相关。写后写冲突仅发生在这样的流水线中： 流水线中不只一个段可以进行写操作； 或者指令被重新排序了(第5章介绍)。前面介绍的5段流水线不会发生写后写冲突。③ 读后写冲突(Write After Read，WAR)。指令j的目的寄存器和指令i的源操作数寄存器相同，而且j在i读取该寄存器之前就先对它进行了写操作，导致i读到的值是错误的。这种冲突是由反相关引起的。读后写冲突在前述5段流水线中不会发生。读后写冲突仅发生在这样的情况下： 有些指令的写结果操作提前了，而且有些指令的读操作滞后了； 或者指令被重新排序了。（2） 使用定向技术减少数据冲突引起的停顿为了减少停顿时间，可以采用定向技术来解决写后读冲突。定向技术(也称为旁路)的关键思想是： 在发生写后读相关的情况下，在计算结果尚未出来之前，后面等待使用该结果的指令并不见得是马上就要用该结果。如果能够将该计算结果从其产生的地方(ALU的出口)直接送到其他指令需要它的地方(ALU的入口)，那么就可以避免停顿。（3） 需要停顿的数据冲突并不是所有的数据冲突都可以用定向技术来解决。对于这种情况，为保证代码能在流水线中正确执行，需要设置一个称为“流水线互锁机制”的功能部件。一般来说，流水线互锁机制的作用是检测和发现数据冲突，并使流水线停顿，直至冲突消失。停顿是从等待相关数据的指令开始，到相应的指令产生该数据为止。停顿导致在流水线中插入气泡，使得被停顿指令的CPI增加了相应的时钟周期数。（4） 依靠编译器解决数据冲突为了减少停顿，对于无法用定向技术解决的数据冲突，可以通过在编译时让编译器重新组织指令顺序来消除冲突，这种技术称为“指令调度”或“流水线调度”。实际上，对于各种冲突，都有可能用指令调度来解决。3) 控制冲突在流水线中，控制冲突可能会比数据冲突造成更多的性能损失，所以同样需要得到很好的处理。执行分支指令的结果有两种，一种是分支“成功”，PC值改变为分支转移的目标地址。另一种则是“失败”，这时PC的值保持正常递增，指向顺序的下一条指令。对分支指令“成功”的情况来说，是在条件判定和转移地址计算都完成后，才改变PC值。对于5段流水线来说，改变PC值是在MEM段进行的。处理分支指令简单的方法是“冻结”或者“排空”流水线。即一旦在流水线的译码段ID检测到分支指令，就暂停其后的所有指令的执行，直到分支指令到达MEM段、确定出是否成功并计算出新的PC值为止。然后，按照新的PC值取指令。在这种情况下，分支指令给流水线带来了三个时钟周期的延迟。显然，这种让流水线空等的方法不是一种好的选择。由分支指令引起的延迟称为分支延迟。为减少分支延迟，可采取以下措施。（1） 在流水线中尽早判断出(或者猜测)分支转移是否成功； （2） 尽早计算出分支目标地址。这两种措施要同时采用，缺一不可。因为只有判断出转移是否成功而且得到分支目标地址后才能进行转移。在下面的讨论中，假设这两步工作被提前到ID段完成，即分支指令是在ID段的末尾执行完，所带来的分支延迟为一个时钟周期。减少分支延迟的方法有许多种。下面只介绍3种通过软件(编译器)来处理的方法，这三种方法有一个共同的特点： 它们对分支的处理方法在程序的执行过程中始终是不变的。它们要么总是预测分支成功，要么总是预测分支失败。（1） 预测分支失败当ID段检测到分支指令时，可以让流水线通过预测选择两条分支路径中的一条，继续处理后续指令。预测有两种选择： 猜测分支成功，或者猜测分支失败。不管哪一种，都可以通过编译器来优化性能，即让代码中常执行的路径与所选的预测方向一致。预测分支失败的方法是沿失败的分支继续处理指令，就好像什么都没发生似的。当确定分支是失败时，说明预测正确，流水线正常流动； 当确定分支是成功时，流水线就把在分支指令之后取出的指令转化为空操作，并按分支目标地址重新取指令执行。采用这种方法处理分支指令的后续指令时，要保证分支结果出来之前不能改变处理机的状态，以便一旦猜错时，处理机能够回退到原先的状态。（2） 预测分支成功这种方法按分支成功的假设进行处理。当流水线ID段检测到分支指令后，一旦计算出了分支目标地址，就开始从该目标地址取指令执行。（3） 延迟分支这种方法的主要思想是从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成。不管分支是否成功，都要按顺序执行延迟槽中的指令。在采用延迟分支的实际机器中，绝大多数的延迟槽都是一个，即： 分支指令延迟槽
下面只讨论这种情况。可以看出，只要分支延迟槽中的指令是有用的，流水线中就没有出现停顿，这时延迟分支的方法能很好地减少分支延迟。放入延迟槽中的指令是由编译器来选择的。实际上延迟分支能否带来好处完全取决于编译器能否把有用的指令调度到延迟槽中。这也是一种指令调度技术。常用的调度方法有3种： 从前调度，从目标处调度，从失败处调度。上述方法受到两个方面的限制，一个是可以被放入延迟槽中的指令要满足一定的条件，另一个是编译器预测分支转移方向的能力。为了提高编译器在延迟槽中放入有用指令的能力，许多处理机采用了分支取消机制。在这种机制中，分支指令隐含预测的分支执行方向。当分支的实际执行方向和事先所预测的一样时，执行延迟槽中的指令，否则就将该指令转化成空操作。3.2.5流水线的实现1. MIPS的一种简单实现
考虑实现MIPS指令子集的一种简单数据通路。该数据通路的操作分成5个时钟周期： 取指令，指令译码/读寄存器，执行/有效地址计算，存储器访问/分支完成，写回。下面只讨论整数指令的实现，包括数据字的load和store，等于0转移，整数ALU指令等。在这个数据通路上，多花5个时钟周期就能实现一条MIPS指令。这5个时钟周期及相应的操作如下。1) 取指令周期(IF)
IR←Mem［PC］
NPC←PC 4
2) 指令译码/读寄存器周期(ID)
A←Regs［rs］
B←Regs［rt］
Imm←((IR16)16##IR16..31)
这里准备的放在A、B和Imm中的数据在后面周期中也许用不上，但也没关系，并不影响程序执行的正确性。而且统一这样处理，可以减少硬件的复杂度，是有益无害的。3) 执行/有效地址计算周期(EX)在这个周期，ALU对在前一个周期准备好的操作数进行运算。不同指令所进行的操作不同： （1） load指令和store指令： ALUo←A Imm（2） 寄存器寄存器ALU指令： ALUo←A funct Bfunct字段给出了运算操作码。（3） 寄存器立即值ALU指令： ALUo←A op Imm（4） 分支指令
ALUo←NPC (Imm<<2)；
cond←(A== 0)
这里只考虑一种分支，即BEQZ(Branch if EQual Zero)，它的判断操作是： 判断是否为0。判断的结果存入寄存器cond，供以后使用。这里将有效地址计算周期和执行周期合并为一个时钟周期，这是因为MIPS指令集采用load／store结构，任何指令都不会同时进行数据有效地址的计算、转移目标地址的计算和对数据进行运算。 4) 存储器访问/分支完成周期(MEM)所有指令都要在该周期对PC进行更新。除了分支指令，其他指令都是做： PC←NPC。在该周期处理的指令只有load、store和分支3种指令。（1） load和store指令load指令： LMD←Mem［ALUo］ store指令： Mem［ALUo］←B（2） 分支指令
if(cond) PC ←ALUoelsePC←NPC
5) 写回周期(WB)（1） 寄存器寄存器ALU指令： Regs［rd］← ALUo（2） 寄存器立即数ALU指令： Regs［rt］← ALUo（3） load指令： Regs［rt］←LMD上述指令均是将结果写入通用寄存器组。2. 基本的MIPS流水线如果把上述实现方案中每一个时钟周期完成的工作看作是流水线的一段，就可以很容易将之改造为流水实现。流水段中的所有操作在一个时钟周期内完成，每个时钟周期启动一条新的指令。这里主要进行了以下改动。(1) 设置了流水寄存器。在段与段之间设置了流水寄存器。流水寄存器的名称用其相邻的两个段的名称来表示。流水寄存器中的字段用“x.y［s］”的形式来表示。其中，x为流水寄存器名称，y为具体子寄存器的名称，s为字段名称。流水寄存器的作用如下。① 将各段的工作隔开，使得它们不会互相干扰； ② 保存相应段的处理结果； ③ 向后传递后面将要用到的数据或者控制信息。(2) 增加了向后传递IR和从MEM/WB.IR回送到通用寄存器组的连接。后者用于实现结果回写到通用寄存器组。(3) 将对PC的修改移到了IF段，以便PC能及时地加4，为取下一条指令做好准备。为了详细了解该流水线的工作情况，需要知道各种指令在每一个流水段进行什么样的操作，如表3.1所示。在IF段和ID段，所有指令的操作都一样。从EX段开始才区分不同的指令。表中IR［rs］是指IR的第6位到第10位，即IR6..10； IR［rt］是指IR11..15； IR［rd］是指IR16..20。
表3.1MIPS流水线的每个流水段的操作
流水段所 有 指 令
IFIF/ID.IR ←Mem［PC］；
IF/ID.NPC，PC ←(if(( EX/MEM.IR［op］ == branch )& EX/MEM.cond)
{EX/MEM.ALUo} else {PC 4})； IDID/EX.A ←Regs［IF/ID.IR［rs］］； ID/EX.B ←Regs［IF/ID.IR［rt］］；
ID/EX.NPC ←IF/ID.NPC； ID/EX.IR ←IF/ID.IR；
ID/EX.Imm ←(IF/ID.IR16)16##IF/ID.IR16..31；
ALU指令load/store指令分支指令
EXEX/MEM.IR ←ID/EX.IR；
EX/MEM.ALUo ←
ID/EX.A funct ID/EX.B
或
EX/MEM.ALUo ←
ID/EX.A op ID/EX.Imm； EX/MEM.IR ←ID/EX.IR；
EX/MEM.ALUo ←
ID/EX.A ID/EX.Imm；
EX/MEM.B←ID/EX.B； EX/MEM.IR ←ID/EX.IR；
EX/MEM.ALUo ←
ID/EX.NPC ID/EX.Imm<<2；
EX/MEM.cond ←
(ID/EX.A==0)； MEMMEM/WB.IR ←EX/MEM.IR；
MEM/WB.ALUo ←
EX/MEM.ALUo； MEM/WB.IR ←EX/MEM.IR；
MEM/WB.LMD ←
Mem［EX/MEM.ALUo］；
或
Mem［EX/MEM.ALUo］ ←
EX/MEM.B； WBRegs［MEM/WB.IR［rd］］ ←
MEM/WB.ALUo；
或
Regs［MEM/WB.IR［rt］］ ←
MEM/WB.ALUo； Regs［MEM/WB. IR［rt］］ ←
MEM/WB.LMD； 为了使该流水线正常工作，还要解决好数据冲突的问题。对于该流水线而言，所有的数据冲突均可以在ID段检测到。如果存在数据冲突，就在相应的指令流出ID段之前将其暂停。完成该工作的硬件称为流水线的互锁机制。类似地，若采用了定向技术，我们可以在ID段确定需要什么样的定向，并设置相应的控制。按这样处理，就不必在流水过程中将已经改变了机器状态的指令挂起，可以降低流水线的硬件复杂度。另外一种处理方法是在使用操作数的那个时钟周期(上述流水线中的EX和MEM段)的开始检测冲突和确定必需的定向。由于使用load的结果而引起的流水线互锁称为load互锁。在load已经进入EX段时，通过比较相应的寄存器，就能判断当前在ID段的指令是否由于使用那条load指令的结果而导致RAW冲突。如果存在，流水线互锁机制必须在流水线中插入停顿，并使当前正处于IF段和ID段的指令不再前进。为实现这点，只要将ID/EX.IR中的操作码改为全0(全0表示空操作)，并将IF/ID寄存器的内容回送到自己的入口。定向逻辑要考虑的情况更多，因此其实现比上述冲突检测机制更复杂。类似地，它也是通过比较流水寄存器中的寄存器地址来确定的。在该流水线中，分支指令的条件测试和分支目标地址计算是在EX段完成，对PC的修改是在MEM段完成。它所带来的分支延迟是3个时钟周期。为了减少分支延迟，需尽早完成这些工作。如果只考虑BEQZ和BNEZ，就可以把这些工作提前到ID段进行。为此，需要在ID段增设一个加法器，用于计算分支目标地址，并把条件测试“=0？”的逻辑电路移到ID段。这样，分支延迟就减少为1个时钟周期。改进后的流水线对分支指令的处理变成了如表3.2所示的操作。斜体部分表示与表3.1不同的操作。
表3.2改进后流水线的分支操作
流水段分 支 指 令
IFIF/ID.IR ←Mem［PC］；
IF/ID.NPC，PC ←(if ((IF/ID［op］ == branch) & (Regs［IF/ID.IR［rs］］== 0))
{IF/ID.NPC (IF/ID.IR16)16 ## (IF/ID.IR16..31<< 2)} else {PC 4})； IDID/EX.A ←Regs［IF/ID. IR［rs］］； ID/EX.B←Regs［IF/ID. IR［rt］］；
ID/EX.IR ←IF/ID.IR；
ID/EX.Imm ←( IF/ID.IR16 )16 ## IF/ID. IR16..31； EXMEMWB习题1. 概念题
【题3.1】解释下列名词流水线技术通过时间排空时间定向技术部件级流水线指令流水线系统级流水线单功能流水线多功能流水线静态流水线动态流水线线性流水线非线性流水线顺序流水线乱序流水线吞吐率流水线的加速比流水线的效率相关数据相关名相关反相关输出相关换名技术控制相关流水线冲突结构冲突数据冲突控制冲突写后读冲突写后写冲突读后写冲突2. 选择题【题3.2】以下说法不正确的是()。
A. 线性流水线是单功能流水线B. 动态流水线是多功能流水线C. 静态流水线是多功能流水线D. 动态流水线只能是单功能流水线【题3.3】非线性流水线的特征是()。A. 一次运算中使用流水线中的多个段B. 一次运算中要多次使用流水线中的某些功能段C. 流水线中某些功能段在各次运算中的作用不同D. 流水线的各功能段在不同运算中可以有不同的连接【题3.4】以下是某非线性流水线的调度方案:［(2，7)； (2，2，7)； (3，4)； (4)； (3，4，7)； (4，7)； (4，3)； (5)； (7)］。其中，平均延迟小的等间隔调度方案是()。A. (4)B. (5)C. (3，4)D. (4，3)【题3.5】与线性流水线吞吐率有关的是()。A. 各个功能段的执行时间B. 快的那一段的执行时间C. 慢的那一段的执行时间D. 后功能段的执行时间【题3.6】在MIPS的指令流水线中，可能发生的冲突有()。A. 同一条指令的读操作与写操作之间的写后读冲突B. 先流入的指令的写操作与后流入的指令的读操作之间的写后读冲突C. 后流入的指令的写操作与先流入的指令的读操作之间的读后写冲突D. 两条指令的写操作之间的写后写冲突3. 填空题【题3.7】流水线中的每个子过程及其功能部件称为流水线的段，流水线的段数称为。【题3.8】流水线中慢的一段称为流水线的。【题3.9】如果流水线处理机具有向量数据表示和向量指令，则称之为流水处理机； 否则就称之为流水处理机。【题3.10】按照流水线所完成的功能来分，流水线可分为和。【题3.11】按照同一时间内各段之间的连接方式来分，流水线可分为和。【题3.12】按照流水的级别来分，流水线可分为、和。【题3.13】按照流水线中是否有反馈回路来分，流水线可分为和。【题3.14】按照输出端任务流出顺序与输入端流入的任务顺序是否相同来分，流水线可分为和。【题3.15】有一条非线性流水线，其预约表为F={2，4，5}，初始冲突向量为C0=(11010)，则对于C0，后续的两个冲突向量分别为和。【题3.16】流水线在连续流动达到稳定状态后所得到的吞吐率，称为。【题3.17】消除流水线瓶颈的方法有和两种。【题3.18】相关有3种类型： 、和。【题3.19】指令之间的名相关有和两种。【题3.20】流水线冲突有、和3种类型。【题3.21】按照指令读访问和写访问的先后顺序，可以将数据冲突分为、和3种类型。【题3.22】由分支指令引起的延迟称为。【题3.23】延迟分支方法有3种调度策略： 、和。【题3.24】基本的MIPS流水线分为5个段，分别是： 、、、和。4. 问答题【题3.25】简述流水线技术的特点。【题3.26】流水寄存器的作用是什么？【题3.27】简述非线性流水线调度所要解决的问题。【题3.28】解决流水线结构冲突的方法有哪些？【题3.29】简述通过软件(编译器)来减少分支延迟的3种方法。这些方法的共同特点是什么？【题3.30】简述延迟分支方法中的3种调度策略的优缺点。5. 应用题【题3.31】设一条指令的执行过程分成取指令、分析指令和执行指令三个阶段，每个阶段所需的时间分别为Δt、Δt和2Δt 。分别求出下列各种情况下，连续执行N条指令所需的时间。(1) 顺序执行方式； (2) 只有“取指令”与“执行指令”重叠； (3) “取指令”“分析指令”与“执行指令”重叠。【题3.32】在一台单流水线多操作部件的处理机上执行下面的程序，取指令、指令译码各需一个时钟周期，MOVE、ADD和MUL操作各需要2个、3个和4个时钟周期。每个操作都在个时钟周期从通用寄存器中读操作数，在后一个时钟周期把运算结果写到通用寄存器中。K： MOVER1，R0；R1←(R0)K 1： MULR0，R2，R1；R0←(R2)*(R1)K 2： ADDR0，R3，R2；R0←(R3) (R2)画出指令执行的流水线时空图，并计算执行完3条指令共需要多少个时钟周期。【题3.33】有一指令流水线如图3.2所示。
图3.2指令流水线
(1) 求连续输入10条指令，该流水线的实际吞吐率和效率； (2) 该流水线的“瓶颈”在哪一段？请采取两种不同的措施消除此“瓶颈”。对于你所给出的两种新的流水线，连续输入10条指令时，其实际吞吐率和效率各是多少？【题3.34】有一条流水线由4段组成，其中每当流经第3段时，总要在该段循环一次，然后才能流到第4段。如果每段经过一次所需要的时间都是Δt，问： (1) 当在流水线的输入端连续地每Δt时间输入任务时，该流水线会发生什么情况？(2) 此流水线的吞吐率为多少？如果每2Δt输入一个任务，连续处理10个任务时的实际吞吐率和效率是多少？(3) 当每段时间不变时，如何提高该流水线的吞吐率？仍连续处理10个任务时，其吞吐率提高多少？【题3.35】有一条静态多功能流水线由5段组成，如图3.3所示。加法用1、3、4、5段，乘法用1、2、5段，第3段的时间为2Δt，其余各段的时间均为Δt，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。现要在该流水线上计算∏4i=1（Ai Bi），画出其时空图，并计算其吞吐率、加速比和效率。
图3.3一条静态多功能流水线
【题3.36】有一条动态多功能流水线由5段组成(如图3.4所示)，加法用1、3、4、5段，乘法用1、2、5段，第2段的时间为2Δt，其余各段时间均为Δt，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。若在该流水线上计算∑4i=1(Ai×Bi)，试计算其吞吐率、加速比和效率。
图3.4一条动态多功能流水线
【题3.37】有一条动态多功能流水线由6个功能段组成，如图3.5所示。
图3.56段动态多功能流水线
其中，S1、S4、S5、S6组成乘法流水线，S1、S2、S3、S6组成加法流水线，各个功能段时间均为50ns，假设该流水线的输出结果可以直接返回输入端，而且设置有足够的缓冲寄存器，若以快的方式用该流水线计算：
∑5i=1xiyizi
(1) 画出时空图； (2) 计算实际的吞吐率、加速比和效率。【题3.38】有一条4段流水线如图3.6所示，一个任务通过此流水线的完成总时间为6Δt，所有相继段必须在每个时钟周期之后才能使用。
图3.6一条4段流水线
写出该流水线的预约表(4行6列)。【题3.39】在一个5段流水线处理机上，各段执行时间均为Δt，需经9Δt才能完成一个任务，任务处理对各段的使用要求预约表如表3.3所示。
表3.3题3.39预约表
时间
功能段123456789
S1√√S2√√S3√√√S4√√S5√√
(1) 画出流水线任务调度的状态转移图。(2) 求出流水线的调度策略和流水线的吞吐率。(3) 按调度策略连续输入6个任务，流水线的实际吞吐率是多少？【题3.40】有一个5段流水线，各段执行时间均为Δt，其预约表如表3.4所示。
表3.4题3.40预约表
时间
功能段1234567
S1√√S2√√S3√√S4√√S5√√
(1) 画出流水线任务调度的状态转移图。(2) 分别求出允许不等时间间隔调度和等时间间隔调度的两种调度策略，以及这两种调度策略的流水线吞吐率。(3) 若连续输入10个任务，求这两种调度策略的流水线实际吞吐率和加速比。【题3.41】在MIPS流水线上运行如下代码序列：
LOOP： LWR1，0(R2)
DADDIUR1，R1，#1
SWR1，0(R2)
DADDIUR2，R2，#4
DSUBR4，R3，R2
BNEZR4，LOOP
其中，R3的初值是R2 396。假设： 在整个代码序列的运行过程中，所有的存储器访问都是命中的，并且在一个时钟周期中对同一个寄存器的读操作和写操作可以通过寄存器组“定向”。问： (1) 在没有任何其他定向(或旁路)硬件的支持下，请画出该指令序列执行的流水线时空图。假设采用排空流水线的策略处理分支指令，且所有的存储器访问都命中Cache，那么执行上述循环需要多少个时钟周期？(2) 假设该流水线有正常的定向路径，请画出该指令序列执行的流水线时空图。假设采用预测分支失败的策略处理分支指令，且所有的存储器访问都命中Cache，那么执行上述循环需要多少个时钟周期？(3) 假设该流水线有正常的定向路径和一个单周期延迟分支，请对该循环中的指令进行调度，你可以重新组织指令的顺序，也可以修改指令的操作数，但是注意不能增加指令的条数。请画出该指令序列执行的流水线时空图，并计算执行上述循环所需要的时钟周期数。【题3.42】假设各种分支指令数占所有指令数的百分比如表3.5所示。
表3.5各种分支指令数占所有指令数的百分比
条件分支20%(其中的60%是分支成功的)跳转和调用5%
现有一条段数为4的流水线，无条件分支在第二个时钟周期结束时就被解析出来，而条件分支要到第3个时钟周期结束时才能够被解析出来。个流水段是完全独立于指令类型的，即所有类型的指令都必须经过个流水段的处理。请问在没有任何控制相关的情况下，该流水线相对于存在上述控制相关情况下的加速比是多少？题解1. 概念题
【题3.1】解释下列名词流水线技术——将一个重复的时序过程，分解成为若干个子过程，而每一个子过程都可有效地在其专用功能段上与其他子过程同时执行。通过时间——流水线中个任务进入流水线到流出结果所需的时间。排空时间——流水线中后一个任务从进入流水线到流出结果所需的时间。定向技术——用来解决写后读冲突。在发生写后读相关的情况下，在计算结果尚未出来之前，后面等待使用该结果的指令并不一定马上就要用该结果。如果能够将该计算结果从其产生的地方直接送到其他指令需要它的地方，那么就可以避免停顿。部件级流水线——又称运算操作流水线。把处理机中的部件进行分段，再把这些部件分段相互连接而成。它使得运算操作能够按流水方式进行。指令流水线——又称处理机级流水线。它是把指令的执行过程按照流水方式进行处理，即把一条指令的执行过程分解为若干个子过程，每个子过程在独立的功能部件中执行。系统级流水线——又称为宏流水线。它是把多个处理机串行连接起来，对同一数据流进行处理，每个处理机完成整个任务中的一部分。前一个处理机的输出结果存入存储器中，作为后一个处理机的输入。单功能流水线——指流水线的各段之间的连接固定不变、只能完成一种固定功能的流水线。多功能流水线——指各段可以进行不同的连接，以实现不同功能的流水线。静态流水线——指在同一时间内，多功能流水线中的各段只能按同一种功能的连接方式工作的流水线。当流水线要切换到另一种功能时，必须等前面的任务都流出流水线之后，才能改变连接。动态流水线——指在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能的流水线。它允许在某些段正在实现某种运算时，另一些段却在实现另一种运算。线性流水线——指各段串行连接、没有反馈回路的流水线。数据通过流水线中的各段时，每一个段多只流过一次。非线性流水线——指各段除了有串行的连接外，还有反馈回路的流水线。顺序流水线——流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。乱序流水线——流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同，允许后进入流水线的任务先完成。这种流水线又称为无序流水线、错序流水线、异步流水线。吞吐率——指在单位时间内流水线所完成的任务数量或输出结果的数量。流水线的加速比——指使用顺序处理方式处理一批任务所用的时间与按流水处理方式处理同一批任务所用的时间之比。流水线的效率——即流水线设备的利用率，它是指流水线中的设备实际使用时间与整个运行时间的比值。相关——指两条指令之间存在某种依赖关系。数据相关——考虑两条指令i和j，i在j的前面，如果下述条件之一成立，则称指令j与指令i数据相关： (1) 指令j使用指令i产生的结果； (2) 指令j与指令k数据相关，而指令k又与指令i数据相关。名相关——如果两条指令使用了相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。反相关——考虑两条指令i和j，i在j的前面，如果指令j所写的名与指令i所读的名相同，则称指令i和j发生了反相关。输出相关——考虑两条指令i和j，i在j的前面，如果指令j和指令i所写的名相同，则称指令i和j发生了输出相关。换名技术——名相关的两条指令之间并没有数据的传送，只是使用了相同的名。可以把其中一条指令所使用的名换成别的，以消除名相关。控制相关——指由分支指令引起的相关。它需要根据分支指令的执行结果来确定后面该执行哪个分支上的指令。流水线冲突——指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期开始执行。结构冲突——因硬件资源满足不了指令重叠执行的要求而发生的冲突。数据冲突——当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突。控制冲突——流水线遇到分支指令或其他会改变PC值的指令所引起的冲突。写后读冲突——考虑两条指令i和j，且i在j之前进入流水线，指令j用到指令i的计算结果，而且在i将结果写入寄存器之前就去读该寄存器，因而得到的是旧值。写后写冲突——考虑两条指令i和j，且i在j之前进入流水线，指令j和指令i的结果寄存器相同，而且j在i写入之前就先对该寄存器进行了写入操作，从而导致写入顺序错误。后在结果寄存器中留下的是i写入的值。读后写冲突——考虑两条指令i和j，且i在j之前进入流水线，指令j的目的寄存器和指令i的源操作数寄存器相同，而且j在i读取该寄存器之前就先对它进行了写操作，导致i读到的值是错误的。1. 选择题【题3.2】答： D【题3.3】答： B【题3.4】答： A【题3.5】答： C【题3.6】答： B3. 填空题【题3.7】答： 流水线的深度【题3.8】答： 瓶颈【题3.9】答： 向量、标量【题3.10】答： 单功能流水线、多功能流水线【题3.11】答： 静态流水线、动态流水线【题3.12】答： 部件级流水线、处理机级流水线、处理机间流水线【题3.13】答： 线性流水线、非线性流水线【题3.14】答： 顺序流动流水线、异步流动流水线【题3.15】答： 111110、11011【题3.16】答： 吞吐率【题3.17】答： 细分瓶颈段、重复设置瓶颈段【题3.18】答： 数据相关、名相关、控制相关【题3.19】答： 反相关、输出相关【题3.20】答： 结构冲突、数据冲突、控制冲突【题3.21】答： 写后读冲突、写后写冲突、读后写冲突【题3.22】答： 分支延迟【题3.23】答： 从前调度、从目标处调度、从失败处调度【题3.24】答： 取指令周期、指令译码/读寄存器周期、执行/有效地址计算周期、存储器访问/分支完成周期、写回周期4. 问答题【题3.25】答： 流水技术具有以下特点。(1) 流水线把一个处理过程分解为若干个子过程，每个子过程由一个专门的功能部件来实现。因此，流水线实际上是把一个大的处理功能部件分解为多个独立的功能部件，并依靠它们的并行工作来提高吞吐率。(2) 流水线中各段的时间应尽可能相等，否则将引起流水线堵塞和断流。(3) 流水线每一个功能部件的前面都要有一个缓冲寄存器，称为流水寄存器。(4) 流水技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。(5) 流水线需要有通过时间和排空时间。在这两个时间段中，流水线都不是满负荷工作。【题3.26】答： 流水寄存器的作用是在相邻的两段之间传送信息，提供后面流水段要用到的信息。【题3.27】答： 在非线性流水线中，由于反馈回路的存在，有可能会出现多个任务争用同一段的冲突现象。究竟应按什么样的时间间隔向流水线输入新任务，才能既不发生冲突，又能使流水线有较高的吞吐率和效率？这就是非线性流水线调度所要解决的问题。【题3.28】答： ①流水化功能单元； ②资源重复； ③暂停流水线。【题3.29】答： (1)预测分支失败： 沿失败的分支继续处理指令，就好像什么都没发生似的。当确定分支是失败时，说明预测正确，流水线正常流动； 当确定分支是成功时，流水线就把在分支指令之后取出的指令转化为空操作，并按分支目标地址重新取指令执行。(2) 预测分支成功： 当流水线ID段检测到分支指令后，一旦计算出了分支目标地址，就开始从该目标地址取指令执行。(3) 延迟分支： 主要思想是从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成。不管分支是否成功，都要按顺序执行延迟槽中的指令。三种方法的共同特点： 它们对分支的处理方法在程序的执行过程中始终是不变的。它们要么总是预测分支成功，要么总是预测分支失败。【题3.30】答： 延迟分支方法中的3种调度策略的优缺点如表3.6所示。
表3.6延迟分支方法中的3种调度策略的优缺点
调 度 策 略对调度的要求对流水线性能改善的影响
从前调度分支必须不依赖于被调度的指令总是可以有效提高流水线性能从目标处调度如果分支转移失败，必须保证被调度的指令对程序的执行没有影响。可能需要复制被调度指令分支转移成功时，可以提高流水线性能。但由于复制指令，可能加大程序空间从失败处调度如果分支转移成功，必须保证被调度的指令对程序的执行没有影响分支转移失败时，可以提高流水线性能
5. 应用题【题3.31】解： (1) 每条指令的执行时间为： Δt＋Δt＋2Δt＝4Δt
连续执行N条指令所需的时间为： 4NΔt(2) 连续执行N条指令所需的时间为： 4Δt＋3(N-1)Δt＝(3N＋1)Δt(3) 连续执行N条指令所需的时间为： 4Δt＋2(N-1)Δt＝(2N＋2)Δt【题3.32】解： 指令/时钟123456789KIFIDEXEXK 1IFIDstallEXEXEXEXK 2IFstallIDEXEXstallEX计算执行完三条指令共使用了9个时钟周期。【题3.33】解： (1)
Tpipeline=∑mi=1Δti (n-1)Δtmax=(50 50 100 200) 9×200=2200(ns)
TP=nTpipeline=1220(ns-1)
E=TP·∑mi=1Δtim=TP·4004=511≈45.45%
(2) 3、4段是瓶颈。① 变成8级流水线(细分)，如图3.7所示。
图3.78级流水线
Tpipeline=∑mi=1Δti (n-1)Δtmax=50×8 9×50=850(ns)
TP=nTpipeline=185(ns-1)
E=TP·∑mi=1Δtim=TP·4008=1017≈58.82%
② 重复设置部件(如图3.8所示)
图3.8重复设置部件
图3.9时空图
TP=nTpipeline=185(ns-1)
E=400×10850×8=1017≈58.82%
【题3.34】解： (1) 会发生流水线阻塞情况，如表3.7所示。
表3.7流水线阻塞情况
第1个任务S1S2S3S3S4第2个任务S1S2stallS3S3S4第3个任务S1stallS2stallS3S3S4第4个任务S1stallS2stallS3S3S4
(2) 不阻塞情况。
图3.10时空图
TPmax=12Δt
Tpipeline=23Δt
TP=nTpipeline=1023Δt
E=TP·5Δt4=5092≈54.35%
(3) 重复设置部件。
图3.11重复设置部件
图3.12重复设置部件后的时空图
TP=nTpipeline=1014·Δt=57·Δt
吞吐率提高倍数＝57Δt1023Δt＝1.64
【题3.35】解： 首先，应选择适合于流水线工作的算法。对于本题，应先计算A1＋B1、A2＋B2、A3＋B3 和A4＋B4； 再计算(A1＋B1)×(A2＋B2)和(A3＋B3)×(A4＋B4)； 然后求总的结果。其次，画出完成该计算的时空图，如图3.13所示，图中阴影部分表示该段在工作。
图3.13时空图
由图3.13可见，它在18个Δt时间中，给出了7个结果。所以吞吐率为：
TP=718Δt
如果不用流水线，由于一次求积需3Δt，一次求和需5Δt，则产生上述7个结果共需(4×5 3×3)Δt=29Δt。所以加速比为：
S=29Δt18Δt=1.61
该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得：
E=4×5 3×35×18=0.322
【题3.36】解： 首先，应选择适合于流水线工作的算法。对于本题，应先计算A1×B1、A2×B2、A3×B3 和A4×B4； 再计算(A1×B1)＋(A2×B2)和(A3×B3)＋(A4×B4)； 然后求总的累加结果。其次，画出完成该计算的时空图，如图3.14所示，图中阴影部分表示该段在工作。
图3.14时空图
由图3.14可见，它在18个Δt时间中，给出了7个结果。所以吞吐率为：
TP=718Δt
如果不用流水线，由于一次求积需4Δt，一次求和需4Δt，则产生上述7个结果共需(4×4 3×4)Δt=28Δt。所以加速比为：
S=28Δt18Δt≈1.56
该流水线的效率可由阴影区和5个段总时空区的比值求得：
E=4×4 3×45×18≈0.31
【题3.37】解： 机器一共要做10次乘法，4次加法。时空图如图3.15所示。
图3.15时空图
【题3.38】解： 流水线的预约表如表3.8所示。
表3.8流水线的预约表
时间
功能段 123456
S1√√S2√√S3√S4√
【题3.39】解： (1) 由预约表得出禁止表： F={8，4，3，1}为避免争用S1段，禁用启动距离： 8； 为避免争用S2段，禁用启动距离： 1； 为避免争用S3段，禁用启动距离： 3，4，1； 为避免争用S4段，禁用启动距离： 1； 为避免争用S5段，禁用启动距离： 1。由禁止表得到初始冲突向量： C0=(10001101)C0=(10001101)有4个后继状态： C1=SHR(2)(C0)∨C0=(00100011)∨(10001101)=(10101111)C2=SHR(5)(C0)∨C0=(00000100)∨(10001101)=(10001101)=C0C3=SHR(6)(C0)∨C0=(00000010)∨(10001101)=(10001111)C4=SHR(7)(C0)∨C0=(00000001)∨(10001101)=(10001101)= C0C1=(10101111)有两个后继状态： C5=SHR(5)(C1)∨C0=(10001101)=C0C6=SHR(7)(C1)∨C0=(10001101)=C0C3=(10101111)有三个后继状态： C7=SHR(5)(C3)∨C0=(10001101)= C0C8=SHR(6)(C3)∨C0=(10001111)= C3C9=SHR(7)(C3)∨C0=(10001101)= C0得出状态转移图如图3.16所示。
图3.16状态转移图
各种调度策略及平均延迟时间如表3.9所示。
表3.9调度策略及平均延迟时间
调 度 策 略平均延迟时间
(2,5)3.5Δt(2,7)4.5Δt(5)5Δt(6,5)5.5Δt(6)6Δt(6,7)6.5Δt(7)7Δt
(2) 在表3.9中，平均延迟时间小的调度策略是调度策略： (2，5)； 流水线的吞吐率就是调度策略的吞吐率： 1/(3.5Δt)。(3) 按调度策略连续输入6个任务，流水线的实际吞吐率为：
TP=6（2 5 2 5 2 9）Δt=625Δt
【题3.40】解： (1) 由预约表得出禁止表： F= {6，3，1}为避免争用S1段，禁用启动距离： 6； 为避免争用S2段，禁用启动距离： 3； 为避免争用S3段，禁用启动距离： 1； 为避免争用S4段，禁用启动距离： 3； 为避免争用S5段，禁用启动距离： 1。由禁止表得到初始冲突向量： C0=(100101)，由初始冲突向量和后继冲突向量的计算公式Cj=SHR(k)(Ci)∨C0，可得流水线任务调度的状态转移图如图3.17所示。
图3.17流水线任务调度的状态转移图
(2) 由状态转移图可得不发生段争用冲突的调度策略以及平均延迟时间，如表3.10所示。
表3.10调度策略和平均延迟时间
调 度 策 略平均延迟时间
(2,2,5)3Δt(2,5)3.5Δt(4)4Δt(4,5)4.5Δt(5)5Δt
由表3.10可知，允许不等时间间隔调度的调度策略是(2，2，5)，流水线吞吐率为： 1/(3Δt)。等时间间隔调度的调度策略是(4)，流水线吞吐率为： 1/(4Δt)。(3) 按调度策略(2，2，5)，连续输入10个任务的流水线实际吞吐率与加速比分别为：
TP1=10（2 2 5 2 2 5 2 2 5 7）Δt=1034Δt
S1=10×7Δt34Δt=2.06
按调度策略(4)，连续输入10个任务的流水线实际吞吐率与加速比分别为：
TP2=10（4×9 7）Δt=1043Δt
S2=10×7Δt43Δt=1.63
【题3.41】解： (1) 寄存器读写可以定向，无其他旁路硬件支持。排空流水线时空图如图3.18所示。
图3.18排空流水线时空图
指令12345678910111213141516171819202122LWIFIDEXMWBDADDIUIFSSIDEXMWBSWIFSSIDEXMWBDADDIUIFIDEXMWBDSUBIFSSIDEXMWBBNEZIFSSIDEXMWBLWIFSSIFIDEXMWB
图3.18排空流水线时空图
第i次迭代(i＝0…98)开始周期： 1＋(i×17)(2) 有正常定向路径，预测分支失败，如图3.19所示。
指令12345678910111131415LWIFIDEXMWBDADDIUIFIDSEXMWBSWIFSIDEXMWBDADDIUIFIDEXMWBDSUBIFIDEXMWBBNEZIFIDEXMWBLWIFmissmissIFIDEXMWB
图3.19采用预测分支失败的时空图
图3.19采用预测分支失败的时空图
第i次迭代(i＝0…98)开始周期： 1＋(i×10)总的时钟周期数： (98×10)＋11＝991(3) 有正常定向路径。单周期延迟分支的时空图如图3.20所示。
LOOP:LWR1，0(R2)
DADDIUR2，R2，#4
DADDIUR1，R1，#1
DSUBR4，R3，R2
BNEZR4，LOOP
SWR1，-4(R2)
第i次迭代(i ＝0…98)开始周期： 1＋(i×6)总的时钟周期数： (98×6)＋10＝598
指令1234567891011LW IFIDEXMWBDADDIUIFIDEXMWBDADDIUIFIDEXMWBDSUBIFIDEXMWBBNEZIFIDEXMWBSWIFIDEXMWBLW IFIDEXMWB
图3.20采用单周期延迟分支的时空图
图3.20采用单周期延迟分支的时空图
【题3.42】解： 没有控制相关时流水线的平均CPI＝1。存在控制相关时，由于无条件分支在第二个时钟周期结束时就被解析出来，而条件分支要到第3个时钟周期结束时才能被解析出来。所以： (1) 若使用排空流水线的策略，则对于条件分支，有两个额外的停顿，对无条件分支，有一个额外的停顿：
CPI=1 20%×2 5%×1=1.45
加速比S=CPI/1=1.45
(2) 若使用预测分支成功策略，则对于不成功的条件分支，有两个额外的停顿，对无条件分支和成功的条件分支，有一个额外的停顿：
CPI=1 20%×(60%×1 40%×2) 5%×1=1.33
加速比S=CPI/1=1.33
(3) 若使用预测分支失败策略，则对于成功的条件分支，有两个额外的停顿； 对无条件分支，有一个额外的停顿； 对不成功的条件分支，其目标地址已经由PC值给出，不必等待，所以无延迟：
CPI=1 20%×(60%×2 40%×0) 5%×1=1.29
加速比S=CPI/1=1.29
评论
还没有评论。