{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T11:30:07Z","timestamp":1763724607984,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,12,10]],"date-time":"2022-12-10T00:00:00Z","timestamp":1670630400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["CCF-2041519 (CAREER), CCF-2021309 (SHF), and CCF-2011412 (SHF)"],"award-info":[{"award-number":["CCF-2041519 (CAREER), CCF-2021309 (SHF), and CCF-2011412 (SHF)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2023,1,31]]},"abstract":"<jats:p>Vectorless integrity verification is becoming increasingly critical to the robust design of nanoscale integrated circuits. This article introduces a general vectorless integrity verification framework that allows computing the worst-case voltage drops or temperature (gradient) distributions across the entire chip under a set of local and global workload (power density) constraints. To address the computational challenges introduced by the large power grids and three-dimensional mesh-structured thermal grids, we propose a novel spectral approach for highly scalable vectorless verification of large chip designs by leveraging a hierarchy of almost linear-sized spectral sparsifiers of input grids that can well retain effective resistances between nodes. As a result, the vectorless integrity verification solution obtained on coarse-level problems can effectively help compute the solution of the original problem. Our approach is based on emerging spectral graph theory and graph signal processing techniques, which consists of a graph topology sparsification and graph coarsening phase, an edge weight scaling phase, as well as a solution refinement procedure. Extensive experimental results show that the proposed vectorless verification framework can efficiently and accurately obtain worst-case scenarios in even very large designs.<\/jats:p>","DOI":"10.1145\/3529534","type":"journal-article","created":{"date-parts":[[2022,6,15]],"date-time":"2022-06-15T12:22:53Z","timestamp":1655295773000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Multilevel Spectral Framework for Scalable Vectorless Power\/Thermal Integrity Verification"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7239-6604","authenticated-orcid":false,"given":"Zhiqiang","family":"Zhao","sequence":"first","affiliation":[{"name":"Stevens Institute of Technology, Hoboken, New Jersey, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2989-2597","authenticated-orcid":false,"given":"Zhuo","family":"Feng","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology, Hoboken, New Jersey, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,12,10]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2492007.2492029"},{"key":"e_1_3_1_3_2","first-page":"7736","article-title":"A unifying framework for spectrum-preserving graph sparsification and coarsening","volume":"32","author":"Hermsdorff Gecia Bravo","year":"2019","unstructured":"Gecia Bravo Hermsdorff and Lee Gunderson. 2019. A unifying framework for spectrum-preserving graph sparsification and coarsening. In Advances in Neural Information Processing Systems, Volume 32, 7736\u20137747.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/347185"},{"key":"e_1_3_1_5_2","article-title":"Graph Coarsening with Neural Networks","author":"Cai Chen","year":"2021","unstructured":"Chen Cai, Dingkang Wang, and Yusu Wang. 2021. Graph Coarsening with Neural Networks. In International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=uxpzitPEooJ.","journal-title":"International Conference on Learning Representations"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/090775087"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1837274.1837292"},{"key":"e_1_3_1_9_2","first-page":"358","volume-title":"Proceedings of the IEEE International Conference on Computer-Aided Design (ICCAD\u201905)","author":"Najm D. Kouroussis, I. Ferzli, and F.","year":"2005","unstructured":"D. Kouroussis, I. Ferzli, and F. Najm. 2005. Incremental partitioning-based vectorless power grid verification. In Proceedings of the IEEE International Conference on Computer-Aided Design (ICCAD\u201905). 358\u2013364."},{"key":"e_1_3_1_10_2","volume-title":"CHOLMOD: Sparse Supernodal Cholesky Factorization and Update\/downdate","author":"Davis T.","year":"2008","unstructured":"T. Davis. 2008. CHOLMOD: Sparse Supernodal Cholesky Factorization and Update\/downdate. Retrieved from http:\/\/www.cise.ufl.edu\/research\/sparse\/cholmod\/."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2012.2215780"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2012.2211050"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488840"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897937.2898094"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3195970.3196114"},{"key":"e_1_3_1_16_2","first-page":"184","volume-title":"Proceedings of the Design Automation Conference (DAC\u201909)","author":"Ghani N.","year":"2009","unstructured":"N. Ghani and F. Najm. 2009. Fast vectorless power grid verification using an approximate inverse technique. In Proceedings of the Design Automation Conference (DAC\u201909). 184\u2013189."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2011.5763269"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2006.876103"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/775832.775861"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2833179.2833188"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502407792"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.858276"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2097308"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/110843563"},{"issue":"116","key":"e_1_3_1_26_2","first-page":"1","article-title":"Graph reduction with spectral and cut guarantees.","volume":"20","author":"Loukas Andreas","year":"2019","unstructured":"Andreas Loukas. 2019. Graph reduction with spectral and cut guarantees.J. Mach. Learn. Res. 20, 116 (2019), 1\u201342.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_1_27_2","first-page":"3237","volume-title":"International Conference on Machine Learning","author":"Loukas Andreas","year":"2018","unstructured":"Andreas Loukas and Pierre Vandergheynst. 2018. Spectrally approximating large graphs with smaller graphs. In International Conference on Machine Learning. PMLR, 3237\u20133246."},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2429384.2429530"},{"key":"e_1_3_1_29_2","volume-title":"IBM Power Grid Benchmarks","author":"Nassif S. R.","year":"2008","unstructured":"S. R. Nassif. 2008. IBM Power Grid Benchmarks. Retrieved from http:\/\/dropzone.tamu.edu\/ pli\/PGBench\/."},{"key":"e_1_3_1_30_2","unstructured":"Gurobi Optimization. 2016. Gurobi Optimizer. Retrieved from www. gurobi. com."},{"key":"e_1_3_1_31_2","volume-title":"Boundary Value Problems of Heat Conduction","author":"Ozisik M. Necati","year":"2002","unstructured":"M. Necati Ozisik. 2002. Boundary Value Problems of Heat Conduction. Courier Corporation."},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2006.879797"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623701"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.846370"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/100791142"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2012.2235192"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/980152.980157"},{"key":"e_1_3_1_38_2","article-title":"Algorithms, graph theory, and linear equations in laplacian matrices","author":"Spielman D.","year":"2010","unstructured":"D. Spielman. 2010. Algorithms, graph theory, and linear equations in laplacian matrices. In Proceedings of the International Congress of Mathematicians.","journal-title":"Proceedings of the International Congress of Mathematicians"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374456"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/1837274.1837484"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2014.2365520"},{"volume-title":"THU Power Grid Benchmarks","author":"Yang J.","key":"e_1_3_1_42_2","unstructured":"J. Yang and Z. Li. [n. d.]. THU Power Grid Benchmarks. Retrieved from http:\/\/tiger.cs.tsinghua.edu.cn\/PGBench\/."},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3061639.3062193"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3316781.3317809"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.23919\/DATE48585.2020.9116438"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2017.8203832"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3437963.3441767"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3529534","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3529534","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:24Z","timestamp":1750183764000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3529534"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,10]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,31]]}},"alternative-id":["10.1145\/3529534"],"URL":"https:\/\/doi.org\/10.1145\/3529534","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2022,12,10]]},"assertion":[{"value":"2021-12-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-29","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}