The number of devices in a chip has increased from about a thousand devices in the early 70's to over tens of million devices now. This has led to a significant increase in the number of interconnections. An efficient routing of these interconnections reduces chip size, and improves the reliability of the chip design. In the light of this routing has received a great deal of attention from researchers.

In the physical design process for very large scale integrated (VLSI) circuits the logical structure of a circuit is transformed into its physical layout. Detailed routing is one of the tasks in this process. A detailed router connects pins of signal nets in a rectangular region in accordance with a set of routing constraints, such as the number of layers, the minimal space between wires, minimum wire width, number of vias, crosstalk and the net length. The results of this detailed routing has a strong influence on the fabrication yield and production costs of the circuit.

The channel routing problem has been found to be NP-complete implying there is no known deterministic algorithm to solve it in polynomial time and several algorithms have been proposed. New approaches are necessary to tackle this problem. Genetic algorithms (GAs) which are a new class of heuristic search methods based on biological evolution in nature have been applied increasingly successfully to find good heuristic solutions to NP-complete optimisation problems including VLSI design issues.

The idea of using the areas over the cells that are adjacent to channels has been put into practice in order to further reduce the total area of channels. Such areas are called over-the-cell (OTC) routing areas. Like a channel, an OTC routing area consists of tracks and columns. The aim of OTC channel routing is to minimise the congestion (number of tracks used) inside the channels.

A number of GAs have been developed for solving different channel routing problems. All these algorithms consider the area inside the channel only, and do not tackle the areas over-the-cell. In this research area GAs are used to carry out both over-the-cell routing and channel routing concurrently. In future, our research will target multi-layer and sytem-level routing.