衡水学院计算机体系结构资料整理.docx

衡水学院计算机体系结构资料整理.docx

《衡水学院计算机体系结构资料整理.docx》由会员分享，可在线阅读，更多相关《衡水学院计算机体系结构资料整理.docx（17页珍藏版）》请在冰点文库上搜索。

衡水学院计算机体系结构资料整理

历年试题整理版

一、名词解释（每题3分，共15分）

系列机：

在一个厂家生产的具有相同的体系结构，但具有不同的组成和实现的一系列不同型号的机器。

强制性失效：

当第一次访问一个块时，该块不在Cache中，需要从下一级存储器中调入Cache，这就是强制性失效。

失效率：

CPU访存时，在一级存储器中找不到所需信息的概率。

定向技术：

p101。

2

透明性：

在计算机技术中，对本来存在的事物或属性，从某一角度来看又好像不存在的概念称为透明性。

堆栈型机器：

每条ALU指令显示表示的操作数个数为0，运算结果的目的地是堆栈，访问操作数的方法是PUSH/POP

失效开销：

数据相关：

当指令在流水线中重叠执行时，流水线有可能改变指令读/写操作的顺序，使得读/写操作顺序不同于它们非流水实现时的顺序，将导致数据相关。

通道处理机：

RAID：

同构型多处理机：

由多个同种类型、至少同等功能的处理机组成、同时处理同一作业中能并行执行的多个任务的机器。

计算机体系结构：

程序员所看到的计算机的属性，即概念性结构与功能特性。

向量处理机：

处理机具有向量数据表示，并通过向量指令对向量的各元素进行处理。

二、填空（每空1分，共20分）

1、数据相关有三种：

（写后读相关）、（写后写相关）和（读后写相关）。

2、从处理数据的角度，并行性等级可以分为：

字串位串、（字串位并）、（字并位串）和全并行。

3、在存储层次中，映象规则有（p183）、（）和（）。

5、设有一个“Cache-主存”层次，Cache为4块，主存为8块；试分别对于以下2种情况，计算访存块地址为5时的索引（index）。

（1）组相联，每组两块；索引为（）

（2）直接映象；索引为（）。

6、对向量的处理有（p123）方式、（）方式、（）方式。

7、根据CPU内部存储单元类型，可将指令集结构分为（p37）型指令集结构、（）型指令集结构和（）型指令集结构。

1、流水线相关有三种：

（结构相关）、（数据相关）和（控制相关）。

2、从执行程序的角度看，并行性等级可以分为：

（p18）、（）、（）和作业或程序级并行。

3、在存储层次中，常用的替换算法有（p187）、（）和（）。

4、计算机系统中提高并行性的技术途径有（p19）、（）和（）三种，在高性能单处理机的发展中，起主导作用的是（）这个途径。

5、按照产生失效的原因不同，可把失效分为（p198）失效、（）失效和（）失效三类。

3、按照流水线所完成的功能来分，流水线可分为（p79）和（）。

4、存储层次中，地址映象方法有（p183）、（）和（）等三种。

2、存储器层次结构设计技术的基本依据是程序的（速度和容量）。

4、2：

1Cache经验规则是指大小为N的（p204）Cache的失效率约等于大小为N/2的（）Cache的失效率。

6、从编译技术的角度来考虑，降低流水线分支损失的方法主要有（p114）、（）和（）方法。

三、简答题（每题5分，共25分）

1、调度分支延迟指令有哪三种常用方法？

它们各有什么优缺点。

P116

2、表示寻址方式的主要方法有哪些？

简述他们的优缺点。

P5

3、简述“Cache-主存”层次与“主存-辅存”层次的区别。

P182

4、试举例说明DLX流水线中存在不能依靠定向技术解决的数据相关及其解决方法。

5、试从3C失效的关系分析增加块大小对Cache性能的影响。

P201

1、写出三级Cache的平均访问时间的公式。

解：

平均访存时间＝命中时间＋失效率×失效开销

只有第I层的失效时才会访问第I＋1

设三级Cache的命中率分别为HL1、Hl2、HL3，失效率分别为Ml1、Ml2、ML3，第三级Cache的失效开销为PL3。

