计算机系统结构作业题解 第1章 作1.2 如有一个经解释实现的计算机，可以按功能划分成4级。每一级为了执行一条指令需要下一级的N条指令解释。若执行第一级的一条指令需K(ns)时间，那么执行第2、3、4级的一条指令各需要用多少时间(ns)? 解：∵第二级的一条指令需第1级的N条指令解释 ∴第二级的一条指令执行时间为NKns；

Presentation on theme: "计算机系统结构作业题解 第1章 作1.2 如有一个经解释实现的计算机，可以按功能划分成4级。每一级为了执行一条指令需要下一级的N条指令解释。若执行第一级的一条指令需K(ns)时间，那么执行第2、3、4级的一条指令各需要用多少时间(ns)? 解：∵第二级的一条指令需第1级的N条指令解释 ∴第二级的一条指令执行时间为NKns；"— Presentation transcript:

1 计算机系统结构作业题解 第1章 作1.2 如有一个经解释实现的计算机，可以按功能划分成4级。每一级为了执行一条指令需要下一级的N条指令解释。若执行第一级的一条指令需K(ns)时间，那么执行第2、3、4级的一条指令各需要用多少时间(ns)? 解：∵第二级的一条指令需第1级的N条指令解释 ∴第二级的一条指令执行时间为NKns； 第三级的一条指令执行时间为N2Kns； 第四级的一条指令执行时间为N3Kns。

2 本题有两个问题应特别注意：第一个问题是“上一级”与“下一级”的关系，即哪是上一级，哪是下一级？在图1
本题有两个问题应特别注意：第一个问题是“上一级”与“下一级”的关系，即哪是上一级，哪是下一级？在图1.1中第3级是第2级的“上一级”，第1级又是第2级的“下一级”。第二个问题是该计算机是一个“经解释实现的计算机”，上一级的程序在下一级上实现不是经翻译完成，只能是解释。 上级 第4级 一条指令 第3级 N条指令解释 第2级 N2条指令解释 第1级 N3条指令解释 下级

3 作1.3 有一个计算机系统可按功能划分成4级，各级的指令都不相同，每一级的指令都比其下一圾的指令在效能上强M倍，即第i级的一条指令能完成第i-1级的M条指令的计算量。现若需第i级的N条指令解释第i+1级的一条指令，而有一段第1级的程序需要运行Ks，问在第2、3和4级上的一段等效程序各需要运行多长时间(s)? 解： 第2级上的一段等效程序运行时间为： 第3级上的一段等效程序运行时间为： 第4级上的一段等效程序运行时间为：

4 作1.7 从机器（汇编）语言程序员看，哪些对应用程序员透明？
指令地址寄存器，指令缓冲器，时标发生器，条件码寄存器，乘法器，主存地址寄存器，磁盘外设，先行进位链，移位器，通用寄存器，中断字寄存器。 答：对机器语言程序员透明，指的是这些器件是机器语言程序员不可修改、不可控制。因此指令缓冲器，时标发生器，乘法器，先行进位链，移位器。

5 作1.6 什么是透明性概念?对计算机系统结构，下列哪些是透明的?哪些是不透明的?
存贮器的模m交叉存取；浮点数据表示；I／O系统是采用通道方式还是外围处理机方式；数据总线宽度；字符行运算指令；阵列运算部件；通道是采用结合型的还是独立型的；PDP一1l系列中的单总线结构；访问方式保护；程序性中断；串行、重叠还是流水控制方式；堆栈指令；存贮嚣最小编址单位；Cache存贮器。 分析：有关系统结构属性所包括的内容，对系统结构都不透明。

6 对于计算机系统结构透明的是：存储器的模m交叉存取、数据总线宽度、阵列运算部件、通道是采用结合型还是独立型、PDP-11系列的单总线结构、串行、重叠还是流水控制方式、Cache存储器。
对于计算机系统结构不透明的是：浮点数据表示、 I/O系统是采用通道方式还是外围处理机方式、字符型运算指令、访问方式保护、程序性中断、堆栈指令、存储器最小编址单位。

7 例1.1 假设将某系统的某一部件的处理速度加快到10倍，但该部件的原处理时间仅为整个运行时间的40%，则采用加快措施后能使整个系统的性能提高多少？
解：由题意可知 fe=0.4, re=10, 根据Amdahl定律

8 作1.13 假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为90％，则采用Cache后，能使整个存储系统获得多高的加速比？
解：fe=0.9 ，re=5

9 解 (1) 作1.11 某工作站采用时钟频率为15MHz、处理速率为 10MIPS的处理机来执行一个巳知混合程序。假定每次
存储器存取为1周期延迟、试问： (1)  此计算机的有效CPI是多少? (2) 假定将处理机的时钟提高到30MHz，但存储器子 系统速率不变。这样，每次存储器存取需要两个时钟 周期。如果30％指令每条只需要一次存储存取，而另 外5％每条需要两次存储存取，还假定已知混合程序 的指令数不变，并与原工作站兼容，试求改进后的处 理机性能。 解 (1)

10 (2) 依题意可知：30%的指令需要一次存储存取，则
这些指令在处理器提高时钟频率之后需要增加1个时 钟周期；另外5%的指令需要增加2个时钟周期。 改进后性能提高情况可用CPU时间之比表示：

11 作1.15 假定利用增加向量模块来提高计算机的运算速度。计算机处理向量的速度比其通常的运算要快20倍，将可用向量处理部分所花费的时间占总时间的百分比称为可向量化百分比。
（1）求出加速比S和向量化百分比之间的关系式。 （2）当要得到加速比为2时的可向量化百分比F为多少？ （3）为了获得在向量模式所得到的最大加速比的一半，可向量化百分比F为多少？

12 解（1）： 由Amdahl定律知 (1) (2) 由（1）式有

13 (3) 由题意可知

14 题1.1 某计算机系统同时采用两种措施改进性能，使得两个功能部件的性能分别提高到原来的re1倍和re2 ，这两个部件在运行时使用的时间比例分别为fe1和fe2 。试分析系统性能提高的总体加速比。
解:

15 例1.2 用一台4OMHz处理机执行标准测试程序，它含的混合指令数和相应所需的时钟周期数如下：
指令类型 指令条数 时钟周期数 整数运算 数据传送 浮点运算 控制传送 求有效CPI、MIPS速率和程序的执行时间。

16 解：依题意可知 IN=105条，n=4

17 题1.2 设有两台机器A和B，对条件转移采用不同的方法。CPUA采用比较指令和条件转移指令处理方法，若条件转移指令占总执行指令数的20％，比较指令也占20％。CPUB采用比较和条件转移指令合一的方法，占执行指令数的20％。若规定两台机器执行条件转移指令需2T，其它指令需1T。CPUB的条件转移指令比CPUA慢25％，现比较CPUA合和CPUB哪个工作速度更快？

