24 KiB
指令级并行 - 各老师章节总结
曲冠南老师
授课主线
本章由曲冠南老师授课，授课主线清晰，从指令级并行的基本概念出发，逐步深入到开发ILP的各类技术方法。具体而言，老师首先阐述指令级并行ILP的基本概念与开发重要性，然后介绍相关的分类与流水线冲突问题，接着引出解决相关的两类方案，随后详细讲解静态调度技术（循环展开与指令调度），最后重点讲授动态调度技术，包括Tomasulo算法、动态分支预测技术（BHT、BTB）以及基于硬件的前瞻执行技术。
知识点总结
1. 指令级并行的概念与重要性
指令级并行ILP是指存在于指令一级即指令间的并行性，主要指机器语言一级，如存储器访问指令、整型指令、浮点指令之间的并行性等。其主要特点是并行性由处理器硬件和编译程序自动识别和利用，不需要程序员对顺序程序作任何修改，这使得ILP的发展与处理器的发展紧密相连。
开发ILP的重要性体现在：CPI流水线 = CPI理想 + 停顿结构冲突 + 停顿数据冲突 + 停顿控制冲突，减少右端各项就能减少总的CPI，从而提高IPC（每个时钟周期完成的指令条数）。
2. 相关与冲突
相关是程序固有的一种属性，反映了程序中指令之间的相互依赖关系。相关分为三类：数据相关、名相关（反相关、输出相关）、控制相关。
流水线冲突是对于具体的流水线来说，由于相关等原因的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。流水线冲突有三种类型：结构冲突、数据冲突、控制冲突。
3. 相关的两类解决方案
方案一是保持相关但避免发生冲突，通过指令调度（编译器静态调度）来实现；方案二是通过代码变换消除相关，采用寄存器重命名（寄存器换名消除WAR和WAW）。
4. 开发指令级并行的方法
开发指令级并行的方法包括：基于软件的静态开发方法、基于硬件的动态开发方法、以及硬件+软件技术。只有硬件技术和软件技术互相配合，才能够最大限度地挖掘出程序中存在的指令级并行。
5. 基本编译技术——循环展开与指令调度
循环展开与指令调度是基于软件静态开发ILP的典型技术。循环展开把循环体的代码复制多次并按顺序排列，然后相应调整循环的结束条件，这给编译器进行指令调度带来了更大的空间。指令调度则通过重命名和调度来开发更多的并行性。
曲老师以具体示例讲解了不调度、进行调度、循环展开不调度、循环展开并调度四种情况下代码执行时间的差异。原始循环每个元素需要10个时钟周期，通过循环展开+指令调度可以降低到平均每个元素3.5个时钟周期，显著提升性能。
6. 动态调度解决数据冒险
静态调度与动态调度的区别：静态调度依靠编译器在代码执行前进行调度；动态调度在程序执行过程中依靠专门硬件对代码进行调度。
指令顺序执行与乱序执行：顺序执行时指令放入流水线的顺序和完成的顺序一致；乱序执行时指令放入流水线的顺序和完成的顺序不一致。
曲老师指出静态调度的问题：当指令因数据相关被阻塞时，其后的无关指令也会被阻塞。解决办法是将ID段分成两个阶段——流出阶段（检查结构冲突）和读操作数阶段（等待数据冲突消失）。
动态调度虽然允许无关指令先执行，但引入了新问题：乱序执行可能导致WAR冲突和WAW冲突。解决方案是采用寄存器换名技术消除名相关。
7. Tomasulo算法
Tomasulo算法的核心思想是：记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小；通过寄存器换名来消除WAR冲突和WAW冲突。
算法基本结构包括：指令队列、保留站、Store/load缓冲器、公共数据总线CDB、运算部件、存储部件、浮点寄存器。
保留站每个保留站中保存一条已经流出并等待到本功能部件执行的指令，包括操作码、操作数以及用于检测和解决冲突的信息。CDB是所有功能部件计算结果送到的数据通路，将结果直接送到（播送到）各个需要该结果的地方。
Tomasulo算法的执行步骤分为三步：流出、执行、写结果。
Tomasulo算法有两个主要优点：一是冲突检测和指令执行控制是分布的；二是消除了WAW冲突和WAR冲突导致的停顿。
8. 动态调度解决控制冒险
动态分支预测技术：通过硬件技术，在程序执行时根据每一条转移指令过去的转移历史记录来预测下一次转移的方向。通过提前预测分支方向，减少或消除控制相关导致的流水线停顿。优点是根据程序的执行过程动态地改变转移的预测方向，有更好的准确度和适应性。
分支历史表BHT：用BHT来记录分支指令最近一次或几次的执行情况（成功或不成功），并据此进行预测。BHT方法只在判定分支是否成功所需的时间大于确定分支目标地址所需的时间时才有用。研究表明，4K大小的BHT预测准确率为82%～99%。
分支目标缓冲器BTB：将分支成功的分支指令的地址和它的分支目标地址都放到缓冲区中保存起来，以分支指令的地址作为标识。目标是将分支的开销降为0。表格中每一项至少有两个字段：执行过的成功分支指令的地址（匹配标识）和预测的分支目标地址。
9. 基于硬件的前瞻执行
前瞻执行的基本思想是：对分支指令的结果进行猜测，假设这个猜测总是对的，然后按这个猜测结果继续取出、流出和执行后续的指令。只是执行指令的结果不是写回到寄存器或存储器，而是放到ROB（ReOrder Buffer）缓冲器中。等到相应的指令得到"确认"后，才将结果写入寄存器或存储器。目的是在猜测错误时能够恢复现场。
基于硬件的前瞻执行结合了三种思想：动态分支预测、在控制相关结果尚未出来之前前瞻执行后续指令、用动态调度对基本块进行跨基本块的调度。实质是数据流执行：只要操作数有效，指令就执行。
ROB中每一项由四个字段组成：指令类型、目标地址、数据值字段、就绪字段。
前瞻执行机制将Tomasulo算法的"写结果"和"指令完成"分成两个不同的段：写结果段和确认段。
李宏图老师
授课主线
李宏图老师的授课特点是对知识点的讲解非常细致系统，尤其擅长通过具体的代码示例和表格来展示算法执行过程。本章内容与曲冠南老师类似，但在记分牌算法的讲解、Tomasulo算法举例、以及VLIW技术方面更加详细。整体分为几个主要部分：指令级并行概念与基本编译技术、动态调度解决数据冒险（含记分牌算法和Tomasulo算法）、动态调度解决控制冒险、以及多指令流出技术。
知识点总结
1. 指令级并行基础知识复习
数据相关：对于两条指令i和j，如果指令j使用指令i产生的结果，或者指令j与指令k数据相关而指令k又与指令i数据相关，则称指令j与指令i数据相关。数据相关具有传递性，反映了数据的流动关系。
当数据流动经过寄存器时，检测比较直观；当数据流动经过存储器时，检测比较复杂，因为相同形式的地址其有效地址未必相同，形式不同的地址其有效地址却可能相同。
名相关：名是指令所访问的寄存器或存储器单元的名称。如果两条指令使用相同的名但没有数据流动，则存在名相关。名相关有两种：反相关（指令j写的名与指令i读的名相同）和输出相关（指令j和指令i写相同的名）。
名相关的两条指令之间并没有数据传送，但执行顺序必须不能颠倒。换名技术可以通过改变指令中操作数的名来消除名相关，既可以用编译器静态实现，也可以用硬件动态完成。
控制相关：控制相关是由分支指令引起的相关，为了保证程序应有的执行顺序，必须严格按控制相关确定的顺序执行。
2. 程序顺序与正确性
程序顺序是由源程序确定的在完全串行方式下指令的执行顺序。对于正确执行程序来说，必须保持两个最关键的属性：数据流和异常行为。保持异常行为弱化为指令执行顺序的改变不能导致程序中发生新的异常。
如果我们能做到保持程序的数据相关和控制相关，就能保持程序的数据流和异常行为。仅仅保持数据相关性是不够的，只有再加上保持控制顺序，才能够保持程序顺序。
3. 静态调度技术
静态调度依靠编译器对代码进行调度，即在代码被执行之前进行调度；动态调度在程序执行过程中依靠专门硬件对代码进行调度。
循环展开与指令调度是开发循环级并行性的最简单和最常用的方法。通过循环展开、寄存器重命名和指令调度，可以有效地开发出指令级并行。
4. 控制冲突与延迟分支
处理分支指令最简单的方法是"冻结"或"排空"流水线，其优点是简单，但在前述5段流水线中给流水线带来了3个时钟周期的延迟。
减少分支延迟的方法包括：预测分支失败（允许分支指令后的指令继续在流水线中流动）、预测分支成功（假设分支转移成功并从分支目标地址处取指令执行）、延迟分支（从逻辑上"延长"分支指令的执行时间，把延迟分支看成由原来的分支指令和若干个延迟槽构成）。
分支延迟指令调度的三种方法：从前往调度（要求保证分支失败时执行被调度指令不会导致错误）、从目标处调度（要求被调度的指令必须与分支无关）、从失败处调度（要求保证分支成功时执行被调度指令不会导致错误）。
5. 动态调度——记分牌算法（自学内容）
记分牌机制：在没有资源冲突的前提下，尽可能早地执行其他没有数据相关的指令。允许指令乱序执行。
记分板记录并管理三张表：指令状态表（分四个阶段：发射、读操作数、执行完成和写回结果）、功能部件状态表、寄存器结果状态表。
限制记分板机制性能的因素：指令中可开发的并行性、记分板部件的入口数、功能部件的数量与类型、反相关和输出相关的存在。
6. 动态调度——Tomasulo算法
Tomasulo算法的核心思想是：记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小；通过寄存器换名来消除WAR冲突和WAW冲突。
Tomasulo算法的基本结构包括：指令队列、保留站、Store/load缓冲器、公共数据总线CDB、运算部件、存储部件、浮点寄存器。
保留站每个保留站中保存一条已经流出并等待到本功能部件执行的指令。公共数据总线CDB是所有功能部件计算结果送到的数据通路，将结果直接送到各个需要该结果的地方。
Tomasulo算法的执行步骤分为三步：流出、执行、写结果。算法具有两个主要优点：冲突检测和指令执行控制是分布的；消除了WAW冲突和WAR冲突导致的停顿。
7. 动态分支预测技术
动态分支预测技术通过硬件根据分支指令过去的表现预测其将来的行为。分支预测的有效性取决于预测的准确性以及预测正确和不正确两种情况下的分支开销。
动态分支预测技术的目的有两个：预测分支是否成功、尽快找到分支目标地址（或指令）。
8. 分支历史表BHT
分支历史表BHT或分支预测缓冲器是最简单的动态分支预测方法，用BHT来记录分支指令最近一次或几次的执行情况并据此进行预测。
只有1个预测位的分支预测缓冲记录分支指令最近一次的历史，只需1位二进制位。
采用两位二进制位来记录历史可以提高预测的准确度。研究表明，两位分支预测的性能与n位（n>2）分支预测的性能差不多。
BHT方法只在判定分支是否成功所需的时间大于确定分支目标地址所需的时间时才有用。研究表明，4K大小的BHT预测准确率为82%～99%。
9. 分支目标缓冲器BTB
在高性能流水线中，特别是多流出的处理机中，只准确地预测分支还不够，还要能够提供足够的指令流。许多现代的处理器要求每个时钟周期能提供4～8条指令。
BTB将分支成功的分支指令的地址和它的分支目标地址都放到缓冲区中保存起来，以分支指令的地址作为标识。表格中每一项至少有两个字段：执行过的成功分支指令的地址和预测的分支目标地址。目标是，将分支的开销降为0。
10. 基于硬件的前瞻执行
前瞻执行对分支指令的结果进行猜测，假设这个猜测总是对的，然后按这个猜测结果继续取出、流出和执行后续的指令。执行指令的结果不是写回到寄存器或存储器，而是放到ROB缓冲器中。等到相应的指令得到"确认"后，才将结果写入寄存器或存储器。目的：在猜测错误时能够恢复现场。
基于硬件的前瞻执行结合了三种思想：动态分支预测、推测执行后续指令、用动态调度对基本块进行跨基本块的调度。实质是数据流执行：只要操作数有效，指令就执行。
前瞻执行的基本思想总结：顺序流出指令队列、猜测路径和乱序执行、顺序确认（保证顺序写回）、猜错或发生异常没写回的全部不算数。
ROB中每一项由四个字段组成：指令类型、目标地址、数据值字段、就绪字段。
11. 多指令流出技术
多流出处理机有两种基本风格：超标量（Super scalar）和超长指令字VLIW。
超标量在每个时钟周期流出的指令条数不固定，依代码的具体情况而定。可以通过编译器进行静态调度，也可以基于Tomasulo算法进行动态调度。
VLIW在每个时钟周期流出的指令条数是固定的，这些指令构成一条长指令或一个指令包。指令包中，指令之间的并行性是通过指令显式地表示出来的。指令调度是由编译器静态完成的。
超标量处理机与VLIW处理机相比有两个优点：超标量结构对程序员是透明的，不需要重新排列指令来满足指令流出；即使是没有经过编译器针对超标量结构进行调度优化的代码也可以运行。
VLIW存在的问题：程序代码长度增加、指令字中的操作槽并非总能填满、采用了锁步机制（任何一个操作部件出现停顿时整个处理机都要停顿）、机器代码不兼容（配置不同的VLIW中机器代码不能移植）。
谭婧炜佳老师
授课主线
谭婧炜佳老师的授课特点是知识体系完整、讲解细致，特别擅长通过具体的代码示例来解释概念，对流水线的冲突类型和Tomasulo算法的讲解尤其详细。本章内容组织与其他两位老师类似，但在基础知识的讲解上更为系统全面，尤其对流水线冲突的类型和处理方法有详细的展开。
知识点总结
1. 指令流水线基础知识复习
相关与冲突：相关是两条指令之间存在的某种依赖关系，是静态属性，包括数据相关、名相关、控制相关。冲突是对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行，是动态属性，包括结构冲突、数据冲突、控制冲突。
冲突带来的问题：导致错误的执行结果；流水线可能会出现停顿，从而降低流水线的效率和实际的加速比。
结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突。常见的导致结构相关的原因：功能部件不是完全流水（瓶颈段）、资源份数不够。解决方法：插入暂停周期（"流水线气泡"）；或设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache。
有时流水线设计者允许结构冲突的存在，主要原因是减少硬件成本。
数据冲突：当相关的指令靠得足够近时，流水线中的重叠执行或重新排序会改变指令读/写操作数的顺序，使之不同于非流水实现时的顺序，则发生了数据冲突。
数据冲突分为三种类型：写后读冲突（RAW，最常见，对应真数据相关）、写后写冲突（WAW，对应输出相关）、读后写冲突（WAR，由反相关引起）。
控制冲突：执行分支指令的结果有两种——分支成功（PC值改变为分支转移的目标地址）和不成功/失败（PC值保持正常递增）。处理分支指令最简单的方法是"冻结"或"排空"流水线。
减少分支延迟的方法：预测分支失败、预测分支成功、延迟分支、循环展开。
2. 指令级并行的概念
指令级并行ILP是指存在于指令一级即指令间的并行性，主要是指机器语言一级，如存储器访问指令、整型指令、浮点指令之间的并行性等。特点是并行性由处理器硬件和编译程序自动识别和利用，不需要程序员对顺序程序作任何修改。
本章研究如何通过各种可能的技术获得更多的指令级并行性，必须是硬件+软件技术互相配合，才能最大限度挖掘程序中存在的指令级并行。
开发ILP的重要性：CPI流水线 = CPI理想 + 停顿结构冲突 + 停顿数据冲突 + 停顿控制冲突，减少右端各项就能减少总的CPI，从而提高IPC。
3. 基本编译技术——循环展开与指令调度
循环展开把循环体的代码复制多次并按顺序排列，然后相应调整循环的结束条件，给编译器进行指令调度带来了更大的空间。
循环展开和指令调度时要注意：保证正确性（注意循环控制和操作数偏移量的修改）、注意有效性（只有能够找到不同循环体之间的无关性才能有效使用循环展开）、使用不同的寄存器、删除多余的测试指令和分支指令并修正、注意对存储器数据的相关性分析、注意新的相关性。
4. 静态调度与动态调度
静态调度依靠编译器在代码执行前进行调度，通过把相关指令拉开距离来减少可能产生的停顿。动态调度在程序执行过程中依靠专门硬件对代码进行调度，减少数据相关导致的停顿。
指令顺序执行时，指令放入流水线的顺序和完成的顺序一致；指令乱序执行时，指令放入流水线的顺序和完成的顺序不一致。
动态调度允许乱序执行，但乱序执行可能导致WAR冲突和WAW冲突，解决方法是寄存器重命名。
5. Tomasulo算法
Tomasulo算法首先在IBM 360/91中被采用。核心思想：记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小；通过寄存器换名来消除WAR冲突和WAW冲突。
Tomasulo算法的硬件结构包括：保留站（保存已流出并等待执行指令的信息）、公共数据总线CDB（播送结果到所有需要该结果的地方）、load/store缓冲器、浮点寄存器等。
算法具有两个主要优点：冲突检测逻辑是分布的（通过保留站和CDB实现）；消除了WAW冲突和WAR冲突导致的停顿。
Tomasulo算法需要3段：流出、执行、写结果。
该算法有个限制：如果流水线中还有分支指令没有执行，那么当前指令就不能进入执行阶段，因为流出后程序顺序不再被保证，所以必须加上这个限制。
6. 动态分支预测技术
动态分支预测技术通过硬件在程序执行时根据分支指令过去的表现预测将来的行为。优点是有更好的准确度和适应性，程序每次执行时预测的分支方向可能与前次相同或不同。
分支预测的有效性取决于：预测的准确性、预测正确和不正确两种情况下的分支开销。
采用动态分支预测技术的目的：预测分支是否成功、尽快找到分支目标地址（或指令）。
需要解决的关键问题：如何记录分支的历史信息；如何根据这些信息来预测分支的去向。
从简单到复杂的动态转移预测技术：分支预测缓存器（BHT）→分支目标缓冲器（BTB）→基于硬件的前瞻执行（ROB）。
7. 分支历史表BHT
BHT或分支预测缓冲器是最简单的动态分支预测方法，记录分支指令最近一次或几次的执行情况并据此进行预测。
只有1个预测位的分支预测缓冲只需1位二进制位。
采用两位二进制位来记录历史可提高预测准确度。两位分支预测的性能与n位（n>2）分支预测的性能差不多。
两位分支预测中的操作有两个步骤：分支预测（根据BHT读出的信息进行预测）和状态修改。
BHT方法只在判定分支是否成功所需时间大于确定分支目标地址所需时间时才有用。对于SPEC89测试程序，4K的BHT预测准确率为82%～99%。
8. 分支目标缓冲器BTB
BTB将分支成功的分支指令的地址和分支目标地址放到缓冲区中保存，以分支指令地址作为标识。目标是将分支开销降为0。
BTB表格中每一项至少有两个字段：执行过的成功分支指令的地址（匹配标识）和预测的分支目标地址。
BTB的另一种形式：在分支目标缓冲器中存放一条或多条分支目标处的指令，而非地址。有三个潜在好处：更快获得分支目标处的指令；可一次提供多条指令；对多流出处理器很有必要；可进行分支折叠优化，实现零延迟分支。
9. 基于硬件的前瞻执行
前瞻执行对分支指令的结果进行猜测，假设猜测总是对的，然后按猜测结果继续取出、流出和执行后续指令。执行结果不是写回到寄存器或存储器，而是放到ROB缓冲器中，等到指令得到"确认"后才将结果写入寄存器或存储器。目的：在猜测错误时能够恢复现场（没有进行不可恢复的写操作）。
前瞻执行结合了三种思想：动态分支预测、推测执行后续指令、用动态调度对基本块进行跨基本块的调度。实质是数据流执行：只要操作数有效，指令就执行。
对Tomasulo算法加以扩充支持前瞻执行，把写结果和指令完成分成两个不同的段：写结果段和确认段。
实现前瞻的关键思想：允许指令乱序执行，但必须顺序确认。
ROB中每一项由四个字段组成：指令类型、目标地址、数据值字段、就绪字段。
前瞻执行通过ROB实现了指令的顺序完成，能够实现精确异常，很容易推广到整数寄存器和整数功能单元上。主要缺点是所需的硬件太复杂。
10. 多指令流出技术
超标量：每个时钟周期流出的指令条数不固定（有上限），可以通过编译器进行静态调度，也可以基于Tomasulo算法进行动态调度。超标量结构对程序员是透明的，不需要重新排列指令来满足指令流出。
VLIW：每个时钟周期流出的指令条数是固定的，指令包中指令之间的并行性通过指令显式表示出来，指令调度由编译器静态完成。
限制超标量流水线性能的障碍：load指令1个时钟延迟（load后续指令不能使用其结果）；分支延迟1个时钟（取决于分支指令在流出包中的位置）。
VLIW存在的问题：程序代码长度增加、指令字中的操作槽并非总能填满、采用锁步机制（任何部件停顿时整个处理机都要停顿）、机器代码不兼容。