Thumbnail
Access Restriction
Subscribed

Author Hambrusch, S.E.
Sponsorship IEEE Council on Electronic Design Automation ♦ IEEE Circuits and Systems Society
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©1982
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science ♦ Natural sciences & mathematics ♦ Physics ♦ Electricity & electronics
Subject Keyword Routing ♦ Wires ♦ Integrated circuit layout ♦ Joining processes ♦ Costs ♦ Nonhomogeneous media ♦ Design automation
Abstract We consider routing models that consist of L layers in which each layer can contain horizontal and vertical wires and in which up to k wires on different layers are allowed to run on top of each other. Within this overlap model we study the relationship between the channel width, the number of contact points, and the amount of overlap used for routing n two-terminal nets across a channel. For k ≤ [L/2] - 2 we show how to solve the channel routing problem using [d/k] + 1 tracks, which is only one track more than the optimal channel width. We extend this algorithm to values of k in the range [L/2] - 1 ≤ k ≤ [L/2] +1. We also present algorithms for the 3- and 4-layer model with double overlap that use fewer tracks than our general channel routing algorithm. All algorithms use O(n) contact points and can be implemented to run in O(n) time.
Description Author affiliation :: Department of Computer Sciences, Purdue University, West Lafayette, IN, USA
ISSN 02780070
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1985-01-01
Publisher Place U.S.A.
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Volume Number 4
Issue Number 1
Size (in Bytes) 1.09 MB
Page Count 8
Starting Page 23
Ending Page 30


Source: IEEE Xplore Digital Library