西安交大计算机系统与应用复习.docx

1、1. 程序访问的局部性原理 n 局部访问性u 程序总是趋向于重用最近使用过的指令和数据u 在程序的执行过程中，CPU访问内存中的指令和数据总是趋向于成簇或成块的。l 程序中包含大量的循环体和子程序，会对这组指令重复访问l 程序中包含大量的表数据和数组，涉及对同一数据块的重复访问n 经验法则u 90%的执行时间花在10%的代码上n 局部访问性包括：u 时间局部性：最近访问过的指令或数据不久的将来还可能被访问u 空间局部性：被访问子附近的子，重用的概率大n 这个原理是设计计算机存储系统的理论基础n 指令局部性强于数据局部性2. 优化处理经常性事件n 在进行计算机设计或者项目设计时，我们必须优化处理

2、经常性事件u 事件经常发生u 优化经常性事件可以提高整个系统性能u 优化处理非经常性事件没有意义n 怎么优化？u 并行处理，更快的算法u 用更快的组件n 提高多少性能？u Amdahl定律3. Amdahl定律n Amdahl定律u 通过使用某种更快速的执行方式而获得的性能改进u 受限于这种快速方式的使用时间在总执行时间中的比例u 它定义了由于使用特殊技术所获得的加速比的大小n 加速比u 一种比值u 采用改进措施后整个任务的性能/没有采用改进措施整个任务的性能u 未采用改进措施时整个任务的执行时间/采用改进措施后整个任务的执行时间n Amdahl定律算加速比改进后整个任务的执行时间：改进后整个

3、系统的加速比：n 加速比和Fe=0的关系u Fe=0, Sn=1，没有可改进的地方u Se=, Sn=1/(1-Fe)u 可获得的性能改善的极限值也受可改进部分所占的比例限制n 例子：假定想改进用于Web服务的处理器。新的处理器在计算Web服务应用时，比原来处理器的速度快10倍。假定原处理器用于计算的时间占总时间的40%，等待I/O的时间占60%，则改进后总的加速比是多少？u 收益递减规律：只改进计算的某一部分而获得的加速比的增量随改进的增加而逐渐减少。u 如果只能对任务的一部分进行改进，对整个任务加速不会超过1/（1-Fe）n 例子：假定浮点平方根（EPSQR）运算占图形测试程序执行时间的2

4、0%，一种建议是改进浮点平方根运算的硬件，使平方根运算的速度提高到10倍；另一种方法是加快图形处理器中所有浮点指令，使FP指令的执行速度提高到1.6倍。浮点指令占整个应用程序执行时间的一半。请比较这两种方案。4. 处理器的性能公式n CPU时间 = 程序的CPU周期数 * 时钟周期n CPU时间 = 程序的CPU周期数 / 时钟频率n CPU时间 = CPI * IC * 时钟周期n CPU时间 = CPI * IC / 时钟频率u CPI：每条指令的平均时钟周期数 IPC：每周期执行的指令数u IC：指令数u CPU性能依赖于三个要素：时钟周期或频率；每条指令所花的时钟周期数；指令条数。5.

5、 可靠性和可用性n 通常用平均无故障时间（MTTF）表示一种可靠性u MTTF：平均无故障时间u 故障率：1/MTTFl 每10亿运行小时发生的故障数l FIT：实时故障数n MTBF：平均故障间隔时间u MTBF=MTTF+MTTRu MTTR：平均修复时间n 集合的故障率为各模块的故障率之和n 可用性：服务完成状态相对于服务完成和服务中断间隔的一种度量u 模块可用性=MTTF/MTTF+MTTRn 例子：假定一个磁盘子系统的构成和各自的MTTF如下（1）10个磁盘，每个磁盘的MTTF为1000000小时（2）一个SCSI控制器，MTTF为500000小时（3）一个电源，MTTF为20000

6、0小时（4）一个风扇，MTTF为200000小时（5）一组SCSI线，MTTF为1000000小时；假定寿命是指数分布的，且故障是独立的。计算整个系统的MTTFn 解决故障问题的主要方法是采用冗余技术n 例子：假定再增加一个电源，组件的寿命指数分布，故障间不相关。如果电源故障的平均修复时间是24小时，计算冗余电源组的可靠性（小时）6. 芯片功耗n 动态功率：静态功率： 电池泄露功耗占总功耗的25%动态能量：u 降低时钟频率可以减少动态功率，但不能减少动态能耗n 芯片成本限制晶体管数量增加和体积减小1. Cache系统组成n Cache设计理论基础u 局部访问性u 90%的执行时间花在10%的代

