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

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.