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.