Approximation algorithms for instruction scheduling

代码生成包括寄存器分配、指令选择和指令调度，是一个非多项式问题，它的满意解影响着我们所做的每一次计算。为了科普这个问题，人们发明了许多聪明的方法，这些方法很快就能提供从好到好的解决方案。启发式使用先验知识的处理器资源约束和共同的源代码模式的相互作用。在最简单的情况下，它们识别循环，并插入先前计算出的最佳循环开销。但是深度无序的处理器可能很难理解，甚至越来越难知道为什么电流理论是有效的。近似算法和更一般的随机算法提供了另一种方法来解决困难的非多项式问题。严格地说，随机近似算法是随机生成优化问题的可行解的过程，以及在最优解的固定公差内找到解的概率分析。在这个项目中，我们将扩展，改进和分析的近似算法，最近开创了在麦克马斯特硕士论文的Kriston Costa，指令调度，以涵盖所有方面的代码生成的软件流水线loop.An这种方法的一个额外的功能是，在随机调度的分布的相关性也可以告诉我们的处理器体系结构的特点。例如，我们之前已经发现了寄存器压力和吞吐量之间的相关性的一个子集的软件流水线的循环，这表明，不同的算法将更成功的循环与不具有此特性。这项工作是我们的合作与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.