Crosstalk-constrained maze routing based on Lagrangian relaxation

Hai Zhou*, D. F. Wong

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE International Conference on Computer Design
Subtitle of host publicationVLSI in Computers and Processors
Editors Anon
PublisherIEEE
Pages628-633
Number of pages6
StatePublished - Dec 1 1997
EventProceedings of the 1997 International Conference on Computer Design - Austin, TX, USA
Duration: Oct 12 1997Oct 15 1997

Other

OtherProceedings of the 1997 International Conference on Computer Design
CityAustin, TX, USA
Period10/12/9710/15/97

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Crosstalk-constrained maze routing based on Lagrangian relaxation'. Together they form a unique fingerprint.

Cite this