j计算机体系结构第三章习题

第 三 章 习 题

1.1 解释下列名词术语

静态多功能流水线是指在同一段时间内，多功能流水线只能按一种方式连接，实现一种功能。 顺序流动是指任务从流水线流出的次序同流入流水线的次序一样。

异步流动是指任务从流水线流出的次序同流入流水线的次序不一样，也称为乱序流动或错序流动。

1.2 什么是流水线？简述流水线的特点。

流水线是指把一个重复的过程分解为若干个子过程，一个过程的子过程可以与其它过程的不同的子过程并行进行，实现不同过程在时间上重叠进行的工作方式。实现流水线的技术方法称为流水线技术。它的特点主要有：

（1）流水线中各功能段的时间应尽量相等，否则将引起“堵塞”、“断流”等 （2）流水线需要有“装入时间”和“排空时间”。

（3）只有连续不断地提供同种任务才能充分发挥流水线的效率。

（4）在流水线的每一个功能部件的后面都要有一个缓冲寄存器，或称为锁存器、闸门寄存器等。

1.3 什么是先行控制？简述处理机采用先行控制的基本原理，描述实现先行控制的基本结构。

先行控制是指通过对任务的预处理和缓冲，以平滑功能部件工作速度上的差异，使功能部件能独立地工作，并始终处于忙碌状态，提高任务执行的速度。它实质是缓冲技术和预处理技术相结合的结果。

先行控制方式的基本原理是：当流水线中某功能段的延迟时间较长时，该功能段前面的功能段对后继任务进行预处理，预处理好的后继任务置于缓冲器中。而该功能段后面的功能段则对以前置于缓冲器的任务进行后行处理。这样，所有的功能段都处于忙碌状态。某任务的流程中，各功能段之间有等待的时间间隔，但各自的流程是连续的。当然，如果前面功能段的缓冲器已满，或者后面功能段没有后行处理任务，流水线仍是不流畅的。实现先行控制的基本结构如下图所示。

先行指令缓冲栈 指令分析器

先行读数栈 存先行操作栈 主

寄储存

存控储 运算控制器 器制器

组 器

1.4 什么是数据相关？它有哪几种类型？

数据相关是指在流水线的机器中，程序中相近的两条指令要对同一存储单元进行操作时，应有一定的先后次序，否则会导致数据供求关系上的冲突，引发程序执行错误。这种相关主要有“先写后读”相关、“先读后写”相关和“写一写”相关三种。由于数据相关对程序执行过程影响较小，仅涉及到相应指令的前后一条或几条指令的执行，所以又称为局部相关。 1.5 什么是控制相关？它有哪几种类型？

控制相关是指在流水线的机器中，由于转移指令或中断引起程序执行方向的改变，使得转移指令或中断引起的断点指令与后续指令不能同时在流水线中执行。它包括转移相关和中断相关两种。由于控制相关对程序执行过程影响较大，可能改变程序的执行方向，所以又称为全局相关。

后行写数栈 运算器 3.8 在一台单流水线多操作部件的处理机上执行下面的程序，每条指令的取指令、指令译码需要一个时

钟周期，MOVE、ADD和MUL操作分别需要2个、3个和4个时钟周期，每个操作都在第一个时钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果写到通用寄存器中。

k： MOVE R1，R0 ；R1← (R0)

k+1： MUL R0，R2，R1 ；R0← (R2)×(R1) k+2： ADD R0，R2，R3 ；R0← (R2)+(R3)

(1)就程序本身而言，可能有哪几种数据相关?

(2)在程序实际执行过程中，哪几种数据相关会引起流水线停顿?

(3)画出指令执行过程的流水线时空图，并计算完成这3条指令共需要多少个时钟周期？ 解：（1）就程序本身而言，可能有三种数据相关。若3条指令顺序流动，则k指令对R1寄存器的写与k+1指令对R1寄存器的读形成的“先写后读”相关。若3条指令异步流动，则k指令对R0寄存器的读与k+1指令对R0寄存器的写形成的“先读后写”相关，k+2指令对R0寄存器的写与k+1指令对R0寄存器的写形成的“写—写”相关。

