高体复习笔记

1、高体复习笔记PAGE PAGE Version 0.5 整理人张栋；最后整理日期 2003-6-25高体复习笔记10208830张栋说明：这份笔记是我复习高体期间整理的，目前还很不完善，很多题目没有想到，也有很多列在上面的要点没有时间写上去，因为我包括整理这份笔记在内复习高体的时间只有不过一天。盼望有人能将之补充完整，或者基于此笔记整理一份更详细的以饷师弟师妹，甚谢甚谢！（如有人愿补充，请在页脚处注明版本号、整理人及修改日期以防冲突。）名词解释BHTBTAC/BTB要点：用一个缓冲站来存储分支后面的下一条指令地址，这种缓冲站叫做分支目标缓冲站（BTB）或分支目标高速缓存（BTAC）Reorde

2、r Buffer要点：按FIFO即指令发射的次序存放指令每个表项包括：PC，目标寄存器，结果，意外状态当指令执行完成时，将结果放在ROB像保留站为其他介于执行、完成、提交的指令提供操作数将结果用ROB的编号来标记指令提交-将ROB顶部的数值放到寄存器中这样就易于实现错误预测路径或一次意外中的推测指令推测错误时只需从ROB中去掉该指令并从正确的后继开始执行。Rename Register/重命名要点：指令中的寄存器被数值或指向保留站的指针代替，这一过程称为寄存器换名；消除了WAR/WAR冒险，保留站比寄存器多，所以可以完成优化编译器所不能完成的调度显式寄存器重命名要点：显式寄存器重命名使用比IS

3、A所说明的寄存器数量要大的物理寄存器堆使用变换表（translation table）完成ISA reg-物理寄存器的映射，当寄存器写时为写的每一条指令从freelist里分配新的物理寄存器，指令不active时回收。Trace CacheSuperScalar/MultiScalarCMP/SMT/SMP/Cluster/ MPPDSM要点：物理上分开的存储器能够作为逻辑上共享的地址空间进行寻址，任何一个处理器能够通过引用地址的方式，访问任意节点上的存储器。SIMD/MIMD要点：同一条指令被多个使用不同数据流的处理器执行。MIMD要点：其中每个处理器取用自己的指令并对自己的数据进行操作。U

4、MA/NUMA/NORMA要点：不同处理器访问memory的时间相同/不同Multicomputer要点：没有远程内存访问，通过send/recv进行网络访问精确中断 （M,N）预测器要点：使用前m个分支行为去从2m个分支预测中进行选择，每一个预测分支对应于单个分支的n位预测器。trace scheduling 要点：trace scheduling分作两步：踪迹选择。从一个基本块中发现（静态分析预测）执行代码序列中最可能执行的代码序列；踪迹压缩。将踪迹挤压成一些VLIW指令，踪迹调度把操作尽可能早地提前执行。结构冒险/数据冒险/资源冒险三种数据相关：RAW/WAR/WAWDelay Slot

5、的三种调度：从前，从目标（只是taken时有效），跳下（not taken时有效）Cancelling Branch要点：错误预测时延迟槽指令squash访问的局部性时间/空间局部性TLB循环展开 vs 软件流水循环展开：从减少循环开销方面软件流水：减少循环执行时间软件流水要点：使用软件调度的方法对循环进行重构，消除/降低每个loop内的相关。最大化结果，比展开代码空间小，每个循环填充和排出流水线一次记住Loop Unrooling和Software Pipelining的对比图保留站CDBSpeculation要点：动态branch预测来选择要执行的指令或对数据值进行预测；允许控制相关解决前

6、指令的执行；（要求能够消除错误speculative序列时所产生的效果）动态调度能够处理不同的基本块的组合其执行的本质是数据流执行：当操作数可用时开始操作。VLIW要点：VLIW使用多个互相不相关的功能部件，不是努力去发射多个互不相关的指令到功能部件中，而是把多个操作封装到一条非常长的指令中。决定哪几条指令可以同时发射的任务交由编译器完成。相关技术：全局调度去发现可以并行发射的指令，例如循环展开并对代码调度进行优化。指令窗口要点：为了同时执行而被检测的指令集合，限制了可以检测的指令数目，也限制了可发射指令的最大指令条数。义务失效/冲突失效/容量失效Victim Cache伪相联/伪命中Non-

