next up previous

The genotype

Figure: The slicing tree for the layout shown in figure 1

The genotype is encoded by a binary slicing tree with additional sizing and routing information for each node. The leaves of this tree represent the macro cells (blocks) and the inner nodes represent partial layouts (meta-blocks), as shown in figure 5. The tree is constructed in a bottom-up fashion. When building a meta-block out of two blocks (or meta-blocks) the arrangement and the rotation of the two blocks are fixed. The exact routing in the channel between these two blocks is done (cf. fig. 6), i.e. nets between the two blocks are connected and routed. Nets which connect other terminals than those on the borders of the two blocks are passed on as terminals to the borders of the resulting meta-block.

Figure 6: Combining two blocks to a meta-block

If the blocks have different layout-alternatives, all necessary combinations of alternatives are stored in the shape-function of the resulting meta-block. The number of combinations does not grow exponentially in the number of blocks contained in a single meta-block, because some of the combinations are redundant (cf. Fig. 7). Storing all alternatives for the meta-blocks is useful because one can not decide in the lower level of the tree, which implementation of a meta-block would be the best to minimize the overall area of the layout.

Figure 7: The construction of the shape-function for a meta-block M for block being positioned upon , or vice versa

Fri Jun 23 12:06:44 MET DST 1995