Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing.

摘要

Channel routing plays an important role in the development of automated layout systems for integrated circuits. Many layout systems first place modules on a chip 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, the channel routing problem has been intensively studied for over a decade, and numerous heuristics and approximation algorithms have been proposed for its solution. 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 q terminals is called an q-terminal net. The smallest net is a two-terminal net; if q>2, we have a multiterminal 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. (kr)