平均访问时间TA＝HL1＋Ml1{Hl2＋Ml2（HL3＋ML3×PL3）}

2、软件兼容有几种？

其中哪一种是软件兼容的根本特征？

3、试从目的、技术途径、组成等3个方面对同构型多处理机和异构型多处理机作一简单比较（列表）。

P22

5、降低Cache失效率有哪几种方法（至少写出5种）？

5.3

1、给出减少Cache失效开销的三种方法，并简述其基本思想。

5.2

2、数据相关有哪几种类型？

解决数据相关有哪些主要方法？

p100

5、写出伪想联Cache的平均访存时间公式（设伪命中Cache需2个额外的周期）p207

1、任写出三种Cache的优化技术，并简述其基本思想。

P212-p214

2、在指令集结构设计中，应该考虑哪些主要问题？

p44

4、试以系列机为例，说明计算机体系结构、计算机组成和计算机实现三者之间的关系p6-8

1、计算机体系结构设计和分析中最经常使用的三条基本原则是什么？

并说出它们的含义。

P15？

4、按照产生失效的原因不同，Cache失效可以分成哪三类？

各是什么含义？

p198

5、解决多处理机系统中的Cache一致性问题可采用哪些方法？

叙述它们的优缺点。

四、（6分）指令的动态调度有哪两种方法？

二者的核心思想各是什么？

答：

1、记分牌的核心思想：

允许暂停之后的指令提前处理（译码→发射指令和读取操作数）

允许乱序执行，从而乱序完成；

ID段检测所有的结构相关。

2、Tomasulo算法的核心思想：

（1） 分布的阻塞检测逻辑机制；

（2） 消除了数据的写后写和先读后写相关导致的阻塞

四、（20分）有一条静态多功能流水线由5段组成（见下图），加法用1、3、4、5段，乘法用1、2、5段，第2段的时间为2△t，其余各段时间均为△t，而且流水线的输出可以直接返回输入端或暂存于相应的流水线寄存器中。

若在该流水线上计算f＝（A1+B1）*（A2+B2）*（A3+B3）*（A4+B4）,（3）

（1）画出处理过程的时空图；

（2）计算其吞吐率、加速比和效率；

（3）该流水线的瓶颈段是哪一段？

可用哪几种方法消除该瓶颈？

画出改进后的流水线。

解：

本题解题的关键是弄清楚机器一共要做4次加法，3次乘法，而且应进行适当的指令调度，以得到最大的吞吐率。

（1）相应的时空图为：

（2）TP＝7/（23△t）

E＝（5×7）/（6×23）＝35/138

五、（10分）

根据Amdahl定律写出系统加速比的公式；

某计算机系统有两个部件可以改进，这两个部件的加速比为：

部件加速比1＝30；部件加速比2＝20；

如果部件1和部件2的可改进比例分别为30％和40％，求整个系统的加速比。

六、（10分）给定以下的假设，试计算直接映象Cache 和两路组相联Cache的平均访问时间以及CPU时间。

（1）理想Cache（命中率为100%）情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.2次；

（2）两种Cache容量均为1KB，块大小都是32字节；

（3）组相联Cache中的多路选择器使CPU的时钟周期增加了10％；

（4）这两种Cache的失效开销都是40个时钟周期；

（5）命中时间为1个时钟周期；

（6）1KB直接映象Cache的失效率为13.3％，1KB两路组相联Cache的失效率为10.5％。

解：

平均访问时间＝命中时间＋失效率×失效开销

平均访问时间1-路=2.0+1.4%*80=3.12ns

平均访问时间2-路=2.0*（1+10%）+1.0%*80=3.0ns

两路组相联的平均访问时间比较低

CPUtime=（CPU执行+存储等待周期）*时钟周期

CPUtime=IC（CPI执行+总失效次数/指令总数*失效开销）*时钟周期

=IC（（CPI执行*时钟周期）+（每条指令的访存次数*失效率*失效开销*时钟周期））

CPUtime1-way=IC（2.0*2+1.2*0.014*80）＝5.344IC

