{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:39:50Z","timestamp":1750307990923,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2004,6,7]],"date-time":"2004-06-07T00:00:00Z","timestamp":1086566400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>The continuous scaling of interconnect wires in deep submicron (DSM) circuits results in increased interconnect delay, power, and crosstalk noise. In this work, we develop a game-theoretic framework and multimetric optimization algorithms for the simultaneous optimization during wire sizing of (i) interconnect delay and crosstalk noise, and (ii) interconnect delay, power, and crosstalk noise. We formulate the wire sizing optimization problem as a normal form-game model and solve it using Nash equilibrium theory. Game theory allows the optimization of multiple metrics with conflicting objectives. This property is exploited in modeling the wire sizing problem while simultaneously optimizing various design parameters like interconnect delay, power, and crosstalk noise, which are conflicting in nature. The nets connecting the driving cell and the driven cell are divided into net segments. The net segments within a channel are modeled as players and the range of possible wire sizes forms the set of strategies. The payoff function is modeled (i) as the geometric mean of interconnect delay and crosstalk noise in the case of first formulation, and (ii) as the weighted sum of interconnect delay, power, and crosstalk noise in the second formulation. The net segments are optimized from the ones closest to the driven cell towards the ones at the driving cell. Complete information about the coupling effects among the nets is extracted after the detailed routing phase. The time and space complexities of the proposed wire sizing formulations are linear in terms of the number of net segments. Experimental results on several medium and large open-core designs indicate that the proposed algorithm for simultaneous optimization of interconnect delay and crosstalk noise yields an average reduction of 21.48% in interconnect delay and a 26.25% reduction in crosstalk noise without any area overhead, over and above the optimization from the Cadence place and route tools. It is shown through experimental results that the algorithm performs significantly better than simulated annealing and genetic search. Further, new simple but accurate models are developed for three parallel interconnect net segments. It is shown that these models yield the same level of accuracy with significantly better run times compared to the models reported in Chen et al. [2004]. A mathematical proof of existence for the Nash equilibrium solution for the proposed wire sizing formulation is also provided.<\/jats:p>","DOI":"10.1145\/1142980.1142988","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"711-739","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A game-theoretic framework for multimetric optimization of interconnect delay, power, and crosstalk noise during wire sizing"],"prefix":"10.1145","volume":"11","author":[{"given":"Narender","family":"Hanchate","sequence":"first","affiliation":[{"name":"University of South Florida, Tampa, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nagarajan","family":"Ranganathan","sequence":"additional","affiliation":[{"name":"University of South Florida, Tampa, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2004,6,7]]},"reference":[{"volume-title":"Proceedings of the ICCAD conference, 430--435","author":"Alpert C. J.","key":"e_1_2_1_1_1"},{"volume-title":"Circuits","author":"Bakoglu H. B.","key":"e_1_2_1_2_1"},{"volume-title":"Proceedings of the ISQED Confernce, 171--176","author":"Becer M. R.","key":"e_1_2_1_3_1"},{"volume-title":"Proceedings of the SRC Techcon Conference, 21--23","author":"Chang C. C.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2003.820529"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/383251.383256"},{"volume-title":"Proceedings of the ACM Design Automation Conference, 604--607","author":"Chung-Ping C.","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of the ICCAD Conference, 408--425","author":"Cong J.","key":"e_1_2_1_8_1"},{"volume-title":"Proceedings of the International Conference Computer-Aided Design, 478--485","author":"Cong J.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.986425"},{"key":"e_1_2_1_11_1","unstructured":"CRETE. Cadence repository for electronic technical education. http:\/\/crete.cadence.com.  CRETE. Cadence repository for electronic technical education. http:\/\/crete.cadence.com."},{"volume-title":"Modern Transmission Line Theory and Applications","author":"Dworsky L. N.","key":"e_1_2_1_12_1"},{"volume-title":"Applications: Introduction to the Theory of Games---Concepts, Methods, Applications","year":"1999","author":"Forgo F.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","unstructured":"GALib. GAlib---A C++ library of genetic algorithm components. http:\/\/lancet.mit.edu\/ga\/.  GALib. GAlib---A C++ library of genetic algorithm components. http:\/\/lancet.mit.edu\/ga\/."},{"volume-title":"Proceedings of the International Conference on VLSI Design. 10","year":"2006","author":"Hanchate N.","key":"e_1_2_1_15_1"},{"volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference, 373--378","author":"He J. A.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","first-page":"5","article-title":"Future CMOS scaling and reliability","volume":"81","author":"Hu C.","year":"1993","journal-title":"Proc. IEEE"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.863640"},{"key":"e_1_2_1_19_1","unstructured":"ITRS. 2004. International technology roadmap for semiconductors. http:\/\/public.itrs.net.  ITRS. 2004. International technology roadmap for semiconductors. http:\/\/public.itrs.net."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1215\/S0012-7094-41-00838-4","article-title":"A generalization of Brouwer's fixed point theorem","volume":"8","author":"Kakutani S.","year":"1941","journal-title":"Duke J. Math."},{"volume-title":"Cross-Talk Noise Immune VLSI Design using Regular Layout Fabrics","author":"Khatri S. P.","key":"e_1_2_1_21_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-1477-0"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2003.819566"},{"key":"e_1_2_1_23_1","first-page":"1","article-title":"Equilibrium points in n-person games","volume":"36","author":"Nash J. F.","year":"1950","journal-title":"Proceedings of the National Academy of Science of the Unitied States of America Conference"},{"key":"e_1_2_1_24_1","first-page":"2","article-title":"The bargaining problem","volume":"18","author":"Nash J. F.","year":"1950","journal-title":"Econometrica"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Neumann J. Von. 1928. Zur Theorie der Gesellschaftsspiele. Zur Theorie der Gesellschaftsspiele 295--320.  Neumann J. Von. 1928. Zur Theorie der Gesellschaftsspiele. Zur Theorie der Gesellschaftsspiele 295--320.","DOI":"10.1007\/BF01448847"},{"key":"e_1_2_1_26_1","unstructured":"Open Cores. Free open source IP cores and chip design. http:\/\/www.opencores.org.  Open Cores. Free open source IP cores and chip design. http:\/\/www.opencores.org."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"volume-title":"Proceedings of the ACM Symposium on the Theory of Computing, 749--753","year":"2001","author":"Papadimitriou C.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","unstructured":"Rahmat K. Nakagawa O. S. Oh S-Y. and Moll J. 1995. A scaling scheme for interconnect in deep submicron processes. In Tech. Rep. HPL-95-77 Hewlett-Packard Laboratories 1--4.  Rahmat K. Nakagawa O. S. Oh S-Y. and Moll J. 1995. A scaling scheme for interconnect in deep submicron processes. In Tech. Rep. HPL-95-77 Hewlett-Packard Laboratories 1--4."},{"volume-title":"Proceedings of the International Symposium on System Synthesis, 126--131","author":"Ranganathan N.","key":"e_1_2_1_30_1"},{"edition":"3","volume-title":"Games and Information: An Introduction to Game Theory","author":"Rasmusen E.","key":"e_1_2_1_31_1"},{"volume-title":"Proceedings of the ACM Conference, 104--113","year":"2001","author":"Roughgarden T.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","article-title":"Simple formulas for two- and three-dimensional capacitances","author":"Sakurai T.","year":"1983","journal-title":"IEEE Trans. Electron Devices ED-30, 183--185."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.511579"},{"key":"e_1_2_1_35_1","article-title":"Analysis of crosstalk in very high-speed LSI\/VLSIs using a coupled multi-conductor stripline model","author":"Seki S.","year":"1984","journal-title":"IEEE Trans. Microwave Theory Tech. MTT-32, 1715--1720."},{"volume-title":"Proceedings of the International Symposium on Low Power Electronics and Design, 295--302","author":"Shanbhag N.","key":"e_1_2_1_36_1"},{"volume-title":"Proceedings of the International Workshop on High-Level Design Validation and Testing, 53--57","author":"Shukla S. K.","key":"e_1_2_1_37_1"},{"volume-title":"Proceedings of the ICCAD Conference, 203--211","author":"Sylvester D.","key":"e_1_2_1_38_1"},{"volume-title":"Procedings of the International Symposium on Physical Design, 48--53","author":"Tang K. T.","key":"e_1_2_1_39_1"},{"volume-title":"Proceedings of the IEEE on symposium the Foundations of Computer Science, 416--425","year":"2002","author":"Vetta A.","key":"e_1_2_1_40_1"},{"volume-title":"Inductance, and Crosstalk Analysis","author":"Walker C. S.","key":"e_1_2_1_41_1"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1142980.1142988","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1142980.1142988","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:16Z","timestamp":1750259176000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1142980.1142988"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6,7]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1142980.1142988"],"URL":"https:\/\/doi.org\/10.1145\/1142980.1142988","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2004,6,7]]},"assertion":[{"value":"2004-06-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}