Crosstalk-constrained maze routing based on Lagrangian relaxation

Author

Zhou, Hai ; Wong, D.F.

Author_Institution

Dept. of Comput. Sci., Texas Univ., Austin, TX, USA

fYear

1997

fDate

12-15 Oct 1997

Firstpage

628

Lastpage

633

Abstract

With the increasing density of VLSI circuits, interconnection wires are getting packed even closer. This has increased the effect of interaction between wires on circuit performance and hence, the importance of controlling crosstalk. Maze routing is a robust and general approach which can be used in many situations including multi-layer interconnections. In this paper we consider crosstalk avoidance in maze routing. The crosstalk-constrained maze routing problem is first formulated. Then we show it is equivalent to the multi-constrained shortest path problem and is strongly NP-complete. Based on the Lagrangian relaxation technique, an effective heuristic algorithm is designed to solve the problem

Keywords

VLSI; circuit layout CAD; computational complexity; crosstalk; integrated circuit interconnections; network routing; relaxation theory; Lagrangian relaxation; VLSI circuits; circuit performance; crosstalk; crosstalk avoidance; heuristic algorithm; interconnection wires; maze routing; multi-layer interconnections; shortest path problem; strongly NP-complete; Circuit optimization; Crosstalk; Heuristic algorithms; Integrated circuit interconnections; Lagrangian functions; Robustness; Routing; Shortest path problem; Very large scale integration; Wires;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Design: VLSI in Computers and Processors, 1997. ICCD '97. Proceedings., 1997 IEEE International Conference on

Conference_Location

Austin, TX

ISSN

1063-6404

Print_ISBN

0-8186-8206-X

Type

conf

DOI

10.1109/ICCD.1997.628931

Filename

628931