A hierarchy-driven FPGA partitioning method

ABSTRACT

This paper addresses an automatic partitioning method of adesign into several FPGAs. Although the circuit partitioningmethods have recently been significantly advanced, partitioningis commonly performed at the gate netlist level. To cope withlarge designs and explore the solution space efficiently,clustering of the logic is mandatory. In this paper, the hierarchyof the design, naturally introduced by the designer, guides thepartitioning. The basic concepts are introduced in terms of"envelope" delimiting hierarchy blocks. These concepts lead toan "envelope"-based clustering and to the proposed finalhierarchy-driven partitioning. Results are given on industrialexamples on XILINX 4000 technology.

REFERENCES

• 1: Charles J. Alpert , Andrew B. Kahng, Recent directions in netlist partitioning: a survey, Integration, the VLSI Journal, v.19 n.1-2, p.1-81, Aug. 1995 [doi>10.1016/0167-9260(95)00008-4]
• 2: D. Brasen, "Prototypage Automatique d'ASIC Sur FPGAs", PhD Thesis, Institut National Polytechnique de Grenoble, (1995).
• 3: T. Bui , C. Heigham , C. Jones , T. Leighton, Improving the performance of the Kernighan-Lin and simulated annealing graph bisection algorithms, Proceedings of the 26th ACM/IEEE conference on Design automation, p.775-778, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74527]
• 4: C-K. Cheng, Y-C. A. Wei, "An improved two-way partitioning algorithm with stable performance", IEEE Trans. on Computer-Aided Design of ICs and Systems, 10/12 (1991): 1502-1511.
• 5: 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]
• 6: 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
• 7: J. Garbers, H.J. Promel, A. Steger, "Finding Clusters in VLSI circuits", Proc. Int. Conf. on Computed-AidedDesign (1990): 520-523.
• 8: J. Hwang, E. Gamal, "Optimal Replication for rain-cut partitioning", IEEE Trans. on Computer-Aided Design of lCs and Systems,. 14/1 (1995): 96-106.
• 9: Frank M. Johannes, Partitioning of VLSI circuits and systems, Proceedings of the 33rd annual conference on Design automation, p.83-87, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240535]
• 10: B. Krishnamurthy, "An Improved Min-Cut Algorithm For Partitioning VLSI Networks", EEE Trans. on Computer-Aided Design of lCs and Systems, 33/5 (1984): 438-446.
• 11: Roman Kužnar , Franc Brglez, PROP: a recursive paradigm for area-efficient and performance oriented partitioning of large FPGA netlists, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.644-649, November 05-09, 1995, San Jose, California, United States
• 12: 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]
• 13: T.K. Ng, J. Oldfield, V. Pitchumani, "Improvements of A Mincut Partition Algorithm", Proc. Int. Conf. on Computed- Aided Design (1987): 470-473.
• 14: L. A. Sanchis, Multiple-Way Network Partitioning, IEEE Transactions on Computers, v.38 n.1, p.62-81, January 1989 [doi>10.1109/12.8730]
• 15: Ching-Wei Yeh , Chung-Kuan Cheng , Ting-Ting Y. Lin, A general purpose multiple way partitioning algorithm, Proceedings of the 28th conference on ACM/IEEE design automation, p.421-426, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127706]
• 16: Dirk Behrens , Klaus Harbich , Erich Barke, Hierarchical partitioning, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.470-477, November 10-14, 1996, San Jose, California, United States

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.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

  C. Computer Systems Organization

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

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