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 currentheuristics 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.