体系结构复习重点

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

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

7、分类，把计算机系统分4、多指令流单数据流、多指令流大类：单指令流单数据流、单指令流多数据流多数据流10并行等级划分（1）指令内部并行：指令内部的微操作之间的并行。（2）指令级并行 （InstructionLevel Parallel ，ILP）:并行执行两条或多条指令。（3） 任务级或过程级并行：并行执行两个或多个过程或任务（程序段）。（4）作业或程序级并行：在多个作业或程序间的并行11堆栈型机器通用计算型一种计算模型。这种类型的电脑，内存以堆栈（Stack）储存。它的指令集中包 含了零位址指令（"0-0perand" 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 _丄亠八,改进后改进部分的执行时间改进后整个系统的加速比达到:Tn (1 Fe) g题假定我们利用增加向量处理模块来提高计算机的运算速度。计算机处理向量的速度比其通常的运算要快20倍。我

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

12、时间二CPU时钟周期数/频率；CPU时间二CPU时钟周期数*时钟周期长；CPU 时间=（IC*C PI） / 频率 f ；平均时钟周期数CP匸CPU时钟周期数/IC （指令的条数）；n（CP lii 1CPU的时钟周期数li)(C PIi Ii)CPI IC通常用Ml PS和MFL OPS反映系统(CPU) MIPS( Millio n In structio ns Per Seco nd)指令条数n(C Plii 1吞吐率： fMIPS =执行时间 *106 =CPl*106MFL OPS ( Millio n Floati ng poi nt Op eratio ns Per Second

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

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

15、：加减法50%,乘法15%，除法5%,程 序控制15%，其他15%静态指令使用频度：在程序中直接统计动态指令使用频度：在程序执行过程中统计等效指令执行时间Tn等效 CPI (CPIii 1等效指令速度MIPSn(Time n Weight i 1 MIPS Weight i)i 1Weight i)1题假设在一般程序中浮点开平方操作 FPSQR所占的比例为2%,它的CPI为 100;其他浮点操作FP所占的比例为23%，它的CPI = 4.0;其余75%指令的CPI =1.33，计算该处理机的等效CPI。如果FPSQR操作的CPI也为4.0,重新计算 等效CP1。等效 CP11 = 100 2%

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

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

18、 T12T H T1 (1 H) T2 H (1 H)舟T1访问效率主要与命中率和两级存储器的速度之比有关提高存储系统速度的两条途径：一是提高命中率H ,二是两个存储器的速度不要相差太大其中：第二条有时做不到(如虚拟存储器)，这时，只能依靠提高命中率例3.2：在虚拟存储系统中，两个存储器的速度相差特别悬殊，例如：T2= 105 T1。如果要使访问效率到达e= 0.9,问需要有多高的命中率？0.9 H (11)1050.9 H+ 90000(1-H) = 189999.1 H= 89999计算得：H = 0.9999988888777770.999999例3.3:在一个Cache存储系统中，当C

19、ache的块大小为一个字时，命中率 H = 0.8;假设数据的重复利用率为 5, T2 = 5T1。计算块大小为4个字时，Cache存 储系统的命中率？并分别计算访问效率。n = 4X 5 = 20,采用预取技术之后，命中率提高到：H n 10.8 20 1H 2 0.99n20当Cache块大小为一个字时：H 0.8,访问效率为：e1 "0.8+5(10.8) 1/1.8 0.55当Cache块大小为4个字时：出 0.99,访问效率为：e2 K0.99+ 5(10.99) 1/1.04 0.96(P166替换算法)例3.9: 个程序共有5个页面组成，在程序执行过程中，页面地址流如下

20、：P1,P2, P1, P5, P4, P1, P3, P4, P2, P4假设分配给这个程序的主存只有 3个页面。(1) 给出用FIFO、LRU和OPT三种页面替换算法对这3个主存页面的调度情况 表，并统计页面命中次数。(2) 计算这LRU页面替换算法的页面命中率。(3) 假设每个数据平均被访问30次，为了使LRU算法的失效率小于10-5，计算 页面大小至少应该为多少？解：(1)FIFO、LRU和OPT的页面命中次数分别为2次、4次和5次(2)LRU页面替换算法的页面命中率为：Hp= 4/10 = 0.4丄 g 105n 30P解得P > 2000字页面大小应该为2K字。例：a Pro

21、gram :P1, P2, P1, P5, P5, P1, P3, P4, P3, P4 page frame is 3 page®FIFO、LRU、OPT。t12345678910# of hitP1P2P1P5P4P1P3P4P2P4FIFO1111*444*4*222次2222*1111*4555*3333*loadlhlrepreprhrrLRU11111111*224次222*444*44455*5*333*3*llhlrhrhrhOPT111111*3*3*335次2222*222225*444444llhlrhrhhh例：有一个Cache存贮器，主存共分8个块(0 7)

22、, Cache为4个块(0 一 3), 采用组相联映象，组内块数为2块，替换算法为近期最少使用法(LRU)。(1)(3)7, 2， 状况 解：首先应根据题意，求得主存和画出主存、Cache地址的各字段对应关系(标出位数)图1 ， 2, 4， 1, 3, 7, 0, 1, 2, 5, 4, 6, 4,Cache中，请列出Cache中各块随时间的使用画出主存、Cache空间块的映象对应关系示意图 对于如下主存块地址流：如主存中内容一开始末装入Cache地址中各字段之位数。Cache 4块，组内2块，所以组数为2组，即组号可有0或1之分。组内块号s为1位。主存8 块，Cache 4块，所以区号nd为

23、1位。由于组相联采用的映象规则是组间直接，组内相联，所以由主存块地址号，先要判断其是在哪一个组中，然后就只能在该组中装入或替换。0组和I组，每组都有其自己的装入和替换问题。2細A 4Hlle le时间t1 2 5 4 5 6 7 X 9 10 1112 15 14 15匸存块地址12413712546473Cache块011 1 1* 1 1 1 1* J 1 r 4 4 4 4 44 4* 4* 4* 0 Q* （）* 5 5* 5* 5* 5* 5*1r2 2 2 2* 7 7 7 7* 7* 7* 6 6 6* 23 3* 3* 3* 2 2 2 2* 2* 7 7*命H' t4

24、况矢失矢II天賛普II普替R n II W nCache中各个块的使用状况,程序运行时，由给出的主存块地址流可得到 如表所示。表中标*的是候选替换块的块号。例：一个二级存储层次，采用全相联映象和最久没有使用算法，实存共 页，为2道程序分享，页地址流分别如下P1 =1 2 3 4 1 3 2 1P2 = 1 2 3 4 2 2 3 3试作2个实存分配方案，分别使2道程序满足(1) 命中率相同；(2) 命中次数之和最大。解：分别为2道程序作“堆栈模拟图”，其中“2”表示命中。12541521命屮次績凡h123413211234132J54J31十244萨10-11|= 20nr 32叫=4/114

25、P、=13453金屮玄数N由123422A3I2.11J7212J4411111tb= 1、lb- 2tb" 3I 4n*= 4、1l4将两图结果综合，得到4个分配方案的命中率情况表如下I34(Ju2443T1N.=)4472444664->N(i) /*%)1+42+33+24-1结论如下命中率相同的方案是n仁3而n2= 2 ；命中次数之和最大的方案是n仁4而n2= 1题在一个Cache存储系统中，主存储器的访问周期、存储容量和单位价格分别为60ns、64MB和10元/MB, Cache的访问周期、存储容量和单位价格分别为10ns、512KB和 100 元/MB, Cache

26、 的命中率为 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 Sm / (Sc + Sm)=(100x 0.5 + 10x 64) / (0.5 + 64)=10.7(元/MB)(2)这个Cache存储系统的访问效率：e = Tc/T=10/11=0.91(2) 三种映射框图题假定计算机的主存

27、储器按64块组织，块大小为8个字。高速缓存有8个块 框。试画出采用以下映射方法从主存储器到高速缓存的映射关系。 尽可能清楚地 画出所有的映射线。(1)直接映射。全相联映射。解(1)直接映射方式主存储器存储器地址(2)全相联映射方式5、中断调度，调度图中断优先级从高到低分别是：1级、2级、3例4.2：某处理机共有4个中断源，级和4级。当处理机在执行主程序时，同时有3级和2级两个中断源向处理机发 出中断服务请求。当处理机为2级中断源服务时又有4级中断源发出中断服务请 求。当处理机为4级中断源服务时又有1级中断源发出中断服务请求。解：处理机响应各中断源的中断请求和执行中断服务程序的过程如下：中断请求

28、主程序中断服务程序1级2级3级4级2、3级4级时间t按照中断优先级响应中断请求的例子例4.3：有四个中断源D1、D2、D3和D4，它们的中断优先级从高到低分别是 1 级、2级、3级和4级。这些中断源的正常中断屏蔽码和改变后的中断屏蔽码见 下表。每个中断源一位，共4位屏蔽码。屮断源名称中断优做正轴断屏彌DgD, D.改变后的中断屏rtJ湘D, D, D, 0D11111110 0 011220 111110 01島3()0111110IM40 0 0 1i 1 i i解：如果4个中断源都使用正常的中断屏蔽码，处理机的中断服务顺序将严格按照中 断源的中断优先级进行。如果改变中断屏蔽码，当D1、D2

29、、D3和D4这4个中断源同时请求中断服务时, 处理机实际为各个中断源服务的先后次序就会改变。处理机响应的顺序是 D1、D2、D3、D4实际服务的顺序是D4、D3、D2、D1中断请求 主程序中断服务程序方法二：改变处理机优先级例4.4:某处理机共有4个中断源D1、D2、D3和D4,它们的硬件中断优先级 从低到高分别为1级、2级、3级和4级。处理机本身的优先级最低，为 0级。 在中断源D1、D2、D3、D4的中断向量中，程序员为它们设置的优先级分别为 4级、3级、2级、1级。解：在处理机状态字中设置3个中断屏蔽位。000为处理机本身的优先级，001100分别表示4个中断源的中断优先级。当4个中断源

30、同时请求中断服务时，D3、D2、D4、D1解：处理机实际完成中断服务的过程是6、通道流量计算通道的容量，工作周期 三种通道的最大流量计算公式：fMAX.BYTEfMAX.SELETE字节/秒(Ts+ Td) P n Ts+ TdP n(Ts/n Td) p n1字节/秒Ts/n TdfMAX.BLOCK(Ts/k TD) p n字节/秒为保证通道不丢失数据，通道的实际流量应不大于通道最大流量: fBYTE < fMAX BYTEfSELETE < fMAX - SELETEfBLOCK < fMAX BLOCK例4.5： 一个字节多路通道连接 D1、D2、D3、D4、D5共5

31、台设备，这些设备 分别每10us、30us、30us、50us和75us发出一次数据传送请求。(1) 计算这个通道的实际流量和工作周期。(2) 如果这个字节多路通道的最大流量正好等于通道实际流量，并假设数据传输率高的设备，其优先级也高。5台设备在0时刻同时向通道发出第一次传送数 据的请求，并在以后的时间里按照各自的数据传输率连续工作。画出通道分时为各台设备服务的时间图，并计算处理完各设备的第一次请求的时刻。(3) 从时间图中发现什么问题？如何解决？ 解：(1)通道的实际流量为：fBYTE = (1/10+1/30+1/30+1/50+1/75)MB/S = 0.2MB/S通道的工作周期为：t=

32、 1/fBYTE = 5us通道处理完各设备这个第一次请求的时间：01020304050607080D2 t 1 11 nt D3 TJLn1 I11t ,D4 nibtD5 IDih h ht (2)处理完各设备这个第一次请求的时间:D1:D2：D3：D4：5us；10us；20us；30usoD5的第一次请求没有响应，数据丢失。D5的第一次请求没有得到响应的原因分析对所有设备的请求时间间隔取最小公倍数， 在这一段时间内通道的流量是平 衡的。可以采取下列方法：方法一：增加通道的最大工作流量。例如，把通道的工作流量增加到 0.25MB/S （工作周期为4us）。方法二：动态改变设备的优先级。例

33、如，在 30us至70us之间临时提高设备 D5的优先级。方法三：增加缓冲存储器。例如，只要为设备D5增加一个数据缓冲寄存器， 它的第一次请求可以在第85us处得到响应，第二次请求可以在第 145us处得到 响应。7、流水（静/动）时空图 （非线性流水有返回）吞吐率 效率 相关性问题处理 不过不知道是不是大题 例5.2:用一条4段浮点加法器流水线求8个浮点数的和：Z = A + B + C+ D + E+ F+G+ H解：Z= (A + B)+ (C + D) + (E + F)+ (G+ H)周期规格化尾数加对阶求阶差加数加数结果1d12345J61 '234561234561234

34、56ABCD2345678910 1112 13 14 15E GA+B E+FF HC+D G+HA+B C+D E+F g+H八空间1A+B+C+DE+F+G+H A+B+C+DZ时间E+F+G+H用一条4段浮点加法器流水线求8个数之和的流水线时空图7个浮点加法共用了流水线的吞吐率为:流水线的加速比为:流水线的效率为:>Tk15 t 0T04 7tTk15tT04 7t15个时钟周期。47*87E k Tk4 15 t0 47题一动态多功能流水线由6个功能段组成，如下图:2其中：s1、S4 S5 S6组成乘法流水线，S1、S2、S3 S6组成加法流水线， 各个功能段时间均为50ns。假定该流水线的输出结果可以直接返回流水线输入 端，而且设置有足 够的缓冲寄存器。若按照最快的方式用该流水线 计算5fXiViZ。i 1(1) 请画出其处理过程的时空图。(2) 计算其实际吞吐率，加速比和效率。解：乘法操作用到的流水段有：S1、S4、S5、S6;加法操作用到的流水段有：S1、S2、S3、S6。以最快的方