Approximation algorithms for instruction scheduling

点击翻译按钮获取中文摘要

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.