A Survey of Problems and Results for Channel Routing (Extended Abstract),
Abstract
Channel routing plays a central role in the development of automated layout systems for integrated circuits. Many layout systems first place modules on a chip or circuit board and then wire together terminals on different modules that should be electrically connected. This wiring problem is often solved by heuristically partitioning the given space into rectangular channels and then assigning to each such channel a set of wires which are to pass through it. This solution reduces a 'global' wiring problem to a set of disjoint (and hopefully easier) 'local' channel routing subproblems. For this reason, channel routing problems have been intensively studied for over a decade, and numerous heuristics and approximation algorithms have been proposed. This paper considers a very specific class of channel routing problems with the following generic form. The channel consists of a rectilinear grid of tracks (or rows) and columns. Along the top and bottom tracks are numbers called terminals, and terminals with the same number form a net. A net with r terminals is called an r-point net. The smallest net is a 2-point net. If r > 2, we have a multipoint net. The channel routing problem is to connect all the terminals in each net using horizontal and vertical wires which are routed along the underlying rectilinear grid. The goal is to complete the wiring using the minimum number of tracks; i.e., to minimize the width of the channel. No constraint is placed on the number of columns used at either end of the channel. A variety of models have been proposed for channel routing, with differences depending on the number of layers allowed and on the ways in which wires are allowed to interact.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1986
- Accession Number
- ADA176657
Entities
People
- Tom Leighton
Organizations
- Massachusetts Institute of Technology