计算机系统结构复习纲要

1、1.1引言计算机系统的发展简史13世纪：算盘(abacus )17世纪：帕斯卡(Pascal)加法机，莱布尼兹(Gottfried Leibniz) 乘法器19世纪：Jacquard织布机，巴贝奇20世纪：图灵，冯诺依曼，ENIAC :阿塔纳索夫，莫克利，埃克特EDVAC：冯诺依曼IBM : 1964 年 IBM/360，1970 年 IBM/370，傲视群雄， 独步天下！是谁在推动计算机系统的飞速发展硬件，计算机系统结构1.2计算机系统结构的概念计算机系统的层次结构计算机系统结构的定义经典定义：程序员所看到的计算机属性，即概念性结构与功 能特性广义定义：指令集结构，计算机组成，计算机实现通俗

2、定义：计算机系统中软、硬件界面的确定计算机组成和计算机实现计算机系统结构的分类冯氏分类，Flynn分类1.3定量分析技术计算机系统设计的定量原理大概率事件优先原则Amdahl定律：加速比(speedup)，改进的比例，改进的倍 数CPU 性能公式：CPU time=IC x CPI x Clock cycle time程序局部性原理计算机系统的性能评测执行时间和吞吐率基准测试程序(benchmark)性能比较1.4 计算机系统结构的发展冯诺依曼结构冯诺依曼结构的特点：二进制，运算器核心，存储程序， 顺序执行对冯诺依曼结构的改进：I/O，并行技术，存储器结构， 指令集发展软件对系统结构的影响系列

3、机(兼容)，模拟和仿真，统一高级语言硬件对系统结构的影响应用对系统结构的影响个人移动设备，桌面系统，服务器，集群，嵌入式系统结构的生命周期1.5计算机系统结构中并行性的发展并行性的概念提高并行性的技术途径单机系统中并行性的发展多机系统中并行性的发展指令集结构的分类三种基本结构(A、B、C均为内存变量)寻址方式寻址方式概述-字节编址-访问位数：字节(8 ),半字(16),字(32)，双字(64)-字中字节的排列次序- 对准用哪些寻址方式-立即数，偏移和寄存器间接寻址占75%到97%偏移寻址方式-偏移字段大小-12 位 75%-16 位 99%立即数寻址方式指令集结构的功能设计对指令集的基本要求-

4、完整性、规整性、高效性、兼容性CISC指令集结构的功能设计-面向目标程序增强指令功能-面向高级语言的优化实现来改进指令集-面向操作系统的优化实现改进指令集RISC指令集结构的功能设计-指令条数少、定长指令格式、单周期、Load-Store型、流 水线控制指令-跳转指令，分支指令操作数的类型和大小数据类型为什么在计算机中要用数据类型？数据表示与数据结构如何指明一个操作数的类型编码在操作码中一一最普遍的用法用标识符标记一一只能在计算机博物馆找到 基本数据类型字符:ASCII 一一 1字节- 整数：二进制补码 8位,16位,32位-单精度浮点数：IEEE 75432位-双精度浮点数：IEEE754

5、-2.5 指令格式的设计 指令集编码的三种主要格式 一个变长指令格式的例子-一条VAX指令：64位add13 r1, 737(r2), (r3)指令含义：一条具有3个操作数的32位整数加法指令，操作码 占1个字节，r2中数加上737所指的内存单元中数与r1中数相加， 结果存放在r3中数所指的内存单元中-该指令长度为：1+(1)+(1+2)+(1)=6 字节-VAX指令的长度从1到53字节2.6 MIPS指令集结构典型的RISC指令集DLX指令集的一些细节-32个64位通用寄存器(R0,R1,.)，R0=0-32个64位浮点寄存器(F0,F1,.)数据类型：字节，半字，字，双字；32位和64位浮

