计算机系统结构第1-8章部分作业答案

第一章

1.6 某台主频为400MHz的计算机执行标准测试程序，程序中指令类型、执行数量和平均时钟周期数如下：

指令类型 整数 数据传送 浮点 分支 指令执行数量 45000 75000 8000 1500 平均时钟周期数 1 2 4 2 求该计算机的有效CPI、MIPS和程序执行时间。 解：（1）CPI ＝(45000×1＋75000×2＋8000×4＋1500×2) / 129500＝1.776 (或

460259)

5180259（2）MIPS速率＝f/ CPI ＝400/1.776 ＝225.225MIPS (或MIPS)

（3）程序执行时间= (45000×1＋75000×2＋8000×4＋1500×2)／400=575?s

1.9 假设某应用程序中有4类操作，通过改进，各操作获得不同的性能提高。具体数据如下表所示： 操作类型 操作1 操作2 操作3 操作4 程序中的数量 （百万条指令） 10 30 35 15 改进前的执行时间 （周期） 2 20 10 4 改进后的执行时间 （周期） 1 15 3 1 （1）改进后，各类操作的加速比分别是多少？ （2）各类操作单独改进后，程序获得的加速比分别是多少？ （3）4类操作均改进后，整个程序的加速比是多少？ 解：根据Amdahl定律Sn 操作类型 操作1 操作2 操作3 操作4 各类操作的指令条数在程序中所占的比例Fi 11.1% 33.3% 38.9% 16.7% 各类操作的加速比Si 2 1.33 3.33 4 各类操作单独改进后，程序获得的加速比 1.06 1.09 1.37 1.14 ?1(1?Fe)?FeSe可

4类操作均改进后，整个程序的加速比：

Sn?(1?1?Fi)??FiSi?2.16

1.10 第二章

变长编码，哈夫曼编码

第三章

3.12 有一条指令流水线如下所示：

1 50ns 2 50ns 3 100ns 4 200ns

（1）求连续输入10条指令的情况下，该流水线的实际吞吐率和效率。

（2）该流水线的瓶颈在哪一段？请采用两种不同的措施消除此瓶颈。对于你所给出的两种新的流水线，连续输入10条指令时，其实际吞吐率和效率各是多少？ 解：

（1）本题主要考察对各功能段用时不等的线性流水线的性能计算公式的掌握情况。

kT流水???ti?1i?(n?1)?tmax?(50?50?100?200)?9?200 ?2200(ns)TP?n?1(ns?1T流水k220)

?E?TP?i?1?tik?TP?4004?511?45.45%

注意：对于公式不能死记硬背，需要充分理解，注意公式的适用条件。 （2）瓶颈在3、4段。

?

变成八级流水线（细分瓶颈段方法）

è?150nsk250ns3_150ns3_250ns4_150ns4_450ns3?

T流水??i?1?ti?(n?1)?tmax

?50?8?9?50?850(ns)TP?nT流水k?185(ns?1)

??tiE?TP?i?1k?TP?4008?1017?58.82%

? 重复设置瓶颈段方法

1 2 3-2 4-3 4-4 4-1 3-1 4-2 Stage4_44_34_24_13_23_12111223134452356671457889679101025891043697108Time850ns

TP?nT流水?185(ns?1)

E?400?10850?8?1017?58.82%

3.13 有一个流水线由4段组成，其中每当流过第三段时，总要在该段循环一次，然后才能流到第4段。如果每段经过一次所需的时间都是△t，问：

（1）当在流水线的输入端连续地每△t时间输入一个任务时，该流水线会发生什么情况？ （2）此流水线的最大吞吐率为多少？如果每2△t输入一个任务，连续处理10个任务时，其实际吞吐率和效率是多少？

（3）当每段时间不变时，如何提高流水线的吞吐率？人连续处理10个任务时，其吞吐率提高多少？

解：

（1）会发生流水线阻塞情况。

（2）当任务流过第三段时要在该段循环一次，相当于要占用第三段2△t时间，则该流水线可看成是具有瓶颈段的线性流水线，瓶颈段即第三段，所需时间为2△t。每2△t输入一个任务，连续处理10个任务的时空图如下：

Stage43211121112322342334534456455675667867789788910899109101010Time23?t

则：

TPmax?12?t?104T流水?23?tTp?nT流水23?t92?54.35%

