计算机系统结构综合题.doc

计算机系统结构综合题

1.一个处理机共有10条指令，各指令在程序中出现的概率如下表：

(1)采用最优Huffman编码法（信息熵）计算这10条指令的操作码最短平均长度。(2)采用Huffman编码法编写这10条指令的操作码，并计算操作码的平均长度，计算与最优Huffman编码法（信息熵）相比的操作码信息冗余量。将得到的操作码编码和计算的结果填入上面的表中。(3)采用2/8扩展编码法编写这10条指令的操作码，并计算操作码的平均长度，计算与最优Huffman编码法相比的操作码信息冗余量。把得到的操作码编码和计算的结果填入上面的表中。

(4)采用3/7扩展编码法编写这10条指令的操作码，并计算操作码的平均长度，计算与最优Huffman编码法相比的操作码信息冗余量。把得到的操作码编码和计算的结果填入上面的表中。

[解答]

0.020.03

0.02

0.03

0.04

0.05

0.08

0.08

0.1

0.15

0.20

0.25

0.05

0.09

0.13

0.17

0.23

0.32

0.43

0.57

1.0

0

0

1

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

指令序号

出现的概率

Huffman编码法

2/8扩展编码法

3/7扩展编码法

I1

0.25

00

00

00

I2

0.20

10

01

01

I3

0.15

010

1000

10

I4

0.10

110

1001

11000

I5

0.08

0110

1010

11001

I6

0.08

1110

1011

11010

I7

0.05

1111

1100

11011

I8

0.04

01110

1101

11100

I9

0.03

011110

1110

11101

I10

0.02

011111

1111

11110

操作码的平均长度

2.99

3.1

3.2

操作码的信息冗余量

1.1%

4.6%

7.6%

2.一个虚拟存储器按字节编址，最多有128个用户，每个用户最多要用2048页，每页512字节。主存容量8M字节，快表按地址访问，共16个存储字，快表地址码经散列变换得到，为减少散列冲突，快表分为两组，有两套独立的相等比较电路。试：

写出多用户虚地址和主存地址的格式，并给出各字段的长度。

散列变换部件的输入、输出位数各为多少？每个相等比较电路的位数是多少？

快表每个存储字的总长度为多少位？为哪几个字段？各字段的长度为多少位？

[解答]

虚地址的长度为27位，格式如下：

主存的地址需要23位：格式如下

由于用户号和虚页号共有18位，所以，散列变换的输入需要18位，而输出的为快表的地址，如果我们假设快表是按照字寻址，那么是3位（快表分为两组，每组8个存储字）。或4位（16个存储字，每字两个入口）。相等比较电路需要比较多用户虚页号，以消除散列冲突，所以，相等比较电路需要18位。

快表中需要存储两项内容：多用户虚页号和实页号。多用户虚页号为18位，实页号为14位，共有32位。

3.用一条5个功能段的浮点加法器流水线计算。每个功能段的延迟时间均相等，流水线的输出端和输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，要求：

列出进行加法的次序；

画出流水线时空图；

并计算流水线在此任务中的实际吞吐率、加速比和效率。

[解答]

（1）首先需要考虑的是，8个数的的和最少需要做几次加法。我们可以发现，加法的次数是不能减少的：7次；于是我们要尽可能快的完成任务，就只有考虑如何让流水线尽可能充满，这需要消除前后指令之间的相关。由于加法满足交换率和结合率，我们可以调整运算次序如以下的指令序列，我们把中间结果寄存器称为R，源操作数寄存器称为A，最后结果寄存器称为F，并假设源操作数已经在寄存器中，则指令如下：

I1： R1←A1+A2

I2： R2←A3+A4

I3： R3←A5+A6

I4： R4←A7+A8

I5： R5←R1+R2

I6： R6←R3+R4

I7： R7←R5+R6

（2）这并不是唯一可能的计算方法。假设功能段的延迟为Δt。时空图如下，图中的数字是指令号：

（3）整个计算过程需要18Δt，所以吞吐率为：

加速比为：

效率为：

=0.39

4.一条3个功能段的非线性流水线及其预约表如下：

S

S1

S2

S3

输入

输出

△t

△t

△t

时间

流水段

1

2

3

4

5

S1

×

×

S2

×

×

S3

×

×

⑴写出流水线的禁止向量和初始冲突向量，并画出调度流水线的状态图。

⑵求流水线的最小启动循环和最小平均启动距离。

⑶通过插入非计算延迟功能段使该流水线达到最优调度