{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T17:45:21Z","timestamp":1777657521721,"version":"3.51.4"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,3,2]],"date-time":"2015-03-02T00:00:00Z","timestamp":1425254400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF CCF-1017864"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2015,3,2]]},"abstract":"<jats:p>\n            We develop a flat, analytic, and nonlinear placement algorithm,\n            <jats:italic>ePlace<\/jats:italic>\n            , which is more effective, generalized, simpler, and faster than previous works. Based on the analogy between placement instance and electrostatic system, we develop a novel placement density function\n            <jats:italic>eDensity<\/jats:italic>\n            , which models every object as positive charge and the density cost as the potential energy of the electrostatic system. The electric potential and field distribution are coupled with density using a well-defined Poisson's equation, which is numerically solved by spectral methods based on fast Fourier transform (FFT). Instead of using the conjugate gradient (CG) nonlinear solver in previous placers, we propose to use Nesterov's method which achieves faster convergence. The efficiency bottleneck on line search is resolved by predicting the steplength using a closed-form equation of Lipschitz constant. The placement performance is validated through experiments on the ISPD 2005 and ISPD 2006 benchmark suites, where ePlace outperforms all state-of-the-art placers (Capo10.5, FastPlace3.0, RQL, MAPLE, ComPLx, BonnPlace, POLAR, APlace3, NTUPlace3, mPL6) with much shorter wirelength and shorter or comparable runtime. On average, of all the ISPD 2005 benchmarks, ePlace outperforms the leading placer BonnPlace with 2.83% shorter wirelength and runs 3.05\u00d7 faster; and on average, of all the ISPD 2006 benchmarks, ePlace outperforms the leading placer MAPLE with 4.59% shorter wirelength and runs 2.84\u00d7 faster.\n          <\/jats:p>","DOI":"10.1145\/2699873","type":"journal-article","created":{"date-parts":[[2015,3,3]],"date-time":"2015-03-03T14:08:19Z","timestamp":1425391699000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":149,"title":["ePlace"],"prefix":"10.1145","volume":"20","author":[{"given":"Jingwei","family":"Lu","sequence":"first","affiliation":[{"name":"University of California, San Diego, La Jolla, CA"}]},{"given":"Pengwen","family":"Chen","sequence":"additional","affiliation":[{"name":"National Chung Hsing University, Taichung City, Taiwan"}]},{"given":"Chin-Chih","family":"Chang","sequence":"additional","affiliation":[{"name":"Cadence Design Systems, Inc., San Jose, CA"}]},{"given":"Lu","family":"Sha","sequence":"additional","affiliation":[{"name":"Cadence Design Systems, Inc., San Jose, CA"}]},{"given":"Dennis Jen-Hsin","family":"Huang","sequence":"additional","affiliation":[{"name":"Cadence Design Systems, Inc., San Jose, CA"}]},{"given":"Chin-Chi","family":"Teng","sequence":"additional","affiliation":[{"name":"Cadence Design Systems, Inc., San Jose, CA"}]},{"given":"Chung-Kuan","family":"Cheng","sequence":"additional","affiliation":[{"name":"University of California, San Diego, La Jolla, CA"}]}],"member":"320","published-online":{"date-parts":[[2015,3,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/996070.1009908"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.846363"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.892854"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055137.1055177"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1123008.1123055"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.923063"},{"key":"e_1_2_1_7_1","volume-title":"Approximation Algorithms for Bin Packing: A Survey","author":"Coffman E. G."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.2006158"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1687399.1687525"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/277044.277119"},{"key":"e_1_2_1_11_1","unstructured":"Eplace Homepage. 2014. http:\/\/vlsi-cuda.ucsd.edu\/&sim; ljw\/ePlace\/index.  Eplace Homepage. 2014. http:\/\/vlsi-cuda.ucsd.edu\/&sim; ljw\/ePlace\/index."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the System Level Interconnect Prediction Workshop (SLIP'11)","author":"Han S. K."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the IEEE International Symposium on Electromagnetic Compatibility (EMC'14)","author":"He Q."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCPMT.2011.2179547"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2024724.2024875"},{"key":"e_1_2_1_17_1","unstructured":"Itrs. 2011. http:\/\/www.itrs.net\/Links\/2011ITRS\/Home2011.htm.  Itrs. 2011. http:\/\/www.itrs.net\/Links\/2011ITRS\/Home2011.htm."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"A. B. Kahng J. Lienig I. L. Markov and J. Hu. 2010. VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer.   A. B. Kahng J. Lienig I. L. Markov and J. Hu. 2010. VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer.","DOI":"10.1007\/978-90-481-9591-6"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1123008.1123057"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Conference on Computer-Aided Design (ICCAD'10)","author":"Kim M.-C."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228496"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2160916.2160958"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Conference on Computer-Aided Design (ICCAD'13)","author":"Lin T."},{"key":"e_1_2_1_24_1","volume-title":"Fundamental research on electronic design automation in vlsi design - Routability. Masters thesis","author":"Lu J."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the IEEE International Conference on ASIC (ASICON'13)","author":"Lu J.","year":"2013"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593133"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2011.11.001"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2011.2168834"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference (ASPDAC'10)","author":"Lu J.","year":"2010"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the International Symposium on Quality Electronic Design (ISQED'13)","author":"Lu J.","year":"2013"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429384.2429441"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the ACM SIGGRAPH\/EUROGRAPHICS Conference on Graphics Hardware (HWWS'03)","author":"Moreland K."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1123008.1123042"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055137.1055182"},{"key":"e_1_2_1_35_1","unstructured":"W. C. Naylor R. Donelly and L. Sha. 2001. Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer. US Patent 6301693.  W. C. Naylor R. Donelly and L. Sha. 2001. Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer. US Patent 6301693."},{"key":"e_1_2_1_36_1","unstructured":"A. S. Nemirovskii and D. B. Yudin. 1983. Problem Complexity and Method Efficiency in Optimization. John Wiley and Sons.  A. S. Nemirovskii and D. B. Yudin. 1983. Problem Complexity and Method Efficiency in Optimization. John Wiley and Sons."},{"key":"e_1_2_1_37_1","unstructured":"Y. E. Nesterov. 1983. A method of solving a convex programming problem with convergence rate.  Y. E. Nesterov. 1983. A method of solving a convex programming problem with convergence rate."},{"key":"e_1_2_1_38_1","unstructured":"T. Ooura. 2001. General purpose fft package. http:\/\/www.kurims.kyoto-u.ac.jp\/&sim;ooura\/fft.html.  T. Ooura. 2001. General purpose fft package. http:\/\/www.kurims.kyoto-u.ac.jp\/&sim;ooura\/fft.html."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'05)","author":"Pan M."},{"key":"e_1_2_1_40_1","volume-title":"Numerical Recipes: The Art of Scientific Computing","author":"Press W. H.","year":"2007"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.855969"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the Annual Design Automation Conference (DAC'86)","author":"Sechen C."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455229.1455241"},{"key":"e_1_2_1_44_1","volume-title":"An introduction to the conjugate gradient method without the agonizing pain. Tech. rep. CMU-CS-TR-94-125","author":"Shewchuk J."},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"G. Skollermo. 1975. A fourier method for the numerical solution of poisson's equation. Math. Comput. 29 131 697--711.  G. Skollermo. 1975. A fourier method for the numerical solution of poisson's equation. Math. Comput. 29 131 697--711.","DOI":"10.1090\/S0025-5718-1975-0371096-4"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.925783"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/2485288.2485727"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055137.1055191"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278480.1278599"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2007.357975"},{"key":"e_1_2_1_51_1","unstructured":"L.-T. Wang Y.-W. Chang and K.-T. Cheng. 2009. Electronic Design Automation: Synthesis Verification and Test. Morgan Kaufmann San Fransisco.  L.-T. Wang Y.-W. Chang and K.-T. Cheng. 2009. Electronic Design Automation: Synthesis Verification and Test. Morgan Kaufmann San Fransisco."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488830"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055137.1055178"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593102"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCCAS.2013.6765395"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699873","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2699873","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:59Z","timestamp":1750227419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699873"}},"subtitle":["Electrostatics-Based Placement Using Fast Fourier Transform and Nesterov's Method"],"short-title":[],"issued":{"date-parts":[[2015,3,2]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,3,2]]}},"alternative-id":["10.1145\/2699873"],"URL":"https:\/\/doi.org\/10.1145\/2699873","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,2]]},"assertion":[{"value":"2013-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}