（2）在程序实际执行过程中，二种数据相关会引起流水线停顿。一是“先写后读”相关，k指令对R1的写在程序执行开始后的第四个时钟；k+1指令对R1的读对指令本身是第三个时钟，但k+1指令比k指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟要读R1。不能在同一时钟周期内读写同一寄存器，因此k+1指令应推迟一个时钟进入流水线，产生了流水线停顿。二是“写—写”相关，k+1指令对R0的写对指令本身是第六个时钟，而要求该指令进入流水线应在程序执行开始后的第三个时钟，所以对R0的写是在程序执行开始后的第八个时钟。k+2指令对R0的写对指令本身是第五个时钟，而k+2指令比k+1指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟，所以对R0的写是在程序执行开始后的第八个时钟。不能在同一时钟周期内写写同一寄存器，因此k+2指令应推迟一个时钟进入流水线，产生了流水线停顿。另外，可分析“先读后写”相关不会产生流水线的停顿。

（3）由题意可认位该指令流水线由六个功能段取指、译码、取数、运一、运二和存数等组成，则程序指令执行过程的流水线时空图如下图所示。若3条指令顺序流动，共需要9个时钟周期。 空间 存数 K存数 K+1存数 K+2存数 运二 K+1运二 运一 K+1运一 K+2运一 取数 K取数 K+1取数 K+2取数 译码 K译码 K+1译码 K+2译码 取指 K取指 K+1取指 K+2取指 时间 0 1 2 3 4 5 6 7 8 9

3.9 某流水线由4个功能部件组成，每个功能部件的执行时间都为△t。当输入10个数据后，停顿5t，

又输入10个数据，如此重复。计算流水线的实际吞吐率、加速比和效率，并画出时空图。

解：该题中的流水线的任务是非连续流入的，因此不能直接应用公式直接计算，要利用时空图。题意的流水线时空图如下图所示。

空间 S4 1 2 3 4 5 6 7 8 9 10 1 2 S3 1 2 3 4 5 6 7 8 9 10 1 2 S2 1 2 3 4 5 6 7 8 9 10 1 2 S1 1 2 3 4 5 6 7 8 9 10 1 2 时间

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

TP = 10/15Δt = 0.67/Δt S = T0/TK = 10×4Δt/15Δt = 2.67 E = 4×10Δt/5×15Δt = 0.67 3.11 有一个四段指令流水线为取指（IF）、译码（ID）、执行（EX）、写回（WB），分支指令在第二个时钟

周期未决定是不是条件失败分支，在第三个时钟周期未决定是不是成功分支，还假定第一个时钟周期的操作和条件分支无关，并略去其它流水线停顿。要求：

（1）分别画出无条件分支、发生的条件分支、不发生的条件分支时指令执行的时空图。

（2）假设条件分支指令占所有指令的20%，且其中60%指令可能执行，无条件分支占5%，问实际的

流水线加速比是多少。 解：（1）根据题意，分支指令采用的是流水线停顿的方法来处理。而判断条件分支指令让流水线停顿，应在取指功能段后设计一个“指令分析器”来判断流水线是否停顿。显然，无条件分支指令与条件成功（发生条件）分支是一样的，需要在第三个时钟周期未决定下一条指令的地址，因此流水线要停顿二个时钟周期。对于条件失败（条件不成功）分支，需要在第二个时钟周期未决定下一条指令的地址，因此流水线要停顿一个时钟周期。

（2）串行执行N条指令的时间为：T1=N·k·Δt，

流水线方式执行N条指令的时间为：Tn=（k-1）Δt+（N+N·5%·2+N·20%·60%·1.5）Δt Sn=T1/Tn=k/1.28

3.13 用一条5个功能段的浮点加法器流水线计算F=

?(Ai)，每个功能段的延迟时间，每个功能段的延

i?110迟时间均相等，流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，计算流水线的实际吞吐率、加速比和效率。 解：为使计算过程充分利用流水线的性能，避免“先写后读”相关，需要将计算的算法改为： （（（（A1 + A2）+（A3 + A4））+（A9 + A10））+（（A5 + A6）+（A7 + A9））） 且按括号的优先次序计算九次加法，相应的流水线时空图如下图所示。

空间 S5 1 2 3 4 5 6 7 8 9 S4 1 2 3 4 5 6 7 8 9 S3 1 2 3 4 5 6 7 8 9 S2 1 2 3 4 5 6 7 8 9 S1 1 2 3 4 5 6 7 8 9 时间

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

