SPFD-based effective one-to-many rewiring (OMR) for delay reduction of LUT-based FPGA circuits

ABSTRACT

This paper proposes an innovative method for SPFD-based rewiring in Look-Up-Table-based (LUT-based) FPGA circuits. The new method adds new input wires to two or more LUT's in order to remove or to replace a target wire. There have been a few rewiring methods for FPGA circuits so far, such as the original SPFD-based optimization sometimes called Local Rewiring (LR), SPFD-based Global Rewiring (GR) and SPFD-based Enhanced Rewiring (ER). However, all of them replace one wire with other new input wire to one LUT but not with those to two or more LUT's. Moreover, the LR removes or replaces input wires with new one to the same LUT only, and the GR and ER topologically limit the LUT's where new input wires are added. Our new method, called One-to-Many Rewiring (OMR), loosens such topological constraints for more flexible FPGA circuit transformation so that it is easier to import constraints on physical design to the logic optimization. The experimental results show our OMR can transform FPGA circuits more flexibly than the LR, GR and ER, by introducing the new manipulation, wire addition. The OMR can rewire 1.2 times as many wires as the existing methods, especially, the ER. The computation time is as short as the existing methods.

REFERENCES

• 1: S. Muroga , Y. Kambayashi , H. C. Lai , J. N. Culliney, The Transduction Method-Design of Logic Networks Based on Permissible Functions, IEEE Transactions on Computers, v.38 n.10, p.1404-1424, October 1989 [doi>10.1109/12.35836]
• 2: X. Xiang and S. Muroga, "Synthesis of Multilevel Networks with Simple Gates," Int'l Workshop on Logic Synthesis, May. 1989.
• 3: S.Yang, "Logic Synthesis and Optimization Benchmarks User Guide Version 3.0," MCNC International Workshop on Logic Synthesis, 1991.
• 4: E. Sentovich, et. al., "SIS: A System for Sequential Circuit Synthesis," Memorandum of No. UCB/ERL M92/41, Dept. of EECS, UC Berkeley, 1992.
• 5: 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
• 6: L. A. Entrena and K. -T. Cheng, "Combinational and Sequential Logic Optimization by Redundancy Addition and Removal," IEEE Trans. on CAD of ICS, Vol. 14, No. 7, pp.909--916, Jul. 1995.
• 7: Shigeru Yamashita , Yahiko Kambayashi , Saburo Muroga, Optimization methods for lookup-table-based FPGAs using transduction method, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.54-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224921]
• 8: S.-C. Chang, M. Marek-Sadowska and K.-T Cheng, "Perturb and Simplify: Multilevel Boolean Network Optimizer," IEEE Trans. on CAD of ICAS, Vol. 15, No. 12, pp. 1494--1504, Dec. 1996.
• 9: 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]
• 10: S. -C. Chang, K. -T. Cheng, N. -S. Woo and M. Marek-Sadowska, "Postlayout rewiring using alternative wires," IEEE Trans. on CAD of ICS, Vol. 16, No. 6, pp.587--596, Jun. 1997.
• 11: 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]
• 12: 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]
• 13: S. Yamashita, H. Sawada and A. Nagoya, "SPFD: A New Method to Express Functional Flexibility," IEEE Trans. on CAD of ICAS, Vol. 19, No. 8, pp. 840--849, Aug. 2000.
• 14: 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]
• 15: Jason Cong , Joey Y. Lin , Wangning Long, A new enhanced SPFD rewiring algorithm, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.672-678, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774671]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

General Terms:
Algorithms, Design

Keywords:
SPFD, collaboration of logic and physical design, global rewiring (GR), logic optimization, one-to-many rewiring (OMR)