体系结构复习重点升级版删减版

1、体系机构复习重点注：红色代表不确定，玫粉色 是加进去的第一章不考大题，第二章不考概念、小题1 Amdahl 定律系统中某一部件由于采用更快的执行方式后，整个系统性能的提高与这种执行方 式的使用频率或占总执行时间的比例有关。2指令级并行一种平行计算形式，在一个程式运行中，许多指令操作，能在同时间进行3程序的局部性原理：是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于 程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。4透明性概念定义：本来存在的事物或属性，从某种角度看似乎不存在5大概率事件优先原则对于大概率事件（最常见的事件），赋予它优先的处理权和资源使用

2、权，以 获得全局的最优结果。7超标量处理机采取设置M条指令流水线同时并行，来实现并行度为m的处理机 8向量流水处理把要解决的问题转化成向量运算， 采用横向，纵向，纵横处理方式 对向量各分量进行独立并行的处理9系列机具有相同的系统结构，但组成和实现技术不同的一系列计算机系统 兼容（软件，硬件）；兼容最基本特征；向右兼容11并行性指令内部指令级线程级任务级作业级指计算机系统具有可以同时进行运算或操作的特性，在同一时间完成两种或 两种以上工作。它包括同时性与并发性两种含义。同时性指两个或两个以上事件 在同一时刻发生。并发性指两个或两个以上事件在同一时间间隔发生。14写直达法写回写直达法：在执行写操作

3、时，不仅把信息写入Cache中相应的块，而且也写入下一级存储器中相应的块。15加速比加速比（speedup），是同一个任务在单处理器系统和并行处理器系统中运行 消耗的时间的比率，用来衡量并行系统或程序并行化的性能和效果。16数据相关在执行本条指令的过中，如果用到的指令、操作数、变址偏移量等正好是前 面指令的执行结果，则必须等待前面的指令执行完成，并把结果写到主存或通用 寄存器中之后，本条指令才能开始执行，这种相关称为数据相关。17控制相关条件分支指令、转子程序指令、中断等引起的相关。18存储器系统计算机中的存储系统是用来保存数据和程序的。 对存储器最基本的要求就是存 储容量要大、存取速度快、成

4、本价格低。为了满足这一要求，提出了多级存储体 系结构。一般可分为高速缓冲存储器、主存、外存3个层次，有时候还包括CPU内部的寄存器以及控制存储器。20虚拟机指通过软件模拟的具有完整硬件系统功能的、 运行在一个完全隔离环境中的完整 计算机系统。二、简单问答题1计算机体系结构：计算机系统结构就是计算机的机器语言程序员或编译程序编写者所看到的外特 性，是硬件子系统的概念结构及其功能特性。2 CPI每条指令所需的平均时钟周期数3软件兼容一个软件可以不经修改或者只需要少量修改就可以由一台计算机移植到另一台 计算机上运行，差别只是执行的时间不同。4仿真与模拟仿真是指用微程序的方法在一台计算机上实现另一台计

5、算机的指令系统。模拟是指用软件的方法在一台计算机上，实现另一台计算机的指令系统,5时间重叠，资源重叠时间重叠：在并行性概念中引入时间因素，让多个处理过程在时间上相互错开, 轮流重叠的使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。，以数量取胜，通过重复设置硬件资源，大幅度的提高计算机系统的 资源重叠(重复)：在并行性概念中引入空间因素性能。6先行控制器先行控制器处理机结构：包括三个独立的控制器和四个缓冲栈。其中三个控制器 为：存储控制器、指令控制器、运算控制器。四个缓冲栈：先行指令缓冲栈、线 性读数缓冲栈、现行操作栈，后行写数栈7紧密耦合系统，松散耦合系统(smp,mpp)紧密耦合系统

