# Mapping Processing Elements of Custom Virtual CGRAs onto Reconfigurable Partitions
## 3 Materials and Methods
### PBlock Candidate Based Floorplanning
Select minimal number of PBlock patterns (as described earlier), identify all PBlock candidates of these patterns, and set them as available for matching. 2. Find the center of PE array and center of mass of PBlock candidate distribution in the FPGA fabric. Start mapping from the center and search outwards. * Setting search tree root at the center of PE array reduces the depth of the search; * Starting from the center helps to preserve consistency between PE array and the floorplan. 3. Obtain the first set of PEs located closest to the center (same distance in logical network). 4. For each PE, generate hypothetical pairs with all available PBlock candidates. * Due to the outward search direction, the number of PEs considered in each iteration grows linearly, but as the number of available PEs decreases at the same rate, the total number of combinations within a single iteration is manageable. 5. Calculate cost of each match based on location (distance, direction) of each candidate. * The cost is calculated as the weighted sum of Euclidean distance from the center and Manhattan distance from the directly connected predecessor (if such exists) with added direction-based penalties; * Physical location is considered directionally consistent with logical structure if the X and Y components of position in relation to the reference in both PE array and FPGA fabric are not of the opposite sign; * A moderate penalty is applied for locations with inconsistent direction in relation to either connected predecessor or the center; * A severe penalty is applied if a PE, located in a particular direction from the center, that has s successors (PEs located outwards, considered in later iterations) further in the consistent direction, is paired with a location that has p < s available PBlock candidates that fulfill the direction consistency; * The penalties help to preserve consistency between PE array and the floorplan and prevent the otherwise greedy matching from exhausting all candidates in a given direction prematurely. This way, scenarios where outermost elements might be left with no reasonable pairing options can be avoided (Figure 9). 6. Rank pairings for all PEs based on cost. Check for conflicts between best matches. In case of pairing conflicts, check costs of switching to lower ranked options and preserve the matching with the highest cost of change. Repeat until no conflicts occur. * At the beginning, all the PEs attempt pairing with their top-rated match; * If multiple PEs opt for the same location, only the element that causes the highest growth in cost if moved is preserved, others are re-assigned to lower ranked locations; * In the case of movement to an unoccupied location, estimated cost increase is the difference between lower and higher ranked results. If the next best location already has a matching, combined cost of movement to the occupied location and re-assigning the occupant is compared with movement cost to next lower ranked option, the lower value option is used; * Re-assignments can lead to new conflicts at different positions. Process is repeated until all conflicts are resolved. 7. Initial floorplanning for this PE group is finished; set selected PBlock candidates as unavailable for next matchings. 8. Obtain the next set of PEs--elements located one position outward in the array--and determine their predecessors (directly connected elements that underwent initial floorplanning). Repeat steps 4-8 for a new set, continue until all PEs are floorplaned. 9. Calculate objective function for the complete initial floorplan. Save individual partial results. 10. Starting from PE [0,0] check if swapping it with any of the neighboring PE (including diagonals) decreases objective function value, if so, accept the swap. Repeat for every node. * For a selected PE located at [x,y], feasibility of location swapping with elements at [x+0,y+1], [x+1,y-1], [x+1,y+0], [x+1,y+1] positions is checked.