# 第六章：指令集并行及其开发 —— 软件方法
# 6.1 基本指令调度及循环展开
编译器指令调度的制约因素：程序固有的指令级并行，流水线功能部件的延迟
编译时指令调度不能消除指令间的相关，而是通过重新安排指令的发射顺序尽可能少地引起流水线空转，进而缩短整个指令序列的执行时间
问题：基本指令调度方法中，指令调度不能跨越分支指令（调度到延迟槽不计）
循环展开：把循环体的代码复制多次并按顺序排放，然后相应调整循环结束条件，删除多余的测试和分支指令；再通过寄存器重命名和指令调度等操作消除相关性，有效实施指令并行
# 6.2 跨越基本块的静态指令调度
# 6.2.1 全局指令调度
分支结构的循环体需要在多个基本块间移动指令，称为 “全局指令调度”。
关键路径（critical path）：根据指令间的相关关系构成的数据流图中延迟最长的路径
基本思想：（1）优化执行频率较高的基本块；（2）在循环体内的多个基本块间移动指令，扩大那些执行频率较高的基本块的体积（放到延迟槽中）
可用的方法：
- 将 thenpart 移到分支判断之前，是否需要在 elsepart 中添加补偿代码？是否会导致额外的数据开销？
- 将分支后继块移到 thenpart 和 elsepart 之中，如果不影响结果则继续前移。
问题：需要确定调度中 thenpart 和 elsepart 的执行频率各是多少，尽量把指令添加到空转周期中
# 6.2.2 踪迹调度
踪迹：程序执行的指令序列，通常由一个或多个基本块组成，踪迹内可以有分支，但一定不能包含循环，踪迹并不限制出入口数量。
当不同踪迹的执行频率差别较大且各条踪迹的执行频率受输入集的影响较小（补偿代码小）时，通过优化执行频率高的踪迹减少其开销（同时低频率的踪迹会增加开销）来优化执行效率，非常适合多发射处理器。
踪迹选择：从程序的控制流图中选择执行频率较高的路径（踪迹）
- 循环结构采用循环展开，根据多次循环体的拼接构建控制流图
- 分支结构根据典型输入集下的运行统计信息，确定目标踪迹
踪迹压缩：确定踪迹后进行指令调度和优化，尽可能地缩短其执行时间；注意跨越踪迹内部的入口或出口调度指令时可能要添加补偿代码
# 6.2.3 超块调度
超块（superblock）是只能拥有一个入口，但可以拥有多个出口的结构。对于超块只需要考虑跨跃踪迹出口的指令调度，减少了生成补偿代码的难度。
尾复制技术：循环展开 n 次后所有的出口 m 都要继续完成余下的 n-m 次迭代，因此需要将源循环体复制一份作为出口的后继基本块，它总是作为退出超块后必须执行的补偿代码
超块结构目标代码的体积大大增加，补偿代码的生成使得编译过程更加复杂
# 6.3 静态多指令发射：VLIW 技术
基本思想：把同时发射的或者满足特定约束的一组操作打包得到更长的指令（64bit，128bit）
与超标量处理器（相关检测和指令调度基本都由硬件完成）不同的是，它的相关检测和指令调度工作全部由编译器完成
需要多个功能单元才能支持多个操作同时执行
问题：编码效率低（需要增加循环展开的次数，很难找到足够多并行指令填满所有槽）；没有检测逻辑，只靠互锁机制保证正确性（编译时无法确定等待时间，当一个功能单元超过编译时默认最小暂停时间时只能暂停整个流水线等待），可能增大开销；代码兼容性差
