Code optimizations for digital signal processors

Abstract

In this work, algorithms are presented which cover three important compilation problems: code generation, addressing mode selection and register allocation. All three algorithms are described with the help of "partitioned boolean quadratic problems" (PBQPs). A PBQP is a kind of quadratic assignment problem, which is NP-complete in general and therefore it is hard to solve. A PBQP can be formulated as a cost function or as a PBQP-graph, which is annotated with cost vectors and cost matrices. The presented solver is able to calculate a optimal solution if the PBQP-graph is reducible with defined reduction rules. If the graph is not reducible, heuristics are used to obtain a solution. The computational complexity is linear with the number of nodes in the PBQP-graph. Therefore the solver yields a solution in short time. All presented algorithms were integrated into a compiler for a commercial DSP. Typical DSP applications were used to compare the algorithms with existing methods. The results have shown that the PBQP method achieved significant improvements for all three optimization problems.

In dieser Dissertation werden Algorithmen vorgestellt, die drei wesentliche Problemstellungen im Übersetzerbau abdecken: Code-Generierung, Auswahl von Addressierungsmodi und Register-Allokation. Alle drei Algorithmen werden mit Hilfe von "Partitionierten Boolschen Quadratischen Problemen" (PBQP) beschrieben. Ein PBQP ist eine Art von quadratischem Zuordnungsproblem, das im Allgemeinen NP-vollständig ist und daher sehr schwierig zu lösen ist. Die Darstellung eines PBQP erfolgt als Kostenfunktion oder als PBQP-Graph, der mit Kostenvektoren und Kostenmatrizen annotiert ist. Es wird ein Lösungsverfahren präsentiert, das eine optimale Lösung berechnen kann, sofern der PBQP-Graph mit Hilfe von definierten Reduktionsregeln reduzierbar ist. Falls der Graph nicht reduzierbar ist, muss auf eine Heuristik zurückgegriffen werden. Da der Berechnungsaufwand nur linear mit der Anzahl der Knoten steigt, liefert der Lösungsalgorithmus meist sehr schnell ein Ergebnis. Alle vorgestellen Algorithmen wurden in einen Übersetzer für einen kommerziellen DSP integriert. Anhand von typischen DSP Applikationen wurden sie mit existierenden Methoden verglichen. Dabei zeigte sich, dass durch die Verwendung des PBQP-Lösungsansatzes erhebliche Verbesserungen in allen drei Optimierungsbereichen erzielt wurden.