7、码上u 将这10%代码装入Cache中n 低一级的Cache总是比高一级的Cache容量大一个量级，速度慢一个量级n 上一级的Cache里存放下一级Cache的部分内容n Cache和CPU之间传送单位是字，Cache和Cache、主存和Cache之间传送单位是块或行n 命中：字传给CPUn 未中：CPU从低一级Cache载入字，包含字的块装入所有高级Cache，可能会发生替换2. Cache系统的性能参数n 平均访问时间：或者：u H：M1（Cache）的命中率u T1：访问M1的时间u T2：访问M2（主存）的时间u 三级存储结构：n 访问效率：二级存储访问效率：n 提高存储系统的访问效率

8、途径：u 提高快速存储器的命中率u 两级存储器的速度不要差别太大n 未中率4C模型u 强制未中型：初始时Cache为空，不管Cache的容量多大，最开始的Cache访问一定不会命中，需要从主存装入块。u 容量未中型：由于Cache的容量不够大，不能装入一个程序执行所需要的全部块，所访问的块被淘汰回了主存，从而未实现命中。u 冲突未中型：在直接映射和组关联映射方式中，不同的主存块可以对应同一Cache行，新装入的主存块会将对应的Cache行淘汰，此时访问被淘汰的数据，就会出现不命中。u 数据一致未中型：多机系统中，当一个CPU更新自己的Cache数据项时，其他Cache中对应的数据项变为无效。此

9、时，对这个无效数据访问就会导致未中。u =命中时间+未中率*未中损失u 减少平均访问时间：l 降低未中率。增加行大小、增加Cache容量、提高关联度l 减少未中损失。使用多级Cache、让读的优先级高于写l 减少Cache命中时间。当判决Cache命中与否时，避免地址变换n 加速比l：Cache的访问周期，：主存的访问周期3. Cache系统设计的关键问题n Cache容量u 小Cache：低功耗，低命中率，快速u 大Cache：高功耗，高命中率，更大的CPU占有，慢u 没有最优值：L1 Cache 1KB，L2 Cache 8 MB，L3 Cache 36MBu 容量与命中率：n 行大小u

10、太小：访问的局部性弱，高替换率，低命中率u 太大：命中率逐渐降低l 新装入数据的使用概率，比被替换数据重用率低l 行中部分字和被请求的字距离太远u 8-64B比较合理n 映射机制u 组关联映射：主存和Cache分成等大小的块，把主存块与Cache行分成相同大小的组，主存中每组的块数和Cache中每组的行数一样。主存的组和Cache的组之间直接映射，组内的块与行之间全关联映射。u K路组关联：每组k行，m行=v组*kl 地址长度=（s+w）位l 主存的容量=2s+w字l 块大小=行大小=2w字l 主存的块数=2s块l Cache的组数=2d组l 组内的行数=k行l Cache的总行数，m=k*2

11、d行l Cache的容量=k*2d+w 行l 例题：在一个四路组关联的Cache系统中，主存的大小为4KB个块，Cache的大小为128行，块大小是16个字。请画出Cache的地址结构Cache的组数v=128/4=32，组号为5；块大小16个字，字号位w=4。主存容量=4k*16，地址长度为16。n 替换算法：u FIFO:先进先出u RAND:随机数发生器确定被替换的行u LFU:最不经常使用u LRU:最近最少使用u OPT:最优替换算法n 写策略u 写命中策略：l 写直达：同时写Cache和主存。一致性较好，写的代价比较大l 写回：只更新Cache，需要替换它时再写回主存。设置脏位=1

12、，替换前检查，为1写回，为0直接替换。写的代价小，一致性差u 未中的写策略l 写分配法：把地址所对应的主存块装入Cache，然后更新。l 写不分配法：直接更新主存里的数据，更新后数据不装入Cache。4. Cache基本优化方法n 增加行大小、容量和关联度，减少未中率；多级Cache减少未中损失；写缓存5. Cache应用： 1. SDRAM和DDR-DRAM：n 同步内存（SDRAM）与CPU交换数据同步于一个外部时钟信号，以CPU和系统总线时间的最大带宽传送数据，没有强制的等待状态。读写都是在时钟控制下。n DDR-DRAM是双倍数据速率的SDRAM，每个时钟周期发送两次数据，一次在上升沿

