Title :
A new lower bound for channel routing
Author :
Pal, R.K. ; Pal, S.P. ; Pal, A.
Author_Institution :
Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Kharagpur, India
Abstract :
Channel routing is a key problem in the physical design of VLSI chips. It is known that max(d/sub max/, /spl upsi//sub max/) is a lower bound on the number of tracks required in the reserved two-layer Manhattan routing model, where d/sub max/ is the channel density and v/sub max/ is the length of the longest path in the vertical constraint graph. We propose a polynomial time algorithm that computes a better lower bound on the number of tracks required for routing. This algorithm is also applicable for computing a lower bound on the number of tracks in the three-layer HVH routing model.<>
Keywords :
VLSI; circuit layout; network routing; network synthesis; VLSI chip design; channel density; channel routing; lower bound; polynomial time algorithm; reserved two-layer Manhattan routing model; three-layer HVH routing model; vertical constraint graph; Computer science; Councils; Design engineering; Electrocardiography; Polynomials; Routing; Shape; Very large scale integration; Wire;
Conference_Titel :
TENCON '93. Proceedings. Computer, Communication, Control and Power Engineering.1993 IEEE Region 10 Conference on
Conference_Location :
Beijing, China
Print_ISBN :
0-7803-1233-3
DOI :
10.1109/TENCON.1993.320037
