Ultra-Fast CGRA Scheduling to Enable Run Time, Programmable CGRAs

Coarse-Grained Reconfigurable Arrays (CGRAs) can offer both energy-efficiency and high-throughput for embedded systems today. But, one limitation of CGRAs is the extremely long mapping time that can take many hours to complete for a typical workload. This extended mapping time, coupled with the typical use of a fixed CGRA program configuration, significantly limits potential use cases as well as hinders the ability to achieve the required performance and efficiency targets.To overcome these limitations, we propose a new, low-complexity CGRA mapping algorithm that compiles applications in milliseconds instead of hours. This is achieved by the use of key instruction placement guidelines which enable speedups of up to 800,000 $\times$ while maintaining comparable kernel performance. This result allows, for the first time, the ability to dynamically reconFigure CGRA accelerators to adapt to the scenario at hand, be it an important phase of an application, or a user-generated query or request. Overall, this compiler solution could lay the foundation for improved system throughput and efficiency.