# Mapping Processing Elements of Custom Virtual CGRAs onto Reconfigurable Partitions
## 3 Materials and Methods
### Design Flow  
Imposing the aforementioned assumptions and restrictions made it possible to develop a productivity-oriented back-end mapping methodology for Virtual CGRAs with relocatable reconfigurable partitions, compatible with off-the-shelf FPGA hardware and CAD tools. The presented solution is an updated and refined version of the methodology proposed in the earlier work [29], adapted for the specificity of virtual CGRA designs and expanded with new functionality--most notably automated floorplanner. In this approach a VCGRA system description with PE array of parametrizable size and explicitly defined reconfigurable partition instances is divided into static and reconfigurable parts that use separate design flows (Figure 6).  
Static design with user-defined MxN PE array and black-box partitions is synthesized using standard Xilinx Vivado tools. The proposed partition floorplanner searches through target FPGA for, preferably homogeneous, regions that satisfy resource requirements of the PE partitions. Then, it attempts to find optimal locations for individual partitions in a reasonably short time. The obtained floorplan is then used to implement the design using Xilinx Vivado toolset and module relocation methodology [29; 39]. The same parametric static overlay can be implemented with different floorplans using various PBlock constructions and PE array sizes or targeting different FPGA. A library of implemented reconfigurable overlays can store different designs for future use.  
Multiple functional variants of modules are developed and implemented separately, in a so-called reference partition design, using the module relocation methodology. As the relocatable modules are location independent, a single variant of placed and routed module for a given PBlock construction can be used for all instances in multiple floorplans and FPGA platforms. If a floorplan uses several types of PBlocks, one reference design of each  
Figure 6: VCGRA with relocatable partitions—back-end mapping design flow overview.  
type is required. On the basis of the application characteristics and target platform capacity, the most appropriate application-specific combination of static and reconfigurable modules can be selected during front-end application mapping (Figure 7).  
The main contribution of this study is an automated custom floorplanner for Virtual CGRAs with relocatable reconfiguration partitions. It is a TCL-based tool that expands the design flow proposed in earlier work [29], which formerly required manual floorplanning. The toolchain was developed for Xilinx FPGAs and operates as an extension for vendor provided software (executed from Vivado command prompt). However, the original floorplanning approach presented in this article could potentially be adapted to different hardware and software.  
The importance of proper floorplanning is significant, considering the fixed binding between the reconfigurable partitions and regions of the underlying FPGA. In order to maximally reduce the number of PE implementation variants used in the design, the floorplanner should attempt to assign PEs to as many identical PBlocks as possible, as module relocation can only be performed between compatible regions. Moreover, directly connected processing elements should be located in close proximity to each other in order to reduce delays and eliminate routing congestion problems.  
Finding optimal floorplan is an NP-hard problem that requires completing two tasks:  
1. Finding appropriate partition block candidates--regions in FPGA fabric with enough resources to fit required logic with minimum overhead--for each partition;
2. Selecting partition locations (PE to PBlock candidate assignments) capable of producing best routing results (short net delays, no routing congestion), optimal design density, and the lowest number of different implementations of PEs.