Channel Assignment for Chip Wiring
Original Publication Date: 1983-Aug-01
Included in the Prior Art Database: 2005-Feb-07
A general strategy for wiring chips is to treat the problem in two phases: a global assignment of wires is made to specific channels; next, the particular channel tracks for individual wires are chosen and interconnections established to specified pins on the macros in the chip. A procedure is described herein for the global assignment task which uses the chip model and routing map concepts described in the preceding article. The routing map is generalized to give not one but K maps from each channel region with which a pin is associated to all other regions. The K maps ideally specify maximally disjoint low-cost routes, which therefore provide alternative choices, and are generated iteratively by a shortest-path algorithm.