计算机体系结构期末辅导201303课件

计算机体系结构期末辅导主讲：何志杰1

1.期末考试题题型一、填空题（每空1分，共14分）

二、名词解释（每题2分，共16分）三、简答题（每题5分，共30分）

四、问答与计算题(第1题10分,第2、3题每题15分共40分)2.期末考试内容分布第1章基础知识第2章指令系统第3章存储系统设计第4章流水线计算机设计技术第5章并行处理技术（互连网络部分）第8章非冯.诺依曼计算机有关概念计算机体系结构期末辅导2按照弗林（Flynn）分类法，计算机系统可以分为4类：SISD计算机、（SIMD计算机）、（MISD计算机）和（MIMD计算机）。早期冯•诺依曼计算机的主要特点是（程序存储）、（指令驱动）、（集中控制）。目前向量处理机的系统结构有两种：（存储器－存储器型和寄存器－寄存器型）。通用计算机基本指令分为5类，它们分别是：（数据传送类，运算类，程序控制类，输入输出类，处理机控制和调试类）。传统的冯•诺依曼计算机是以控制驱动方式工作，以数据驱动方式工作的典型计算机是（数据流计算机），以需求驱动方式工作的典型计算机是（归约机），以模式匹配驱动方式工作的典型计算机是（人工智能计算机）。3、填空题（举例）34、名词解释(举例)计算机体系结构透明性系列机兼容机模拟仿真程序的局部性原理MIPS基准测试程序高速缓冲存储器虚拟存储器快表程序定位延迟转移技术窗口重叠技术流水线技术先行控制技术动态流水线静态流水线线性流水线非线性流水线流水线的吞吐率超标量计算机向量的分段开采技术41、简述冯.诺依曼计算机的特征。2、什么是存储系统？3、简述组相联映象规则。4、引起Cache与主存内容不一致的原因是什么？为了保持Cache的一致性，在单计算机系统中一般采取哪些措施？5、影响虚拟存储器命中率的因素有哪些？它们是如何影响的？6、在指令编码中，缩短地址码的方法很多，请列出三种缩短地址码的方法，并说明理由。7、什么是指令的重叠解释方式？重叠解释方式有哪三种？8、试述页式管理虚拟存储器的工作过程。5、简答题（举例）56、典型例题分析与解答[例1]如有一个经解释实现的计算机，可以按功能划分成4级。每一级为了执行一条指令需要下一级的N条指令解释。若执行第一级的一条指令需K(ns)时间，那么执行第2、3、4级的一条指令各需要用多少时间(ns)?解：∵第二级的一条指令需第1级的N条指令解释∴第二级的一条指令执行时间为NKns；第三级的一条指令执行时间为N2Kns；第四级的一条指令执行时间为N3Kns。6本题有两个问题应特别注意：第一个问题是“上一级”与“下一级”的关系，即哪是上一级，哪是下一级？在下图中第3级是第2级的“上一级”，第1级又是第2级的“下一级”。第二个问题是该计算机是一个“经解释实现的计算机”，上一级的程序在下一级上实现不是经翻译完成，只能是解释。第1级N3条指令解释第2级N2条指令解释第3级N条指令解释

第4级一条指令上级下级7[例2]假设将某系统的某一部件的处理速度加快到10倍，但该部件的原处理时间仅为整个运行时间的40%，则采用加快措施后能使整个系统的性能提高多少？解：由题意可知fe=0.4,re=10,根据Amdahl定律8[例3]用一台4OMHz处理机执行标准测试程序，它含的混合指令数和相应所需的时钟周期数如下：指令类型指令条数时钟周期数整数运算450001数据传送320002浮点运算

150002控制传送

80002求有效CPI、MIPS速率和程序的执行时间。9解：依题意可知IN=105条，n=410[例4]若某机要求有：三地址指令4条，单地址指令192条，零地址指令16条。设指令字长为12位，每个地址码长3位。问能否以扩展操作码为其编码？11解：

三种指令格式字如下：OPCA1A2A3

OPCA1

OPC000xxxxxxxxx

⋮011xxxxxxxxx000000xxx

⋮

⋮111101xxx111111110000

