系统结构试题

一、（20分）选择题:

1、在计算机系统结构来看，机器语言程序员看到的机器属性是（C)0

A）计算机软件所要完成的功能B）计算机硬件的全部组成

C）编程要用到的硬件知识D）计算机各部件的硬件实现

2.对汇编语言程序员透明的是（A

A）I/O方式中的DMA访问方式B）浮点运算

C）程序性中断D）存取操作数

3.用循环表示PM2-1的互连函数,应该是（A）o

A)(6420)(7531)B)(0246)(1357)

C)(01234567)D)(76543210)

4.在提高CPU性能的问题上，从系统结构角度，可以（C）。P10

A）提高时钟频率B）减少程序指令条数

C）减少每条指令的时钟周期数D）减少程序指令条数和减少每条指令的时钟周期数

5.能实现指令、程序、任务级并行的计算机系统属于（D）o

A）SISDB）SIMDOMISDD）MIMD

6.计算机系统结构不包括（A）。P4

A）主存速度B）机器工作状态C）信息保护D）数据表示

7、”一次重叠“中消除"指令相关"最好的方法是（A）。

A）不准修改指令B）设相关专用通路C）推后分析下条指令D）推后执行下条指令

8、重叠寄存器技术主要用于解决在RISC系统中因（B）而导致的问题。P121

A）JMP指令影响流水线B）CALL指令的现场保护

0只有I0AD和ST0RF指今带来的访问存储器不便D）存储器访问速度

10、推出系列机的新机器，不能更改的是（A）0

A）原有指令的寻址方式和操作码B）系统的总线的组成

C）数据通路宽度D）存储芯片的集成度

11.在流水机器中，全局性相关是指（D）o

A）先写后读相关B）先读后写相关C）指令相关D）由转移指令引起的相关

12.下列说法不正确的是（D）o

A）线性流水线是单功能流水线B）动态流水线是多功能流水线

C）静态流水线是多功能流水线D）动态流水线只能是单功能流水线

13.结构不对称的静态互联网络是是（A）。

A）线性阵列B）环网O立方体网络D）全连接网络

14.在系统结构设计中，提高软件功能实现的比例会（C）o

A）提高解题速度B）减少需要的存储容量C）提高系统的灵活性D）提高系统的性能价格比

15.多处理机主要实现的是（B）oP500

A）指令级并行B）任务级并行0操作级并行D）操作步骤的并行

16.虫蚀寻径以流水方式在各寻径器是顺序传送的是（0）。

A）消息B）包C）片D）字节

17、BSP计算机的并行处理机有16个处理单元，并行存储器的存储体个数为（D）。P463

A）16B）1032D）17

20^ILLIACIV是一种（C）o

A）流水线处理机B）指令重叠处理机C）阵列处理机D）多处理机

二、G0分）判断题:

1.对计算机系统中经常使用的基本单元功能，宜于用软件来实现，这样可降低系统的成本。

（F）

2.由于RISC简化了指令系统，因此，RISC上的目标程序比CISC上的目标程序要短一些，程

序执行的时间就会少一些。（F）

3.流水线调度是看如何调度各任务进入流水线的时间，使单功能线性流水线有高的吞n二率和

效率。（T）

4.无论采用什么方法，只要消除流水线的瓶颈段，就能提高流水线的吞吐率和效率。（F）

5.在满足Cache与主存的一致性方面，写回比写直达法好。（F）

6、在多处理机上，各个任务的执行时间不同时，在个处理机总的运行时间均衡的前提下，取

不均匀分配，让各处理机所分配的任务数要么尽量的多，要么尽量的少，这样，才可使总的

运行时间减少。（「）

7、Cache组相联映象的块冲突概率比直接映象的高。（F）

8、要使线性流水线的实际吞吐率接近于理想的最大吞吐率，应将子过程数分得越多越好。（F）

9、在系列机内可以将单总线改为双总线，以减少公共总线的使用冲突。（F）

10、0-15共16个处理单元用Cube2单级互连网络互连，第10号处理单元将连到第8号处理

单元。（F）

三、（10分）如果某计算机系统有3个部件可以改进，则这三个部件经改进后的加速比分别

为:S1=30,S2=20,S3=10o

（1）如果部件1和部件2改进前的执行时间占整个系统执行时间的比例都为30$,那么，部

件3改进前的执行时间占整个系统执行时间的比例为多少，才能使3个部件都改进后的整个

系统的加速比Sn达到10

（2）如果3个部件改进前执行时间占整个系统执行时间的比例分别为30%、30%和20%,那么，

3个部件都改进后系统的加速比是多少未改进部件执行时间在改进后的系统执行时间中占的

比例是多少

由此可以得到7条指令的编码分别如下:

指令出现的频率编码

135%00

225%01

320%10

410%110

