Crosstalk-constrained maze routing based on Lagrangian relaxation

Hai Zhou; D.F. Wong

doi:10.1109/ICCD.1997.628931

Crosstalk-constrained maze routing based on Lagrangian relaxation

Hai Zhou, D.F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Chapter › peer-review

7 Citations (Scopus)

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 language	English
Title of host publication	1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors
Publisher	IEEE
Pages	628-633
Number of pages	6
ISBN (Print)	081868206X
DOIs	https://doi.org/10.1109/ICCD.1997.628931
Publication status	Published - Oct 1997
Event	1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors - Austin, United States Duration: 12 Oct 1997 → 15 Oct 1997

Publication series

Name	Proceedings of 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors

Conference

Conference	1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors
Country/Territory	United States
City	Austin
Period	12/10/97 → 15/10/97

Scopus Subject Areas

Hardware and Architecture
Electrical and Electronic Engineering

Access to Document

10.1109/ICCD.1997.628931

Cite this

Zhou, H., & Wong, D. F. (1997). Crosstalk-constrained maze routing based on Lagrangian relaxation. In 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors (pp. 628-633). (Proceedings of 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors). IEEE. https://doi.org/10.1109/ICCD.1997.628931

@inbook{3b7a7023194649eeb50969c65e797d1b,

title = "Crosstalk-constrained maze routing based on Lagrangian relaxation",

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.",

author = "Hai Zhou and D.F. Wong",

note = "Publisher Copyright: {\textcopyright} 1997 IEEE; 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors ; Conference date: 12-10-1997 Through 15-10-1997",

year = "1997",

month = oct,

doi = "10.1109/ICCD.1997.628931",

language = "English",

isbn = "081868206X",

series = "Proceedings of 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors",

publisher = "IEEE",

pages = "628--633",

booktitle = "1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors",

address = "United States",

}

Zhou, H & Wong, DF 1997, Crosstalk-constrained maze routing based on Lagrangian relaxation. in 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors. Proceedings of 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors, IEEE, pp. 628-633, 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors, Austin, Texas, United States, 12/10/97. https://doi.org/10.1109/ICCD.1997.628931

Crosstalk-constrained maze routing based on Lagrangian relaxation. / Zhou, Hai; Wong, D.F.
1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors. IEEE, 1997. p. 628-633 (Proceedings of 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors).

Research output: Chapter in book/report/conference proceeding › Chapter › peer-review

TY - CHAP

T1 - Crosstalk-constrained maze routing based on Lagrangian relaxation

AU - Zhou, Hai

AU - Wong, D.F.

PY - 1997/10

Y1 - 1997/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0031338210&partnerID=8YFLogxK

U2 - 10.1109/ICCD.1997.628931

DO - 10.1109/ICCD.1997.628931

M3 - Chapter

AN - SCOPUS:0031338210

SN - 081868206X

T3 - Proceedings of 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors

SP - 628

EP - 633

BT - 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors

PB - IEEE

T2 - 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors

Y2 - 12 October 1997 through 15 October 1997

ER -

Crosstalk-constrained maze routing based on Lagrangian relaxation

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this