Approximation algorithms for instruction scheduling

代码生成，包括寄存器分配、指令选择和指令调度，是一个非多项式问题，它的满意解影响着我们所做的每一次计算。为了应对这一点，许多聪明的启发式算法被发明出来，它们很快就提供了好的到好的解决方案。启发式算法使用关于处理器资源约束和常见源代码模式相互作用的先验知识。在最简单的情况下，它们识别循环，并插入先前计算出的最优循环开销。但是，严重乱序的处理器可能很难理解，甚至越来越难知道为什么当前**启发式算法是有效的。**近似算法和更一般的随机算法为困难的非多项式问题提供了另一种方法。严格地说，随机逼近算法是随机生成优化问题的可行解，并分析在最优解的固定容差内找到解的概率的过程。在这个项目中，我们将扩展、改进和分析一个近似算法，该算法最近在麦克马斯特的Kriston Costa论文中首创，用于指令调度，以涵盖软件流水线循环代码生成的所有方面。**该方法的另一个特征是，随机调度分布的相关性也可以告诉我们处理器体系结构的特征。例如，我们之前发现了软件可流水线循环的子集的寄存器压力和吞吐量之间的相关性，这表明对于具有和不具有此特征的循环，不同的启发式方法会更成功。**这项工作是我们与IBM多伦多实验室合作的继续，该实验室使我们能够瞄准当前和未来的zSeries大型机，这与本研究特别相关。作为回报，IBM已经能够通过许可和雇佣项目校友将我们的研究结果和想法纳入他们自己的产品中。

Code generation, including register allocation, instruction selection and instruction scheduling, is a non-polynomial problem, whose satisfactory solution affects every computation we do. To cope with this, many clever heuristics have been invented which afford good to great solutions, very quickly. Heuristics use a-priori knowledge about the interplay of processor resource constraints and common source-code patterns. At their simplest, they recognize loops, and insert previously worked-out optimal loop overhead. But deeply out-of-order processors can be difficult to understand, and it is getting harder to even know why current**heuristics are effective.**Approximation algorithms and more-general stochastic algorithms provide another approach to hard non-polynomial problems. Strictly speaking, a stochastic approximation algorithm is a procedure for randomly generating a feasible solution to an optimization problem, together with an analysis of the probability of finding a solution within a fixed tolerance of the optimal solution. In this project, we will extend, improve and analyze an approximation algorithm, recently pioneered in the McMaster master's thesis of Kriston Costa, for instruction scheduling to encompass all aspects of code generation for software-pipelined loops.**An additional feature of this approach is that correlations in the distribution of random schedules can also tell us about characteristics of the processor architectures. For example, we have previously found a correlation between register pressure and throughput for a subset of software-pipelinable loops, which suggests that different heuristics would be more successful for loops with and without this trait.**This work is a continuation of our collaboration with IBM Toronto Lab, which allows us to target current and future zSeries mainframes, which are particularly relevant for this research. In return, IBM has been able to incorporate the results and ideas of our research into their own products, through licensing, and through the hiring of project alumni.