# H.3 为并行性调度和组织代码 我们已经看到，循环展开通过生成更长的直线代码序列，有助于发现指令之间的并行性。为此，人们还发展了两项重要技术：软件流水线和踪迹调度。 ## 软件流水线：符号化循环展开 **软件流水线**（software pipelining）重新组织循环，使新循环的每次迭代都由原循环不同迭代中的指令组成。查看 2.2 节例子中已经调度的展开循环代码，最容易理解这种方法。[^section-number] 该例的调度器实际上交错排列了不同迭代的指令，从而把同一次迭代内部具有依赖关系的指令隔开。从不同迭代中选择指令，可以使相互依赖的计算之间隔着整个循环体，增加展开后循环在调度时不发生停顿的机会。 软件流水线无需真正展开循环，就能交错安排不同迭代的指令，如图 H.1 所示。这可以看作 Tomasulo 算法硬件机制的软件对应物。前例的软件流水线循环包含一条加载、一条加法和一条存储，分别取自不同迭代。进入循环前还需要一些启动代码，循环完成后也需要收尾代码；为简化讨论，暂时忽略它们。 **例题**　下面的循环将数组中每个元素加上 F2 的内容，数组起始地址在 R1 中。给出它的软件流水线版本，可以省略启动和收尾代码。 ~~~asm Loop: L.D F0,0(R1) ADD.D F4,F0,F2 S.D F4,0(R1) DADDUI R1,R1,#-8 BNE R1,R2,Loop ~~~ **解答**　软件流水线对循环进行符号化展开，再从每次迭代中选取指令。由于展开只是符号化的，循环开销指令 DADDUI 和 BNE 不必复制。下列展开后的循环体省去了这些开销指令，并标出各次迭代选中的指令： ~~~asm ; 迭代 i L.D F0,0(R1) ADD.D F4,F0,F2 S.D F4,0(R1) ; 选中 ; 迭代 i+1 L.D F0,0(R1) ADD.D F4,F0,F2 ; 选中 S.D F4,0(R1) ; 迭代 i+2 L.D F0,0(R1) ; 选中 ADD.D F4,F0,F2 S.D F4,0(R1) ~~~ ![软件流水线从不同迭代中选取指令](/figures/app-h/fig-h-1.png) {#fig-H.1 .wide .expand num="H.1" caption="软件流水线循环从不同的循环迭代中选取指令，从而隔开原循环同一次迭代内部相互依赖的指令。软件流水线迭代上方和下方的部分，分别对应启动和收尾代码。"} 图内术语：Iteration＝迭代；Software-pipelined iteration＝软件流水线中的一次迭代。 把来自不同迭代的选中指令与循环控制指令合在一起，得到： ~~~asm Loop: S.D F4,16(R1) ; 存储到 M[i] ADD.D F4,F0,F2 ; 对 M[i-1] 做加法 L.D F0,0(R1) ; 加载 M[i-2] DADDUI R1,R1,#-8 BNE R1,R2,Loop ~~~ 忽略启动和收尾部分，假定将 DADDUI 调度到 ADD.D 之前，并调整 L.D 的偏移量、把它放入分支延迟槽，这个循环可以达到每 5 个时钟周期产生一个结果。加载与存储的偏移量相差 16，即两次迭代，因此主循环应少运行两次。注意，重复使用 F4、F0、R1 等寄存器，要求硬件避免循环中可能出现的读后写（WAR）冒险。在本例中，应该不会因数据依赖而停顿，因此该冒险不应构成问题。 查看展开版本，就能确定启动和收尾代码。启动时，要执行第 1、2 次迭代中主循环尚未执行的指令，即这两次迭代的 L.D，以及第 1 次迭代的 ADD.D。收尾时，要执行最后两次迭代中尚未执行的指令，包括最后一次迭代的 ADD.D 和最后两次迭代的 S.D。 软件流水线循环的寄存器管理可能很棘手。前例还不太难，因为一次迭代写入的寄存器，在下一次迭代就会读取。在其他情况下，可能需要增加从指令发射到结果被使用之间间隔的迭代数：循环体指令少而延迟大时，就有这种需要。这时必须将软件流水线与循环展开结合起来。 软件流水线可以视为符号化循环展开；事实上，一些软件流水线算法正是利用循环展开算法来确定如何安排流水线。相对于直接展开，软件流水线的主要优点是占用的代码空间更少。二者除了改善内层循环的调度，还分别减少不同类型的开销。循环展开减少分支和计数器更新所构成的循环开销；软件流水线则让循环未以峰值速度运行的阶段只在整个循环的开头和结尾各出现一次。若将一个执行 100 次迭代的循环固定展开 4 次，那么每次启动展开后的内层循环时都要支付启动开销，共支付 (100/4=25) 次。图 H.2 直观展示了这种行为。 两项技术针对的是不同开销，因此结合使用可能得到最佳性能。实践中，采用软件流水线的编译相当困难：许多循环必须经过大量变换才能流水化；流水线循环的开销与效率之间存在复杂权衡；寄存器管理又增加了一层复杂性。IA-64 为软件流水线加入了大量硬件支持，以帮助处理后两类问题。这些硬件可以提高软件流水线的应用效率，却不能省去复杂的编译器支持，也不能免除对循环最佳编译方式的艰难选择。 ![软件流水线与循环展开的执行模式](/figures/app-h/fig-h-2.png) {#fig-H.2 .wide .expand num="H.2" caption="(a) 软件流水线循环与 (b) 展开循环的执行模式。阴影部分表示指令间未达到最大重叠程度或最大并行性的时间。软件流水线只在开头和结尾各出现一次；若循环共 m 次迭代、每次展开 n 次，展开循环则出现 m/n 次。每一块代表 n 次迭代的展开。增加展开次数可以减少启动和收尾开销；相邻两次展开的开销彼此重叠，影响因而减小。两幅图中多边形下的总面积相同，因为操作总数等于执行速率乘以时间。"} 图内术语：Software pipelining＝软件流水线；Loop unrolling＝循环展开；Number of overlapped operations＝重叠执行的操作数；Time＝时间；Start-up code＝启动代码；Wind-down code＝收尾代码；Proportional to number of unrolls＝与展开次数成正比；Overlap between unrolled iterations＝展开迭代之间的重叠。 ## 全局代码调度 3.2 节讨论了利用循环展开与代码调度提高 ILP。若循环体是直线代码，这些技术效果很好，因为展开后的循环看起来像一个基本块。同样，若循环体只有一个基本块，就比较容易找到可重复的调度，软件流水线也很有效。但若展开循环的循环体内部还存在控制流，调度就会复杂得多。一般来说，要有效调度这类循环体，必须把指令移过分支，这就是**全局代码调度**。 本节先讨论全局代码调度的难点和限制。H.4 节讨论消除内层循环内部控制流的硬件支持；这里还将介绍两项在无法消除控制流时可用的编译技术。 全局代码调度的目标，是在保持数据依赖和控制依赖的前提下，把含有内部控制结构的代码片段压缩成尽可能短的序列。数据依赖为操作规定了偏序；控制依赖则限制代码跨越某些指令的移动。数据依赖可通过循环展开来处理；对于存储器操作，还可借助依赖分析，判断两次访问是否指向同一地址。寻找最短代码序列，意味着尽量缩短关键路径，也就是最长的相互依赖指令序列。 循环展开可以减少循环分支造成的控制依赖；全局代码调度则通过代码移动，减弱非循环条件分支造成的控制依赖。代码移过分支，往往会改变其执行频率，因此，要有效利用全局代码移动，就需要估计不同路径的相对执行频率。全局代码移动不能保证代码一定更快，但只要频率信息准确，编译器就能判断这种移动是否可能提高速度。 许多内层循环包含条件语句，因此全局代码移动十分重要。图 H.3 给出一个典型片段，可将其视为展开循环的一次迭代；较常执行的控制流以阴影标出。 ![包含条件分支的代码片段及常见路径](/figures/app-h/fig-h-3.png) {#fig-H.3 .wide .expand num="H.3" caption="一个代码片段，灰色表示较常执行的路径。移动对 B 或 C 的赋值，需要比直线代码更复杂的分析。本节关注不借助硬件支持时如何高效调度该片段；下一节的谓词化或条件指令提供另一种方法。"} 图内 T、F 分别表示条件为真、为假；X 是 else 分支中的代码。A(i)、B(i)、C(i) 表示相应数组元素。 要有效调度这段代码，可能需要把对 B、C 的赋值提前到检查 A 之前。这样的全局代码移动必须满足一组约束才合法。另外，移动 B 的代码具有推测性，而移动 C 的代码没有这种性质：只有原本会执行包含 B 的路径时，移动 B 才能加快计算。 要移动 B，必须确保数据流和异常行为都不改变。编译器通常不移动某些可能产生异常的指令，例如存储器访问，以此避免改变异常行为。H.5 节将说明，硬件支持如何增加推测性代码移动的机会，并消除控制依赖。即使增强了推测支持，能够探索更多机会，选择最佳编译方式仍很复杂。 编译器怎样才能确认移动 B、C 的赋值不会影响数据流？考察图 H.3 流程图的一种典型代码生成结果。假设 A、B、C 的地址分别在 R1、R2、R3 中： ~~~asm LD R4,0(R1) ; 加载 A LD R5,0(R2) ; 加载 B DADDU R4,R4,R5 ; 加到 A 上 SD R4,0(R1) ; 存储 A ... BNEZ R4,elsepart ; 检查 A ... ; then 部分 SD ...,0(R2) ; 存储到 B ... J join ; 跳过 else 部分 elsepart: ... ; else 部分 X ; X 的代码 ... join: ... ; if 之后 SD ...,0(R3) ; 存储 C[i] ~~~ 先考虑把对 B 的赋值移到 BNEZ 之前。将 if 语句之前最后一条对 B 赋值的指令记为 (i)。若在代码段 X 中或 if 语句之后，B 在再次被赋值前就被引用，将这条引用指令记为 (j)。只要存在这样的 (j)，移动 B 的赋值就会改变程序数据流：原先 (j) 依赖于 (i)，移动后却会依赖提前执行的 B 赋值。可以设想更复杂的方法，在 B 的旧值仍被使用时也允许移动赋值，例如在 if 之前保存 B 的影子副本，并在 X 中使用该副本。通常会避免这种方法，因为实现复杂，而且一旦选中的踪迹不是最佳路径，额外指令就可能拖慢程序。 把 C 的赋值移到第一个分支之前，需要两步。首先，将赋值越过 else 部分的汇合点，移入 then 部分。这会让计算 C 的指令依赖于分支控制；若走较少执行的 else 路径，它们就不再执行。因此，在这个片段之后执行、且数据依赖于 C 赋值的指令，会受到影响。为了让这些指令得到正确值，必须在 else 路径上复制一份计算 C 并赋值的指令。第二步，如果移动不会影响流入分支条件的数据，就可以将 C 从 then 部分移过条件判断。C 一旦移到 if 检查之前，else 中的副本通常就成为冗余，可以删除。 由此可见，全局代码调度受到许多约束。这也是设计者提供硬件支持、简化此类代码移动的动机；H.4 和 H.5 节将详细讨论。 全局代码调度还要通过复杂权衡来决定是否移动代码。例如，假设能够将 B 的赋值移到条件分支之前，必要时在另一分支加入补偿代码，这样就一定更快吗？答案是：有可能！同样，将 C 复制到 if 的两个分支，最初只会使代码变大；只有编译器最终成功地把计算移过 if 检查，才可能受益。 在移动 B 的计算及赋值时，编译器必须考虑： - then 和 else 分支的相对执行频率是多少？若 then 频繁得多，移动可能有益；否则移动的可能性较低，但并非绝无可能。 - 在分支之前执行 B 的计算与赋值，代价是多少？分支之前可能有空闲指令发射槽，可以容纳 B 的指令。从一阶近似看，B 的计算因此可能是“免费的”。 - 移动 B 会怎样改变 then 分支的执行时间？若 B 位于该分支关键路径的起点，收益可能很大。 - B 是否是最值得移到分支之前的片段？与移动 C 或 then 中其他语句相比如何？ - else 分支可能需要的补偿代码，代价是多少？这些代码能否得到有效调度，对执行时间又有何影响？ 仅从这份不完整清单，就能看出全局代码调度极其复杂。权衡取决于许多因素，各项全局调度决策又高度相互依赖。甚至最初选择哪些指令作为全局移动候选，也很复杂。 为简化这一过程，人们发展了多种全局代码调度方法。下面简要介绍的两种方法遵循同一原则：让编译器集中处理一个直线代码片段，该片段代表估计最常执行的路径。通过循环展开生成直线代码，而难点当然在条件分支的处理。两种方法都选择并调度最常执行的路径，相当于把控制流“拉直”。 ## 踪迹调度：聚焦关键路径 对于每周期发射许多指令的处理器，若条件执行或谓词执行（见 H.4 节）不适用或不受支持，而单靠循环展开又无法暴露足够的 ILP，踪迹调度就很有用。**踪迹调度**（trace scheduling）组织全局代码移动的过程，把潜在的代码移动代价转移到较少执行的路径上，从而简化调度。由于指定为低频的路径可能承担大量额外开销，这项技术最适合以下情况：性能剖析信息表明路径之间存在显著频率差异，而且这些信息能够较好地反映程序行为，不太依赖具体输入。当然，这也把它的有效应用限制在某些程序类别中。 踪迹调度分两步。第一步称为**踪迹选择**：寻找一个很可能执行的基本块序列，把其中的操作合并到更少的指令中；这一序列称为**踪迹**（trace）。循环分支的跳转概率很高，因此可用循环展开生成长踪迹。另外，静态分支预测也会为其他条件分支选择跳转或不跳转，于是多个基本块串接成直线序列。例如，若图 H.3 是内层循环，阴影路径比其他路径频繁得多，将循环展开四次后，主要踪迹就由阴影部分的四个副本组成，如图 H.4 所示。 选择踪迹后，第二步**踪迹压缩**（trace compaction）试图将它压缩成少量宽指令。踪迹压缩就是代码调度：尽可能把操作提前，并将其装入尽量少的宽指令或发射包中。 踪迹调度的优点是简化了全局代码移动的决策。它把分支视为进入或离开选定踪迹的跳转，并假定该踪迹是最可能的路径。将代码移过踪迹入口或出口时，通常需要在相应位置加入额外的维护代码。 ![循环展开四次后形成的踪迹](/figures/app-h/fig-h-4.png) {#fig-H.4 .wide .expand num="H.4" caption="将图 H.3 的代码片段视为内层循环，展开四次，并把其中的阴影部分视为最可能路径，便得到这条踪迹。踪迹出口对应离开高频路径的跳转，踪迹入口对应返回该踪迹的跳转。"} 图内术语：Trace entrance＝踪迹入口；Trace exit＝踪迹出口；T、F 表示条件为真、为假。 核心假设是：踪迹的执行概率远高于其他路径，因此维护代码的代价不必成为决定因素。只要指令能够移动，而且移动可以加快主要踪迹，就移动它。 踪迹调度已经成功应用于循环密集、性能剖析数据准确的科学代码。但对于行为不易刻画、循环不那么密集的程序，这种方法是否适合仍不清楚。在此类程序中，补偿代码的显著开销可能使踪迹调度失去吸引力；即使可用，编译器要有效使用它也会极其复杂。 ## 超块 踪迹调度的主要缺点之一，是踪迹中间的入口与出口会造成严重复杂性：编译器必须生成并跟踪补偿代码，而且往往难以估计其代价。**超块**（superblock）的形成过程类似踪迹，但它是一种扩展基本块，只允许一个入口，可以有多个出口。 由于只有一个入口，超块压缩只需考虑跨越出口的代码移动，因此比踪迹压缩容易。在前例中，可以形成只有一个入口的超块，移动 C 便更简单。此外，若循环只有一个基于计数的出口，例如没有提前退出、仅通过终止条件退出的 for 循环，那么得到的超块也只有一个入口和一个出口，调度就更加容易。 怎样构造只有一个入口的超块？方法是使用**尾部复制**（tail duplication），为踪迹入口之后的部分创建一个独立代码块。在前例中，每次循环展开都会创建一个从超块通往残余循环的出口，残余循环负责余下的迭代。图 H.5 将图 H.3 的片段视为内层循环体，展开四次后给出超块结构。选择了未预测到的路径时，执行便退出超块，之后的迭代由残余循环处理。如果残余循环的预期执行频率仍很高，也可以为它创建超块。 相对于更一般的踪迹生成方法，超块减少了维护与调度的复杂性，但可能导致更大的代码膨胀。与踪迹调度一样，当其他技术（例如 if 转换）失效时，超块调度可能最适合。即便如此，代码复制代价的估计仍可能限制其用途，并且必然增加编译过程的复杂性。 循环展开、软件流水线、踪迹调度和超块调度，都试图增加每周期发射多条指令的处理器能够开发的 ILP。 ![循环展开形成的超块与残余循环](/figures/app-h/fig-h-5.png) {#fig-H.5 .wide .expand num="H.5" caption="将图 H.3 的代码展开四次，并创建超块，得到图示结构。"} 图内术语：Superblock exit with n＝对应 n 值的超块出口；Execute n times＝执行 n 次；T、F 分别表示条件为真、为假。四个出口分别将 n 设为 4、3、2、1，交由右侧残余循环处理。 这些技术各自的有效性，以及它们与不同体系结构方法的适配性，是高速处理器研究者和设计者最积极探索的热点之一。 [^section-number]: 译注：本段原文写作 2.2 节；同节后文将循环展开及调度的相关讨论指向 3.2 节。