6、：机间物理连接的频带较高，它们往往通过总线或者告诉开关实现 互联，可以共享主存。松散耦合系统：通过通道或者通信线路实现计算机间互联，共享某些外围设备， 机器间的相互作用是在文件或者数据集一级进行。8异构型多处理机系统，同构型多处理机类型 同构型(对称型)多处理机：由多个同类型，至少担负同等功能的处理机组成， 同时处理同一作业中能并行执行的多个任务。异构型(非对称型)多处理机：由多个不同类型，至少担负不同功能的处理机组 成，按照作业要求的顺序，利用时间重叠原理，依次对它们的多个任务进行加工, 各自完成规定的功能动作。9佛林分类他按照指令流和数据流的多倍性特征对计算机系统进行分类，把计算机系统分4

7、大类：单指令流单数据流、单指令流多数据流、多指令流单数据流、多指令流多数据流10并行等级划分(1) 指令内部并行：指令内部的微操作之间的并行。(2) 指令级并行(Instruction Level Parallel，ILP):并行执行两条或多条指令。(3) 任务级或过程级并行：并行执行两个或多个过程或任务(程序段)。(4) 作业或程序级并行：在多个作业或程序间的并行11堆栈型机器通用计算型一种计算模型。这种类型的电脑，内存以堆栈(Stack)储存。它的指令集中包 含了零位址指令("0-operand" instruction set )。硬件在执行运算时，到堆栈 的顶端去取

8、出算子，至运算结束时，再储存到堆栈的顶端。12 RISC指令系统的设计原则a大多数指令在单周期内完成b采用LOAD/STOR结构c硬布线控制逻辑d减少指令和寻址方式的方案f固定的指令格式g注重译码的优化13静态流水、动态流水动态流水线在同一时间内允许按多种不同运算的联结方式工作。静态流水线在同一时间内只能按一种运算的联结方式工作。14分支指令调度分支条件由指令确定，提供一组比较指令，用于比较两个寄存器的值。有的分支 指令可以直接判断寄存器内容是否为负， 或者比较两个寄存器是否相等。分支的 目标地址由16位带符号偏移量左移两位后和 PC相加的结果来决定一条浮点条件 分支指令：通过测试浮点状态寄存

9、器来决定是否进行分支。15链接技术，分段开采当利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术称为链接技术；向量的长度大于向量寄存器的长度时， 必须把长向量分成 长度固定的段，采用循环结构处理这个长向量，这种技术称为向量循环开采技术， 也称为向量分段开米技术。16半性能向量长度达到一半最大性能值所需的向量长度。17超流水通过细化流水，提高主频,使得机器在一个周期内完成一个甚至多个操作，其实质 是用时间换取空间。18 CISC复杂指令集CPU内部为将较复杂的指令译码，也就是指令较长，分成几个微指 令去执行，正是如此开发程序比较容易（指令多的缘故），但是由于指令复杂， 执行

10、工作效率较差，处理数据速度较慢，PC中Pentium的结构都为CISC CPU二、计算题1、Amdahl定律（见书P10两个例子）系统中某一部件由于采用更快的执行方式后，整个系统性能的提高与这种执行方 式的使用频率或占总执行时间的比例有关。可改进部分的比例：可改进部分的执行时间Fe 改进前整个任务的执行 时间改进部分的加速比：C 改进前改进部分的执行 时间Se 二，改进后改进部分的执行时间改进后整个系统的加速比达到:s=T01(1-Fe) S题假定我们利用增加向量处理模块来提高计算机的运算速度。计算机处理向量的速度比其通常的运算要快20倍。我们将可用向量处理部分所花费的时间占总 时间的百分比称

11、为可向量化百分比。1）求出加速比S和可向量化百分比F之间的关系式。2）当要得到加速比为2时的可向量化百分比F为多少？解1）1(1 -F) F/202020-19 F2） 由上式,将S=2代入得:F = 10/19 = 0.53 2、CPI 和等效 CPI（ P11）平均时钟周期数CPI:平均每条指令执行所需的时钟周期。越少，程序执行越快。这主要取决于 CPU的体系结构，包括指 令系统的设计、指令时序过程的安排等。CPI的含义：以CPU为评估的模块，以指令系统中各条指令被执行的概率 （频度）为依据，以平均每条指令所花费的时钟周期数标尺，对CPU的速度进行评估。CPU时间=CPU时钟周期数/频率；

