Scheduling on CGRAs with Heterogenous PEs and Sparse Interconnect

The technical advances in the (micro-)computer industry during the last 20 years have lead to a broad distribution and need for mobile and stationary computer systems. The ever rising demand for more features and power of the devices had been satisfied by the exponential growth of integration density. The growth described by Moore’s law is about to reach physical limits. The structure size is already in the range of a few layers of atoms and the clock frequencies stagnated for more than 5 years. Another dimension of demands can be seen looking at source compression. Better and better compression algorithms for video and audio shall suit the need for permanent media consumption. For efficient coding and decoding, especially on mobile devices, specifically tailored accelerators have to be used. These requirements suggest the development of dynamically adaptable accelerators. A promising realization are Coarse Grained Reconfigurable Architectures (CGRAs). They are composed of a number of Processing Elements (PEs) that communicate with each other and perform simple arithmetic operations. A central task when mapping applications onto a CGRA is the timing of each operation on the individual arithmetic units. This is called scheduling. In high-level synthesis data usually resides in registers right after the operation implementation and interconnect is generated as required. In contrast to this CGRAs may store data in distinct Register Files (RFs) and have sparse interconnect between PEs and differing operational capabilities inside them. This introduces additional constraints which increase the difficulty of scheduling. This thesis describes some scheduling algorithms that handle these additional constraints and evaluates them in different application scenarios. The evaluation is done in a simulator for the CGRA. Special focus is put on the runtime of the scheduling algorithm and the mapped applications, because it is intended to be used in online synthesis and the ultimate goal is to speed up general purpose applications.

Die technischen Fortschritte der (Mikro-)Computerindustrie in den letzten 20 Jahren haben zu einer enormen Verbreitung und Nachfrage an mobilen und stationären Rechnersystemen geführt. Der stetig wachsende Anspruch an die Funktionen und die Leistung der Geräte konnte lange durch das exponentielle Wachstum der Integrationsdichte befriedigt werden. Das durch das Moor’sche Gesetz beschriebene Wachstum gerät jedoch an physikalische Grenzen. Die Strukturbreite befindet sich bereits in Bereichen von wenigen Atomlagen und die erreichbaren Taktfrequenzen stagnieren seit mehr als 5 Jahren. Eine andere Dimension der Ansprüche zeigt die Entwicklung bei der Quellenkodierung. Immer bessere Kompressionsverfahren für Video- und Audiomaterial sollen dem Bedarf an ständigem Medienkonsum gerecht werden. Für die effiziente Kodierung und Dekodierung insbesondere auf mobilen Geräten müssen spezialisierte Hardware-Beschleuniger eingesetzt werden. Diese Anforderungen legen die Entwicklung dynamisch anpassbarer Rechenbeschleuniger nahe. Eine vielversprechende Umsetzung solcher Beschleuniger sind Coarse Grained Reconfigurable Architectures (CGRAs). Sie bestehen aus einer Anzahl an Processing Elements (PEs) die untereinander verbunden sind und einfache arithmetische Operationen ausführen können. Eine zentrale Aufgabe bei der Abbildung von Programmen auf das CGRA ist die zeitliche Planung der Befehle auf den verschiedenen Recheneinheiten. Dies wird als Aufgabenoder Ablaufplanung (engl. Scheduling) bezeichnet. Im Vergleich zum aus der High-Level-Synthese bekannten Problem der Abbildung, ergeben sich durch Datenlokalität, begrenzte Verbindungen zwischen den PEs und unterschiedliche Operationsspektren zusätzliche Randbedingungen, welche die Aufgabenplanung erschweren. Im Rahmen dieser Arbeit werden mehrere Abbildungsverfahren, die mit den zusätzlichen Bedingungen umgehen können, beschrieben und in verschiedenen Anwendungsszenarien evaluiert. Die Evaluation erfolgt in einem Simulator. Dabei wird der Laufzeit des Abbildungsverfahrens und der abgebildeten Anwendung besondere Aufmerksamkeit gewidmet.