扬州大学计算机体系结构试卷

1、CPU性能计算2、计算机系统设计的定量原理1）只加快经常性事件的速度:使经常性事件的速度尽可能处理快,而对不经常发生处理得慢也不会对系统性能有太大影响。2）Amdahl定律:系统中某一部件由于采用某种更快的执行方式后整个系统性能提高与这种执行方式的使用频率或总执行时间的比例有关。n Fe=(改进前可改进部分占用的时间)/(改进前整个任务的执行时间)，即改进部分所占比例。n Se=(改进前改进部分的执行时间)/(改进后改进部分的执行时间)，即改进部分的加速比 则: 1.改进后的整个任务的执行时间为: Tn=To(1-Fe+Fe/Se) 其中,To为改进前的整个任务的执行时间 2.改进后的整个系统

2、加速比为: SP=To/Tn=1/(1-Fe)+Fe/Se例1 假设将某系统的某一部件的处理度加快到10倍,但该部件的原处理时间仅为整个运行时间的40%,则采取加快措施后整个系统的性能提高多少?解:由题意知:Fe=0.4,Se=10,根据Amdahl定律,SP=1/(0.6+0.4/10)=1/0.64=1.56. Amdahl定律告诉我们:一项改进措施可以使整个系统的性能提高多少;为了改进性能价格比,如何合理分配系统资源.例2 采用哪种实现技术来求浮点数平方根FPSQR 操作对系统的性能影响较大.假设FPSQR操作占整个程序执行时间的20%.一种使采用FPSQR硬件,使FPSQR操作的速度加

3、快到10倍.另一种是使所有浮点数据指令的速度加快,使FP指令的速度加快到2倍,还假设FP指令占整个执行时间的50%.请比较这两种方案.解:分别计算这两种设计方案所能得到的加速比: SFPSQR=1/(1-0.2)+0.2/10=1/0.82=1.22 SFP=1/(1-0.5)+0.5/2=1/0.75=1.33 -更好3） CPU性能公式n CPU的性能取决于三个要素：n 时钟频率f(或时钟周期t)；n 每条指令所花的时钟周期数CPI；n 指令条数ICn 一个程序所花的CPU时间(T)可以表示：n CPU时间(T)=CPU时钟周期数(CPI×IC)*时钟周期长(t) n 每条指令的

4、平均时钟周期数：n CPU时钟周期数=å(CPIi*Ii )n CPU时间(T)=时钟周期长度*å(CPIi*Ii )n CPI=å(CPIi*Ii )/ IC=å(CPIi*Ii /IC)Ii是第i种指令的执行次数Ii/IC是第i种指令所占比例n 例3如果FP操作的比例为25%，FP操作的平均CPI=4.0，其它指令的平均CPI为1.33，FPSQR操作的比例为2%， FPSQR的CPI为20。假设有两种设计方案，公别把FPSQR操作的CPI和所有FP操作的CPI减为2。试利用CPU性能公式比较这两种设计方案哪一个更好(只改变CPI而时钟频率和指令条数

5、保持不变)。解：原系统的CPI=25%×4+75%×1.33=2方案1(使FPSQR操作的CPI为2)系统CPI=CPI原-2%×(20-2)=2-2%×18=1.64方案2(提高所有FP指令的处理速度)系统CPI=CPI原-25%×(4-2)=2-25%×2=1.5我们也可以根据以下公式计算出方案2系统的CPICPI= 75%×1.33+25%×2=1.5显然，提高所有FP指令处理速度的方案要比提高FPSQR处理速度的方案要好。方案2的加速比=2/1.5= 1.33例4假设这两台机器的指令系统中，执行条件转移指令

6、需2个时钟周期，而其它指令只需1个时钟周期。CPUA:采用一条比较指令来设置相应的条件码，由紧随其后的一条转移指令对此条件码进行测试，以确定是否进行转移。显然实现一次条件转移要执行比较和测试两条指令。条件转移指令占总执行指令条数的20%。由于每条转移指令都需要一条比较指令，所以比较指令也将占20%。CPUB采用比较功能和判别是否实现转移功能合在一条指令的方法，这样实现一条件转移就只需一条指令就可以完成。由于CPUB在转移指令中包含了比较功能，因此它的时钟周期就比CPUA要慢25%。现在要问，采用不同转移指令方案的CPUA和CPUB，那个工作速度会更快些？n 解：CPIA=0.2×2+