12、CPU时间=CPU时钟周期数*时钟周期长；CPU 时间=（IC*CPI）/频率 f ；平均时钟周期数CPI=CPU时钟周期数/IC （指令的条数）；nCPU的时钟周期数=7 （CPIi Ii）i WnE（CPli） nICPI 二 g（CPIj AICy ' IC通常用MIPS和MFLOPS反映系统（CPU）吞吐率：MIPS （ Millio n In structio ns Per Seco nd）指令条数fMIPS =执行时间 *106 =CPI *106MFLOPS （ Millio n Float ing poi nt Operatio ns Per Seco nd）程序中的浮

13、点操作次数MFLOPS =执行时间*106题有效(平均)CPI计算假设在一台40MHZi理机上运行200,000条指令的目标代码，程序主要由四种指令组成。根据程序跟踪实验结果，已知指令混合 比和每种指令所需的指令数如下。计算在单处理机上用跟踪数据运行程序的平均 CPI,并根据所得的CPI,计算相应的MIPS速率。指令类型CPI指令混合比算术和逻辑160%高速缓存命中的加载/存储218%转移412%高速存储缺失的存储器访问810%解CPI = 1*60% + 2*18% + 4*12% + 8*10%= 2.24MIPS = f/(CPI*106) = (40*10 6)/(2.24*10 6)

14、 = 17.86题A机执行的程序中有20%转移指令(2TC)，转移指令都需要一条比较指令(1TC)配合，其他指令 仃CoB机中转移指令包含比较指令，但TC比A机慢15% A机、B机哪个工作速度快？A 机：TCPUA=INA X (0.2 X 2+0.2 X 1+0.6 X 1)XTCA=1.2 INA XTCAB 机：TCPUB=0.8INA X (0.2/0.8) X 2+(1- 0.2/0.8) X 1) X15TCA=1.15 INA 灯CA结果：B机比A机工作速度快。注意：不能仅按主频衡量系统性能。等效指令速度：吉普森(Gibs on)法：加减法50%，乘法15%，除法5%，程 序控制

15、15%，其他15%静态指令使用频度：在程序中直接统计 动态指令使用频度：在程序执行过程中统计n等效指令执行时间T二 (Time i Weight i) n7等效 CPI 二' (CPI i Weight i)71等效指令速度MIPS二丁T Weight iy MIPS题假设在一般程序中浮点开平方操作 FPSQR所占的比例为2%，它的CPI为 100;其他浮点操作FP所占的比例为23%，它的CPI = 4.0;其余75%指令的CPI =1.33，计算该处理机的等效 CPI。如果FPSQR操作的CPI也为4.0,重新计算 等效CPIo等效 CPI1=%+'%+1用 75%= 3.9

