next up previous
Next: FUTURE WORK Up: GENETIC DESIGN OF Previous: Crossover


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.

next up previous
Next: FUTURE WORK Up: GENETIC DESIGN OF Previous: Crossover

Fri Jun 23 12:06:44 MET DST 1995