CPUtime2-way=IC（2.2*2+1.2*0.01*80）＝5.36IC

相对性能比：

5.36/5.344=1.003

直接映象cache的访问速度比两路组相联cache要快1.04倍，而两路组相联Cache的平均性能比直接映象cache要高1.003倍。

因此这里选择两路组相联。

五、将计算机系统中某一功能的处理速度加快10倍，但该功能的处理时间仅为整个系统运行时间的40%，则采用此增强功能方法后，能使整个系统的性能提高多少？

（5分）系统加速比=1.56

六、（15分）假设当按直接映象位置没有发现匹配，而在另一个位置才找到数据（伪命中）时，需要2个额外的周期，而且不交换两个Cache中的数据。

Cache参数如下：

容量128KB；

直接映象情况下命中时间为1个时钟周期，失效开销为50个时钟周期；

时钟周期2路＝1.10×时钟周期1路

直接映象失效率为0.010，两路组相联失效率为0.007；

问：

当直接映象、两路组相联映象和伪相联映象这三种组织结构时，速度各是多少？

2、（15分）假定Cache的失效开销为50个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是2.0个时钟周期，访问Cache失效率为2%，平均每条指令访存1.33次。

求没有Cache和有Cache两种情况下的平均指令执行时间。

4、计算机A和计算机B具有相同的指令系统。

执行同一个程序时，计算机A的时钟周期为1.1ns，CPI为2.0，计算机B的时钟周期为2ns，CPI为1.3。

请问执行这个程序时，哪个机器更快？

（9分）

一、（10分）已知有以下的测量结果：

FP指令（不包括FPSQR指令）的执行频度＝25％

FP指令的平均CPI＝4.0

其它指令的平均CPI＝1.33

FPSQR指令的执行频度＝2％

FPSQR指令的CPI＝20

假设有两种改进方案，其中方案一是将FPSQR指令的CPI降到2，方案二是把FP指令的平均CPI降至2.5。

试运用CPU性能公式比较这两种改进方案的优劣。

解：

首先可以观察到只有CPI改变了，而时钟频率和指令数保持不变。

我们先计算改进前系统的CPI：

CPIoriginal=

=（4×25%）+（1.33×75%）

=2.0

我们可以用改进前的CPI减去由于改进FPSQR功能而减少的时钟周期得到改进后FPSQR指令的CPI：

CPIwithnewFPSQR=CPIoriginal–2%×（CPIoldFPSQR–CPIofnewFPSQRonly）

=2.0–2%×（20–2）

=1.64

我们也可以用同样的方法计算改进全部FP方案得到的CPI，或者也可以将FP的CPI值和非FP的CPI值相加得到。

利用后一种方法如下：

CPInewFP=（75%×1.33）+（25%×2.5）

=1.625

因为通过改进所有FP方案所带来的CPI更小，所以这种方案的性能更好。

改进全部FP的加速比是：

。

五、（8分）在处理器N=8的Omega网络中，实现置换∏＝（0，1，3，2，5，6，7）（4），画出其开关的设置，指出被阻塞的开关。

六、（7分）考虑一个拥有4个处理机的UMA系统，每个处理机都有一个写回Cache（write-backCache），对于下列事件序列，写出该系统使用写作废（writeinvalidate）协议时Cache的值和状态。

（1）处理机0读地址1000H单元的值12H；

（2）处理机2向地址1000H单元写数据34H；

（3）处理机1读地址1000H单元的值；

（4）处理机0向地址1000H单元写数据56H；

（5）处理机3读地址1000H单元的值；

（6）处理机1向地址1000H单元写数据78H；

（7）处理机1读地址1000H单元的值。

解：

Action

Result

Cache0

Cache1

Cache2

Cache3

Shared

P0read

Readmiss

1000:

12H,E

1000:

12H

P2write

Writemiss

1000:

XXI

1000:

34H,M

1000:

12H

P1read

Readmiss

1000:

34H,S

1000:

34H,S

1000:

34H

P0write

Writemiss

1000:

56H,M

1000:

XXI

1000:

XXI

1000:

