Benchmarking and Robustness of Gate Sizing Heuristics

We are looking into optimality of power optimization heuristics, specifically gate sizing. Gate sizing, along with gate length and Vt assignment, are important methods for physical design. They allow for an effective optimization method that can balance the power, delay and area costs. The importance of these methods highlights the importance of a systematic benchmarking and evaluation methodology to compare methods, and to gain an understanding of the “best-practices” for gate sizing. These questions are addressed in the research.

---

Empirical Benchmarking

By: Santiago Mok, advised by Prof. Puneet Gupta Objective: To investigate benchmarking alternatives and performance of post-layout gate sizing algorithm. The first step in this project is to enhance an open-source static timing engine. Spef-reading, Elmore wire delay calculation and power calculation are functions developed so far that serve as the infrastructure for gate sizing algorithm. The enhancement are integrated into OA Gear static timing engine. OA Gear is an open source toolkit based on Si2 OpenAccess. OpenAccess is an open source API built on C++ for IC CAD design and development.

• UCLA-Timer Enhanced Features:
  1. Elmore wire delay calculator with SPEF including a wire slew degradation model.
  2. A simple power calculator and extended parser functionalities to parse power related entries.
  3. Added support for reading units from .lib/SPEF and ensuring consistency.
  4. A simple Ceff calculation (disabled by default).
  5. Sensitivity-based gate sizing approaches: (updated 09/14/2009)
     • Power Sensitivity
     • Duet Sensitivity based on 1) power-delay and 2) power-slack
  • Download: UCLA-Timer (LICENSE) (subset of OA Gear, for full OA Gear refer to OAGear project page)

UCSD benchmarks for gate sizing can be found in this link: UC Benchmark Suite for Gate Sizing

---

Benchmarking using Synthetic Eyecharts

By: Amarnath Kasibhatla, advised by Prof. Puneet Gupta

Objective: Discrete gate sizing is one of the most commonly used, flexible, and powerful techniques for digital circuit optimization. The underlying problem has been proved to be NP-hard. Several (suboptimal) gate sizing heuristics have been proposed over the past two decades, but research has suffered from lack of any systematic way of assessing the quality of the proposed algorithms. We develop methods to generate benchmark circuits (called eyecharts) of arbitrary size along with their optimal solutions calculated using dynamic programming. We evaluate the suboptimalities of some popular gate sizing algorithms. Eyecharts help diagnose weaknesses of existing gate sizing algorithms, enable systematic and quantitative comparison of sizing algorithms, and catalyze further gate sizing research. Our results show that common sizing methods (including commercial tools) can be suboptimal by as much as 46% for realistic libraries and circuit topologies. The benchmarks and the code can be downloaded from EyeCharts.

---

Manufacturing-Aware Gate Sizing: Benchmarking and ECO-Awareness

By: John Lee, advised by Prof. Puneet Gupta

Objective: This research seeks to answer practical questions related to the gate sizing problem (1) what is the advantage of using a statistical power objective in gate sizing, and (2) how can gate sizing be used to perform late ECOs.

(1) In response to the increasing variations in integrated-circuit manufacturing, the current trend is to create designs that take these variations into account statistically. In this paper, we quantify the difference between the statistical and deterministic optima of leakage power while making no assumptions about the delay model.We develop a framework for deriving a theoretical upper bound on the suboptimality that is incurred by using the deterministic optimum as an approximation for the statistical optimum. We show that for the mean power measure, the deterministic optima is an excellent approximation, and for the mean plus standard deviation measures, the optimality gap increases as the amount of inter-die variation grows, for a suite of benchmark circuits in a 45 nm technology. For large variations, we show that there are excellent linear approximations that can be used to approximate the effects of variation. Therefore, the need to develop special statistical power optimization algorithms is questionable.

(2) Circuit design often runs in parallel with the development of the manufacturing process that will be used to fabricate it. However, as the manufacturing process matures, its models may undergo substantial changes as the design nears production. These changes may cause the design itself to fail its specifications, and in these cases it is necessary to perform an Engineering Change Order (ECO) to correct these problems. We present a new framework to perform incremental gate sizing for process changes late in the design cycle. This includes a method to measure and estimate ECO cost, transform these costs into a linear programming optimization problem, and solve the problem to find the ECO. This method performs well, compared to a leading commercial physical design tool, reducing ECO costs by 18% to 99% in changed area, and 1% to 96% in number of pins with unnecessary pin timing changes.

---

Publications:

[1] J. Lee and P. Gupta, “Impact of range and precision in technology on cell-based design,” in Proc. IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2012.
[Bibtex]

@inproceedings{C67,
author = {Lee, John and Gupta, Puneet},
booktitle = {{Proc. IEEE/ACM International Conference on Computer-Aided Design (ICCAD)}},
category = {C67},
keywords = {sizing},
month = {November},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/C67_paper.pdf},
slideurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/C67_slides.pdf},
title = {Impact of Range and Precision in Technology on Cell-Based Design},
year = {2012}
}


