Optimal non-uniform wire-sizing under the Elmore delay model

Chung-Ping Chen; Hai Zhou; D. F. Wong

doi:10.1109/ICCAD.1996.568937

Optimal non-uniform wire-sizing under the Elmore delay model

Chung-Ping Chen, Hai Zhou, D. F. Wong

Office of the Provost

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

22 Citations (Scopus)

Abstract

We consider non-uniform wire-sizing for general routing trees under the Elmore delay model. Three minimization objectives are studied: 1) total weighted sink-delay; 2) total area subject to sink-delay bounds; and 3) maximum sink-delay. We first present an algorithm NWSA-wd for minimizing total weighted sink-delays based on iteratively applying the wire-sizing formula in [1]. We show that NWSA-wd always converges to an optimal wire-sizing solution. Based on NWSA-wd and the Lagrangian relaxation technique, we obtained two algorithms NWSA-db and NWSA-md which can optimally solve the other two minimization objectives. Experimental results show that our algorithms are efficient both in terms of runtime and storage. For example, NWSA-wd, with linear runtime and storage, can solve a 6201-wire-segment routing-tree problem using about 1.5-second runtime and 1.3-MB memory on an IBM RS/6000 workstation.

Original language	English
Title of host publication	1996 IEEE/ACM International Conference on Computer-Aided Design
Publisher	IEEE
Pages	38-43
Number of pages	6
ISBN (Print)	0818675977
DOIs	https://doi.org/10.1109/ICCAD.1996.568937
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.568937

Cite this

@inbook{042ba01ded714a04ba3bd1fbab4c7e9b,

title = "Optimal non-uniform wire-sizing under the Elmore delay model",

abstract = "We consider non-uniform wire-sizing for general routing trees under the Elmore delay model. Three minimization objectives are studied: 1) total weighted sink-delay; 2) total area subject to sink-delay bounds; and 3) maximum sink-delay. We first present an algorithm NWSA-wd for minimizing total weighted sink-delays based on iteratively applying the wire-sizing formula in [1]. We show that NWSA-wd always converges to an optimal wire-sizing solution. Based on NWSA-wd and the Lagrangian relaxation technique, we obtained two algorithms NWSA-db and NWSA-md which can optimally solve the other two minimization objectives. Experimental results show that our algorithms are efficient both in terms of runtime and storage. For example, NWSA-wd, with linear runtime and storage, can solve a 6201-wire-segment routing-tree problem using about 1.5-second runtime and 1.3-MB memory on an IBM RS/6000 workstation.",

author = "Chung-Ping Chen and Hai Zhou and Wong, {D. F.}",

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

language = "English",

isbn = "0818675977",

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

publisher = "IEEE",

pages = "38--43",

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

address = "United States",

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

}

Chen, C-P, Zhou, H & Wong, DF 1996, Optimal non-uniform wire-sizing under the Elmore delay model. in 1996 IEEE/ACM International Conference on Computer-Aided Design . Proceedings of 1996 IEEE/ACM International Conference on Computer-Aided Design , IEEE, pp. 38-43, 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.568937

TY - CHAP

T1 - Optimal non-uniform wire-sizing under the Elmore delay model

AU - Chen, Chung-Ping

AU - Zhou, Hai

AU - Wong, D. F.

PY - 1996/11

Y1 - 1996/11

N2 - We consider non-uniform wire-sizing for general routing trees under the Elmore delay model. Three minimization objectives are studied: 1) total weighted sink-delay; 2) total area subject to sink-delay bounds; and 3) maximum sink-delay. We first present an algorithm NWSA-wd for minimizing total weighted sink-delays based on iteratively applying the wire-sizing formula in [1]. We show that NWSA-wd always converges to an optimal wire-sizing solution. Based on NWSA-wd and the Lagrangian relaxation technique, we obtained two algorithms NWSA-db and NWSA-md which can optimally solve the other two minimization objectives. Experimental results show that our algorithms are efficient both in terms of runtime and storage. For example, NWSA-wd, with linear runtime and storage, can solve a 6201-wire-segment routing-tree problem using about 1.5-second runtime and 1.3-MB memory on an IBM RS/6000 workstation.

AB - We consider non-uniform wire-sizing for general routing trees under the Elmore delay model. Three minimization objectives are studied: 1) total weighted sink-delay; 2) total area subject to sink-delay bounds; and 3) maximum sink-delay. We first present an algorithm NWSA-wd for minimizing total weighted sink-delays based on iteratively applying the wire-sizing formula in [1]. We show that NWSA-wd always converges to an optimal wire-sizing solution. Based on NWSA-wd and the Lagrangian relaxation technique, we obtained two algorithms NWSA-db and NWSA-md which can optimally solve the other two minimization objectives. Experimental results show that our algorithms are efficient both in terms of runtime and storage. For example, NWSA-wd, with linear runtime and storage, can solve a 6201-wire-segment routing-tree problem using about 1.5-second runtime and 1.3-MB memory on an IBM RS/6000 workstation.

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

U2 - 10.1109/ICCAD.1996.568937

DO - 10.1109/ICCAD.1996.568937

M3 - Chapter

AN - SCOPUS:0030416298

SN - 0818675977

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

SP - 38

EP - 43

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 non-uniform wire-sizing under the Elmore delay model

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this