7、blocking Cache/Lockup-free Cache要点：CPU在等待cache返回缺失数据的同时可以继续cache访问。需要多端口，严重增加了cache控制的复杂性。提前重启要点：一旦块中所需字到达，就立即把它送到CPU，使CPU继续执行。关键字先送要点：首先向存储器请求缺失的字，然后一旦它到了就把它发送到CPU中，让CPU继续执行，同时装入块中其他字。局部失效率/总失效率要点：这一级cache的miss数除以对这一级cache的访问总数 vs CPU产生的访问总数。hit under miss/hit under multiple miss/miss under miss流缓冲

8、器（stream buffer）cache技术中的读比写优先要点：带write buffer的write through：读失效时查看write buffer，如果没有冲突而且存储器系统可以访问，就然读失效继续。Write back：把脏块拷贝到一个缓冲区后就去读下层存储器，然后在将该脏块写入下层存储器，而不是相反。比较共享存储和消息传递模型要点：共享存储易于在小规模机器上实现，易于编程，低时延，易于使用硬件控制的cache技术。消息传递使用硬件少，易于设计。刻画并行机器的三个要点要点：命名、同步、时延和带宽SCSI要点：即小型计算机系统接口。SCSI协议包括控制器和SCSI设备之间进行特定动

9、作的一系列状态。包括：n位计数器辨析/Pitfalls/Fallcies使用相同指令体系结构的的处理器的相对性能可以用时钟频率或者一套benchmark suite的性能来来比较。MIPS/MFLOPS是比较机器间性能的准确指标要点：MIPS=Extime=为何要用几何平均值来测定性能合成的基准测试程序能够预测真实程序的性能要点：易被优化与真实程序可被优化方式不同好的benchmark永远有效易被编译选项和预处理器优化易被体系结构开发人员特定优化实际需求随时变化设计一种“高级”指令集特性来支持一种高级语言体系结构要点：复杂、得不偿失，只能在有限环境中应用。可以设计一个没有缺陷的系统结构要点：体

10、系结构是软/硬件权衡，技术随着时间变化而变换。当初正确的可能到后来看起来是错误的。高的流水级数提高性能要点：load delay更长转移延迟更长转移预测失败的损失latch和时钟扭斜的影响superscalar和vliw的主要区别在于后者能够并行发射更多的指令 预测错误之间的指令数目比预测错误率更能体现预测性能要点：basic block大小是我们所关心的前者蕴涵了后者mips r4000的8级流水线是由mips r3000的4级流水线逐级细分而来不惜成本可以完全解决资源冲突完美无缺的体系结构是计算机系统成功的保证计算机的最好设计式不考虑实现优化最初目标n路组相联一定优于直接映射cache要点

11、：N个比较器与一个增加了额外的多路选择延迟判断命中/失效时才能得到数据虚拟cache总是比物理cache要好要点：同义问题，两个不同的虚拟地址可以映射到同一物理地址对于更新，必须更新具有同一物理地址的cache表项或允许存储不一致需要大量硬件，特别是需要对物理标签进行相联查找已确定是否出现多次命中；或者通过软件强制实现：alias boundary，即VA和PA相同的低位空间 cache大小两条指令之间有dependence一定会发生hazardcache在任何情况下都可以加速应用要点：cache是利用了时间/空间局部性降低了局部性的程序很难利用cache，例如流媒体，实时应用Global O

12、ptimization的代码调度范围通常比Inter Procedure Optimization要大要点：Global是指跨越基本块的代码调度，Inter Procedure是指跨越过程的代码调度多发射处理机的发射速率可以任意扩大要点：程序代码中固有的对指令级并行的限制；（相关；可开发并行性限制）在已有的硬件架构中使用多发机制的困难性；（硬件资源需求；应该评估硬件机制和编译器方法两者性能及成本上的优劣，并做更好的结合。）每一个超标量或VLIW机器具体实现时所面对的限制性因素。对于supersaclar的主要问题是指令发射逻辑部件的设计；对VLIW则存在技术上和逻辑设计上的问题。技术上代码膨胀

13、需要展开循环来填充长指令字，未被填满的指令，功能部件在译码时仍然会被翻译由于要把指令压缩到主存中并在指令读出到cache或进行译码时才扩展它们，而VLIW时静态调度的系统结构，在操作上锁定，任何一个功能部件的暂停均会导致处理器的暂停。增加了内存结构复杂性和存储访问延迟。VLIW的主要逻辑问题时二进制代码兼容问题。需要代码重新编译。SuperScalar vs VLIW的优势：可以更容易的开发不规则结构代码中的并行性对内存结构要求更少在评估系统或检查性-价时忽略软件要点：目前软件代价已经成为计算机系统成本中很重要的一部分cache的设计空间正交性认为增加指令发射速率并牺牲时钟频率来减少CPI会导

