9th International Conference on VLSI Design: VLSI in Mobile Communication
Channel routing in Manhattan-diagonal model
Bangalore, INDIA
January 03-January 06
ISBN: 0-8186-7228-5
This paper presents a new technique of channel routing based on the Manhattan-Diagonal (MD) model. The layout grid is assumed to consist of two layers with tracks in horizontal, vertical and /spl plusmn/45/spl deg/ directions. First, we consider the non-overlap model and present a simple O(l,d) time algorithm that routes an arbitrary channel with no cyclic vertical constraints in w tracks, where l is the length of the channel, d is the channel density, and d/spl les/w/spl les/(d+1). Next, we describe an output-sensitive algorithm that can route general channels with cyclic vertical constraints using w tracks, in O(l,w) time allowing overlapping of wiring segments in two layers. The router outputs an 18-track solution for the Deutsch's difficult example, a 2-track solution for Burstein's difficult channel, and a 15-track solution for cycle.tough without inserting any extra row or column. Apart from quick termination, the proposed algorithms provide solutions with significantly low via count and reduced wire length. The study thus reveals the superiority of MD-routing strategy to classical techniques.
Index Terms:
network routing; VLSI; circuit layout CAD; integrated circuit layout; Manhattan-diagonal model; channel routing; layout grid; output-sensitive algorithm; cyclic vertical constraints; low via count; reduced wire length; VLSI layout
Citation:
S. Das, B. Bhattacharya, "Channel routing in Manhattan-diagonal model," vlsid, pp.43, 9th International Conference on VLSI Design: VLSI in Mobile Communication, 1996