research-article

Sensitivity-guided metaheuristics for accurate discrete gate sizing

Authors:

Andrew B. Kahng,

SeokHyeong Kang,

Myung-Chul Kim,

Igor L. MarkovAuthors Info & Claims

ICCAD '12: Proceedings of the International Conference on Computer-Aided Design

Pages 233 - 239

https://doi.org/10.1145/2429384.2429428

Published: 05 November 2012 Publication History

Abstract

The well-studied gate-sizing optimization is a major contributor to IC power-performance tradeoffs. Viable optimizers must accurately model circuit timing, satisfy a variety of constraints, scale to large circuits, and effectively utilize a large (but finite) number of possible gate configurations, including V_t and L_g. Within the research-oriented infrastructure used in the ISPD 2012 Gate Sizing Contest, we develop a metaheuristic approach to gate sizing that integrates timing and power optimization, and handles several types of constraints. Our solutions are evaluated using a rigorous protocol that computes circuit delay with Synopsys PrimeTime. Our implementation Trident outperforms the best-reported results on all but one of the ISPD 2012 benchmarks. Compared to the 2012 contest winner, we further reduce leakage power by an average of 43%.

References

[1]

D. Aldous and U. Vazirani, "'Go with the Winners' Algorithms", Proc. FOCS, 1994, pp. 492--501.

Digital Library

[2]

M. R. C. M. Berkelaar and J. A. G. Jess, "Gate Sizing in MOS Digital Circuits with Linear Programming", Proc. EURO-DAC, 1990, pp. 217--221.

Digital Library

[3]

K. D. Boese, A. B. Kahng and S. Muddu, "A New Adaptive Multi-Start Technique for Combinatorial Global Optimizations", Operations Research Letters 16(2) (1994), pp. 101--113.

Digital Library

[4]

C.-P. Chen, C. Chu and D. F. Wong, "Fast and Exact Simultaneous Gate and Wire Sizing by Lagrangian Relaxation", IEEE Trans. on CAD 18(7) (1999), pp. 1014--1025.

Digital Library

[5]

D. G. Chinnery and K. Keutzer, "Linear Programming for Sizing, V_th and V_dd Assignment", Proc. ISLPED, 2005, pp. 149--154.

Digital Library

[6]

H. Chou, Y.-H. Wang, and C. C.-P. Chen, "Fast and Effective Gate Sizing with Multiple-Vt Assignment Using Generalized Lagrangian Relaxation", Proc. ASP-DAC, 2005, pp. 381--386.

Digital Library

[7]

O. Coudert, "Gate Sizing for Constrained Delay/Power/Area Optimization", IEEE Trans. on VLSI Systems 5(4) (1997), pp. 465--472.

Digital Library

[8]

J. P. Fishburn and A. E. Dunlop, "Tilos: A Posynomial Programming Approach to Transistor Sizing", Proc. ICCAD, 1985, pp. 326--328.

[9]

T. F. Gonzalez (editor), Handbook of Approximation Algorithms and Metaheuristics, Chapman and Hall/CRC 2007.

Digital Library

[10]

P. Grassberger, "Go with the Winners: A General Monte Carlo Strategy", http://arxiv.org/pdf/cond-mat/0201313v1.pdf.

[11]

P. Gupta, A. B. Kahng, P. Sharma and D. Sylvester, "Selective Gate-Length Biasing for Cost-Effective Runtime Leakage Control", Proc. DAC, 2004, pp. 327--330.

Digital Library

[12]

P. Gupta, A. B. Kahng and P. Sharma, "A Practical Transistor-Level Dual Threshold Voltage Assignment Methodology", Proc. ISQED, 2005, pp. 421--426.

Digital Library

[13]

P. Gupta, A. B. Kahng, P. Sharma and D. Sylvester, "Gate-Length Biasing for Runtime-Leakage Control", IEEE Trans. on CAD 25(8) (2006), pp. 1475--1485.

Digital Library

[14]

S. Held, "Gate Sizing for Large Cell-Based Designs", Proc. DATE, 2009, pp. 827--832.

Digital Library

[15]

S. Hu, M. Ketkar and J. Hu, "Gate Sizing for Cell-Library-Based Designs", IEEE Trans. on CAD 28(6) (2009), pp. 818--825.

Digital Library

[16]

IWLS 2005 Benchmarks, http://iwls.org/iwls2005/benchmarks.html

[17]

K. Jeong, A. B. Kahng and H. Yao, "Revisiting the Linear Programming Framework for Leakage Power vs. Performance Optimization", Proc. ISQED, 2009, pp. 127--134.