[2] J. Lee and P. Gupta, Discrete circuit optimization: library based gate sizing and threshold voltage assignment, Now Publishers, 2012.
[Bibtex]

@book{B2,
author = {Lee, J. and Gupta, P.},
isbn = {978-1-60198-542-2},
keywords = {sizing},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/B2_paper.pdf},
publisher = {Now Publishers},
title = {Discrete Circuit Optimization: Library Based Gate Sizing and Threshold Voltage Assignment},
year = {2012}
}


[3] J. Lee, “Implications of modern semiconductor technologies on gate sizing,” PhD Thesis, Department of Electrical Engineering, University of California Los Angeles, 2012.
[Bibtex]

@phdthesis{PHDTH2,
author = {Lee, John},
institution = {Department of Electrical Engineering, University of California Los Angeles},
keywords = {sizing},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/PHDTH2_paper.pdf},
title = {Implications of Modern Semiconductor Technologies on Gate Sizing},
year = {2012}
}


[4] S. Mok, J. Lee, and P. Gupta, “Discrete sizing for leakage power optimization in physical design: a comparative study,” ACM Transactions on Design Automation of Electronic Systems, 2012.
[Bibtex]

@article{J25,
author = {Santiago Mok and John Lee and Puneet Gupta},
journal = {{ACM Transactions on Design Automation of Electronic Systems}},
keywords = {sizing},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/J25_paper.pdf},
title = {Discrete Sizing for Leakage Power Optimization in Physical Design: A Comparative Study},
year = {2012}
}


[5] J. Lee and P. Gupta, “ECO Cost Measurement and Incremental Gate Sizing for Late Process Changes,” ACM Transactions on Design Automation of Electronic Systems, 2012.
[Bibtex]

@article{J24,
author = {John Lee and Puneet Gupta},
journal = {{ACM Transactions on Design Automation of Electronic Systems}},
keywords = {sizing},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/J24_paper.pdf},
title = {{ECO Cost Measurement and Incremental Gate Sizing for Late Process Changes}},
year = {2012}
}


[6] S. Mok, “Post-Layout Sizing for Leakage Power Optimization: A Comparative Study,” Department of Electrical Engineering, University of California Los Angeles 2011.
[Bibtex]

@techreport{MSTR4,
author = {Mok, Santiago},
institution = {Department of Electrical Engineering, University of California Los Angeles},
keywords = {sizing, msreport},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/MSTR4_paper.pdf},
title = {{Post-Layout Sizing for Leakage Power Optimization: A Comparative Study}},
year = {2011}
}


[7] J. Cong, P. Gupta, and J. Lee, “Evaluating Statistical Power Optimization,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 29, iss. 11, p. 1750–1762, 2010.
[Bibtex]

@article{J12,
author = {Cong, J. and Gupta, P. and Lee, John},
journal = {{IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)}},
keywords = {sizing, mad},
month = {Nov},
number = {11},
pages = {1750--1762},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/J12_paper.pdf},
title = {{Evaluating Statistical Power Optimization}},
volume = {29},
year = {2010}
}


[8] J. Lee and P. Gupta, “Incremental Gate Sizing for Late Process Changes,” in Proc. IEEE International Conference on Computer Design, 2010.
[Bibtex]

@inproceedings{C51,
author = {Lee, John and Gupta, Puneet},
booktitle = {{Proc. IEEE International Conference on Computer Design}},
category = {C51},
keywords = {sizing, mad},
month = {October},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/C51_paper.pdf},
slideurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/C51_slides.pdf},
title = {{I}ncremental {G}ate {S}izing for {L}ate {P}rocess {C}hanges},
year = {2010}
}


[9] P. Gupta, A. Kahng, A. Kasibhatla, and P. Sharma, “Eyecharts: Constructive Benchmarking of Gate Sizing Heuristics,” in Proc. ACM/IEEE Design Automation Conference (DAC), 2010.
[Bibtex]

@inproceedings{C50,
author = {Gupta, Puneet and Kahng, Andrew and Kasibhatla, Amarnath and Sharma, Puneet},
booktitle = {{Proc. ACM/IEEE Design Automation Conference (DAC)}},
category = {C50},
keywords = {sizing, eyecharts},
month = {June},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/C50_paper.pdf},
title = {{E}yecharts: {C}onstructive {B}enchmarking of {G}ate {S}izing {H}euristics},
year = {2010}
}


[10] A. Kasibhatla, “Eyecharts: Constructive Benchmarking of Gate Sizing Heuristics,” Department of Electrical Engineering, University of California Los Angeles 2010.
[Bibtex]

@techreport{MSTR3,
author = {Kasibhatla, Amarnath},
institution = {Department of Electrical Engineering, University of California Los Angeles},
keywords = {sizing, msreport},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/MSTR3_paper.pdf},
title = {{Eyecharts: Constructive Benchmarking of Gate Sizing Heuristics}},
year = {2010}
}


[11] J. Lee and P. Gupta, “Incremental gate sizing for late process changes,” in IEEE International Workshop on Design for Manufacturibility and Yield, 2010.
[Bibtex]

