高体复习要点-xflove

1、局部性原理：器时，无论取指令或者存取数据，单元都趋向于在一个较小的连CPU续区域中。局部性原理包含时间局部性和空间局部性。时间局部性指如果一个信息项正在被，那么近期它还会再被。原因：程序循环和堆栈技术。空间局部性指在最近的将来用到的信息很可能在现在正在使用的信息在空间地址上放。原因：指令顺序执行和数组存微处理器分为通用高性能处理器、微处理器和微控制器三种。微处理器(DSP)指产品最终用户无法计算机体系结构：编程接口的可编程处理器。机器语言程序员要为该机器写一个正确的且与时序无关的程序需要了解的该机器结构。计算机性能评价标准：总执行时间：一致的综合度量标准，最简单的相对性能平均时间：可以清楚地知

2、道相对性能及权重值。权重不仅与该程序执行负载频度有关，而且与运行程序机器的特性以及程序输入数据的多少有关。归一化执行时间：将执行时间对一台参考机器归一化取平均值。SPEC 基准程序使用标准几何平均时间：与参考机器无关，可以减少输入不确定引起的误导，但无法执行时间。它机器运行时间。利用流水线技术使指令的执行可以来提高效率的方法称为指令级并行。若两条指令是可并行的，假定流水线资源充足，那么它们可以在流水线上同时执行而不会造成停顿，若两条指令是相关的，那么它们是不可并行的（尽管有时可以部分令之间是否存在相关性很重要。执行）。所以，判断指相关性是程序的特性，一个相关是否会导致实际的，该是否会造成停顿，

3、这是流水线结构的基本特征。指令共有三种不同类型的相关：数据相关、名字相关和控制相关。数据相关后面的指令的源操作数是前面指令的目的操作数，即后面指令需要用到前面指令产生的结果。如果指令中存在数据相关，反映产生该指令序列的程序源代码中也存在这种相关关系，这种源代码的相关性一般是不能破坏的。所以，如果两条指令之间存在数据相关，它们就不能同时执行或完全执行。说明它们存在数据的相关链，执行这些指令会使流水线互锁结构检测到并停顿。编译器不能调度相关指令是它们完全的执行，因为那样会使执行结果出错。硬件：在无法消除数据相关时，它会尽量避免相关所带来的停顿。：依赖于编译器的静态流水线调度法，则是尽量通过分离相关

4、的指令使它们不会导致，从而减少停顿的影响。1. 数据相关性的基本特征1）相关性预示存在的可能性；相关性决定必须遵循的计算顺序；数据相关性决定可被利用的并行性的上限，决定了指令级的并行性在多大程度上能够得到利用。2.克服数据相关性的工作保持相关性避免突常用的基本方法。、通过变换代码消除相关性。对代码调度是保持相关关系并避免冲1高体复习要点 (1) 指令级并行技术基础高体复习要点 (0) 体系结构中的基础性概念3.如何检测相关性？数据在指令中的既可能通过寄存器也可能通过内存。当数据流发生在寄存器中时，由于指令中的寄存器名均是固定的，因而相关关系可以简单明了的检测出来；而涉及到内存操作的数据流之间的

5、相关性时，则相对较难被检测出来，因而即使两个形式上完全不相同的地址，也有可能指向同一个内存地址单元（而有效地址在不同执行时刻，其地址也可能不同），这些都使得相关性检测工作进一步复杂化。名字相关当两条指令使用同一个寄存器或是同一个内存地址，但指令之间不存在数据流（即不交换数据）时，即存在名称相关。名称相关有两种：反相关、输出相关。反相关是先读后写相关，由于对指定位置进行写操作使读操作失效。输出相关是写写相关，对同一个单元同时进行写。与真正的数据相关不同，名称相关中指令间没有相互传递数值，因而有名称相关的指令是可以同时执行或进行重新排序的。对指令中寄存器进行重命名，就能使指令之间不再存在这种。寄存

6、器重命名可以由编译器静态实现，也可以由硬件动态完成。控制相关控制相关决定了跟分支指令有关的指令的执行顺序，即支指令只能在该执行的时候才执行。所以，它会带来两方面的限制控制相关与一个分支指令的指令不能被移到分支之前执行，没有控制相关与一个分支指令的指令不能移到分支指令之后去执行（本来不受控制，改变后会变得会受控制）。保证控制相关通过以下两个方面保证：一是指令按顺序执行，使分支转移指令之前指令先执行。二是对控制或分支前不会被执行。进行检测，保证控制相关分支指令在没有确定分支控制相关并不是必须保留下来的关键性。通过数据和控制相关所保证对程序正确执行起关键作用的特性：异常行为和数据流。保留异常行为指不

7、管怎样改变指令运行顺序都不能改变原先程序的异常情况。数据流指指令中确实存在的数据值在产生它的指令之间的形态。保证程序顺利执行需要控制相关。改变控制相关可以既不影响异常行为也不影响数据流。比如，若控制相关与分支指令的指令中用到的目标寄存器，在后面不会被用到，那么在分支指令之前就改变那个寄存器的值也不会影响到数据流状况。对于这种情况，就可以把控制相关的那个指令移到分支之前进行。若分支转移却是成功，则该指令执行；否则，将它换为空操作，也不会影响程序的结果。（这种情况，相当于可以用“猜测分支转移不成功”处理。）流水线相关与相关并不一定引起存在相关性，。a) 且相关指令的执行时间相近时，可能会在流水线中