Digital Library

[18]

W. N. Li, "Strongly NP-Hard Discrete Gate-Sizing Problems", IEEE Trans. on CAD 13(8) (1994), pp. 1045--1051.

Digital Library

[19]

Y. Liu and J. Hu, "A New Algorithm for Simultaneous Gate Sizing and Threshold Voltage Assignment", IEEE Trans. on CAD 29(2) (2010), pp. 223--234.

Digital Library

[20]

N. D. MacDonald, "Timing Closure in Deep Submicron Designs", DAC Knowledge Center Article, 2010.

[21]

O. Martin, S. W. Otto and E. W. Felten, "Large-Step Markov Chains for the Traveling Salesman Problem", Complex Systems 5(3) (1991), pp. 299--326.

[22]

M. M. Ozdal, S. Burns and J. Hu, "Gate Sizing and Device Technology Selection Algorithms for High-Performance Industrial Designs", Proc. ICCAD, 2011, pp. 724--731.

Digital Library

[23]

M. M. Ozdal, C. Amin, A. Ayupov, S. Burns, G. Wilke and C. Zhuo, "ISPD-2012 Discrete Cell Sizing Contest and Benchmark Suite", Proc. ISPD, 2012, pp. 161--164. http://archive.sigda.org/ispd/contests/12/ispd2012_contest.html

Digital Library

[24]

M. Rahman, H. Tennakoon and C. Sechen, "Power Reduction via Near-Optimal Library-Based Cell-Size Selection", Proc. DATE, 2011, pp. 867--870.

[25]

H. Ren and S. Dutt, "A Network-Flow Based Cell Sizing Algorithm", Proc. IWLS, 2008, pp. 7--14.

[26]

S. Roy, W. Chen, C. C.-P. Chen and Y. H. Hu, "Numerically Convex Forms and Their Application in Gate Sizing", IEEE Trans. on CAD 26(9) (2007), pp. 1637--1647.

Digital Library

[27]

S. S. Sapatnekar, V. B. Rao, P. M. Vaidya and S.-M. Kang, "An Exact Solution to the Transistor Sizing Problem for CMOS Circuits Using Convex Optimization", IEEE Trans. on CAD 12(11) (1993), pp. 1621--1634.

Digital Library

[28]

S. Shah, A. Srivastava, D. Sharma, D. Sylvester, D. Blaauw and V. Zolotov, "Discrete V_t Assignment and Gate Sizing Using a Self-Snapping Continuous Formulation", Proc. ICCAD, 2005, pp. 704--711.

Digital Library

[29]

A. Srivastava, D. Sylvester and D. Blaauw, "Power Minimization Using Simultaneous Gate Sizing, Dual-V_dd and Dual-V_th Assignment", Proc. DAC, 2004, pp. 783--787.

Digital Library

[30]

H. Tennakoon and C. Sechen, "Gate Sizing Using Lagrangian Relaxation Combined with a Fast Gradient-Based Pre-Processing Step", Proc. ICCAD, 2002, pp. 395--402.

Digital Library

[31]

J. Wang, D. Das and H. Zhou, "Gate Sizing by Lagrangian Relaxation Revisited", IEEE Trans. on CAD 28(7) (2009), pp. 1071--1084.

Digital Library

[32]

L. Wei, K. Roy and C. Koh, "Power Minimization by Simultaneous Dual-V_th Assignment and Gate-Sizing", Proc. CICC, 2000, pp. 413--416.

[33]

Synopsys PrimeTime User's Manual, http://www.synopsys.com.

Cited By

Cheng CHoltz CKahng ALin BMallappa U(2023)DAGSizer: A Directed Graph Convolutional Network Approach to Discrete Gate Sizing of VLSI GraphsACM Transactions on Design Automation of Electronic Systems10.1145/357701928:4(1-31)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1145/3577019
Lu YNath SPentapati SLim S(2023)ECO-GNN: Signoff Power Prediction Using Graph Neural Networks with Subgraph ApproximationACM Transactions on Design Automation of Electronic Systems10.1145/356994228:4(1-22)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1145/3569942
Mangiras DChinnery DDimitrakopoulos G(2023)Task-Based Parallel Programming for Gate SizingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.319749042:4(1309-1322)Online publication date: Apr-2023
https://doi.org/10.1109/TCAD.2022.3197490
Show More Cited By

Index Terms

Sensitivity-guided metaheuristics for accurate discrete gate sizing
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
  2. Very large scale integration design
    1. Application-specific VLSI designs

Recommendations

