{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T15:54:13Z","timestamp":1762876453509,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T00:00:00Z","timestamp":1697414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U19A2062"],"award-info":[{"award-number":["U19A2062"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2023,11,30]]},"abstract":"<jats:p>With the continuous shrinking of feature size, detection of lithography hotspots has been raised as one of the major concerns in Design-for-Manufacturability (DFM) of semiconductor processing. Hotspot detection, along with other DFM measures, trades off turnaround time for the yield of IC manufacturing, and thus a simplified but wide-ranging pattern definition is a key to the problem. Layout pattern clustering methods, which group geometrically similar layout clips into clusters, have been vastly proposed to identify layout patterns efficiently. To minimize the clustering number for subsequent DFM processing, in this article, we propose a geometric-matching-based clip relocation technique to increase the opportunity of pattern clustering. Particularly, we formulate the lower bound of the clustering number as a maximum-clique problem, and we have also proved that the clustering problem can be solved by the result of the maximum-clique very efficiently. Compared with the experimental results of the state-of-the-art approaches on ICCAD 2016 Contest benchmarks, the proposed method can achieve the optimal solutions for all benchmarks with very competitive runtime. To evaluate the scalability, the ICCAD 2016 Contest benchmarks are extended and evaluated. Moreover, experimental results on the extended benchmarks demonstrate that our method can reduce the cluster number by 16.59% on average, while the runtime is 74.11% faster on large-scale benchmarks compared with previous works.<\/jats:p>","DOI":"10.1145\/3610293","type":"journal-article","created":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T12:15:22Z","timestamp":1690200922000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A General Layout Pattern Clustering Using Geometric Matching-based Clip Relocation and Lower-bound Aided Optimization"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3516-3171","authenticated-orcid":false,"given":"Xu","family":"He","sequence":"first","affiliation":[{"name":"Hunan University, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-3652-0424","authenticated-orcid":false,"given":"Yao","family":"Wang","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4201-9985","authenticated-orcid":false,"given":"Zhiyong","family":"Fu","sequence":"additional","affiliation":[{"name":"Hunan University, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-3893-0594","authenticated-orcid":false,"given":"Yipei","family":"Wang","sequence":"additional","affiliation":[{"name":"Hunan University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9050-0866","authenticated-orcid":false,"given":"Yang","family":"Guo","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, China"}]}],"member":"320","published-online":{"date-parts":[[2023,10,16]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"1","volume-title":"Proceedings of the 54th Annual Design Automation Conference (DAC\u201917)","author":"Chang Wei-Chun","year":"2017","unstructured":"Wei-Chun Changet al. 2017. iClaire: A fast and general layout pattern classification algorithm. In Proceedings of the 54th Annual Design Automation Conference (DAC\u201917). 1\u20136."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2019.2917849"},{"key":"e_1_3_1_4_2","first-page":"1","volume-title":"Proceedings of the 54th Annual Design Automation Conference (DAC\u201917)","author":"Chen Kuan-Jung","year":"2017","unstructured":"Kuan-Jung Chen, Yu-Kai Chuang, Bo-Yi Yu, and Shao-Yun Fang. 2017. Minimizing cluster number with clip shifting in hotspot pattern classification. In Proceedings of the 54th Annual Design Automation Conference (DAC\u201917). 1\u20136."},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/1950815.1950963"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2016.2638440"},{"key":"e_1_3_1_7_2","first-page":"90530E","volume-title":"Design-Process-Technology Co-optimization for Manufacturability VIII","author":"Gao Jhih-Rong","year":"2014","unstructured":"Jhih-Rong Gao, Bei Yu, and David Z. Pan. 2014. Accurate lithography hotspot detection based on PCA-SVM classifier with hierarchical data clustering. In Design-Process-Technology Co-optimization for Manufacturability VIII, Vol. 9053. International Society for Optics and Photonics, 90530E."},{"key":"e_1_3_1_8_2","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"e_1_3_1_10_2","article-title":"Lithography hotspot detection with FFT-based feature extraction and imbalanced learning rate","author":"He Xu","year":"2019","unstructured":"Xu He, Yu Deng, Shizhe Zhou, Rui Li, Yao Wang, and Yang Guo. 2019. Lithography hotspot detection with FFT-based feature extraction and imbalanced learning rate. ACM Trans. Des. Autom. Electr. Syst. (2019).","journal-title":"ACM Trans. Des. Autom. Electr. Syst."},{"key":"e_1_3_1_11_2","first-page":"304","volume-title":"Proceedings of the IEEE 38th International Conference on Computer Design (ICCD\u201920)","author":"He Xu","year":"2020","unstructured":"Xu He, Yipei Wang, Zhiyong Fu, Yao Wang, and Yang Guo. 2020. Maximum clique based method for optimal solution of pattern classification. In Proceedings of the IEEE 38th International Conference on Computer Design (ICCD\u201920). 304\u2013311."},{"key":"e_1_3_1_12_2","first-page":"569","article-title":"An improved branch and bound algorithm for the maximum clique problem","volume":"58","author":"Konc Janez","year":"2007","unstructured":"Janez Koncet al. 2007. An improved branch and bound algorithm for the maximum clique problem. MATCH Commun. Math. Comput. Chem. 58 (2007), 569\u2013590.","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.09.028"},{"key":"e_1_3_1_14_2","unstructured":"Daniel Leskosky. Largest Rectangle in Histogram. Retrieved from https:\/\/www.danielleskosky.com\/largest-rectangle-in-histogram\/."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488817"},{"key":"e_1_3_1_16_2","volume-title":"Automatic IC Hotspot Classification and Detection Using Pattern-based Clustering","author":"Ma Ning","year":"2009","unstructured":"Ning Ma. 2009. Automatic IC Hotspot Classification and Detection Using Pattern-based Clustering. University of California, Berkeley."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1117\/1.JMM.15.4.043507"},{"key":"e_1_3_1_18_2","article-title":"CHIP: Clustering hotspots in layout using integer programming","volume":"2019","author":"Takkala Rohit Reddy","year":"2019","unstructured":"Rohit Reddy Takkalaet al. 2019. CHIP: Clustering hotspots in layout using integer programming. J. Electr. Comput. Eng. 2019 (2019).","journal-title":"J. Electr. Comput. Eng."},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2015.2406854"},{"key":"e_1_3_1_20_2","first-page":"41","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD)","author":"Topaloglu Rasit O.","year":"2016","unstructured":"Rasit O. Topaloglu. 2016. ICCAD-2016 CAD contest in pattern classification for integrated circuit design space analysis and benchmark suite. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD). 41."},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2014.2351273"},{"key":"e_1_3_1_22_2","first-page":"512","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201917)","author":"Woo Mingyu","year":"2017","unstructured":"Mingyu Wooet al. 2017. GRASP based metaheuristics for layout pattern classification. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201917). 512\u2013518."},{"key":"e_1_3_1_23_2","first-page":"1","volume-title":"Proceedings of the International Symposium on VLSI Design, Automation and Test (VLSI-DAT\u201918)","author":"Wu Yan-Shiun","year":"2018","unstructured":"Yan-Shiun Wuet al. 2018. MapReduce-based pattern classification for design space analysis. In Proceedings of the International Symposium on VLSI Design, Automation and Test (VLSI-DAT\u201918). 1\u20134."},{"key":"e_1_3_1_24_2","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201907)","author":"Xu Jingyu","year":"2007","unstructured":"Jingyu Xu, Subarna Sinha, and Charles C. Chiang. 2007. Accurate detection for process-hotspots with vias and incomplete specification. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201907)."},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.3015903"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2837078"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228576"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3610293","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3610293","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:02Z","timestamp":1750182542000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3610293"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,16]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,11,30]]}},"alternative-id":["10.1145\/3610293"],"URL":"https:\/\/doi.org\/10.1145\/3610293","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2023,10,16]]},"assertion":[{"value":"2022-09-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-15","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}