8、操作b) 指令的重新排序改变了有相关的操作数的这时就会发生数据。数据相关可能引起 RAW顺序；反相关可能引起 WAR；输出相关可能引起 WAW。）：试图同时以两种不同的方式使用同一资源。1）资源（也称结构处理器进行流水处理时，指令的执行要求功能能流水，以便流水线中的指令能组合。因为资源而无法使用某种指令的组合，则称该机器是存在结构的。原因：硬件无法支持同时执行的所有指令组合2解决方法：所有的方法在发现结构后必须先暂停，等待结构消除2）数据：在产生数据之前就试图使用它们。流水线的一个主要影响时，通过执行指令来改变指令的相对执行时间。当流水线改变操作数的读写顺序，使得顺序与非流水线时的指令序列不相

9、同，这是就会出现数据。原因：流水线执行指令依赖与前面指令的结果解决方法：可以通过数据前递部分解决，还可通过硬件的检测避免3）控制：流水线中的分支指令或其他改写 PC 的指令造成的。在判断转移条件之前，就试图决策转移的方向。原因：可能改变 PC 指令的流水解决方法：通过转移、延迟转移等解决控制并在硬件支持下防止出现数据和转移失败后的状态回复。转移处理的四种策略暂停直到判别转移方向转移不发生串行执行后续指令如果实际指令发生，碾压执行指令利用流水线晚期才改变流水线状态优势47%转移指令不发生3）转移发生53%转移指令发生，但由于没有计算转移目标地址，会导致一个周期的转移损失。其他机器也可能在结果产生

10、之前提前知道转移目标。4） 延迟转移重定义转移行为在后续指令之后发生。通过一个漕的延迟即可作出正确决定并计算转移目标地址。1) 基本原理记分板是在资源充足，没有数据相关存在的条件下，允许指令乱序执行的一种技术。它通过使用硬件来支持指令级并行，从而能够处理某些在编译阶段无法知道的相关关系（如涉及内存时），简化编译处理过程的设计，同时实现代码的可移植性。记分板的目的是，在没有资源 的前提下，使每条指令尽可能早的执行，以保持每一个时钟周期执行一条指令的速率。即，当某条指令将要执行的指令被暂停时，其他没有相关于任何正在执行或被暂停指令的指令，应该可以提到前面来发射并执行。（条件满足，立即执行，无需等待

11、前面指令完成。）它的思路是：利用寄存器换名策略（1）允许暂停指令之后的指令被执行，实现按序发射、乱序执行、乱序完成。（2）对于乱序完成而产生的 WAR、WAW，采用以下方法解决：对于 WAR，要求排队等待操作以及操作数拷贝，并只在读操作阶段才暂停并等待其它指令完成。寄存器。对于 WAW，则检测，（3）把 ID 阶段分成 Ie 和 Read Operands 两段，这里将检测所有结构，等待不存在数据的情况，从而支持在保证按序发射的情况下乱序执行。3高体复习要点 (2) 记分板系统结构 (流水的集中式动态调度)2) 设计结构上图给出了记分板的基本系统结构，记分板的功能是控制指令的执行，所有数据通过

12、总线为这一组功能提供服务。不仅负责实现指令发射和执行的，也负责所有的检测。（1）每条指令都要从记分板了 ID 阶段的发射部分。通过，并在这里建立相应的数据相关结构，这一步代替（2）由记分板决定何时可以读操作数、执行指令，如果判断还不能立即执行，则会监视硬件上的每一个变化并决定该指令何时才能执行。（3）记分板可以控制指令写入目标寄存器。这样，所有的记分板由三部分检测及解除工作都集中在记分板：上。1）、指令状态。说明指令处于 4 个阶段中的哪个阶段（i write back）。e、read operands、execution、2）、功能状态。指明功能的状态，每一个功能包括 9 个域。Busy 指

13、明功能是否正被使用；Op 指明功能正在进行的操作；Fi 指明目的寄存器；Fj、Fk 指明源操作数所在的寄存器；当源操作数不直接从寄存器取到，而要等待前面执行的指令的功能产生时，使用 Qj、Qk 分别指明 Fj、Fk 将由哪个功能产生；Rj、Rk 指明源操作数（即 Fj、Fk）现在是否可用，若这两个域指示为不可用时，说明需要等待别的功能（即Qj、Qk）产生。3）、寄存器结果状态。指明哪个功能为空白。3) 具体实现步骤将写入该寄存器。如果没有指令将写入该寄存器，则该寄存器的状态记分板用四个阶段代替 ID、EX、WB 三个阶段。4 个阶段分别如下：1）、发射阶段。该阶段完成指令译码，并检测结构。该阶

14、段按程序的次序发射指令。当需要发射的那条指令要用到的功能空闲（没有结构），而且待发射指令与已发射但尚未完成的指令之间没有输出相关没有其他活动指令和该指令争用同一个目的寄存器时（没有 WAW），记分板就直接把指令发射到功能并更新自己的数据结构。否则（如果存在结构或写写）暂停发射任何后继指令，直至解决。（通过确保无其他活动的功能与其争用同一目标寄存器，可以杜绝 WAW。）2）、读操作数（readoperands）。等待更早发射但未完成的指令写回其结果，所以在该阶段可解决所有真数据相关。4记分板监视源操作数的可用情况，如果没有更早发射的指令要写源操作数所在寄存器（没有 RAW），或者存放源操作数的寄

15、存器此刻正在被某个活动的功能写入，那么源操作数是可用的。此时功能可以操作数。否则，暂停在该阶段直到满足条件。通过这种方法，记分板解决了写读，指令从而可以乱序地进入执行阶段。3）、执行（Execution）。功能后，通知记分板已经完成执行。在得到操作数之后即开始执行，执行结束，结果产生4）、写结果（write back）。当不存在 WAR时，功能写回结果到寄存器。其操作数（前面要读得还没判断的方法是：如果在该执行完的指令之前的指令尚未读），且其中一个操作数使用的寄存器正好与等待写回结果的寄存器相同（先写得还没先），则判断为此时存在 WAR。一旦 WAR果。被解决后，记分板就通知功能让其写回运算结

