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

1. 一个处理机共有 10 条指令,各指令在程序中出现的概率如下表: (1) 采用最优 Huffman 编码法(信息熵)计算这 10 条指令的操作码最短平均长度。(2) 采用 Huffman 编码法编写这 10 条指令的操作码,并计算操作码的平均长度,计算与最优 Huffman 编码法(信息熵)相比的操作码信息冗余量。将得到的操作码编码和计算的结果填入上面的表中。(3) 采用 2/8 扩展编码法编写这 10 条指令的操作码,并计算操作码的平均长度,计算与最优 Huffman 编码法相比的操作码信息冗余量。把得到的操作码编码和计算的结果填入上面的表中。(4) 采用 3/7 扩展编码法编写这 10 条指令的操作码,并计算操作码的平均长度,计算与最优 Huffman 编码法相比的操作码信息冗余量。把得到的操作码编码和计算的结果填入上面的表中。[ 解答] 采用最优 Huffman 编码法(信息熵)的操作码最短平均长度为: 957 .2 log pH n1i p2i i??????指令序号出现的概率 Huffman 编码法 2/8 扩展编码法 3/7 扩展编码法 I0. 25 00 00 00 I0. 20 10 01 01 0 010 0 0 0 0 0 01 1 1 1 1 111 I0. 15 010 1000 10 I0. 10 110 1001 11000 I0. 08 0110 1010 11001 I0. 08 1110 1011 11010 I0. 05 1111 1100 11011 I0. 04 01110 1101 11100 I0. 03 011110 1110 11101 I0. 02 011111 1111 11110 操作码的平均长度 操作码的信息冗余量 1 .1% % % 2. 一个虚拟存储器按字节编址, 最多有 128 个用户, 每个用户最多要用 2048 页, 每页 512 字节。主存容量 8M 字节, 快表按地址访问,共 16 个存储字, 快表地址码经散列变换得到, 为减少散列冲突,快表分为两组,有两套独立的相等比较电路。试: (1) 写出多用户虚地址和主存地址的格式,并给出各字段的长度。(2) 散列变换部件的输入、输出位数各为多少?每个相等比较电路的位数是多少? (3) 快表每个存储字的总长度为多少位?为哪几个字段?各字段的长度为多少位? [ 解答](1) 虚地址的长度为 27 位,格式如下: 0 26 用户号( 0- 127 )虚页号( 0- 2047 )页内偏移地址( 0- 511 ) 8 19 主存的地址需要 23 位:格式如下 0 22实页号( 0- 16383 )页内偏移( 0- 511 ) 8 (2) 由于用户号和虚页号共有 18 位,所以,散列变换的输入需要 18 位,而输出的为快表的地址,如果我们假设快表是按照字寻址,那么是 3 位(快表分为两组,每组 8 个存储字)。或4 位( 16 个存储字,每字两个入口) 。相等比较电路需要比较多用户虚页号,以消除散列冲突,所以,相等比较电路