Direct Mapping algorithm

View the Project on GitHub ignacioarnaldo/floorplanning

Representation

We introduce a novel representation suitable for fixed-outline floorplanning problems that allows a direct mapping of the individuals into configurations of the architecture. The example below shows a 2-layer architecture composed of 3 cores (C1,C2,C3) and 3 memories (M1,M2,M3). Each component of the architecture is characterized with a coordinate and a boolean flag. The coordinate determines the location of the left-bottom corner of the element while the flag indicates whether or not the given element is rotated. Note that a component can occupy several cells. With this representation, the decoding of the solutions is direct and does not require a placement heuristic.
ALFA

Multi-Objective Search

The released thermal-aware floorplanner is based on Non-Dominated Sorting Genetic Algorithm-II, a well-known Multi-Objective Evolutionary Algorithm. Candidate solutions are evaluated according to the three following objectives:

  1. The number of topological constraints violated (partial overlapping between different blocks and components partly out of the borders of the chip).
  2. The wire length approximated with the sum of the Manhattan distances between interconnected blocks.
  3. The temperature of the chip.

Crossover

The crossover operator is based on a Single-Point crossover, in which two children (Child1 and Child2) are obtained from the selected parents Parent1 and Parent2:

  1. We randomly select a point in [1..size], where size is the number of components of the architecture.
  2. Then, the components Ci of Parent1 and Parent2 such that point≥i are copied into Child1 and Child2 respectively.
  3. Finally, the locations of the components Cj such that j ≥ point of Parent1 have to be transmitted to Child2 while Child1 must inherite from Parent2. If any of these components overlaps with an already placed block, then such component is assigned the coordinate and rotation flag of the other parent. If none of these two options leads to a feasible configuration, then the block is relocated according to a First Fit strategy.
    4. ALFA

    Mutation

    The mutation of the solutions is performed in three ways, each with the same probability.

    1. Swapping the position of two elements of the chromosome, resulting in a change of the placement of the two involved components.
    2. Rotation of a component.
    3. Randomly moving a component one cell in one of the following directions: up, down, left, right, forward, and backwards.
    ALFA