16、以下为记分板系统流水线控制的细节，在观察实例图时要非常认真。4) 局限性分析减少流水线暂停受到以下的限制指令中可并行的数量取决于有多少独立指令可以被发掘来并行执行记分板数量影响流水线可以提前查找独立不相关指令能力功能的种类和数量影响资源的可能性反相关和输出相关导致读写和写写的可能记分板技术的一些缺点：、没有用来流水线的前递硬件，只用寄存器传值；、指令调度局限于基本块内，指令窗口小；而实际上程序中常常存在很多 branch，使得基本块很小。3）、功能少，容易引起结构，特别是用得多的eger/load store；存在结构，就暂停发射指令，按序发射耽误了时间；4）、由于寄存器不够多，存在 WAR、

17、WAW。需要等待，防止出现 WAW，直到 WAR解决记分板的方法总的特点是集中控制，复杂度高。高体复习要点 (3) 基于 Tomasulo 算法系统结构(流水的分布式动态调度)Tomasulo 算法保证指令在存在的情况下仍继续执行，它可以操作数就绪时间，减少写写命名避免和写读，使得指令的操作数已准备好就允许指令执行，同时通过寄存器重。（当指令所需要操作数就绪之后可以执行指令这样可以避免写读，通过寄存器命名实现避免由名字相关引起的读写和写写。寄存器重命名指对相关目标寄存器重新命名，使得乱序执行的写操作不会影响需要写入以前值指令的正确执行）51） 技术特点通过保留站实现寄存器重命名技术、源操作数缓

18、存技术，保留站中缓存了即将发射指令所需要的操作数，其基本是尽可能早的取得并缓存一个操作数，从而避免需要读操作数时才去寄存器中的情况。即将执行的指令也会有保留站取得所需要的操作数。当多个操作同时作用寄存器，只允许最后一个写操作更新寄存器。指令发射以后，它所需要的操作数对应的寄存器将换为保留站的名字。通过使用比寄存器多得多的保留站技术，可以消除原先编译器无法消除的。(寄存器数目少可能成为编译的瓶颈)使用保留站技术与集中是寄存器文件1）检测和执行控制是分布式的，每一个功能的保留站控制该中指令的执行时间。2）结果可以从保留站缓冲区直接送到功能，而不通过寄存器传送，使用公共数据总线使所有功能可以同时取得

19、该数据。2） 基本的基本组成1. 保留站 担当了控制角色，它的组成包括以下几个字段：busy指明保留站或者功能是否处于忙状态；指明功能将完成的具体操作；OpVj、Vk 指明源操作数的实际数值，缓冲器中设有 V 域，存放将的结果；Qj、Qk 分别指明将产生源寄存器值的保留站，保留站中不包含就序与否的状态指示，Qj、Qk 为 0 表示就绪，对于缓冲器，只有存放 RS 产生结果的Qi；载入和保存时计算内存地址的信息A（不用记分板中的就绪标志，因为一旦产生结果，通过公共数据总线广播了）2. 寄存器 对应一个字段：寄存器结果状态（Register result sus），指明哪个功能如果没有将写入该寄存

20、器的未决指令，则该域为空白。3. 读数和写数缓冲器包含字段：A 用于在第一步结束后保存有效地址的结果。3） 基本工作原理将写入哪个寄存器（Qi）。1 发射阶段从浮点运算队列中取指令，按 FIFO 的方式保留在队列中，以保持数据流正确性。若指令操作数已经准备好，保留站中有空位置（无结构），控制机制发射指令并发送操作数（对寄存器进行换名）到保留站中。若没有空余的保留站，说明发生了资源，指令等待保留。在发射阶段还站出现空闲；若指令操作数还不在寄存器里，则产生操作数的功能6进行寄存器重命名工作，消除读写2 执行阶段和写写。如果两个操作数都已就绪，就执行，如果没有就绪，就监测 CDB，等待所需结果。由于

21、这里的指令需要等待操作数就绪后才能执行，所以不会产生 RAW。虽然不同功能可以同时开始执行几条指令，但同一时钟周期内一个功能只能执行一条指令，所以需要3 写回结果通过公共数据总线将结果写入到所有等待的，标记保留站可用。所有的写操作，不管是写寄存器还是写器，都将在这个阶段中完成。当地址和数据值都有效时，缓冲器会向内存写回数据，并结束缓存。检测并消除的数据结构附在保留站、寄存器堆、读数缓冲器和写数缓冲器。除了读数缓冲器外，其他都会带有一个标志字段，作为重命名使用的虚拟寄存器的名称。它可以指明产生源操作数指令所在的保留站。指令发射并等待操作数时，标志字段会指向产生该操作数的保留站号，而不是指向目标寄

22、存器。保留站可作为扩展的模拟寄存器使用。4） 评价算法Tomasulo 算法的主要优点在于：1）分布式保留站的结构和 CDB 技术的使用如果多条指令等待一个结果，且每个结果已经读到另一操作数，那么公共数据总线可以利用广播机制使得所有指令能够同时得到这个操作数并同时执行。而集中式寄存器必须通过寄存器总线去所需要的寄存器取值。2） 保留站作用于虚拟扩展寄存器保留站技术可以通过寄存器重命名技术使操作数尽可能早地存入保留站，从而消除写写相关和读写相关。其主要缺点如下所示：一、实现较复杂，需要大量硬件去实现，每个保留站都需要相关联的有复杂控制逻辑的高速缓存；二、公共数据总线将成为制约性能增长的瓶颈，每个

