The layout generation is one of the most time consuming tasks in the design cycle for VLSI- (very large scale integrated) microchips [13,17]. The input to this problem is a partitioned circuit, i.e. the elementary components of the circuit are grouped to build up to 50 macro-cells (modules). On the borders of these cells, terminals are located which have to be connected by signal nets.
The output of this design process is a layout for the circuit (fig. 1). The layout describes the placement of the cells and the routes for the interconnection wires between them. The main objective in layout optimization is to find an arrangement with a minimal overall area. Cells are not allowed to overlap each other, and the routing has to meet the technical constraints: space between parallel wires has to be added to prevent short circuits and for some critical nets the delay has to stay below a given threshold, which results in maximal admissible wirelengths for these nets.
Due to the complexity of the single tasks, placement of the cells is usually optimized separately from the computation of the routing for the interconnection nets. During placement an estimated amount of routing space is added, which restricts the maximal number of nets to be routed inside a channel between two cells. The following routing is two-phase: in the global routing the `loose' (global) routes for all interconnection nets are determined, whereas during the detailed routing the exact ways for the wires in the channels between the modules are fixed. Due to an overestimation of the needed routing space during placement, the layout has to be compacted after completion. In case of fault estimation, the routing cannot be completed inside the reserved routing area. This is either realized during the computation of the global routes, or during channel routing. In the latter case, the process has to backtrack and different global routes for some nets have to be chosen. If even global routing is impossible, the modules have to be rearranged, i.e.\ the process has to backtrack to the placement task.
The splitting of the layout design process results from the fact that the combined optimization of both tasks is too complex to be managed by most optimization techniques. Nevertheless, because of the interdependencies between placement and routing, it is wise to combine both tasks.
Figure 1: A layout for the circuit ami49 with 49 macro-cells and 408 nets