Performance-driven multi-level clustering with application to hierarchical FPGA mapping

ABSTRACT

In this paper, we study the problem of performance-driven multi-level circuit clustering with application to hierarchical FPGA designs. We first show that the performance-driven multi-level clustering problem is NP-hard (in contrast to the fact that single-level performance-driven clustering can be solved in polynomial time optimally). Then, we present an efficient heuristic for two-level clustering for delay minimization. It can also provide area-delay trade-off by controlling the amount of node duplication. The algorithm is applied to Altera's latest APEX FPGA architecture which has a two-level hierarchy. Experimental results with combinational circuits show that with our performance-driven two-level clustering solution we can improve the circuit performance produced by the Quartus Design System from Altera by an average of 15% for APEX devices measured in terms of delay after final layout. To our knowledge this is the first in-depth study for the performance-driven multi-level circuit clustering problem.

REFERENCES

• 1: Brayton R.K., Rudell R., and Sangiovanni-Vincenteli A.L. MIS: A Multiple-Level Logic Optimization, IEEE Transactions on CAD, pages 1062-1081, Nov. 1987
• 2: Jason Cong , Sung Kyu Lim , Chang Wu, Performance driven multi-level and multiway partitioning with retiming, Proceedings of the 37th conference on Design automation, p.274-279, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337418]
• 3: Jason Cong , Songjie Xu, Invited talk: synthesis challenges for next-generation high-performance and high-density PLDs, Proceedings of the 2000 conference on Asia South Pacific design automation, p.157-162, January 2000, Yokohama, Japan [doi>10.1145/368434.368596]
• 4: Jason Cong , Honching Li , Chang Wu, Simultaneous circuit partitioning/clustering with retiming for performance optimization, Proceedings of the 36th ACM/IEEE conference on Design automation, p.460-465, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309980]
• 5: Cong J. and Ding Y. FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup- Table Based FPGA Designs, IEEE Trans. On Computer- Aided Design, 1994, pages 1-12.
• 6: 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]
• 7: 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]
• 8: Cong J. and Romesis M. Performance-Driven Multi-Level Clustering with Application to Hierarchical FPGA Mapping. UCLA CSD Technical Report #010007.
• 9: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 10: D. J. -H. Huang , A. B. Kahng, When clusters meet partitions: new density-based methods for circuit decomposition, Proceedings of the 1995 European conference on Design and Test, p.60, March 06-09, 1995
• 11: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 12: Lawler E.L., Levitt K.N., and Turner J. Module Clustering to Minimize Delay in Digital Networks, IEEE Transactions on Computers, Vol. C-18, No.1, January 1966, page 47-57.
• 13: Murgai R., Brayton R.K., and Sangiovanni - Vincentelli A. On Clustering for Minimum Delay/Area, IEEE International Conference on Computer-Aided Design, November 1991, pages 6-9.
• 14: Pan P., Karandikar A.K., and Liu C.L. Optimal Clock Period Clustering for Sequential Circuits with Retiming. IEEE Trans. on Computer-Aided Design, pages 489-498, 1998.
• 15: Rajmohan Rajaraman , D. F. Wong, Optimal clustering for delay minimization, Proceedings of the 30th international conference on Design automation, p.309-314, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164907]
• 16: Wei Y.C. and Cheng C.K. Ratio cut partitioning for hierarchical designs. IEEE Trans. on Computer-Aided Design, pages 911-921, 1992.
• 17: Yang H.H. and Wong D.F. Circuit Clustering for Delay Minimization under Area and Pin Constraints, IEEE Transactions on Computer-Aided Design of Integrated Circuits, September 1997, pages 976-986.

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.2 DISCRETE MATHEMATICS

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

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