E?TP?5?t?50

（3）重复设置部件。重复的部件可并联在流水线上，也可串联于流水线中。如下图所示：

t 3_1 1 t 2 t 3_2 t 4 t

3_2t4t

1t2t3_1t

采用并联方式时的时空图如下：

Stage43_23_1211121232134123452435634567465785678968791078910810991010Time14?t

TP?nT流水?1014??t57?t23?t?57??t

吞吐率提高倍数＝

10＝1.64

3.14 有一条静态多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第3段的时间为2△t，其余各段的时间均为△t，而且流水线的输出可以直接返回输入端或暂存

4于相应的流水线寄存器中。现在该流水线上计算?(Ai?Bi)，画出时空图，并计算其吞吐

i?1率、加速比和效率。

1 △t 2 △t 2△t 3 △t 4 △t 5 解：此题容易出的问题是忽略静态流水线的特点，当加法任务流入流水线后紧跟着启动乘法任务。正确的做法是当所有加法任务完成从流水线流出后再启动乘法任务，同时还应注意到流水线中的第三段所用时间为2△t。 （1）任务分析

（2）画时空图 1 1 2 1 2 3 1 2 3 4 2 3 4 3 4 4 5 5 6 5 6 6 7 7 7 18△t （3）计算流水线性能 吞吐率：Tp?nT?718?t

加速比：Sp?T串行T流水?4?5?t?3?3t18?t?29182990

效率： E?实际占用面积时空区总面积?4?5?t?3?3t5?18?t?

3.18 在CRAY-l机器上，按照链接方式执行下述4条向量指令(括号中给出了相应功能部件时间)，如果向量寄存器和功能部件之间的数据传送需要1拍，试求此链接流水线的通过时间是多少拍？如果向量长度为 64，则需多少拍才能得到全部结果。

V0←存储器 V2←V0＋V1 V3←V2＜A3 V5←V3∧V4

（从存储器中取数：７拍） （向量加：３拍）

（按(A3)左移：４拍） （向量逻辑乘：２拍）

远的是几号处理机？

解：

（1）共有32台处理机，因此用log232 = 5比特表示各处理器编号。

E2(12) 十进制 = E2(01100) 二进制=（01000）二进制= (8) 十进制

S(8) 十进制 = S（01000）二进制= （10000）二进制= (16) 十进制 B(9) 十进制 = B（01001）二进制= （11000）二进制= (24) 十进制

PM2I+3(28) = (28 +23) mod 32 = 4 E0(S(4))十进制 = E0(S（00100））二进制= E0（01000）= （01001）二进制= (9) 十进制 S(E0(18)) 十进制 = S (E0（10010））二进制=S（10011）= （00111）二进制= (7) 十进制

（2）2个结点的均匀洗牌交换网的网络直径是2n-1，32个结点的均匀洗牌交换网的网络直径为9。

从5号处理机发送数据到7号处理机，最短路径要经过6步：

000 00101???00100???01000???01001???10010???10011???00111n

ESESES（3）网络直径是3，节点度是9，与2号处理机距离最远的是13、15、21、23号处理机。.

第八章 多处理机

8.1 解释下列术语（不要求写在作业本上，但应作为复习内容）

集中式共享多处理机 分布式共享多处理机 通信延迟 计算/通信比 监听协议 目录协议 写作废协议 写更新协议

答：答案略

8.2 一个具有32个处理器的多处理机，对远程存储器访问时间为2000 ns。除了通信以外，假设所有其他访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器的时钟周期时间是10ns，假设指令基本的CPI为1.0（设所有访存均命中局部存储器）。对于下述两种情况：

（1）没有远程访问。

（2）有0.5%的指令需要远程访问。 试问前者比后者快多少? 解：

已知远程访问率p=0.5%，远程访问时间t=2000ns，时钟周期时间T=10ns，则 远程访问开销C=t/T = 2000ns/10ns = 200 个时钟周期 则有0.5%远程访问的机器的实际CPI2为： CPI2= CPI1 + p×C = 1.0 + 0.5%×200 = 2.0

只有局部访问的机器的基本CPI1 =1.0 ，故 CPI2/CPI1 = 2.0/1.0 = 2(倍)

因此，没有远程访问状态下的机器速度是有0.5%远程访问的机器速度的2倍。

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