Advanced

Processor Models For Instruction Scheduling using Constraint Programming

Hylén, Karl LU (2015) In LU-CS-EX 2015-34 EDA920 20151
Department 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:
author
Hylén, Karl LU
supervisor
organization
course
EDA920 20151
year
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},
  keyword      = {Compiler optimisation,Instruction Scheduling,Constraint Programming,Optimal method},
  language     = {eng},
  note         = {Student Paper},
  series       = {LU-CS-EX 2015-34},
  title        = {Processor Models For Instruction Scheduling using Constraint Programming},
  year         = {2015},
}