6、点数寻址模式：立即数，偏移量寻址指令格式：寻址方式编码在指令操作码中Opcode rs1 rd immediateOpcode rs rt rd functionOpcodeOffset added to PC-I类指令，R类指令，J类指令MIPS典型指令举例3.1重叠执行和先行控制重叠执行- 顺序执行-一次重叠执行方式二次重叠执行方式先行控制-缓冲技术-预处理技术-先行依据-善后处理3.2流水线的基本概念流水线的概念将一个重复的时序过程分解成为若干个子过程，每一 个子过程都可以有效的在其专用功能段上与其它子过程同时执行流水深度流水瓶颈流水线分类-单功能与多功能-静态与动态-部件级、处理机级与

7、处理机间-线性与非线性-顺序与乱序3.3流水线性能分析加速比(Speedup，理想情况，k段n个任务)吞吐率(Throughput rate，理想情况，k段n个任务)效率(Efficiency，理想情况，k段n个任务)3.4典型的指令执行过程(教材3.5)取指令周期(IF )IR e MemPC, NPC 6 PC4 指令译码/读寄存器周期(ID )A 6 RegSIR 6.10，B 6 RegSIR11.15，Imm 6 (IR16)16#IR16.31)执行/计算有效地址周期(EX )ALUOutput 6 AImm orALUOutput 6 A func B/Immor ALUOutp

8、ut 6 NPCImm, Cond 6 (A op 0)访存/分支完成周期(MEM )LMD 6MemALUOutputorMemALUOutput 6 Bor if (Cond) PC 6 ALUOutputelse PC 6NPC写回周期(WB )RegsIR16.2 6 ALU OutputRegsIRH.15 6 ALU Outputor RegsIR11.15 6 LMD 几点分析分支(12%)和存储(5%)需要4个周期，其余(83%)需要 5个周期，因此CPI=4.83若将ALU( 47%)在MEM周期就完成，则CPI=4.31-速度提升了 4.83/4.31=1.12任何其它降低

9、CPI的企图都将增加时钟周期时间，是 否有效需要分析如果指令的实现在一个长周期中完成则可以省略临 时寄存器但设计者不愿意采用单周期方法：首先：不同的指令需要不同的时间其次：多周期可以共享功能单元3.5简单指令流水线相关(dependence)数据相关名字相关(反相关，输出相关)控制相关冲突(hazards)结构冲突数据冲突控制冲突相关与冲突的关系相关是程序的属性冲突是流水线的特性冲突是因为相关，相关不一定引起冲突 结构冲突资源冲突引起的冒险- 为什么设计者容忍结构冒险？降低成本，减少功能单元的延迟- 如果结构相关并不经常发生，则没必要增加大量 硬件代价 数据冲突指令流水后改变了读写操作数的程序

10、顺序-定向技术不能通过定向技术解决的情况-编译器调度解决数据冲突(流水线调度)控制冲突冻结(freeze)或排空(flush)尽早判断，尽早计算预测编译器调度3.6向量处理机向量处理方式向量处理机的结构提高向量处理机性能的方法设置多个功能部件采用链接技术采用循环开采技术采用多处理技术向量处理机的性能评价4.1指令级并行的概念指令级并行(ILP)程序中指令之间存在的潜在并行性。开发指令级并行的方法基于硬件的动态开发和基于软件的静态开发基本程序块保持程序顺序数据流和异常行为DADDUR2,R3,R4DADDUR1,R2,R3BEQZR2,L1BEQZR4,L1LWR1,0(R2)DSUBUR1,R

11、5,R6L1:L1:ORR7,R1,R84.2指令的动态调度动态调度的基本思想DIVD F4,F0,F2SUBD F10,F4,F6ADDD F12,F6,F14按序执行和乱序执行乱序执行的异常处理可能多个异常同时发生，异常发生的顺序可能乱序精确异常，非精确异常Tomasulo 算法1、基本思想记录和检测数据相关，通过重命名技术消除名字相关基本结构：保留站，公共数据总线，load和store缓冲器，浮点寄存器，执行部件指令执行步骤：流出，执行，写结果2、举例3、具体算法4.3动态分支预测技术分支历史表(Branch History Table， BHT)根据分支指令的历史执行情况预测其当前的执

