Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation

Chung-Ping Chen; Chris C. N. Chu; D. F. Wong

doi:10.1145/288548.289097

Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation

Chung-Ping Chen, Chris C. N. Chu, D. F. Wong

Office of the Provost

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

52 Citations (Scopus)

Abstract

This paper considers simultaneous gate and wire sizing for general VLSI circuits under the Elmore delay model. We present a fast and exact algorithm which can minimize total area subject to maximum delay bound. The algorithm can be easily modified to give exact algorithms for optimizing several other objectives (e.g. minimizing maximum delay or minimizing total area subject to arrival time specifications at all inputs and outputs). No previous algorithm for simultaneous gate and wire sizing can guarantee exact solutions for general circuits. Our algorithm is an iterative one with a guarantee on convergence to global optimal solutions. It is based on Lagrangian relaxation and `one-gate/wire-at-a-time' local optimizations, and is extremely economical and fast. For example, we can optimize a circuit with 27,648 gates and wires in about 36 minutes using under 23 MB memory on an IBM RS/6000 workstation.

Original language	English
Title of host publication	ICCAD '98
Subtitle of host publication	Proceedings of the 1998 IEEE/ACM International Conference on Computer-aided Design
Publisher	Association for Computing Machinery (ACM)
Pages	617-624
Number of pages	8
ISBN (Print)	9781581130089
DOIs	https://doi.org/10.1145/288548.289097
Publication status	Published - 8 Nov 1998
Event	1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998 - San Jose, United States Duration: 8 Nov 1998 → 12 Nov 1998 https://dl.acm.org/doi/proceedings/10.1145/288548 (Conference proceedings)

Publication series

Name	IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
ISSN (Print)	1092-3152

Conference

Conference	1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998
Country/Territory	United States
City	San Jose
Period	8/11/98 → 12/11/98
Internet address	https://dl.acm.org/doi/proceedings/10.1145/288548 (Conference proceedings)

Scopus Subject Areas

Software
Computer Science Applications
Computer Graphics and Computer-Aided Design

Access to Document

10.1145/288548.289097

Cite this

Chen, C.-P., Chu, C. C. N., & Wong, D. F. (1998). Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation. In ICCAD '98: Proceedings of the 1998 IEEE/ACM International Conference on Computer-aided Design (pp. 617-624). (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers). Association for Computing Machinery (ACM). https://doi.org/10.1145/288548.289097

Chen, Chung-Ping ; Chu, Chris C. N. ; Wong, D. F. / Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation. ICCAD '98: Proceedings of the 1998 IEEE/ACM International Conference on Computer-aided Design. Association for Computing Machinery (ACM), 1998. pp. 617-624 (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers).

@inproceedings{f0ff19dd892d4e7cb6a2654f15e04145,

title = "Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation",

abstract = "This paper considers simultaneous gate and wire sizing for general VLSI circuits under the Elmore delay model. We present a fast and exact algorithm which can minimize total area subject to maximum delay bound. The algorithm can be easily modified to give exact algorithms for optimizing several other objectives (e.g. minimizing maximum delay or minimizing total area subject to arrival time specifications at all inputs and outputs). No previous algorithm for simultaneous gate and wire sizing can guarantee exact solutions for general circuits. Our algorithm is an iterative one with a guarantee on convergence to global optimal solutions. It is based on Lagrangian relaxation and `one-gate/wire-at-a-time' local optimizations, and is extremely economical and fast. For example, we can optimize a circuit with 27,648 gates and wires in about 36 minutes using under 23 MB memory on an IBM RS/6000 workstation.",

author = "Chung-Ping Chen and Chu, {Chris C. N.} and Wong, {D. F.}",

note = "This work was partly supported by the Texas Advanced Research Program under Grant No. 00365S2SS and by a grant from Intel Corporation.; 1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998 ; Conference date: 08-11-1998 Through 12-11-1998",

year = "1998",

month = nov,

day = "8",

doi = "10.1145/288548.289097",

language = "English",

isbn = "9781581130089",

series = "IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers",

publisher = "Association for Computing Machinery (ACM)",

pages = "617--624",

booktitle = "ICCAD '98",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/288548",

}

Chen, C-P, Chu, CCN & Wong, DF 1998, Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation. in ICCAD '98: Proceedings of the 1998 IEEE/ACM International Conference on Computer-aided Design. IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, Association for Computing Machinery (ACM), pp. 617-624, 1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998, San Jose, California, United States, 8/11/98. https://doi.org/10.1145/288548.289097

Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation. / Chen, Chung-Ping; Chu, Chris C. N.; Wong, D. F.
ICCAD '98: Proceedings of the 1998 IEEE/ACM International Conference on Computer-aided Design. Association for Computing Machinery (ACM), 1998. p. 617-624 (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers).

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

TY - GEN

T1 - Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation

AU - Chen, Chung-Ping

AU - Chu, Chris C. N.

AU - Wong, D. F.

N1 - This work was partly supported by the Texas Advanced Research Program under Grant No. 00365S2SS and by a grant from Intel Corporation.

PY - 1998/11/8

Y1 - 1998/11/8

N2 - This paper considers simultaneous gate and wire sizing for general VLSI circuits under the Elmore delay model. We present a fast and exact algorithm which can minimize total area subject to maximum delay bound. The algorithm can be easily modified to give exact algorithms for optimizing several other objectives (e.g. minimizing maximum delay or minimizing total area subject to arrival time specifications at all inputs and outputs). No previous algorithm for simultaneous gate and wire sizing can guarantee exact solutions for general circuits. Our algorithm is an iterative one with a guarantee on convergence to global optimal solutions. It is based on Lagrangian relaxation and `one-gate/wire-at-a-time' local optimizations, and is extremely economical and fast. For example, we can optimize a circuit with 27,648 gates and wires in about 36 minutes using under 23 MB memory on an IBM RS/6000 workstation.

AB - This paper considers simultaneous gate and wire sizing for general VLSI circuits under the Elmore delay model. We present a fast and exact algorithm which can minimize total area subject to maximum delay bound. The algorithm can be easily modified to give exact algorithms for optimizing several other objectives (e.g. minimizing maximum delay or minimizing total area subject to arrival time specifications at all inputs and outputs). No previous algorithm for simultaneous gate and wire sizing can guarantee exact solutions for general circuits. Our algorithm is an iterative one with a guarantee on convergence to global optimal solutions. It is based on Lagrangian relaxation and `one-gate/wire-at-a-time' local optimizations, and is extremely economical and fast. For example, we can optimize a circuit with 27,648 gates and wires in about 36 minutes using under 23 MB memory on an IBM RS/6000 workstation.

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

U2 - 10.1145/288548.289097

DO - 10.1145/288548.289097

M3 - Conference proceeding

AN - SCOPUS:0032318215

SN - 9781581130089

T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers

SP - 617

EP - 624

BT - ICCAD '98

PB - Association for Computing Machinery (ACM)

T2 - 1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998

Y2 - 8 November 1998 through 12 November 1998

ER -

Chen CP, Chu CCN, Wong DF. Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation. In ICCAD '98: Proceedings of the 1998 IEEE/ACM International Conference on Computer-aided Design. Association for Computing Machinery (ACM). 1998. p. 617-624. (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers). doi: 10.1145/288548.289097

Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this