# Mapping Processing Elements of Custom Virtual CGRAs onto Reconfigurable Partitions
## 2 Related Work
### Partition Floorplanning  
The majority of state-of-the-art FPGA partition floorplanning solutions (i.e., [40; 41; 42; 43; 44]) focus on optimizing area coverage (best utilization of available area, with minimal overhead) and minimizing total wire length (Manhattan distance between connected components). Typically, optimization is based on simulated annealing. However, some solutions use Mixed-Integer Linear Programming, which is claimed to be more effective for large partitions with a time limited search. Contrary to the previously used techniques, all contemporary solutions must consider FPGAs heterogeneity. Another key restriction for floorplanning reconfigurable modules in Xilinx devices, acknowledged in the aforementioned work, is regularity of partition geometry (due to the configuration memory construction, only rectangular reconfigurable regions aligned to clock region borders are supported). Module relocation entails even more restrictions as it is only possible if original and target regions use identical resource distribution. Given the heterogeneity of modern FPGAs, partition relocatability is only obtainable at very specific locations in the fabric. Consequently, the characteristics of the floorplanning problem are completely different than for designs without module relocation. Instead of being an area coverage problem, floorplanning becomes a combination of common pattern search (finding regions with identical resource distribution) and combinatorial optimization (selecting which region should be occupied by each PE). [PERSON] et al. [45] proposed a technique that can be used to identify homogenous reconfigurable regions in modern heterogeneous FPGAs for the purpose of partition relocation. The approach exploits column-based regularity of resource distribution in Xilinx FPGAs. The technique identifies column patterns that satisfy resource requirements for partition, eliminates non-minimal patterns, and finds all occurrences of regions that use such a distribution in a target chip. The authors present search results for Xilinx Virtex (xc5 vfx70, xc6 vlx240, xc7 vx690) devices but do not test the partition relocation between such regions. Although the general ideas are relevant and constitute a solid foundation for the work presented in this study, several issues important for actual implementation of relocatable partitions were not addressed. Regions might be misidentified as compatible since no differentiation between resource columns of opposite alignment is made. Inseparability of adjacent interconnection tiles is also not respected, which may cause back-to-back violations in Xilinx 7-Series [46]. Finally, no isolation feasibility checks are performed. AutoReloc [36] is a bitstream relocation design-flow enhancing capabilities of the now obsolete Xilinx PlanAhead software. It uses a two-phase partition floorplanning algorithm. The initial stage is a column pattern choice. Contrary to [45], it uses a different search strategy and considers left- and right-alignment of resource tiles and interconnection columns inseparable. The proposed search method always finds only minimal patterns, which is usually an advantage, but, as explained later in this article, is not always desirable. What is more, the algorithm omits non-reconfigurable regions, but can place partitions directly adjacent to them, which can make partition-to-static routing generated elsewhere impossible to recreate, unless additional restrictions are applied. The technique could be adapted to use with module isolation, required for routing feed-through prevention, but does not support it in the original form. From all patterns found with at least a designer-specified number of occurrences, one is selected based on arbitrary but reasonable criteria. Once a pattern is chosen, simulated annealing is performed to find optimal selection of available blocks.