23、 CDB 必须广播到多个功能单元意味着大容量、写操作密集，同时每个周期可以完成功能线的限制。数量可能受到单一总Tomasulo 算法运用了寄存器重命名技术和源操作数缓存技术。源操作数缓存技术解决了读写，使操作数一旦在寄存器中有效即可使用。防止寄存器数目成为系统结构性能的瓶颈，同时防止记分板的读写相关和写写相关，具有硬件动态完成循环展开的功能。此外它对降低 Caches 失效和系统开销有利，其动态调度、寄存器换名深深影响了后续机型的发展。它对代码调度存在和缺乏寄存器的系统结构比较有效。1）概念精确中断：精确中断指的是对于单条指令，所有该指令之前的指令都已提交其状态，且所有后续指令（包括产生中断的

24、指令）没有改变任何机器状态。需要一定措施将指令执行的次序与指令发射流进行再同步。7进行选择。针对写读和读写需要执行两个步骤：在基址寄存器计算有效地址，然后再将数据读入读数缓冲器或从写数缓冲器写入内存。通过有效地址计算，读写和写数都得以保留原程高体复习要点 (4) Tomasulo 算法系统结构对猜测式、精确中断的支持和影响序的执行顺序，从而避免了内存的。推测式：是猜测的一种，包括分支和数据，当正确时，对于程序的正常执行没有影响，当推测错误时，也要求在推测错误的转移指令之后执行的指令没有改变任何机器状态，或者可以从改变的机器状态中恢复。为了解决精确中断与推测式，都是需要指令按序提交，可以采用相同

25、的方法进行处理。2） 技术原理实现猜测法是允许指令乱序执行但按序提交，并在指令提交前避免任何无法恢复的行为发生。因而需要把指令执行完成的过程从指令提交过程中脱离，利用排序缓冲器来保存指令执行结束和提交指令之间的执行结果。Tomasulo 算法对于推测式和精确中断的支持是引入了重排序缓冲器（ROB）。允许指令乱序执行但必须按序提交，并且在指令提交前应该避免任何无法恢复的行为发生。重排序缓冲器在指令执行结束和指令提交之间保存指令的执行结果。（允许继续执行，允许产生的结果给别人用，但是，没到顶端不允许写。）重排序缓冲器的工作原理如下：1）按 FIFO 的次序存放指令，即按指令发射的次序存放指令。把存

26、放在寄存器或者排序缓冲器的操作数送至保留站并更新相应的控制令发射等待空闲位置。每个 ROB 的表项包括：来停用缓冲器。如果保留站已满，暂停指PC指令类型目标字段寄存器序号或内存地址结果状态保存指令执行结果，直至指令提交表明指令已经执行完毕，其结果已经准备好2）当指令完成时，将结果放在 ROB，向其它介于执行、完成和提交的指令提供操作数，并将结果用重排序缓冲器的来标记，相当于了保留站的一部分工作；3）指令提交，将重排序缓冲器顶部的数据放到寄存器中。通过引入重排序缓冲器，实现了按序发送、乱序完成和按序提交。因为重排序缓冲器中只有缓冲器顶部的指令在完成后可以提交，这样对于式中的转移指令以及精确中断中

27、的被中断指令，当他们到达缓冲器顶部时，它们前面的指令已经提交状态，而他们后面的指令还没有改变任何机器状态。保证了指令前面的指令全部写完后，它才能写 memory、register。这样的设计可以保持精确中断，只等待该指令到达排序缓冲器顶部才产生中断，同时保证了指令的顺序执行。所以当失败或者中断要求转向处理别的指令时，可以将重排序缓冲器中，跟在错误分支或中断指令之后的所有排序缓冲器清空，而不会影响程序的正确执行，实现了对于式和精确中断的支持。基于这样的技术仍然在内存中可能出现写读在 ST 指令完成之前不执行。3） 评价，主要解决方法是内存的 LD 指令排序缓冲器完全代替了读数缓冲器和写数缓冲器，

28、并实现原来有保留站实现的重命名功能；仍旧保存保留站，用来缓存介于指令发射阶段和指令执行阶段之间的操作及操作数；指令提交前，寄存器得不到更新，由排序缓冲器在指令执行完毕和提交之间提供操作数；的数据不是一旦准备好就更新内存，直到数据到达 ROB 头部时，才能够更新内存，从而保证指令在猜测性质方面有一定的优势。之前不被更新。ROB 技术使得系统结构对精确中断和分支等8器歧义指在指令执行中，两条指令会非显式的指向同一个器地址。相关，猜测 load 和 store 是否硬件支持方法和 1）、使用缓冲区相关，相当于在 load 和 store 指令之间隐式地加了一条分支指令。：所有的已经发生的对内存的操作

29、，并且要和程序次序一致。记录的内容包括有效地址和有效值，并且的次序和程序次序一致；2）、当发射 load 指令，当前缓冲区中顶部的 store 指令，这样可以明确哪些 store 指令在 load 指令之前；3）、当获得 load 所需的地址后，检查 store 队列：若前面 store 指令等待地址，则暂停 load；若 load 和 store 指令的地址匹配，说明存在RAW，通过查看重排序缓冲器ROB，若发现 store 指令的值可用了（指令已经执行完，产生了结果），则从那里取得值；否则，返回产生该值的 ROB。4）、因为 store 指令按序提交，所以内存中不会发生WAR、WAW。若上

30、述两种情况不存在，则可直接向内存发出请求。高体复习要点 (6) 显式寄存器更名的原理、优点和在计分板中的实现方法1） 基本原理提供的物理寄存器，多于指令系统结构中所使用的寄存器数目，任何一个指令若需要写某个寄存器，则给该指令分配一个新的物理寄存器。该方法类似于一种编译转换技术单赋值表示（SSA），但是这是硬件实现的方法，它避免了 WAR 和 WAW，拥有和Tomasulo 算法一样的允许指令可以乱序完成的好处，是基于硬件的动态调度算法。实现方法是一张转换表，指令中使用的寄存器与物理寄存器的关系。当一个指令写寄存器，更新物理寄存器空闲表状态；若一个物理寄存器没有任何指令向它写入数据，则把该物理寄

