# Mapping Processing Elements of Custom Virtual CGRAs onto Reconfigurable Partitions
## 3 Materials and Methods
### Overlay Architecture Assumptions  
In theory, any CGRA can be implemented in the form of an overlay atop sufficiently powerful FPGA, but due to the characteristics of the underlying hardware, virtual implementations of some architectures might be far less efficient than others. In addition, the diversity of CGRAs causes great differences in both front-end and back-end mapping tasks, hence establishing universal techniques compatible with all architectures is impossible. The mapping methodology presented in this study is relatively versatile, it allows using various architectures based on the most popular solutions, and it proposes reconfigurable partition usage that can maximize its impact on the VCGRA operation. Nevertheless, it is based on certain assumptions and restrictions regarding overlay architecture (presented further in this section). At a high abstraction level, CGRA systems can be described as arrays of coarse-grained processing elements connected to host processors, memory, and peripheries (Figure 2). Depending on the architecture, CPU might be used only for configuration or during system operation as control unit or main processing platform (with CGRA being an auxiliary accelerator). In the case of VCGRA, CPUs embedded in FPGAs--in the form of either soft cores (e.g., Microblaze, NIOS) or SoC hardware (e.g., ARM core in Zynq)--can be used instead of external processors. Additional virtual hardware, including reconfigurable fine-grained logic, might also be implemented in the FPGA alongside the PE array. For the purpose of the proposed mapping methodology, only the PE array is considered. Other components may either be distributed across the FPGA as a part of global static design or assigned to certain locations. In the latter scenario, occupied regions need to be defined before partition floorplanning to eliminate them from the allowed search space. Figure 1: Simplified schematic of resource distribution in Xilinx 7-Series devices. The FPGA fabric is divided into lock regions (X0Y0 to X1Y2), interconnection blocks are located to either side of logic resources (CLB, BRAM, DSP). Dashed lines indicate repetitions of arbitrarily selected column pattern across clock regions. Due to relatively large size of minimal independently reconfigurable fragment of FPGA fabric, partial reconfiguration is suitable for significant functional changes in processing elements rather than connection switching. At the same time, using a small number of large partitions limits reconfiguration time reduction, depriving the approach of its greatest advantage. In order to fully exploit partial reconfiguration, partitions should be used as core components for a large number of PEs. It needs to be stressed that the abstract overlay structure does not need to match the actual physical partitioning (Figure 3). Static components of processing elements can be excluded from reconfigurable partitions in order to reduce their size, hence decreasing reprogramming time. Moreover, virtual switches of interconnection network corresponding to individual PEs, but regarded as separate entities at the overlay level, can be included within the scope of reconfigurable partitions to reduce logic utilization overhead. Due to restrictions of the PR mechanism, the reconfigurable modules must be instantiated at the top level of design hierarchy. As a result, such solutions require non-intuitive architecture description. Therefore, direct PE-to-partition binding might be more convenient. Even though proposed model supports multitude of interconnected network structures and allows setting-register-based run-time switching, some solutions are better suited for use with the proposed approach than others. Mesh-based patterns can be effectively used with a large number of elements. Direct connections between a small number of neighboring partitions simplifies routing in the FPGA, which can reduce net delays and probability of congestion problems. Moreover, 2-D mesh is the most popular connection pattern in both virtual and physical CGRAs [16; 19].