18 解: CPIA=0.2×2＋0.8×1＝1.2 CPUA时间＝ICA×CPIA×TA＝1.2TA×ICA ICA是CPUA的指令条数，由于CPUB无比较指令，因此ICB=0.8 ICA，若ICA=100，则ICB=80 ，而CPUB的条件转移指令仍是20条，所以占比例为20/80＝0.25＝25％ CPIB=0.25×2＋0.75×1＝1.25 又因为CPUB的TB比CPUA的TA慢25%，所以TB=1.25TA CPUB=ICB×CPIB×TB＝0.8ICA×1.25×1.25TA ＝1.25TA×ICA 可见，CPUA时间<CPUB时间，CPUA比CPUB工作速度快。

19 上例中，TB只比TA 慢10%，则哪个CPU更快些？
解： TB＝1.1TA CPUB时间＝0.8ICA×1.25×1.1TA ＝1.1TA×ICA 因此CPUB时间<CPUA时间，则CPUB更快些。

20 题1.3 某向量计算机系统中，标量指令的平均CPI是1，向量运算指令的平均CPI是64，系统加快向量部件的速度后使向量运算速度提高到原来的2倍，某一测试程序执行时的向量运算指令数量占全部指令数的10％，问计算机系统运行这个测试程序的整体性能比原来提高多少？ 解：

21 (1)计算在单处理机上用上述踪数据运行程序的平均CPI。 (2)根据(1)所得CPI，计算相应的MIPS 速率。
作1.12 假设在一台40MHz处理机上运行 条指令的目标代码，程序主要由四种指令组成。根据程序跟踪实验结果，已知指令混合比和每种指令所需的指令数如下： 指令类型 CPI 指令混合百分比 算术和逻辑运算 1 60% Cache命中的加载/存储 2 18% 转移 4 12% Cache失效时访问主存 8 10% (1)计算在单处理机上用上述踪数据运行程序的平均CPI。 (2)根据(1)所得CPI，计算相应的MIPS 速率。

22 解：依题意可知 IN=2×105条，n=4，

23 第2章 题2.1 一种浮点数有1位符号位，阶码为7位移码，尾数8位与符号位一起采用原码的规格化表示，基数为2，该浮点数可表示的最大数为 ，最大数与最接近它的数据（次最大数）的差值为 ，可表示的最小数为 ，最小数与最接近它的正数（次最小数）的差值为 。 解： 最大数 最小正数 最大数与次大数的差值 最小正数与次小正数的差值