16、2等效 CPI2=%+% = 2.00改进了在用户程序中仅占2%的开平方操作，整个机器的等效运算速度提高了近 一倍。题我国早期研制的一种小型计算机 DJS-130定点16位，加法指令每秒50万次, 但没有硬件乘除法指令。用软件实现乘除法，速度低100倍左右。求等效指令速 度。解：等效指令速度为：1等效指令速度 MIPS0.02 MIPS(0.80 丄 0.20、(0.50.5/100”即每秒2万次，由于用软件实现乘除法，等效指令速度降低了25倍3、Huffman 编码(见 P92 例)最短平均长度H = -' pi l o (g pii T(其中：Pi表示第i种操作码在程序中出现的概率

17、)固定长操作码相对于Huffman操作码的信息冗余量为:n-乞 pi log2 piR = 1 -log? nl采用Huffman编码法操作码的最短平均长度可以通过如下公式计算:nH 八 Pi lii=1Huffman操作码的主要缺点：操作码长度很不规整，硬件译码困难律 与地址码共同组成固定长的指令比较困难4、替换策略：FIFO, LRU, OPT， 组相联，命中率命中率定义：在M1存储器中访问到的概率其中：N1是对M1存储器的访问次数N2是对M2存储器的访问次数 访问周期与命中率的关系：T = HT1 + (1 H)T2当命中率H 1时，TT1存储系统的访问效率：T1T1=T H T1 (1

18、 - H) T21T2H (1H)T2f(H, 丁)T1访问效率主要与命中率和两级存储器的速度之比有关提高存储系统速度的两条途径：一是提高命中率H ,二是两个存储器的速度不要相差太大其中：第二条有时做不到(如虚拟存储器)，这时，只能依靠提高命中率T2= 105 T例3.2:在虚拟存储系统中，两个存储器的速度相差特别悬殊，例如:1。如果要使访问效率到达e= 0.9，问需要有多高的命中率？0.9(P166替换算法)例3.9： 一个程序共有5个页面组成，在程序执行过程中，页面地址流如下：P1,P2, P1, P5, P4, P1, P3, P4, P2, P4 假设分配给这个程序的主存只有 3个页面

19、。 给出用FIFO、LRU和OPT三种页面替换算法对这3个主存页面的调度情况 表，并统计页面命中次数。 计算这LRU页面替换算法的页面命中率。 假设每个数据平均被访问30次，为了使LRU算法的失效率小于10-5，计算 页面大小至少应该为多少？ 解：(1)FIFO、LRU和OPT的页面命中次数分别为2次、4次和5次(2)LRU页面替换算法的页面命中率为：Hp= 4/10 = 0.45H (1 - H ) 10 1-Hp 1二0.4 .=- <100.9H+ 90000(1-H) = 189999.1 H= 89999计算得： H = 0.999998888877777 0.999999例3

20、.3:在一个Cache存储系统中，当Cache的块大小为一个字时，命中率 H = 0.8;假设数据的重复利用率为 5, T2 = 5T1。计算块大小为4个字时，Cache存 储系统的命中率？并分别计算访问效率。n = 4X 5 = 20,采用预取技术之后，命中率提高到:H2H n -10.8 20-120= 0.99当Cache块大小为一个字时：H = 0.8,访问效率为：e1 =化0.8+5(10.8) =1/1.8 = 0.55 当Cache块大小为4个字时：H2 =0.99, 访问效率为：e2="0.99+ 5(1-0.99) =1/1.04 = 0.96解得P > 20

21、00字页面大小应该为2K字例：a program :P1, P2, P1, P5, P5, P1, P3, P4, P3, P4 page frame is 3 pagesFIFO、LRU、OPT。例：有一个Cache存贮器，主存共分8个块(0 7), Cache为4个块(0 一 3), 采用组相联映象，组内块数为2块，替换算法为近期最少使用法(LRU)。(1) 画出主存、Cache地址的各字段对应关系(标出位数)图(2) 画出主存、Cache空间块的映象对应关系示意图(3) 对于如下主存块地址流：1，2，4，1，3，7, 0，1, 2, 5, 4, 6, 4, 7, 2,如主存中内容一开始末

22、装入 Cache中，请列出Cache中各块随时间的使用 状况解：首先应根据题意，求得主存和 Cache地址中各字段之位数。Cache 4块，组 内2块，所以组数为2组，即组号可有0或1之分。组内块号s为1位。主存8 块，Cache 4块，所以区号nd为1位。由于组相联采用的映象规则是组间直接，组内相联，所以由主存块地址号，先要判断其是在哪一个组中，然后就只能在该组中装入或替换。0组和I组，每组都有其自己的装入和替换问题。程序运行时，由给出的主存块地址流可得到Cache中各个块的使用状况,如表所示。表中标*的是候选替换块的块号时旧t1 2 3 斗 5 6 7 8 9 1（）丨 1 12 1.3

23、14 15Mr块地 址124137012 546472Cache块011 1 I* 1 1 1 P 1 1 1* 4 4 4 4 斗4 斗总4卑4帝（） 0* （）* 、 5韭 气帝5雜5帝 S232 2 2 2* 7 7 7 7* 7* 7* 6 6 6* 23 3* 3 3* 2 2 2 2* 2* 7 严命中情况夫失失II失替替H替替替替H替替4N ik例：一个二级存储层次，采用全相联映象和最久没有使用算法，实存共5页，为2道程序分享，页地址流分别如下P1 =1 2 3 4 1 3 2 1P2 = 1 2 3 4 2 2 3 3试作2个实存分配方案，分别使2道程序满足(1) 命中率相同；

24、(2) 命中次数之和最大。解：分别为2道程序作“堆栈模拟图”，其中“V”表示命中。1234)1321命中次数N123413211234132123411312244场-10吩20叫=37V2幼-41V1斗ni1234*(02斗n7£4221%)4422N叫44461+42+33+24+1F严12342233命屮次数N123422312344寸12334斗11111小1ii2ik=2112n311114n2- 4iiVi Vi V斗将两图结果综合，得到4个分配方案的命中率情况表如下结论如下命中率相同的方案是n仁3而n2= 2 ；命中次数之和最大的方案是 n仁4而n2= 1题在一个Cac

