Compiler Techniques for Coarse-Grained Reconfigurable Architecture

Abstract

Recently coarse-grained reconfigurable architectures (CGRAs) have drawn increasing attention due to their efficiency and flexibility. While many CGRAs have demonstrated impressive performance improvements, the effectiveness of CGRA platforms ultimately hinges on the compiler and the architecture customization.

Existing CGRA compilers do not model the details of the CGRA, and thus they are i) unable to map applications, even though a mapping exists, and ii) using too many processing elements (PEs) to map an application. In this dissertation, we model several CGRA details, e.g., irregular CGRA topologies, shared resources and routing PEs in our compiler and develop base kernel mapping (BKM) algorithm, integer linear programming (ILP) formulation, and a graph drawing based approach, Split-Push Kernel Mapping (SPKM), for mapping applications onto CGRAs. BKM is the first mapping algorithm for spatial mapping. SPKM was developed to improve the performance of BKM. SPKM can map more applications than the BKM, while generating mappings which have better qualities in terms of utilized CGRA resources. Utilizing fewer resources is directly translated into increased opportunities for novel power and performance optimization techniques. SPKM is not a customized algorithm only for a specific CGRA template, and it is demonstrated by exploring various PE interconnection topologies and shared resource configurations with SPKM.

Integrating CGRAs into a System-on-a-Chip (SoC) presents many benefits as well as important challenges. One of the challenges is how to customize the architecture for the target applications efficiently and effectively without performing explicit design space exploration. In this dissertation we present a novel methodology for incremental interconnect customization of CGRAs that can suggest a new interconnection architecture which is able to maximize the performance for a given set of application kernels while minimizing the hardware cost. In our methodology, we translate the problem of interconnect customization into that of inexact graph matching, and we devised a heuristic for A* search algorithm to efficiently solve the inexact graph matching problem. Our experimental results demonstrate that our customization method can quickly find application-optimized interconnections that exhibit much higher performance on average compared to the base architecture which has mesh interconnections, with little energy and hardware increase in interconnections and muxes.