⋮111111111111三地址4条一地址192条零地址16条3333三地址指令4条单地址指令192条零地址指令16条12[例5]假设一台模型计算机共有10种不同的操作码，如果采用固定长操作码需要4位。已知各种操作码在程序中出现的概率如下表所示，计算采用Huffman编码法的操作码平均长度，并计算固定长操作码和Huffman操作码的信息冗余量（假设最短平均长度H＝3.1位）指令序号指令使用频度Pi指令序号指令使用频度PiI10.17I60.09I20.15I70.08I30.15I80.07I40.13I90.03I50.12I100.0113答：构造Huffman树如下：

14Huffman编码如下表：

指令号指令使用频度PiHuffman编码码长指令号指令使用频度PiHuffman码码长I10.17102I60.0901104I20.150003I70.0801114I30.150013I80.0711104I40.130103I90.03111105I50.121103I100.0111111515Huffman编码的平均码长为：冗余量＝（3.15－3.10）/3.15＝1.59%固定码长：log210＝4冗余量＝（4－3.10）/4＝22.5%16[例6]设某用户虚存共有8页,主存有4页,每页大小为1KB.试根据页表计算出虚地址1023和6800的主存实地址。提示：注意页表中虚、实页对应关系页表虚页号实页号装入位03111122033042151060170017每页首地址=页号X每页大小第0页0—1023第1页1024—2047第2页2048—3071第3页3072—4095第4页4096—5119第5页5120—6143第6页6144—7167第7页7168--8191解：页号与地址对应关系虚地址1023，虚页号为0，页内位移为1023；根据虚页号查页表得知实页号为3，且装入位为1。主存实地址PA=3072+1023=4095虚地址6800，虚页号为6，页内位移为656；根据虚页号查页表得知实页号为0，且装入位为1。主存实地址PA=0+656=656虚页号＝虚地址％102418[例7]某机主存容量为512KB，Cache的容量为32KB，每块的大小为16个字（或字节）。划出全相联方式主、缓存的地址格式、目录表格式及其容量。

答：全相联映象方式：

主存与缓存分成相同大小的数据块，主存的某一数据块可以装入缓存的任意一块空间中。根据已知条件可以求得：主存块数：512K/16＝32K＝215；缓存块数：32K/16＝2K＝211；块内地址：16＝2419

容量：与缓冲块数量相同即211＝2048(或32K/16＝2048)。主存块号Bi块内地址18430主存地址缓存块号Bi块内地址14430缓存地址主存块地址缓存块地址有效位26121110目录表20图2.6全相联地址转换

21[例8]某机主存容量为512KB，Cache的容量为32KB，每块的大小为16个字（或字节）。划出直接相联方式主、缓存的地址格式、目录表格式及其容量。

答：直接相联映象方式：主存与缓存分成相同大小的数据块，将主存空间按缓存的容量分成区，主存中某区的一块存入缓存时只能存入缓存中块号相同的位置。根据已知条件可以求得：主存区数：512K/32K＝16＝24；缓存块数：32K/16＝2K＝211；块内地址：16＝24

22容量：与缓冲块数量相同即211＝2048(或32K/16＝2048)。主存区号有效位410目录表缓存块号块内地址14430缓存地址区号区内块号块内地址181514430主存地址23高速缓冲存储器图2.8直接相联地址转换24[例9]主存容量为512KB，Cache的容量为32KB，每块为64个字（或字节），缓存共分128组。划出组相联方式主、缓存的地址格式、目录表格式及其容量。答：组相联映象方式：主存与缓存分成相同大小的数据块，主存和Cache按同样大小划分成组，将主存空间按缓存的容量分成区，当主存的数据调入缓存时，主存与缓存的组号应相等，但组内各块地址之间则可以任意存放。根据已知条件可以求得：