TP = 9/21Δt = 0.429/Δt S = T0/TK = 9×5Δt/21Δt = 2.143 E = 5×9Δt/5×21Δt = 0.429

3.15 有一条3个功能段的流水线如下图所示，每个功能段的延迟时间均为△t，但是，功能段S2的输出

要返回到它自己的输入端循环执行一次。

S1 S2 S3 输入 输出

△t △t △t

（1）如果每隔一个△t向流水线连续输入任务，这条流水线会发生什么问题？ （2）求这条流水线能够正常工作的实际吞吐率、加速比和效率。

（3）可用什么办法来提高流水线的吞吐率，画出改进后的流水线结构。

解：（1）每个任务在段S2要反馈循环一次，执行时间为2Δt，其它各段的执行时间为Δt，因此应按瓶颈段的执行时间2Δt流入任务，才不会发生冲突现象，否则会发生流水线的阻塞。 （2）若连续输入n个任务，则流水线的实际吞吐率、加速比和效率分别为： TP = n/（4Δt +2（n–1）Δt）= n/2（n + 1）Δt

S = 4nΔt/（4Δt +2（n–1）Δt）= 2n/（n + 1）

E = 4nΔt/3（4Δt +2（n–1）Δt）= 2n/3（n + 1）

（3）为提高流水线的吞吐率，可重复设置段S2，并使两个段S2串连在一起，从而消除瓶颈段S2，而且各段执行时间相等为Δt，流水线的段数为4。流水线的结构如下图所示。

S1 S2 S2 S3 输入 输出

△t △t △t △t

3.16 在一个5段的流水线处理机上需经9△t才能完成一个任务，其预约表为：

时间 1 2 3 4 5 6 7 8 9 流水段 S1 × × S2 × × × S3 × S4 × ×

S5 × ×

（1）写出流水线的初始冲突向量。

（2）画出流水线任务调度的状态有向图。

（3）求出流水线的最优调度策略及最小平均延迟时间和流水线的最大吞吐率。 （4）按最优调度策略连续输入8个任务时，流水线的实际吞吐率是多少? 解：（1）根据初始冲突向量的构成方法，对预约表各行中打“×”的拍数求出差值，除去重复的后汇集在一起，即得到延迟禁止表为F =｛1，5，6，8｝。由F可得到初始冲突向量为： C =（10110001）

（k）

（2）根据后继冲突向量的递推规则Cj = SHR（Ci）∨C0则可得出所有的后继状态，具体有：

（2）

C0四个后继状态：C1 =SHR（C0）∨C0 = 10111101 7 （3）

C2 =SHR（C0）∨C0 = 10110111 10110001 C0 （4）

C3 =SHR（C0）∨C0 = 10111011 3 2 （7）

C4 =SHR（C0）∨C0 = 10110001=C0 7 4 7 （2）

C1二个后继状态：C5 =SHR（C1）∨C0 = 10111111 10110111 C2 10111101 C1 （7）

C6 =SHR（C1）∨C0 = 10110001=C0 7 （4）

C2二个后继状态：C7 =SHR（C2）∨C0 = 10111011=C3 3 4 7 2 （7）

C8 =SHR（C2）∨C0 = 10110001=C0

（3）10111011 C3 10111111 C5 C3二个后继状态：C9 =SHR（C3）∨C0 = 10110111=C2 （7）

C10=SHR（C3）∨C0 = 10110001=C0

（7）

C5一个后继状态：C11=SHR（C5）∨C0 = 10110001=C0

由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。

（3）由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间，如下表所示。

调度策略 平均延迟时间 特别地，从C0出发的[3，（4，3）]也是一个 （2，2，7） （2+2+7）△t/3 = 3.67△t 任务调度策略，除第一条有向弧外，第二、三条 （2，7） （2+7）△t/2 = 4.5△t 有向组成一个环路，该调度策略为（4，3）。从表 （3，4，7） （3+4+7）△t/3 = 4.67△t 中可以得到平均延迟时间最小的调度策略为（4， （3，7） （3+7）△t/2 = 5△t 3），该调度策略则为最优调度策略，相应的最小

（4，3，7） （4+3+7）△t/3 = 4.67△t 平均延迟时间为3.5△t，所以流水线的最大吞吐 （4，7） （4+7）△t/2 = 5.5△t 率为：

