Modern VLSI (very large scale integrated) microchips contain some million transistors.
The design cycle for these chips consists of different serial steps (e.g. system
specification, functional design, logic design, circuit design, physical design)[8].
The physical design outlines the transformation of a circuit description (which is the
result of the preceding circuit design process) into the layout of a
chip, which is needed for the following fabrication step [3,5].
The layout includes the geometric description of the circuit components
and the information for the routes of the interconnections between them.
It also has pads positioned on its borders for the I/O-connections
of the chip.
The objectives in layout generation are to minimize the area of the circumscribing rectangle
and to produce a routing with short wirelengths, especially for some critical nets.
Due to its complexity, the physical design is usually divided into various, consecutive sub-steps:
The circuit has to be partitioned to get a number of modules (macro cells)
which have to be placed on the chip (floorplanning).
During placement there has to be enough space reserved to ensure the
completion of all interconnections later on.
In the routing phase, pins on the border of the modules have to be connected.
This is done in two steps: In the global routing the `loose' routes are determined, while
in the detailed routing the exact routes for the nets in each channel between two modules are
computed.
The last step in the physical design is the compaction of the layout, where it is compressed in all
dimensions so that the total area is reduced.
The algorithm described in this paper combines the routing
with the placement process during layout generation.
For a more detailed description of the usual phases and possible solution methods
in contrast to the approach described in this paper see [7].