第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
系统结构应用的题目？.doc
第 三 章 习 题
3.8 在一台单流水线多操作部件的处理机上执行下面的程序，每条指令的取指令、指令译
码需要一个时钟周期，MOVE、ADD 和 MUL 操作分别需要 2 个、3 个和 4 个时钟周期，每
个操作都在第一个时钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果
写到通用寄存器中。
MOVE
R1，R0
k：
k+1： MUL R0，R2，R1
k+2： ADD R0，R2，R3
；R1← (R0)
；R0← (R2)×(R1)
；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 个数据
后，停顿 5△t，又输入 10 个数据，如此重复。计算流水线的实际吞吐率、加速比和效
率，并画出时空图。
解：该题中的流水线的任务是非连续流入的，因此不能直接应用公式直接计算，要利用
时空图。题意的流水线时空图如下图所示。
空间
1
2
3
4
5
6
7
8
9
10
1
1
2
2
3
3
4
4
5
1
1
2
3
4
5
5
6
6
6
7
7
7
8
8
9
9
10
10
8
9
10
2
1
2
1
1
2
S4
S3
S2
S1
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
E = 4×10Δt/4×15Δt = 0.67
S = T0/TK = 10×4Δt/15Δt = 2.67
3.13 用一条 5 个功能段的浮点加法器流水线计算 F=
(
Ai ，每个功能段的延迟时间，每
)
10
i
1
个功能段的延迟时间均相等，流水线的输出端与输入端之间有直接数据通路，而且设
置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，计算
流水线的实际吞吐率、加速比和效率。
解：为使计算过程充分利用流水线的性能，避免“先写后读”相关，需要将计算的算法
改为：
（（（（A1 + A2）+（A3 + A4））+（A9 + A10））+（（A5 + A6）+（A7 + A8）））
且按括号的优先次序计算九次加法，相应的流水线时空图如下图所示。
空间
1
2
3
4
5
6
7
4
5
1
2
3
2
3
4
3
4
5
4
5
1
2
3
5
6
6
6
7
6
7
7
1
2
1
7
8
8
8
8
8
9
9
9
9
0
1
2
3
4
5
6
7
8
9
10
11 12
13 14
15 16
17 18
19
S5
S4
S3
S2
S1
9
时间
20 21
TP = 9/21Δt = 0.429/Δt
E = 5×9Δt/5×21Δt = 0.429
S = T0/TK = 9×5Δt/21Δt = 2.143
3.16 在一个 5 段的流水线处理机上需经 9△t 才能完成一个任务，其预约表为：
时间 1
2
3
4
5
6
7
8
流水段
S1
S2
S3
S4
×
×
×
×
×
×
×
9
×
（1）写出流水线的初始冲突向量。
（2）画出流水线任务调度的状态有向图。
（3）求出流水线的最优调度策略及最小平均延迟时间和流水线的最大吞吐率。
（4）按最优调度策略连续输入 8 个任务时，流水线的实际吞吐率是多少?
解：（1）根据初始冲突向量的构成方法，对预约表各行中打“×”的拍数求出差值，除去重
复的后汇集在一起，即得到延迟禁止表为 F =｛1，5，6，8｝。由 F 可得到初始冲突向量为：
（2）根据后继冲突向量的递推规则 Cj = SHR（k）（Ci）∨C0 则可得出所有的后继状态，
C =（10110001）
具体有：
C0 四个后继状态：C1 =SHR（2）（C0）∨C0 = 10111101
C2 =SHR（3）（C0）∨C0 = 10110111
C3 =SHR （ 4 ）（ C0 ） ∨ C0 = 10111011
2
C4 =SHR（7）（C0）∨C0 = 10110001=C0
C1 二个后继状态：C5 =SHR（2）（C1）∨C0 = 10111111
C6 =SHR（7）（C1）∨C0 = 10110001=C0
7
10110001 C0
7
4
3
7
10110111 C2
10111101 C1
7
7
2
C2 二个后继状态：C7 =SHR（4）（C2）∨C0 = 10111011=C3
3
4
C8 =SHR（7）（C2）∨C0 = 10110001=C0
C3 二个后继状态：C9 =SHR（3）（C3）∨C0 = 10110111=C2
C10=SHR（7）（C3）∨C0 = 10110001=C0
C5 一个后继状态：C11=SHR（7）（C5）∨C0 = 10110001=C0
10111011 C3
10111111 C5
由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。
（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
△t
3，（4，3）
（4+3）△t/2 = 3.5△t
TPmax = 1/（3.5△t）= 0.286/
（4）按最优调度策略[3，（4，3）]连续输入 8 个任务时，流水线的实际吞吐率为：
TP = 8/[（3 + 4 + 3 + 4 + 3 + 4 + 3 + 9）△t] = 0.24/△t
第四章习题
4.17 在一个采用组相联映象方式的 Cache 存储系统中，主存由 B0～B7 共 8 块组成，
Cache 有 2 组，每组 2 块，每块大小为 16B。在一个程序执行过程中，访存的主存块地址流
为：B6，B2，B4，B1，B4，B6，B3，B0，B4，B5，B7，B3。
(1)写出主存地址的格式，并标出各字段的长度。
(2)写出 Cache 地址的格式，并标出各字段的长度。
(3)指出主存与 Cache 之间各个块的映象关系。
(4)若 Cache 的 4 个块号为 C0、C1、C2 和 C3，列出程序执行过程中的 Cache 块地址流。
(5)若采用 FIFO 替换算法，计算 Cache 的块命中率。
(6)若采用 LRU 替换算法，计算 Cache 的块命中率。
(7)若改为全相联映象方式，再做(5)和(6)。
(8)若在程序执行过程中，每从主存装入一块到 Cache，平均要对这个块访问 16 次，计
算在这种情况下的 Cache 命中率。
解：（1）（2）采用组相联映象时，主存和 Cache 地址的格式分别为：
区号 E
区内组号 G 主存组内块号 B 块内地址 W
组号 g
组内块号 b
块内地址 w
主存按 Cache 的大小分区，现主存有 8 个块，Cache 有 2×2=4 个块，则主存分为 8/4=2
个区，区号 E 的长度为 1 位。又每区有 2 个组，则组号 G、g 的长度都为 1 位。而每组有 2
个块，则块号 B、b 的长度又都为 1 位。每块大小为 16 个存储字，故块内地址 W、w 的长度
都为 4 位。
（3）根据组相联映象的规则，主存块 0～7 与 Cache 块 0～3 之间的映象关系为：主存
块 0、1、4、5 与 Cache 块 0、1 之间全相联，主存块 2、3、6、7 与 Cache 块 2、3 之间全相
联。
（4）根据组相联映象的规则，该主存块地址流相应的一种 Cache 块地址流如下表所示
（组内替换算法为 FIFO）。
2
B2
C3
时间： 1
主存块地址流： B6
Cache 块地址流：C2
3
B4
C0
4
B1
C1
5
B4
C0
6
B6
C2
7
B3
C2
8
B0
C0
9
B4
C0
10
B5
C0
11
B7
C3
12
B3
C2
（5）组内替换算法采用 FIFO 时，Cache 块 0～3 的使用过程如下表所示。
4
6*
2
4*
1
6*
2
4*
1
6*
2
4*
1
6*
2
4*
1
3
2*
0
1*
3
2*
0*
4
3
2*
5
4*
3
2*
5
4*
3*
7
5
4*
3*
7
6
6*
2
时间： 1
主存块地址流： B6
2
B2
3
B4
4
B1
5
B4
6
B6
7
B3
8
B0
9
B4
10
11
B5 B7
12
B3
Cache 块 0
Cache 块 1
4
6
6*
6*
4*
1
6*
4
1*
6*
2
2
2
2
4
1*
6
2*
4
1*
6*
3
4*
0
6*
3
4
0*
6*
3
4*
5
6*
3
4*
4*
5
7
5
7
3*
3*
Cache 块 2
Cache 块 3
可见命中三次，Cache 块命中率为 Hi = 3/12 = 0.25。
（6）组内替换算法采用 LRU 时，Cache 块 0～3 的使用过程如下表所示。
命中 命中
命中
6
6
2
6
2
4
6*
6*
6*
2
4
1
2
4
1
2
4
1
3
2*
4
1
3
0
3
0
4*
4*
3
0
5
1
1
1*
3*
3*
0
5
7
0
5
7
时间： 1
主存块地址流： B6
2
B2
4
3
B4 B1
5
B4
6
B6
7
B3
8
B0
9
B4
10
B5
11
B7
12
B3
Cache 块 0
Cache 块 1
Cache 块 2
Cache 块 3
命中 命中
命中
命中
可见命中四次，Cache 块命中率为 Hi = 4/12 = 0.33。
（7）全相联映象的规则是主存块 0～7 可装入 Cache 块 0～3 的任一块上。
当替换算法采用 FIFO 时，Cache 块 0～3 的使用过程如下表所示。
时间： 1
主存块地址流： B6
2
B2
3
B4
4
B1
5
B4
6
B6
7
B3
8
B0
9
B4
10
11
B5 B7
12
B3
Cache 块 0
Cache 块 1
Cache 块 2
Cache 块 3
命中 命中
命中
命中
可见命中四次，Cache 块命中率为 Hi = 4/12 = 0.33。
当替换算法采用 LRU 时，Cache 块 0～3 的使用过程如下表所示。
时间： 1
主存块地址流： B6
2
B2
3
B4
4
B1
5
B4
6
B6
7
B3
8
B0
9
B4
11
10
B5 B7
12
B3
Cache 块 0
Cache 块 1
Cache 块 2
Cache 块 3
可见命中三次，Cache 块命中率为 Hi = 3/12 = 0.25。
（8）当命中三次时，Cache 的命中率为 Hi = （12×16-9）/（12×16）≈1，当命中四
次时，Cache 的命中率为 Hi = （12×16-8）/（12×16）≈1。
命中 命中
命中
4.18 在某采用全相联映象、相联目录表实现地址变换 Cache 存储器中，Cache 的容
量是 2cB，主存是由 m 个存储体组成的低位交叉访问存储器，主存总容量是 2MB，每一个存储
体的字长是 w 位，。
(1)画出地址变换图。
(2)写出主存地址和 Cache 地址的格式，并标出各字段的长度。
(3)说明目录表的行数、相联比较的位数和目录表的宽度。
解：（1）
主存地址
主存块号 B
块内地址 W
Cache 地址
Cache 块号 b
块内地址 W
命中
6*
6*
6
2
4
1
2
4
1
2*
3
Cache 块号 b
4
4*
4
1
1*
0
3
4
0
…
6
b
3
6
6*
…
5
1
3*
有效位
4
0
5
7
4
5
7
4*
0*
3
录表
个字
用 全 相 联 映
Cache 地址的
6
6
…
6
B
2
4
2
主存块号 B
目
共 有 Cb
（2）采
象时，主存和
格式分别为：
主存块号 B
块内地址 W
组内块号 b
块内地址 w
主存和 Cache 单元数分别为：8×2M/w、8×2c/w，相应的地址长度分别为：
log2（8×2M/w）=M+3-log2w、log2（2c/w）=C+3-log2w。
块的大小为 m 个存储字，则主存和 Cache 的块内地址长度均为：log2m，所以主存和 Cache
的块号长度分别为：（M+3-log2w）-log2m = M+3-log2wm、（C+3-log2w）-log2m = C+3-log2wm。
（3）相联目录表的行数为 Cache 的块数，即 Cb=2（C+3-log2wm）=2C+3/wm；相联比较的位数为
主存块号长度，即 M+3-log2wm；目录表的宽度（位数）为主存块号长度、Cache 块号长度和
有效位的和，即 M+3-log2wm + C+3-log2wm +1= M+C+6-2 log2wm +1（有效位一位）。
第五章习题
5.10 设 16 个处理器编号分别为 0、1、5.10……、15，要用单级互连网络，当互连函数分
别为：
（2）PM+3
（3）Shuffle
（4）Shuffle（Shuffle）
（1）Cube3
时，第 13 号处理器分别与哪一个处理器相连?
解：（1）因为 Cube3（X3X2X1X0）=X3X2X1X0
（2）因为 PM+3 = X + 23 MOD N
（3）因为 Shuffle（X3X2X1X0）=X2X1X0X3 所以 13 → Shuffle（1101）=1011 → 11
（4）因为 Shuffle（Shuffle（X3X2X1X0））= Shuffle（X2X1X0X3）= X1X0X3X2
所以 13 → Cube3（1101）=0101 → 5
所以 13 →PM+3（13）= 5
所以 13 → Shuffle（Shuffle（1101））= Shuffle（1011）= 0111 → 7
5.13 在编号分别为 0，1，2，……，9 的 16 个处理器之间，要求按下列配对通信：
(B、1)，(8、2)，(7、D)，(6、C)，(E、4)，(A、0)，(9、3)，(5、F)。试选择所用互
连网络类型、控制方式，并画出该互连网络的拓扑结构和各级的交换开关状态图。
解：16 个处理机通过 N = 16 的互连网络互联，通信配对连接的二进制编号为：
(0、A)：0000---1010
(1、B)：0001---1011
(2、8)：0010---1000
(3、9)：0011---1001
(4、E)：0100---1110
(5、F)：0101---1111
(6、C)：0110---1100
(7、D)：0111---1101
(8、2)：1000---0010
(9、3)：1001---0011
(A、0)：1010---0000
(B、1)：1011---0001
(C、6)：1100---0110
(D、7)：1101---0111
(E、4)：1110---0100
(F、5)：1111---0101
显然要求互连网络实现的互联函数为 f（X3 X2 X1 X0）= X3X2X1X0，为多重方体置换。
N = 16 的 STARAN 网络在级控方式下实现的是方体置换，且当级控信号为 F = f3f2f1f0 =
1010 时，实现的互联函数是 Cube3（Cube1（X3 X2 X1 X0））= X3X2X1X0。
所以采用 N = 16 的 STARAN 网络在级控方式且级控信号 F = 1010 时，可实现要求配对
通信。
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
