{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:54:46Z","timestamp":1759146886976,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,8,1]],"date-time":"2014-08-01T00:00:00Z","timestamp":1406851200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["133999\/2010-6, 313724\/2009-1, and 309047\/2012-9"],"award-info":[{"award-number":["133999\/2010-6, 313724\/2009-1, and 309047\/2012-9"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2014,8]]},"abstract":"<jats:p>Discrete gate sizing has attracted a lot of attention recently as the EDA industry faces the challenge of optimizing large standard cell-based circuits. The discrete nature of the problem, along with complex timing models, stringent design constraints, and ever-increasing circuit sizes, make the problem very difficult to tackle. Lagrangian Relaxation (LR) is an effective technique to handle complex constrained optimization problems and therefore has been successfully applied to solve the gate sizing problem. This article proposes an improved Lagrangian relaxation formulation for discrete gate sizing that relaxes timing, maximum gate input slew, and maximum gate output capacitance constraints. Based on such formulation, we propose a hybrid technique composed of three steps. First, a topological greedy heuristic solves the LR formulation. Such a heuristic is applied assuming a slightly increased target clock period (backoff factor) to better explore the solution space. Second, a delay recovery heuristic reestablishes the original target clock with small power overhead. Third, a power recovery heuristic explores the remaining slacks to further reduce power. Experiments on the ISPD 2012 Contest benchmarks show that our hybrid technique provides less leakage power than the state-of-the-art work for every circuit from the ISPD 2012 Contest infrastructure, achieving up to 24% less leakage. In addition, our technique achieves a much better compromise between leakage reduction and runtime, obtaining, on average, 9% less leakage power while running 8.8 times faster.<\/jats:p>","DOI":"10.1145\/2647956","type":"journal-article","created":{"date-parts":[[2014,8,26]],"date-time":"2014-08-26T12:08:55Z","timestamp":1409054935000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["A Hybrid Technique for Discrete Gate Sizing Based on Lagrangian Relaxation"],"prefix":"10.1145","volume":"19","author":[{"given":"Vinicius S.","family":"Livramento","sequence":"first","affiliation":[{"name":"Federal University of Santa Catarina, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chrystian","family":"Guth","sequence":"additional","affiliation":[{"name":"Federal University of Santa Catarina, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 Lu\u00eds","family":"G\u00fcntzel","sequence":"additional","affiliation":[{"name":"Federal University of Santa Catarina, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcelo O.","family":"Johann","sequence":"additional","affiliation":[{"name":"Federal University of Rio Grande do Sul, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,8,29]]},"reference":[{"volume-title":"Proceedings of the International Conference on Computer-Aided Design. 246--249","author":"Alpert C.","key":"e_1_2_1_1_1","unstructured":"C. Alpert , C. Chu , and P. G. Villarubia . 2007. The coming age of physical synthesis . In Proceedings of the International Conference on Computer-Aided Design. 246--249 . C. Alpert, C. Chu, and P. G. Villarubia. 2007. The coming age of physical synthesis. In Proceedings of the International Conference on Computer-Aided Design. 246--249."},{"volume-title":"Proceedings of the Design, Automation and Test in Europe Conference. 217--221","author":"Berkelaar M.","key":"e_1_2_1_2_1","unstructured":"M. Berkelaar and J. Jess . 1990. Gate sizing in mos digital circuits with linear programming . In Proceedings of the Design, Automation and Test in Europe Conference. 217--221 . M. Berkelaar and J. Jess. 1990. Gate sizing in mos digital circuits with linear programming. In Proceedings of the Design, Automation and Test in Europe Conference. 217--221."},{"key":"e_1_2_1_3_1","unstructured":"J. Bhasker and R. Chadha. 2009. Static Timing Analysis for Nanometer Designs. Springer.   J. Bhasker and R. Chadha. 2009. Static Timing Analysis for Nanometer Designs. Springer."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe. 2004. Convex Optimization. Cambridge University Press.   S. Boyd and L. Vandenberghe. 2004. Convex Optimization. Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.771182"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077603.1077642"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.645073"},{"volume-title":"Proceedings of the International Conference on Computer-Aided Design. 326--328","author":"Fishburn J. P.","key":"e_1_2_1_8_1","unstructured":"J. P. Fishburn and A. E. Dunlop . 1985. TILOS: A posynomial programming approach to transistor sizing . In Proceedings of the International Conference on Computer-Aided Design. 326--328 . J. P. Fishburn and A. E. Dunlop. 1985. TILOS: A posynomial programming approach to transistor sizing. In Proceedings of the International Conference on Computer-Aided Design. 326--328."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120725.1120881"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429384.2429428"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1960397.1960436"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"A. Kahng J. Lienig I. Markov and J. Hu. 2011. VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer.   A. Kahng J. Lienig I. Markov and J. Hu. 2011. VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer.","DOI":"10.1007\/978-90-481-9591-6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.851993"},{"volume-title":"Proceedings of the International Conference on Computer Design. 215--221","author":"Lee J.","key":"e_1_2_1_14_1","unstructured":"J. Lee and P. Gupta . 2010. Incremental gate sizing for late process changes . In Proceedings of the International Conference on Computer Design. 215--221 . J. Lee and P. Gupta. 2010. Incremental gate sizing for late process changes. In Proceedings of the International Conference on Computer Design. 215--221."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"J. Lee and P. Gupta. 2012. Discrete Circuit Optimization: Library Based Gate Sizing and Threshold Voltage Assignment. Now Publishers.  J. Lee and P. Gupta. 2012. Discrete Circuit Optimization: Library Based Gate Sizing and Threshold Voltage Assignment. Now Publishers.","DOI":"10.1561\/9781601985439"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.1993.393332"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429384.2429427"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2035575"},{"volume-title":"Proceedings of the Latin American Symposium on Circuits and Systems. 1--4.","author":"Livramento V. S.","key":"e_1_2_1_19_1","unstructured":"V. S. Livramento , C. Guth , J. L. Guntzel , and M. Johann . 2012. Evaluating the impact of slew on delay and power of neighboring gates in discrete gate sizing . In Proceedings of the Latin American Symposium on Circuits and Systems. 1--4. V. S. Livramento, C. Guth, J. L. Guntzel, and M. Johann. 2012. Evaluating the impact of slew on delay and power of neighboring gates in discrete gate sizing. In Proceedings of the Latin American Symposium on Circuits and Systems. 1--4."},{"volume-title":"Proceedings of the Design Automation and Test in Europe Conference. 1855--1860","author":"Livramento V. S.","key":"e_1_2_1_20_1","unstructured":"V. S. Livramento , C. Guth , J. L. Guntzel , and M. Johann . 2013. Fast and efficient lagrangian relaxation-based discrete gate sizing . In Proceedings of the Design Automation and Test in Europe Conference. 1855--1860 . V. S. Livramento, C. Guth, J. L. Guntzel, and M. Johann. 2013. Fast and efficient lagrangian relaxation-based discrete gate sizing. In Proceedings of the Design Automation and Test in Europe Conference. 1855--1860."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2390191.2390206"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/871506.871545"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2160916.2160950"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2012.2196279"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2011.6105409"},{"volume-title":"Proceedings of the Design, Automation, and Test in Europe Conference. 99--104","author":"Rahman M.","key":"e_1_2_1_26_1","unstructured":"M. Rahman and C. Sechen . 2012. Post-synthesis leakage power minimization . In Proceedings of the Design, Automation, and Test in Europe Conference. 99--104 . M. Rahman and C. Sechen. 2012. Post-synthesis leakage power minimization. In Proceedings of the Design, Automation, and Test in Europe Conference. 99--104."},{"volume-title":"Proceedings of the Design, Automation, and Test in Europe Conference. 1--4.","author":"Rahman M.","key":"e_1_2_1_27_1","unstructured":"M. Rahman , H. Tennakoon , and C. Sechen . 2011. Power reduction via near-optimal library-based cell-size selection . In Proceedings of the Design, Automation, and Test in Europe Conference. 1--4. M. Rahman, H. Tennakoon, and C. Sechen. 2011. Power reduction via near-optimal library-based cell-size selection. In Proceedings of the Design, Automation, and Test in Europe Conference. 1--4."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.895793"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/996566.996777"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/774572.774631"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.927758"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2647956","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2647956","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:40Z","timestamp":1750231180000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2647956"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.1145\/2647956"],"URL":"https:\/\/doi.org\/10.1145\/2647956","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2014,8]]},"assertion":[{"value":"2013-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}