Agile SMT-Based Mapping for CGRAs with Restricted Routing Networks

Abstract

Coarse-grained reconfigurable architectures (CGRAs) are becoming popular accelerators for computationally intensive tasks. CGRAs offer the reconfigurability of an FPGA, but with larger configurable blocks which provide performance closer to ASICs. CGRAs can achieve very high compute density if the routing networks are restricted; however, mapping using traditional annealing-based approaches does not perform well for such architectures. This paper uses Satisfiability Modulo Theories (SMT) solvers to rapidly map designs onto arbitrary CGRA fabrics. This approach is sound, complete, and in many cases an order of magnitude faster than state-of-the-art constraint-based mapping techniques using integer linear programming (ILP). Additionally, we propose a functional duplication strategy that decreases pressure on the routing network from high-fanout operations, leading to significant performance improvements.