# Mapping Processing Elements of Custom Virtual CGRAs onto Reconfigurable Partitions
## 3 Materials and Methods
### PBlock Candidate Based Floorplanning  
The second stage of partition floorplanning consists of solving a combinatorial optimization problem of finding best possible matching. Each of the reconfigurable partitions needs to be individually assigned to one of the PBlock candidates. Considering that module relocation is only possible between compatible regions, it is desirable to use as few PBlock variants as possible, optimally one for all partitions. Starting from the pattern with the most occurrences, if the number of PBlock candidates is greater than or equal to the number of PEs in the overlay, no other PBlock variants are used. Otherwise, PBlock candidates that use pattern with the next largest number of occurrences are added until the condition is fulfilled. PBlocks with different constructions use their individual sets of placement and routing results for all reconfigurable modules in the later implementation stages. Nevertheless, apart from different connection cost resulting from partition ports arrangement, all variants are treated equally for the purpose of PBlock selection. Finding the optimal matching is virtually impossible due to two factors. First of all, for k reconfigurable partitions and n possible locations (PBlock candidates) there are n!/(n - k)! possible combinations of partition to location assignments. Secondly, a complete evaluation of a solution would require performing a full implementation run with post-routing timing and power analysis, which is extremely time consuming and offers only approximate heuristic-based solution. Moreover, any modifications of static functionality may influence the efficiency of individual partition floorplans. In order to make the floorplanning more feasible, a non-exhaustive search strategy with simplified solution evaluation must be used. Total wire-length (i.e., a sum of Manhattan distances between directly connected elements) is a parameter commonly used for approximate solution evaluation in the state-of-the art approaches. The total connection length affects average net delays, routing resources utilization, and probability routing congestion. Considering that no routing can feed through relocatable partitions, in the proposed floorplanner a modified distance calculation method that includes the cost of routing detours through other clock regions is used. Additionally, maximal connection length is considered. Being the worst-case scenario, it has significant impact on timing closure unless register-based buffers are used at partition ports. Therefore, the objective function used in the proposed floorplanner comprises of a weighted sum of total wire-length and maximum connection cost with adjustable weights. Since determining the total connection cost requires calculating length of all individual connections, it takes little computational effort to evaluate maximum length too. The majority of floorplanners (i.e., [40; 41; 42; 43; 44]) use simulated annealing search, which is a commonly used strategy for many combinatorial optimization problems. The approach is versatile and offers satisfactory results but requires evaluating an immense number of possible solutions, which makes it slow if objective function is time consuming. Alternatively, a decisive search based on the characteristics of the actual problem can be employed. In theory, similar arrangement of logical and physical representation of partitions can result in a good floorplan. However, the shape of a custom MxN PE array and PBlock candidate distribution rarely match. Nevertheless, some aspects of the geometry can still be exploited to guideline the floorplanning process. The proposed approach is used to determine an initial matching by performing a modified breadth-first search with direction-based penal ties and then to attempt to improve the results by performing a local 2-opt optimization between neighboring partitions. The exact procedure is outlined below:  
1.