Universität zu Köln

Mallach, Sven ORCID: 0000-0001-5335-0678 (2015). Exact Integer Programming Approaches to Sequential Instruction Scheduling and Offset Assignment. PhD thesis, Universität zu Köln.

Preview

PDF diss_mallach_kups.pdf - Published Version Download (2MB)

Abstract

The dissertation at hand presents the main concepts and results derived when studying the optimal solution of two NP-hard compiler optimization problems, namely instruction scheduling and offset assignment, by means of integer programming. It is the outcome of several years of research as an assistant at Michael Jünger's computer science chair in Cologne, with the particular aim to apply exact mathematical optimization techniques to real-world problems arising in the domain of technical computer science. The two problems studied are rather unrelated apart from the fact that they both take place during the machine code generation phase of a compiler and deal with the handling of limited resources. Instruction scheduling is about the assignment of issue clock cycles to instructions in the presence of precedence, latency, and resource constraints such that the total time needed to execute all the instructions is minimized. Offset assignment deals with storage layouts of program variables and the efficient use of address registers for accesses to these variables. The objective is to employ specialized instructions in order to minimize the overhead caused by address computations. While instruction scheduling needs to be carried out by almost every present compiler irrespective of the processor architecture, the offset assignment problem occurs mainly in compilers for highly specialized processor designs. Instruction scheduling is a well-studied field where several exact and heuristic approaches have been developed and experimentally evaluated in the past. In this thesis, we concentrate on the basic-block instruction scheduling problem for single-issue processors. Basic blocks are program fragments with no side-entrances and -exits, i.e., every instruction of a basic block needs to be executed before the control flow may leave it and enter another basic block. Single-issue processors are capable of starting the execution of exactly one instruction per clock cycle. A number of techniques to preprocess instances of the basic-block instruction scheduling problem were proposed in the literature and are, with emphasis on the more recent ones that arose since the year 2000, thoroughly reviewed in this thesis. They finally led to a constraint programming approach in 2006 that was shown to solve about 350,000 instances to optimality and where some of these instances comprised up to about 2,500 instructions. The last attempt to tackle the problem using integer programming however dates to a time prior to the publication of the latest preprocessing advances. While being successful on a set of instances that impose very restrictive latency constraints, it was shown to be unable to solve hundreds of instances from the aforementioned benchmark set that comprises also large and varying latencies. In addition, the previous integer programming models were almost all based on so-called time-indexed formulations where decision variables model an explicit assignment of instructions to clock cycles. In this thesis, a completely different and novel approach is taken based on the linear ordering problem, a well-studied combinatorial optimization problem. The new models lead to alternative characterizations of the feasible solutions to the basic-block instruction scheduling problem. These facilitate the employment of advanced integer programming methodologies, in particular the design of branch-and-cut algorithms that can handle larger instances. The formulations are further extended by additional inequalities that can be used as cutting planes. Combined with the preprocessing routines that are partially extended and improved as well, the respective solver implementation eventually turned out to be competitive to the constraint programming method. Reaching this point has taken some years and this thesis presents not only the derived models but also several ideas and byproducts that arose in the meantime, and that can help and inspire researchers even if they aim at the application of different solution methodologies. The starting point regarding the offset assignment problem was a different one because especially exact solution approaches were rather rare prior to the models presented in this thesis. The offset assignment problem arose in the 1990s and is considered in several variants that are of theoretical and practical interest. In the simplest one, a processor is assumed to provide only a single address register and only very restricted possibilities to avoid address computation overhead. However, even this simplest variant, that may serve as a building block for the more complex ones, is already NP-hard and has been studied mainly from a heuristic point of view. The few existing exact solution approaches were not capable to solve moderately sized instances so that the quality of heuristic solutions relative to the optimum was hardly known at all. Again, the inspection of the combinatorial structure of the various problem variants turned out to be the key for designing branch-and-cut implementations that can profit from knowledge about related combinatorial optimization problems. The implementation targeting the simple problem variant was the first capable to optimally solve the majority of about 3,000 instances collected in a standard benchmark set. The method could then be further generalized in two steps. First, in a collaboration with Roberto Castañeda Lozano, additional techniques could be incorporated into the approach in order to handle multiple address registers. Fortunately, the methods could then even be further extended to as well deal with more flexible addressing capabilities. In this way, the thesis at hand does not only answer the question how large the address computation overhead can be when using heuristics, but as well presents first results that allow to analyze the impact of the mentioned increased addressing capabilities on the runtime performance and size of real-world programs.

