# Mapping Processing Elements of Custom Virtual CGRAs onto Reconfigurable Partitions
## 3 Materials and Methods
### Finding Relocation Compatible Regions  
The first step in finding appropriate regions for reconfigurable partitions is determining resource requirements. If all possible variations of reconfigurable modules are known in advance, the number of primitives of each type should be determined as a superposition of variants' resource utilization, estimated during logical synthesis, with an additional margin. However, with the proposed separation of VCGRA structure and module functionality development, modules' functionality might be unknown at that stage. In that case, several generic overlay implementations with PBlocks using different configuration of resources can be prepared beforehand and the most appropriate variant can be selected once actual module requirements are determined. Considering that relocatable partitions operate on entire columns within the scope of a single clock region, resource requirements based on  
Figure 7: VCGRA with relocatable partitions—front-end mapping design flow overview. primitives are converted to a minimal number of columns of different types that need to be included within PBlocks. The state-of-the-art solutions [36; 45] can identify homogeneous regions with specified amount of reconfigurable resources. However, additional conditions need to be satisfied for regions to support module relocations:  
* Regions with compatible column types but opposite alignment must be differentiated;
* Partition borders cannot be placed between inseparable adjacent interconnection columns;
* Feasibility of isolation fence insertion and anchoring point placement needs to be checked. The proposed search procedure addresses these issues. The approach obtains resource distribution information directly from Xilinx Vivado software (using get_tiles and get_property queries with filters) and performs column pattern checks in individual clock regions. Multiple non-overlapping regions of different constructions are considered because the number of identical regions can be smaller than the required PE array size. The procedure comprises the following steps:  
1. Define partition candidate search parameters: * Minimal number of columns with given resource type (DPSs, BRAMs, LUTs etc.) --user provided or calculated from primitive-based resource utilization estimation. Note that certain resources are contained within more than one column type; * Maximum column width of partitions; * Anchoring points position (left/right/either/both sides of PBlock); * Overlapping pattern reduction preferences (see steps 10-12); * Optional prohibited regions, excluded from PBlock search space. 2. Select target platform. 3. Obtain clock regions information for the target. Start search for a single region. 4. Identify indices of columns where resources of certain types occur and store them in temporary lists. 5. Reduce search space based on availability of BRAMs and DSPs. * BRAMs and DSPs instances in FPGA fabric are quite rare. If several columns of BRAM or DSP types are required, the search can be limited to few locations where such columns occur within acceptable range. 6. Identify PBlock candidates--subsectors of search space with required resources. * Iterative checks on regions of width (w) varying from minimum (sum of required columns of each type) to maximum allowed column span are performed on lists of column indices (Figure 8); * Starting from column with the lowest index \(i_{0}=i_{min}\) the floorplanner checks if enough columns of each type reside between \(i_{0}\) and \(i_{0}+w\); * Incrementations of start index (i) and width (w) take interconnection block distribution into consideration--start and end columns of checked regions are always left- and right-aligned, respectively. 7. Check feasibility of isolation fence insertion and anchoring buffer placement.