{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:56Z","timestamp":1750219856822,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2023,9,8]],"date-time":"2023-09-08T00:00:00Z","timestamp":1694131200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Young Scientist Project of MOE Innovation Platform, the State Key Laboratory of ASIC & System","award":["2021MS008"],"award-info":[{"award-number":["2021MS008"]}]},{"name":"MOST of Taiwan","award":["MOST 110-2224-E-002-012 and MOST 110-2221-E-002-177-MY3"],"award-info":[{"award-number":["MOST 110-2224-E-002-012 and MOST 110-2221-E-002-177-MY3"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>As design complexity keeps increasing, the 2.5D field-programmable gate array (FPGA) with large logic capacity has become popular in modern circuit applications. A 2.5D FPGA consists of multiple dies connected through super long lines (SLLs) on an interposer. Each die contains heterogeneous logic blocks and ASIC-like clocking architectures to achieve better skew and timing. Existing works consider these problems separately and thus may lead to serious timing issues or routing failure. This article presents an analytical placement algorithm for the 2.5D FPGA to simultaneously minimize the number of inter-die SLL signals and intra-die clocking violations. Using a lifting dimension technique, we first formulate the 2.5D global placement problem as a three-dimensional continuous and differential minimization problem, where the SLL-aware block distribution is modeled by 3D Poisson\u2019s equation and directly solved to obtain an analytical solution. Then, we further reformulate the minimization problem as a separable optimization problem with linear constraints. Based on the proximal alternating direction method of multipliers optimization method, we efficiently optimize the separable subproblems one by one in an alternating fashion. Finally, clock-aware legalization and detailed placement are applied to legalize and improve our placement results. Compared with the state-of-the-art works, experimental results show that our algorithm can resolve all clocking constraints and reduce the number of SLL crossing signals by 36.9% with similar wirelength in a comparable running time.<\/jats:p>","DOI":"10.1145\/3582554","type":"journal-article","created":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T12:01:24Z","timestamp":1675166484000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Analytical Placement with 3D Poisson\u2019s Equation and ADMM-based Optimization for Large-scale 2.5D Heterogeneous FPGAs"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1444-4281","authenticated-orcid":false,"given":"Min","family":"Wei","sequence":"first","affiliation":[{"name":"Fudan University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9057-9172","authenticated-orcid":false,"given":"Xingyu","family":"Tong","sequence":"additional","affiliation":[{"name":"Fudan University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0033-242X","authenticated-orcid":false,"given":"Yuan","family":"Wen","sequence":"additional","affiliation":[{"name":"Fudan University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5405-8441","authenticated-orcid":false,"given":"Jianli","family":"Chen","sequence":"additional","affiliation":[{"name":"Fudan University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4286-9292","authenticated-orcid":false,"given":"Jun","family":"Yu","sequence":"additional","affiliation":[{"name":"Fudan University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8698-0024","authenticated-orcid":false,"given":"Wenxing","family":"Zhu","sequence":"additional","affiliation":[{"name":"Fuzhou University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0564-5719","authenticated-orcid":false,"given":"Yao-Wen","family":"Chang","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taiwan"}]}],"member":"320","published-online":{"date-parts":[[2023,9,8]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"1","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201919)","author":"Chen Jianli","year":"2019","unstructured":"Jianli Chen, Wenxing Zhu, Jun Yu, Lei He, and Yao-Wen Chang. 2019. Analytical placement with 3D Poisson\u2019s equation and ADMM-based optimization for large-scale 2.5D heterogeneous FPGAs. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201919). IEEE, 1\u20138."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.2968892"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2015.2478280"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.3001392"},{"key":"e_1_3_1_6_2","first-page":"16","volume-title":"Proceedings of the 28th International Conference on Field Programmable Logic and Applications (FPL\u201918)","author":"Ravishankar Chirag","year":"2018","unstructured":"Chirag Ravishankar, Dinesh Gaitonde, and Trevor Bauer. 2018. Placement strategies for 2.5D FPGA fabric architectures. In Proceedings of the 28th International Conference on Field Programmable Logic and Applications (FPL\u201918). IEEE, 16\u2013164."},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.2970019"},{"key":"e_1_3_1_8_2","first-page":"1","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201918)","author":"Chen Shih-Chun","year":"2018","unstructured":"Shih-Chun Chen, Richard Sun, and Yao-Wen Chang. 2018. Simultaneous partitioning and signals grouping for time-division multiplexing in 2.5D FPGA-based systems. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201918). IEEE, 1\u20137."},{"key":"e_1_3_1_9_2","unstructured":"Xilinx. [n.d.]. Retrieved from http:\/\/www.xilinx.com."},{"key":"e_1_3_1_10_2","first-page":"922","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201917)","author":"Li Wuxi","year":"2017","unstructured":"Wuxi Li, Meng Li, Jiajun Wang, and David Z. Pan. 2017. UTPlaceF 3.0: A parallelization framework for modern FPGA global placement. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201917). IEEE, 922\u2013928."},{"key":"e_1_3_1_11_2","first-page":"17","volume-title":"Proceedings of the International Conference on Field Programmable Technology (ICFPT\u201917)","author":"Vercruyce Dries","year":"2017","unstructured":"Dries Vercruyce, Elias Vansteenkiste, and Dirk Stroobandt. 2017. Liquid: High quality scalable placement for large heterogeneous FPGAs. In Proceedings of the International Conference on Field Programmable Technology (ICFPT\u201917). IEEE, 17\u201324."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2021.3053191"},{"key":"e_1_3_1_13_2","first-page":"1","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201916)","author":"Pui Chak-Wa","year":"2016","unstructured":"Chak-Wa Pui, Gengjie Chen, Wing-Kai Chow, Ka-Chun Lam, Jian Kuang, Peishan Tu, Hang Zhang, Evangeline F. Y. Young, and Bei Yu. 2016. RippleFPGA: A routability-driven placement for large-scale heterogeneous FPGAs. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201916). IEEE, 1\u20138."},{"key":"e_1_3_1_14_2","first-page":"1","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201916)","author":"Pattison Ryan","year":"2016","unstructured":"Ryan Pattison, Ziad Abuowaimer, Shawki Areibi, Gary Gr\u00e9wal, and Anthony Vannelli. 2016. GPlace: A congestion-aware placement tool for ultrascale FPGAs. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201916). IEEE, 1\u20137."},{"key":"e_1_3_1_15_2","first-page":"106","volume-title":"Proceedings of International Symposium on Physical Design","author":"Kuo Wan-Sin","year":"2018","unstructured":"Wan-Sin Kuo, Shi-Han Zhang, Wai-Kei Mak, Richard Sun, and Yooh Kah Leow. 2018. Pin assignment optimization for multi-2.5D FPGA-based systems. In Proceedings of International Symposium on Physical Design. 106\u2013113."},{"key":"e_1_3_1_16_2","unstructured":"William C. Naylor Ross Donelly and Lu Sha. 2001. Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer October 9 2001. US Patent 6 301 693."},{"key":"e_1_3_1_17_2","first-page":"48","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201905)","author":"Pan Min","year":"2005","unstructured":"Min Pan, N. Viswanathan, and C. Chu. 2005. An efficient and effective detailed placement algorithm. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201905). 48\u201355."},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1981.1084903"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2012.2232708"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2012.2226584"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2012.2193582"},{"key":"e_1_3_1_22_2","first-page":"11","volume-title":"Proceedings of International Symposium on Physical Design","author":"Lu Jingwei","year":"2016","unstructured":"Jingwei Lu, Hao Zhuang, Ilgweon Kang, Pengwen Chen, and Chung-Kuan Cheng. 2016. ePlace-3D: Electrostatics based placement for 3D-ICs. In Proceedings of International Symposium on Physical Design. 11\u201318."},{"key":"e_1_3_1_23_2","unstructured":"IBM-PLACE. [n.d.]. Retrieved from http:\/\/er.cs.ucla.edu\/benchmarks\/ibm-place."},{"key":"e_1_3_1_24_2","first-page":"2:1\u20132:8","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201918)","author":"Zhu Wenxing","year":"2018","unstructured":"Wenxing Zhu, Zhipeng. Huang, Jianli. Chen, and Yao-Wen Chang. 2018. Analytical solution of Poisson\u2019s equation and its application to VLSI global placement. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201918). 2:1\u20132:8."},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.923063"},{"key":"e_1_3_1_26_2","first-page":"3:1\u20133:7","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201918)","author":"Chen Jianli","year":"2018","unstructured":"Jianli Chen, Li Yang, Zheng Peng, Wenxing Zhu, and Yao-Wen Chang. 2018. Novel proximal group ADMM for placement considering fogging and proximity effects. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201918). 3:1\u20133:7."},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004603514434"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2014.2304432"},{"key":"e_1_3_1_30_2","first-page":"163","article-title":"Determination approch\u00e9e d\u2019un point fixe d\u2019une application pseudo-contractante","author":"Martinet Bernard","year":"1972","unstructured":"Bernard Martinet. 1972. Determination approch\u00e9e d\u2019un point fixe d\u2019une application pseudo-contractante. Compte Rendu Academic des Science de Paris (1972), 163\u2013165.","journal-title":"Compte Rendu Academic des Science de Paris"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/153390.153393"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022503820909"},{"key":"e_1_3_1_33_2","first-page":"159","volume-title":"Proceedings of International Symposium on Physical Design","author":"Yang Stephen","year":"2017","unstructured":"Stephen Yang, Chandra Mulpuri, Sainath Reddy, Meghraj Kalase, Srinivasan Dasasathyan, Mehrdad E. Dehkordi, Marvin Tom, and Rajat Aggarwal. 2017. Clock-aware FPGA placement contest. In Proceedings of International Symposium on Physical Design. 159\u2013164."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2699873"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3582554","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3582554","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:16Z","timestamp":1750178836000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3582554"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,8]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3582554"],"URL":"https:\/\/doi.org\/10.1145\/3582554","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2023,9,8]]},"assertion":[{"value":"2022-08-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-29","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}