A general graph theoretic framework for multi-layer channel routing

Author

Pal, R.K. ; Datta, A.K. ; Pal, S.P. ; Das, M.M. ; Pal, Arnab

Author_Institution

Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Kharagpur, India

fYear

1995

fDate

4-7 Jan 1995

Firstpage

202

Lastpage

207

Abstract

In this paper we propose a general framework for viewing a class of heuristics for track assignment in channel routing from a purely graph theoretic angle. Within this framework we propose algorithms for computing routing solutions using optimal or near optimal number of tracks for several well-known benchmark channels in the two-layer VH. Three-layer HVH, and multi-layer V_iH_i and V_iH_i+1 routing models. Within the same framework we also design an algorithm for minimizing the total wire length in the two-layer VH and three-layer HVH routing models

Keywords

VLSI; circuit layout CAD; graph theory; integrated circuit layout; minimisation; network routing; VLSI layout; graph theoretic framework; heuristics; multilayer channel routing; three-layer HVH routing model; total wire length minimisation; track assignment; two-layer VH routing model; Algorithm design and analysis; Computer industry; Computer science; Councils; Design engineering; Integrated circuit layout; Integrated circuit modeling; NP-complete problem; Routing; Wire;

fLanguage

English

Publisher

ieee

Conference_Titel

VLSI Design, 1995., Proceedings of the 8th International Conference on

Conference_Location

New Delhi

ISSN

1063-9667

Print_ISBN

0-8186-6905-5

Type

conf

DOI

10.1109/ICVD.1995.512109

Filename

512109