# Mapping Processing Elements of Custom Virtual CGRAs onto Reconfigurable Partitions
## 2 Related Work
### Mapping Tools and Techniques  
Apart from work focused on specific VCGRA architectures, many design tools and techniques that can be used with a variety of coarse-grained overlays have been proposed recently. The majority of the work uses standard off-the-shelf FPGA flows for the back-end and concentrates on different aspects of front-end mapping. Focusing on application mapping is understandable since temporal granularity of application-specific configurations is much finer than that of overlays. Consequently, as multiple applications can be mapped and run using a single virtual architecture, the impact front-end mapping has on performance and especially development productivity is significant. CGRA-ME [21; 27] is an extremely versatile, VTR [28] inspired mapping framework for CGRA that can be used with both physical and overlay manifestations. It allows for the definition of custom architectures via an XML-based description language and supports a variety of connection patterns. The framework translates LLVM-compiled intermediate representation of a program into a data-flow graph (DFG) and maps it onto PEs of the architecture using a simulated-annealing based mapper or integer linear programming technique. Virtual architecture can then be implemented as either standard-cell or FPGA overlay using standard tool flows. The presented virtual solution uses Altera/Intel FPGAs and tools. It is mentioned that placing a physical realization of PEs in the form of a regular grid coherent with logic representation in the virtual CGRA is desired, but no methods for obtaining that goal are presented. A huge advantage of overlays is that each application can be mapped onto an individual optimized version of virtual architecture. QuickDough [6], a design framework for soft CGRA accelerators, analyses requirements of compute kernel and selects the best fitting accelerator from a library of pre-built overlays. The library can be updated upon users' requests with custom architectures based on the provided SCGRA template. The framework uses standard FPGA design flow to implement the overlays, but the authors note that due to regularity of SCGRA template architectures, other state-of-the-art techniques [12] (described further in this section) could be used to accelerate the process. Prioritizing front-end mapping without considering its influence on the back-end process can have a negative impact on VCGRA performance. Even though front-end mapping is theoretically independent from the low-level aspects of the micro-architecture, individual techniques may be applicable only for architectures with certain structures and interconnection networks or they may work well only for applications with specific communication patterns. Certain architecture features that simplify the front-end mapping can increase the complexity of the back-end process. Crossbar routing with direct connections between all PEs is an exemplary case. It is an excellent solution for Just-in-Time task scheduling, as it simplifies the overlay placement and routing problem to O(1), at the expense of the connection cost of O(\(N^{2}\)) [9]. Apart from direct changes in required routing resources, increasing complexity diminishes the chances of CAD tools finding a solution with satisfactory timing and no congestion. Increasing the efficiency of the overlay to FPGA mapping and improving the performance of the actual underlying hardware are less common subjects of research, as standard techniques and tools for logical synthesis and implementation for FPGAs are considered efficient. However, specificity of VCGRA architectures can be exploited for better results. TLUT/TCON [13; 23; 24] is a complex design flow for FPGA overlays aimed at reducing logic utilization overheads. It uses the parametrized VCGRA model with expression-based definitions of setting registers which are then implemented as tunable look-up tables (with table entries being Boolean functions of a parameter rather than ones and zeros).