Routing-Probleme in VLSI-Systemen - Lösungsansätze mit Genetischen Algorithmen

| project staff | cooperation partners | project description | project software | publications |

In highly complex VLSI-systems – principally made possible by technological progress – the realization of connections between the switching elements, the so-called routing, is of great importance. However conventional wiring-algorithms often only provide insufficient solutions for concrete and practical relevant problem instances. Within the framework of the project it is being analyzed how and in which extent Genetic Algorithms (GAs) can be used for modelling and solving routing problems wrt. the aspects of quality and time. The following key aspects form the basis of developments:

Modelling problems with the help of GAs
It is to decide how the routing problem has to be encoded in the GA. The GA then works on this encoding. The developed software-package GAME makes it possible to use multiple encodings. It has to be determined how dedicated algorithms for selection, recombination and mutation can be defined. The performance of a GA strongly depends on how efficient the quality (fitness-function) of the elements of population can be calculated and on how fast the genetic operators (Crossing Over, Mutation, ...) can be accomplished.

Designing hybrid GAs
Due to our experiences the performance of GAs, especially in the CAD-area, can be improved by using problem specific knowledge. The interaction between GAs and classical optimization tools,e.g. greedy heuristics and Branch & Bound, must be organized. The problem specific methods, which are used here, are provided by the software-library MaDRE.

Heuristic-Learning
On the one hand the advantages of the GA-approach should be utilized, on the other hand also an efficient heuristic has to be developed. Thereby the problem is not directly solved by the GA. Rather GAs are used for the construction of heuristics. These are designed on the basis of BOMs and their quality is measured by a set of chosen samples. Here the individual routing strageties of the software-library MaDRE are used as BOMs.

For the work on the project following software-packets were developed and specifically adjusted:

GAME (Genetic Algorithm Managing Environment):
The program-library GAME is a unitized software-system and was designed by the work group in Freiburg especially for the application of GAs for optimization problems in circuit design.
(Contact adress: Frank Schmiedle)

MaDRE (Multiple Strategy Detailed Routing Environment)
The programm-library MaDRE contains a data structure for routing problems and also wiring algorithms for divers wiring models. The basis data structure was developed by the working group in Halle, the wiring algorithms were developed by the working groups in Freiburg and Halle.

RAVER (Random Violation, Exact Repair)
RAVER implements a router which combines traditional methods with
an exact router and profits of the advantages of both approaches.
It was developed by the working group in Freiburg.
(Contact adress: Christian Matuszewski)