A new enhanced SPFD rewiring algorithm

ABSTRACT

This paper presents an in-depth study of the theory and algorithms for the SPFD-based (Set of Pairs of Functions to be Distinguished) rewiring, and explores the flexibility in the SPFD computation. Our contributions are in the following two areas: (1) We present a theorem and a related algorithm for more precise characterization of feasible SPFD-based rewiring. Extensive experimental results show that for LUT-based FPGAs, the rewiring ability of our new algorithm is 70% higher than SPFD-based local rewiring algorithms (SPFD-LR) [19][21] and 18% higher than the recently developed SPFD-based global rewiring algorithm (SPFD-GR)[20]. (2) In order to achieve more rewiring ability on certain selected wires used in various optimizations, we study the impact of using different atomic SPFD pair assignment methods during the SPFD-based rewiring. We develop several heuristic atomic SPFD pair assignment methods for area or delay minimization and show that they lead to 10% more selected rewiring ability than the random (or arbitrary) assignment methods. When combining (1) and (2) together, we can achieve 38.1% higher general rewiring ability.

REFERENCES

• 1: Altera. Quartus II Software Overview. http://www.altera.com/products/software/quartus2/qtsindex.html.
• 2: L. A. Entrena and K.-T. Cheng. Combinational and Sequential Logic Optimization by Redundancy Addition and Removal. IEEE Transaction on CAD of ICS, Vol. 14, No. 7, pp. 909--916, July 1995.
• 3: R. K. Brayton. Understanding SPFDs: A New Method for Specifying Flexibility. In International Workshop on Logic Synthesis, 1997.
• 4: Chih-Wei Chang , Chung-Kuan Cheng , Peter Suaris , Malgorzata Marek-Sadowska, Fast post-placement rewiring using easily detectable functional symmetries, Proceedings of the 37th conference on Design automation, p.286-289, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337420]
• 5: S.-C. Chang, M Marek-Sadowska, and K-T Cheng. Perturb and Simplify: Multilevel Boolean Network Optimizer. IEEE Trans CAD of ICAS, Vol. 15, No. 12, Dec 1996, pp. 1494--1504.
• 6: S.-C. Chang, K.-T. Cheng, N.-S. Woo, and M. Marek-Sadowska. Postlayout rewiring using alternative wires. IEEE Transaction on CAD of ICS, Vol. 16, No. 6, p. 587--96, June 1997.
• 7: 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]
• 8: P. Chong, Y. Jiang, S. Khatri, F. Mo, S. Sinha, and R. Brayton. Don't Care Wires in Logical/Physical Design. In International Workshop on Logic Synthesis, pp. 1--9, 2000.
• 9: Jason Cong , Yean-Yow Hwang, Simultaneous depth and area minimization in LUT-based FPGA mapping, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.68-74, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201322]
• 10: Jason Cong , Sung Kyu Lim, Edge separability based circuit clustering with application to circuit partitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.429-434, January 2000, Yokohama, Japan [doi>10.1145/368434.368728]
• 11: Jason Cong , John Peck , Yuzheng Ding, RASP: a general logic synthesis system for SRAM-based FPGAs, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.137-143, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228390]
• 12: Ric Chung-Yang Huang , Yucheng Wang , Kwang-Ting Chen, LIBRA—a library-independent framework for post-layout performance optimization, Proceedings of the 1998 international symposium on Physical design, p.135-140, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274555]
• 13: Jan-Min Hwang , Feng-Yi Chiang , TingTing Hwang, A re-engineering approach to low power FPGA design using SPFD, Proceedings of the 35th annual conference on Design automation, p.722-725, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277225]
• 14: 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]
• 15: Wolfgang Kunz , Prem R. Menon, Multi-level logic optimization by implication analysis, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.6-13, November 06-10, 1994, San Jose, California, United States
• 16: E. Sentovich, et. al. SIS: A System for Sequential Circuit Synthesis. Memorandum No. UCB/ERL M92/41, Dept. EECS, UC Berkeley, 1992.
• 17: Subarnarekha Sinha , Robert K. Brayton, Implementation and use of SPFDs in optimizing Boolean networks, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.103-110, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288584]
• 18: Fabio Somenzi. CUDD: CU Decision Diagram Package Release 2.3.0. Technique Report, Dept. of ECE, Univ. of Colorado at Boulder, 1998.
• 19: Shigeru Yamashita , Hiroshi Sawada , Akira Nagoya, A new method to express functional permissibilities for LUT based FPGAs and its applications, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.254-261, November 10-14, 1996, San Jose, California, United States
• 20: Jason Cong , Yizhou Lin , Wangning Long, SPFD-based global rewiring, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503060]
• 21: S. Sinha, R.K. Brayton. Improved Robust SPFD Computations. In International Workshop on Logic Synthesis, p. 156--161, 2001.
• 22: 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
• 23: J. Cong, Y. Lin and W. Long. New Advances in SPFD Rewiring. In UCLA CSD Tech. Report. May 2002.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments
  D.4 OPERATING SYSTEMS
      D.4.8 Performance

General Terms:
Algorithms, Experimentation, Theory