34H

P3read

Readmiss

1000:

56H,S

1000:

56H,S

1000:

56H

P1write

Writemiss

1000:

XXI

1000:

78H,M

1000:

XXI

1000:

56H

P1read

Readhit

1000:

78HM

1000:

78H

七、（12分）假设Cache的块长为1字（32位），存储器总线宽度为1字，Cache的失效率为15%，每条指令平均访存1.2次。

Cache命中时指令执行时间为2个周期。

Cache的失效时间为8个时钟周期。

（1）求指令平均执行时间；

（2）如果将块长改为2字后，失效率降低到10%，求指令平均执行时间；

（3）在

（2）的基础上，对存储器采用2路多体交叉技术，求指令平均执行时间；

（4）在

（2）的基础上，将总线宽度改为64位，求指令平均执行时间。

八、（15分）一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10微秒、30微秒、30微秒、50微秒和75微秒向通道发一次数据传送的服务请求，请回答下列问题：

（清华P244）

1、计算这个字节多路通道的实际流量和工作周期。

2、如果设计字节多路通道的最大流量正好等于通道实际流量，并假设对数据传输率高的设备，通道响应它的优先级也高。

5台设备在0时刻同时向通道发出第一次传送数据的请求，并在以后的时间里按照各自的数据传输率连续工作。

画出通道分时为各台设备服务的时间关系图，并计算这个字节多路通道处理完各台设备的第一次数据传送请求的时刻。

3、从时间关系图上发现什么问题？

如何解决这个问题？

九、（30分）现有如下DLX代码：

LOOP：

LDF0，0（R2）

LDF4，0（R3）

MULTDF0，F0，F4

ADDDF2，F0，F2

SD0（R2），F2

ADDIR2，R2，#8

ADDIR3，R3，#8

SUBIR5，R4，R2

BNEZR5，LOOP

其中，R4的初值是R2+396。

假设：

在整个代码序列的运行过程中，所有的存储器访问都是Cache命中，并且对同一寄存器的读操作和写操作可以在同一个时钟周期中进行。

利用改进的DLX流水线和浮点运算流水线（结构图如下，假设图中每个方框的执行时间为一个时钟周期），计算：

1、假设没有任何其它定向路径的支持，且分支指令采用排空流水线的策略，请画出该指令序列执行的流水线时空图，并计算执行上述循环需要的时钟周期数。

2、假设该DLX流水线有正常的定向路径，且分支指令采用预测分支失败的策略，请画出该指令序列执行的流水线时空图，并计算执行上述循环需要的时钟周期数。

3、该DLX流水线有正常的定向路径，请对该循环中的指令进行调度。

注意可以重新组织指令的顺序，也可以修改指令的操作数，但是不能增加指令的条数。

请画出该指令序列执行的流水线时空图，并计算执行上述循环需要的时钟周期数？

二、现有如下表达式：

Y＝a×X

其中：

X和Y是两个有64个元素的32位的整数的向量，a为32位的整数。

假设在存储器中，X和Y的起始地址分别为1000和5000，a的起始地址为6000。

1．请写出实现该表达式的DLX代码。

2．假设指令的平均执行时钟周期数为5，机器的主频为500MHZ，请计算上述DLX代码（非流水化实现）的执行时间。

3．将上述DLX代码在改进的DLX流水线上（有正常的定向路径、分支指令在译码段被解析出来）执行，请以最快执行方式调度该DLX指令序列。

注意：

可以改变操作数，但不能改变操作码和指令条数。

画出调度前和调度后的DLX代码序列执行的流水线时空图，计算调度前和调度后的DLX代码序列执行所需的时钟周期数，以及调度前后的DLX流水线执行的加速比。

4．根据3的结果说明流水线相关对CPU性能的影响。

五、（15分）设有一个“Cache-主存”层次，Cache为4块，主存为8块；试分别对于以下3种情况，画出其映象关系示意图，并计算访存块地址为5时的索引（index）。

全相联；

组相联，每组两块；

直接映象。

10.动态多功能流水线由6个功能段组成，如下图：