14、致系统性能降低仅提高影响多发射机制处理器的某一方面因素就可以提高整体性能要点：许多因素限制这多发射机器的性能，提高某一方面因素后，常常会发现其他方面限制系统性能的因素严重起来使用硬件预取总能提高性能简答raid05要点：RAID 0：无冗余RAID 1：磁盘映像，完全复制，一次逻辑写需要两次物理写，容量开销100RAID 3：加位交叉奇偶校验磁盘。RAID 5：将奇偶校验信息均匀的分布到各个磁盘中。一次逻辑写对应2次物理读+2次物理写。使得cpu从i/o事务中解脱出来的方法减少转移延迟的基本方法，包括使用条件和效果bank interleaved原理试述解决结构、数据、控制相关的方法要点：结构

15、增加关键路径上的硬件资源数据前递，编译器调度控制跳转预测，delayed slot试述cache和tlb重叠访问方式及其适用情况跳转预测的advantage要点：降低stall，更大的basic block-调度优化Loop Unrolling技术及其优缺点优点：增大基本块有利于代码调度减少了branch指令缺点：code density降低代码体增大register占用多硬件提高ilp的核心思想要点：乱序执行寄存器换名记分板的核心思想、局限性，在控制上和Tomasulo的不同核心思想：允许暂停后的指令提前处理（允许乱序执行-乱序完成，ID阶段检测所有结构冒险）局限：没有前递硬件，只有写回re

16、g file以后才能从reg中读，不能读流水线中间结果指令调度局限在基本块内（没有指令窗口），对于branch只能stall，不能跨越basic block功能部件少（结构冒险）存在结构冒险就暂停发射stall至WAR冒险解决-为什么不读后续指令？防止WAW冒险不同：控制&缓冲器分布于功能部件（Tomasulo）与集中于记分板使用编译优化减少cache失效的方法要点：合并数组、循环交换、循环合并、块化交互或事务处理的三部分要点：报交时间：用户输入命令的时间系统响应时间：用户报交和系统应答之间的时间思考时间：从系统应答到用户输入下一命令的时间I/O控制结构方式要点：轮询中断DMAI/O控制器I/

17、O处理器总线仲裁方式分类要点：菊花链、并行仲裁、轮询总线主设备/从设备/协议要点：主设备具有控制总线能力，发起总线事务。从设备是被总线事务激活的模块。总线协议是在总线事务中事件序列的规范和定时需求规范。动态调度的优点和核心思想优点：处理某些在编译阶段无法知道的相关，并简化编译器设计允许在别的流水线机器上编译的指令不经重编也能有效运行。思想：允许暂停之后的指令被执行，允许乱序执行，使用寄存器换名消除WAW和WAR冒险。记分板的核心思想：允许暂停之后的指令提前处理（允许乱序执行，ID阶段检测所有结构冒险）记分板的对WAR冒险的解决：排队等待操作以及它们操作数的拷贝只在读操作数阶段才读取寄存器记分板

18、的对WAW冒险的解决：暂停等待到其他指令的完成。记分板的局限性：没有前递硬件，只有写回reg file以后才能从reg中读取操作数，不能读流水线中间结果。指令窗口小，调度局限在基本块内部， 对于branch只能stall。功能部件少导致结构冒险存在结构冒险就暂停发射指令暂停执行到WAR解决设计记分板和tomasulo的结构、原理、步骤，以及对tomasulo推测式和精确中断的支持。（推测式乱序执行、按序提交、指令提交前保证不会出现意外）。比较记分板和Tomasulo算法结构：原理：步骤：区别：Tomasulo算法寄存器换名机制消除WAW和WAR冒险 vs 记分板使用编译器来做寄存器换名。Tom

19、asulo算法冒险检测和执行控制分散于功能部件的保留站 vs记分板集中于记分板Tomasulo算法使用CDB将结果从保留站缓存的地方直接送到功能部件（廉价的前递方法）vs 记分板从寄存器传送（无前递）。Tomasulo算法中L/S也像其他部件一样使用保留站。对specalation和precise interrupt的支持：需要从指令的实际完成中将提高cache性能的途径要点：降低失效率通过增大块大小来降低失效通过增加相联度来降低失效使用Victim Cache通过伪相联通过硬件预取指令和数据通过软件预取数据减少失效通过编译优化降低失效损失在失效时读比写优先子块放置提前重启和关键字先送用Non-blocking