7、0.8×1=1.2 TCPUA=ICA×1.2×tA CPUB转移指令为20%÷80%=25% CPIB = 0.25×2+0.75×1=1.25 由于CPUB中没有比较指令，因此ICB = 0.8×ICA。 t B = 1.25tA TCPUB = ICB×CPIB×tB = 0.8 ICA×1.25×1.25tA = 1.25 ICA×tA可见TCPUA比TCPUB小，所以CPUA比CPUB运行得更快些。n 例5在例4中，如果CPUB的时钟周期只比CPUA的慢10%，那么

8、哪一个CPU会工作得更快些？n 解：n TCPUA = 1.2ICA ×tA , 因tB = 1.10tA，所以TCPUB = 0.8 ICA×1.25×1.10tA= 1.10 ICA ×tA,由于CPUB所需时间较少，所以CPUB比CPUA运行得更快些。例6：用一台40MHz处理机执行标准测试程序，它含的混合指令数和相应所需的时钟周期数如下：指令类型指令数时钟周期数整数运算45000 1数据传送32000 2浮点15000 2控制传送8000 2求有效CPI，MIPS速率（百万条指令/秒）和程序的执行时间。解：CPI=(45000*1+32000*2

9、+15000*2+8000*2)/ (45000+32000+15000+8000) =1.55周期/指令MIPS速率=F/(CPI*106)=40*106/(1.55*106) =25.8 MIPS程序执行时间T=(45000*1+32000*2+15000*2+8000*2)/ (40* 106)=3.875*10-3秒2.Flynn分类法1966年，Michael.J.Flynn提出根据指令流、数据流的多倍性（multiplicity）特征对计算机系统进行分类，定义如下。·指令流：机器执行的指令序列计算机体系结构·数据流：由指令流调用的数据序列，包括输入数据和中间结果

10、·多倍性：在系统性能瓶颈部件上同时处于同一执行阶段的指令或数据的最大可能个数。Flynn根据不同的指令流-数据流组织方式把计算机系统分为4类。1·单指令流单数据流（SingleInstructionStreamSingleDataStream，SISD）SISD其实就是传统的顺序执行的单处理器计算机，其指令部件每次只对一条指令进行译码，并只对一个操作部件分配数据。2·单指令流多数据流（SingleInstructionStreamMultipleDataStream，SIMD）SIMD以并行处理机为代表，结构如图，并行处理机包括多个重复的处理单元PU1PUn，由单

11、一指令部件控制，按照同一指令流的要求为它们分配各自所需的不同的数据。3·多指令流单数据流（MultipleInstructionStreamSingleDataStream，MISD）MISD的结构，它具有n个处理单元，按n条不同指令的要求对同一数据流及其中间结果进行不同的处理。一个处理单元的输出又作为另一个处理单元的输入。4·多指令流多数据流（MultipleInstructionStreamMultipleDataStream，MIMD）MIMD的结构，它是指能实现作业、任务、指令等各级全面并行的多机系统，多处理机就属于MIMD。（2）冯式分类法1972年冯泽云提出用最

12、大并行度来对计算机体系结构进行分类。所谓最大并行度Pm是指计算机系统在单位时间内能够处理的最大的二进制位数。设每一个时钟周期ti内能处理的二进制位数为Pi，则T个时钟周期内平均并行度为Pa=(Pi)/T(其中i为1，2，T)。平均并行度取决于系统的运行程度，与应用程序无关，所以，系统在周期T内的平均利用率为=Pa/Pm=(Pi)/(T*Pm)。用最大并行度对计算机体系结构进行的分类。用平面直角坐标系中的一点表示一个计算机系统，横坐标表示字宽(N位)，即在一个字中同时处理的二进制位数；纵坐标表示位片宽度(M位)，即在一个位片中能同时处理的字数，则最大并行度Pm=N*M。由此得出四种不同的计算机结

13、构：字串行、位串行(简称WSBS)。其中N=1，M=1。字并行、位串行(简称WPBS)。其中N=1，M>1。字串行、位并行(简称WSBP)。其中N>1，M=1。字并行、位并行(简称WPBP)。其中N>1，M>1。冯氏分类法 1972年冯泽云提出用最大并行度对计算机系统结构进行分类.分为: .字串位串WSBS .字并位串WPBS .字串位并WSBP .字并位并WPBP另外还有HANDLER分类法： 根据并行度和流水线提出的分类方法3.操作码优化n 采用Huffman编码法所得到的操作码的平均长度=0.45×1+0.30×2+0.15×3+0.

14、05×4+0.03×5+0.01×6+0.01×6=1.97(位)n 采用最优Huffman编码法，操作码的最短平均长度=0.45×1.152+0.30×1.737+0.15×2.737+0.05×4.322+0.03×5.059+0.01×6.644+0.01×6.644=1.95(位)采用3位固定长操作码的信息冗余量为：Huffman编码法的信息冗余量仅为：与3位定长操作码的冗余量35%相比要小得多Huffman操作码的优点：平均长度最短，信息的冗余量最小；(2) 等长扩展法n 为

