计算机系统结构网上作业参考答案.doc

计算机系统结构作业参考答案
一、
1、 试述现代计算机系统的多级层次结构。
计算机系统具有层次性，它由多级层次结构组成。从功能上计算机系统可分为五个层次级别：
第一级是微程序设计级。这是一个硬件级，它由机器硬件直接执行微指令。
第二级是一般机器级，也称为机器语言级。它由微程序解释机器指令系统.这一级是硬件级。
第三级是操作系统级，它由操作系统程序实现。这些操作系统由机器指令和广义指令组成，这些广义指令是操作系统定义和解释的软件指令。这一级也称混合级。
第四级是汇编语言级。它给程序人员提供一种符号形式的语言，以减少程序编写的复杂性。这一级由汇编程序支持执行。
第五级是高级语言级。这是面向用户为编写应用程序而设置的。这一级由各种高级语言编译程序支持。

2、试述RISC设计的基本原则和采用的技术。
答：一般原则：
(1)确定指令系统时，只选择使用频度很高的指令及少量有效支持操作系统，高级语言及其它功能的指令，大大减少指令条数，一般使之不超过100条；
(2)减少寻址方式种类，一般不超过两种；
(3)让所有指令在一个机器周期内完成；
(4)扩大通用寄存器个数，一般不少于32个，尽量减少访存次数；
(5)大多数指令用硬联实现，少数用微程序实现；
(6)优化编译程序，简单有效地支持高级语言实现。
基本技术：
(1)按RISC一般原则设计，即确定指令系统时，选最常用基本指令，附以少数对操作系统等支持最有用的指令，使指令精简。编码规整，寻址方式种类减少到1、2种。
(2)逻辑实现用硬联和微程序相结合。即大多数简单指令用硬联方式实现，功能复杂的指令用微程序实现。
(3)用重叠寄存器窗口。即：为了减少访存，减化寻址方式和指令格式，简有效地支持高级语言中的过程调用，在RISC机器中设有大量寄存嚣，井让各过程的寄存器窗口部分重叠。
(4)用流水和延迟转移实现指令，即可让本条指令执行与下条指令预取在时间上重叠。另外，将转移指令与其前面的一条指令对换位置，让成功转移总是在紧跟的指令执行之后发生，使预取指令不作废，节省一个机器周期。
(5)优化设计编译系统。即尽力优化寄存器分配，减少访存次数。不仅要利用常规手段优化编译，还可调整指令执行顺序，以尽量减少机器周期等。

3、  试述全相联映像与直接映像的含义及区别 
（1） 全相连映像
  主存中任何一个块均可以映像装入到Cache中的任何一个块的位置上。主存地址分为块号和块内地址两部分，Cache地址也分为块号和块内地址。Cache的块内地址部分直接取自主存地址的块内地址段。主存块号和Cache块号不相同，Cache块号根据主存块号从块表中查找。Cache保存的各数据块互不相关，Cache必须对每个块和块自身的地址加以存储。当请求数据时，Cache控制器要把请求地址同所有的地址加以比较，进行确认。
（2） 直接映像
把主存分成若干区，每区与Cache大小相同。区内分块，主存每个区中块的大小和Cache中块的大小相等，主存中每个区包含的块的个数与Cache中块的个数相等。任意一个主存块只能映像到Cache中唯一指定的块中，即相同块号的位置。主存地址分为三部分：区号、块号和块内地址，Cache地址分为：块号和块内地址。直接映像方式下，数据块只能映像到Cache中唯一指定的位置，故不存在替换算法的问题。它不同于全相连Cache，地址仅需比较一次。
（3） 区别：
全相连映像比较灵活，块冲突率低，只有在Cache中的块全部装满后才会出现冲突，Cache利用率高。但地址变换机构复杂，地址变换速度慢，成本高。
直接映像的地址变换简单、速度快，可直接由主存地址提取出Cache地址。但不灵活，块冲突率较高，Cache空间得不到充分利用。

4. 画出冯∙诺依曼机的结构组成？

5. 试用图示法说明超标量、超流水线和超长指令字技术原理。