Gate sizing: finFETs vs 32nm bulk MOSFETs
DAC '06: Proceedings of the 43rd annual Design Automation Conference

FinFET devices promise to replace traditional MOSFETs because of superior ability in controlling leakage and minimizing short channel effects while delivering a strong drive current. We investigate in this paper gate sizing of finFET devices, and we ...
NBTI tolerance and leakage reduction using gate sizing

Leakage power is a major design constraint in deep submicron technology and below. Meanwhile, transistor degradation due to Negative Bias Temperature Instability (NBTI) has emerged as one of the main reliability concerns in nanoscale technology. Gate ...
Impact of channel length, gate insulator thickness, gate insulator material, and temperature on the performance of nanoscale FETs

Aggressive technology scaling as per Moore's law has led to elevated power dissipation levels owing to an exponential increase in subthreshold leakage power. Short channel effects (SCEs) due to channel length reduction, gate insulator thickness change, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '12: Proceedings of the International Conference on Computer-Aided Design

November 2012

781 pages

ISBN:9781450315739

DOI:10.1145/2429384

General Chair:
Alan J. Hu
Univ. of British Columbia, Vancouver, BC, Canada

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE CEDA

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

ICCAD '12

Sponsor:

SIGDA

ICCAD '12: The International Conference on Computer-Aided Design

November 5 - 8, 2012

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
197
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)7

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cheng CHoltz CKahng ALin BMallappa U(2023)DAGSizer: A Directed Graph Convolutional Network Approach to Discrete Gate Sizing of VLSI GraphsACM Transactions on Design Automation of Electronic Systems10.1145/357701928:4(1-31)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1145/3577019
Lu YNath SPentapati SLim S(2023)ECO-GNN: Signoff Power Prediction Using Graph Neural Networks with Subgraph ApproximationACM Transactions on Design Automation of Electronic Systems10.1145/356994228:4(1-22)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1145/3569942
Mangiras DChinnery DDimitrakopoulos G(2023)Task-Based Parallel Programming for Gate SizingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.319749042:4(1309-1322)Online publication date: Apr-2023
https://doi.org/10.1109/TCAD.2022.3197490
Wang ZGuo ZShi X(2023)A Variation-Aware Lagrangian Relaxation-Based Gate Sizing Framework for Timing Optimization2023 International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA59274.2023.10218448(309-313)Online publication date: 8-May-2023
https://doi.org/10.1109/ISEDA59274.2023.10218448
Zhang XDutt SBadaroglu MDutt S(2022)Limiting Interconnect Heating in Power-Driven Physical SynthesisProceedings of the 24th ACM/IEEE Workshop on System Level Interconnect Pathfinding10.1145/3557988.3569712(1-7)Online publication date: 3-Nov-2022
https://dl.acm.org/doi/10.1145/3557988.3569712
Zhang GLi BHuang XYin XZhuo CHashimoto MSchlichtmann U(2022)VirtualSync+: Timing Optimization With Virtual SynchronizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.315343341:12(5526-5540)Online publication date: Dec-2022
https://doi.org/10.1109/TCAD.2022.3153433
Kessler HBohlke Mda Rosa LPorto MCamargo V(2022)Calibration of Logical Effort Transistor Sizing for On-the-Fly Low-Power Supergate Design2022 IEEE 13th Latin America Symposium on Circuits and System (LASCAS)10.1109/LASCAS53948.2022.9789079(1-4)Online publication date: 1-Mar-2022
https://doi.org/10.1109/LASCAS53948.2022.9789079
Chabini NBelkouch SNajoui M(2022)An Algorithm for Gate Resizing to Reduce Power Dissipation in Combinational Digital Designs2022 IEEE 3rd International Conference on Electronics, Control, Optimization and Computer Science (ICECOCS)10.1109/ICECOCS55148.2022.9982942(1-3)Online publication date: 1-Dec-2022
https://doi.org/10.1109/ICECOCS55148.2022.9982942
Wang KCao PWang T(2022)A Graph Neural Network Method for Fast ECO Leakage Power OptimizationProceedings of the 27th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC52403.2022.9712486(196-201)Online publication date: 17-Jan-2022
https://dl.acm.org/doi/10.1109/ASP-DAC52403.2022.9712486
Mangiras DDimitrakopoulos G(2021)Incremental Lagrangian Relaxation Based Discrete Gate Sizing and Threshold Voltage AssignmentTechnologies10.3390/technologies90400929:4(92)Online publication date: 26-Nov-2021
https://doi.org/10.3390/technologies9040092
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents