计算机系统结构模拟.docx
《计算机系统结构模拟.docx》由会员分享，可在线阅读，更多相关《计算机系统结构模拟.docx（29页珍藏版）》请在冰点文库上搜索。
计算机系统结构模拟
计算机系统结构
试卷一
1.经统计,某机器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。
请分别求出用等长码,哈夫曼码,只有两种码长的扩展操作码的操作码平均码长。
2.设有两个向量C和D，各有4个元素，在图中的静态双功能流水线上工作。
其中，1->2->3->5组成加法流水线，1->4->5组成乘法流水线。
设每个流水线所经过的时间均为Δt，而且流水线的输出结果可以直接返回到输入或暂存于相应的缓冲寄存器中，其延迟时间和功能切换所需要的时间都可以忽略不计。
求：
该流水线的实际吞吐率TP和效率η。
3.在一个5段的流水线处理机上需经9拍才能完成一个任务，其预约表如下表所示。
（1）分别写出延迟禁止表F、初始冲突向量C；
（2）画出流水线状态转移图；
（3）求出最小平均延迟、调度最佳方案。
4.如果设一个系统有四个中断级，中断响应次序为1->2->3->4。
现要求中断处理次序改为1->4->3->2,
（1）请画出中断级屏蔽位表。
（2）如果在运行用户程序的过程中同时发生了1,2,3,4级中断,请画出此程序运行过程示意图。
（3）如果在运行用户程序的过程中同时发生了2,3级中断,而在3级中断未处理完毕又发生了4级中断,最后回到用户程序时又同时发生了1,2级中断,请画出此程序运行过程示意图。
试卷一答案：
1.
等长码码长为４位，哈夫曼码平均码长为３.３８位，两种码长的扩展操作码的操作码平均码长为３.４位
2.
5
4
3
2
1
012345678910111213141516时间Δt
实际吞吐率TP=7/（15Δt）
η=32%
3.
分别写出延迟禁止表F={1,5,6,8},
初始冲突向量C={10110001},
流水线状态转移图
最小平均延迟:
3.5拍调度最佳方案 （３，４）
4.
（１）
（２） （３）
试卷二
二、（10分）在采用通用寄存器指令集结构的计算机上得到了如下所示的数据：
指令类型
执行频率
时钟周期数
ALU指令
43%
1
LOAD指令
21%
2
STORE指令
12%
2
分支指令
24%
2
假若编译器优化后能去掉50%的ALU指令，但不能去掉其它三类指令。
求优化后的MIPS与优化前的MIPS速率比。
三、（10分）设某机器系统指令字长12位，每个操作码和地址均占3位，试提出一种分配方案，使该指令系统有4条三地址指令，8条二地址指令和180条单地址指令。
四、（10分）设通道在数据传送期中，选择设备需4.9μS，传送一个字节数据需0.lμS。
（1）其低速设备每隔250μS发出一个字节数据传送请求，问最多可接多少台这种设备？
（2）若有A～E共5种高速设备，要求字节传送的间隔时间如下表所示，其时间单位为μS。
若一次通信传送的字节数不少于1024个字节，问哪些设备可挂在此通道上？
哪些则不能？
设备
A
B
C
D
E
时间间隔（μS）
0.13
0.1
0.11
0.2
0.3
五、（10分）有一非线线性流水线预约表如下。
功能段
1
2
3
4
5
6
S1
√
√
S2
√
√
√
S3
√
√
S4
√
（1）求平均延迟最小的最佳调度方案；
（2）画出按最佳方案之一连续输入3个任务的时空图。
六、（10分）有一四段线性流水线,每功能段延时时间分别是：
△t1=△t3=△t4=△t0,△t2=3△t0。
若在这个流水线上执行40个任务。
求实际吞吐率、效率和加速比。
输
出
端
输
入
端
七、（10分）N=8个结点的三级立方体网络如下图所示。
当K1=0时，试说明输入4号结点不能实现和哪些输出结点相连？
C3
八、（10分）在8个PE构成的双向环互连的并行处理机中，计算点积S=
（n=8）所需要的时间。
设初始化时将A,B各分量已分配到各PE中，且设相邻处理单元之间传送一次数据需要时间△t，完成一次加法需要时间2△t，完成一次乘法需要时间4△t。
试卷二答案：
二、（10分）
[解]：
三、（10分）
[解]：
000×××××××××
011×××××××××
100000××××××
100111××××××
101000000×××
64+116=180
101111111×××
110000000×××
111110011×××
四、（10分）
[解]：
（1）低速设备应接字节多路通道
所以，n≤50台，即最多可接50台
（2）根据题意，此通道为选择通道
其中，n≥1024，应使selecti≤maxselect，由此可得出通道工作周期为：
T≈0.1014（us）
所以，只有A、C、D、E可挂在此通道上，B则不行。
五、（10分）
[解]：
（1）状态图略。
最佳调度方案为（3）和（1，5）
（2）输入3个任务时空图略。
六、（10分）
[解]：
七、（10分）
[解]：
不能与输出的2、3、6、7结点相连。
八、（10分）
[解]：
需要8次乘法，7次加法；
共14△t
试卷三
一、计算题：
1．设一台模型机有7条指令，其使用频度为：
____________________________________________________
指令使用频度|指令使用频度
I10.03|I40.05
I20.03|I50.15
I30.04|I60.3
|I70.4
_____________________________________________________
求出：
（1）利用哈夫曼（Huffman）压缩技术，构造哈夫曼树；
（2）.操作码平均码长和扩展码长。
2.如果设一个系统有四个中断级，个级中断响应次序为1->2->3->4。
见中断级屏蔽位表
中断处理
程序级别
中断级屏蔽位
1级
2级
3级
4级
第1级
第2级
第3级
第4级
0
1
1
1
0
0
1
1
0
0
0
1
0
0
0
0
求当把中断次序改为1->4->3->2时，画出中断级屏蔽位表。
3.计算流水线实际吞吐率TP和效率η。
设有两个向量C和D，各有4个元素，在图中的静态双功能流水线上工作。
其中，1->2->3->5组成加法流水线，1->4->5组成乘法流水线。
设每个流水线所经过的时间均为Δt，而且流水线的输出结果可以直接返回到输入或暂存于相应的缓冲寄存器中，其延迟时间和功能切换所需要的时间都可以忽略不计。
求：
该流水线的实际吞吐率TP和效率η。
4.计算多级立方体互连网络。
见图N=8多级立方体互连网络，求当输入端级控制信号为S2S1S0=010时，输入端为01234567时，输出端为：
。
输出
输入
试卷三答案：
1.
1.0
（1）
1
0.6
1
0.3
1
0.15
10000
0.09
0.06
1010
0.03
0.04
0.05
0.15
0.3
0.4
0.03
（2）H=2.17
H=2.2
2.
中断处理
程序级别
中断级屏蔽位
1级
2级
3级
4级
第1级
第2级
第3级
第4级
0
1
1
1
0
0
0
0
0
1
0
0
0
1
1
0
3.
空间
5
4
3
2
1
012345678910111213141516时间Δt
实际吞吐率TP=7/（15Δt）η=32%
4.23016745
试卷四
1.（12分）假设某模型机共有7条指令，7条指令I1—I7使用的频度分别为：
0.35,0.25,0.20,0.10,0.04,0.03,0.03。
（1）利用Huffman算法，构造Huffman树，并给出Huffman编码和平均码长。
（2）给出Huffman扩展码编码。
2.（10分）多级混洗交换网络是如何组成的？
它与间接二进制n立方体网络有何差异?
并画出N=8时的多级混洗交换网络图。
3.（8分）设向量A和B各有4个元素在下图所示的静态双功能流水线上计算向量点积A·B=
，其中1→2→3→5组成加法流水线，1→4→5组成乘法流水线。
若假定流水线的各段所经过的时间均为△t=2.5，流水线输出可直接送回输入或暂存于相应缓冲寄存器中，其延迟时间和功能切换所需的时间都可忽略。
求出吞吐率和加速比。
试卷四答案：
1.
表操作码的Huffman码及扩展操作码的编码
指令
频度（Pi）
操作码使用
Huffman编码
OP长度（Li）
利用Huffman概念的扩展操作码
OP长度（Li）
I1
0．35
0
1
00
2
I2
0．25
10
2
01
2
I3
0.20
110
3
10
2
I4
0.10
11100
5
1100
4
I5
0.04
11101
5
1101
4
I6
0.03
11110
5
1110
4
I7
0.03
11111
5
1111
4
2.多级混洗交换网络由n级相同的网络组成，每一级都包含一个全混拓扑和随后一列2n-1个四功能交换单元，采用单元控制方式。
多级混洗交换网络与间接二进制n方体网络只有两点差别：
前者数据流向的级号顺序n-1,n-2,…，1，0，用四功能交换单元，后者数据流向相反，其级号顺序0，1,…,n-1,用二功能交换单元。
33．实际吞吐率为=
因顺序方式所需时间为4
，
因此加速比SP=24
=1.6
试卷五
1、一模型机有10条指令，各指令的使用频度分别为：
0.25,0.20,0.15,0.10,0.08,0.08,0.05,0.04,0.03,0.02。
（H=2.96）
（1）写出这些指令操作码的哈夫曼编码，并求其平均码长和信息冗余量。
（2）写出这些指令的3/7和2/8两种扩展编码，并计算其平均码长和信息冗余量。
2、在三种类型的通道上各接有5台设备。
请分别写出这三种通道上每个设备完成1024B数据传输的总时间，并画简图来示意传送过程。
（设TS=9.8us,TD=0.2us,K=512B）
3、有一四段线性流水线，每功能段延时时间分别是：
△t1=△t3=△t4=△t，△t2=3△t。
现在这个流水线上分别执行4个任务（要求画出时空图）和40个任务，求实际吞吐率、效率和加速比。
4、对于采用级控制的三级立方体网络，当第2级为直连状态时，PE5不能实现与哪些结点之间的通信？
当第2级为交换状态时，又不能实现与哪些结点之间的通信？
5、对于一非线性流水线，其4行6列的预约表如下：
功能段
1
2
3
4
5
6
S1
√
√
S2
√
√
√
S3
√
√
S4
√
求出该流水线的最佳调度方案。
试卷五答案
二、应用题：
（共6题、共80分）
1．（15分）
解：
（1）L哈=2.99（位），R哈=（2.99-2.96）/2.99=1%（7分）
（2）L3/7=3.2（位），R3/7=7.5%；L2/8=3.1（位），R2/8=4.5%（8分）
2、（15分）
解：
（每小步5分）
Tbyte=np（TS+TD）=1024×5×（9.8+0.2）=51200（us）
Tblock=2×5×（9.8+512×0.2）=1122（us）
Tselect=5×（9.8+1024×0.2）=1073（us）
3、（15分）
解：
执行4个任务时：
TP=4/15Δt，E=40%，SP=1.6（7分）
执行40个任务时：
TP=40/123Δt，E=48.8%，SP=1.95（8分）
4、（15分）
解：
当第2级为直连时，PE5不能与输出2、3、6、7结点相连；（7分）
当第2级为交换时，PE5不能与输出0、1、4、5结点相连。
（8分）
6、（10分）
解：
状态图如下：
（5分）
最佳调度方案为（1，5）或（3），平均延时为3。
（5分）
试卷六
二．（15分）设一模型机有7条指令，它们的使用频度如下表所示。
请设计出指令的Huffman编码和只有两种码长的扩展操作码编码，求其平均码长和信息冗余量。
（已知H=1.95）
指令
I1
I2
I3
I4
I5
I6
I7
使用频度
0.45
0.30
0.15
0.05
0.03
0.01
0.01
三．（15分）为提高流水线的效率可采用哪两种主要技术途径来克服速度瓶颈？
现有3段流水线，各段经过时间依次为Δt、3Δt、Δt。
（1）分别计算在连续输入3条指令时和30条指令时的吞吐率和效率；
（2）按两种途径之一改进，画出你的流水线结构示意图。
四．（15分）在一个5功能段非线性流水线处理机上需经9△t才能完成一个任务，预约表如下：
时间t
1
2
3
4
5
6
7
8
9
K=1
∨
∨
K=2
∨
∨
∨
K=3
∨
K=4
∨
∨
K=5
∨
∨
求出流水线的最优调度方案及最小平均延迟时间和流水线的最大吞吐率。
五．（15分）画出N=8（0---7）个处理单元的间接二进制n方体多级互连网络图。
并指当K2K1K0=100时，输入端的第5号处理单元与输出端的哪一个处理单元相连？
六、（20分）在CRAY-1型向量处理机上，V为向量寄存器，长度为32；S为标量寄存器。
所用浮点功能部件的执行时间分别为：
加法需6拍，乘法需7拍，从存储器读数需6拍，打入寄存器需1拍，启动功能部件（包括存储器）需1拍。
问下列各指令组中的哪些指令可以链接？
哪些可以并行执行？
说明原因并分别计算各指令组全部完成所需的拍数。
（1）V0←存储器，V1←V2+V3，V4←V5×V6；
（2）V3←存储器，V2←V0×V1，V4←V2+V3；
试卷六答案
二．（15分）（已知H=1.95）
解：
由各条指令的使用频度构造Huffman树图略。
由此可求出Huffman编码和只有两种码长的扩展编码以及它们的码长如下表所示：
指令
使用频度
Huffman编码
码长
扩展编码
码长
I1
0.45
1
1
00
2
I2
0.30
01
2
01
2
I3
0.15
O01
3
10
2
I4
0.05
0001
4
1100
4
I5
0.03
00001
5
1101
4
I6
0.01
000001
6
1110
4
I7
0.01
000000
6
1111
4
Huffman编码平均码长为：
信息冗余量为：
（1.97-1.95）/1.97≈1.02%
扩展编码的平均码长为：
信息冗余量为：
（2.2-1.95）/2.2≈11.36%
三．（15分）
解：
（1）连续输入3条指令时，吞吐率和效率分别为
当连续输入30条指令时，流水线的吞吐率和效率分别为
（2）按方法一改进后的流水线示意图如下所示：
四．（15分）
解：
（1）初始冲突向量为C0=（10110001）。
（2）状态图如图所示。
（3）平均延迟最小的调度方案（3，4）。
最大吞吐率为
五．（15分）
解：
网络图如图所示。
输入5号与输出1号相连。
六、（20分）
解：
（1）这三条指令可并行执行。
执行时间为：
T=（1+7+1）+N-1=40（拍）。
（2）前二条指令可并行执行，再与第三条链接。
执行总的执行时间为：
T=（1+7+1）+（1+6+1）+N-1=48（拍）。
试卷七
2．（10分）Cache—主存系统，Cache有4页，主存有8页，采用组相联变换，每组2页，LRU替换算法，根据下列页地址流，画出调页情况，计算命中率。
1，2，3，1，3，7，0，1，2，5，4，6，4，7，2
3．（10分）有一个Cache存储器，主存有8块（0-7），Cache有4块（0-3），采用组相联映像，组内块数为2块。
采用LRU（近期最久未使用）替换算法。
（1）指出主存各块与Cache各块之间的映像关系。
（2）某程序运行过程中，访存的主存块地址流为：
2，3，4，1，0，7，5，3，6，1，5，2，3，7，1
说明该程序访存对Cache的块位置的使用情况，计算Cache命中率。
4．有一条静态多功能流水线由5段组成（如下图所示），加法用1、3、4、5段，乘法用1、2、5段，第2段的时间为2△t，其余各段时间均为△t，而且流水线的输出可以直接返回输入端或暂存于相应的流水线寄存器中。
若在该流水线上计算
f＝A1*B1+A2*B2+A3*B3+A4*B4,
（1）画出处理过程的时空图；
（2）计算其吞吐率、加速比和效率；
加法
（3）该流水线的瓶颈段是哪一段？
可用哪几种方法消除该瓶颈？
画出改进后的流水线。
试卷七答案
2.
．
123137012546472
1
中
中
4
中
0
5
2
7
6
2
3
中
2
7
命中率：
4/15
3.
（2）
Cache中的地址流为下图所示：
234107536152371
4
4*
0
0
0*
0
0
0*
5
5
5
5
5*
1
1*
1*
5
5*
5*
1
1*
1*
1*
1*
1
2
2*
2*
2*
2*
7
7
7*
6
6
6
6*
3
3*
3*
3
3
3
3
3*
3*
3
3*
3*
3*
2
2*
7
7
命中率：
2/15（1分）
4.
下图1、2、3、4进程是乘法，5、6、7进程是加法。
时间
流水级
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
5
1
2
3
4
5
6
7
4
5
6
7
3
5
6
7
2
1
1
2
2
3
3
4
4
1
1
2
3
4
5
6
7
（2）计算其吞吐率、加速比和效率（5分）；
吞吐率TP=N/TK=7/16
加速比=（3×4+4×3）/16=3/2=1.5
效率=（3×4+4×3）/（5×16）=3/10
（3）该流水线的瓶颈段是哪一段？
可用哪几种方法消除该瓶颈？
画出改进后的流水线。
（5分）
瓶颈段是第二段（1分），可用串行和并行两种方法（或说分割瓶颈法）消除瓶颈（1分）。
串行方法如下：
时间
流水级
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
5
1
2
3
4
5
6
7
4
5
6
7
3
5
6
7
2—2
1
2
3
4
2—1
1
2
3
4
1
1
2
3
4
5
6
7
试卷八
1．（5分）假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为0.9，则采用Cache后，能使整个存储系统获得的加速比是多少？
2．（10分）假设在一台40MHZ的处理机上运行200000条指令的目标代码，程序主要由四种类型的指令所组成。
根据程序跟踪实验结果，已知指令混合比和每类指令的CPI值如下表所示。
指令类型
指令混合比
CPI
算术和逻辑
60%
1
高速缓存命中的加载/存储
18%
2
转移
12%
4
高速缓存缺失的存储器访问
10%
8
（1）试计算用上述跟踪数据在单处理机上执行该程序时的平均CPI。
（2）根据
（1）所得到的CPI，计算相应的MIPS速率及程序的执行时间。
3．（15分）在一个具有五个功能级的流水处理机上，每级运行时间相等，每一个任务需经9拍才能完成，其预约表如下图所示。
（1）分别写出禁止向量和初始冲突向量
（2）画出流水线的调度状态图
（3）求出流水线的最小平均启动距离
（4）求出此流水线的最大吞吐率
（5）若按此调度方案输入六个任务，求实际吞吐率。
级号
1
2
3
4
5
6
7
8
9
S1
×
×
S2
×
×
升级会员 