Optimal algorithm for river routing with crosstalk constraints

Hai Zhou; D.F. Wong

doi:10.1109/ICCAD.1996.569717

Optimal algorithm for river routing with crosstalk constraints

Hai Zhou, D.F. Wong

Office of the Provost

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

27 Citations (Scopus)

Abstract

With the increasing density of VLSI circuits, the interconnection wires are getting packed even closer. This has increased the effect of interaction between these wires on circuit performance and hence, the importance of controlling crosstalk. In this paper, we consider river routing with crosstalk constraints. Given the positions of the pins in a single-layer routing channel and the maximum tolerable crosstalk between each pair of nets, we give a polynomial time algorithm to decide whether there is a feasible river routing solution and produce one with minimum crosstalk whenever the problem is feasible.

Original language	English
Title of host publication	1996 IEEE/ACM International Conference on Computer-Aided Design
Publisher	IEEE
Pages	310-315
Number of pages	6
ISBN (Print)	0818675977
DOIs	https://doi.org/10.1109/ICCAD.1996.569717
Publication status	Published - Nov 1996
Event	1996 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1996 - San Jose, United States Duration: 10 Nov 1996 → 14 Nov 1996 https://ieeexplore.ieee.org/xpl/conhome/4215/proceeding (Link to conference proceedings)

Publication series

Name	Proceedings of 1996 IEEE/ACM International Conference on Computer-Aided Design

Conference

Conference	1996 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1996
Country/Territory	United States
City	San Jose
Period	10/11/96 → 14/11/96
Internet address	https://ieeexplore.ieee.org/xpl/conhome/4215/proceeding (Link to conference proceedings)

Scopus Subject Areas

Software
Computer Science Applications
Computer Graphics and Computer-Aided Design

Access to Document

10.1109/ICCAD.1996.569717

Cite this

@inbook{e83643b4ca214312bf55b5c0c594e248,

title = "Optimal algorithm for river routing with crosstalk constraints",

abstract = "With the increasing density of VLSI circuits, the interconnection wires are getting packed even closer. This has increased the effect of interaction between these wires on circuit performance and hence, the importance of controlling crosstalk. In this paper, we consider river routing with crosstalk constraints. Given the positions of the pins in a single-layer routing channel and the maximum tolerable crosstalk between each pair of nets, we give a polynomial time algorithm to decide whether there is a feasible river routing solution and produce one with minimum crosstalk whenever the problem is feasible.",

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

note = "Publisher Copyright: {\textcopyright} 1996 IEEE ; 1996 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1996 ; Conference date: 10-11-1996 Through 14-11-1996",

year = "1996",

month = nov,

doi = "10.1109/ICCAD.1996.569717",

language = "English",

isbn = "0818675977",

series = "Proceedings of 1996 IEEE/ACM International Conference on Computer-Aided Design",

publisher = "IEEE",

pages = "310--315",

booktitle = "1996 IEEE/ACM International Conference on Computer-Aided Design",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/4215/proceeding",

}

Zhou, H & Wong, DF 1996, Optimal algorithm for river routing with crosstalk constraints. in 1996 IEEE/ACM International Conference on Computer-Aided Design . Proceedings of 1996 IEEE/ACM International Conference on Computer-Aided Design, IEEE, pp. 310-315, 1996 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1996, San Jose, California, United States, 10/11/96. https://doi.org/10.1109/ICCAD.1996.569717

TY - CHAP

T1 - Optimal algorithm for river routing with crosstalk constraints

AU - Zhou, Hai

AU - Wong, D.F.

PY - 1996/11

Y1 - 1996/11

N2 - With the increasing density of VLSI circuits, the interconnection wires are getting packed even closer. This has increased the effect of interaction between these wires on circuit performance and hence, the importance of controlling crosstalk. In this paper, we consider river routing with crosstalk constraints. Given the positions of the pins in a single-layer routing channel and the maximum tolerable crosstalk between each pair of nets, we give a polynomial time algorithm to decide whether there is a feasible river routing solution and produce one with minimum crosstalk whenever the problem is feasible.

AB - With the increasing density of VLSI circuits, the interconnection wires are getting packed even closer. This has increased the effect of interaction between these wires on circuit performance and hence, the importance of controlling crosstalk. In this paper, we consider river routing with crosstalk constraints. Given the positions of the pins in a single-layer routing channel and the maximum tolerable crosstalk between each pair of nets, we give a polynomial time algorithm to decide whether there is a feasible river routing solution and produce one with minimum crosstalk whenever the problem is feasible.

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

U2 - 10.1109/ICCAD.1996.569717

DO - 10.1109/ICCAD.1996.569717

M3 - Chapter

AN - SCOPUS:0030408885

SN - 0818675977

T3 - Proceedings of 1996 IEEE/ACM International Conference on Computer-Aided Design

SP - 310

EP - 315

BT - 1996 IEEE/ACM International Conference on Computer-Aided Design

PB - IEEE

T2 - 1996 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1996

Y2 - 10 November 1996 through 14 November 1996

ER -

Optimal algorithm for river routing with crosstalk constraints

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this