Optimal FPGA mapping and retiming with efficient initial state computation

ABSTRACT

For sequential circuits with given initial states, new equivalent initial states must be computed for retiming, which unfortunately is NP-hard. In this paper we propose a novel polynomial time algorithm for optimal FPGA mapping with forward retiming to minimize the clock period with guaranteed initial state computation. It enables a new methodology of separating forward retiming from backward retiming to avoid time-consuming iterations between retiming and initial state computation. Our algorithm compares very favorably with both of the conventional approaches of separate mapping followed by retiming [1, 8] and the recent approaches of combined mapping with retiming [12, 2]. It is also applicable to circuits with partial initial state assignment.

REFERENCES

• 1: J. Cong and Y. Ding. FlowMap' An Optimal Technology Mapping Algorithm for Delay Optimizationin Lookup-Table Based FPGA Designs. IEEE Trans. on Computer-Aided Design of Integrated Circuits And Systems, 13(1):1-12, 1994.
• 2: 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
• 3: J. Cong and C. Wu. Optimal FPGA Mapping and Retiming with Efficient Initial State Computation. UCLA-CSD 980016, Technique Report, March 1998.
• 4: G. Even, I. Y. Spillinger, and L. Stok. Retiming Revisited and Reversed. IEEE Trans. on Computer-Aided Design of Integrated Circuits And Systems, 15(3):348-357, 1996,
• 5: H. Fujiwara and S. Toida. The Complexity of Fault Detection: An Approach to Design for Testability. In FTCS-12, pages 101-108, 1982.
• 6: Sandip Kundu , Leendert M. Huisman , Indira Nair , Vijay S. Iyengar , Lakshmi N. Reddy, A Small Test Generator for Large Designs, Proceedings of the IEEE International Test Conference on Discover the New World of Test and Design, p.30-40, September 20-24, 1992
• 7: C. Legl, P. Vanbekbergen, and A. Wang. Retiming of Edge- Triggered Circuits with Multiple Clocks and Load Enables. In International Workshop on Logic Synthesis, 199Z
• 8: C. E. Leiserson and J. B. Saxe. Retiming Synchronous Circuitry. Algorithmica, 6:5-35, 1991.
• 9: Naresh Maheshwari , Sachin S. Sapatnekar, Minimum area retiming with equivalent initial states, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.216-219, November 09-13, 1997, San Jose, California, United States
• 10: 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.
• 11: G. D. Micheli. Synchronous Logic Synthesis: Algorithms for Cycle-Time Minimization. IEEE Trans. on Computer- Aided Design of Integrated Circuits And Systems, 10(1):63- 73, 1991.
• 12: 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]
• 13: E. Sentovich, K. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. Stephan, R. Brayton, and A. Sangiovanni-Vincent elli. SIS: A System for Sequential Circuit Synthesis. Electronics Research Laboratory, Memorandum No. UCB/ERL M92/41, 1992.
• 14: L. Stok , I. Spillinger , G. Even, Improving initialization through reversed retiming, Proceedings of the 1995 European conference on Design and Test, p.150, March 06-09, 1995
• 15: H. Touati and R. K. Brayton. Computing the Initial States of Retimed Circuits. IEEE Trans. on Computer-Aided Design of lntegrated Circuits And Systems, 12(1):157-162, 1993.
• 16: H. Touati, N. Shenoy, and A. Sangiovanni-Vincentelli. Retiming for Table-Lookup Field-Programmable Gate Arrays. In FPGA '92, pages 89-94, 1992.
• 17: H. Yotsuyanagi, S. Kajihara, and K. Kinoshita. Retiming for Sequential Circuits with a Specified Initial State and Its Application to Testability Enhancement. IEICE Trans. INF. F_4 SYST.,E78-D(7):861-867, July 1995.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

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

  J. Computer Applications

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

Keywords:
congestion, global routing, quadratic placement, relaxed pins, routing models, supply-demand