{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T16:17:56Z","timestamp":1781885876231,"version":"3.54.5"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000028","name":"Semiconductor Research Corporation","doi-asserted-by":"publisher","award":["2008-TJ-1822"],"award-info":[{"award-number":["2008-TJ-1822"]}],"id":[{"id":"10.13039\/100000028","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>We introduce a technique that utilizes distributing computing resources for the efficient optimization of a traditional physical design problem. Specifically, we present a detailed placement strategy designed to exploit distributed computing environments, where the additional computing resources are employed in parallel to improve the optimization time. A Mixed Integer Programming (MIP) model and branch-and-cut optimization strategy are employed to solve the standard cell placement problem. By exploiting the problem structure, our algorithm improves upon the solutions afforded by existing optimization algorithms. First, an efficient batch-branching technique can eliminate several integer decision variables during each step of the optimization procedure. This batch-branching scheme can be performed serially or in parallel. In addition, custom cutting-planes are shown to significantly reduce the run time for optimizations as they efficiently refine the feasible region in order to quickly produce integer solutions. Our serial branch-and-cut strategies allow for significant reductions in wirelength, relative to the state-of-the-art commercial software package CPLEX, assuming a fixed allotment of time. Furthermore, we show that distributed computing resources can be used to significantly reduce the time required to achieve reductions in wirelength.<\/jats:p>","DOI":"10.1145\/1929943.1929950","type":"journal-article","created":{"date-parts":[[2011,4,6]],"date-time":"2011-04-06T16:08:07Z","timestamp":1302106087000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["A parallel branch-and-cut approach for detailed placement"],"prefix":"10.1145","volume":"16","author":[{"given":"Stephen","family":"Cauley","sequence":"first","affiliation":[{"name":"Purdue University, Northwestern Ave., IN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkataramanan","family":"Balakrishnan","sequence":"additional","affiliation":[{"name":"Purdue University, Northwestern Ave., IN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Y. Charlie","family":"Hu","sequence":"additional","affiliation":[{"name":"Purdue University, Northwestern Ave., IN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cheng-Kok","family":"Koh","sequence":"additional","affiliation":[{"name":"Purdue University, Northwestern Ave., IN"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,4,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Applegate D. Bixby R. Chvatal V. and Cook W. 1995. Finding cutis in the TSP (a preliminary report). Tech. rep. DIMACS Tchnical Report 95--05. Mar.   Applegate D. Bixby R. Chvatal V. and Cook W. 1995. Finding cutis in the TSP (a preliminary report). Tech. rep. DIMACS Tchnical Report 95--05. Mar."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1123008.1123055"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055137.1055177"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.923063"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1123008.1123057"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/981066.981084"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1987.1270301"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.884575"},{"key":"e_1_2_1_9_1","unstructured":"Luenberger D. 2003. Linear and Nonlinear Programming. Springer.  Luenberger D. 2003. Linear and Nonlinear Programming. Springer."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Mohan J. 1982. A study in parallel computation - the traveling salesman problem. Tech. rep. CMU-CS-82-136 Computer Science Department Carnegie Mellon University.  Mohan J. 1982. A study in parallel computation - the traveling salesman problem. Tech. rep. CMU-CS-82-136 Computer Science Department Carnegie Mellon University.","DOI":"10.21236\/ADA123327"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120725.1120865"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233501.1233537"},{"key":"e_1_2_1_13_1","unstructured":"Wagner H. 1975. Principles of Operational Research. Prentice-Hall.  Wagner H. 1975. Principles of Operational Research. Prentice-Hall."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Symposium on Circuits and Systems.","volume":"4","author":"Xing Z."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1929943.1929950","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1929943.1929950","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:32Z","timestamp":1750278392000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1929943.1929950"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.1145\/1929943.1929950"],"URL":"https:\/\/doi.org\/10.1145\/1929943.1929950","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3]]},"assertion":[{"value":"2009-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-04-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}