12、行结果采用分支目标缓冲器(Branch Target Buffer,BTB)缓冲器中保存分支成功的指令及其目标地址，取指令时进入， 更快。基于硬件的前瞻执行(speculation)解决控制相关的问题。对分支指令的结果进行猜测，并假设这个猜测总是对的，然 后按这个猜测结果继续取、流出和执行后续的指令。但执行的结果 不写回寄存器或存储器，而是放到一个称为ROB(ReOrder BUffer) 的缓冲器中，等到相应的指令得到确认后，才将结果最后写入正确 位置。4.4 多指令流出技术基于静态调度的多流出技术 基于动态调度的多流出技术 超长指令字技术 多流出处理机的限制程序所固有的指令级并行性硬件实现

13、上的困难超标量和超长指令字处理机固有的技术限制 超流水线处理机SGI公司MIPS系列R4000简介4.5循环展开和指令调度5.1存储器的层次结构-存储器层次结构能显著改善计算机系统的性能程序的局部性原理存储器容量越小，其访问速度越快5.2 Cache基本知识Cache含义Cache工作基本原理块地址块内 偏移标志字段索引字段映像规则全相联；直接映射；组相联查找方法替换算法随机算法；LRU算法；FIFO算法；CLOCK算法； 写策略写直达；写回法；写分配；不按写分配；一致性Cache性能分析缺失率；存储器平均访问时间；程序执行时间存储器平均访问时间=命中时间+缺失率X缺失代 价5.3降低Cach

14、e失效率的方法失效分类强制缺失；容量缺失；冲突缺失增加Cache块大小提高相联度增加Cache的容量Victim Cache伪相联映像Cache硬件预取编译器控制的预取编译器优化数组合并，内外循环交换，循环融合，分块5.4减少Cache失效开销让读失效优先于写 写缓冲合并请求字处理技术非阻塞Cache技术采用两级Cache5.5减少命中时间容量小、结构简单的Cache-Cache命中时间中最耗时部分是按地址的索引字 段去读标志存储器简单（直接映射）而小到Cache当然可以减少命 中时间虚拟Cache在Cache中预留特殊比特位，用来预测下一次访 问Cache时可能的块Pentium 4Cach

15、e访问流水化Trace CacheCache优化技术总结既不简单也不常用且成本昂贵，昙花一现，Pentium45.6主存内存储器技术及性能优化DRAM: main memory地址线减半，刷新，快速页模式SRAM: cache与DRAM相比，容量小，速度快带宽比时延来得更实际一些 虚拟存储器最初内存储器共享技术进而提供保护机制还有重定位技术页式管理-Cache和虚拟存储器的典型参数指标 逻辑地址、虚拟地址、物理地址逻辑地址（LA）是程序空间的地址，等同于虚拟地址虚拟地址（VA）是虚拟存储器的地址物理地址（PA）是真正物理内存储器的地址如果没有内存储器管理单元（MMU），VA = PA如果有MM

16、U，VA经过地址转换成为PA在操作系统管理之下，用户无法使用PA。如C语言中指 针的值指的是虚拟地址。为便于地址转换，虚拟地址不一定从0开始关于内存储器层次结构的四个问题-一个页可以放到内存中的什么位置？为避免过高的缺失代价而选择较低的缺失率，全相联如何在内存中查找一个页？页表（虚拟页号索引，很大），反向页表当发生虚拟存储器缺失时应该替换哪个页？LRU算法，使用位（逻辑位集合，定期清除并记录）写操作时会发生什么？总是写回法快速地址转换技术页表太大，页表本身分页，访问数据需两次访存变换旁路缓冲器（TLB），也称快表（TB）相联存储器，常用页表项（虚拟页号，物理页号，其它 位）选择页大小大页（4M

