# Mapping Processing Elements of Custom Virtual CGRAs onto Reconfigurable Partitions
## 3 Materials and Methods
### Finding Relocation Compatible Regions
* Depending on selected anchoring points position for partitions, the floorplanner checks if adjacent isolation fence columns (any type) and anchor point CLB columns are available next to selected region (Figure 8); * If anchoring buffer placement is impossible, PBlock candidate is removed from the results. 8. Identify column pattern of the region found and group with others. * If pattern already exists, regions are appended to associated list; * Otherwise, new pattern structure is created. 9. Repeat steps 4-8 for all clock regions. 10. Reduce overlapping patterns. * Shorter patterns may be entirely contained within longer ones, but they may have more occurrences;
* As overlay floorplanning might be performed before all module variants are designed, minimal size is not always desirable;
* Currently, overlapping pattern reduction supports three strategies: always select minimum size, always select maximum size, and select longer if it does not reduce number of occurrences;
* Intermediate results obtained up to this step can be reused with multiple strategies. * Eliminate PBlocks located in areas reserved for routing. * At least some part of each column must be included in static for the purpose of global routing, as it cannot feed through partitions (due to module relocation restrictions);
* For FPGAs with small number of clock regions (e.g., Artix-7 family, Kintex-7 xc7k160t) default strategy leaves a single central row of clock regions for routing. Custom strategies can be defined;
* This step could be performed at an earlier stage to reduce search space, but the proposed order allows testing multiple strategies of routing interleave placement on single search results (basing on intermediate results from step 10). * Eliminate overlapping regions. * Partition blocks not only cannot overlap but need additional spacing for at least isolation fence and anchoring buffers. Regions that violate this need to be eliminated;
* If a region overlap is identified the procedure keeps the region of the more popular pattern (or instance that occurs earlier in the clock region in the case when both regions use same resource distribution) and eliminates the other--in order to maximize number of PBlocks using the same pattern. * Export PBlock candidates, grouped by patterns and ranked by group size. * Generate parametric constraints for PE array and reference partitions. * A parametric, conditional if-clause based constraint file with placement constraints for all partition blocks is generated; only the sections of the file corresponding to PBlocks selected for the overlay are applied to further design. Figure 8: Example of iterative region search—required resource columns: BRAM, DSP, 2\(\times\) logic. If partition ports are located on right or both sides only regions (i\({}_{k}\); i\({}_{k}+w_{1}\)) and (i\({}_{k+1}\); i\({}_{k+1}+w_{0}\)) can be accepted. (Region (i\({}_{k}\); i\({}_{k}+w_{0}\)) does not satisfy resource requirements—no BRAM. Other regions can only use ports to the left as no logic for anchoring buffers is available to the right). Pattern ranking determines which overlapping regions are eliminated and what subset of patterns is used in the later stage of the floorplanning. Group size based ranking aims to minimize the number of different PBlock variants used in the design, and consequently the number of required placement and routing runs and partial bitstreams for reprogramming. However, if fully implemented relocatable modules using a particular PBlock construction are available, PBlocks of such construction requires no additional implementation. Therefore, it might be desirable to select them first. For this purpose, support of optional user-defined pattern preferences, that override group based ranking, has been introduced to the proposed floorplanner.