Multi-way system partitioning into a single type or multiple types of FPGAs

ABSTRACT

This paper considers the problem of partitioning a circuit into a collection of subcircuits, such that each subcircuit is feasible for some device from an FPGA library, and the total cost of devices is minimized. We propose a three-phase heuristic that uses ordering, clustering, and dynamic programming to achieve good solutions. Experimental comparisons are made with the previous methods of [4][9].

REFERENCES

• 1: C. J. Alpert , A. B. Kahng, Multi-way partitioning via spacefilling curves and dynamic programming, Proceedings of the 31st annual conference on Design automation, p.652-657, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196603]
• 2: C. J. Alpert , A. B. Kahng, A general framework for vertex orderings, with applications to netlist clustering, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.63-67, November 06-10, 1994, San Jose, California, United States
• 3: P. K. Chan, M. D. F. Schlag and J. Y. Zien, "Spectral K-Way Ratio-Cut Partitioning and Clustering", IEEE Trans. on CAD 13(9), Sept. 1994, pp. 1088-1096.
• 4: Nan-Chi Chou , Lung-Tien Liu , Chung-Kuan Cheng , Wei-Jin Dai , Rodney Lindelof, Circuit partitioning for huge logic emulation systems, Proceedings of the 31st annual conference on Design automation, p.244-249, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196365]
• 5: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 6: L. Hagen and A. B. Kahng, "New Spectral Methods for Ratio Cut Partitioning and Clustering", IEEE Trans. on CAD 11(9), Sept. 1992, pp. 1074-1085.
• 7: James Hwang , Abbas El Gamal, Optimal replication for min-cut partitioning, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.432-435, November 1992, Santa Clara, California, United States
• 8: C. Kring and A. R. Newton, "A Cell-Replication Appraoch to Mincut-Based Circuit Partitioning", Proc. IEEE Intl. Conf. on Computer-Aided Design, 1991, pp. 2-5.
• 9: Roman Kužnar , Franc Brglez , Krzysztof Kozminski, Cost minimization of partitions into multiple devices, Proceedings of the 30th international conference on Design automation, p.315-320, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164910]
• 10: Roman Kužnar , Franc Brglez , Baldomir Zajc, Multi-way netlist partitioning into heterogeneous FPGAs and minimization of total device cost and interconnect, Proceedings of the 31st annual conference on Design automation, p.238-243, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196364]
• 11: Wern-Jieh Sun , Carl Sechen, Efficient and effective placement for very large circuits, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.170-177, November 07-11, 1993, Santa Clara, California, United States
• 12: Nam Sung Woo , Jaeseok Kim, An efficient method of partitioning circuits for multiple-FPGA implementation., Proceedings of the 30th international conference on Design automation, p.202-207, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164669]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

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