Abstract |
Channel routing is a basic problem in the design of VLSI-circuits and has received considerable attention in the past. There are essentially two different routing models: *Knock-knee routing* and *Manhattan routing*. We consider the knock-knee model; only two terminal nets are involved. The *channel routing problem (CRP)* is given by a bounded rectangle in a rectilinear grid (the *channel*) and a collection of pairs of terminals (called *nets*), where the *input terminal* lies on the upper boundary and the *exit terminal* lies on the lower boundary of the channel. The *layout* consists of edge-disjoint paths (called *wires*) through the channel connecting the input- and the exit terminal of the nets. To avoid physical contacts between the wires, the edges of the paths are assigned to different layers, such that no two wires share a grid point in the same layer (called *wiring*). Connections between distinct layers (called *vias*) are placed on grid points. For the design of algorithms solving the layout respectively wiring problem the following criteria are of central importance: The *area of the layout*, the *length of the wires*, the *number of layers*, the \it number of vias and the *complexity of the algorithm*. In this paper we present two new algorithms, that guarantee good respectively optimal solutions for these problems. |