Optimal global instruction scheduling for the Itanium processor architecture [Elektronische Ressource] / von Sebastian Winkel
281 Pages
English

Optimal global instruction scheduling for the Itanium processor architecture [Elektronische Ressource] / von Sebastian Winkel

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

Optimal Global Instruction Scheduling for theRItanium Processor ArchitectureDissertationzur Erlangung des Grades desDoktors der Ingenieurwissenschaften (Dr.-Ing.) derNaturwissenschaftlich-Technischen Fakultäten derUniversität des SaarlandesvonDiplom-InformatikerSebastian WinkelSaarbrückenSeptember 2004iiDas Bildmaterial für den Umschlag und für die Abbildungen auf den Seiten 32, 35 und 42 wurdefreundlicherweise zur Verfügung gestellt von Intel Deutschland GmbH.Intel, Itanium und Pentium sind eingetragene Warenzeichen der Intel Corporation oder ihrerTochterunternehmen in den USA und anderen Ländern. Andere Marken oder Produktnamensind Eigentum der jeweiligen Inhaber.Tag des Kolloquiums: 16.12.2004Dekan: Prof. Dr. Jörg EschmeierPrüfungsausschuss:Gutachter: Prof. Dr. Reinhard WilhelmPriv.-Doz. Dr. Friedrich Eisenbrand,Max-Planck-Institut für Informatik, SaarbrückenProf. Dr. Peter Marwedel, Universität DortmundVorsitzender: Prof. Dr. Raimund SeidelAkademischerMitarbeiter: Dr.-Ing. Stephan ThesingiiiAbstractOn the Itanium 2 processor, effective global instruction scheduling is cru-cial to high performance. At the same time, it poses a challenge to thecompiler: This code generation subtask involves strongly interdependentdecisions and complex trade-offs that are difficult to cope with for heuris-tics. We tackle thisNP-complete problem with integer linear program-ming (ILP), a search-based method that yields provably optimal results.

Subjects

Informations

Published by
Published 01 January 2005
Reads 22
Language English
Document size 2 MB