二、
某模型机由8条指令，使用频度为0.3 0.3 0.2 0.1 0.05 0.02 0.02 0.01试分别用哈夫曼编码和扩展编码对其操作码进行编码，限定扩展编码只能有两种长度，则它们的编码长度比定长操作码的长度减少多少？
答：

频度
Huffman
长度
扩展
长度
I1
0.3
00
2
00
2
I2
0.3
01
2
01
2
I3
0.2
10
2
10
2
I4
0.1
110
3
11000
5
I5
0.05
1110
4
11001
5
I6
0.02
11110
5
11010
5
I7
0.02
111110
6
11011
5
I8
0.01
111111
6
11100
5
定长编码长度：3
Huffman长度：(0.3+0.3+0.2)*2 + 0.1*3 + 0.05*4 + 0.02*5 + 0.02*6 0.01*6 = 2.38
长度减少3-2.38=0.62
扩展编码长度： (0.3+0.3+0.2)*2 + (0.1 + 0.05 + 0.02 + 0.02 +0.01) * 5 = 2.6
长度减少3-2.6=0.4

三．
设某个程序包含5个虚页，实页数为3，其页地址流为4，5，3，2，5，1，3，2，2，5，1，3。试画出FIFO、LRU、OPT 替换算法的时间状态图，写出各自的命中率。

答：

4
5
3
2
5
1
3
2
2
5
1
3
FIFO
4
4
4*
2
2
2
2
2
2
2*
2
2

5
5
5*
5*
1
1
1
1
1
1*
3

3
3
3
3*
3*
3*
3*
5
5
5

H

H
H
H

H

命中率5/12

4
5
3
2
5
1
3
2
2
5
1
3
LRU
4
4
4*
2
2
2*
3
3
3
3*
1
1

5
5
5*
5
5
5*
2
2
2
2*
3

3
3
3*
1
1
1*
1*
5
5
5*

H

H

命中率2/12

4
5
3
2
5
1
3
2
2
5
1
3
OPT
4
4
4*
2*
2
2
2
2
2*
5*
5
5

5
5
5
5*
1*
1
1
1
1
1
1

3
3
3
3
3*
3*
3
3
3
3

H

H
H
H

H
H
命中率6/12

四、（第三小问的解答和教材略有不同，如果不理解，也可参考教材193页原题）
在一个5段的流水线处理机上需经9拍才能完成一个任务，其预约表为：

T1
T2
T3
T4
T5
T6
T7
T8
T9
S1
√

√
S2

√
√

√

S3

√

S4

√
√

S5

√
√

分别写出延迟禁止表、冲突向量，画出流水线状态图，并给出平均延迟最小的调度方案。

答： 解：（1）根据初始冲突向量的构成方法，对预约表各行中打“×”的拍数求出差值，除去重复的后汇集在一起，即得到延迟禁止表为F =｛1，5，68｝。由F可得到初始冲突向量为：
C =（10110001）
（2）根据后继冲突向量的递推规则Cj = SHR（k）（Ci）∨C0则可得出所有的后继状态，具体有：
10110001 C0
10110111 C2
10111101 C1
10111011 C3
10111111 C5
C0四个后继状态：C1 =SHR（2）（C0）∨C0 = 10111101 7
C2 =SHR（3）（C0）∨C0 = 10110111
C3 =SHR（4）（C0）∨C0 = 10111011 3 2
C4 =SHR（7）（C0）∨C0 = 10110001=C0 7 4 7
C1二个后继状态：C5 =SHR（2）（C1）∨C0 = 10111111
C6 =SHR（7）（C1）∨C0 = 10110001=C0 7
C2二个后继状态：C7 =SHR（4）（C2）∨C0 = 10111011=C3 3 4 7 2
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
由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。
（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 TPmax = 1/（3.5△t）= 0.286/△t
3，（4，3） （4+3）△t/2 = 3.5△t

（4）按最优调度策略[3，（4，3）]连续输入8个任务时，流水线的实际吞吐率为：
TP = 8/[（3 + 4 + 3 + 4 + 3 + 4 + 3 + 9）△t] = 0.24/△t

[此文档可自行编辑修改，如有侵权请告知删除，感谢您的支持，我们会努力把内容做得更好]