Technical Report 269-1990
- Title
- Optimizing Area and Layer Assignment in Knock-Knee Channel Routing
- Authors
- Ruth Kuchem, Dorothea Wagner, and Frank Wagner
- Source
-
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
- Classification
-
not available
- Keywords
-
not available
-
In this paper we consider the channel routing problem in the knock-knee mode. An algorithm is presented that always constructs a correct layout in a channel of bounded size if there is one, and guarantees that it is wirable with only three conducting layers, i.e. the layout is optimal with respect to the area and to the number of layers. The algorithm thus improves all previously known layout algorithms, which either use additional columns to produce a three-layer wirable layout or construct a layout for which the three-layer wirability is not proved. Moreover, for the layer assignment only O(N) (N number of nets) vias are used.