{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:42Z","timestamp":1750308762761,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T00:00:00Z","timestamp":1187308800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2007,8,17]]},"abstract":"<jats:p>We propose two new algorithms for rewiring: a postplacement optimization that reconnects pins of a given netlist without changing the logic function and gate locations. In the first algorithm, we extract small subcircuits consisting of several gates from the design and reconnect pins according to the symmetries of the subcircuits. To enhance the power of symmetry detection, we also propose a graph-based symmetry detector that can identify permutational and phase-shift symmetries on multiple input and output wires, as well as hybrid symmetries, creating abundant opportunities for rewiring. Our second algorithm, called long-range rewiring, is based on reconnecting equivalent pins and can augment the first approach for further optimization. We apply our techniques for wirelength optimization and observe that they provide wirelength reduction comparable to that achieved by detailed placement.<\/jats:p>","DOI":"10.1145\/1255456.1255469","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Postplacement rewiring by exhaustive search for functional symmetries"],"prefix":"10.1145","volume":"12","author":[{"given":"Kai-Hui","family":"Chang","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}]},{"given":"Igor L.","family":"Markov","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}]},{"given":"Valeria","family":"Bertacco","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}]}],"member":"320","published-online":{"date-parts":[[2008,5,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2004.1382639"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.816218"},{"volume-title":"Proceedings of the ICCAD. 78--82","author":"Bertacco V.","key":"e_1_2_1_3_1","unstructured":"Bertacco , V. and Damiani , M . 1997. The disjunctive decomposition of logic functions . In Proceedings of the ICCAD. 78--82 . Bertacco, V. and Damiani, M. 1997. The disjunctive decomposition of logic functions. In Proceedings of the ICCAD. 78--82."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/337292.337549"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/622209.623157"},{"volume-title":"Proceedings of the IWLS. 391--398","author":"Chai D.","key":"e_1_2_1_6_1","unstructured":"Chai , D. and Kuehlmann , A . 2005. Building a better Boolean matcher and symmetry detector . In Proceedings of the IWLS. 391--398 . Chai, D. and Kuehlmann, A. 2005. Building a better Boolean matcher and symmetry detector. In Proceedings of the IWLS. 391--398."},{"volume-title":"Proceedings of the IWLS. 228--234","author":"Chai D.","key":"e_1_2_1_7_1","unstructured":"Chai , D. and Kuehlmann , A . 2006. A compositional approach to symmetry detection in circuits . In Proceedings of the IWLS. 228--234 . Chai, D. and Kuehlmann, A. 2006. A compositional approach to symmetry detection in circuits. In Proceedings of the IWLS. 228--234."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.819904"},{"volume-title":"Proceedings of the ICCAD. 606--609","author":"Chang C.-W. J.","key":"e_1_2_1_9_1","unstructured":"Chang , C.-W. J. and Marek-Sadowska , M . 2001. Single-Pass redundancy addition and removal . In Proceedings of the ICCAD. 606--609 . Chang, C.-W. J. and Marek-Sadowska, M. 2001. Single-Pass redundancy addition and removal. In Proceedings of the ICCAD. 606--609."},{"volume-title":"Proceedings of the ICCAD. 56--63","author":"Chang K.-H.","key":"e_1_2_1_10_1","unstructured":"Chang , K.-H. , Markov , I. L. , and Bertacco , V . 2005. Post-Placement rewiring and rebuffering by exhaustive search for functional symmetries . In Proceedings of the ICCAD. 56--63 . Chang, K.-H., Markov, I. L., and Bertacco, V. 2005. Post-Placement rewiring and rebuffering by exhaustive search for functional symmetries. In Proceedings of the ICCAD. 56--63."},{"key":"e_1_2_1_11_1","unstructured":"Chang K.-H. Markov I. L. and Bertacco V. 2006. Keeping physical synthesis safe and sound. Tech. rep. CSE-TR-522-06 University of Michigan.  Chang K.-H. Markov I. L. and Bertacco V. 2006. Keeping physical synthesis safe and sound. Tech. rep. CSE-TR-522-06 University of Michigan."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.640617"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.795224"},{"volume-title":"Proceedings of the IWLS. 150--155","author":"Cong J.","key":"e_1_2_1_14_1","unstructured":"Cong , J. and Long , W . 2001. Theory and algorithm for SPFD-based global rewiring . In Proceedings of the IWLS. 150--155 . Cong, J. and Long, W. 2001. Theory and algorithm for SPFD-based global rewiring. In Proceedings of the IWLS. 150--155."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/996566.996712"},{"volume-title":"Proceedings of the SAT. 502--518","author":"E\u00e9n N.","key":"e_1_2_1_16_1","unstructured":"E\u00e9n , N. and S\u00f6rensson , N . 2003. An extensible SAT-solver . In Proceedings of the SAT. 502--518 . E\u00e9n, N. and S\u00f6rensson, N. 2003. An extensible SAT-solver. In Proceedings of the SAT. 502--518."},{"key":"e_1_2_1_17_1","unstructured":"GSRCBookshelf. 2007. http:\/\/vlsicad.eecs.umich.edu\/BK.  GSRCBookshelf. 2007. http:\/\/vlsicad.eecs.umich.edu\/BK."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/996566.996761"},{"key":"e_1_2_1_19_1","unstructured":"IWLSBenchmarks. 2005. http:\/\/iwls.org\/iwls2005\/benchmarks.html.  IWLSBenchmarks. 2005. http:\/\/iwls.org\/iwls2005\/benchmarks.html."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/266021.266313"},{"volume-title":"Proceedings of the ICCAD. 526--532","author":"Kravets V. N.","key":"e_1_2_1_21_1","unstructured":"Kravets , V. N. and Sakallah , K. A . 2000. Generalized symmetries in Boolean functions . In Proceedings of the ICCAD. 526--532 . Kravets, V. N. and Sakallah, K. A. 2000. Generalized symmetries in Boolean functions. In Proceedings of the ICCAD. 526--532."},{"key":"e_1_2_1_22_1","first-page":"1629","article-title":"A signal correlation guided circuit-SAT solver","volume":"10","author":"Lu F.","year":"2004","unstructured":"Lu , F. , Wang , L.-C. , Cheng , K.-T. T. , Moondanos , J. , and Hanna , Z. 2004 . A signal correlation guided circuit-SAT solver . J. UCS 10 , 12, 1629 -- 1654 . Lu, F., Wang, L.-C., Cheng, K.-T. T., Moondanos, J., and Hanna, Z. 2004. A signal correlation guided circuit-SAT solver. J. UCS 10, 12, 1629--1654.","journal-title":"J. UCS"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.818371"},{"key":"e_1_2_1_24_1","unstructured":"OpenCores. 2007. http:\/\/www.opencores.org\/.  OpenCores. 2007. http:\/\/www.opencores.org\/."},{"volume-title":"Proceedings of the ICCAD. 628--631","author":"Panda S.","key":"e_1_2_1_25_1","unstructured":"Panda , S. , Somenzi , F. , and Plessier , B . 1994. Symmetry detection and dynamic variable ordering of decision diagrams . In Proceedings of the ICCAD. 628--631 . Panda, S., Somenzi, F., and Plessier, B. 1994. Symmetry detection and dynamic variable ordering of decision diagrams. In Proceedings of the ICCAD. 628--631."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.329273"},{"key":"e_1_2_1_27_1","unstructured":"Saucy. 2007. http:\/\/vlsicad.eecs.umich.edu\/bk\/saucy\/.  Saucy. 2007. http:\/\/vlsicad.eecs.umich.edu\/bk\/saucy\/."},{"volume-title":"Proceedings of the ICCD. 498--503","author":"Wang G.","key":"e_1_2_1_28_1","unstructured":"Wang , G. , Kuehlmann , A. , and Sangiovanni-Vincentelli , A. L . 2003. Structural detection of symmetries in Boolean functions . In Proceedings of the ICCD. 498--503 . Wang, G., Kuehlmann, A., and Sangiovanni-Vincentelli, A. L. 2003. Structural detection of symmetries in Boolean functions. In Proceedings of the ICCD. 498--503."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the IWLS. 207--212","author":"Wllace D. E.","year":"2001","unstructured":"Wllace , D. E. 2001 . Recognizing input equivalence in digital logic . In Proceedings of the IWLS. 207--212 . Wllace, D. E. 2001. Recognizing input equivalence in digital logic. In Proceedings of the IWLS. 207--212."},{"volume-title":"Proceedings of the ICCD. IEEE Computer Society","author":"Wu Q.","key":"e_1_2_1_30_1","unstructured":"Wu , Q. , Chen , C. Y. R. , and Acken , J. M . 1994. Efficent Boolean matching algorithm for cell libraries . In Proceedings of the ICCD. IEEE Computer Society , Washington, DC, 36--39. Wu, Q., Chen, C. Y. R., and Acken, J. M. 1994. Efficent Boolean matching algorithm for cell libraries. In Proceedings of the ICCD. IEEE Computer Society, Washington, DC, 36--39."},{"volume-title":"Proceedings of the VLSI Design. 268--273","author":"Wu Y.-L.","key":"e_1_2_1_31_1","unstructured":"Wu , Y.-L. , Long , W. , and Fan , H . 2000. A fast graph-based alternative wiring scheme for Boolean networks . In Proceedings of the VLSI Design. 268--273 . Wu, Y.-L., Long, W., and Fan, H. 2000. A fast graph-based alternative wiring scheme for Boolean networks. In Proceedings of the VLSI Design. 268--273."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1255456.1255469","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1255456.1255469","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:28Z","timestamp":1750278148000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1255456.1255469"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8,17]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,8,17]]}},"alternative-id":["10.1145\/1255456.1255469"],"URL":"https:\/\/doi.org\/10.1145\/1255456.1255469","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2007,8,17]]},"assertion":[{"value":"2005-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}