31、存器加入空闲列表；2）评价算法减少了调度时对寄存器进行更名的要求。使得流水线更像标准的 DLX 流水线或者是标准的计分板和 Tomasulo 系统结构；数据前递和旁路技术可以使用。允许数据仅仅从寄存器中获得，不再需要从重排序缓冲器中保存值，这对平衡流水线是重要的。很多处理器采用这种技术的变体，它提供了另外一种支持精确中断段。对精确中断的 undo 处理变为仅需要恢复寄存器表工作。利用显式寄存器更名，结果可以立即写入寄存器文件，并且 ISA 中的寄存器名字在程序中的顺序中是3）实现方法的。9高体复习要点 (5) 消除器别名带来的写读基于显示寄存器换名策略的记分板控制的方法如上图所示，分为以下四个

32、步骤：1）ie。该阶段译码并检测结构。指令按照程序次序发射，如果有结构或者没有空闲的物理寄存器则暂停发射；2）read operand。当没有数据解决方法和标准计分板相同；时，操作数。所有的数据相关在这个阶段解决，3）execute。功能执行指令；和标准计分板相同。4）write back。写回结果，和标准计分板相同。对于精确中断和式的支持，通过保存转移指令和中断时的寄存器表，当错误时将寄存器表恢复到保存时的状态。显示寄存器换名是对转换表的快速，拥有的物理寄存器并能够辨认出哪些寄存器有空闲，但是它并不需要有保留站技术，现代高等计算机体系结构都会将这两种技术一起使用来提高流水线的性能。1）怎样管

33、理显式寄存器表？一般来说物理寄存器文件大于 ISA 寄存器，发射时每个修改寄存器的指令会从列表中分配一个新的物理寄存器。当使用LD 指令后原有寄存器取值会变得无意义。1) 基本原理为了使使用者可以大容量的快速器，且经济代价小采用器层次结构，其根据是程序的局部性原理和内存技术的性能价格比原则。从而建立自上到下的层次结构，并通过地址机制将其联系起来。2）层次设计相关问题块的放置与直接相连、全相联、组相联(折中原则)块的寻找和搜索通过地址标记给出块地址，检查块标记是否与对应块地址相匹配块的替换保留策略随机替换策略写操作的实现LRU 最近最少使用替换策略先进先出策略写直达策略(信息同时写到 Cache

34、 和器)出于数据一致性考虑写回策略(cache 中对应块被替换时才会被写入内存)3)改进 Cache 功能的途径Cache 性能评价公式：出于通信量减少考虑器平均时间=命中时间+缺失率*缺失代价CPU 时间=(CPU 执行时间时钟周期数+器停顿时间时钟周期数)*时钟周期时间提高 Cache 性能途径可以用公式来解释，主要是减少缺失代价，减少缺失率，减少命中时间去实现的。以下1） 降低 Cache 缺失率详细介绍改进性能相关方法：缺失分为以下三种类型：强制缺失由于首次或冷启动不得不重新调用的块缺失容量缺失Cache 容纳不了程序执行所需要的所有数据块引起的缺失缺失太多块被到同一组中，不得不放弃再

35、重新调用的缺失具体途径：(共七种方法)增大块容量降低强制缺失，增大 Cache 容量可以降低容量缺失，提高相联度可以降低缺失，指令和数据的硬件和预取是根据对Cache 需求估计，利用器10高体复习要点 (7) 器层次结构设计与 Cache 相关原理带宽来提高性能。编译优化是根据程序结构对其优化调整以改进性能。a)通过增大块容量来减少失效要平衡时间和空间局部性，不是越大越好。块容量越小，空间局部性不能很好利用；块容量越大，时间局部性不好，且传输成本增加，交换代价越大。而且，更大的块容量会引起更大的失效损失。块容量的选择取决于较低层器的延迟和带宽，高延迟和高带宽，则块容量大一些好，因为这样在每次失

36、效时 cache 可以获得b)通过增大相联度来减少失效两个重要经验规律：的字节，而失效损失量的增加。8 路组相联和相同容量的全相联 Cache 在降低缺失率方面同样有效容量为 N 的直接与容量为 N/2 的 2 路组相联具有同样的缺失率因为相联度增加会引起命中时间增加，有可能造能下降，所以相联度不是越高越好。c) 使用牺牲 Cache(Victim Cache)来减少失效，增加一个存放从 cache 中放弃的数据块的缓冲器（一个全相联 cache）。每次数据。下级器之前首先检查一下牺牲 Cache 是否有所需d）通过伪相联来减少失效。结合了直接的快速命中和 2 路组相联的低的优势。用 cach

37、e 分解：若命中，过程同直接cache 的过程相同；在失效时，检查 cache的另一半看是否有所需要的信息，有则称为伪命中。能够每个组中哪一块是快命中，哪一个是慢命中（伪命中）是非常重要的。若块命中需要 12 个周期，CPU 难以流水化，所以不适合用于一级cache；平均间短，做成二级、三级 cache 好。e）通过硬件预取指令和数据减少失效。时失效时取多个块，多取的块放在流缓冲器中，当失效时检测流缓冲器，若被请求块在流缓冲区中找到，则原cache 请求被取消，块从流缓冲区中读入，然后发出下一个预取请求。要求具有额外的带宽，并且没有其他破坏代价。用带宽换取时间。f）通过编译器预取数据减少失效。

