A channel compaction algorithm incorporating via minimization and lateral via shifting is discussed. Bump propagation from the center of vias is the crucial phenomenon preventing compaction results from attaining the lower bound. Via minimization reduces the sources of the bumps, and lateral via shifting splits the critical paths which dominate the height of the channel. The authors adopt a contour-following approach as the basic operation to compact and straighten each wire. The sequence of the wires is determined by a topological sorting algorithm which also resolves any ordering conflicts by splitting the wires. The authors show the effectiveness of via minimization and shifting in reducing channel routing area. An improvement of up to 22.9% over one-dimensional compaction has been observed. Experiments on various solutions of Deutsch's difficult example indicate no significant relationship between the compacted channel height and the number of tracks in the routing solution.>

The novel and more difficult channel routing problems are proposed. Each is a simple transformation of the original that maintains all the old vertical constraints but adds an equivalent new set resulting in cycles (none were present previously). These variations can be considered gridless.>

A program that produces single-layer planar routing over the cells for I2L and LST2L logic arrays is described. This router has been integrated into a layout system which was previously restricted to the layout of standard cell LSI chips. When used in conjunction with a channel router, the complete routing is produced automatically. This paper defines the over-the-cell routing problem, describes the algorithms for its solution, and presents typical routing results.

This paper presents an algorithm for interconnecting two sets of terminals across an intervening channel. It is assumed that the routing is done on two distinct levels with all horizontal paths being assigned to one level and all vertical paths to the other. Connections between the levels are made through contact windows. A single net may result in many horizontal and vertical segments. Experimental results indicate that this algorithm is very successful in routing channels that contain severe constraints. Usually, the routing is accomplished within one track of the mathematical lower bound. The routing algorithm presented here was developed as part of LTX, a computer-aided design system for integrated circuit layout and was implemented on an HP-2100 minicomputer. A typical channel (300 terminals, 100 nets) can be routed in less than 5 seconds. Routing results are presented both for polycell chips under development at Bell Laboratories and for examples that exist in the published literature. For the latter, reductions of 10% in the wiring area were typical.

LTX is a minicomputer-based design system for large-scale integrated circuit chip layout which offers a flexible set of interactive and automatic procedures for translating a circuit connectivity description into a finished mask design. The system encompasses algorithms for two-dimensional placement, string placement, exploitation of equivalent terminals, decomposition of routing into channels, and channel routing. Circuit connectivity is preserved during interactive procedures. LTX runs on an H-P 2100 series computer with 32K of memory and disc.

Suppose we are given two disjoint linearly ordered subsets A and B of a linearly ordered set C , say A = { a 1 < a 2 < ··· < a m } and B = { b 1 < b 2 < ··· < b n }. The problem is to determine the linear ordering of their union (i.e. to merge A and B ) by means of a sequence of pairwise comparisons between an element of A and an element of B (which we refer to in the paper as the ( m, n ) problem). Given any algorithm s to solve the ( m, n ) problem, we are interested in the maximum number of comparisons K s ( m, n ) required under all possible orderings of A ∪ B . An algorithm s is said to be minimax if K s ( m, n ) = K ( m, n ) where K ( m, n ) = mins K s ( m, n ) It is a rather difficult task to determine K ( m, n ) in general. In this study the authors are only concerned with the minimax over a particular class of merging algorithms. This class includes the tape merge algorithm, the simple binary algorithm, and the generalized binary algorithm.