direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 1990

Channel Routing under Different Optimization Criteria
Zitatschlüssel Report-240-1989
Autor Dorothea Wagner and Frank Wagner
Seiten 295-305
Jahr 1989
Journal Methods of Operations Research, 1990
Jahrgang 62
Nummer 240
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Download Bibtex Eintrag