24 解：阶码为7位移码表示，1位符号位，尾数8位，原码规格化表示，基数为2，其格式为：
阶码6位 q p 尾符 尾数8位 阶符 浮点数N 尾数基值 rm ＝2（二进制） 阶码的基值re ＝2，尾数长度p=8 (不包括符号位），阶码长度q=6(不包括符号位）， 规格化表示的正数的范围：

25 规格化表示的正数的范围： 最小尾数为 最大尾数为 最大阶码为 最小阶码为 可表示的最大正浮点数为 可表示的最小正浮点数为 可表示的正阶、正尾规格化数的个数为

26 规格化表示的负数的范围： 最小尾数（原码）为 最大尾数为 最大阶码为 最小阶码为 可表示的最大负浮点数为 可表示的最小负浮点数为

27 例2.1 某指令系统各指令使用频度如下： I1 I2 I3 I4 I5 I6 I7
例2.1 某指令系统各指令使用频度如下： I1 I2 I3 I4 I5 I6 I7 1.Huffman编码 1.00 1 0.60 1 0.30 1 0.15 1 0.06 0.09 1 1 0.03 0.03 0.04 0.05 0.15 0.30 0.40 I I6 I I I I I1

28 由此可得到哈夫曼编码如下： 平均码长 L=0.4*1+0.3*2+0.15*3+0.05*5+0.04*5
I1: I2: I3: I4: 11100 I5: I6: I7: 11111 平均码长 L=0.4*1+0.3*2+0.15*3+0.05*5+0.04*5 +0.03*5+0.03*5 = 2.20位 信息冗余量R=( )/2.20=1.36% 指令长度个数=4

29 2.扩展哈夫曼编码 I1, I2, I3 用两位: 00, 01, 10 I4, I5, I6, I7 用四位: 1100, 1101, 1110, 1111 L=( )*2+( )*4 = 2.30位 信息冗余量=( )/2.30=0.0565=5.65%

30 操作码的扩展（等长扩展） 4 5 0.03 I7 I6 0.04 I5 0.05 I4 2 1 0 3 0.15 I3 0 1 1 0 0.30 I2 0 0 1 0.40 I1 OP长度 li huffman扩展编码 操作码OP 使用哈夫曼编码 频 度 （Pi） 指 令 平均码长：

31 因每段指令数基本相同，故可采用等长扩展(4-8-12位)， 保留特征码的每段指令数相同(15-15-15)方法。结果如图所示；
例2.2 指令系统共有42种指令，前15种使用频率平均为0.05，中间13种使用频率平均为0.015，最后14种使用频率平均为0.004。如何编码？ 0000 ： 种 1110 ： ： 种 ： ： ： 种 解：因频率分布有三种，故码长可有三种； 因每段指令数基本相同，故可采用等长扩展(4-8-12位)， 保留特征码的每段指令数相同( )方法。结果如图所示； 结果：采用 扩展方法，最后一种编码用于扩展，每段0000～1110用于编码，1111用于扩展。

32 例2. 3 指令系统共有74种指令，前4种使用频率平均为0. 12，中间15种使用频率平均为0. 02，最后55种使用频率平均为0
例2.3 指令系统共有74种指令，前4种使用频率平均为0.12，中间15种使用频率平均为0.02，最后55种使用频率平均为0.004。如何编码？ 解：同上例方法，码长可有三种； 因每段指令数成比例(1：4)，故可采用等长扩展方法(3-6-9位)扩展，保留标志位方法，结果如图所示； 0xx 种 1xx 0xx 种 1xx 1xx 0xx 64种 结果：采用 扩展方法，编码第一位用于扩展，每段0XX用于编码，1XX用于扩展。 平均码长 =0.12*4*3+0.02*15* *55*9=5.22；

33 解：同上例方法，码长可有三种；因每段指令数比例为1：2：5，故不可采用等长扩展，采用不等长编码( 4-6-10位)较能减少平均码长。
例2.4 指令系统共有78种指令，前10种使用频率平均为0.049，中间18种使用频率平均为0.02，最后50种使用频率平均为0.003。如何编码？ 解：同上例方法，码长可有三种；因每段指令数比例为1：2：5，故不可采用等长扩展，采用不等长编码( 位)较能减少平均码长。 第一种采用4位编码中前10种(0000~1001)； 第二种采用第一种频率编码中的后5种编码(1010~1110)与扩展的2位共20种编码； 第三种采用第一种频率编码中的最后一种(1111)与扩展的6位共64种编码。 0000 ： 10种 1001 ： ： 20种 ： ： ： 种

34 解：p=6、m=48时，在非负阶、规格化、正尾数情况下，尾基rm=2、8、16时的各个参数的计算结果如下表所示。
作2.3 设某机阶码6位、尾数48位，阶符和数符不在其内，当尾数分别以2、8、16为基时，在非负阶、正尾数、规格化数情况下，求出其最小阶、最大阶、阶的个数、最小尾数值、最大尾数值、可表示的最小值和最大值及可表示的规格化数的总个数 解：p=6、m=48时，在非负阶、规格化、正尾数情况下，尾基rm=2、8、16时的各个参数的计算结果如下表所示。

35 非负阶、正尾数、规格化 最小阶值 最大阶值 阶的个数 最小值 最大值 数的个数 尾基rm(p=6位，m=48位) 2(48位) 8(16位)
16(12位) 最小阶值 最大阶值 2p-1 63 阶的个数 2p 64 尾数最小值 1/2 1/8 1/16 尾数最大值 1-2-48 1-8-16 最小值 最大值 263· (1-2-48)) 863 · (1-8-16) 1663 · ( ) 数的个数 253 7 ·251 15 ·250

36 作2.15 某模型机有9条指令，其使用频率为： ADD（加）　　　　30%　　　　SUB（减）　　　24% JOM（按负转移）　6%　　　　 STO（存）　　　7% JMP（转移）　　　7%　 　　　SHR（右移）　　2% CIL（循环左移）　3%　　　　 CLA（清加）　　20% STP（停机）　　　1% 要求有两种指令字长，都按双操作数指令格式编,采用扩展操作码，并限制只能有两种操作码码长。设该机有若干个通用寄存器，主存为16位宽，按字节编址，采用整数边界存贮，任何指令都在一个主存周期中取得，短指令为寄存器－寄存器型，长指令为寄存器－主存型，主存地址应能变址寻址。

37 解：(1) Huffman树的形式如图所示。
0.56 1 1 0.26 1 0.12 1 0.06 1 0.44 0.03 0.14 1 1 1 0.01 0.02 0.03 0.06 0.07 0.07 0.20 0.24 0.30

38 由上图可得到的Huffman编码为： ADD(加) 30% 01 SUB(减) 24% 11 CLA(清加) 20% 10
JOM(按负转移) 6% STO(存) % JMP(转移) % CIL(循环左移) 3% SHR(右移) % STP(停机) % 因此，操作码的平均码长为：

39 (2) 采用2-5扩展的操作码编码为： ADD(加) 30% 00 SUB(减) 24% 01 CLA(清加) 20% 10
JOM(按负转移) 6% STO(存) % JMP(转移) % SHR(右移) % CIL(循环左移) 3% STP(停机) % 因此，操作码的平均码长为：

40 (3) 该机允许使用的可编址的通用寄存器个数为23=8个 (4) 短指令为寄存器-寄存器型，格式如下：
OP(2位) R1(3位) R2(3位) 长指令为寄存器-主存型，格式如下： OP(5位) R1(3位) X(2位) 相对位移d(6位) (5) 访主存操作数地址寻址的最大相对位移量为64个字节(-32~+31个字节)

41 例2.5 若某机要求有：三地址指令4条，单地址指令192条，零地址指令16条。设指令字长为12位，每个地址码长3位。问能否以扩展操作码为其编码？

42 解： 1. 三种指令格式字如下： 000 xxx xxx xxx ⋮ 011 xxx xxx xxx 000 000 xxx
解： 1. 三种指令格式字如下： 3 3 3 3 OPC A1 A2 A3 000 xxx xxx xxx ⋮ 011 xxx xxx xxx xxx xxx 三地址4条 三地址指令4条 OPC A1 一地址192条 单地址指令192条 OPC 零地址16条 零地址指令16条

43 2.某机指令字长16位。设有单地址指令和双地址指令两类。若每个地址字段为6位，且双地址指令有X条。问单地址指令最多可有多少条？
解：二种指令格式字如下： OPC A A2 OPC A1 10位 位 6位 4位 由于双地址指令有X条，单地址指令最多可有：

44 作2.16 某处理机的指令字长为16位，有双地址指令、单地址指令和零地址指令三类，并假设每个地址字段的长度为16位。
（1）如果双地址指令有15条，单地址和零地址指令的条数基本相同，问单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。 （2）如果三类指令的比例为1：9：9，问双地址指令、单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。

45 解： （1）双地址指令15条，地址码： 0000～1110 单地址指令26－1＝63条，地址码： 零地址指令64条，地址码： （2）双地址指令14条，地址码：0000～1101 单地址指令26×2－2＝126条， 零地址指令128条，地址码：

46 第3章 作3.2 设一个任务在计算机中的处理时间为50秒，CPU处理时间为30秒，I/O处理时间为20秒。如果将CPU的处理速度提高4倍，则总的处理时间将是多少？ 解：如使CPU的速度增加4倍,则CPU的处理时间为: Tcpu=30/4=7.5s 则总的处理时间为:T=Tcpu+Ti/o=7.5+20=27.5s

47 题3.1 假设一台计算机的I/O处理占10％，当其CPU性能改变，而I/O性能保持不变，系统总体性能会出现什么变化？
（1－10％）/10+10%=0.19 即整机性能只能提高约5倍，差不多有50％的CPU性能浪费在I/O上。 如果CPU的性能提高100倍，则程序的计算时间为 （1－10％）/100+10%=0.109 而整机性能只能提高约10倍，表示有90％的性能浪费在I/O上了。

48 例3.1 某字节交叉多路通道连接6台设备，其数据传送速率如下表所示。
例3.1 某字节交叉多路通道连接6台设备，其数据传送速率如下表所示。 设备号 1 2 3 4 5 6 传送速率(B/ms) 50 40 25 10 二次请求的间隔时间(μS) (1)在上表中填出设备相应二次请求传送字节的间隔时间。 (2)当所有设备同时要传送数据时，求其对通道要求的总流量fbyte

49 (3)让通道以极限流量fmax.byte=fbyte的工作周期工作，通道的工作周期(即TS+TD的时间间隔)是多少？
(4)让通道中所挂设备速率越高的数据传送请求被响应的优先级越高。画出6台设备同时发送请求到下次同时发送请求期间里，通道响应和处理完各设备请求时刻的示意图。哪个设备丢失了信息？提出一种不丢失信息的解决办法。

50 解：(1) (2) 总容量 (3) 传送周期 TS+TD=1ms/200B=5μS 设备号 1 2 3 4 5 6 传送速率(B/ms)
50 40 25 10 二次请求的间隔时间(μS)  20 20  25  40  100  (2) 总容量 (3) 传送周期 TS+TD=1ms/200B=5μS 20us 1 2 3 4 5 6 6号设备丢失了一次数据

51 方法1：增加通道的最大流量，保证连接在通道上的所有设备的数据传送请求能够及时得到通道的响应
方法2：动态改变设备的优先级 方法3：增加一定数量的数据缓冲器，特别是对优先级比较低的设备

52 例3.2 印字机各占一个子通道，0号打印机、1号打印机和0号光电输入机合用一个子通道。假定数据传送期内高速印字机每隔25us发一个请求，低速打印机每隔150us发一个字节请求，光电输入机每隔800us发一个字节请求，则这5台设备要求通道的实际流量为多少？ 字节多路通道 0子通道 1子通道 2子通道 0号高速印字机 1号高速印字机 0号打印机 1号打印机 0号光电输入机

53 解：5台设备要求通道的数据流量为： 可将该通道设计成0.1MB/s，即所设计的工作周期为： 这样各设备的请求就能及时得到响应和处理，不会丢失信息。

54 优先级次序：0号印字机、1号印字机、0号打印机、1号打印机、0号光电机
通道工作周期 0us us us us 表示设备提出申请的时刻 表示通道处理完设备申请的时刻 优先级次序：0号印字机、1号印字机、0号打印机、1号打印机、0号光电机

55 例3.3 设通道在数据传送期中，选择设备需4.9μS，传送一个字节数据需0.lμS。
（2）若有A～E共5种高速设备，要求字节传送的间隔时间如下表所示，其时间单位为μS。若一次通信传送的字节数不少于1024个字节，问哪些设备可挂在此通道上？哪些则不能？ 设备 A B C D E 时间间隔(μS) 0.13 0.1 0.11 0.2 0.3

56 其中，n≥1024，应使select i ≤maxselect 由此可得出通道工作周期为：T≈0.1048(us)
解：(1)低速设备应接字节多路通道 n ＝250/5=50台，所以，n≤50台，即最多可接50台这种设备 (2)根据题意，此通道为选择通道 其中，n≥1024，应使select i ≤maxselect 由此可得出通道工作周期为：T≈0.1048(us) 所以，只有A、C、D、E可挂在此通道上，B则不行。

57 作3.2 设一个任务的处理时间为64秒，CPU在这期间始终忙于处理，I/O处理时间为36秒。为提高系统性能，有两种方案：使CPU的速度增加1倍，或者使CPU和I/O的处理速度同时增加1倍。计算这两种情况下的处理时间。 解：如使CPU的速度增加1倍,则CPU的处理时间为: Tcpu=64/2=32 则总的处理时间为:T=Tcpu+Ti/o-Toverlap ∵ Toverlap<=min{Tcpu ,Ti/o} ∴T>= =36 当两者速度同时增加1 倍时: Tcpu=64/2=32 Ti/o=18 则: T>= =32

58 作3.10 （1）字节多路通道、数组多路通道、选择通道，它们一般用什么数据宽度来进行通信？
（2）如果通道在数据传送期中选择设备需9.8us，传送一个字节数据需0.2 us，某低速设备每隔500 us发出一个字节数据传送请求，问至多可接几台这种低速设备？对于如下A~F6种高速设备，一次通信传送的字节数不少于1024个字节，问哪些设备可以挂在此通道上？哪些则不能？其中A~F设备每发一个字节数据传送请求的时间间隔分别为 设备 A B C D E F 发申请间隔（us） 0.2 0.25 0.5 0.19 0.4 0.21

59 解: （1） 字节通道的数据流量为： （2） 传送周期 TS+TD=3us＋2us=5μS

60 优先级次序：0号设备、1号设备、2号设备、3号设备
通道工作周期 （3）通道处理完成各设备第一次服务请求的时刻： 0号设备：5us，1号设备：10us ，2号设备：30 us，3号设备：丢失 表示设备提出申请的时刻 表示通道处理完设备申请的时刻 优先级次序：0号设备、1号设备、2号设备、3号设备

61 (4) 从时间关系图中看，这个字节通道不能正常工作，因为以现在的工作频率，不可能连接过多的设备。
（5）改进的措施： 1）增加此通道的工作频率； 2）改变设备的优先级； 3）增加一定数量的缓冲器，保存优先级低设备可能丢失的数据。

62 第4章 例4.1 假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为90％，则采用Cache后，能使整个存储系统获得多高的加速比？ 解：

63 例4.2 假设高速缓存Cache的访问周期为50ns，主存的访问周期为400ns ，且Cache被访问命中的概率为95％，则采用Cache后，能使整个存储系统等效的访问周期为多少？获得多高的加速比？
解：

64 例4.3 设某用户虚存共有8页, 主存有4页, 每页大小为1KB. 试根据页表计算出虚地址1023和6800的主存实地址。
虚页号 实页号 装入位 提示：注意页表中虚、 实页对应关系

65 解：页号与地址对应关系 每页首地址=页号X每页大小 第0页 0—1023 第1页 1024—2047 第2页 2048—3071 第3页
3072—4095 第4页 4096—5119 第5页 5120—6143 第6页 6144—7167 第7页 虚页号＝虚地址％1024 虚地址1023，虚页号为0，页内位移 为1023；根据虚页号查页表得知实页 号为3，且装入位为1。 主存实地址PA= =4095 虚地址6800，虚页号为6，页内位移 为656；根据虚页号查页表得知实页 号为0，且装入位为1。 主存实地址PA=0+656=656 每页首地址=页号X每页大小

66 解： 例4.4 虚存32页, 主存16页, 每页为1KB。某时刻已调入主存的实页与虚页对应如下: 虚页号 0 1 2 8
虚页号 实页号 求虚地址0A5CH和1A5CH对应的实地址。 主存实地址 查页表（已装入） 直接 d p 125CH 单用户的虚地址 P D 0A5CH 解：

67 解： 用户的虚页并未装入主存中，当执行该虚页程序时，找不到对应的实页。 P D 单用户的虚地址 1A5CH 页面失效，无对应的主存实地址。
1A5CH 查页表（未装入） 直接 页面失效，无对应的主存实地址。 用户的虚页并未装入主存中，当执行该虚页程序时，找不到对应的实页。

68 例4.5 虚拟存储器举例—IBM370/168 224 212=4K 212=4KB 15位 30位 64行 24+24位 用户数？
每个用户虚页数？ 每页大小？ 15位 30位 64行 相等比较位数？ 相等寄存器位数？ 快表行数？ 快表每行的位数？ 24+24位 如何减少散列冲突？ 快表为何采用两组？ 相等比较的作用？

69 例4.6 假若一计算机的主存储器按64块组织，块大小 为8个字，高速缓存有8块。试按下述要求画图 回答问题。 （1）画出全相联映像示意图、指定标记字段 和主存地址格式。 （2）画出直接映像示意图、指定标记字段和 主存地址格式。 （3）画出2路组相联映像示意图、指定标记字段

70 解： （1）全相联映像 ⋮ 标记6位的高速缓存 主存储器 主存地址 缓存地址 标记 （块号）标记（6位）字（3位） 行号（3位） 字（3位）
B7 B8 B9 ⋮ B1 B0 B56 B57 B63 主存储器 标记 b0 b1 b7 ⋮ ⋮ 标记6位的高速缓存 主存地址 （块号）标记（6位）字（3位） 缓存地址 行号（3位） 字（3位）

71 （2）直接映像 区0 ⋮ 标记3位的高速缓存 区7 主存储器 3位 3位 3位 主存地址 3位 3位 缓存地址 标记 ⋮ ⋮
B0 B1 区0 标记 ⋮ ⋮ B7 b0 b1 b7 ⋮ B8 ⋮ B9 ⋮ B56 ⋮ B57 标记3位的高速缓存 区7 ⋮ B63 主存储器 3位 3位 3位 主存地址 区号E（标记） 块号B 字W 3位 3位 缓存地址 行号L 字w

72 （3）2路组相联映像 标记4位的高速缓存 区0 ⋮ 区15 主存储器 4位 2位 3位 主存地址 2位 1位 3位 缓存地址 0组 1组
B0 B1 标记4位的高速缓存 区0 B2 B3 0组 1组 2组 3组 b0 b1 b7 b2 b3 b4 b5 b6 B4 B5 ⋮ ⋮ B60 B61 区15 B62 B63 主存储器 4位 2位 3位 主存地址 区号E（标记） 组号G 字W 2位 1位 3位 缓存地址 组号g 行号L 字w

73 作4.6 解： （1）由于虚地址中有2位表示段号、2位表示页号，所 以此地址空间共有22Ⅹ22=16个虚页。
段0 段1 段2 段3 访问方式 只读 可读/执行 可读/写/执 可读/写 虚页0 实页9 在辅存内 页表不在主存 实页14 虚页1 实页3 实页0 实页1 虚页2 实页15 实页6 虚页3 实页12 实页8 （2）根据上页表，题中所示操作的虚地址访问情况如下 其中，实地址=实页号Ⅹ页大小+页内位移。如下表第1行中， 实地址=3Ⅹ2048+1=6145

74 方式 段 页 页内位移 段失效 页失效 实页号 实地址 保护失效 取数 1 无 3 6145 10 2047 有 / 存数 4 6148 2 14 转移至此 100 8 16484 50 5 60 28732

75 作4.8 解： （1）∵可有1K个任务，短期内只有4个用户， ∴指示用户号的地址字段U=10位；ID=2位；
作4.8 解： （1）∵可有1K个任务，短期内只有4个用户， ∴指示用户号的地址字段U=10位；ID=2位； 又∵每个用户程序空间可达4096页，每页512B， ∴P=12, D=(9+3)=12位； 又∵主存地址长度为20位， ∴ 实页号p=20-12=8位。 （2）每个相联寄存器的相联比较位数为U=10位； （3）每个相联寄存器的总位数为U+ID=12位； （4）散列变换硬件的输入和输出位数为14位和4位； （5）每个相等比较器的位数为P+ID=12+2=14位； （6）快表的总容量为16×(12+2+8)×2=704（位）。

76 虚实地址经快表变换的逻辑示意图 10位 12位 多用户的虚地址 用户号U 虚页号P 页内位移D 34位 直接 8位 12位 U1 00
主存实地址 实页p 页内位移d U2 01 20位 U3 10 U3 11 14位 散列变换 相等？ 相等？ 4位 P+ID p P+ID p 16行

77 作4.12 解： 依题意可知，每块大小为4Ⅹ4=16B，用4位二进制表示。 采用4个外相等比较电路，指示块号用2位二进制表示。
作4.12 解： 依题意可知，每块大小为4Ⅹ4=16B，用4位二进制表示。 采用4个外相等比较电路，指示块号用2位二进制表示。 指示组号地址为10-2-4=4位。 又因为主存容量为256KB，主存总位数18位。所以， 指示区号的位数为18-10=8位。 地址对应关系如下： 区号E 组号Q 组内块号B 块内字W 组号q 组内块号b 块内字w 主存地址 Cache地址 8位 4位 2位

78 每个相等比较电路的位数：E+B=8+2=10位。
相联目录表如下： E+B b 16行 相联目录表行数：2q=24=16行； 每行总位数：E+B+b=8+2+2=12位； 每个相等比较电路的位数：E+B=8+2=10位。

79 题4.1 在一个Cache存储系统中， Cache的访问周期为10ns，主存储器的访问周期为60ns，每个数据在Cache中平均重复使用4次。当块大小为1个字节时，存储系统的访问效率只有0.5，现在要通过增加块大小，使存储系统的访问效率达到0.94。 （1）当存储系统的访问效率为0.5时，计算命中率和等效访问周期。 （2）为了使存储系统的访问效率达到0.94，命中率和等效访问周期应该提高到多少？ （3）为了使存储系统的访问效率从0.5提高到0.94，块的大小至少增加到几个字？

80 解:（1）当存储系统的访问效率为0.5时，由表达式
可求出命中率为 等效访问周期为 或由 得

81 （2）当存储系统的访问效率提高到0.94时，命中率
应该提高到H2 等效访问周期应提高为 或由 得

82 （3）为了使存储系统的访问效率由0.5提高到0.94， 块大小应为B个字。则有 在上式中代入相关参数，可求出
其中n为Cache的块大小与数据重复使用次数的乘积，H1是原来的命中率，H是块大小增加后的命中率。 在上式中代入相关参数，可求出

83 题4.2 对于下述访存字节地址序列： 1,14,50,89,20,17,19,56,19,11,14,43,15,16,9,17标出每次访存后的cache存储空间的分配情况和命中情况。假定cache是2路组相联的，采用FIFO替换策略，每块是4个32位的字。Cache的容量是16字，初始cache为空。

84 解： 3位 1位 1位 2位 主存地址 1位 1位 2位 cache地址 主存储器 区0 区1 组0 组1 ⋮ ⋮ ⋮ 区7
区号 组号 块号 字W 1位 1位 2位 cache地址 组号 块号 字w 主存储器 B0 B1 区0 B2 B3 B4 B5 区1 组0 B6 组1 B7 ⋮ ⋮ ⋮ B4 B5 B6 区7 B7

85 （2路组相联FIFO） 调进 调进 调进 调进 替换 替换 替换 替换 命中 替换 替换 替换 替换 替换 替换 替换 命中1次
时间 t 字地址流 1 1 1 1* 20 20* 19 19 19 19 19 19 19 19 19* 17 组0 50 50 50* 17 17 17 17 17 17 17 17* 16 16 16 14 14 14 14 14 14* 56 56 56* 14 14* 15 15 15 15 组1 89 89* 11 11* 43 43 43* 9 9 调进 调进 调进 调进 替换 替换 替换 替换 命中 替换 替换 替换 替换 替换 替换 替换 命中1次

86 第5章 作5.2 设一条指令的执行过程分为“取指令”、“分析”和“执行”三段，每一段的执行时间分别为Δt、2Δt和3Δt。在下列各种情况下，分别写出连续执行n条指令所需要的时间表达式。 （1）顺序执行方式。 （2）仅“取指令”和“执行”重叠。 （3） “取指令”、“分析”和“执行”重叠 （4）先行控制方式

87 解： （1）顺序执行需要的时间如下： （2）取指令和执行重叠，即一次重叠执行方式，我们假设第n+1条指令的取指令和第n条指令的执行同时结束，那么所需要的时间为： （3）取指令、分析和执行重叠 (4)先行控制方式

88 例5.1 带有瓶颈部件的4功能段流水线, △t1=△t2=△t4=△t, △t3=3△t,4个任务、10个任务时TP，E、SP 。
（1）分析法: 各段时间不等 TP= n Σ△ti+(n-1)△tj i=1 m

89 Σ△ti+(n-1)*△tj （2）时空图法 输出 S S4 1 2 3 4 S3 1 2 3 4 S2 1 2 3 4 S1 1 2 3
E= n个任务实际占用的时-空区 M各段总的时-空区 = Sp= n *Σ△ti m i=1 Σ△ti+(n-1)*△tj I=1 4*6 △t 15 △t 24 15 =1.6

90 例5. 2 以浮点加法运算为例（四段流水线）各段时间相等，求吞吐率、效率。
求Z=A+B+C+D+E+F+G+H，TP、E、Sp (注意有相关) TP=7/15△t E=7*4/(15*4)=7/15＝46% Sp=4*7/15=28/15=1.87 解: Z=A+B+C+D+E+F+G+H 1 2 3 4 5 6 7 时间 空间 1 2 3 4 5 6 7 流水线的效率不高，原因在于存在着数据相关,有空闲功能段。

91 例5.3 ASC计算机多功能算术运算流水线各段时间相等，6次浮点加、 5次定点乘的吞吐率，效率，加速比 m=8，n=11
浮加 定点乘 8 1 2 3 4 5 6 一 二 三 四 五 7 一 二 三 四 五 6 一 二 三 四 五 5 1 2 3 4 5 6 4 1 2 3 4 5 6 3 1 2 3 4 5 6 2 1 2 3 4 5 6 1 1 2 3 4 5 6 一 二 三 四 五 分析：T加=6+(6-1)*1=11(△t) T乘=4+(5-1)*1=8(△t) 时间 则 TP=11/(11+8)△t=11/19△t E=(6*6+5*4)△t/(19*8△t)=36.8% Sp=(6*6+5*4)△t/19△t=56/19=2.94

92 题5.1 一条线性流水线有4个功能段组成，每个功能段的延迟时间都相等，都为Δt。开始5个Δt，每间隔一个Δt向流水线输入一个任务，然后停顿2个Δt，如此重复。求流水线的实际吞吐率、加速比和效率。
[解答]流水线的时空图如下：

93 我们可以看出，在（11n+1）Δt的时间内，可以输出5n个结果，如果指令的序列足够长（n→∞），并且指令间不存在相关，那么，吞吐率可以认为满足：
加速比为： 从上面的时空图很容易看出，效率为：

94 例5.4 用一条5个功能段的浮点加法器流水线计算 每个功能段的延迟时间均相等，流水线的输出端和输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。 [解答]首先需要考虑的是，10个数的的和最少需要做几次加法。我们可以发现，加法的次数是不能减少的：9次；于是我们要尽可能快的完成任务，就只有考虑如何让流水线尽可能充满，这需要消除前后指令之间的相关。由于加法满足交换率和结合率，我们可以调整运算次序如以下的指令序列，我们把中间结果寄存器称为R，源操作数寄存器称为A，最后结果寄存器称为F，并假设源操作数已经在寄存器中，则指令如下：

95 I1： R1←A1+A2 I2： R2←A3+A4 I3： R3←A5+A6 I4： R4←A7+A8 I5： R5←A9+A10 I6： R6←R1+R2 I7： R7←R3+R4 I8： R8←R5+R6 I9： F←R7+R8 这并不是唯一可能的计算方法。假设功能段的延迟为Δt。时空图如下，图中的数字是指令号。

96 部件m R2 R4 R1 R3 R5 R6 R7 R8 F 5 1 2 3 4 5 6 7 8 9 4 1 2 3 4 5 6 7 8 9 3 1 2 3 4 5 6 7 8 9 2 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 21Δt R1=A1+A2 R5=A9+A10 R2=A3+A4 R6=R1+R2 R8=R5+R6 R3=A5+A6 R4=A7+A8 R7=R3+R4 F=R7+R8

97 整个计算过程需要21Δt，所以吞吐率为： 加速比为： 效率为：

98 作5.5 流水线由4个功能部件组成，每个功能部件的延迟时间为⊿t。当输入10个数据后，间歇5⊿t ，又输入10个数据，如此周期性地工作，求此时流水线的吞吐率，并画出其时空图。

99 [解答]按题意可得4个功能部件流水时的时空关系如下图所示
3 2 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 1 2 3 4 5 6 7 8 9 10 1 2 时间(⊿t) 5⊿t 所以，按周期性工作时的流水线平均吞吐率为 Tp=10/(14⊿t)=5/(7⊿t)

100 作5. 6 有一个浮点乘流水线如下图(a)所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出实现A. B. C
作5.6 有一个浮点乘流水线如下图(a)所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出实现A*B*C*D的时空图以及输入端的变化，并求出该流水线的吞吐率和效率；当流水线改为下图(b)形式实现同一计算时，求该流水线的效率及吞吐率。 ⊿t 3⊿t ⊿t 操作数 阶加 尾乘 规格化 积 图(a) 3⊿t 尾乘1 ⊿t 3⊿t ⊿t 阶加 尾乘2 规格化 积 3⊿t 尾乘3 图(b)

101 [分析]为了减少运算过程中的操作数相关，A*B*C*D应改为采用((A*B)*(C*D)) 的算法步骤进行运算。
[解]按图(a)组织，实现A*B*C*D的时空关系如下图(A)所示。 部件 规格化 尾乘 阶加 时间 13 A B C D A*B C*D 输入 图(A) 输出 A*B C*D A*B*C*D 吞吐率TP=3/(13⊿t) 效率E=(3×5⊿t)/(3×13⊿t)=5/13=38.5%

102 流水线按图(b)组织时，实现A*B*C*D的时空关系如图(B) 吞吐率TP=3/(11⊿t)
部件 规格化 尾乘3 尾乘2 尾乘1 阶加 时间 11 A B C D A*B C*D 输入 图(B) 输出 A*B C*D A*B*C*D 流水线按图(b)组织时，实现A*B*C*D的时空关系如图(B) 吞吐率TP=3/(11⊿t) 效率E =(3×5⊿t)/(5×11⊿t)=3/11=27.3%

103 例5.5 (类似题5.8) 一条线性静态多功能流水线由6个功能段组成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每个功能段的延迟时间均相等。流水线的输入端与输出端之间有直接数据通路，而且设置有足够的缓冲寄存器。现在用这条流水线计算： 画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。

104 解：为了取得较高的速度，我们需要一次将乘法作完，设源操作数存放在寄存器A、B中，中间结果存放在寄存器R中，最后结果存放在寄存器F中，则执行的指令序列如下所示：
I1： R1←A1*B1 I2： R2←A2*B2 I3： R3←A3*B3 I4： R4←A4*B4 I5： R5←A5*B5 I6： R6←A6*B6 I7： R7←R1+R2 I8： R8←R3+R4 I9： R9←R5+R6 I10： R10←R7+R8 I11： F←R9+R10 这并不是唯一可能的计算方法。假设功能段的延迟为Δt。时空图（不完全）如下，图中的数字是指令号。

105 部件m R1 R6 R7 R8 R10 F 6 1 2 3 4 5 6 7 8 9 10 11 5 1 2 3 4 5 6 4 1 2 3 4 5 6 3 7 8 9 10 11 2 7 8 9 10 11 1 1 2 3 4 5 6 7 8 9 10 11 22Δt 乘法 加法 R1=A1*B1 R2=A2*B2 R7=R1+R2 R3=A3*B3 R4=A4*B4 R8=R3+R4 R10=R7+R8 R5=A5*B5 R6=A6*B6 R9=R5+R6 F=R9+R10

106 （2）在程序实际执行过程中，有哪几种相关会引起流水线的停顿?
作5.4 在一台单流水线多操作部件的处理机上执行下面的程序，取指令、指令译码各需要1个时钟周期，MOVE,ADDT和MUL操作各需要2个、3个和4个时钟周期。每个操作都在第一个时钟周期从寄存器中读取操作数，在最后1个时钟周期把运算结果写到通用寄存器中。 K： MOVE R1,R0 ; R1←R0 K+1：MUL R0 , R2 ,R1 ; R0← (R1)×( R2) K+2：ADD R0,R2 , R3 ; R0← (R2) +( R3) （1）就程序本身而言，可能有哪几种相关？ （2）在程序实际执行过程中，有哪几种相关会引起流水线的停顿? （3）画出指令执行过程的流水线时空图，并计算机执行晚这3条指令共使用了多少个时钟周期？

107 解（1） K、K+1 存在写读相关，读写相关； K+1、K+2存在写写相关。 （2）K、K+1 的写读相关，会引起流水线的停顿；
K： MOVE R1,R0 ; R1←R0 K+1：MUL R0 , R2 ,R1 ; R0← (R1)×( R2) K+2：ADD R0,R2 , R3 ; R0← (R2) +( R3) K、K+1 存在写读相关，读写相关； K+1、K+2存在写写相关。 （2）K、K+1 的写读相关，会引起流水线的停顿； K+1、K+2的写写相关会引起流水线的停顿。

108 （3） 1 2 3 4 5 6 7 8 9 10 I1 IF1 ID1 RR1 EXE1 WR1 时钟周期 I2 IF2 ID2 RR2
I1 IF1 ID1 RR1 EXE1 WR1 时钟周期 I2 IF2 ID2 (RAW) (RAW) RR2 MD1 MD2 MD3 WR2 I3 IF3 ID3 RR3 FA1 FA2 WAW WAW WAW WR3 K： MOVE R1,R0 ; R1←R0 共使用11个时钟周期 K+1：MUL R0 , R2 ,R1 ; R0← (R1)×( R2) K+2：ADD R0,R2 , R3 ; R0← (R2) +( R3)

109 作5.13 一台非流水处理机A的工作时钟频率为25MHz，它的平均CPI为4。处理器B是A的改进型，它有1条5段的线性指令流水线。由于锁定电路延迟及时钟扭斜效应，它的工作时钟频率仅为20MHz,问：
（1）若在A和B两个处理器上执行100条指令的程序，则处理器B对A的加速比是多少？ （2）在执行上述程时，计算A，B处理器各自的MIPS速率是多少？ 解: 已知：MIPSB=20

110 解（1）相关性分析:1、2 存在写读相关；4、5存在读写相关；3、6存在写读相关；3、6存在写写相关。
题5.2 某超标量流水线计算机每个时钟发射两条指令，其4级指令流水线中包含IF、ID、EXE、WB流水级，各个流水段都是花费一个时钟周期。ALU指令在EXE流水段完成算术运算，乘除指令比ALU指令多花费2个时钟周期，访存指令在EXE功能段完成访存操作。流水中无相关专用通路。指出下列指令序列中的数据相关性，分别画出指令流水线在有序执行有序写回、无序执行无序写回情况下的时空图。 1：LOAD R0 , A ; R0←主存(A)单元 2：ADD R1 , R0 ; R1← (R1) +( R0) 3: LOAD R2 , B ; R2←主存(B)单元 4：MUL R3 , R4 ; R3← (R3) +( R4) 5：AND R4 , R5 ; R4← (R4) ∧ ( R5) 6：ADD R2 , R5 ; R2← (R2) +( R5) 解（1）相关性分析:1、2 存在写读相关；4、5存在读写相关；3、6存在写读相关；3、6存在写写相关。

111 （2）相关性分析: 按序发射按序完成之调度 1 2 3 4 5 6 7 8 9 10 I1 IF1 ID1 EXE1 WR1 时钟周期 I2
（2）相关性分析: 按序发射按序完成之调度 I1 IF1 ID1 EXE1 WR1 时钟周期 I2 IF2 (RAW) (RAW) (RAW) ID2 EXE2 WR2 I3 IF1 ID1 EXE1 MD2 顺序 顺序 顺序 WR1 I4 IF2 ID2 MD1 MD2 MD3 顺序 顺序 WR2 I5 IF1 ID1 EXE1 顺序 顺序 顺序 顺序 WR1 I6 IF2 (RAW) (RAW) (RAW) (RAW) (RAW) ID2 EXE2 WR2 1：LOAD R0 , A ; R0←主存(A)单元 (1,2RAW) 2：ADD R1 , R0 ; R1← (R1) +( R0) 主共使用11个时钟周期 3: LOAD R2 , B ; R2←主存(B)单元 (3,6RAW,WW) 4：MUL R3 , R4 ; R3← (R3)×( R4) (4,5WAR) 5：AND R4 , R5 ; R4← (R4) ∧ ( R5) 6：ADD R2 , R5 ; R2← (R2) +( R5)

112 （3）相关性分析: 无序发射无序完成之调度 1 2 3 4 5 6 7 8 9 10 I1 IF1 ID1 EXE1 WR1 时钟周期 I3
（3）相关性分析: 无序发射无序完成之调度 I1 IF1 ID1 EXE1 WR1 时钟周期 I3 IF2 ID2 EXE2 WR2 I4 IF1 ID1 MD1 MD2 MD3 WR1 I5 IF2 ID2 EXE2 WR2 I2 IF1 RAM ID1 EXE1 WR1 I6 IF2 (RAW) ID2 EXE2 WR2 1：LOAD R0 , A ; R0←主存(A)单元 (1,2RAW) 2：ADD R1 , R0 ; R1← (R1) +( R0) 主共使用7个时钟周期 3: LOAD R2 , B ; R2←主存(B)单元 (3,6RAW),WW 4：MUL R3 , R4 ; R3← (R3) ×( R4) (4,5WAR) 5：AND R4 , R5 ; R4← (R4) ∧ ( R5) 6：ADD R2 , R5 ; R2← (R2) +( R5)

113 （4）相关性分析: 无序发射无序完成之调度（设置专用数据通路）
（4）相关性分析: 无序发射无序完成之调度（设置专用数据通路） I1 IF1 ID1 EXE1 WR1 时钟周期 I3 IF2 ID2 EXE2 WR2 I4 IF1 ID1 MD1 MD2 MD3 WR1 I5 IF2 ID2 EXE2 WR2 I2 IF1 ID1 EXE1 WR1 I6 IF2 ID2 EXE2 WR2 1：LOAD R0 , A ; R0←主存(A)单元 (1,2RAW) 2：ADD R1 , R0 ; R1← (R1) +( R0) 主共使用7个时钟周期 3: LOAD R2 , B ; R2←主存(B)单元 (3,6RAW),WW 4：MUL R3 , R4 ; R3← (R3) ×( R4) (4,5WAR) 5：AND R4 , R5 ; R4← (R4) ∧ ( R5) 6：ADD R2 , R5 ; R2← (R2) +( R5)

114 作 在CRAY-1机上，设向量长度均为64，所有浮点功能部件的执行时间分别为：相加需6拍，相加需7拍，求倒数近似值需14拍，从存储器读数据需6拍，打入寄存器机启动功能部件各需1拍，问下列个指令组，组内的哪些指令可以链接？，哪些指令不可以链接？不能链接的原因是什么？并分别计算各指令组全部完成所需的拍数。 （1） V0 ←存储器 （2） V2 ← V0 × V1 V1 ← V2 ＋ V V3 ←存储器 V4 ← V5×V V4 ← V2 ＋ V3 （3） V0 ←存储器 （4） V2 ← 存储器 V2 ← V0 × V V1 ←1/V0 V3 ← V2＋ V V3 ← V1 × V2 V5 ← V3＋ V V5 ← V3 ＋ V4

115 解： 组（1）三条指令可并行执行。 T= =72(拍)。 组（2）前二条指令可并行执行，前两条与第三条指令可链接执行。 T=（ ）+63=80（拍）。 组（3） 前3条指令可链接执行，后一条指令只能串行（加法部件冲突） T=（ ）+8+63=159（拍）。 组（4）前二条指令可并行执行，后两条可链接，这样前两条与后两条指令可链接执行。 T=（14）+（9）+(8)+63=94（拍）。

116 题5.3 对于以下计算表达式: I=A+B+C+D×E×F+G+H 其中A,B…,I 都是寄存器名。
题5.3 对于以下计算表达式: I=A+B+C+D×E×F+G+H 其中A,B…,I 都是寄存器名。 （1）指出其中的并行性，即哪些操作可以并行执行； （2）对于采用5级指令流水线的计算机，试安排完成表达式计算的操作顺序，并写出指令序列，使得流水线的停顿时间最少； （3）对于一台VLIW计算机，假定其有2个加法部件和一个乘法部件，都能在一个流水周期中完成计算，试将上述表达式用最少的超长指令序列表示。

117 解（1） I=A+B+C+D×E×F+G+H 可并行操作的运算为： A+B+C+G+H D×E×F （3） ① A+B，G+H， D×E

118 （2） IF1 ID EXE MEM WR 1: R0←D IF2 ID EXE1 MEM WR 2: R1←E IF3 ID EXE
3: R2←G （2） IF4 ID EXE MEM WR 4: R3←A IF5 ID EXE1 MEM WR 5: R4←B IF6 ID MD1 MD2 MD3 MEM WR 6: R0←D *E 7: R5←H IF7 ID EXE MEM WR 8: R6←F IF8 ID EXE4 MEM WR 9: R3← A+B IF9 ID EXE MEM WR 10: R7←C IF10 ID EXE MEM WR IF11 ID EXE MEM WR 11: R3←G+H IF12 ID MD1 MD2 MD3 MEM WR 12: R5←D*E*F IF14 ID EXE MEM WR 14: R3←A+B+C IF18 ID EXE MEM WR 18: R3←A+B+C+R5 共用21个时钟周期，有4个 时钟周期的停顿

119 第6章 作6.1 画出16台处理器仿ILLIAC Ⅳ的模式进行互连的互连结构图，列出PE0分别只经一步、二步和三步传送能将信息传送到的各个处理器号。 解：16台处理机仿ILLIAC Ⅳ的模式互连结构图如下页图所示。由图可知： PE0经一步可将信息传送到的处理器号有PE1、PE4、PE12、PE15。 PE0经二步可将信息传送到的处理器号有PE2、PE3、PE5、PE8、PE11、PE13、PE14。 PE0经三步可将信息传送到的处理器号有PE6、PE7、PE9、PE10。 可见，最多经3步就可以将PE0的信息传送到任何其它的处理器上，所以其最大的距离为3步。

120 PE0 PE1 PE2 PE3 PE4 PE5 PE6 PE7 PE8 PE9 PE10 PE11 PE12 PE13 PE14 PE15 16台处理器仿ILLIAC Ⅳ机的互连机构

121 例6.1 编号为0、1、·····14、15的16个处理器，用单级互连网络互连。当互连函数分别为
（1）Cube3 （2）PM2+3 （3）PM2-0 （4）Shuffle （5）Shuffle(Shuffle)时，第13号处理器各连至哪一个处理器？ ［分析］：由于是16个处理器组成的单级互连网络，每个处理器的二进制地址编号为4位。根据互连函数关系式，即可求出与第13号处理器相连的处理器号。

122 解： （1） ， （2） 即第13号处理器连至第5号处理器； （3） 即第13号处理器连至第12号处理器； （4）
（1）　　　　　　　　　　　　　　　　　　， 　　第13号处理器连至5号处理器； （2） 　　　即第13号处理器连至第5号处理器； （3） 　　即第13号处理器连至第12号处理器； （4） 第13号处理器与第11号处理器相连； （5） 第13(1101)号处理器连至第7(0111)号处理器。

123 作6.6 冲突 全混拓扑 全混拓扑 全混拓扑 冲突 1 1 E I 4 A 2 1 1 4 2 2 3 B F J 2 3 5 6 3 出 端 入 端 2 1 4 4 5 4 5 C G K 6 3 5 3 6 5 6 7 6 7 D H L 7 7 7 级 2 1 5→0与7→1冲突 N=8多级混洗交换网络 0→5与1→7不冲突

124 作6.18 由霍纳（Horner）法则给定的表达式如下：E=a(b+c(d+e(f+gh)))，利用减少树高的办法来加速运算，要求：
（1）画出树形流程图； （2）确定Tp、P、Sp、Ep等诸值。 解：（1）利用交换律、结合律、分配律，将原始表达式转换成如下表达式： E＝a(b+cd)+ace(f+gh) 在单处理机上的计算的树形图如图7.4(a)所示，在多处理机上并行运算的树形图如图7.4(b)所示。

125 E＝a(b+c(d+e(f+gh))) E＝a(b+cd)+ace(f+gh) (a) (b) + * a b e c d f h + *

126

127 举例1(续) E1=a+bx+cx2+dx3 用3台处理机，需4级运算 级数(高度)Tp=4 处理机数P=3 加速比Sp=顺序运算级数T1/ P台处理机运算的级数Tp =6/4=3/2 效率Ep=Sp/P=1/2 即运算的加速总是伴随着效率的下降