FPGA synthesis with retiming and pipelining for clock period minimization of sequential circuits

ABSTRACT

In this paper, we present a new algorithm, named TurboSYN,for FPGA synthesis with retiming and pipelining to minimizethe clock period for sequential circuits.For a target clockperiod, since pipelining can eliminate all critical I/O paths,but not critical loops, we concentrate on FPGA synthesis toeliminate the critical loops.We combine the combinationalfunctional decomposition technique with retiming to performthe sequential functional decomposition, and incorporate itin the label computation of TurboMap to eliminate allcritical loops.The results show a significant improvementover the state-of-the-art FPGA mapping and resynthesis algorithms(1.7 ~ 2 times reduction on the clock period).Moreover,we develop a novel approach for positive loop detectionwhich leads to over 10 ~ 50 times speedup of the algorithm.As a result, TurboSYN can optimize sequential circuits ofover 10¿ gates and 10{3} flipflops in reasonable time.

REFERENCES

• 1: Altera. Flex 8000 and Flex 10000 Programmable Logic Device Family Data Sheets. 1995.
• 2: R. K. Brayton, R. Rudell, A. L. Sangiovanni-Vincentelli, and A. R. Wang. Mis: A multiple-level logic optimization system. IEEE Tans. on Computer-Aided Desing, 6(6):1062-1081, 1987.
• 3: Srimat T. Chakradhar , Sujit Dey , Miodrag Potkonjak , Steven G. Rothweiler, Sequential circuit delay optimization using global path delays, Proceedings of the 30th international conference on Design automation, p.483-489, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164991]
• 4: 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]
• 5: Jason Cong , Yuzheng Ding, Beyond the combinatorial limit in depth minimization for LUT-based FPGA designs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.110-114, November 07-11, 1993, Santa Clara, California, United States
• 6: J. Cong and Y. Ding. FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs. IEEE Trans. on Computer-Aided Design of Integrated Circuits And Systems, 13(1):1-12, 1994.
• 7: Jason Cong , Yuzheng Ding, Combinational logic synthesis for LUT based field programmable gate arrays, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.145-204, April 1996 [doi>10.1145/233539.233540]
• 8: 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]
• 9: Jason Cong , Yean-Yow Hwang, Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA design, Proceedings of the 33rd annual conference on Design automation, p.726-729, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240656]
• 10: 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]
• 11: Jason Cong , Chang Wu, An Improved Algorithm for Performance Optimal Technology Mapping with Retiming in LUT-Based FPGA Desig, Proceedings of the 1996 International Conference on Computer Design, VLSI in Computers and Processors, p.572-578, October 07-09, 1996
• 12: J. Cong and C. Wu. FPGA Synthesis with Retiming and Pipelining for Clock Period Minimization of Sequential Circuits. UCLA-CSD 970011, Technique Report, March 1997.
• 13: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 14: Yung-Te Lai , Kuo-Rueih Ricky Pan , Massoud Pedram, FPGA Synthesis Using Function Decomposition, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.30-35, October 10-12, 1994
• 15: Christian Legl , Bernd Wurth , Klaus Eckl, A Boolean approach to performance-directed technology mapping for LUT-based FPGA designs, Proceedings of the 33rd annual conference on Design automation, p.730-733, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240657]
• 16: C. E. Leiserson and J. B. Saxe. Retiming Synchronous Circuitry. Algorithmica, 6:5-35, 1991.
• 17: S. Malik, K. J. Singh, R. K. Brayton, and A. Sangiovanni-Vincentelli. Performance Optimization of Pipelined Logic Circuits Using Peripheral Retiming and Resynthesis. IEEE Trans. on Computer-Aided Design of Integrated Circuits And Systems, 12(5):568-578, 1993.
• 18: AT&:T Microelectronics. ATUT Field-Programmable Gate Arrays Data Book. 1995.
• 19: Peichen Pan , C. L. Liu, Optimal clock period FPGA technology mapping for sequential circuits, Proceedings of the 33rd annual conference on Design automation, p.720-725, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240655]
• 20: Peichen Pan , C. L. Liu, Technology mapping of sequential circuits for LUT-based FPGAs for performance, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.58-64, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228379]
• 21: Peichen Pan , C. L. Liu, Optimal clock period FPGA technology mapping for sequential circuits, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.3, p.437-462, July 1998 [doi>10.1145/293625.293632]
• 22: Marios C. Papaefthymiou, Understanding retiming through maximum average-delay cycles, Mathematical Systems Theory, v.27 n.1, p.65-84, Jan./Feb. 1994
• 23: E. Sentovich, K. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. Stephan, R. Brayton, and A. Sangiovanni-Vincentelli. SIS: A System for Sequential Circuit Synthesis. Electronics Research Laboratory, Memorandum No. UCB/ERL M92/41, 1992.
• 24: H. Touati, N. Shenoy, and A. Sangiovanni-Vincentelli. Retiming for Table-Lookup Field-Programmable Gate Arrays. In FPGA'92, pages 89-94, 1992.
• 25: U. Weinmann and W. Rosenstiel. Technology Mapping For Sequential Circuits Based On Retiming Techniques. In Proceedings of European Design Automation Conference, pages 318-323, 1993.
• 26: Bernd Wurth , Klaus Eckl , Kurt Antreich, Functional multiple-output decomposition: theory and an implicit algorithm, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.54-59, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217506]
• 27: Xilinx. The Programmable Logic Data Book. 1994.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory