Browsing by Author "CHEN, Liang"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Graph Minor Approach for Application Mapping on CGRAs
    (2013-06-18) CHEN, Liang; MITRA, Tulia
    Coarse-grained reconfigurable arrays (CGRAs) exhibit high performance, improved flexibility, low cost, and power efficiency for various application domains. Computeintensive loop kernels are mapped onto CGRAs through modified modulo scheduling algorithms that integrate placement and routing. We formalize the CGRA mapping problem as a graph minor containment problem. We essentially test if the data flow graph representing the loop kernel is a minor of the modulo routing resource graph representing the CGRAs resources and their interconnects. We design an exact graph minor testing approach that exploits the unique properties of both the data flow graph and the routing resource graph to significantly prune the search space. We introduce additional heuristic strategies that drastically improve the compilation time while still generating optimal or near-optimal mapping solutions. Experimental evaluation confirms the efficiency of our approach.