13、，一次在下降沿2. 高性能存储器n 多体交叉主存：多个存储体连接在一起，形成一个交叉的存储系统n 并行访问主存：u 单体多字主存：字加长，一个存储体内放n个字，一次读写n个字。u 双端口存储器：两组相互独立的写控制线路和两个端口，每一个端口都有自己的片选控制信号和输出使能控制信号，允许两个独立的CPU或控制器同时异步地访问存储单元。n 关联存储器：把存储单元里内容的一部分作为关键字，来检验存储器，并将与关键字匹配的存储单元的内容读出或写入。3. 硬盘读写规则：n 读：磁头静止，磁盘旋转。n 写：电流脉冲送给写磁头，会产生不同方向的磁场，磁化磁盘的小区域，从而录0或1. T：平局访问时间，：平均

14、寻道时间，r：转速，b：要传送的字节，N：每个磁道的字节数4. RAID和平行存储器n RAID：独立磁盘冗余阵列，提高存储系统可靠性和性能的一种新技术。三个特征：物理上一组磁盘，在操作系统的管理下逻辑上成为一个磁盘 数据条带化、轮转分布到阵列的所有磁盘上 冗余的磁盘容量用来存放校验信息，在磁盘故障时用以恢复数据u RAID0：没有冗余。条带化的数据按照阵列方式轮转分布到所有盘上，强调的是容量和吞吐率，不强调可靠性。u RAID1：两套RAID0组成，其中一套作为镜像，有两份相同的数据。采用数据条带，每个逻辑条带映射到两个独立的物理硬盘上。l 特点：一个读请求可以由两个盘中的任意一个响应； 写

15、请求要求两个相应的条带同时更新，没有写损失； 故障恢复简单。当一个盘故障，可以从另一个盘访问数据。l 性能是RAID0的两倍，成本高。u RAID5：数据条带形式是数据块，将校验块轮转式、平均分不到所有盘上。当要写一个数据块时，阵列控制器需要计算校验块放到哪个盘上。较低开销，适合全盘数据的读写。较高性价比。u RAID7：高I/O请求率和高数据传输率的最优异步阵列。结构中包含了阵列管理计算机和阵列操作系统，具有数据缓冲Cache，可完全独立于主机运行，不占用主机CPU资源。它的存储计算机的OS是一套实时事件驱动的操作系统，用来进行系统初始化、调度数据传输，并把它们转换到相应的物理存储驱动器上。

16、自身设定和控制读写速度，操作系统可使主机I/O传送性能达到最佳。故障可自行恢复。非同步访问。成本高。n 组合式RAID：由两个独立地RAID1组合形成的RAID0。数据被有序的写入两个RAID中。左边两个磁盘组成RAID1，右边组成另外一个RAID1。这两个组成新的RAID0。适用于高性能、高容错但对容量要求不大的应用。n SAN:通过专用高速网将一个或多个网络存储设备和服务器连接起来的专用存储网络。n NAS:连接到网络上的带有文件管理和通信功能的磁盘阵列，拥有自己的CPU和存储管理系统，独立于应用服务器。n 对象存储文件系统：将SAN和NAS结合，支持阵列的直接访问。将文件的数据和一组属性

17、组合成对象，对象是数据存储的基本单位。5. CD和DVDn 读写规则：通过其表面为坑记录数据。反射光强弱，陆地，微坑集成光盘设备：光盘塔：叠加；光盘库：自动换盘；光盘阵列：数据分布到多个光盘中。1. 虚拟内存的组成：主存和硬盘通过I/O系统和OS进行组织。n 优点：u 提供一个透明或半透明的大容量主存，一个很大的用户进程，即使超过了实存的容量也能够执行；u 增加了用户并发执行的进程数量；u 提高了物理主存的使用效率；u 简化了用户的内存管理；u 保护每个进程空间，避免与其他进程冲突2. 加快访问虚拟内存n TLB：使用专门的Cache来存放页表，这个专用的Cache通常叫做转换后备缓冲器。n

18、关联目录表：压缩装入位为1的页表，为关联目录表，放到专用Cache里，采用全关联映射机制。n 哈希函数：把虚拟地址中的长页号变短，跟页表中的哈希值比较，以加快页表的查询速度。3. 帧分配算法：n PFF：页故障频率分配算法。一种动态分配算法，其基本实现是根据各个进程实际运行中的页故障频率，动态为其分配空闲帧数。4. 降低页面故障率的方法：n 尽力保持程序的局部性，尽力减少转移；n 页不要太大或太小；n 增加主存容量；页调度方式：按需装页，按照一定策略提前装入一定页数 ，限制装入的进程数。l 流水线的原理和特点n 原理：简单说：指令流水线就是不同的指令能够交叠执行的技术。一条指令的处理分解为6个