主存区数：512K/32K＝16＝24；缓存组数：128＝27；缓存块数：32K/64＝512＝29；组内块数：512/128＝4＝22块内地址：64＝2625容量：29＝512(或32K/64＝512)。区号块号缓存块号有效位8543210目录表组号缓存块号块内地址1487650缓存地址区号组号块号块内地存地址26高速缓冲存储器图2.10组相联映象地址转换27[例10]一个有快表和慢表的页式虚拟存储器，最多有64个用户，每个用户最多要用1024个页面，每页4K字节，主存容量8M字节。（1）写出多用户虚地址的格式，并标出各字段的长度。（2）写出主存地址的格式，并标出各字段的长度。（3）快表的字长为多少位？分几个字段？各字段的长度为多少位？（4）慢表的容量是多少个存储字？每个存储字的长度为多少位？28答：用户号：64＝26，虚页号：1024＝210，页内地址：4K＝212，主存页数：8M/4K＝211（1）多用户虚地址：用户号（6位）＋虚页号（10位）＋页内地址（12位）共28位（2）主存地址：主存实页号（11位）＋页内地址（12位）共23位（3）快表字长27位；分3个字段：用户号6位，虚页号10位，实页号11位（4）慢表容量为2(6+10)，每个存储字长为：主存页号＋1＝12位。29[例11]为在页式虚拟存储器中，一个程序由P1～P5共5个页面组成。在程序执行过程中依次访问的页面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2假设系统分配给这个程序的主存有3个页面，分别采用FIFO、LFU和OPT三种页面替换算法对这3页主存进行调度。(1)画出主存页面调入、替换和命中的情况表。(2)统计三种页面替换算法的页命中率。解：三种替换算法的替换过程：30页地址流232152453252

FIFO命中3次223232*3153*1521*5*245*2432*432*4354*3*52调进调进命中调进替换替换替换命中替换命中替换替换LRU命中5次22323123*512*251*425*542*354*235*523*253*调进调进命中调进替换命中替换命中替换替换命中命中OPT命中6次22323231*23*52*354*354*354*3523*5235235调进调进命中调进替换命中替换命中命中替换命中命中31[例12]用一条4段浮点加法器流水线求8个浮点数的和:Z＝A＋B＋C＋D＋E＋F＋G＋H,求流水线的吞吐率、加速比和效率,其中△t1=△t2=△t3=△t4=△t。解：由于存在数据相关，A+B的运算结果要在第5时钟周期才能继续做加C运算，这样，每个功能部件都要空闲3个时钟周期，为此，可对原式作一简单变化，得到：Z＝[（A＋B）＋（C＋D）]＋[（E＋F）＋（G＋H）]327个加法8个数的流水线时空图如下：33从流水线的时空图中可以很清楚地看到，7个浮点加法共用了15个时钟周期。流水线的吞吐率为：

流水线的加速比为：

流水线的效率为：

34[例13]设有两个向量A，B，各有4个元素，若在如图5-2-16a所示的静态双功能流水线上，计算向量点积：

其中，1→2→3→5组成加法流水线，1→4→5

组成乘法流水线。35又设每个流水线所经过的时间均为△t，而且流水线的输出结果可以直接返回到输入或暂存于相应的缓冲寄存器中，其延迟时间和功能切换所需的时间都可以忽略不计。请使用合理的算法，能使完成向量点积A*B所用的时间最短，并求出流水线在此期间实际的吞吐率TP和效率E。

解：首先，应选择适合于静态流水线工作的算法。对于本题，应先连续计算al*bl、a2*b2、a3*b3和a4*b4共4次乘法，然后功能切换，按((albl+a2b2)+(a3b3+a4b4))经3次加法来求得最后的结果。按此算法可画出流水线工作时的时空图。如图5-2-16b所示。3637

由图可见，总共在15个△t的时间内流出7个结果，所以在这段时间里，流水线的实际吞吐率TP为7/15△t。

若不用流水线，由于一次求积需3△t,一次加法需

4△t,产生上述结果就需要43△t+34△t=24△t。因此,加速比为S=24△t/(15△t)=1.6。

该流水线的效率可用阴影区面积和全部5个段的总时空图面积之比求得，即38[例14]什么是方体置换？写出方体置换函数的表达式，假设互联网有16个结点，请画出4个方体置换函数（即C0，C1，C2，C3）的输入端与输出端的连接关系。

答：方体置换是实现二进制地址编号中第k位位值不同的输入端输出端之间的连接。其表达式为：

3900000001001000110100010101100111000000010010001101000101011001111000100110101011110011011110111110001001101010111100110111101111C0立方置换函数：40C1立方置换函数：00010010001101000101011001110001001000110100010101100111100110101011110011011110111110011010101111001101111011110000