Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing.
Abstract
Channel routing plays a crucial role in the development of automated layout systems for integrated circuits. Most layout systems first place modules on a chip and then wire together terminals on different modules that should be electrically connected. This wiring problem id 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, the channel routing problem has been intensively studied for over a decade, a numerous heuristics and approximation algorithms have been proposed. The generic form of the channel routing problem may be described as follows. 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. 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
- ADA176613
Entities
People
- Bonnie Berger
- Donna Brown
- Martin Brady
- Tom Leighton
Organizations
- Massachusetts Institute of Technology