Graph minor approach for application mapping on CGRAs
Authors:
- 1 December 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 285-292
Abstract
Coarse-grained reconfigurable arrays (CGRA) exhibit high performance, improved flexibility, low cost, and power efficiency for various application domains. Compute-intensive loop kernels are mapped to CGRA through modified modulo scheduling algorithms that integrate placement and routing. Most existing approaches are heavily influenced by VLIW compilation and FPGA synthesis techniques. A salient feature of these approaches is that data routing from a single source node to multiple destination nodes follow independent paths leading to resource wastage and hence inefficient schedule.We transform the CGRA mapping problem with route sharing into a graph minor problem. Our graph minor formalization provides a solid foundation for application mapping on CGRA. We provide an efficient framework based on graph mapping to solve this problem. Experimental validation shows that our approach leads to higher performance compared to state-of-the-art solutions with better resource utilization and minimal compilation time.Keywords
This publication has 12 references indexed in Scilit:
- Mapping loops onto Coarse-Grained Reconfigurable Architectures using Particle Swarm Optimization2010
- SPR2009
- Edge-centric modulo scheduling for coarse-grained reconfigurable architectures2008
- Placement-and-routing-based register allocation for coarse-grained reconfigurable arrays2008
- A Modulo Scheduling Algorithm for a Coarse-Grain Reconfigurable Array Template2007
- Modulo graph embedding2006
- Exploiting loop-level parallelism on coarse-grained reconfigurable architectures using modulo scheduling2003
- MorphoSys: an integrated reconfigurable system for data-parallel and computation-intensive applicationsIEEE Transactions on Computers, 2000
- Graph MinorsJournal of Combinatorial Theory, Series B, 1999
- Principles of Artificial Intelligence1982