38、预取指令，提前发出数据请求。一般限制使用它，因为提前预装可能会挤掉其他原先在 cache 里的随后又马上可能需要用到的块，这样反而不好。发射预取指令需要时间代价，引起一些开销。g）通过编译优化减少失效，常用的技术包括：合并数组、循环交换、循环合并和块化等。合并数组通过将两个独立数组合并为一个复合元素的数组来改进空间局部性；循环交换通过改变循环嵌套，来按序在器中的数据；循环合并将两个具有相同循环类型，且有一些变量的独立循环合并；块化通过不断使用一些数据块，而不是完整的遍历一行或一列；合并数组、循环交换、循环合并改进空间局部性，分块改进时间局部性。2） 降低损失代价处理器和器的性能差异使得缺失代价

39、的相应成本变高。a）保证在失效时读缺失对写优先。在带有写缓冲区的写直达策略下，cache 失效引起的读主存可能会引起 RAW，所以读失效时不能任意直接读内存（可能会读出老值），但如果简单的等待写缓冲区排空，则会增加读失效的损失。比较好的策略是，先读写缓冲区，如果没有再去读主存。在回写策略下，也可以通过读优先降低处理器开销：当发生读缺失要替换一个被写过了的块时，把该块到一个缓冲区后就去读下一层器，然后再把该脏块写入下一层11器。这样使得 CPU 的读操作可以很快结束。子块放置。对每个子块设置有效位，当失效时并不装入整块，只替换掉一部分。提前重启和关键字先送。在整个数据块装入cache 之前重新启

40、动 CPU。提前重起是指一旦所需要的数据到达，立即将其送到 CPU 中使 CPU 可以继续执行； 关键字先送是指将 CPU 所要求的关键字先从主存中取出并送给 CPU，在 CPU 执行过程中再将块中剩下的内容送入缓冲器中。这些设计只能使大容量的cache 块受益。e）用-Blocking cache 来减少失效时暂停。当 cache 失效后，允许其它的指令在该块上命中，要求 CPU 支持乱序执行。 “失效时仍命中”，通过在失效时发挥作用而不是忽略CPU 请求降低了有效“失效损失”。如果 cache 能多个失效，可能会进一步降低有效“失效损失”。乱序执行的 CPU 若能在二级 cache 中命中

41、，则能隐藏一级cache 的失效损失，但却不能隐藏二级cache 失效所带来的失效损失。f）使用多级 Cache由于命中增多，目标失效减少。更加关心总失效率。二级 cache 相对于一级 cache 命中慢，所以重点在减少失效上花功夫采用更大的cache 容量、选择较高相联度或加大块容量来减低失效率。多级 Cache 策略使用了越多越好的，在局部性原理的基础上加入多级大容量的cache 满足需求。关键字优先策略则比较急躁，一旦获取需要的关键字则马上工作。读比写优先比较偏心，处理器必须停下工作等待读操作的结果，可以在发射写操作之后继续工作。合并写缓冲区是一种伙伴关系，将若干字的连续写操作放到一个

42、块中，提高内存效率。3） 降低命中时间a）通过小、简单的 cache 来加快命中时间。小硬件但会增加失效率。速度快，有助于减少命中时间，b）通过避免地址变换加快命中：利用地址的物理部分进行索引。使用虚拟 cache，则每次进程间的切换都必须冲洗 cache，代价是冲洗时间和空 cache的义务失效，同时还要处理别名问题因为不同的虚拟地址可能到相同的物理地址。该法限制了cache过页大小增大相联度解决。c）通过流水化写操作来加快命中时间。将检测和更改 cache 分为不同流水级，当前写操作的检测和上一次写操作的cache 更改同时进行；d）通过小子块加快失效时写操作。如果大多数写操作是一个字，子

43、块也是一个字，并采用全写策略，那么总是立即进行写子块和更新。注意，该策略不能用于回写 cache。1) 基本技术DRAM 技术(动态随机器)：利用多路复用技术将地址分为行器和列器，分。因此别在不同的选通信号的基础上设置。为了尽可能多地存放信息，只用一个晶体管需要周期性刷新。不过由于刷新引起的时间和性能损失是影响变化的主要原因。器性能和 cache 缺失代价12高体复习要点 (8)器技术基础知识所有 cache 的设计的本质都是在加快命中和减少失效上进行平衡。SRAM 技术是静态技术，它一般使用 6 位晶体管来数据，以防止数据被破坏。SRAM 可以使用低耗能保持信息不丢失，主要优势在于其容量和速

44、度。2）性能提高的几种利用快速页模式，利用 N*M 行来保存一行信息。在一行到寄存器时，只需要 CAS 列选择信号该行的其他 M 位块。而不用像传统的 DRAM 一样，每次必须指定行和列选通信号。它是利用同步信号在不需要额外行时间内对行缓冲信息进行重复。利用同步 DRAM 技术,即在 DRAM 接口上添加一个时钟信号，使得重复传输不需要承担开销。可编程的寄存器保存了每次请求的字节数。它可以为每个请求在几个时间周期SDRAM内传送大量的字节。PC100，PC133 都是高速运行的 SDRAM DIMM。DDR 技术，即在时钟上升沿和下降沿均可以发送数据，这样保证了数据双倍传输。只需在传统的技术基

45、础上进行小量的改进。以上技术均通过添加少量的逻辑电路来开发利用 DRAM的高带宽，并没有影响系统开销。不像传统的交叉4）RAMBUS 技术器，随着 DRAM 容量增加，这些方法仍然适用。RAMBUS 技术在 DRAM 和 CPU 之间做了进一步的优化。它定义了新的接口使得单块芯片是一个系统。每个都包含了交叉器和一个高速接口。它使用全新的内存架构来实现高时钟速率和高带宽技术。三种不同的封装技术SIMM内嵌单个DIMM内嵌两个的内存模块的内存模块RIMM内嵌 RAMBUS 的内存模块4）虚拟器一种器共享技术，可以将物理内存分块分配给不同的进程使用。在虚拟器中，CPU产生虚拟地址，然后利用硬件和进行