（7） 7△t TPmax = 1/（3.5△t）= 0.286/△t 3，（4，3） （4+3）△t/2 = 3.5△t

（4）按最优调度策略[3，（4，3）]连续输入8个任务时，流水线的实际吞吐率为： TP = 8/[（3 + 4 + 3 + 4 + 3 + 4 + 3 + 9）△t] = 0.24/△t

3.17 有一个5段流水线的预约表如下：

(1)画出流水线调度状态有向图。

(2)分别求出允许不等间隔调度和等间隔调度的最优调度策略以及这两种调度策略的最大吞吐率。 (3)若连续输入10个任务，求这两种调度策略的实际吞吐率。 时间 1 2 3 4 5 6 7 流水段

S1 × ×

S2 × ×

S3 × ×

S4 × ×

S5 × × 解：（1）根据初始冲突向量的构成方法，对预约表各行中打“×”的拍数求出差值，除去重复的后汇集在一起，即得到延迟禁止表为F =｛1，3，6｝。由F可得到初始冲突向量为： C0 =（100101）

（k）

根据后继冲突向量的递推规则Cj = SHR（Ci）∨C0则可得出所有的后继状态，具体有：

（2）

C0三个后继状态：C1 =SHR（C0）∨C0 = 101101 5 （4）

C2 =SHR（C0）∨C0 = 100111 100101 C0 （5）

C3 =SHR（C0）∨C0 = 100101= C0 4 2 5 5 C1二个后继状态：C4 =SHR（C1）∨C0 = 101111 100111 C2 101101 C1 （5）

C5 =SHR（C1）∨C0 = 100101=C0 5 （4）

C2二个后继状态：C6 =SHR（C2）∨C0 = 100111=C2 4 2 （5）

C7 =SHR（C2）∨C0 = 100101=C0

（5）101111 C4 C4一个后继状态：C8 =SHR（C4）∨C0 = 100101=C0

由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。

（2）由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间，如下表所示。

（2）

调度策略 平均延迟时间 特别地，从C0出发的[4，（4）]也是一个任务 （2，5） （2+5）△t/2 = 3.5△t 调度策略，除第一条有向弧外，第二条有向弧是一 （4，5） （4+5）△t/2 = 4.5△t 个环路，该调度策略为（4）。从表中可以得到平均 （5） 5△t 延迟时间最小的等间隔和不等间隔的调度策略为 （2，2，5） （2+2+5）△t/3 = 3△t [4，（4）]和（2，2，5），相应的最小平均延迟时

4，（4） 4△t 间为4△t和3△t，所以流水线的最大吞吐率为：

TPAmax = 1/（4△t）= 0.25/△t TPBmax = 1/（3△t）= 0.33/△t （3）按等间隔最优调度策略[4，（4）]连续输入10个任务时，流水线的实际吞吐率为： TP = 10/[（4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 7）△t] = 10/43△t 按不等间隔最优调度策略（2，2，5）连续输入10个任务时，流水线的实际吞吐率为： TP = 10/[（2 + 2 + 5 + 2 + 2 + 5 + 2 + 2 + 5 + 7）△t] = 5/17△t

调度策略 平均延迟时间 特别地，从C0出发的[4，（4）]也是一个任务 （2，5） （2+5）△t/2 = 3.5△t 调度策略，除第一条有向弧外，第二条有向弧是一 （4，5） （4+5）△t/2 = 4.5△t 个环路，该调度策略为（4）。从表中可以得到平均 （5） 5△t 延迟时间最小的等间隔和不等间隔的调度策略为 （2，2，5） （2+2+5）△t/3 = 3△t [4，（4）]和（2，2，5），相应的最小平均延迟时

4，（4） 4△t 间为4△t和3△t，所以流水线的最大吞吐率为：

TPAmax = 1/（4△t）= 0.25/△t TPBmax = 1/（3△t）= 0.33/△t （3）按等间隔最优调度策略[4，（4）]连续输入10个任务时，流水线的实际吞吐率为： TP = 10/[（4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 7）△t] = 10/43△t 按不等间隔最优调度策略（2，2，5）连续输入10个任务时，流水线的实际吞吐率为： TP = 10/[（2 + 2 + 5 + 2 + 2 + 5 + 2 + 2 + 5 + 7）△t] = 5/17△t

本文来源：https://www.bwwdw.com/article/pkw8.html