Optimal Global Instruction Scheduling for the
R
Itanium Processor Architecture
Dissertation
zur Erlangung des Grades des
Doktors der Ingenieurwissenschaften (Dr.-Ing.) der
Naturwissenschaftlich-Technischen Fakultäten der
Universität des Saarlandes
von
Diplom-Informatiker
Sebastian Winkel
Saarbrücken
September 2004ii
Das Bildmaterial für den Umschlag und für die Abbildungen auf den Seiten 32, 35 und 42 wurde
freundlicherweise zur Verfügung gestellt von Intel Deutschland GmbH.
Intel, Itanium und Pentium sind eingetragene Warenzeichen der Intel Corporation oder ihrer
Tochterunternehmen in den USA und anderen Ländern. Andere Marken oder Produktnamen
sind Eigentum der jeweiligen Inhaber.
Tag des Kolloquiums: 16.12.2004
Dekan: Prof. Dr. Jörg Eschmeier
Prüfungsausschuss:
Gutachter: Prof. Dr. Reinhard Wilhelm
Priv.-Doz. Dr. Friedrich Eisenbrand,
Max-Planck-Institut für Informatik, Saarbrücken
Prof. Dr. Peter Marwedel, Universität Dortmund
Vorsitzender: Prof. Dr. Raimund Seidel
Akademischer
Mitarbeiter: Dr.-Ing. Stephan Thesingiii
Abstract
On the Itanium 2 processor, effective global instruction scheduling is cru-
cial to high performance. At the same time, it poses a challenge to the
compiler: This code generation subtask involves strongly interdependent
decisions and complex trade-offs that are difficult to cope with for heuris-
tics. We tackle thisNP-complete problem with integer linear program-
ming (ILP), a search-based method that yields provably optimal results.
This promises faster code as well as insights into the potential of the ar-
chitecture. Our ILP model comprises global code motion with compen-
sation copies, predication, and Itanium-specific features like control/data
speculation.
In integer linear programming, well-structured models are the key to
acceptable solution times. The feasible solutions of an ILP are repre-
sented by integer points inside a polytope. If all vertices of this polytope
are integral, then the ILP can be solved in polynomial time. We define
two subproblems of global scheduling in which some constraint classes
are omitted and show that the corresponding two subpolytopes of our ILP
model are integral and polynomial sized. This substantiates that the found is of high efficiency, which is also confirmed by the reasonable so-
lution times.
The ILP formulation is extended by further transformations like cyclic
code motion, which moves instructions upwards out of a loop, circularly
in the opposite direction of the loop backedges. Since the architecture re-
quires instructions to be encoded in fixed-sized bundles of three, a bundler
is developed that computes bundle sequences of minimal size by means
of precomputed results and dynamic programming.
Experiments have been conducted with a postpass tool that imple-
ments the ILP scheduler. It parses assembly procedures generated by In-
tel’s Itanium compiler and reschedules them as a whole. Using this tool,
we optimize a selection of hot functions from the SPECint 2000 bench-
mark. The results show a significant speedup over the original code.ivv
Zusammenfassung
Globale Instruktionsanordnung hat beim Itanium-2-Prozessor großen
Einfluß auf die Leistung und stellt dabei gleichzeitig eine Herausforde-
rung für den Compiler dar: Sie ist mit zahlreichen komplexen, wechsel-
seitig voneinander abhängigen Entscheidungen verbunden, die für Heuri-
stiken nur schwer zu beherrschen sind. Wir lösen diesesNP-vollständige
Problem mit ganzzahliger linearer Programmierung (ILP), einer suchba-
sierten Methode mit beweisbar optimalen Ergebnissen. Das ermöglicht
neben schnellerem Code auch Einblicke in das Potential der Itanium-
Prozessorarchitektur. Unser ILP-Modell umfaßt globale Codeverschie-
bungen mit Kompensationscode, Prädikation und Itanium-spezifische
Techniken wie Kontroll- und Datenspekulation.
Bei ganzzahliger linearer Programmierung sind wohlstrukturierte
Modelle der Schlüssel zu akzeptablen Lösungszeiten. Die zulässigen Lö-
sungen eines ILPs werden durch ganzzahlige Punkte innerhalb eines
Polytops repräsentiert. Sind die Eckpunkte dieses Polytops ganzzahlig,
kann das ILP in Polynomialzeit gelöst werden. Wir definieren zwei Teil-
probleme globaler Instruktionsanordnung durch Auslassung bestimmter
Klassen von Nebenbedingungen und beweisen, daß die korrespondieren-
den Teilpolytope unseres ILP-Modells ganzzahlig und von polynomieller
Größe sind. Dies untermauert die hohe Effizienz des gefundenen Modells,
die auch durch moderate Lösungszeiten bestätigt wird.
Das ILP-Modell wird um weitere Transformationen wie zyklische Co-
deverschiebung erweitert; letztere bezeichnet das Verschieben von Befeh-
len aufwärts aus einer Schleife heraus, in Gegenrichtung ihrer Rückwärts-
kanten. Da die Architektur eine Kodierung der Befehle in Dreierbündeln
fester Größe vorschreibt, wird ein Bundler entwickelt, der Bündelsequen-
zen minimaler Länge mit Hilfe vorberechneter Teilergebnisse und dyna-
mischer Programmierung erzeugt.
Für die Experimente wurde ein Postpassoptimierer erstellt. Er liest
von Intels Itanium-Compiler erzeugte Assemblerroutinen ein und ordnet
die enthaltenen Instruktionen mit Hilfe der ILP-Methode neu an. Ange-
wandt auf eine Auswahl von Funktionen aus dem Benchmark SPECint
2000 erreicht der Optimierer eine signifikante Beschleunigung gegenüber
dem Originalcode.viExtendend Abstract
HP and Intel’s Itanium Processor Family (IPF) is considered as one of the most challenging
processor architectures to generate code for. Its performance is highly compiler-dependent since
it relies on static instruction scheduling. The code generator is responsible for extracting a high
amount of instruction-level parallelism and exposing it to the processor. To achieve this, it must
combine global instruction scheduling (with code motion between basic blocks) with the use of
predication and Itanium-specific features like explicit speculation.
When applying these techniques, the compiler must deal with strongly interdependent deci-
sions and keep the increasing resource pressure as a result of compensation copies and specula-
tive computations under control: Overuse can spoil the benefit due to execution unit shortage,
but the opposite, a too conservative application, can lead to many unused execution slots. It
is difficult for the greedy scheduling heuristics found in Itanium compilers to find a balance.
Moreover, resource-constrained instruction scheduling is—even when limited to basic blocks—
an NP-complete problem, for which heuristics deliver only approximations. It is unclear how
far away these are from exact, optimal solutions.
In this thesis we tackle the global instruction scheduling problem for the Itanium 2 processor
with integer linear programming (ILP), a search-based combinatorial optimization method that
yields provably optimal results. Our ILP model comprises global code motion with automated
generation of compensation code, predication, as well as vital IPF features like control and data
speculative loads. The ILP approach can—within certain limits—resolve the interdependences
between the involved decisions and deliver the global optimum in the form of a schedule with
minimal length. This promises faster code, as well as some theoretically well-founded insights
into the potential of the architecture.
In integer linear programming, the search space of feasible solutions is represented by the in-
teger points inside a polytope. A well-structured model, in which these integer points are tightly
enclosed by the polytope, is the key to acceptable solution times. If all vertices of the polytope
are integral, then the ILP can even be solved in polynomial time. Since we are modeling anNP-
complete problem, however, we cannot expect to find such a polytope of polynomial size for the
entire global instruction scheduling problem, but only possibly for subproblems. Therefore we
define several such subproblems in which some constraint classes are omitted (such as the re-
source constraints, which model the occupation of execution units, or the precedence constraints,
which enforce data dependence preservation). For subproblems that are no longerNP-complete,
ILP formulations may exist that describe integral and polynomial sized subpolytopes—and are
in fact developed in this thesis.
viiviii
For one of these subproblems, this is achieved by reducing it to a node packing problem on
a perfect graph and exploiting a standard result in order to obtain an integral subpolytope. A
further subproblem is modeled as a network flow problem, a problem class for which integral
polytopes are well known, too. In both cases, it is necessary to reduce the complexity of the
resulting ILP formulation afterwards, which is in the former case even exponential. This is
done by removing redundant constraints and by applying integrality-preserving transformations.
These include lifting the polytope to a higher dimension (to reduce the number of constraints
needed to describe it), or inversely, projecting it onto a lower-dimensional subspace (to reduce
the number of needed variables).
As a central theoretical result of this thesis, we further show that the identified integral and
polynomial sized subpolytopes are maximal in the sense that they cannot be extended by other
constraint classes without losing one of their two efficiency properties (integrality or polyno-
mial size). This follows—under the assumption P =NP—from twoNP-completeness proofs
for the extended subproblems. It substantiates that the found ILP model is close to maximal effi-
ciency. The polyhedral analysis also reveals in detail that there is a wide complexity gap between
local and global instruction scheduling.
The developed basic ILP model is enriched with further variants of code motion and spec-
ulation: Predicated code motion extends the scope of code motion via predication. Similarly,
partial-ready code motion is included, which allows instructions to be moved further upwards
along a control flow path by speculatively ignoring data dependences on instructions from other
paths. To increase the scheduling scope in the presence of loops, the model is extended to support
code motion into and out of loops. Upward code motion out of loops includes cyclic code motion
circularly in the opposite direction of the backedges, a variant which can effectively reduce the
schedule length of the loop body. A further add-on models the changes in the branch structure
resulting from blocks that are emptied via code motion. On the Itanium architecture, instructions
have to be encoded in fixed-sized bundles of three, which are further specified by templates.
To bundle the obtained schedules, a method is developed that computes bundle sequences of
minimal size by means of precomputed results and dynamic programming.
The experiments were conducted with a postpass tool that implements the ILP scheduler. It
parses assembly procedures and optimizes them as a whole. Various precomputations are per-
formed to reduce the search space. During the ILP generation, constraints are tightened dynam-
ically. This leads, in combination with the high efficiency of the used ILP model, to reasonable
solution times of not more than a few minutes. Using this tool, we optimize a selection of hot
functions from the SPECint 2000 benchmark. Assembly versions of them are generated with
Intel’s Itanium compiler and fed into the postpass optimizer. The rescheduled code turns out to
run significantly faster than the original version.
Although the ILP method is, because of the comparatively long solution times, not suited for
product compilers, the experimental results show that it is promising as a stand-alone optimiza-
tion tool for compute-intensive application kernels like compression and encryption routines. A
further interesting application is as a research tool: The comparison of the optimal results with
those of heuristics can help find and quantify room for improvements in the latter. Moreover, the
ILP approach can be used to explore the potential of the Itanium architecture since it delivers—in
contrast to all heuristics and limit studies—concretely the best achievable solutions.
Ausführliche Zusammenfassung
Bei der Itanium-Prozessorfamilie von HP und Intel gilt Codeerzeugung als eine gleichermaßen
wichtige und schwierige Compilerphase. Da diese Prozessorarchitektur auf statischer Instruk-
tionsanordnung beruht, ist ihre Leistung stark von der Qualität des Codeerzeugers abhängig.
Dieser ist dafür verantwortlich, ein hohes Maß an Parallelität auf Befehlsebene zu extrahieren
und explizit an den Prozessor zu übermitteln. Zu diesem Zweck muß er globale Instruktionsan-
ordnung (mit Codeverschiebungen zwischen Basisblöcken) mit dem Einsatz von Prädikation und
Spekulation kombinieren.
Dabei muß er zahlreiche wechselseitig voneinander abhängige Entscheidungen überblicken
und insbesondere den erhöhten Ressourcenbedarf infolge von Kompensationscode und spekula-
tiven Berechnungen unter Kontrolle halten: Ein übermäßiger Gebrauch von Codeverschiebungen
und Spekulation durch den Compiler kann zu Knappheit von funktionalen Einheiten führen, die
den Nutzen wieder zunichte macht. Das Gegenteil, eine zu konservative Benutzung, läßt das
Potential der Architektur ungenutzt. Für die in Itanium-Compilern eingesetzten Heuristiken ist
es schwer, hier einen Ausgleich zu finden. Darüber hinaus ist Instruktionsanordnung unter be-
grenzten funktionalen Ressourcen – auch wenn lokal auf einzelne Basisblöcke beschränkt – ein
NP-vollständiges Problem, für das Heuristiken nur Näherungslösungen berechnen. Wie weit
diese beim Itanium vom globalen Optimum entfernt liegen, ist unbekannt.
In der vorliegenden Arbeit wird das Problem globaler Instruktionsanordnung für den Itanium-
2-Prozessor mit ganzzahliger linearer Programmierung (ILP) gelöst, einer suchbasierten Metho-
de zur exakten Lösung kombinatorischer Optimierungsprobleme. Das entwickelte ILP-Modell
umfaßt globale Codeverschiebungen mit automatischer Einfügung von Kompensationskopien,
Prädikation sowie den Einsatz Itanium-spezifischer kontroll- und datenspekulativer Ladebefeh-
le. Der ILP-Ansatz kann – innerhalb gewisser Grenzen – die wechselseitigen Abhängigkeiten
zwischen den modellierten Entscheidungen auflösen und das globale Optimum in Form eines
Schedules mit minimaler Länge berechnen. Das läßt neben schnellerem Code auch theoretisch
fundierte Einblicke in das Potential der Itanium-Prozessorarchitektur erwarten.
Der Suchraum eines ILPs wird durch ganzzahlige Punkte innerhalb eines Polytops repräsen-
tiert. Wohlstrukturierte Modelle, bei denen diese Punkte so eng wie möglich von dem Polytop
umschlossen werden, sind der Schlüssel zu akzeptablen Lösungszeiten. Ganzzahlige Polytope
(mit ausschließlich ganzzahligen Eckpunkten) erlauben sogar Lösbarkeit in Polynomialzeit. Da
wir einNP-vollständiges Problem modellieren, können wir zwar nicht erwarten, ein solches Po-
lytop polynomieller Größe für das Gesamtproblem zu finden, möglicherweise aber für Teilpro-
bleme. Daher definieren wir mehrere solcher Teilprobleme durch Auslassung bestimmter Klas-
ixx
sen von Nebenbedingungen (wie zum Beispiel der Ressourcenschranken, die die Belegung der
funktionalen Einheiten modellieren, oder der Vorrangbedingungen, die die Einhaltung von Da-
tenabhängigkeiten sicherstellen). Für diejenigen Teilprobleme, die nicht mehr NP-vollständig
sind, können ILP-Formulierungen polynomieller Größe existieren, die ganzzahlige Polytope be-
schreiben – und werden in der Tat in dieser Arbeit entwickelt.
Für eines dieser Teilprobleme geschieht dies durch Reduktion auf ein Node-Packing-Problem
auf einem perfekten Graphen. Unter Ausnutzung eines bekannten Satzes kann dann eine Be-
schreibung dieses Problems durch ein ganzzahliges Polytop gefunden werden. Ein weiteres Teil-
problem wird als Netzwerk-Fluß-Problem formuliert, eine Problemklasse, für die ebenfalls ganz-
zahlige Polytope wohlbekannt sind. In beiden Fällen ist es allerdings notwendig, die Komplexität
der erhaltenen ILP-Formulierungen anschließend zu reduzieren (im ersteren Fall ist sie anfangs
sogar exponentiell). Dies geschieht durch Entfernung redundanter Nebenbedingungen und durch
die Anwendung von Transformationen auf die Polytope, wie zum Beispiel ein Lifting in eine
höhere Dimension (um die Anzahl der zur Beschreibung notwendigen Ungleichungen zu redu-
zieren), oder umgekehrt, eine Projektion auf einen Unterraum geringerer Dimension (um die
Anzahl benötigter Variablen zu reduzieren). Diese Transformationen werden so durchgeführt,
daß sie die Ganzzahligkeit der Polytope bewahren.
Als ein zentrales theoretisches Ergebnis dieser Arbeit zeigen wir dann, daß die gefundenen
ganzzahligen Teilpolytope polynomieller Größe maximal sind in dem Sinne, daß eine Hinzu-
nahme anderer Klassen von Nebenbedingungen nicht ohne einen Verlust von Ganzzahligkeit
oder polynomieller Größe möglich wäre. Dies folgt – unter der Annahme P = NP – aus zwei
NP-Vollständigkeitsbeweisen für die auf diese Weise erweiterten Teilprobleme. Es untermauert
die hohe Effizienz der gefundenen Formulierung. Die Ergebnisse der Analyse zeigen außerdem
im Detail auf, daß globale Instruktionsanordnung auch aus komplexitätstheoretischer Sicht ein
wesentlich schwierigeres Problem als die lokale Variante ist.
Das entwickelte Basismodell wird um weitere Varianten von Codeverschiebungen und Spe-
kulation erweitert: Prädikative Codeverschiebung erweitert den Spielraum für die Plazierung von
Befehlen mit Hilfe von Prädikation. Demselben Zweck dient partial-ready code motion, das es
ermöglicht, Befehle auf einem Kontrollflußpfad dadurch weiter nach oben zu verschieben, in-
dem Datenabhängigkeiten von Befehlen auf anderen Pfaden spekulativ ignoriert werden. Um
den Spielraum für die Anordnung von Befehlen bei Anwesenheit von Schleifen zu vergrößern,
wird das Modell um Codeverschiebungen in und aus Schleifen erweitert. Diese umfassen auch
zyklische Codeverschiebung, das Verschieben von Befehlen aufwärts über den Schleifenkopf hin-
aus in Gegenrichtung der Rückwärtskanten der Schleife. Weitere ILP-Formulierungen modellie-
ren Änderungen der Struktur der Sprungbefehle, die sich ergeben, wenn Blöcke durch globale
Codeverschiebungen ganz geleert werden.
Die Itanium-Architektur schreibt eine Kodierung der Befehle in Dreierbündeln fester Größe
vor, deren Befehlstypen durch Auswahl einer Vorlage (template) jeweils genauer spezifiziert
werden. Um die berechneten Schedules entsprechend zu bündeln, wird eine Methode entwickelt,
die Bündelsequenzen minimaler Länge mit Hilfe vorberechneter Teilergebnisse und dynamischer
Programmierung erzeugt.
Für die Experimente wurde ein Postpassoptimierer erstellt. Er liest von Intels Itanium-Com-
piler erzeugte Assemblerroutinen ein und optimiert sie als Ganzes, ordnet die enthaltenen In-