Processor Models For Instruction Scheduling using Constraint Programming
(2015) In LU-CS-EX 2015-34 EDA920 20151Department of Computer Science
- Abstract
- Instruction scheduling is one of the most important optimisations performed
when producing code in a compiler. The problem consists of finding a minimum
length schedule subject to latency and different
resource constraints. This is a hard problem, classically approached
by heuristic algorithms. In the last decade, research interest has shifted
from heuristic to potentially optimal methods. When using
optimal methods, a lot of compilation time is spent searching for an optimal
solution. This makes it important that the problem
definition reflects the reality of the processor.
In this work, a constraint programming approach was used to study the impact
that the model detail has on performance. Several models of a superscalar
... (More) - Instruction scheduling is one of the most important optimisations performed
when producing code in a compiler. The problem consists of finding a minimum
length schedule subject to latency and different
resource constraints. This is a hard problem, classically approached
by heuristic algorithms. In the last decade, research interest has shifted
from heuristic to potentially optimal methods. When using
optimal methods, a lot of compilation time is spent searching for an optimal
solution. This makes it important that the problem
definition reflects the reality of the processor.
In this work, a constraint programming approach was used to study the impact
that the model detail has on performance. Several models of a superscalar
processor were embedded in LLVM and evaluated using
SPEC CPU2000. The result shows that there is substantial performance to be
gained, over 5% for some programs. The stability of the
improvement is heavily dependent on the accuracy of the model. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/7791287
- author
- Hylén, Karl LU
- supervisor
- organization
- course
- EDA920 20151
- year
- 2015
- type
- H3 - Professional qualifications (4 Years - )
- subject
- keywords
- Compiler optimisation, Instruction Scheduling, Constraint Programming, Optimal method
- publication/series
- LU-CS-EX 2015-34
- report number
- LU-CS-EX 2015-34
- ISSN
- 1650-2884
- language
- English
- id
- 7791287
- date added to LUP
- 2015-08-27 07:57:49
- date last changed
- 2015-08-27 07:57:49
@misc{7791287, abstract = {{Instruction scheduling is one of the most important optimisations performed when producing code in a compiler. The problem consists of finding a minimum length schedule subject to latency and different resource constraints. This is a hard problem, classically approached by heuristic algorithms. In the last decade, research interest has shifted from heuristic to potentially optimal methods. When using optimal methods, a lot of compilation time is spent searching for an optimal solution. This makes it important that the problem definition reflects the reality of the processor. In this work, a constraint programming approach was used to study the impact that the model detail has on performance. Several models of a superscalar processor were embedded in LLVM and evaluated using SPEC CPU2000. The result shows that there is substantial performance to be gained, over 5% for some programs. The stability of the improvement is heavily dependent on the accuracy of the model.}}, author = {{Hylén, Karl}}, issn = {{1650-2884}}, language = {{eng}}, note = {{Student Paper}}, series = {{LU-CS-EX 2015-34}}, title = {{Processor Models For Instruction Scheduling using Constraint Programming}}, year = {{2015}}, }