Agile SMT-Based Mapping for CGRAs with Restricted Routing Networks

“Agile SMT-Based Mapping for CGRAs with Restricted Routing Networks” by Caleb Donovick, Makai Mann, Clark Barrett, and Pat Hanrahan. In Proceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig '19), (David Andrews, René Cumplido, Claudia Feregrino, and Marco Platzner, eds.), Dec. 2019. Cancun, Mexico.

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.

BibTeX entry:

@inproceedings{DMB+19,
   author = {Caleb Donovick and Makai Mann and Clark Barrett and Pat Hanrahan},
   editor = {David Andrews and Ren{\'e} Cumplido and Claudia Feregrino and
	Marco Platzner},
   title = {Agile {SMT}-Based Mapping for {CGRA}s with Restricted Routing
	Networks},
   booktitle = {Proceedings of the International Conference on
	ReConFigurable Computing and FPGAs (ReConFig '19)},
   publisher = {IEEE},
   month = dec,
   year = {2019},
   doi = {10.1109/ReConFig48160.2019.8994781},
   note = {Cancun, Mexico},
   url = {http://theory.stanford.edu/~barrett/pubs/DMB+19.pdf}
}

(This webpage was created with bibtex2web.)