# Mapping Processing Elements of Custom Virtual CGRAs onto Reconfigurable Partitions
## 2 Related Work
### Virtual Coarse-Grained Reconfigurable Architectures  
For all the benefits they offer, CGRAs have one fundamental flaw--they are not generally available. As a result, virtual implementations in the form of FPGA overlays are often used to exploit some of the advantages of CGRAs. In addition to its undoubted value in prototyping and architecture development, the overlay approach has an advantage from the programming perspective, even if it does not provide the same performance nor energy efficiency [20].  
Multiple architectures, analysis, techniques, and tools for Virtual CGRAs have been introduced over the years [4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 21]. In spite of the lack of standardization, different motivations and approaches to virtual CGRA architecture design, common features, and solutions can be observed.  
Typically, a CGRA overlay uses a 2-D mesh of homogeneous processing elements (PEs) with NESW (north-east-south-west) connections [4; 5; 6; 7; 21]. A linear communication pattern is often used for image processing applications [8]. More complex models like crossbar [9] and multistage global interconnections [10] offer simplified front-end mapping, but high connection cost and potential congestion problems make them unusable for large networks.  
The micro-architecture of individual PEs is rarely discussed. In most cases, the VCGRA design operates on higher abstraction and implementation details and depends entirely on FPGA CAD tools responsible for back-end mapping. The few exceptions include arrays of DSP-based processor-like cores [11; 22]. Reconfigurability of the virtual architecture layer is usually obtained by using a runtime circuit switching controlled by setting registers and virtual switch blocks implemented using FPGA logic resources. However, in order to reduce resource utilization overhead, tunable LUTs and switch blocks were proposed [13; 23; 24] to utilize FPGA configuration memory for that purpose.  
In contrast to CGRAs with physical manifestation, overlay architectures can offer another layer of reconfiguration as the entire virtual architecture can be reformed. QUKU [4], a prototype FPGA-based overlay with 2-D mesh of virtual programmable elements, is a good example. On the FPGA configuration layer, each of the PEs can be configured as one of several possible variants, like a multiplier or a simple ALU. On the overlay layer, a simple instruction-like configuration is used to determine a cycle-by-cycle behavior of individual PEs (which input arguments are used, which parts of the available operation are performed in ALU, etc.). The proposed solution offers rapid overlay configuration changes, which are essential for temporal distribution of computations. However, this requires reprogramming the entire FPGA if even a single PE is replaced with a different module.  
It is worth noting that although the most overlays use homogeneous coarse PE arrays, they are often used as a component of heterogeneous systems. Most commonly, VCGRAs are used with general-purpose CPUs, not only as external hosts controllers but often in the form of soft cores implemented in FPGA [7] or processors embedded with FPGA in a SoC [6; 22]. Moreover, as the granularity is defined by the abstract programming model, fine-grained logic can be used alongside it to provide better adaptability and state machine logic handling in a so-called Mixed-Grained or Multi-Grained approach [15; 20; 25].  
A recent survey [26] comparing multiple VCGRA architectures suggests that overlays can be effectively used as general-purpose, on-demand application accelerators for FPGA-based systems. They do introduce a significant hardware performance penalty, but in the case of general-purpose acceleration, adaptation to application changes is more important. According to the study, this is where overlays really excel, with three orders of magnitude reduction in placement and routing time as well as hardware kernel context switching time.