25、he存储系统中，主存储器的访问周期、存储容量和单位价格分 别为60ns、64MB和10元/MB, Cache的访问周期、存储容量和单位价格分别为10ns、512KB和 100 元/MB, Cache 的命中率为 0.98。(1) 计算这个Cache存储系统的等效访问周期、存储容量和单位价格(2) 计算这个Cache存储系统的访问效率。解：(1)这个Cache存储系统的等效访问周期：T = Tc H + Tm (1 H)=10nsx0.98 + 60ns x( 1 0.98)=11ns等效存储容量：S = 64MB等效单位价格：C = ( Cc Sc + Cm Sn) / (Sc + Sm)=(

26、100X 0.5 + 10X 64) / (0.5 + 64)=10.7(元/MB)(2)这个Cache存储系统的访问效率：e = Tc/T=10/11=0.91(2)三种映射框图题假定计算机的主存储器按64块组织，块大小为8个字。高速缓存有8个块 框。试画出采用以下映射方法从主存储器到高速缓存的映射关系。 尽可能清楚地 画出所有的映射线。(1) 直接映射。全相联映射。解(1)直接映射方式存储器地址主存储器(2)全相联映射方式存储器地址主存储器5、中断调度，调度图例4.2:某处理机共有4个中断源，中断优先级从高到低分别是：1级、2级、3 级和4级。当处理机在执行主程序时，同时有3级和2级两个中