17、）：页表小，传送效率高，TLB缺失少小页（4K）：节省存储空间，进程启动速度快I/O系统性能与CPU性能I/O性能没有引起足够的重视系统的响应时间比CPU处理时间更能反映系统的性能多进程技术只能提高吞吐率而不能减少响应时间I/O性能是系统的瓶颈I/O系统的可靠性、可用性和可信性可靠性从某点开始系统连续提供服务的能力。平均无故障时间MTTF平均修复时间MTTR可用性MTTF/（MTTF+MTTR）可信性服务的质量，即在多大程度上可以合理的认为服务是可 靠的有效构建（valid construction）在构建系统的过程中消除故障隐患纠错（error correction）在系统构建中采用容错的方

18、法6.3廉价磁盘冗余阵列RAID用多个磁盘的组合来代替一个大容量的磁盘并行性提高性能；冗余提高可靠性；热备份；热交换RAID0只是并行不提供冗余可靠性低。视频处理，超级计算RAID1镜像，成本高，设计简单RAID3位交叉奇偶校验，细粒度，高速RAID4RAID5RAID6RAID10 与 RAID016.4总线总线的设计总线的速率受限于长度、设备数目、信号强度等各种物理因素的限制I/O操作响应速度与吞吐量之间的冲突总线的主要特性总线宽度，传输块大小，总线主设备，分离事务（打包），定时方式总线标准和实例总线标准很重要：数据宽度，时钟频率，同步方式IDE，SCSI，PCI，IIC，RS-232，R

19、S-485，USB，1394，SPI与CPU的连接I/O交互方式查询，中断6.5通道处理机通道的作用和功能解放CPU，提高I/O接口利用率接收CPU的I/O指令，执行通道程序，发送中断请求通道的工作过程用户程序调用广义指令进入操作系统的管理程序管理程序根据广义指令生成通道程序，并启动通道通道执行通道程序，完成I/O工作通道程序结束后向CPU发中断请求通道的种类字节多路通道，选择通道，数组多路通道通道流量分析6.6 I/O与操作系统DMA和虚拟存储器DMA使用物理地址，OS要确保数据页面都在物理内存中DMA使用虚拟地址，需要地址转换寄存器组I/O和Cache数据一致性异步I/O允许进程发出I/O

20、请求后，进一步发出更多I/O请求，从而可 以有多个I/O请求在同时进行，有效的提高了性能。7.1互连网络的基本概念互连网络的功能和特征互连网络（interconnection network）是一种由开关原件按照一定的拓扑结构和控制方式构成的网络，用于实现计算机系统中结 点之间的相互连接。这些结点可以是处理器、存储模块或其他设备。互连函数不同特性的互连函数可用一组互连函数来描述。交换函数，均匀洗牌函数，蝶式函数，反位序函数，PM2I 函数互连网络的特性参数网络规模：网络中结点的个数结点度：与结点相连的边数，包括入度和出度距离：任意两个结点之间的连接边数网络直径：网络中任意两个结点之间距离的最大

21、值7.2 互连网络的结构静态互连网络结点之间有固定的连接通路，在运行中不能改变的网络线性阵列（linear array）环和带弦环（chordal ring）循环移数网络（barrel shifter）树形和星形（tree and star）胖树形（fat tree）网格形和环网形超立方体动态互连网络总线，多级互连网络，交叉开关网络8.1引言多处理器设计计算机系统结构的新时代主流技术：少量到中等数量处理器（432）组成的多 处理器设计大规模多处理器中（科学计算）互连网络的设计至关重 要Flynn 分类（1966）-MIMD :单处理器-SIMD：达到构建三维、实时虚拟环境理想性能的最好选 择-

22、MISD:没有商业先例-MIMD :多处理器系统，比较灵活，性价比高集群（Cluster）商业集群，客户集群，Linux，消息传递多处理器系统SMP （Symmetrical Multi-Processing，对称多处理器系统）集中式共享存储器系统（CSM ），均匀存储器访问（UMA）MPP （Massively Parallel Processing，大规模并行处理系统）分布式共享存储器系统（DSM ），非均匀存储器访问 （NUMA）集中式共享存储器多处理器的基本结构。多个处理器-Cache子系统共享一个物理存储器。所有处理器访问存储器的时间一致分布式共享存储器多处理器的基本结构。每个节点包