15、了便于实现分级译码，一般采用等长扩展法；n 根据不同的扩展标志，对于等长扩展法还可以有多种不同的扩展方法，衡量的标准主要看这种编码方法的操作码的平均长度是否最短，或信息量的冗余量是否最小； n 用码长表示：例如4-8-12法。n 这并不能说明具体编码方法，n 如下面两种编码方法都是4-8-12法。n 用码点数表示：例如15/15/15法，8/64/512法15/15/15法 每一种码长都有4位可编码位(前面可以有相同的扩展标识前缀)，可产生16个码点(即编码组合)； 使用其中15个来表示事件，留下1个或多个码点组合作为更长代码的扩展标识前缀；8/64/512法 每一种码长按4位分段 每一段中至

16、少要留下1位或多位作为扩展标识，各段剩余的码位一起编码，所产生的码点用来对应被编码事件 每一段中的标识位指出后面还有没有后续段。(3) 不等长编码法小结n 操作码优化的主要目的：尽可能地减少各种信息冗余，即：n 空间、时间少、短，尽可能不要跨断；n 要想程序占地空间小，则应使操作码尽可能短。第五章：时空图为了缩短运算时间，首先应考虑“最少切换算法”，即先执行完所有乘法（任务编号1-6）再执行加法（任务编号7-11），其次在加法中采用“最少相关算法”（即二叉树算法）。 记c1=A1×B1，c6=A6×B6，下图(a)是加法的计算顺序二叉树，注意任务10应该用前一级最早完成的任

17、务7和8的结果，如果用任务9的结果则要推迟1拍启动，使总时间增加1拍。根据时空图(b)得n TP = 11/(22t) = 1/(2t)n S = (6×4t + 5×4t)/(22t) = 2n E = (6×4t + 5×4t)/(6×22t) = 1/3非线性流水线的调度技术n 非线性流水线的调度问题：在非线性流水线的输入端，究竟每间隔多少个时钟周期向流水线输入一个新任务才能使流水线的各个功能段都不发生冲突。n 非线性流水线的调度的任务：找出一个最小的循环周期，按照这个周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的

18、吞吐率和效率最高。n 以下首先介绍非线性流水线的表示方法，然后分析冲突情况，最后介绍无冲突调度方法。非线性流水线的表示 一条非线性流水线的一般需要一个各功能段间的 连接图和一张预约表共同表示。 下图是一条4个功能段组成的非线性流水线，它有从S1到S4 的单方向传输线。但它有两条反馈线和一条前馈线；输出端不一定在最后一个功能段，而可能从任意一个功能段输出。 非线性流水线的预约表对于非线性流水线预约表的说明n 预约表的横坐标表示流水线的时钟周期，纵坐标表示流水线的功能段，中间有“× ”的表示该功能段在这一个时钟周期处于工作状态，即在这个时钟周期有任务通过这个功能段；空白的表示该功能段在这

19、一个时钟周期不处于工作状态。n 预约表行数是非线性流水线的段数；而列数是一个任务从进入流水线到从流水线中输出所经历的时钟周期数。n 一张非线性流水线的预约表可能与多个非线性流水线连接图相对应；同样，一个非线性流水线的连接图也可能对应有多张预约表。非线性流水线的冲突n 非线性流水线的启动距离：向一条非线性流水线的输入端连续输入两个任务之间的时间间隔。n 非线性流水线的冲突：当以某一个启动距离向一条非线性流水线连续输入任务时，可能在某一个功能段或某几个功能段中发生有几个任务同时争用同一个功能段的情况。n 上图所示的非线性流水线中，当启动距离为3时，冲突情况如图：无冲突调度方法n 目标：找出具有最小

20、平均启动时间的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有功能段在任何时间都没有冲突。n 步骤：1、根据预约表求禁止向量进而得到冲突向量。冲突向量是一个M位 的二进制数表示，其中M是禁止向量中的最大值。一般的禁止向量用C=（CmCm-1 C2C1 )表示。如果I在禁止表中，则 Ci=1，否则Ci=0。其中Cm一定为1，因为m必定在禁止表中。如上图所示的预约表，其冲突向量C=（101100）。3.2 虚拟存储器n 虚拟存储器由主存储器和联机工作的外部存储器共同组成。n 在目前的计算机系统中，n 主存储器通常用动态随机存储器(DRAM)实现，它的存储容量相对比较小，速度比较快，单位容量的价格比较贵。n 联机工作的外部存储器通常为磁盘存储器，它的存储容量很大，与主存储器相比，速度很低，单位容