Table 1: The benchmark instances
The algorithm has been tested on real-life circuits chosen from a layout-benchmark suite maintained
by MCNC (North Carolina's microelectronics, computing and networking center), see table 1.
The instances are layout-problems of the field of full-custom macro-cell layout.
Figure 8: Layout for ami49 (area: 57.3
)
Figure 8 shows a layout for the instance ami49, a problem with only
fixed-size cells.
The dark blocks show the cells, the lighter surface represents the
routing space, while the white area shows the wasted space inside the layout.
The actual implementation does not do the detailed routing but adds an estimated routing space
when combining two blocks.
The estimation is quite bad, because actually one track is reserved for each net in
the channel between two blocks.
Implementing a better heuristic for the detailed routing would further reduce
the channel width.
Figure 9: The performance with respect to the creation of the initial population (ami49)
Figure 9 shows the performance of the genetic algorithm for circuit ami49.
The best fitness averaged over 10 runs is shown for both cases up to 400
generations, the population-size was 20 individuals.
The upper curve describes the progress of the fitness (layout area) for runs
of the algorithm started with populations of totally random generated
individuals.
The lower curve describes the performance for runs which have started with
a set of very good individuals, which have been generated by application of the
iterated matching.
For an impression of the solution quality, which was on average 58.9
for the
10 runs with the `intelligent' creation of the initial population, note that the
layout shown in figure 8 has an area of 57.3
.
Figure: The benefit of shape-functions for meta-blocks, average of 10 runs (
)
For circuits with flexible cells it is helpful to store all non-redundant layout-alternatives
for the meta-blocks in shape-functions to enhance the quality of the initial population.
This also decreases the performance of the mutation-operator, because after the movement
of a meta-block its best implementation on the new position can be chosen.
Figure 10 shows the benefit of storing shape-functions even
for the meta-blocks for the circuit 
with 33 flexible cells, each having
three different implementations.
It is seen that the version which stores all alternatives for the meta-blocks clearly
outperformes the version of the algorithm which is described in the upper curve.
Here, when pairing two flexible blocks to a meta-block, only the implementation
with the minimal area is stored.