@conference{W7,
author = {Lee, John and Gupta, Puneet},
booktitle = {{IEEE International Workshop on Design for Manufacturibility and Yield}},
category = {W7},
keywords = {sizing},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/W7_paper.pdf},
slideurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/W7_slides.pdf},
title = {Incremental Gate Sizing for Late Process Changes},
year = {2010}
}


[12] J. Cong, P. Gupta, and J. Lee, “On the Futlity of Statistical Power Optimization,” in Proc. Asia and South Pacific Design Automation Conference, 2009.
[Bibtex]

@inproceedings{C38,
author = {Cong, J. and Gupta, P. and Lee, John},
booktitle = {{Proc. Asia and South Pacific Design Automation Conference}},
category = {C38},
keywords = {sizing, mad},
month = {January},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/C38_paper.pdf},
slideurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/C38_slides.pdf},
title = {On the {F}utlity of {S}tatistical {P}ower {O}ptimization},
year = {2009}
}


[13] V. Popuri, “Bias-driven Robust Analog Circuit Sizing Scheme,” Department of Electrical Engineering, University of California Los Angeles 2009.
[Bibtex]

@techreport{MSTR1,
author = {Popuri, Viswakiran},
institution = {Department of Electrical Engineering, University of California Los Angeles},
keywords = {sizing, msreport},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/MSTR1_paper.pdf},
title = {{Bias-driven Robust Analog Circuit Sizing Scheme}},
year = {2009}
}


[14] P. Gupta, A. B. Kahng, and S. Shah, “Standard Cell Library Optimization for Leakage Reduction,” in Proc. ACM/IEEE Design Automation Conference (DAC), 2006.
[Bibtex]

@inproceedings{C32,
author = {Gupta, P. and Kahng, A. B. and Shah, S.},
booktitle = {{Proc. ACM/IEEE Design Automation Conference (DAC)}},
category = {C32},
keywords = {sizing},
month = {July},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/C32_paper.pdf},
title = {Standard {C}ell {L}ibrary {O}ptimization for {L}eakage {R}eduction},
year = {2006}
}


[15] P. Gupta, A. B. Kahng, P. Sharma, and D. Sylvester, “Gate-Length Biasing for Runtime Leakage Control,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 2006.
[Bibtex]

@article{J4,
author = {Gupta, P. and Kahng, A. B. and Sharma, P. and Sylvester, D.},
category = {J4},
journal = {{IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)}},
keywords = {sizing, mad},
month = {June},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/J4_paper.pdf},
title = {Gate-{L}ength {B}iasing for {R}untime {L}eakage {C}ontrol},
year = {2006}
}


[16] P. Gupta, A. B. Kahng, and P. Sharma, “A Practical Transistor-Level Threshold Voltage Assignment Methodology,” in IEEE International Symposium on Quality Electronic Design, 2005, pp. 261-265.
[Bibtex]

@inproceedings{C18,
author = {Gupta, P. and Kahng, A. B. and Sharma, P.},
booktitle = {{IEEE International Symposium on Quality Electronic Design}},
category = {C18},
keywords = {sizing},
month = {March},
pages = {261-265},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/C18_paper.pdf},
title = {A {P}ractical {T}ransistor-{L}evel {T}hreshold {V}oltage {A}ssignment {M}ethodology},
year = {2005}
}


[17] P. Gupta, A. B. Kahng, P. Sharma, and D. D. Sylvester, “Selective Gate-Length Biasing for Cost-Effective Runtime Leakage Reduction,” in Proc. ACM/IEEE Design Automation Conference (DAC), 2004.
[Bibtex]

@inproceedings{C15,
author = {Gupta, P. and Kahng, A. B. and Sharma, P. and D. Sylvester, D.},
booktitle = {{Proc. ACM/IEEE Design Automation Conference (DAC)}},
category = {C5},
keywords = {sizing, mad},
month = {July},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/C15_paper.pdf},
title = {Selective {G}ate-{L}ength {B}iasing for {C}ost-{E}ffective {R}untime {L}eakage {R}eduction},
year = {2004}
}


[18] P. Gupta, A. B. Kahng, D. Sylvester, and J. Yang, “A Cost-Driven Lihographic Correction Methodology Based on Off-the-Shelf Sizing Tools,” in Proc. ACM/IEEE Design Automation Conference (DAC), 2003.
[Bibtex]

@inproceedings{C7,
author = {Gupta, P. and Kahng, A. B. and Sylvester, D. and Yang, J.},
booktitle = {{Proc. ACM/IEEE Design Automation Conference (DAC)}},
category = {C7},
keywords = {sizing, dats},
month = {June},
paperurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/C7_paper.pdf},
slideurl = {https://nanocad.ee.ucla.edu/pub/Main/Publications/C7_slides.pdf},
title = {A {C}ost-{D}riven {L}ihographic {C}orrection {M}ethodology {B}ased on {O}ff-the-{S}helf {S}izing {T}ools},
year = {2003}
}