Compiling parallel applications to coarse-grained reconfigurable architectures

Reconfigurable computing has been an active field of research for the past two decades. Coarse-Grained Reconfigurable Architectures (CGRAs) are gaining interest for embedded systems and multimedia applications, which demand a flexible but highly efficient platform. A CGRA comprises a network of simple programmable processing elements (PEs). CG RAs exploit the inherent parallelism and repetitive computations found in these applications and can adapt themselves to diverse computations by dynamically changing configurations. Although CGRAs have the potential to exploit both hardware like efficiency and software like extensibility, the absence of proper compilation approaches is an obstacle to their widespread use. -- In this thesis a novel approach for compiling parallel applications to a target CGRA will be presented. The application will be written in HARPO/L, a parallel object oriented language suitable for hardware. HARPO/L is first compiled to a Data Flow Graph (DFG) representation. The remaining compilation steps are a combination of three tasks: scheduling, placement and routing. For compiling cyclic portions of the application, we have adapted a modulo scheduling algorithm: modulo scheduling with integrated register spilling, which incorporates register spilling with instruction scheduling. For scheduling, the nodes of the DFG are ordered using the hypernode reduction modulo scheduling (HRMS) method. The placement and routing is done using the neighborhood relations of the PEs