23、含处理器、存储器、输入输出系统和互连网络的接口。每个节点可能含有少量处理器，这 些处理器使用小总线或其他互连技术连接在一起。节点内采用的互连技术的可扩展性低于全局互连网络。8.3分布式共享存储器系统结构目录协议简介通信模型和存储器的结构模型MIMD的两种地址空间的组织方案对应不同的通信机制通过共享的地址空间进行通信（单寻址空间）（DSM）通过消息传递来进行通信（多寻址空间，很具有挑战性！）PVM 和 MPI通信带宽：理想情况下受限于处理器、存储器和互联网 络的带宽通信延迟：发送开销，跨越时间，传输时间，接收时间通信延迟的隐藏：如何更好的把通信和计算重叠起来 并行处理面临的挑战并行度低100个处

24、理器要获得80倍的加速比时程序中的并行度 要达到99.75%通信时延负载平衡、同步和通信时延依赖于应用程序特点计算/通信比率8.2对称式共享存储器系统结构对称式共享存储器系统中缓存数据缓存私有数据，程序的行为与单存储器系统相同缓存共享数据，引起Cache 一致性问题Cache 一致性问题两个处理器A和B对同一个存储器位置X进行读写操作。 假设最初两个Cache都不包含该变量而且X的值为1。假设是写直达Cache （写回Cache问题更多九当X的值被A改写后，A的Cache和存储器中的副本 都做了更新，但B的Cache则没有，此时如果B读取X，则会得到错误的值Cache 一致性的定义如果在一个存

25、储器系统中读取任何一个数据项的返回 结果总是最近写入的数值，那么就可以认为该存储器具有一致性。-一切操作基于时间顺序实施一致性的基本方案Cache 一致性协议（Cache-coherence protocols）:监听式， 目录式监听协议所有Cache控制器对总线进行监听，确定自己是否有 总线上的数据写无效协议写更新协议对称式共享存储器多处理器监听协议的局限性总线带宽小存储器带宽小对称式共享存储器多处理器的性能处理器个数-Cache大小块大小分布目录-目录中保存所有存储器块的状态数据块的状态共享：一个或多个处理器的Cache中拥有该数据块，并 且存储器中的数据也是最新的（与所有Cache中的值

26、一样）未缓存：没有任何一个处理器的Cache中含有该数据块 的副本修改：只有一个处理器在本地Cache中拥有该数据块的 副本并且对该块执行过写操作，因此存储器中的副本是无效的。这 个处理器称为该块的拥有者除了跟踪数据块的状态，还要跟踪哪些处理器拥有该数 据块的副本本地节点：产生请求的节点主节点：数据块和对应的目录所在的节点远程节点：拥有数据块副本的节点如果一个数据块还未被缓存，那么存储器的副本就是当前 值，所以可能对这个块产生的请求是：读缺失存储器向发出请求的处理器送回所要求的数据，而发送 请求的节点成为唯一的共享节点。块的状态设为共享。写缺失向发出请求的处理器送回数据并使它成为共享节点。数

27、据块设为独占状态，指明这是唯一有效的Cache副本。共享集中指 明所有者。当数据块处于共享状态时存储器中的值也是最新的，可能 的请求是：读缺失存储器向发出请求的处理器送回所要求的数据，然后将 发送请求的处理器放到共享集中。写缺失向发出请求的处理器送回数据。向共享集中所有处理器 发送无效信息，并且共享集中要保存发送请求的处理器标识。数据 块设为独占状态。数据块处于独占状态时，块的最新值保存在由共享者集（即所 有者）所指明的处理器的Cache中，因此有以下可能的目录请 求：读缺失：向所有者处理器发送数据消息，这将使所有者 Cache中该块的状态转为共享，并且由所有者向目录发送数据。在 目录中该数据被写入存储器并发送回发出请求的处理器上。发出请 求的处理器的身份会被添加到共享者集中，这时集合中仍然会有所 有者处理器的身份（因为此处理器中含有可读的副本）数据写回：由于此时所有者处理器将数据块改写，因此 必须