SPFD-based global rewiring

ABSTRACT

This paper presents the theory and algorithm for SPFD-based global rewiring (SPFD-GR). SPFD-GR allows us to globally replace a target wire with some alternative wire possibly far away from the target. It successfully overcomes the limitations of the existing SPFD-based local rewiring algorithm (SPFD-LR), which can only replace a wire with another wire that has the same destination node. In order to perform SPFD-based global rewiring, we developed the theory and algorithm for solving a fundamental problem in SPFD-based rewiring: Given the in-pin functions of a node and the SPFD at the node's out-pin, is there a way to modify the node's internal function so that the SPFD at the node's out-pin can be satisfied? Combined with a state-of-the-art partitioning algorithm, SPFD-GR scales well to large circuits with good synthesis quality. Our SPFD-based rewiring algorithm is ideal for LUT-based FPGAs, where the node's internal function can be changed freely without any area or delay penalty. Extensive experimental results show that for LUT-based FPGAs, the rewiring ability of SPFD-GR (in terms of the number of wires that have alternative wires) is 1.45, and 3 times that of SPFD-LR and an ATPG-based rewiring algorithm (with a preliminary experimental flow), respectively, while the run time is quite acceptable. When applied to the post-mapping area reduction for large LUT-based FPGAs under circuit depth restriction, SPFD-GR achieves 17.1% average area reduction, with no or little delay increase.

REFERENCES

• 1: Altera, Quartus II Software Overview, http:// www.altera.com/products/software/quartus2/qts-index.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: 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
• 21: Kuang-Chien Chen , Jason Cong , Yuzheng Ding , Andrew B. Kahng , Peter Trajmar, DAG-Map: Graph-Based FPGA Technology Mapping for Delay Optimization, IEEE Design & Test, v.9 n.3, p.7-20, July 1992 [doi>10.1109/54.156154]
• 22: J. Cong, Y. Lin, W. Long. SPFD-based Global Rewiring. In UCLA CSD Tech. Report. No.010043. Dec. 2001.

INDEX TERMS

Keywords:
FPGA synthesis, SPFD, SPFD-based global rewiring, logical re-synthesis