A polynomial time optimal algorithm for simultaneous buffer and wire sizing

C. C. N. Chu; D. F. Wong

doi:10.1109/DATE.1998.655901

A polynomial time optimal algorithm for simultaneous buffer and wire sizing

C. C. N. Chu, D. F. Wong

Office of the Provost

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

5 Citations (Scopus)

Abstract

An interconnect joining a source and a sink is divided into fixed-length uniform-width wire segments, and some adjacent segments have buffers in between. The problem we considered is to simultaneously size the buffers and the segments so that the Elmore delay from the source to the sink is minimized. Previously, no polynomial time algorithm for the problem has been reported in the literature. In this paper, we present a polynomial time algorithm SBWS for the simultaneous buffer and wire sizing problem. SBWS is an iterative algorithm with guaranteed convergence to the optimal solution. It runs in quadratic time and uses constant memory for computation. Also, experimental results show that SBWS is extremely efficient in practice. For example, for an interconnect of 10 000 segments and buffers, the CPU time is only 0.127 s.

Original language	English
Title of host publication	Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 1998
Publisher	IEEE
Pages	479-485
Number of pages	7
ISBN (Print)	0818683597
DOIs	https://doi.org/10.1109/DATE.1998.655901
Publication status	Published - 23 Feb 1998
Event	1998 Design, Automation and Test in Europe Conference and Exhibition, DATE 1998 - Paris, France Duration: 23 Feb 1998 → 26 Feb 1998 https://ieeexplore.ieee.org/xpl/conhome/5270/proceeding (Conference proceedings)

Publication series

Name	Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE
ISSN (Print)	1530-1591

Conference

Conference	1998 Design, Automation and Test in Europe Conference and Exhibition, DATE 1998
Country/Territory	France
City	Paris
Period	23/02/98 → 26/02/98
Internet address	https://ieeexplore.ieee.org/xpl/conhome/5270/proceeding (Conference proceedings)

Scopus Subject Areas

Engineering(all)

Access to Document

10.1109/DATE.1998.655901

Cite this

@inproceedings{5f55728938b8409bb42a8d9a9285be0b,

title = "A polynomial time optimal algorithm for simultaneous buffer and wire sizing",

abstract = "An interconnect joining a source and a sink is divided into fixed-length uniform-width wire segments, and some adjacent segments have buffers in between. The problem we considered is to simultaneously size the buffers and the segments so that the Elmore delay from the source to the sink is minimized. Previously, no polynomial time algorithm for the problem has been reported in the literature. In this paper, we present a polynomial time algorithm SBWS for the simultaneous buffer and wire sizing problem. SBWS is an iterative algorithm with guaranteed convergence to the optimal solution. It runs in quadratic time and uses constant memory for computation. Also, experimental results show that SBWS is extremely efficient in practice. For example, for an interconnect of 10 000 segments and buffers, the CPU time is only 0.127 s.",

author = "Chu, {C. C. N.} and Wong, {D. F.}",

year = "1998",

month = feb,

day = "23",

doi = "10.1109/DATE.1998.655901",

language = "English",

isbn = "0818683597",

series = "Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE",

publisher = "IEEE",

pages = "479--485",

booktitle = "Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 1998",

address = "United States",

note = "1998 Design, Automation and Test in Europe Conference and Exhibition, DATE 1998 ; Conference date: 23-02-1998 Through 26-02-1998",

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

}

Chu, CCN & Wong, DF 1998, A polynomial time optimal algorithm for simultaneous buffer and wire sizing. in Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 1998. Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE, IEEE, pp. 479-485, 1998 Design, Automation and Test in Europe Conference and Exhibition, DATE 1998, Paris, France, 23/02/98. https://doi.org/10.1109/DATE.1998.655901

A polynomial time optimal algorithm for simultaneous buffer and wire sizing. / Chu, C. C. N.; Wong, D. F.
Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 1998. IEEE, 1998. p. 479-485 (Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE).

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

TY - GEN

T1 - A polynomial time optimal algorithm for simultaneous buffer and wire sizing

AU - Chu, C. C. N.

AU - Wong, D. F.

PY - 1998/2/23

Y1 - 1998/2/23

N2 - An interconnect joining a source and a sink is divided into fixed-length uniform-width wire segments, and some adjacent segments have buffers in between. The problem we considered is to simultaneously size the buffers and the segments so that the Elmore delay from the source to the sink is minimized. Previously, no polynomial time algorithm for the problem has been reported in the literature. In this paper, we present a polynomial time algorithm SBWS for the simultaneous buffer and wire sizing problem. SBWS is an iterative algorithm with guaranteed convergence to the optimal solution. It runs in quadratic time and uses constant memory for computation. Also, experimental results show that SBWS is extremely efficient in practice. For example, for an interconnect of 10 000 segments and buffers, the CPU time is only 0.127 s.

AB - An interconnect joining a source and a sink is divided into fixed-length uniform-width wire segments, and some adjacent segments have buffers in between. The problem we considered is to simultaneously size the buffers and the segments so that the Elmore delay from the source to the sink is minimized. Previously, no polynomial time algorithm for the problem has been reported in the literature. In this paper, we present a polynomial time algorithm SBWS for the simultaneous buffer and wire sizing problem. SBWS is an iterative algorithm with guaranteed convergence to the optimal solution. It runs in quadratic time and uses constant memory for computation. Also, experimental results show that SBWS is extremely efficient in practice. For example, for an interconnect of 10 000 segments and buffers, the CPU time is only 0.127 s.

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

U2 - 10.1109/DATE.1998.655901

DO - 10.1109/DATE.1998.655901

M3 - Conference proceeding

AN - SCOPUS:0006683092

SN - 0818683597

T3 - Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE

SP - 479

EP - 485

BT - Proceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 1998

PB - IEEE

T2 - 1998 Design, Automation and Test in Europe Conference and Exhibition, DATE 1998

Y2 - 23 February 1998 through 26 February 1998

ER -

A polynomial time optimal algorithm for simultaneous buffer and wire sizing

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this