1、第3章 指令级并行的限制o介绍o指令级并行限制的研究 o实际处理器中指令级并行性限制o硬件和软件推测的限制o多线程 3.1 介绍o问题引出 上一章我们介绍了流水线机制、多发射机制、动态调度机制和推测机制。当前设计者将精力集中在优化设计上，尝试在不改变发射速率的情况下获得更快的时钟频率，即开发指令级并行的时代即将结束。 本章我们讨论指令级并行的限制，如程序结构、硬件的预算以及转移预测的准确率等；最后讨论线程级并行线程级并行，作为指令级并行的替代和补充。3.2 指令级并行性限制的研究o研究五个方面的内容 指令级并行性限制的研究涉及以下五个方面的内容：硬件模型、窗口的大小和最大发射数的限制、实际转移
2、和跳转预测的影响、有限寄存器的影响以及非完美别名分析的影响。3.2 指令级并行性限制的研究o硬件模型 理想处理器：是指消除了所有指令级并行约束的处理器，在理想处理器中，对指令级并行的唯一约束来自寄存器或存储器中的实际数据流。 理想处理器包含以下方面的假设：寄存器重命名、转移预测、跳转预测、存储器地址别名分析、最优Cache。 3.2 指令级并行性限制的研究o理想处理器 寄存器重命名寄存器重命名 可用的虚寄存器数量没有限制，可以避免WAW和WAR冒险，可以有无限的指令同时开始执行 转移预测转移预测 最佳的转移预测，能够准确预测所有条件转移条件转移 跳转预测跳转预测 能够准确预测所有跳转，包括返回
3、跳转和需要计算的跳转 3.2 指令级并行性限制的研究o理想处理器 存储地址别名分析存储地址别名分析 能够准确确定所有的存储器地址，在不引用同一地址的情况下，load指令可以移动到store指令之前，这实现了最佳地址别名分析 最优最优Cache 所有的存储器访问花费1个时钟周期，实际应用中处理器通常隐含Cache缺失，使指令级并行度大受限制 3.2 指令级并行性限制的研究o理想处理器 转移预测和跳转预测消除了所有的控制相关，寄存器重命名和存储器地址别名分析消除了除真数真数据相关之外据相关之外的所有相关性，这些假设意味着经过调度，程序执行过程中任意一条指令都可以在其前序相关指令执行完成之后的时钟周
4、期立即开始立即开始执行执行，同时，还意味着对控制和地址的推测都是完美的。3.2 指令级并行性限制的研究o硬件模型 处理器模型 假设所有处理器模型均没有限制哪些指令可以在一个时钟周期内执行，即可以在一个时钟周期内发射无数条load或store指令；假设所有功能单元时延为1个时钟周期，因此，所有的相关指令相关指令都可以在相继的时钟周期内连续地发射。3.2 指令级并行性限制的研究o硬件模型 实际处理器 以上假设的理想处理器几乎是不可能实现的。比如IBM Power5是当前最为先进的超标量处理器之一，其每时钟周期最多发射4条指令，启动执行最多6条指令（对指令类型严格限制，如最多2条load-store
5、指令），拥有大量的重命名寄存器，强大的转移预测器，并能动态消除存储器二义性。指令级并行度测试见图3.1.3.2 指令级并行性限制的研究o窗口大小和最大发射数的限制 理想处理器进行了5个方面的假设，满足这些要求的算法是非常复杂的。假设所有的指令为寄存器指令且可用寄存器数量无限，为了判断要发射的n条指令是否存在寄存器相关，需要进行n*n量级的比较（排列数），即使只发射50条指令，也需要近2500次比较，这限制了一次发射指令的数量。 3.2 指令级并行性限制的研究o窗口大小和最大发射数的限制 为了实现并行执行，需要对指令间是否存在相关性进行检测，被检测指令的集合称为窗口窗口。窗口中的所有指令都必须保
6、存在处理器中，处理器每时钟周期需要比较的次数不小于最大完成速率乘以窗口大小，再乘以每条指令的操作数数量。 窗口的大小直接限制了在给定时钟周期内开始执行的指令数量，处理器所拥有的功能单元数量有限，寄存器端口数量也受限制，因此，一个时钟周期内发射执行指令数量要远低于窗口大小。 3.2 指令级并行性限制的研究o窗口大小和最大发射数的限制 多发射处理器的实现受到很多限制，包括每时钟周期发射指令数量、功能单元及单元延迟、寄存器端口、功能单元队列、对转移发射的限制以及对指令提交的限制，所有这些限制都是影响并行度的因素。这里只集中讨论窗口的大小。 窗口大小对并行度的影响见图3.2. 随着窗口大小的减小，指令
7、级并行度严重下降；定点程序的指令级并行度要低于浮点程序的指令级并行度。3.2 指令级并行性限制的研究o窗口大小和最大发射数的限制 窗口大小并不是越大越好，太大容量的窗口是不切实际且效率低下的，图3.2表明，与理想情况相比，实际窗口的大小会使指令的吞吐量严重下降。假设基本窗口大小为2K（为2005年的10倍），并假设最大发射能力为每时钟周期发射64条指令（ 同样为2005年的10倍），这些假设不会对非理想处理器开发指令级并行造成限制3.2 指令级并行性限制的研究o实际转移和跳转预测的影响 理想处理器总是能够准确预测转移和跳转，实际处理器不可能做到。图3.3说明实际转移预测带来的影响。 转移预测的
8、5个等级： 1、完美 所有的的转移在执行开始时准确预测 2、基于Tournament的转移预测器 使用相关2bit预测器和不相关2bit预测器，结合使用选择器，由选择器为每个转移选择最好的预测器3.2 指令级并行性限制的研究o实际转移和跳转预测的影响 3、标准2bit预测器 有512个2bit入口，还假设使用一个有16个 入口的缓存负责对返回地址进行预测 4、基于历史的预测器 静态预测器使用程序的历史文件预测转移是否被选中 5、无转移预测 不使用转移预测器，只有跳转被预测3.2 指令级并行性限制的研究o实际转移和跳转预测的影响 不考虑由错误转移预测引起的额外开销，改变转移预测方法只对基本块之间
9、可开发的并行度产生影响。 使用窗口大小为2K且发射速率为每时钟周期64条指令的情况下，转移预测方法的选择对并行度非常关键，图3.4给出了3种条件转移预测的成功概率（图中以错误率描述）3.2 指令级并行性限制的研究o有限寄存器的影响 理想寄存器通过使用无限数量的虚拟寄存器消除了所有寄存器访问中的名字相关。前面提及IBM Power5拥有最多虚拟寄存器，除64个系统结构寄存器外，还补充了88个定点和88个浮点寄存器。在多线程模式下，所有这些240个寄存器被两个线程共享，并且在单线程模式下所有寄存器对单线程可用。图3.5给出了减少重命名可用寄存器数量对并行度的影响。3.2 指令级并行性限制的研究o非
10、完美别名分析的影响 完美的别名分析在实际应用中是不可能实现的，这是由于编译阶段的别名分析不可能是完美的；此外，由于对并行存储器访问的数量没有限制，因此，在运行时可能需要进行无数次比较。图3.6给出完美模型与其他三种存储器别名分析模型对并行度的影响。 1、全局/堆栈完美分析模型 能够准确预测所有全局和堆栈访问，且假设所有堆栈访问都不发生冲突。3.2 指令级并行性限制的研究o非完美别名分析的影响 2、检测分析模型 在编译阶段对访问操作进行检测，以确定它们是否会相互影响，此外，假设基址寄存器指向的地址（如全局或堆栈）不是别名 3、无分析 假设所有的存储器访问都是冲突的 全局/堆栈完美分析方法的性能大
11、约是检测分析方法的两倍，这表明，要想获得更高的并行度，要有复杂的编译技术和动态分析的支持3.3 实际处理器中指令级并行性限制o较完美的处理器配置 今后将面世的处理器一些特性： 1、没有发射限制，每时钟周期至少发射64条指令，这不是主要问题，实现宽发射所需的高时钟频率、逻辑复杂性和功耗才是限制指令级并行度开发的首要问题。 2、1K入口的tournament预测器和16入口的返回预测器，预测器不是主要的瓶颈。 3、动态地、完美地消除存储器引用二义性，可通过小窗口或存储器相关预测器来实现。 3.3 实际处理器中指令级并行性限制o较完美的处理器配置 4、64个附加定点寄存器和浮点寄存器，浮点寄存器用于
12、寄存器重命名。 图3.7给出了以上配置在改变窗口大小时并行度与窗口大小的关系。 实际情况中，窗口大小和重命名寄存器的数量必须保持平衡，以防止其中之一成为发射速率的限制因素。3.3 实际处理器中指令级并行性限制 窗口的大小对定点程序的影响不如对浮点程序的影响大。由于浮点程序中循环级并行度较高，因此可开发的指令级并行度也高；而对定点程序来说，一些其他因素如转移预测、寄存器重命名以及可开发的并行度较少等，都是重要的限制因素。 简单大容量Cache、高时钟频率处理器与强调指令级并行度但时钟频率较慢Cache容量较小处理器之间作出权衡，见P116页例子。3.3 实际处理器中指令级并行性限制o克服研究模型
13、的限制 完美研究模型存在的限制主要有： 1、访问存储器的数据冒险 通过寄存器重命名可以消除WAW和WAR冒险，但并没有涉及存储器访问的WAW和WAR冒险，对堆栈的某个操作重用前一个使用过的堆栈空间，会引起WAW和WAR冒险，从而带来不必要的限制。3.3 实际处理器中指令级并行性限制o克服研究模型的限制 2、多余的相关 在寄存器数量无限的情况下，只有真寄存器数据相关被保留下来，但在递归或代码生成约定仍然会产生一些多余的真数据相关。比如循环控制变量的相关，由于控制变量每次循环时都会递增，因此循环中至少存在一个相关。此外，一些代码生成约定也会产生不必要的相关，这种问题在使用返回地址寄存器和堆指针寄存
14、器（在调用/返回队列中递增递减）格外突出3.3 实际处理器中指令级并行性限制o克服研究模型的限制 3、克服数据流的限制 在准确率足够高的情况下，值预测技术可以克服数据流的限制，但到目前为止，在关于这一主题的多篇研究论文中，没有一篇能通过实际的预测方法来明显提高指令级并行度。 指令级并行性限制的延伸以及实现宽发射的代价是限制开发指令级并行的主要因素3.5 多线程 在某些应用的高层中可能蕴含着大量的并行度，而开发指令级并行度的方法对这种高层并行度无能为力。比如联机事务处理系统中，查询操作和更新操作之间存在大量的天然并行度，由于互不相关，大部分查询操作和更新操作都可以并行处理。3.5 多线程o线程级
15、并行（TLP） 线程是指可以独立执行的进程，它拥有自己的指令和数据，一个线程可以是包含很多进程的并行程序的一部分，也可以是一个独立的程序。前面提到的高层并行度称为线程级并行，与开发循环代码中的并行操作指令级并行不同，线程级并行目标是开发多个执行线程之间内在的并行性。3.5 多线程o线程级并行（TLP） 线程级并行是一种可替代指令级并行的重要方法，因为开发线程级并行所需的成本比指令级并行低得多。线程级并行在许多重要应用中天然存在，比如服务器应用。 线程级并行与指令级并行是程序并行结构中两个不同方面，使用指令级并行可支持线程级并行的开发。3.5 多线程o多线程 多线程可使多个线程以重叠的方式共享一
16、个处理器中的功能单元。为了支持这种共享，处理器必须为每个线程保存指令状态。硬件必须对不同线程之间的快速切换提供支持，特别是线程切换的效率应比进程切换高得多，后者通常花费数以百计的处理器时钟周期。3.5 多线程o多线程 多线程的两种方法 1、细粒度多线程 能够在指令之间进行线程切换，从而使多个线程交替执行。交替常采用轮流的方式，跳过某一时刻的所有停顿线程，处理器在每一时钟周期必须具备线程切换的能力。优点是，在某个线程停顿时执行其他线程的指令；缺点是降低了每个线程的执行速度。3.5 多线程o多线程 多线程的两种方法 2、粗粒度多线程 是作为细粒度多线程的替代而设计的。粗粒度多线程只发生在代价较高的
17、停顿时才切换线程，比如二级Cache缺失。粗粒度多线程降低了线程切换代价，很大程度上避免了降低处理器速度的问题，但缺点是克服吞吐量损失能力有限。3.5 多线程o同时多线程 同时多线程是细粒度多线程的改进版本，它可以使超标量处理器能够完整有效地开发指令级并行和多线程。同时多线程使用多发射和动态调度处理器在开发线程级并行的同时开发指令级并行。 同时多线程的产生是由于现代多发射处理器的功能单元中含有大量的并行度，而单个线程无法有效地利用这种并行度。3.5 多线程o同时多线程 几种处理器性能比较： 1、不支持多线程 发射槽利用率受到缺乏指令级并行度的限制 2、粗粒度处理器 可以在一个线程停顿时切换到另
18、一个线程以 利用处理器资源，但在每个时钟周期内部，指令级并行的限制仍然会引起空闲。3.5 多线程o同时多线程 几种处理器性能比较（见图3.8）： 3、细粒度处理器 线程的交替消除了完全空的发射槽，但由于在给定的时钟周期内只允许一个线程发射指令，因此每个时钟周期内部还是会出现空闲的发射槽 4、同时多线程 所有发射槽在一个时钟周期内被多个线程共享，线程级并行和指令级并行被同时开发3.5 多线程o同时多线程的设计挑战 将多个线程混合在一起会影响单个线程的执行时间，在取指令的过程中也存在类似的问题。为了最大限度维持单个线程的性能，应当尽可能早地为单个线程取指，并在转移预测错误和预取缓存缺失时清空取指单
19、元。但这种做法会限制其他线程可调度的指令数，降低吞吐量，多线程处理器必须在这个矛盾中作出权衡。3.5 多线程o同时多线程的设计挑战 其他的一些挑战： 1、为了保存多个上下文信息，寄存器文件会很庞大； 2、不能影响每个时钟周期的开销，特别是在关键步骤上，比如在指令发射步骤中需要考虑更多候选指令，在指令完成步骤中需要对提交的指令进行选择； 3、必须保证Cache冲突不会使性能显著下降3.5 多线程o同时多线程的潜在优势 测试数据表明（见图3.9），同时多线程的的加速比在0.9-1.67之间，平均1.2。IBM Power5是目前多线程的强大实现，对于大多数应用来说，同时多线程或多或少都使性能得到了提升，而对于浮点密集型应用来说，由于Cache冲突最为严重，因此从同时多线程中获益最少。