46、一系列的转换，可以得到实际的物理地址。Cache 缺失主要由硬件控制进行替换，而虚拟器替换主要由操作系统实现。因此需要为操作系统提高良好的替换算法。处理器地址大小决定了虚拟器大小，但与 Cache 大小无关。虚拟系统可以分为固定大小的页式系统和可变长度的段式系般会结合两者优势使用段页式系统实现。虚实地址变换机制 MMU：由 CPU 发出虚拟地址，MMU 机制将通过 table walk (页表查找机制)主存页表来获得关系。MMU 再将虚页号转换为物理页号，产生物理地址来访13问内存。当产生缺页时，CPU 将转到页面失效交给操作系统去实现。MMU 是管理和地址转换的。它主要实现在 TLB 协助下

47、进行快速地址转换TLB 失效后的填充机制。TLB 的控制机制，负责保护，快速地址转换技术(TLB):利用空间局部性原理将转换地址存放到专门的 Cache 使得器很少要求两次内存。这样特殊的地址转换 Cache 成为地址转换旁路缓冲器。TLB 的条目中的标志字段包含部分虚拟地址，数据部分包含物理页号、保存字段、有效位和使用位。如果要改变页面的条目的物理实页号，操作系统必须确认原来条目不在 TLB 中。TLB 技术极大地提高了地址转换的速度，页表项的 局部性更好，有更小的实效性。典型的 TLB 由符号位，(虚拟地址号),PPN(物理地址号)和联方法和多级机制。Table Walking 机制权限位

48、组成。它可以 Cache 中的各种机制，相TLB 实效发生后，重新填充 TLB 表项的机制。可以通过硬件模拟，通过状态机的控制来搜索页表获得信息填充到 TLB 中，优点是速度快，不需要指令执行和中断机制，但有可能产生Cache 中断，造成更大的实效损失。通过的模拟方式主要由操作系统去处理函数搜索页表，找到相应的表项，通过特定的指令填充到 TLB 中。优点是灵活性高，可移植性好，但处理性能不如硬件。高体复习要点 (8) 系统和 I/O 系统基础知识磁盘的指标：容量由面密度表示，面密度=表面磁道数/英寸(TPI)*磁道位数/英寸(BPI)磁盘延迟时间由排队时间+控制器时间+寻道时间+旋转时间+传输

49、时间总线操作总线包含两种基本类型：I/O 总线是多类型的设备之间互联，数据带宽变化范围大且遵从总线标准。CPU总线以高速与系统匹配以获取最大的带宽。总线操作由发送地址和接收和发送数据组成。由时钟信号分为同步总线和异步总线。同步总线控制线路由一个时钟和相关地址和数据协议组成。不需要其他的逻辑判断，速度快且费用低。异步总线可以接受各种类型的设备，可以加长总线长度，不考虑时钟和同步问题。选择同步和异步总线主要取决于数据带宽和连接总线的设备数量，以及物理长度的 I/O 能力。总线仲裁指对总线的使用进行合理的分配和管理。仲裁方式分集中式仲裁和分布式仲裁。集中式仲裁包含链式查询方式、计数器定时查询方式和独

50、立请求方式。分布式仲裁无需仲裁器，每个功能设备都有自己仲裁好和仲裁策略。143） 设备之间信息交换的方式程序查询方式利用程序控制实现数据传输，频繁的查询动作影响了系统的性能。程序中断方式设备主动通知 CPU 准备数据传输，当中断发生，CPU 中断当前工作转向中断处理子程序，提高了 CPU 使用效率，适合随机出现的服务。但系统开销较大。直接器的 DMA 方式DMA 方式是利用硬件控制的特殊处理器，它可以在 CPU 做其他工作时在内存和 IO设备之间传送数据。它适组数据的交换，DMA 控制器可以接管 CPU 总线控制，数据传输不受 CPU 干预，直接在销。通道方式器和设备之间传输数据，节约了中断开

51、利用通道实现对 IO 设备的管理和 DMA 操作，大大提高 CPU 工作效率，分担了 CPU 的 IO 处理能力。这种处理机称为通道。通道吸收了 DMA 硬件技术，又添加了管理，从而实现有层次性的IO 系统。4） 可靠性、有效性和稳定性是评价性能的标准错误、差错和故障错误指程序错误。其结果会产生一个或多个差错。当服务启动后差错才开始作用。由于差错造成数据影响到传输服务则产生了故障。三者关系如下：一个错误可以产生一个或多个延迟差错。差错当服务启动时才起作用，在延迟和作用状态循环，有可能产生新的差错。而模块故障由差错影响传输服务产生。这样的特点是可递归的，可适用于系统任何模块。可靠性的两种主要度量

52、标准模块可靠性标准是指从初始化开始到完成服务的持续时间。MTTF(平均无故障时间)是度量可靠性的标准。 服务 中止用 MTTR 来度量，而模块有效性由 MTTF/(MTTF+MTTR)来度量。5） RAID 独立磁盘冗余阵列廉价独立磁盘冗余阵列可以有效提高系统的可靠性和性能，比容量较大的硬盘更有容错性和纠错能力。不过需要的额外容量去冗余数据和的带宽去实现修改。RAID0 指非冗余磁盘阵列，表示数据无冗余地带状分布在几个磁盘。RAID1 指磁盘镜像，每个磁盘都可以完全到它的镜像，实现写操作必须两次物理写，读操作可以优化读。主要面向高 I/O 速率的高可用环境。RAID3 是奇偶校验硬盘，通过在恢