其中，S1、S4、S5、S6组成乘法流水线，S1、S2、S3、S6组成加法流水线，各个功能段时间均为50ns，假设该流水线的输出结果可以直接返回输入端，而且设置有足够地缓冲寄存器，若以最快的方式用该流水计算：

画出时空图；

计算实际的吞吐率、加速比和效率。

四、计算题

1、（10分）给定以下的假设，试计算直接映象Cache和两路组相联Cache的平均访问时间以及CPU的性能。

由计算结果能得出什么结论？

（1）理想Cache情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.4次；

（2）两者Cache容量均为128KB，块大小都是32字节；

（3）组相联Cache中的多路选择器使CPU的时钟周期增加了10％；

（4）这两种Cache的失效开销都是80ns；

（5）命中时间为1个时钟周期；

（6）128KB直接映象Cache的失效率为1.0％，128KB两路组相联Cache的失效率为0.7％。

2、（10分）假设要在一个时钟速率为400MHZ的标量处理机上执行一个典型测试程序，该程序中含有4种类型指令，每种指令的条数和每条指令的CPI如下表所示：

指令类型

指令数

CPI

ALU

120000

1

Load/Store指令（Cache命中时）

36000

2

转移指令

24000

4

访存指令（Cache不命中时）

20000

8

计算在单处理机上执行该程序的平均CPI；

根据

（1）所得的CPI值，计算相应的MIPS速率和程序执行时间。

解：

（运用CPU性能公式）

CPU时间=（45000×1＋75000×2＋8000×4＋1500×2）/（400×106）=0.575（ms）

（MIPS——每秒百万次指令MFLOPS——每秒百万次浮点运算）

3、（25分）现有如下C语言源代码：

for（i=0；i<100，i++）

{A[i]=B[i]+C；}

其中，A和B是两个32位整数的数组，C和i均是32位整数。

假设所有数据的值及其地址均保存在存储器中，A和B的起始地址分别是0和5000，C和i的地址分别是1000和2000。

现假设将i的值和数组变量的地址在程序运行过程中，只要有可能就一直保存在寄存器中

（1）请写出该C语言源程序的DLX实现代码。

DLX代码的大小是多少？

LWRi,#400

LWRc,1000（R0）

Loop:

LWRb,5000（Ri）

ADDRa,Rb,Rc

SD0（Ri）,Ra

SUBIRi,Ri,#4

BENZRi,Loop

（2）假设上述DLX代码在改进的DLX流水线上（有正常的定向路径、分支指令在译码段被解析出来，所有存储器访问全部Cache命中）执行，请以最快的执行方式调度该DLX指令序列。

注意：

可以改变操作数，但不能改变操作码和指令条数。

计算调度后的DLX代码序列执行所需的时钟周期数，以及对于上述标准DLX流水线执行的加速比。

请写出该DLX代码的存储器数据访问地址流（十进制表示）。

在前面（3）中的实现中，均是假设存储器访问全部Cache命中，且Cache命中访问时间为1个时钟周期。

现假设该改进的DLX流水线没有Cache，所有存储器访问均需50个时钟周期（失效损失），请问（3）中调度后的DLX指令序列在该改进的DLX（没有Cache）上执行需要多少个时钟周期数。

（5）现假设为改进的DLX流水线设置一个大小为400字节的一级Cache，Cache块的大小为200B，采用全相联映射策略和写回策略，Cache的命中时间为1个时钟周期，失效损失为50个时钟周期，失效时每次预取一个块，预取一个块的时间为50个时钟周期，请计算该Cache的失效率，以及现在3中调度后的DLX指令序列在改进的DLX上执行需要多少个时钟周期数。

八、（9分）假设当按直接映象找到的位置处没有发现匹配，而在另一个位置才找到数据（伪命中）需要2个额外的周期。

Cache参数如下：

·容量128KB

·直接映象情况下命中时间为1个时钟，失效开销为50个时钟周期；

·时钟周期2路=1.10×时钟周期1路；

·直接映象失效率为0.010，两路组相联失效率为0.007；

问：

当直接映象、两路组相联和伪相联这三种组织结构时，速度各是多少