Skip to main content

LUP Student Papers

LUND UNIVERSITY LIBRARIES

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}},
  language     = {{eng}},
  note         = {{Student Paper}},
  series       = {{LU-CS-EX 2015-34}},
  title        = {{Processor Models For Instruction Scheduling using Constraint Programming}},
  year         = {{2015}},
}