计算机体系结构.doc

Chapter 1计算题l 需求筛选的依据是成本性能比l 直接实现一般指用硬件实现，而间接实现是指用软件实现l 软件和硬件要综合考虑，要以价格性能比高低为取舍原则。l 常用的基本功能或产量很大的功能才适宜于用硬件实现。l 设计者最终要用成本性能比作为软、硬件实现功能的取舍标准；消费者要用价格性能比作为选购计算机系统的取舍标准。l 设计人员的参考原则:n 考虑用户应用领域n 设计周期长的硬件不宜采用n 常用的功能尽量采用硬件实现n 实现功能的成本性能比(或价格性能比)要低n 超前设计l 某一计算机用于商业外贸的事务处理，有大量的字符串处理操作。由于这种商务处理很普遍，有较大的市场，故而设计人员决定在下一代计算机的CPU中加入字符串操作的功能。经测试应用软件调查发现，字符串操作的使用占整个程序运行时间的50%。而增加此功能如用软件(如微程序)实现，则快5倍，增加CPU成本1/5倍；如果用硬件实现，则快100倍，CPU成本增加到5倍。问设计人员提出增加此功能是否恰当？如恰当则此功能应该用软件实现还是用硬件实现？设CPU成本占整机成本的1/3解： 首先来计算机在两种情况下提高的性能和成本性能比。 设： S为CPU未增加字符串功能时的CPU平均速度，Told为此时运行程序的时间，Tnew为增加字符串功能后程序运行的时间，则l Amdahl定律 (性能递减规则)n 某部件应用越频繁，当提高该部件性能时，整机性能也提高的越多。但不管该部件性能提高多大，整机的性能加速不可能大于在原机器中除该部件外所有其它部件运行时间的百分比的倒数1/(1-F)n 计算机性能的改善程度受其采用的快速部件(被提高性能的部件)在原任务中使用所占的时间百分比的限制nl 采用新器件使某一功能性能提高10倍，但该功能的使用只占原程序运行时间的40%。请计算新计算机性能改善了多少？ll 高频事件高速处理(大概率事件优先的原则)l 局部性原理n 最重要的是90/10局部性规则n 时间局部性n 空间局部性l 适应计算机发展趋势l 在指令系统中指令的确定是属于计算机系统结构的，而指令操作的实现，如取指令、取操作数、运算、送结果等具体操作及排序方式是属于计算机组成的，而实现这些指令功能的具体电路、器件的设计及装配技术是计算机物理实现的l 计算机的性能是指在计算机上完成用户的应用任务所需的时间长短l 响应(实耗)时间是指计算机系统完成某一任务(程序)所花费的时间n 速度，即用响应时间的倒数n 用速度来评价性能，我们称“高”为性能好；如果用响应时间来评价性能，我们称“短”为性能好l 计算机整机性能分成两部分：一是CPU执行程序的时间，二是等待时间。提高计算机性能就是提高CPU性能和减少等待时间。l CPU时间也包含两部分，即用户CPU时间(user CPU time)和系统CPU时间(system CPU time)l CPUtime =整个程序的总时钟数时钟周期l 每条指令的平均时钟周期数(Clock cycles Per Instruction)，简称为CPIl 指令数CPI代替总时钟数l 设条件转移指令的实现有两种方案可以选择。机器A：用两条指令完成。由比较指令建立条件码，再在转移指令中测试条件码。机器B：只用一条指令。比较和转移一起执行。对于这两种机器来说，条件转移指令用2个时钟，所有其它指令花费一个时钟。在机器A上有20%的执行指令是条件转移指令，因此每个转移都需要比较，有20%是比较指令。由于机器A在转移指令中没有比较功能，这样时钟频率比机器B快25%，问哪个机器快？解：忽略所有等待及系统时间，我们可以用CPU时间来比较机器的性能。 机器A： CPIA20%2 80%11.2 CPUtimeA指令数A1.2时钟周期A 1.2IA A机器B： 无比较指令，则指令数要比机器A少20%，只有机器A指令数的80%，即指令数B=80%指令数A。在机器A的指令中有20%指令是转移指令，它占机器B的指令数的百分比是20%80%=25%。因此机器B的CPIB25%275%11.25。同时A机器时钟比B机器快25%，故时钟周期B(1+25%)A1.25ACPUtimeB指令数BCPIB时钟周期B 0.80IA1.251.25A 1.25IAA 从计算中我们看出机器A虽然比机器B多执行了20%的指令，但由于它的时钟周期短，同时CPI也小，反而比机器B快l 某台计算机的指令集原来进行存储器访问的指令只有Load/Store，其它指令只能在寄存器之间操作。这种机器我们称为Load/Store型机器。现测得这台Load/Store计算机指令的使用频率和时钟数如表1-5所示。在ALU操作中，有25%的操作数是由Load指令取得。现在ALU操作中使其有一个操作数可以在存储器内，即register-memory指令，这条指令执行的时钟数是2。假设扩展指令集后使转移指令增加1个时钟数，但不影响时钟周期，问这样改变后计算机性能是否提高？ ll 对于例1-6的计算机，我们采用优化编译来改善其性能。编译可以减少50%的ALU指令，但它不能减少Load，Store和Branch指令，忽略系统因素，并假设时钟周期是20ns(50MHz频率)，请问优化编译后的MIPS和没有优化编译时的MIPS各为多少？MIPS的变化和执行时间的变化是否一致？ll 基准程序的一般设计原则n 具有代表性 n 不能对基准程序进行优化。n 复现性。n 可移植性。n 紧凑性。n 成本-效率要高l 性能报告相关参数的计算l 哈夫曼压缩的基本思想是：出现频率最大的事件用最少的位（或最短的时间）来表示（或处理），而频率较小的事件用较多的位（较长的时间）来表示（或处理），从而达到平均位数（或时间）缩短的目的l 操作码的信息源熵(entropy 系统包含的平均信息量)公式 H=pilog2pi式中pi为事件出现的频率lChapter 2l 计算机的三种机器结构n 堆栈u 优点：赋值表达式简单，指令长度较短，代码密度高；u 缺点：不能随机访问存储器，代码效率低。n 累加器u 优点：机器内部状态最少，指令长度最短（9bytes）；u 缺点：仅一个暂存器，和存储器的通信频繁。n 通用寄存器u 优点：最一般的指令模型，第一类，寄存器利用率最高，代码长度MAX15字节。第二类，和累加器形式相似，暂存器个数多；u 缺点：寄存器要显示说明，导致指令字较长。l 在ALU指令中不对内存进行操作的计算机称为载入-存储(Load-Store)或者寄存器-寄存器(register-register)机器。ALU指令中有一个内存操作数的指令称为寄存器-存储器(register- memory)指令。有多个内存操作数的指令称为存储器-存储器(memory-memory)指令。l 我们是在确定了计算机应有的功能后，并确定了哪些功能是由硬件来实现(直接提供指令)，哪些功能是由软件实现(由基本指令组合实现)后，再来进行指令集的设计。l 最常用的指令操作：存储器访问(memory references)、算术逻辑单元(ALU operation)操作和转移指令(branch)操作三类。l 控制操作、算术操作和数据传输三大类指令是最常用的，可以认为也是各种计算机必不可少的指令。l 假定反向条件转移指令90%是成功的，用表2-4平均数计算正向条件转移的成功率。ll 正向条件转移大部分是不成功的，它满足条件的概率较低l 在字单元地址内有两种字节排列次序：第一种为低位收尾(little endian)，其字节次序是低字节在最低位的排列；第二种为高位收尾(big endian)，其字节次序是高字节在最低位的排列l 假设访问的数据字节数是S，而访问的字节地址是A，那么A mod S =0，则称为地址A所访问的S字节是对齐的。l 只要是跨CPU字地址的寄存器总线访问一定要两个总线访问周期才能完成l 寄存器分配策略1. 假设计算机具有无穷多个寄存器，根据需要分配寄存器的变量个数，以出现时间先后为序建立一个寄存器变量图。图中每个变量用小圆圈表示，圈内标上变量名，每个变量称为一个节点。2. 用弧连接各相邻节点。连接的原则是可能同时出现的变量节点作为相邻节点，用弧连接起来。从变量角度来讲，线段连接的是时空上重叠出现的变量生存范围。此时称整个图为相干图。3. 编译程序给相干图着色。着色的颜色数应小于等于能分配给变量的寄存器数，着色的条件是相邻节点不可以用同样的颜色。这种限制使两个同时出现的变量不会争用同一个寄存器。没有线段相连的节点，可以是同一种颜色，即允许不重叠出现的变量使用同一个寄存器。着色后每一种颜色对应一个活动变量或一个寄存器。根据相干图分配物理寄存器。l RISC设计思想是：指令集设计时根据Amdahl定律选择使用概率高的指令构成指令集，这些大概率指令一般是简单指令，因此控制器可以设计的简单、高速，且占CPU集成电路芯片的面积少，空出较多的集成电路芯片面积用来增加寄存器数量。在编译的配合下减少访存次数，减少指令间的各种相关和竞争，尽可能得到最佳指令序列，从而提高计算机系统的整体性能。l 某应用程序，简单的基本指令占80%，而复杂指令占20%，在传统CISC计算机上运行，简单指令的CPI=4，复杂指令的CPI=8，而在RISC计算机上运行只有简单指令，其CPI=1，复杂指令用简单指令合成实现。假设平均每条复杂指令需14条基本指令组合，请比较个计算机系统运行该应用程序的性能。解：设CISC计算机的时钟周期为 TCISC，RISC计算机的时钟周期为TRISC，则： CISC计算机的平均 CPI=0.84+0.28=4.8RISC计算机的指令数增加为 IRISC=0.8ICISC+0.2ICISC14=3.6ICISC因 CPUtime=ICPIT故 CPUtime-CISC=ICISC 4.8TCISC=4.8ICISCTCISC CPUtime-RISC=IRISC1TRISC=3.6ICISCTRISC 若TCISC=TRISC ，则RISC计算机比CISC计算机性能提高33%。实际上，减少TRISC比减少TCISC要来的容易。Chapter 3画图题l 处理器可分为两部分n 数据通路n 控制器ll 一条指令的执行分为以下五个步骤：n 1. 取指令(instruction fetch) 。n 2. 指令译码/寄存器读出(instruction decode/register fetch)。n 3. 执行/有效地址计算(execution/effective address)。u a. 访存指令(access instruction)u b. ALU指令(ALU instruction )u c. 无条件转移/条件转移指令(jump instruction / branch)n 4. 存储器访问/完成转移(memory access/branch completion)u a. 访存指令(access instruction)u b. 转移指令(branch instruction)n 5. 写回(write-back）。llChapter 4计算题 简答题l 流水线（pipeline）是指在程序执行时多条指令重叠进行的操作的一种准并行处理实现技术l 流水线的特点：n 一条流水线由多个流水级组成；n 每个流水级有专门的功能部件对指令进行某种加工；n 各流水级所需时间是一样的（同时）；n 流水线工作阶段可分为建立、满载和排空三个阶段；n 单位时间内流出流水线的指令数即吞吐率。l 流水线设计最难的任务是确定每个流水级功能部件处理事件的时间l 每条指令平均执行时间=l 流水线深度是指流水线中总的流水级的数目。在这种条件下，流水线计算机的加速比(speedup)就等于流水级的深度。l 流水线只能减少每条指令的平均执行时间，一条指令的实际执行时间要经过所有流水级，其实际执行时间有可能比未流水时还要长l 流水线有多种分类方法n 按处理的级别分类u 操作部件级u 指令级u 处理器级n 按完成的功能分类u 单功能流水线u 多功能流水线n 按连接的方式分类u 静态流水线u 动态流水线静态流水线是指在同一个时间内，多功能结构只能按一种功能的连接方式工作，这对于大量数据进行相同处理来说，具有很好的效果。但是遇到不同功能交替处理时，流水线就失去了其优点，运算速度与顺序处理方式没有什么区别。 动态流水线是指在同一个时间内，可以有多种功能的连接方式同时工作。如图4-5中多个功能段，其中一些功能段正在实现乘法运算，同时其它功能段还可以进行浮点加减运算，这种方式的流水工作效率最高，但是控制也变得更复杂。n 按处理的数据类型分类u 标量流水线u 向量流水线n 从流水线结构上分类u 线性流水线u 非线性流水线l 假定RISC流水线计算机，时钟周期是10ns，ALU操作和条件转移要4个时钟周期，而存储器访问操作要5个时钟周期。这三种指令操作的使用概率相应是40%，20%和40%。假设由于时钟上升和建立，流水线机器周期要增加1ns的开销。忽略任何其它延时影响，问5级流水线机器可以获得的加速比是多少？解：非流水线计算机平均每条指令执行时间为： TimeupCPI10(40%+20%)4+40%5104.4=44ns 流水线计算机每条指令平均执行时间为： Timep(10+1)5/511ns 则流水线计算机的Speedup为：Speedup=44/11=4倍l 假定机器指令执行需要5个功能单元，这5个单元的操作所需时间分别是10，8，10，10，7ns。假定流水要增加1ns的开销。求出流水相对于单周期指令机器的加速比 解：非流水计算机执行所有指令都用单个时钟，它的每条指令平均时间直接是一个时钟周期。时钟周期等于每一步的执行时间之和，即 timeup=10+8+10+10+7=45ns 在流水线机器上的时钟周期必须是流水线中执行时间最长的流水部件的执行时间，再加上1ns的开销，总共是 timep=10+1=11ns Speedup=45/11=4.1(倍) 一般认为，流水线改善了CPI，也可以把它看作是提高了时钟频率。l 流水线竞争有三种n 结构竞争（structure hazard）(资源竞争)：由资源缺乏引起n 数据竞争（data hazard）：由指令间数据相关而引起n 控制竞争（control hazard）：由程序指针PC值的改变而引起l 计算存储器结构竞争的代价。假定程序中存储器数据访问有40%。计算机流水线忽略结构冲突的理想CPI等于1。又假设有结构竞争的计算机时钟频率是没有结构竞争时的1.05倍。不考虑其它性能损失。流水线有结构竞争和无结构竞争哪一个执行速度快？快多少？解： 有许多方法可以解这个问题，最简单的方法是计算平均指令的运行时间 TaverICPI 两机器和时钟关系 f有结构竞争1.05f理想 有结构竞争理想/1.05无结构竞争，即没有插入Stall，由于理想CPI1，故平均指令执行时间 Ta无结构竞争ICPI理想I理想有结构竞争平均指令执行时间为 Ta有结构竞争ICPI(1+0.41)I理想/1.051.3I理想很明显，无结构竞争的计算机运行速度要快，且要快1.3倍。l 允许结构竞争存在n 减少成本n 降低单元电路的延时时间n 减少电路的复杂程度l 现代许多RISC计算机，浮点操作都没有采用完全流水方式。假设在5级RISC流水处理器中，浮点乘法操作没用流水方式实现，有4个时钟的等待时间。已知浮点乘法指令使用频率为14%，且假设浮点乘法指令在程序中完全均匀分布，请分析结构竞争对性能影响的程度。分两种极端情况分析： 1. 浮点乘法操作均匀分布，这是最佳情况，此时每7条指令有一个浮点乘法操作，大于5，故所有浮点乘法都可以和其它指令重叠执行，这种情况始终没有关于浮点乘法器的结构竞争，也不需插入Stall，性能没有损失。 2. 浮点乘法操作成串出现，且中间没有其它指令间隔，这是最差的情况。这时局部相当于每条指令都是浮点乘法操作(即100%)，结构竞争最严重。在这种情况下，14%的浮点乘法都要延时4个时钟才能进入浮点乘法执行部件。假定理想CPI1，此时的CPI为 CPI1414%1.6l 旁路技术l 插入Stalll 假定30%的指令是Load指令，其中一半情况是紧跟Load后面的指令依赖Load指令的结果。如果出现数据竞争要停顿一个流水节拍。那么相对于理想流水线机器（CPI=1），实际流水线性能损失多少？忽略其它流水停顿。解： 当有数据竞争时，Load后面的指令其CPI=2，这种情况Load指令的一半，即15%，而其余指令的CPI值仍为1，没有变化，故实际机器的CPI为 CPI(100%15%)115%21.15由于指令总数和时钟周期均未变化，故实际机器性能损失 (1.151)115%即与理想机器相比性能损失了15%。l 静态调度（避免插入Stall的性能损失）l 假定由Load指令引起的数据竞争有一个流水节拍的停顿，采用指令调度方法生成代码，避免下列语句序列出现流水等待 abc defl 指令从ID级流入EX级，一般称指令发射(instruction issue)。一条指令已建立了这一过程，称为已发射(issued)l 把碰到转移指令到转移行为明确之间的时间间隔称为转移的延时时间，后继指令组成的转移延时时间称为转移延时槽l 对延时槽的处理有三种编译调度方法n 取自转移指令前。这是最佳选择。n 取自目标指令。一般用于转移成功概率高的地方，如循环语句。n 取自转移指令后。一般用于转移成功概率较低的地方。l 功