Generic Connectivity-Based CGRA Mapping via Integer Linear Programming
Authors:
- 1 April 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 65-73
Abstract
Coarse-grained reconfigurable architectures (CGRAs) are programmable logic devices with large coarsegrained ALU-like logic blocks, and multi-bit datapath-style routing. CGRAs often have relatively restricted data routing networks, so they attract CAD mapping tools that use exact methods, such as Integer Linear Programming (ILP). However, tools that target general architectures must use large constraint systems to fully describe an architecture's flexibility, resulting in lengthy run-times. In this paper, we propose to derive connectivity information from an otherwise generic device model, and use this to create simpler ILPs, which we combine in an iterative schedule and retain most of the exactness of a fully-generic ILP approach. This new approach has a speed-up geometric mean of 5.88x when considering benchmarks that do not hita time-limit of 7.5 hours on the fully-generic ILP, and 37.6x otherwise. This was measured using the set of benchmarks used to originally evaluate the fully-generic approach and several more benchmarks representing computation tasks, over three different CGRA architectures. All run-times of the new approach are less than 20 minutes, with 90th percentile time of 410 seconds. The proposed mapping techniques are integrated into, and evaluated using the open-source CGRA-ME architecture modelling and exploration framework.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- A Scalable Design Approach to Efficiently Map Applications on CGRAs2016
- Reconfigurable Computing ArchitecturesProceedings of the IEEE, 2015
- Graph Minor Approach for Application Mapping on CGRAsACM Transactions on Reconfigurable Technology and Systems, 2014
- REGIMap2013
- EPIMap2012
- SciNet: Lessons Learned from Building a Power-efficient Top-20 System and Data CentreJournal of Physics: Conference Series, 2010
- SPR2009
- Edge-centric modulo scheduling for coarse-grained reconfigurable architectures2008
- ADRES: An Architecture with Tightly Coupled VLIW Processor and Coarse-Grained Reconfigurable Matrix2003
- The directed subgraph homeomorphism problemTheoretical Computer Science, 1980