A 'greedy' channel-router is presented. It is quick, simple and effective. It always succeeds, usually using no more than one track more than required by channel density. It may be forced in rare cases to make a few connections "off the end' of the channel, in order to succeed. It assumes that all pins and wiring lie on a common grid, and that vertical wires are on one layer, horizontal on another. The greedy router wires the channel left-to-right, column-bycolumn, wiring each column completely before starting the next. Within each column the router tries to maximize the utility of the wiring produced, using simple, 'greedy' heuristics. It may place a net on more than one track for o few columns, end collapse the net to a single track later on, using a vertical jog. It may also use o jog to move a net to a track closer to its pin in some future column. The router may occasionally add a new track to the channel, to avoid getting stuck. integrated circuits, layout, routing Introduced in 19711, channel routing has become a very popular method of routing integrated circuits 2-s . Typically, the wiring area is first divided into disjoint rectangular channels. A global router then determines which channels each net traverses. Finally a channel router computes a detailed routing for each channel. This approach is effective because it breaks down the overall problem into a number of simpler problems and simultaneously considers all nets traversing each channel.
The general channel-routing problem has been proven NP-Complete ~-1~ , although algorithms exist for highlyrestricted cases 1°'13-16 . A slightly different wiring model permits one to come within a factor of two of channel density 17. Useful methods also exist for computing lower bounds on channel widths 18,19 . These results highlight the need for good practical heuristics.
The algorithm presented here exploits a novel control structure: a left-to-right column-by-column scan of the channel, where the router completes the routing for one column before proceeding to the next. In each column the router acts in a 'greedy' manner trying to maximize the utility of the wiring produced.
Our work is an extension of Alford's =°, who also considered a left-to-right scan of the channel. His router did not guarantee success (because it did not allow nets to occupy more than one track in any column), ran quite slowly, and produced poorer results than our 'greedy' algorithm.
Kawarnoto and Kajitani 7 use a similar column-by-column approach, but not in left-to-right order. They also assume (as we do not) that between adjacent columns there is enough room to wire an arbitrary permutation.