编译原理复习题 (1).doc

一、 选择题：1、虚拟存储器地址变换是指（ B）A 多用户虚地址与实地址如何一一对应B 程序的逻辑地址变换成主存实地址C 程序执行时将虚地址变换成对应的实存地址D 指令的符号地址变换成二进制地址2、计算机系统多级层次中，从下层到上层，各级相对顺序正确的应当是（ B ）A 汇编语言机器级，操作系统机器级，高级语言机器级B 微程序机器级，传统机器语言机器级，汇编语言机器级C 传统机器语言机器级，高级语言机器级，汇编语言机器级D 汇编语言机器级、应用语言机器级、高级语言机器级3、操作码优化的主要目的是（ D ）A 缩短指令字长 B减少程序总位数 C增加指令字表示的信息D A和B和C4、为实现“执行K”与“分析k+1”的重叠，必须( C )。 A. 操作数和指令分别存放在两个独立编址的存储器中 B采用多体交叉主存结构，且不共存于一个体中 C有独立的指令分析部件和指令执行部件 D增设指令缓冲寄存器5、计算机系统中主存一辅存存储层次或Cache一主存存储层次常用的替换算法是( B )A 随机算法 B 近期最少使用算法C 先进后出算法 D OPT算法6、数据表示的意义是：（ B ）A 它是计算机系统能表示的数据类型B 它是计算机硬件能直接识别的数据类型C 它是计算机硬件能直接识别的数据结构D 它是数据结构的一个子集7、如果一台计算机的输入输出由一个独立的处理机来完成，它应该是：（ C ）A 采用DMA的计算机系统 B 采用通道处理机的系统C 采用I/O处理机的系统 D 采用程序传送方式进行I/O的系统8、假设禁止向量为（1，5，6，8），则8位的初始冲突向量为（10110001）。若选择第二个任务在2拍后送入流水线，则新的冲突向量为（ C ）00101100A 10101010 B 01011111 C 10111101 D 101110119、系列机软件兼容必须有的基本要求是：应能保证做到( D )。A 向上兼容 B 向下兼容 C 向前兼容 D 向后兼容10、对计算机系统结构，下列哪个是透明的：（ B ）A 操作系统程序员 B 应用程序员 C 系统结构设计人员 D 机器语言程序设计人员2、24扩展编码最多可以得到的码点数是（ D）? A、6 B、7 C、10 D、134、静态流水线是指（ C ） A、功能不能改变的流水线 B、可同时执行多种功能的流水线 C、同时只能完成一种功能的多功能流水线 D、各段之间的连接是固定不变的流水线5、虚拟存储器主要是为了解决（ A ） A、扩大存储系统的容量 B、Cache提高存储系统的速度 C、扩大存储系统的容量和速度 D、便于程序的访存操作6、输入输出数据不经过CPU内部寄存器的输入输出方式是（ B ） A、中断方式 B、DMA方式 C、程序查询方式 D、上述3种方式8、RISC执行程序的速度比CISC要快的原因是（ D ）A、RISC的指令系统的指令数少B、程序在RISC上编译生成的目标程序较短C、RISC只允许load指令和store指令访存D、RISC的指令平均周期数较少10、字节多路通道的实际流量是（ C ）A、 连接在这个通道上所有外设的最大数据传输速率B、 连接在这个通道上所有外设的最小数据传输速率C、 连接在这个通道上的所有设备的数据传输速率之和D、 以上3者都不是1、在计算机的系统结构设计中，提高硬件功能实现的比例会（ B ）?A、 提高硬件利用率 B、提高系统的运行速度C、减少需要的存储器容量 D、提高系统的性能价格比2、平均码长最短的编码是（ D ）A、定长码 B、24扩展码 C、36扩展码 D、哈夫曼编码4、与线性流水线最大吞吐率有关的是（ C ） A、各个子过程的执行时间 B、最快子过程的执行时间 C、最慢子过程的执行时间 D、最后子过程的执行时间5、与全相联映象相比，组相联映象的优点是（ A ）? A、目录表小 B、块冲突概率低 C、命中率高 D、主存利用率高6、程序员编写程序时使用的访存地址是（ D ） A、主存地址 B、物理地址 C、有效地址 D、逻辑地址7、在顺序流动的指令流水线中，可能发生的相关有（ C ）？A、 同一条指令的读操作和写操作之间的先写后读相关B、 先流入的指令的写操作与后流入的指令的读操作之间的先写后读相关C、 后流入的指令的写操作与先流入的指令的读操作之间的先读后写相关D、 两条指令的写操作之间的写写相关8、设置中断屏蔽码可以改变（ D ）?A、多个中断源的中断请求优先级 B、多个中断服务程序被开始执行的次序C、CPU对多个中断响应的优先次序 D、多个中断服务程序执行完的次序9、流水线的技术指标不包括( A ) A、响应比 B、吞吐率 C、加速比 D、效率10、通道最大流量等于通道实际流量时，有可能发生局部的数据丢失，这是因为（ D ）A通道流量匹配的要求不合理B多个外设的数据传输速率之和大于通道最大流量C通道没有空闲的工作周期及时响应优先级低的外设的个别数据传送请求 D通道在数据传送过程中丢失数据1、不同系列的机器之间，实现软件移植的途径不包括（ B ）A、采用统一的高级语言 B、采用统一的汇编语言 C、模拟 D、仿真2、多处理机上两个程序之间若有先写后读的数据相关，则（ b）？A 、 可以并行执行 B 、不可能并行 C 任何情况均可交换串行 D、 必须并行执行3、采用先行控制技术必须增设( D )。A、指令缓冲栈 B、先行操作栈 C、数据缓冲栈 D、以上都需要 6、指令流水线属于（ C ） A、操作流水线 B、部件级流水线 C、系统级流水线 D、处理机级流水线7、按Cache地址映像的块冲突概率从高到低的顺序是（A）A、 直接映像、组相联映像、全相联映像B、 全相联映像、组相联映像、直接映像C、 组相联映像、直接映像、全相联映像D、 全相联映像、直接映像、组相联映像1、系列机在软件兼容上应做到（ B ）A、 向前兼容，并向上兼容 B、 向后兼容，力争向上兼容 C、向前兼容，并向下兼容 D、向后兼容，力争向下兼容 7、指令的二次交叉执行方式是指（ B ）?A、 同时解释执行相邻的2条指令 B、 把指令的解释执行过程分为指令分析和指令执行2个子过程交叉执行C、 一条指令的取指、分析与执行同时解释执行D、 取指K，分析K1与执行K2同时解释执行8、虚拟存储器常用的地址映像是（ ）A全相联映像 B、组相联映像 C、直接映像 D、以上三种9、直接存储器访问方式的并行性是指( C )?A、 多个外设可同时并行地通过DMA控制器进行数据传送 B、 外设和主存储器并行工作C、 CPU和DMA控制器并行工作D、 CPU和主存储器并行工作 5浮点数表示的尾数的基Rm16，尾数的长度P8，可表示的规格化最大正尾数的值是（ ）? A0.5 B.0.125 C.0.25 D.1/64 3、非线性流水线的特征是（ B ） A、一次运算中使用流水线中的多个功能段 B、一次运算中要多次使用流水线中的某些功能段 C、流水线中某些功能段在各次运算中的作用不同 D、流水线的各功能段在不同运算中可以有不同连接二、填空题： 1、计算机实现是指计算机组成的 物理 实现,而计算机组成则是计算机系统结构的 逻辑 实现.2、按照在同一时间内是否能够连接成多种方式，同时执行多种功能，可以把非线性流水线分为 动态非线性流水线 和 静态非线性流水线 。3、地址映象是指将每个虚存单元按一定规则装入 主存储器 ；地址变换是指程序执行中，如何将多用户虚地址变换成对应的 主存实地址 。4、 CPI表示执行每条指令所需的_ 平均时钟周期数 。5、 按照Flynn分类法,根据指令流和数据流的不同组织方式,计算机系统的结构可以分为SISD(单指令流单数据流)、MISD（多指令流单数据流）、SIMD 和 MI 。6、数组多路通道与设备之间的数据传送的基本单位是_ 数据块 _。7、目前常用的基本输入输出方式有如下三种 I/0处理机方式 ,直接存储器访问 和 程序控制输入出 （程序查询方式和程序中断方式） 。8、 为了满足向量计算机中运算器带宽的要求，通常有两种向量处理机结构，它们是P190 横向处理方式 和 纵向处理方式 。？3、流水线消除速度瓶颈的方法是 将瓶颈子过程进一步细分成若干个子子过程，使每一个子子过程与其他子过程时间相等；在瓶颈段设置多套功能段部件，使它们轮流工作 如 P169 。4、就其本质而言，局部性原理包括 时间局部性 和空间局部性 两部分。5、CPU响应中断后，硬件自动 关中断？ 是为了使CPU不再响应其他中断请求，使保存断点及现场信息的工作不受干扰。在保存现场之后和执行中断服务功能之前，应使CPU 开中断 ，是为了能实现多重中断。P73752、CISC中,各种指令的使用频率相差很悬殊，大量的统计数字表明，大约有 20% 的指令使用频率比较高，占据了 80% 的处理机时间。3、根据所采用的地址映象和地址变换方法的不同，有多种类型的Cache，如全相联映象直接相联映像 和 组相联映像 。5、按照流水线的各个功能段之间是否有反馈信号，可以把流水线分为 线性流水线和 非线性流水线 。1、 当两个虚页要求装入同一主存页面的位置时，称为 页面冲突 ；当发生页面失效，同时又发生页面冲突时，需要进行 置换 。？2、若通道连接的外设台数为p，外设 i 的数据传输速率为fi，那么，字节多路通道的实际流量fbyte 所有通道流量之和fi，选择通道的实际流量fselect 通道的最大流量max fi ，数组多路通道的实际流量fblock 通道的最大流量max fi。3、假设高速缓存Cache工作速度是主存的5倍，且cache被访问命中的概率为90，则采用Cache后，能使整个存储系统获得的加速比3.57 Sn=T0/Tn=1/(1-Fe+Fe/Se)。5、先行控制技术的关键是 缓冲技术 和 预处理技术 。1、实现程序移植的主要途径有系列机、采用统一的高级语言、模拟和仿真。2、假设将某系统某一部件的处理速度加快到10倍，但该部件的原处理时间仅为整个运行时间的40，则采用加快措施后能使整个系统的性能提高 1.56 倍。3、Cache存储器采用组相联映像是指组间采用 直接相联 映像，组内各块采用 全相联 映像方式。1、数据存储空间的编址单位有 字 编址、字节 编址和 位 编址。P432、只需要通过该层的语言就可以使用机器，而不必关心其下层的机器级是如何工作和如何实现各自功能的，这一性质称为 透明性 。？ 3、在Cache存储器中，CPU每次可在写Cache的同时也写入主存，也可以在发生块替换的时候才写回主存，这2种保持Cache一致性的方法中，前者称为 写直达法 ，后者称为 写回法 。 4、在程序控制输入输出方式中，由CPU执行用户程序来完成输入输出工作；在中断输入输出方式中，由 CPU 执行 中断服务 程序来完成输入输出工作；在通道输入输出方式中，由 CPU 通道 执行 通道指令控制设备控制器 来完成输入输出工作。三、名词解释： 1、 RISC :是在20世纪80年代发展起来的，尽量简化指令功能，只保留那些指令功能简单，能在一个节拍内执行完成的指令，较复杂的功能用一段子程序来实现的计算机系统。2、 虚拟存储器：是主存储器联机外部存储器（辅存）层次结构的进一步发展和完善，主要是为了克服主存容量满足不了要求而提出来的。（Cache与虚拟存储器的区别）存储系统 Cache 虚拟存储器要达到的目标 提高主存速度 扩大主存容量实现方法 全部硬件 软件为主，硬件为辅两级存储器速度比 310倍 100倍页（块）大小 116字 116KB等效存储容量 主存储器 虚拟存储器透明性 对系统和应用程序员 仅对应用程序员不命中是的处理方式 等待主存储器 任务切换3、 向量处理：P189由于向量内部各个元素（分量）之间很少相关，且对这些元素一般是执行同一种操作，比较容易发挥出流水线的效能，所以一般是将向量数据表示和流水线技术结合起来，构成向量流水处理机，以提高主要米昂想向量数组计算类应用的计算机的速度性能。4、 流水线的吞吐率：流水线单位时间里能处理的任务数或输出的结果数。 1、 Amdahl定律 ：系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高取决于这种执行方式的使用频率或占总执行时间的比例。实际上定义了加快某部分功能处理后，整个系统所获得的性能改进或执行时间的加速比的大小。加速比与两个因素有关：一是计算机执行某个人物的总时间中可被改进部分的时间所占的百分比，Fe=可改进部分占用的时间/改进前整个任务的执行时间，它总小于1；二是改进部分采用改进措施后比没有采用改进措施前性能提高倍数，Se=改进前改进部分的执行时间/改进后改进部分的执行时间，它总大于1。（1） 改进后整个任务的执行时间：Tn=T0(1-Fe+Fe/Se)，T0是改进前整个任务的执行时间。（2） 改进后整个系统的加速比：Sn=T0/Tn=1/(1-Fe+Fe/Se)。（1-Fe）表示不可改进部分，当Fe=0，既没有改进部分，Sn为1，所以性能的提高幅度受改进部分所占比例的限制。当Se，则Sn=1/1-Fe，因此，可获取性能改善极限受Fe值的约束。 2、 透明性：一种本来存在的有差异的事物或属性，从某种角度来看似乎不再存在。3、 数据相关：P161由于重叠方式中“执行K”和“分析K+1”同时进行，而“执行K”写结果数据的空间和“分析K+1”的数据所在空间刚好相同，从而造成K指令和K+1指令的数据在空间上相关联。 4、 地址映像：在Cache中，它是把主存空间地址映像到Cache地址空间，具体地说及时把存放在主存中的程序按照某种规则装入到Cache中，并建立主存地址与Cache地址之间的对应关系。（虚拟：虚拟空间地址映像到主存地址空间，把虚拟地址编写的程序按照某种规则装入到主存储器中，并建立多用户虚地址与主存实地址之间的对应关系）5、 地址变换：指当程序已经装入到Cache之后， 在实际运行过程中，把主存地址变换成Cache地址。（程序被装入主存储器后在程序执行时进行，多用户虚地址变换成主存是地址称为内部地址变换；多用户虚地址变换成此怕存储器地址称为外部地址变换）6、 中断源 ：引起中断请求的各种事件。7、 中断响应时间：允许该中断请求中断CPU现行程序的运行，转而去处理该请求的过程的时间。8、 局部性原理：从大量的统计中得到的一个规律。（程序对存储空间的90%的访问局限于存储空间的10%的区域中，而另外10%的访问则分布在存储空间的90%的区域中）9、 流水线的链接 ：按其分为线性流水线和非线性流水线。 3、 非线性流水线 ：存在反馈回路，从输入到处处过程中，流水线经反馈回路和多路开关时某些段可能要多次通过，而有些段可能被跳过。4、 链接技术：P194实质上是吧“相关通路”的思想引入到向量指令的执行过程之中。只有在前一条指令的第1个结果分量送入结果向量寄存器组的那一个时钟周期为允许连接时间才行。5、 静态流水线：同一时间内它时能以一种工作方式工作的多功能流水线。（可是是单功能的） 6、 数据表示： 研究的是计算机硬件能够直接识别，可以被指令系统直接调用的哪些数据类型。 7、 CPI ：每条指令的平均时钟周期数。 四、判断题1、扩展编码要求所有的短码都不能是长码的前缀，否则会产生解码不惟一的问题（ ）？2无论采用何种方法，只要消除流水线的瓶颈段就能提高流水线的吞吐率和效率（只能提高吞吐率）（ ）3、FIFO、LRU和OPT（根据将来的情况）等替换算法都是根据虚页的过去使用情况来确定被替换页的（ ）4、在直接存储器访问方式中，DMA控制器接收外设的DMA请求后，就可在DMA控制器的管理下，在主存和外设之间传送数据。（ ）（CPU接收请求，对D预处理）1、带标志符的数据表示增大了数据字的字长，从而会增大目标程序在这种机器上运行时所占用的存储空间（ ）？（大量分析，带标识符的数据表示会节约存储空间）2、当访存发生页面失效时，就需要进行页面替换（主存满置换，主存空装入）（ ）3、输入输出系统的设备无关性是指计算机系统通过一些独立与具体外设的标准I/O接口来连接各种外设（ ）4、当通道实际流量大于通道最大流量时，可以通过配置缓冲存储器来暂存未及时传送的数据，从而避免数据丢失。（ ）（通道实际流量=最大流量时，会有数据的丢失，可设置缓冲存储器）2浮点数据表示可以表示示数范围内的所有实数（ ）（浮点数是若干个连续的店）3、把瓶颈段进一步细分可以消除瓶颈段（ ）4、通过设置中断屏蔽码，可以动态改变中断响应的次序（ ）（可改变中断处理的次序）29四、综合题1、(10分)某计算机有7条指令，它们的使用频率分别为： 0.41，0.30，0.10，0.08，0.05，0.03，0.03要求：分别用霍夫曼编码和扩展编码对其操作码进行编码，其中限定扩展编码只能有2、4两种长度。 （1）画出霍夫曼编码时的霍夫曼树。（2）列出各种指令的霍夫曼编码及其扩展编码对应表。Huffman0.41 0，0.30 10，0.10 1100,0.08 1101,0.05 1110,0.03 11111,0.03 11110；2-4扩展编码0.41 00，0.30 01，0.10 10,0.08 1100,0.05 1101,0.03 1111,0.03 1110。（3） 求出霍夫曼编码及24扩展编码的平均码长。Huffman H=0.41*0+0.30*2+0.10*12+0.08*13+0.05*14+0.03* 31+0.03*30=4.292-4H=0.41*0+0.30*1+0.10*2+0.08*12+0.05*13+0.03*14+0.03*15=2.962、假设在一个采用组相联映象方式的Cache中，主存由B0-B7共8块组成，Cache有2组，每组2块，每块的大小为16个字节，采用LFU块替换算法。在一个程序执行过程中依次访问这个Cache的块地址流如下： B6,B2,B4,B1,B4,B6,B3,B0,B4,B5,B7,B3(1) 写出主存地址的格式，并标出各字段的长度(2) 写出Cache地址地址的格式，并标出各字段的长度(3) 计算Cache的块命中率4/12=33%(4) 如果采用全相联映像方式，计算Cache的命中率，要求有相应的过程图示说明3、fp操作的比例为25，FP操作的平均CPI4.0，其他指令的平均CPI为1.33，FPSQR操作的比例为2，FPSQR的CPI为20。假设有两种设计方案，为别把FPSQR操作的CPI和所有的FP操作的CPI减为2。试利用CPU性能公式比较这两种方案哪一个更好。4、在CRAY-1机上，Vi为向量寄存器，设向量长度为32，s为标量寄存器，所有浮点功能执行部件的执行时间分别为：加法需6拍，相乘需7拍，从存储器读数需6拍，结果打入寄存器和启动功能部件（包括存储器）各需1拍，计算下列指令序列全部完成所需要的拍数。（需划出流水线链接图） V0存储器 V3V1V2 V4V0V3 V6V4V5 1+6+1+1+7+1+1+6+1+31=565、已知：有一个5段流水线，其预约表如下：1234567S1S2S3S4S5(1)列出禁止表F（1，3,6）及原始冲突向量00100101（禁止启动距离为1、3、6，说明冲突向量第一位即D0、D2、D5为1）：(2)画出用冲突向量表示的流水线状态图00101101、00101111、00100111，（3）计算出每种调度法的平均间隔拍数，井选出最佳调度方案(8),(4,4)。（5/7/8）2.5/3.5/4，（2,5/7/8）3.2/4.5/5，（2,2,5/7/8）4.5/5.5/6，（4,5/7/8）4.5/5.5/6，（4,4）4，（4,4,5/7/8）6.5/7.5/81、设某台计算机有9条指令，各指令的使用频率分别为： I1：52 I2：14 I3：12I4：7 I5：6I6：5 I7：2 I8：1I9：1试分别用哈夫曼编码和37扩展编码？为其操作码编码，并分别计算平均码长Huffman：I1：0 I2：100 I3：110 I4：1010 I5：1011 I6：1110 I7：11110 I8：111111 I9：1111103-7：I1：0 I2：100 I3：110 I4：1010 I5：1011 I6：1110 I7：11110 I8：111111 I9：1111102、有一个Cache存储器，主存有B0B7共8块组成，Cache有4块，采用组相联映象，组内块数为2块，每块大小为16个字节。采用LRU替换算法。（1） 写出主存地址和Cache地址得格式，并指出各字段得长度。（2） 画出主存各块与Cache各块之间得映象关系。 （3） 某程序运行过程中，访存得主存块地址流为1，2，4，1，3，7，0，1，2，5，4，6，4，7，2 说明该程序访存对Cache得块位置的使用情况，指出发生块失效且块争用的时刻？，计算Cache命中率。3/15=20% 3、有5个中断源D1、D2、D3、D4、D5，优先级从高到低1、2、3、4、5，已知各种中断处理程序的中断屏蔽码设置如下表所示，中断屏蔽位为“0”表示该中断源被屏蔽；“1”对应开放。 中断源中断屏蔽码D1D2D3D4D5D110000D201000D310100D411011D511101（1） 5个中断源同时请求中断服务时，处理机响应次序是什么D5D4D3D2D1？实际中断处理次序是什么D1D2D3D5D4？ （2） 假设从处理机响应中断源的请求到第一次开中断所用时间为1个单位时间，处理机运行中断服务程序的其他部分所用时间为4个单位时间。在执行用户程序时，同时发生第3、4级和第5级中断请求；过了3个单位时间之后，又同时发生第1、2级中断请求。请画出中断处理程序的运行过程示意图，说明中断处理次序。 执行完1，2返回用户程序，开中断1个单位时间，再到D3。4、有一个5段流水线，各段执行时间均为t，其预约表如下表所示：T1T2T3T4T5T6T7S1S2S3S4S5(1) 画出流水线调度的状态有向图。禁止启动距离（1,3,6）(2) 分别求出允许不等时间间隔调度和等时间间隔调度？的两种最优调度策略（确定启动距离，最多的3），以及这两种调度策略的流水线最大吞吐率(3) 若连续输入10个任务，求等时间间隔调度的流水线实际吞吐率和加速比。1、某个处理机的时钟频率为15MHz,执行测试程序的速率为10MIPS，假设每次存储器存取需1个时钟周期的时间，试问：（2） 处理机的CPI值是多少？MIPS=时钟f/CPI*106，CPI=15*106/107=1.5（3） 假设将处理机的时钟频率提高到30MHz，但存储器的工作速率不变，这使得每次存储器存取需2个时钟周期。如果测试程序得30指令需要1次访存，5指令需要2次访存，其他指令不需要访存，试求测试程序在改进后得处理机上执行得 MIPS=30*106/CPI*106,=37.5。CPI=30%*2+5%*4+65%*0=0.82、在CRAY-1机上，Vi为向量寄存器，设向量长度为64，s为标量寄存器，所有浮点功能执行部件的执行时间分别为：加法需6拍，相乘需7拍，从存储器读数需6拍，结果打入寄存器和启动功能部件（包括存储器）各需1拍，计算下列指令序列全部完成所需要的拍数。（需划出流水线链接图） V3存储器 V2V0V1 V4V2V3 存储器V41+6+1+1+7+1+1+6+63=873、有5级中断源D1、D2、D3、D4、D5，优先级从高到低1、2、3、4、5，已知各种中断处理程序的中断屏蔽码设置如下表所示，中断屏蔽位为“1”表示该中断源被屏蔽；“0”对应开放。 中断源中断屏蔽码D1D2D3D4D5D111111D201100D300100D401111D501101（3） 5个中断源同时请求中断服务时，处理机响应次序是什么D5D4D3D2D1？实际中断处理次序是什么D3D2D5D4D1？ （4） 若在运行用户程序时，同时出现第2、4级中断请求，而在第2级中断已经开始处理却处理未完成时又出现第1，3，5级中断请求。请画出中断处理程序的