19、流水段：取指令、指令译码、计算操作数的地址、取操作数、执行指令、写操作数。每个流水段所需时间为时间拍，每个时间拍进入流水线一条指令，第一个执行完后，每个时间拍流出一个结果。n 特点：u 把一条指令分解为若干个关联的子操作，每个在操作由一个专门的功能部件来执行u 每一个功能部件后面需要一个有缓存寄存器构成的锁存器，用于保存流水段的执行结果u 每个流水段的时间开销（也叫流水段的长度）要大致相等，使得流线的利用率尽量高u 流水线要求要执行的指令是连续的、可流水执行的指令，指令间的冲突要尽量减少。u 流水线有装入时间和清空时间。完全充满的流水线效率最高。l 流水线的性能分析n 加速比：u 理想情况下：

20、 ：流水执行时间，：流水周期，k：流水线段数 ：非流水执行时间，n条指令u 不均衡时：理想和实际差异原因：锁存延时总开销变大，增加单条指令执行总时间； 出现依赖关系，转移的概率很大，流水线性能急剧下降；逻辑门控制会变得相当复杂，增加指令的执行时间。n 吞吐率：提高流水线吞吐率：降低流水段的时间开销。一方面适当增加流水段数。另一方面要均衡每一个流水段的长度。n 效率：实际加速比和最大加速比之间的比值。效率和吞吐率成正比，和加速比也成正比。，l 流水线瓶颈解决办法：消除流水线瓶颈的方法：串行细分，讲瓶颈流水段再细分为多个串行连接的子功能端，使得每个子功能段的时间开销跟其他功能段的时间一样；并行复制

21、，并行设置多套瓶颈功能段，轮转方式分配任务，使得多套部件并发工作，使任务的执行时间跟其他流水段一样。l 流水线冲突与对策n 结构冲突与对策：也叫资源冲突，是指流水线中两条或两条以上的指令同时使用相同的资源。冲突的结果就是指令必须串行来使用流水线的部分资源。u 对策：气泡技术，竞争资源的部分指令暂停流水或后推一个时间拍，等待资源可用。n 数据冲突与对策：流水线中指令的交叠执行使得指令中操作数读写的顺序不同于串行之行时的顺序。u 对策：l 转发技术，直接将上一条指令的执行结果通过专门的路径传递给需要它的功能部件。l 互锁技术，为维持正确的执行模式，采用停滞或气泡方法消解数据冲突的一种硬件技术n 控

22、制冲突与对策：控制依赖或转移冲突。当条件转移指令发生了转移，其后续流入的一段指令是无效指令，需要对其清除。u 对策：l 多流技术：硬件上有多套流水线，遇到转移指令时再启动一条从转移目标开始处开始流水的流水线，两条流水线同时流水，等转移指令执行完，取消错误的一路。l 预取转移目标：当条件转移指令识别后，当转移目标欲取到一个缓存中，同时指令正常流水。l 循环缓存：一个小的Cache，由流水线的取指令段维护，容纳n条最近取来的指令。指令流水过程中，当发生条件转移，硬件首先检查转移目标是否在此Cache中；如果在，就从Cache中取下一条指令。l 转移预测：静态转移预测：预测转移不发生、预测转移发生和

23、根据操作吗预测；动态转移预测：转移发生/不发生切换和根据转移历史信息预测l 延迟转移：充分利用延迟槽，使转移指令之后进入流水线的指令都是有效指令。5. 动态调度和循环展开1. RISC系统：依靠编译技术，将一条HLL语句解释为一串简单的机器指令序列，指令集小且指令比较简单。n 特征：u 大量的通用寄存器或通过编译器技术优化寄存器的使用，优化了标量访问和子程序调用u 有限且简单的指令集，优化了简单指令的访问u 强调优化指令流水线，优化了转移指令的处理。1. 提高ILP的方法：ILP，平均指令级并行度，提高ILP减少CPI流水线技术、超标量技术、超长指令字（VLIW）技术、多核。2. 超标量的基本

24、特征：n 并行流水线技术，不相关的几条标量指令可以同时启动、并行执行。n CPU的特征：允许一个时拍流入多条普通的指令，这些指令完全并行执行。3. 性能分析：m条基准流水线组成的，所以其指令的并行度为（m，1）。理想情况下，k段的基流水线完成N条指令的时间为，为流水线前进一步的时间。同样，理想情况下这N条指令在并行度为（m，n）的超标量流水线处理器上执行完的时间为，在式中，k为前m条指令通过流水线所需要的时间；N-m表示剩余的指令；mn表示每个能完成的指令数。则超标量超流水线CPU的加速比S（m，n）为，当N，。超标量加速比：，；超流水线加速比：，4. 动态调度：按序发出，按序执行；按序发出，