53、复组硬盘上进行奇偶位检查来防止硬盘失效。需要增加 33%的容量开销。RAID4 是块交错分布奇偶校验机制，对小数据写操作的优化，减少了磁盘数目和硬盘数量。可以有效支持大数量读写，缺点是每次写操作必须更新校验盘，达到顺序操作的瓶颈。RAID5 使用分布式奇偶校验机制，允许独立写的信息可以不同时在同一硬盘并行操作。1） Flynn 的结构分类体系单指令流单数据流(SISD)单处理器单指令流多数据流(SIMD)向量系统结构多指令流单数据流(MISD)流式处理器多指令流多数据流(MIMD)通用的微处理器15高体复习要点 (9) 多处理器和线程级并行MIMD 优势：1) 灵活性强。能够提供高性能单一应用

54、的单用户多处理器系统，也可以作为多道程序多处理器系统。2)能够充分利用现有微处理器的性能/价格优势。2） 并行计算机：通过多个处理元素的合作与通信来快速解决大问题的并行式计算机。主要分为两类：集中式共享结构和分布式共享结构。集中式共享结构中各处理器可以共享单个集中式器，通过一根总线将处理器和器互连起来。由器的时间相同。器在物理上是分布于单个主器对每个处理器都是对称关系，且每个处理器主因此称这个结构为均匀器(UMA).分布式共享结构的，分别服务于各个处理器。采用分布式器对互联网络的带宽要求比较高，缩短了本地器延迟，但处理器之间的数据通信变得很复杂。SMP 对称多处理器互方式指所有位置具有相同的时

55、间。与对称式共享器多处理器 UMA(也称均匀式器)，分布式共享器 DSM 系统，是将物理分开的器作为逻辑上器的位置，也共享的地址空间称为非均匀。DSM 多处理器由于时间取决于数据字在器(NUMA)。每个地址空间组织方式对应不同的通信机制。对于共享地址空间的机器可以利用地址空间通过加载和操作隐式传输数据。有多个寻址空间的多处理系统，数据通信通过显式在处理器间传送数据，这称为消息传递多处理器系统。基本概念SMP 指多个处理器通过总线共1)个物理器，每个处理器与同一个共享内存有相同的关系的设计结构。它支持共享和私有数据的高速缓存。私有数据是被单个处理器使用，而共享数据由多个处理器使用，本质上通过读写

56、共享数据完成处理器之间的通信。把私有数据缓存到总线就可以直接数据，减少了平均时间和对器带宽的要求，但要求减少延迟和降低带宽要求，同时减少多处理器数据的竞争现象。高速缓存一致性共享的高速缓存中的数据由多个处理器实现，如何对其数据一致性进行控制，需要深入2)研究。一个器数据返回结果都是最近写入的数值称为器的一致性。它分为高速缓存一致性和器一致性。高速缓存一致性定义了读操作可以返回什么数值，而器一致性定义写入数据何时才能被读操作返回。高度缓存一致性定义了对同一个存储器地址进行读写操作的行为，为。它们是互补的。器一致性的必要条件器一致性定义了关于其他器地址的读写行3)任何读操作都必须返回最近写的内容，

57、要求太严格。一般的认为，满足：任何写操作的结果最终都会被任何一次读操作可见，且所有的写操作都以正确的次序可见，则是一致的。为了保证上述要求，有 2 个原则：、如果 P 写 x，P1 读 x，且读和写之间足够远，那么 P 的写效果将被P1 看见；、对单一位置的写操作是串行化和序列化的：任何两个处理器对同一地址的两个写操作在所有处理器中都有相同的顺序。4) 增强一致性的基本方案高速缓存的一致性，为同时的共享数据作了备份，因此要为这些数据提供。副本可以减少延迟和共享数据的竞争现象。用于一致性的原因是在输入输出中，会尽量避免出现一个数据有多个副本的情况，但在多个处理系统上运行的程序却恰恰相反，为了减少

58、共享数据项的延迟，减少对共享内存的带宽要求，会要求在多个高速缓存由同一个数据的副本。这就需要不同处理器cache 之间的一致性，一16高体复习要点 (10) 对称式共享器系统结构(SMP)联般在硬件上引入一个协议高速缓存的一致性。关键在于态。广泛使用的协议包括：所有共享数据块的状目录式协议：把物理块的共享状态放到一个地点，成为目录式协议：每个含副本的高速缓存要保留该数据块共享状态的副本，但不集中保存状态。高速缓存通常放到共享式协议总线上。5)式协议可以通过两种方法实现一致性，一个是在处理器写数据项之前保证该处理器能够独占数据项，称为写无效协议。它在执行写操作时要使其他副本无效。即独占，使其它该

59、数据项的副本无效。该协议中必须保证执行写操作的串行化。(注意：该协议下读数据缺失时，拥有数据的处理器会应答并同时取消求处理器的 Cache 和内存都会被更新使用写回高速缓存)器相应。数据更新时请另外一种是在写入数据项时更新该数据项所有副本，称为写广播协议。内存的数据总是被更新，这要求要器数值都要更新。高速缓存中每个字是否共享。广播写操作时，其它处理器和写无效协议和写广播协议的性能差异：a、执行同一个字的多次写操作，其间没有读操作时：写广播协议多次广播，写无效协议只需在最初设置一次无效即可；b、对于含多个字的 cache：写广播协议对每个字执行写时都需要广播一次，写无效协议只需要对整块设置一次无

60、效即可。写广播协议作用于单个字，写无效协议作用于 cache 数据块。（可通过合并写操作来提高性能）c、一个处理器写入数据，另一个处理器读该数据时：写广播协议在两者之间的延迟会小一些。写无效协议数据副本先要置为无效，然后执行读操作，发现数据无效要阻塞，直到读入新的副本才能继续执行。式的协议实现在 SMP 中实现写无效协议成为主要的实现机制，写无效协议不会给总线和6)器带来太大压力，而总线和带宽是最紧张的资源。实现写无效协议关键在于利用总线来完成无效操作，即处理器只要获取总线控制权后在总线广播无效数据地址。所有处理器不断总线来检测地址。如果有广播地址，则在各自缓存中将数据设置为无效。总线保证的串