55%1110

63%11110

72%11111

这样，采用Huffman编码法得到的操作码的平均长度为:

H=2X+++3X+4X+5X+

=+++

（2）设计8位字长的寄存器•寄存器型变址寻址方式指令如下

,因为只有8个通用寄存器，所以寄存器地址需3位，操作码只

有两位，设计格式如下：

233

操作码0P源寄存器R1目的寄存器R2

三条指令的操作码分别为00,01,10

设计16位字长的寄存器•存储器型变址寻址方式指令如下:

4318

操作码OP通用寄存器变址寄存器偏移地址

四条指令的操作码分别为1100,1101,1110,1111

题:一个程序由5个虚页组成，采用LFU替换算法，在程序执行过程中，依

次访问的意味地址流如下：

4,5,3,2,5,1,3,2,3,5,1,3

1）可能的最高页命中率是多少？

2）至少要分配给该程序多少个页面才能获得最高的命中率.

3）如果在程序执行过程中每访问一个页面，平均要对该页面内的存

储单元1024次，求访问存储单元的命中率.

解答：

（1）由于在页地址流中互不相同的页共有5页，因此可能的最高页命中率

为：HNi=__1_2_-_5___7___

12"12

（2）由于LFU算法为堆栈型替换算法，即随着分配给该程序的主存页面数

减少，其命中率单调递减，因此，可采用逐渐减少所分配的主存页数

的方法进行推算：若分配N个页面时可获得最高命中率，但分配N・1个

页面时命中率却减少，这时我们可以得出分配给N个主存页面才能荻得

最高命中率的结论.

时间123456789101112

页地址流453251323513

4444*4*11111*11

5555555*5*555

LFUN=4

3333*333333

命中7次

2222*2222*2*

进进进进中换中中中中中中

时间123456789101112

页地址流453251323513

444*222*33333*3

555*555*222*11

LFUN=3

333*111*1*555*

命中3次

进造进换中换换换中换换中

（3）访问存储单元的命中率为:

1024x12—5

HJ.99959

,—1024x12

五、（10分）在页式虚拟存储器中，一个程序由P1〜P6共6个页面组成，系统分

配给这个程序的主存只有4个页面。在程序开始执行之前，P1至P4已经装入主

存。程序执行过程中依次访问到的页面如下：P1,P2,P3,P4,P5,P3,P6,P5,

P2,P1,P5,P2,P4,P10采用LRU页面替换算法对这4页主存进行调度。

⑴画出主存页面替换和命中的情况表。

⑵计算两种页面替换算法的页命中率。

⑶假设每个数据平均被访问10次，采用LRU页面替换算法，为了使页面失效率小于10-5.

计算页面大小至少应该为多少

六、（10分）有一个4段流水线，如下图所示：

TTS2fS3S4f

其中，段S1和S3的执行时间均为200ns，段S2和S4的执行时间均为100ns。

（1）分别使用公式和时空图求连续流入4条指令的实际吞吐率和效率。

（2）若瓶颈段S1可使用细分方法改造，瓶颈段S3可使用并联方法改造，对改造后的流水线,

分别使用公式和时空图求连续流入4条指令的实际吞吐玉和效率

解：

(1)使用公式计算如下:

n41

TP1=-------------------=----------------------------------------=-------------

£Ati+(n-1)AQ(200+100+200+100)+(4-1)X200300

i-1

Atj4X(200+100+200+100)

E1=------------------*=-----------------------------------------------=0.5

k

k£Ati+(n-1)A^j4X[(200+100+200+100)+(4-1)X200]

改造前时空图:

S41234

S311223344

S21234

S111223344

可得;

TP1=4Z(12At)=4/(12X100)=1/300

E1=(8At+4At+8At+4At)/(4X12At)=0.5

(2)改造后的时空图(公式计算略)：

S41234

S322244

S311133

S21234

S121234

S111234

可得:

TP2=4/(9At)=4/(9X100)=1/22.5

E2=(6X4At)/(6X9At)=0.44

七、（10分）设向量长度均为64.在CRAY-1机上所用浮点功能部件的执行时间分别为：相加

6拍，相乘7拍，求倒数近似值14拍；从存储器读数6拍，打入寄存器及启动功能部件各1

拍，问下列各指令组,组内的哪些指令可以链接哪些指令不可链接不能链接的原因是什么：

分别计算出各指令组全部完成所需要的拍数。

（1）V0-存储器(2)V24-V0*V1(3)V0—存储器(4)V0-存储器

V14-V2+V3V34-存储器V2^-V0*V1V1I/V0

V4—V5*V6V4―V2+V3V3W2+V0V34-V1*V2

V5—V3+V4V54-V3+V4

解:⑴第我而蚕箱令与第二条向量指令有源目向量相关，可以链接执行;