25、乱序执行；乱序发出，乱序执行。5. VLIW和EPICn VLIW：超长的指令字。VLIW处理器发出固定数量的指令，或者是一条长指令，或者是固定的指令包，内含明确的指令并行信息。其指令调度采用基于编译器的静态调度策略。n EPIC技术：明确地并行指令计算。u 关键技术：在机器指令中明确指令级的并行，而不是等到处理器运行时才确定；u 长或超长的指令字；u 转移断定；u 推测执行；u 软件流水线。1. 多核架构：专用L1，专用L2，共享L2，共享L3Cache2. 互联机制：总线方式，交叉开关，环形方式，片内互联网络3. 数据一致性协议：MOESI，MOSI，M：修改状态，O：拥有状态，E：专有状

26、态，S：共享状态，I：无效状态4. ATR：自适应守时替换算法5. 并行程序设计的理论基础：Amdahl定律，n核，串行占S比例，定义线程开销为，考虑开销，加速比。n 结论：u 对于一个应用程序而言，加速比的增加随计算核数的增加而逐渐减小，所以不能依靠无限增加计算核数来有效提高加速比。u 加速比主要取决于应用程序的串行部分，尽可能减少串行部分、增加并行部分能有效地提高应用的加速比Gustafson定律：Amdahl隐含约束条件：一个具体应用或问题的大小在执行过程中是固定的。6. 并行程序设计模式：n 并发性发现：识别和分析问题中可开发的并发性，展现并发性的任务。n 算法结构设计：讲任务映射为线

27、程或进程，设计并行结构。n 结构支撑：程序结构和共享数据的结构表示。SPMD,所有的线程或进程并行执行相同的程序（单程序），但各自使用自己的数据集（多数据）n 实现机制：进程或线程在具体编程环境里的实现。1. MIMD：多指令，多数据流。分类：共享内存架构：SMP，多处理器计算机；NUMA，非均匀内存访问系统：所有的处理器使用load/store指令可以访问主存的任一位置，但处理器访问主存的时间会因访问区域不同而不同。分布式内存架构：机群2. Cache的一致性协议：MESI：M，修改状态：改行数据刚被修改过，主存和其他Cache中均没有这个数据，只有Cache中有；专有状态：改行数据只在本C

28、ache和主存中，其他Cache中没有这个数据；共享状态：该行数据在本Cache和主存中，其他Cache中至少有一个拥有这个数据；无效状态：该数据在本Cache中是无效数据，其他Cache修改过这个数据。3. SMP互联网络关键技术：拓扑结构、寻径算法、交换与通信策略和流量控制4. 机群是由多个完整的计算机通过高速网络连接起来的、特殊操作系统管理、可并行工作的一台计算机。是由同构或异构的独立计算机、高速网络和机群操作系统组成的，是松散耦合的结构，不同的节点间不共享内存，属于完全的分布式系统。5. 机群特点：绝对的可扩展性；可逐步扩容；高可用性；较高的性价比；构建机群的代价小（可以采用普遍的服务

29、器、PC和现有的告诉以太网构建，可以充分利用现有的硬件资源和开源的机群OS,节省时间和成本）；投资风险小。6. 应用配置：面向高性能计算的配置结构和面向服务器的配置结构（被动式备份，主从式配置（独立服务器，不共享磁盘阵列，共享阵列）1 云的概念和云计算：云是一种比喻，不是指具体的技术或框架，而是泛指不同领域里的基础设施，是一个组合的技术集合。云计算是一种模式，在这种模式中，能够跟方便的通过网络按需访问共享的、可配置的计算资源池（网络、服务器、存储设备、应用和各种服务），用户能够很容易地使用或释放资源，甚至不需要跟服务商交互。2 云计算5个基本特征：按需自服务普遍的网络访问资源池技术快速弹性可测

30、量的服务3. 云计算的服务模型：BPaaS：一些列按步骤发生的动作，在云平台上完成一个商业任务。SaaS: 应用即服务。给用户提供的服务是运行在云基础设施上的多种软件PaaS：为用户开发和部署应用程序提供一个平台，包括编程语言、调试工具和运行环境。IaaS：资源云，将可托管的资源作为服务提供给用户。4. 部署模型：私有云：内部云。每个企业各自拥有或租用的云基础设施，只对企业内部提供服务，具有很好的安全性和可控性。公共云：一般公众可以使用的云设施。社区云：几个关联的组织构成一个社区，将社区内每个组织的云设施聚集起来，构成一个大的、社区共享的云基础设施。混合云：由私有云、公共云以及社区云基础设施组成的云，一部分内部使用，另一部分对外服务，以便最大限度减少成本。