27、断源向处理机发 出中断服务请求。当处理机为2级中断源服务时又有4级中断源发出中断服务请 求。当处理机为4级中断源服务时又有1级中断源发出中断服务请求。解：处理机响应各中断源的中断请求和执行中断服务程序的过程如下：中断请求 主程序中断服务程序1级2级3级4级2、3 级4级时间t按照中断优先级响应中断请求的例子例4.3:有四个中断源D1、D2、D3和D4，它们的中断优先级从高到低分别是 1 级、2级、3级和4级。这些中断源的正常中断屏蔽码和改变后的中断屏蔽码见 下表。每个中断源一位，共4位屏蔽码。中断源名称中斷优趣正鮒断屏聘叽必口凶变后的中断屏蔽码Dj D3 D3 D(D11111110 0 0D

28、220 1111 L 0 0D330 0 111 L 1 0EH40 0 0 11 L 11解：如果4个中断源都使用正常的中断屏蔽码，处理机的中断服务顺序将严格按照中 断源的中断优先级进行。如果改变中断屏蔽码，当D1、D2、D3和D4这4个中断源同时请求中断服务时, 处理机实际为各个中断源服务的先后次序就会改变。处理机响应的顺序是 D1、D2、D3、D4实际服务的顺序是D4、D3、D2、D1中断请求 主程序中断服务程序Di D 2 D 3 D 4D|,D2,D 3Q4时间t1方法二：改变处理机优先级例4.4：某处理机共有4个中断源D1、D2、D3和D4，它们的硬件中断优先级 从低到高分别为1级

29、、2级、3级和4级。处理机本身的优先级最低，为 0级。 在中断源Di、D2、D3、D4的中断向量中，程序员为它们设置的优先级分别为 4级、3级、2级、1级。解：在处理机状态字中设置 3个中断屏蔽位。000为处理机本身的优先级，001100分别表示4个中断源的中断优先级。当4个中断源同时请求中断服务时，解：处理机实际完成中断服务的过程是D3、D2、D4、D16、通道流量计算通道的容量，工作周期三种通道的最大流量计算公式:fMAX.BYTE =(Ts+ Td) p nTs+ Td字节/秒fMAX.SELETE 二(Ts/n +Td) p nTs/n +TdfMAX.BLOCKp n(Ts/ k T

30、d) p nTiTT帀字节/秒为保证通道不丢失数据，通道的实际流量应不大于通道最大流量:fBYTE < fMAX BYTEfSELETE < fMAX SELETEfBLOCK < fMAX BLOCK例4.5: 一个字节多路通道连接 D1、D2、D3、D4、D5共5台设备，这些设备 分别每10us、30us、30us、50us和75us发出一次数据传送请求。(1) 计算这个通道的实际流量和工作周期。(2) 如果这个字节多路通道的最大流量正好等于通道实际流量，并假设数据传输率高的设备，其优先级也高。5台设备在0时刻同时向通道发出第一次传送数 据的请求，并在以后的时间里按照各自

31、的数据传输率连续工作。画出通道分时为各台设备服务的时间图，并计算处理完各设备的第一次请求的时刻。(3) 从时间图中发现什么问题？如何解决？解：(1)通道的实际流量为：fBYTE = (1/10+1/30+1/30+1/50+1/75)MB/S = 0.2MB/S通道的工作周期为：t= 1/fBYTE = 5us通道处理完各设备这个第一次请求的时间：01020304050607080DiiJJeJ1J ta1,tD2h.11 tD3卜1tD4 i，tD51tlb(2) 处理完各设备这个第一次请求的时间：D1: 5us；D2： 10us；D3： 20us；D4： 30usoD5的第一次请求没有响应

32、，数据丢失D5的第一次请求没有得到响应的原因分析对所有设备的请求时间间隔取最小公倍数， 在这一段时间内通道的流量是平 衡的。可以采取下列方法：方法一：增加通道的最大工作流量。例如，把通道的工作流量增加到 0.25MB/S （工作周期为4us）。方法二：动态改变设备的优先级。例如，在 30us至70us之间临时提高设备 D5的优先级。方法三：增加缓冲存储器。例如，只要为设备D5增加一个数据缓冲寄存器， 它的第一次请求可以在第 85us处得到响应，第二次请求可以在第 145us处得到 响应。7、流水（静/动）时空图 （非线性流水有返回）吞吐率 效率 相关性问题处理 不过不知道是不是大题 例5.2:

33、用一条4段浮点加法器流水线求8个浮点数的和：Z = A + B + C+ D + E+ F+ G+ H解：Z= (A + B) + (C + D) + (E + F) + (G+ H)F空间周期12345678910111213规格化:123456尾数加123456对阶123456JF求阶差123456Z加数 加数 结果ABCDE GA+B E+FA+B+C+DF HC+D G+HE+F+G+HA+B C+D E+F g+H A+B+C+DE+F+G+H用一条4段浮点加法器流水线求8个数之和的流水线时空图时间14 157个浮点加法共用了流水线的吞吐率为:流水线的加速比为:流水线的效率为:i =Tk015讥_ To4 7讥Tk15吐T04 7辻15个时钟周期。1 87k Tk题一动态多功能流水线由6个功能段组成，如下图:21其中：si、S4 S5 S6组成乘法流水线，S1、S2、S3 S6组成加法流水线， 各个功能段时间均为50ns。假定该流水线的输出结果可以直接返回流水线输入 端，而且设置有足 够的缓冲寄存器。若按照最快的方式用该流水线 计算5f =為 XiyiZ。i 4（1）请画出其处理过程的时空图。（2）计算其实际吞吐率，加速比和效率。解：乘法操作用到的流水段有：Si、S4、S5、S6;加法操作用到的流水段有：Si、S2、S3、S6。以最快的方式处理的流水线时空图如图所