Item Type:	Thesis (PhD thesis)
Translated abstract:	Abstract Language Die vorliegende Dissertation berichtet über die wesentlichen Konzepte und Resultate wissenschaftlicher Studien zur exakten Lösung zweier NP-schwerer Compiler- Optimierungsprobleme, Instruction Scheduling und Offset Assignment, mittels ganzzahliger linearer Programmierung. Sie ist das Ergebnis mehrjähriger Forschung als wissenschaftlicher Mitarbeiter am Lehrstuhl von Michael Jünger in Köln, mit einer besonderen Ausrichtung darauf, mathematische Optimierungsverfahren auf praktische Problemstellungen aus dem Bereich der technischen Informatik anzuwenden. Die beiden behandelten Probleme sind im Wesentlichen völlig unabhängig voneinander, beschäftigen sich aber beide mit der Zuteilung von beschränkt zur Verfügung stehenden Ressourcen und treten während der Erzeugung von Maschinencode innerhalb eines Compilers auf. Instruction Scheduling behandelt die Zuteilung von Taktzyklen zu Instruktionen mit dem Ziel, die Gesamtausführungszeit aller Instruktionen zu minimieren. Diese Zuteilung muss Datenabhängigkeiten, Latenzbedingungen und Ressourcenbeschränkungen berücksichtigen. Beim Offset Assignment geht es um Speicherlayouts von Programmvariablen und den effizienten Einsatz von Adressregistern für Zugriffe auf diese Variablen, so dass der erforderliche Zusatzaufwand in Form von expliziten Adressberechnungen minimiert wird. Im Gegensatz zum Instruction Scheduling, das Bestandteil nahezu jedes Compilers ist, tritt das Offset Assignment Problem hauptsächlich bei Compilern für spezialisierte Prozessorarchitekturen auf. Instruction Scheduling ist ein bereits sehr intensiv studiertes Problem, zu dem diverse exakte und heuristische Verfahren entworfen und experimentell analysiert wurden. Diese Arbeit konzentriert sich auf das Basic-Block Instruction Scheduling Problem für Single-Issue Prozessoren. Basic Blocks sind Programmfragmente mit einem einzigen Einstiegs- und Ausstiegspunkt. Es müssen daher alle Instruktionen eines Basic Blocks ausgeführt werden, bevor der Kontrollfluss zu einem anderen Basic Block übergeht. Single-Issue Prozessoren sind in der Lage, pro Taktzyklus mit der Ausführung exakt einer neuen Instruktion zu beginnen. Eine Reihe von Techniken zur Vorbehandlung von Basic Block Instanzen wurden in der Literatur vorgestellt. Sie werden, mit einem Schwerpunkt auf aktuellere Verfahren seit dem Jahr 2000, in dieser Arbeit ausgiebig diskutiert, denn sie führten zu einem Constraint Programming Ansatz im Jahr 2006, der etwa 350000 Instanzen optimal lösen konnte, wobei einige dieser Instanzen bis zu 2500 Instruktionen beinhalten. Der letzte Versuch, das Problem mittels ganzzahliger Programmierung zu lösen, datiert hingegen aus einer Zeit vor Veröffentlichung der jüngsten Vorbehandlungsmethoden. Es erwies sich bei sehr restriktiven Latenzbedingungen als erfolgreich, konnte aber hunderte der soeben benannten Instanzen, die große und stärker variierende Latenzen beinhalten, nicht lösen. Des Weiteren basieren nahezu alle bisher vorgestellten Verfahren auf sogenannten zeitindizierten Formulierungen, bei denen Entscheidungsvariablen eine explizite Zuweisung von Instruktionen zu Taktzyklen modellieren. Die vorliegende Arbeit beschreibt hingegen einen vollkommen neuen Ansatz basierend auf dem Linearen Ordnungsproblem, das ein bereits sehr gut studiertes kombinatorisches Optimierungsproblem ist. Die neuen Modelle führen zu einer alternativen Charakterisierung der zulässigen Lösungen des Basic-Block Instruction Scheduling Problems. Sie ermöglichen den Einsatz von Branch-and-Cut Algorithmen, die auch größere Instanzen lösen können. Die Formulierungen werden außerdem durch zusätzliche Ungleichungen erweitert, die als Schnittebenen verwendet werden können. Kombiniert mit den Methoden zur Vorbehandlung, die zum Teil ebenfalls noch erweitert und verbessert werden, kann die entwickelte Implementierung vergleichbare Ergebnisse wie der Constraint Programming Ansatz erzielen. Dieses Ziel zu erreichen hat einige Jahre in Anspruch genommen. Die vorliegende Arbeit berichtet daher nicht nur über die entwickelten Modelle, sondern auch über diverse Ideen und Nebenprodukte, die in dieser Zeit entstanden und die inspirierend sein bzw. anderen Wissenschaftlern helfen könnten, selbst wenn sie andere Lösungsverfahren einsetzen möchten. Die Ausgangssituation bzgl. des Offset Assignment Problems war eine andere, da insbesondere exakte Verfahren vor den in dieser Arbeit vorgestellten eher rar waren. Das Offset Assignment Problem kam in den neunziger Jahren auf und wird in diversen Varianten betrachtet, die von theoretischer und praktischer Bedeutung sind. In der einfachsten Variante wird angenommen, dass ein Prozessor lediglich ein einzelnes Adressregister und sehr limitierte Möglichkeiten zur Adressierung von Programmvariablen ohne Verursachung zusätzlichen Aufwands bietet. Selbst für diese einfachste Variante, die auch als Baustein für komplexere dient, ist das Berechnen einer Optimallösung jedoch bereits NP-schwer und somit wurde das Problem im Wesentlichen im Sinne einer heuristischen Lösung studiert. Die wenigen exakten Lösungsverfahren waren nicht in der Lage, mittelgroße Instanzen zu lösen, so dass die tatsächliche Güte heuristischer Lösungen für eine lange Zeit kaum bekannt war. Auch hier zeigte sich die Untersuchung der kombinatorischen Struktur der verschiedenen Problemvarianten als Schlüsselansatz, um Branch-and-Cut Verfahren entwerfen zu können, die von bekanntem Wissen über verwandte kombinatorische Optimierungsprobleme profitieren. Die Implementierung zur Lösung der einfachsten Problemvariante war dann die erste, die die große Mehrheit von etwa 3000 Instanzen eines Standard-Benchmarks optimal lösen konnte. Im Anschluss konnten zunächst, in Zusammenarbeit mit Roberto Castañeda Lozano, zusätzliche Techniken eingebunden werden, die es dem Ansatz erlaubten, auch über den Einsatz mehrerer Adressregister zu optimieren. Erfreulicherweise konnten die Verfahren dann sogar noch weiter verallgemeinert werden, um mit flexibleren Möglichkeiten zur Adressierung von Programmvariablen umgehen zu können. Auf diese Weise beantwortet die vorliegende Arbeit nicht nur die Frage, wie groß der zusätzliche Adressierungsaufwand ist, wenn Heuristiken verwendet werden, sondern liefert auch erste Resultate, die es erlauben, die Auswirkungen flexiblerer Adressierungsmöglichkeiten auf die Laufzeit und Größe realer Anwendungen zu analysieren. German
Creators:	Creators Email ORCID ORCID Put Code Mallach, Sven mallach@informatik.uni-koeln.de orcid.org/0000-0001-5335-0678 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-60399
Date:	16 March 2015
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Natural sciences and mathematics Mathematics
Uncontrolled Keywords:	Keywords Language Instruction Scheduling, Offset Assignment, Compiler Optimization, Code Compaction, Address Code Generation, Combinatorial Optimization, Branch-and-Cut, Integer Linear Programming English
Date of oral exam:	15 January 2015
Referee:	Name Academic Title Jünger, Michael Prof. Dr. Marwedel, Peter Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/6039