Grant: Collaborative Research and Development Grants
McMaster University
$44,500.00
Approximation algorithms for instruction scheduling
FY 2018-19
Summary
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.
Program
Collaborative Research and Development Grants
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
498032-2016
Name nom
Anand, Christopher
Department département
Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2018
Competition year année de concours
2016
Award amount
44500
Program id
CRDPJ
Program name en
Collaborative Research and Development Grants
Program name fr
Subventions de recherche et développement coopérative
Group en
Research partnerships programs
Group fr
Programmes de partenariat
Committee code
96
Committee name en
RPP Internal Decision Cttee
Committee name fr
Cté de décision interne - PPR
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2715
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Optimization
Research subject fr
Optimisation
Partie
3
Nb partie
3
Application title
Approximation algorithms for instruction scheduling
Keyword
NSERC
Application summary
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.