Dynamisches Scheduling in der Hochsprachen-Compilierung für adaptive Rechner

The single-thread performance of conventional CPUs has not improved significantly due to the stagnation of the CPU frequencies since 2003. Adaptive computers, which combine a CPU with a reconfigurable hardware unit used as hardware accelerator, represent a promising, alternative compute platform. During the past 10 years, much research has been done to develop tools that enhance the usability of adaptive computers. An important goal here is the development of an adaptive compiler, which compiles hardware descriptions from common high-level languages such as C in a fully automated way. Most of the compilers developed until today use static scheduling for the generated hardware. However, for complex programs containing nested loops, irregular control flow, and arbitrary pointers, dynamic scheduling is more appropriate. This work examines the feasibility of compiling to dynamically scheduled hardware, an approach that has been the subject of only limited research efforts so far. Based on previous work we have developed the adaptive compiler COMRADE 2.0, which generates synthesizable hardware descriptions (using dynamic scheduling) from ANSI C. For this, the compiler utilizes our COMRADE Controller Micro-Architecture (COCOMA), an intermediate representation which models even complex control and memory dependences and is thus especially suitable in a compile flow that supports complex C programs. We examine the effects of parameter variations and low-level optimizations on the simulation and synthesis results. The most promising optimization technique considering the runtime is memory localization which can significantly increase the memory bandwidth available to the compiled hardware kernels. Using memory localization we have obtained hardware kernel speed-ups of up to 37x over an embedded superscalar CPU.Bedingt durch die Stagnation der CPU-Frequenzen stagniert seit 2003 auch die Single-Thread-Rechenleistung herkömmlicher CPUs. Adaptive Rechner bieten eine vielversprechende, alternative Rechenarchitektur, indem sie die CPU um eine rekonfigurierbare Einheit, die als Hardware-Beschleuniger verwendet wird, erweitern. In den vergangenen zehn Jahren wurde viel Forschung in Entwurfswerkzeuge investiert, die eine praktikablere Verwendung adaptiver Rechner ermöglichen sollen. Ein wesentliches Ziel ist dabei die Entwicklung eines adaptiven Compilers, der aus einer allgemein verwendeten Hochsprache wie C vollautomatisch Hardwarebeschreibungen erzeugen kann. Die meisten der bisher entwickelten Compiler setzen in der erzeugten Hardware statisches Scheduling ein. Für komplexere Programme mit verschachtelten Schleifen, irregulärem Kontrollfluss und beliebigen Zeigerzugriffen ist jedoch dynamisches Scheduling besser geeignet. Diese Arbeit untersucht die praktische Machbarkeit des dynamischen Schedulings, zu dem es bislang kaum Untersuchungen im Kontext adaptiver Rechner gibt. Auf der Grundlage bestehender Vorarbeiten haben wir den Compiler COMRADE 2.0 entwickelt, der aus ANSI C vollautomatisch synthetisierbare Hardwarebeschreibungen generieren kann, die dynamisches Scheduling verwenden. Eine zentrale Rolle spielt dabei die von uns entwickelte Zwischendarstellung COMRADE Controller Micro-Architecture (COCOMA), die auch komplexere Kontroll- und Speicherabhängigkeiten korrekt modelliert und daher besonders für die Compilierung komplexerer C-Programme geeignet ist. Wir untersuchen die Auswirkungen von Parameteränderungen und Low-Level-Optimierungen auf die Simulations- und Syntheseergebnisse. Als sehr vielversprechend hat sich die Speicherlokalisierung herausgestellt, die eine wesentlich höhere Speicherbandbreite bei geringer Latenz bietet. Wir messen hier Beschleunigungen eines Hardware-Kernels gegenüber einer eingebetteten, superskalaren CPU von bis zu 37-fach