Postplacement rewiring by exhaustive search for functional symmetries

ABSTRACT

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.

REFERENCES

• 1: S. N. Adya , S. Chaturvedi , J. A. Roy , D. A. Papa , I. L. Markov, Unification of partitioning, placement and floorplanning, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.550-557, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382639]
• 2: Aloul, F. A., Ramani, A., Markov, I. L., and Sakallah, K. A. 2003. Solving difficult instances of Boolean satisfiability in the presence of symmetry. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 22, 9, 1117--1137.
• 3: Valeria Bertacco , Maurizio Damiani, The disjunctive decomposition of logic functions, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.78-82, November 09-13, 1997, San Jose, California, United States
• 4: Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337549]
• 5: Andrew E. Caldwell , Igor L. Markov, Toward CAD-IP Reuse: A Web Bookshelf of Fundamental Algorithms, IEEE Design & Test, v.19 n.3, p.72-81, May 2002
• 6: Chai, D. and Kuehlmann, A. 2005. Building a better Boolean matcher and symmetry detector. In Proceedings of the IWLS. 391--398.
• 7: Chai, D. and Kuehlmann, A. 2006. A compositional approach to symmetry detection in circuits. In Proceedings of the IWLS. 228--234.
• 8: Chang, C.-W. J., Hsiao, M.-F., Hu, B., Wang, K., Marek-Sadowska, M., Cheng, C.-K., and Chen, S.-J. 2004. Fast postplacement optimization using functional symmetries. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 23, 1, 102--118.
• 9: Chih Wei Jim Chang , Malgorzata Marek-Sadowska, Single-pass redundancy addition and removal, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 10: Kai-hui Chang , I. L. Markov , V. Bertacco, Post-placement rewiring and rebuffering by exhaustive search for functional symmetries, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.56-63, November 06-10, 2005, San Jose, CA
• 11: 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.
• 12: Chang, S.-C., Cheng, K.-T., Woo, N. S., and Marek-Sadowska, M. 1997. Postlayout logic restructuring using alternative wires. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 16, 6, 587--596.
• 13: Shih-Chieh Chang , Lukas P. P. P. van Ginneken , Malgorzata Marek-Sadowska, Circuit Optimization by Rewiring, IEEE Transactions on Computers, v.48 n.9, p.962-970, September 1999 [doi>10.1109/12.795224]
• 14: Cong, J. and Long, W. 2001. Theory and algorithm for SPFD-based global rewiring. In Proceedings of the IWLS. 150--155.
• 15: Paul T. Darga , Mark H. Liffiton , Karem A. Sakallah , Igor L. Markov, Exploiting structure in symmetry detection for CNF, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996712]
• 16: Eén, N. and Sörensson, N. 2003. An extensible SAT-solver. In Proceedings of the SAT. 502--518.
• 17: GSRCBookshelf. 2007. http://vlsicad.eecs.umich.edu/BK.
• 18: Miloš Hrkić , John Lillis , Giancarlo Beraudo, An approach to placement-coupled logic replication, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996761]
• 19: IWLSBenchmarks. 2005. http://iwls.org/iwls2005/benchmarks.html.
• 20: Yi-Min Jiang , Angela Krstic , Kwang-Ting Cheng , Malgorzata Marek-Sadowska, Post-layout logic restructuring for performance optimization, Proceedings of the 34th annual conference on Design automation, p.662-665, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266313]
• 21: Victor N. Kravets , Karem A. Sakallah, Generalized symmetries in boolean functions, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 22: 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.
• 23: Mishchenko, A. 2003. Fast computation of symmetries in Boolean functions. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 22, 11, 1588--1593.
• 24: OpenCores. 2007. http://www.opencores.org/.
• 25: Shipra Panda , Fabio Somenzi , Bernard F. Plessier, Symmetry detection and dynamic variable ordering of decision diagrams, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.628-631, November 06-10, 1994, San Jose, California, United States
• 26: Pomeranz, I. and Reddy, S. M. 1994. On determining symmetries in inputs of logic circuits. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 13, 11, 1428--1434.
• 27: Saucy. 2007. http://vlsicad.eecs.umich.edu/bk/saucy/.
• 28: Guoqiang Wang , Andreas Kuehlmann , Alberto Sangiovanni-Vincentelli, Structural Detection of Symmetries in Boolean Functions, Proceedings of the 21st International Conference on Computer Design, p.498, October 13-15, 2003
• 29: Wllace, D. E. 2001. Recognizing input equivalence in digital logic. In Proceedings of the IWLS. 207--212.
• 30: Qinghong Wu , C. Y. Roger Chen , John M. Acken, Efficent Boolean Matching Algorithm for Cell Libraries, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.36-39, October 10-12, 1994
• 31: Yu-Liang Wu , Wangning Long , Hongbing Fan, A Fast Graph-Based Alternative Wiring Scheme for Boolean Networks, Proceedings of the 13th International Conference on VLSI Design, p.268, January 04-07, 2000

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design, Performance

Keywords:
VLSI, placement, rewiring