A layout is described by the positions of the modules, the chosen
implementation for the flexible modules and the routes of the interconnection
nets on the layout-surface between the cells.
Such a complex phenotype can not directly be represented by a gene-string of
elementary data-types.
A feasible way to characterize the placement of the modules is
a binary slicing tree.
This tree is the problem specific genotype encoding for the layout optimization (cf. fig. 2).
Figure 2: The genotype representation
The structure of the tree fixes the relative placement of the single blocks (modules) which are represented by its leaves. Each inner node represents a meta-block, which defines the arrangement for the set of blocks characterized by the leaves of the corresponding sub-tree and information about the routing inside this partial layout. All possible implementations for flexible blocks are taken into account by storing shape-functions for all nodes in the tree so that a single individual represents different layouts, if some blocks are flexible. When combining two blocks to a meta-block, the arrangement and the rotation of the composed blocks are fixed. Hence, the shape-functions of both blocks can be added which results in a shape-function for the meta-block. The number of implementations for the meta-blocks in the higher levels of the tree does not grow exponentially with their height in the tree because there are redundant implementations [7]. For the example shown in figure 3, two flexible blocks with three and two implementations are positioned upon. The shape-function for the resulting meta-block has only two different (non redundant) implementations. An upper bound for the routing space inside the meta-block is computed and added to its shape-function.
Figure 3: The combination of two flexible blocks to a meta-block and the addition of routing space