Optimal Code Generation for Explicitly Parallel Processors

Embedded system designers today are faced with computational workloads that have been state-of-the-art in the supercomputing domain not long ago. However, normalized to the same technology, a 2 - 3x speedup with traditional techniques very roughly requires about an increase of 80x in area and, maybe even more important, about 12x in power consumption - a cost too high to bear for most pervasive mobile applications. A popular approach among embedded systems designers are VLIW architectures employing a large number of parallel datapaths and functional units as well as application specific instruction set extensions that are taylored to a particular application. Those systems rely on highly optimizing compilers that apply aggressive code transformations in order to acquire sufficient amounts of parallelism. However, ILP-oriented optimizations impose complex trade-offs that often cannot be accomplished by traditional heuristic approaches. Additionally, application- specific architectural restrictions and asymmetries challenge the development of compilers in several ways. First, the large number of application-specific architectural variants imposes a major engineering problem that is hard to cope with using traditional compiler backends. Second, heuristic techniques often fail to effectively exploit those architectural features, thus resulting in inefficient code. Techniques based on combinatorial optimization such as integer linear programming have the potential to overcome those deficiencies. Mathematical formulations allow for combined optimization of several subproblems and are capable to formulate complex architectural constraints that can be automatically derived from abstract machine descriptions. However, previously proposed approaches have achieved little relevance in practice. The main reason is that several arising subproblems are known to be NP complete in general and naive formulations inevitably lead to unacceptable compile time. The aim of this project is to develop new algorithms and mathematical formulations that maintain the advantages of integer linear programming based code generation techniques while remaining computational feasible for real- world programs. This includes the application of well-known techniques from the operations research domain to decrease the required solver time such as cutting plane algorithms, column generation techniques, or Lagrangian relaxation. As some of the subproblems are known to be computationally hard for real-world instances, we want to use the developed models also to learn when and why established heuristics fail, and to develop efficient approximation algorithms and near-optimal techniques that remain computationally feasible even for large problems. Our focus is on phase ordering issues among scheduling and register allocation, integrated scheduling of cyclic regions (software pipelining), and support for irregular architectural constraints and asymmetric datapaths. Instead of fully integrated techniques, we propose a novel compilation scheme that decomposes register allocation into several subtasks that can be solved separately. This approach allows to keep the scheduling formulation comparatively small by maintaining only simple additional invariants.

The focus of this project was on research for optimal and near optimal code generation for explicitly parallel processors. Explicitly parallel processors can execute more than one instruction every cycle, but the programmer (or the compiler) has to explicitly specify which instructions are independent from each other and can be executed in parallel in the same cycle. These processors are mostly used in embedded applications like smart phones and often have hardware constraints like clustered functional units and register files, predicated execution or rotating register files. Code generation is the final machine dependent part of a compiler and contains passes like instruction selection, register allocation, instruction scheduling, software pipelining, if-conversion and cluster assignment. Finding optimal solutions for these passes is often computationally intractable. Furthermore, these passes are usually executed independently from each other resulting in non optimal code. The results of this project were new heuristic and exact methods for optimal and near optimal integrated code generation. Heuristic methods give nearly as good results as optimal methods and are fast enough to be incorporated in production compilers.