第一条向量指令与第二、三条向量指令无关，可以与它们并行执行。

16117164-1—79柏

启动访存访存存V3送浮加部件浮加存V4第存V4其

一分量它分量

送浮素部浮乘淬乘存V2送浮

件加部件

（2）三条向量指令都无关，所以，三条向量指令可以并行执行。

161164-1—72拍

启动访存访存存V0存V4第存V4其它

送江加部件淬加存V1一分量分量

送浮加部件浮乘洋乘

送停乘部件

送浮乘部件

（3）第二条向量指令与第一条向量指令有源目向量相关，可以链接执行；第

三条向量指令与第二条向量指令有源向量冲突，故只能等到第二条向量指

令执行完毕后，才能执行第三条向量指令。

16117164-116164-1=151拍

启动访存送浮乘部件浮存送浮加部件浮存

存

访存V0遂浮乘部件乘V2送浮加部件V3

注意：1）在分析向量指令的处理时，特别关注无关向量指令的并行执行，

源目向量相关的向量指令的锥接执行，除源目向量相关外其它发生向量寄存

器冲突的向量指令的串行执行，功能部件冲突的向量指令的串行执行以及向

量内部各分量流水处理之间的区别。

2）启动、输出延迟（各1拍）

八、（10分）假定有128个处理器，采用PM2I多级网络互连，若网络中的i=2的1级损坏，拟

用Cubei多级网络代替损坏的这一级，试说明最多需要几级Cubei网络5

［分析］：已知PM2I和兔心鼾的互连函数分别为：

3

PM2±j(X)=X+2'modN#4,0<=X<=N-1,n=log2N,0<=i<=n-1

上乂卜禽(甚好1・・・Xj・・・…工…XiX0

由题意，有N=128,n=log2N=7,PM2I多级网络i=2级实现的互连为：

2

PM2+2(X)=X+2=X+4mod1280<=X<=127

用二进制表示该级网络的输入端和输出端的编号，实现的互连为：

PM2+2(X6X5X4X3X2X1XO)=X6X5X4X3X2X1XO+1OOmod128

若PM2I多级网络中,PM2我级损坏抑Qufa闻多级网络代替,即要求QyJ刈

多级网络能实现PM2校指定的互连.

对于Cube侈级网络的128个输入端中所有X2=0的输入端，有：

PM2+2(X6X5X4X3X2X1XO)=X6X5X4X3X2X1XO+1OOmod128

=x6x5x4x3x2x1x0

=Cube2(x6x5x4x3x2x1x0)

则只需1级Cub岛网络并实现Cube?就可以代替PM2也指定的连接.

对于Cube侈级网络的128个输入端中所有乂2=1、X3R的输入端，有：

PM2+2(X6X5X4X3X2X1XQ)=X6X5X4X3X2X1XO+1OOmod128

=x6x5x4x3x2x1x0

=CubegtCub^fXsXgX^XgX!XQ))

则只需2级Qub助网络并实现Cube3(Cube2)就可以代替PM2+2指定的连接.

对于Qjbe侈级网络的128个输入端中所有X2=1、x3=1,X4=0的输入端，有:

PM242(X6X5X4X3X2X1XQ)=X6X5X4X3X2X1XO+1OOmod128

=XgXgX^XgX^o

=Cube4(Cube3(Cube2(x6x5x4x3x2x1x0)))

则只需3级6*禽网络并实现Cube，Cube3(Cube2))就可以代替PM2也指定

的连接.

对于Cyhl多级网络的12的输入端中所有9=乂3=乂4=1>%=0的输入端南：

PM2+2(X6X5X4X3X2X1XQ)=&&a±&*1乂0+100mod128

=x6x5x4x3x2x1x0

=Cube5(Cube4(Cube3(Cube2(x6x0x4x3x2x1xo))))

则只需4级加西网^>^<Cube5(Cube4(Cube3(Cube2))m^T以代替

PM2+2指定的连接.

对于《曲鼬多级网络的12衿输入端中所有。=乂3=乂4=)(5=1、4=0的输入端,

有：

PM2+2(X6X5X4X3X2X1XQ)=X6X5X4X3X2X1XO+1OOmod128

=X6X5X4X3X2X1X0

=Cube6(Cube5(Cube4(Cube3(Cube2(x6x5x4x3x2x1x0)))))

则需5级Cy%j网^^^<Cube6(Cube5(Cube4(Cube3(Cube2)))m^以代

替PM2也指定的连接.

因此，最多需要5级念由后网络代替PM2+2指定的连接.

九、(10分)A和B都是元素为浮点表示的64X64的二维数组，一次浮点加法的计算过程可

由取数、求阶差、对阶、尾数加、规格化和存数共6个段组成，若每个段的执行时间均为△

工请分别求出在下列结构不同的处理机上