Figure 2: The genotype (left), and the composition of a meta-block (right)
The genotype is encoded as a binary slicing tree, which defines the relative placement of the cells (fig. 2, left). It is composed in a bottom-up fashion. In each inner node two blocks (in the lowest level these are single cells) are joined to a meta-block (partial placement). In each meta-block the orientations of the combined blocks are fixed (fig. 2, right). If the blocks represent flexible macro-cells, which are cells with variable aspect ratios, different shapes are stored for the meta-block. Therefore every tree describes several possible shapes for the corresponding layout, which enormously improves the performance of the GA. While here only results for circuits with fixed cells are presented, more information and empirical data for the flexible case can be found in a former paper [15].
Figure 3: A placement (I), the routing graph (II), the width for channel [A,E]
is established by its widest region [C,D] (III), and the layout with added routing space (IV)
After the construction of the tree, the relative positions of the blocks are given and the locations of all terminals are known. Out of the tree a routing graph (fig. 3, (II)) is constructed. The edges in this graph represent routing regions, which are parts of a channel, the vertices describe connections between two channels. For each net the shortest paths between its terminals in the routing graph are computed. Thus afterwards, the number of all nets routed through each region is known. For each channel inside a meta-block, routing space is added depending on the widest region within this channel (fig. 3, (III)).
During the construction of the initial individuals a special heuristic, the iterated matching introduced by Fritsch and Vornberger [10], is used to take care that highly connected cells are placed next to each other. For that purpose, out of all possible combinations those pairings of blocks are chosen which yield a maximal global quality with respect to the number of common nets. For further details on this point see [16].