题型四：（八）（九）（十）（十一）（十二）（十三）（十四）（十五） 题型五：（十六）（十七）（十八）
题型六：（十九）（二二）（二三）（二五）（二六）（二七）（二八） 其他题型考选择题：（二十）（二一）（二四）（二九）（三十） （一）【7-6】由霍纳法则给定的表达式如下：E=a(b+c(d+e(f+gh))) 利用减少树高的办法来加速运算，要求： （1） 画出树形流程图。 （2） 确定TP、P、SP、EP的值。
解：（1）若用单处理机处理，T1=7，改成E=ace(f+gh)+a(b+cd)，其计算的树形流程图如附图46所示。
（2） P=3；TP=4；SP=T1/TP=7/4；EP=SP/P=7/12
（二）【6-2】设向量长度均为64，在CRAY-1机上所用浮点功能部件的执行时间分别为：相加6拍，相乘7拍，求倒数近似值14拍；在存储器读数6拍，打入寄存器及启动功能部件各1拍。问下列各指令组内的哪些指令可以链接？哪些指令不可链接？不能链接的原因是什么？分别计算出各指令全部完成所需的拍数。 （1） V0←存储器 （2）V2←V0×V1
V1←V2+V3 V3←存储器
V4←V5×V6
V4←V0+ V3
（3） V0←存储器 （4）V0←存储器
V2←V0×V1 V1←1/ V0 V3←V2+ V0 V3←V1×V2 V5←V3+ V4 V5←V3+ V4
解：（1）三条全并行，完成时间为72拍
（2）一、二条并行，链接第三条，完成时间为80拍
（3）第一条链接第二条，与第三条串行，与第四条串行，完成时间为222拍
（4）全链接，完成时间为104拍
（三）【例5-3】在一个4段的流水线处理机上需经7拍才能完成一个任务，其预约表如表5-2所示。
表5-2 7拍才能完成一个任务的预约表 段 时间 1 2 3 4 5 6 7 S1 S2 S3 S4 √ √ √ √ √ √ √ √ 分别写出延迟禁止表F、冲突向量C；画出流水线状态转移图；求出最小平均延迟及流水线的最大吞吐率及其调度时的最佳方案。按此调度方案，输入6个任务，求实际的吞吐率。 解：此例可得延迟禁止表F={2,4,6}。
初始冲突向量C=（101010）。 状态转移图如图5-29所示。
各种调度方案及其相应的平均延迟如表5-3所示。 表5-3 调度方案及其相应的平均延迟 调度方案 （1,7） （3,5） 平均延迟/拍 4 4 （5,3） （5） 4 4 由表5-3可知，最小平均延迟为4拍。
此时流水线的最大吞吐率Tpmax=1/4（任务/拍）。 最佳调度方案宜选其中按（1,7）周期性调度的方案。
按（1,7）调度方案输入6个任务，全部完成的时间为1+7+1+7+1+7=24（拍），实际吞吐率Tp=6/24（任务/拍）。
若按（3,5）调度方案输入6个任务，全部完成的时间为3+5+3+5+3+7=26（拍），实际吞吐率Tp=6/26（任务/拍）。
若按（5,3）调度方案输入6个任务，全部完成的时间为5+3+5+3+5+7=28（拍），实际吞吐率Tp=6/28（任务/拍）。
可见，最佳的方案应为（1,7）调度方案，输入6个任务的实际吞吐率较之其他方案要更高些。
（四）【5-11】在一个5段的流水线处理机上需经9拍才能完成一个任务，其预约表如表5-4所示。分别写出延迟禁止表F、冲突向量C；画出流水线状态转移图；求出最小平均延迟及流水线的最大吞吐率及其调度方案。按此流水线调度方案输入6个任务，求实际吞吐率。 表5-4 9拍才能完成一个任务的预约表 段 时间 T0 S1 S2 √ T1 √ T2 √ T3 T4 T5 T6 T7 T8 √ S3 S4 S5 √ √ √ √ √ √ √ 解：根据预约表中各个行中打“√”的拍数求出差值，并将这些差值汇集在一起，就可得到延迟禁止表F={1,3,4,8}。由延迟禁止表F可转换得初始冲突向量C=（10001101）。根据初始冲突向量可画出状态转换图如附图31所示。
各种周期性调度方案列于附表15。由附表15可知最小平均延迟为3.5拍。此时，Tpmax=1/3.5（任务/拍）。 最佳调度方案为（2,5）。
附表15 周期性调度方案
调度方案 （2,5） （2,7） （5） 平均延迟/拍 3.5 4.5 5 调度方案 （6,7） （7） （5,2） 平均延迟/拍 6.5 7 3.5 （6,5） （6） 5.5 6 … … 按（2,5）调度方案实际输入6个任务的时空图如附图32所示。实际吞吐率Tp=6/25（任务/拍）。
（五）【例7-4】计算E1=a+bx+cxx+dxxx。 利用减少树高的办法来加速运算，要求： （1） 画出树形流程图。 （2） 确定TP、P、SP、EP的值。
解：（1）利用霍纳法可得到E1=a+x(b+x(c+x(d)))。若用单处理机处理，T1=7，改成E1=a+x(b+x(c+x(d)))。其计算的树形流程图如附图7-17（a）所示。
（2） TP=4、P=3、SP=3/2、EP=1/2
（六）【例7-6】表达式E2=a+b(c+def+g)+h。 利用减少树高的办法来加速运算，要求： （1） 画出树形流程图。 （2） 确定TP、P、SP、EP的值。 解：P253-P254
（七）【P201】设向量长度均为64，在CRAY-1机上所用浮点功能部件的执行时间分别为：相加6拍，相乘7拍，求倒数近似值14拍；在存储器读数6拍，打入寄存器及启动功能部件各1拍。问下列指令组内的哪些指令可以链接？哪些指令不可链接？不能链接的原因是什么？分别计算出各指令全部完成所需的拍数。
V3←存储器 V2←V0+V1 V4←V2×V3 解：P201-P202
（八）【5-3】有一个浮点乘流水线如图5-36（a）所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出实现A×B×C×D的时空图以及输入端的变化，并求出流水线的吞吐率和效率；当流水线改为图5-36（b）所示的形式实现同一计算时，求该流水线的效率及吞吐率。
解：按图5-36（a）组织，实现A×B×C×D的时空关系如附图16所示。
吞吐率：Tp=3/13△t ；效率：η=（3×5△t）/（3×13△t）=5/13 流水线按图5-36（b）组织，实现A×B×C×D的时空关系如附图17所示。
吞吐率：Tp=3/11△t；效率：η=（3×5△t）/（3×11△t）=5/11
（九）【5-4】一个4段的双输入端规格化浮点加法流水线，每段经过时间为10ns，输出可直接返回输入或将结果暂存于相应缓存器中，问最少需要经多长时间才能求出Σ
10
（i=1）Ai，并画出时空图。
解：按（（（（A1+A2）+（A3+A4））+（A9+A10））+（（A5+A6）+（A7+A8）））流水的时空图如附图18所示。
（十）【5-5】为提高流水线效率可采用哪两种主要途径来克服速度瓶颈？现有3段流水线各经过时间依次为△t、3△t、△t。
（1）分别计算在连续输入3条指令和30条指令时的吞吐率和效率。 （2）按两种途径之一进行改进，画出流水线结构示意图，同时计算连续输入3条指令和30条指令时的吞吐率和效率。
（3）通过对（1）、（2）两小题的计算比较可得出什么结论？ 解：提高流水线效率，消除速度瓶颈主要有两种途径：①将瓶颈段再细分；②重复设置多个瓶颈段并联工作，给其轮流分配任务。
（1） 在3段流水线各段经过时间依次为△t、3△t、△t的情况下，
连续流入3条指令时，将n=3，m=3，△t1=△t、△t 2=3△t、△t3=△t，△tj=3△t代入，可得吞吐率Tp和效率η为
（2） 若采取将2段细分成3个子段，每个子段均为△t，构成流水线
结构如附图10所示。
若采取将3个2段并联构成的流水线，其构成如附图20所示。
（十一）【5-6】有一个双输入端的加---乘双功能静态流水线，由经过时间为△t、2△t、2△t、△t的1、2、3、4四个子过程构成。“加”按1→2→4连接，“乘”按1→3→4连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。现要执行A×（B+C×（D+E×F））+G
×H的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空图，标出流水线入、出端数的变化情况，求出完成全部运算的时间及此期间流水线的效率。如对流水线瓶颈子过程再细分，最少需多长时间可完成全部运算？若子过程3不能再细分，只能用并联方法改进，则流水线的效率为多少？ 解：
（十二）【5-7】有一个乘---加双功能静态流水线，“乘”由1→2→3→4完成，“加”由1→5→4完成，各段延时均为△t，输出可直接返回输入或存入缓冲器缓冲。现要求计算长度均为8的A、B两个向量逐对元素求和的连乘积
S=Π8（i=1）（Ai+Bi） (1) 画出流水线完成此运算的时空图。
(2) 完成全部运算所需多少△t？此期间流水线的效率是多少？ 解：
（十三）【5-8】带双输入端的加---乘双功能静态流水线有1、2、3、4四个子部件，延时分别为△t、△t、2△t、△t，“加”按1→2→4连接，“乘”按1→3→4连接，输出可直接返回输入或锁存，现欲执行Σ4（i=1）[（ai+bi）×ci]。
（1） 画出此流水线时空图，标出流水线入端数据变化情况。 （2） 计算运算全部完成所需时间及在此期间流水线的效率。 （3） 将瓶颈子部件再细分，画出解此题的时空图。
（4） 求出按（3）解此题所需时间及在此期间流水线的效率。 解：（1）
（2）（3）（4）
（十四）【5-9】现有长度为8的向量A和B，请分别画出下列4种结构的处理器上求点积A·B的时空图，并求完成全部结果的最少时钟拍数。设处理器中每个部件的输出均可直接送到任何部件的输入或存
入缓冲器中，其间的传送延时不计，指令和源操作数均能连续提供。 （1） 处理器有个一乘法部件和一个加法部件，不能同时工作，部件
内也只能以顺序方式工作，完成一次加法或乘法均需5拍。 （2） 与（1）基本相同，只是乘法部件和加法部件可并行。 （3） 处理器有一个乘---加双功能静态流水线，乘、加均由5个流水
线构成，各段经过时间要1拍。
（4） 处理器有乘、加两条流水线，可同时工作，各由5段构成，每
段经过时间为1拍。 解：
（十五）【5-2】流水线由4个功能部件组成，每个功能部件的延迟时间为△t，当输入10个数据后间歇5△t又输入10个数据，如此周期性地工作，求此时流水线的吞吐率，并画出其时空图。
（十六）【例3-3】P89~P91
（十七）【3-5】设中断级屏蔽位“1”对应于开放，“0”对应于屏蔽，各级中断处理程序的中断级屏蔽设置如表3-6所示。 表3-6 习题3-5中的中断级屏蔽位设置 中断处理 中断级屏蔽位 程序级别 第1级 第1级 0 第2级 0 第3级 0 第4级 0 第2级 第3级 第4级 1 1 1 0 0 0 1 0 1 1 0 0 （1） 当中断相应优先次序为1→2→3→4时，其中断处理次序是什
么？
（2） 设所有的中断处理都各需3个单位时间，中断响应和中断返回
时间相对中断处理时间少得到多。当机器正在运行用户程序时，同时发生第2、3级中断请求，过两个单位时间后，又同时发生第1、4级中断请求，试画出程序运行过程示意图。 解：（1）中断处理（完）的次序为1→3→4→2。
（2） CPU运行程序的过程示意图如附图4所示。在该图中，粗短线
部分代表进行交换程序状态字的时间，△t为1个单位时间。
（十八）【3-6】若机机器共有5级中断请求，中断响应优先次序为1→2→3→4→5，现要求其实际的中断处理次序为1→4→5→2→3，回答下面问题：
（1） 设计各级中断处理程序的中断级屏蔽位（令“1”对应于屏蔽，
“0”对应于开放）；
（2） 若在运行用户程序时，同时出现第4、2级中断请求，而在处
理第2级中断未完成时，又同时出现第1、3、5级中断请求，请画出此程序运行过程示意图。 解：（1）
（2）
（十九）【例2-5】现假设某模型机共有n（n=7）条指令，使用频度如表2-4所示。若操作码用定长表示，需要3位。而按信息论观点，若各种指令的出现是互相独立的（实际并不都是如此），操作码的信息源熵（信息源所含平均信息量）H=-Σn（i=1）pi1bpi。由表2-4的数据可得H=-Σn（i=1）pi1bpi=2.17。说明表示这7种指令的操作码平均只需2.17位即可。现在用3位定长码表示，信息冗余度为（3-2.17）/3≈28%。冗余度相当大。 指令 I1 I2 I3 I4
使用频度（pi） 指令 0.40 0.30 0.15 0.05 I5 I6 I7 - 使用频度（pi） 0.04 0.03 0.03 - （1） 改用哈夫曼编码以及扩展的哈夫曼编码； （2） 构造哈夫曼数； 解：（1） 指令 I1 I2 I3 I4 I5 I6 I7 频度操作码OP使用哈OP长利用哈夫曼概念的OP长pi 0.40 0.30 0.15 0.05 0.04 0.03 0.03 夫曼编码 0 10 110 11100 11101 11110 11111 度li 1 2 3 5 5 5 5 扩展操作码 00 01 10 1100 1101 1110 1111 度li 2 2 2 4 4 4 4 （2）
（二十）【例2-6】P59
（二一）【例2-7】若某机要求有：三地址指令4条，单地址指令255条，零地址指令16条。设指令字长为12位，每个地址码长为3位。能否以扩展操作码为其编码？如果单地址指令改为254条呢？ 解：P60
（二二）【例2-8】某模型机9条指令的使用频度如表2-7所示。要求有两种指令字长，都按双操作数指令格式编排，采用扩展操作码，并限制只能有两种操作码码长。设该机有若干通用寄存器，主存为16位宽，按字节编址，采用按整数边界存储，任何指令都在一个主存周期中取得，短指令为寄存器---寄存器型，长指令为寄存器---主存型，主存地址应能变址寻址。
表2-7 模型机指令
指令 使用频指令 度 使用频指令 度 使用频度 ADD（加） STO（存） 30% 7% SUB（减） 24% JMP（转移） 7% CLA（清加） 20% JOM 6% SHR（右移） 2% STP（停机） 1% CIL（循环左移） 3% （1） 改用哈夫曼编码以及扩展的哈夫曼编码； （2） 构造哈夫曼数； （3） 计算平均码长 解：（1）哈夫曼编码： ADD（加） SUB（减） CLA JOM STO JMP SHR CIL STP 扩展的操作码编码： ADD（加） SUB（减） CLA 30% 24% 20% 00 01 10 30% 24% 20% 6% 7% 7% 2% 3% 1% 01 11 10 0001 0011 0010 000001 00001 00000 JOM STO JMP SHR CIL STP （2） 哈夫曼树：
6% 7% 7% 2% 3% 1% 11000 11001 11010 11011 11100 11101
（3） 平均码长：
哈夫曼编码：2.61位；扩展码：2.78位。
（二三）【2-4】设某机器阶值6位、尾数48位，阶符和数符不在其内，当尾数分别2、8、16为基时，在非负阶、正尾数、规格化情况下，求出其最小阶、最大阶、阶的个数、最小尾数值、最大尾数值、可表示的最小值和最大值及可表示数的个数。
解：p=6，m=48时，在非负阶、规格化、正尾数的情况下，rm=2,8,16的各个参数的计算结果如附表1所示：
（二四）【2-5】浮点数系统使用的阶基rp=2，阶值位数p=2，尾数基值rm=10，以rm为基的尾数m′=1。
（1） 试计算在非负阶、正尾数、规格化情况下的最小尾数值、最
大尾数值、最大阶值、可表示的最小值和最大值及可表示数的个数；
（2） 对于rp=2，p=2，rm=4，m′=2，重复以上计算。 解：（1）在非负阶、正尾数、规格化情况下：
（2）
（二五）【2-6】由4位数（其中最低位为下溢处理的附加位）经ROM查表舍入法，下溢处理成3位结果，设计使下溢处理平均误差接近于0的ROM表，列出ROM编码表的地址与内容的对应关系。 解：ROM下溢处理表16个单元的地址码为0000~1111，它与其内容（即下溢处理后的3位结果值）的对照关系如下表所示： 地址 内容 地址 内容
0000 000 1000 100 0001 001 1001 101 0010 001 1010 101 0011 010 1011 110 0100 010 1100 110 0101 011 1101 111 0110 011 1110 111 0111 100 1111 111 （二六）【2-9】经统计，某机器14条指令的使用频度分别为0.01,0.15,0.12,0.03,0.02,0.04,0.02,0.04,0.01,0.13,0.15,0.14,0.11,0.03。分别求出用等长码、哈夫曼码、只有两种码长的扩展操作码等3种编码方式的操作码平均码长。
解：14条指令的等长操作码的平均码长是4位。 哈夫曼编码平均码长3.38位。
只有两种码长的扩展操作码平均码长3.4位。
（二七）【2-10】电文由A~J及空格字符组成，其字符出现频度依次为0.17,0.05,0.20,0.06,0.08,0.03,0.01,0.08,0.13,0.08，0.11。
（1） 各字符用等长二进码编码，传送103个字符时，共需传送多少
个二进制码码位？
（2） 构造哈夫曼数，写出各字符的二进码码位数，计算字符的二进
制位平均码长。
（3） 用哈夫曼码传送103个字符，比定长码传送减少传送的二进制
码码位数是多少？ 解：（1）共需传送4×103位。
（2） 哈夫曼树如附图2所示。字符码的二进制位平均码长为3.23
位。
（3） 可减少传送的二进制码码位数是（4-3.23）×103=770位
（二八）【2-11】用于文字处理的某专用机，每个文字符用4位十进制数字（0~9）编码表示，空格则用口表示，在对传送的文字符号和空格进行统计后，得出数字和空格的出现频度分别为 口：20% 0:17% 1:6% 2：8% 3:11% 4:8% 5：5% 6:8% 7:13% 8：3% 9:1%
（1） 若上述数字和空格均用二进制编码，试设计二进制信息位平均
长度最短的编码。
（2） 若传送106个文字符号（每个文字符号后均跟一个空格），按
最短的编码，共需传送多少个二进制位？
（3） 若十进制数字和空格均用4位二进制码表示，共需传送多少个
二进制位？
解：（1）按所给的十进制数字和空格字符出现的频度，构造哈夫曼树如图3所示。这得到哈夫曼编码如下： 口：01 0:111 1:1000 2:1001 3:001 4:1100 5:0001 6:1101 7:101 8:00001 9:00000
其平均二进制位码长为3.23位
（2） 按最短的编码来传送106个文字符号，因为每个文字符又用4
位十进制数字，再后跟一个空格表示，所以总共需传送的二进制位数应当是106×（4+1）×3.23位=1.615×107位。 （3） 若十进制数字和空格均用4位二进制码表示，则共需传送106
×（4+1）×4=2×107位。
（二九）【2-12】某机器指令字长16位，设有单地址指令和双地址指令两类。若每个地址字段为6位，且双地址指令有x条，则单地址指
令最多可以有多少条？
解：设双地址指令x条，则单地址指令最多可有（24-x）·26条。
（三十）某模型机有10条指令，其中有2条指令使用都在30%以上，其他8条指令使用不到10%，写出两种码长的扩展操作码。 解：第一种码长：00,01
第二种码长：0001,0010,0011,0100,0101,0110,0111,1000
因篇幅问题不能全部显示，请点此查看更多更全内容