Multi-way FPGA partitioning by fully exploiting design hierarchy

ABSTRACT

In this paper, we present a new integrated synthesisand partitioning method for multiple-FPGA applications.This method first synthesizes a design specificationin a fine-grained way so that functional clusters can bepreserved based on the structural nature of the designspecification.Then, it applies a hierarchical set-coveringpartitioning method to form the final FPGA partitionings.Our approach bridges the gap between HDL synthesisand physical partitioning by fully exploiting the designhierarchy.Experimental results on a number of benchmarksand industrial designs demonstrate that I/O limitsare the bottleneck for CLB utilization when applying atraditional multiple-FPGA synthesis method on flattenednetlists.In contrast, by fully exploiting the design structuralhierarchy during the multiple-FPGA partitioning,our proposed method produces fewer FPGA partitionswith higher CLB and low I/O-pin utilizations.

REFERENCES

• 1: Michael Butts , Jon Batcheller , Joseph Varghese, An Efficient Logic Emulation System, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.138-141, October 11-14, 1992
• 2: C. E. Cox and W. E. Blan% "GANGLION- A Fast Field- Programmable Gate Array Implementation of a Connectionist Classifier," IEEE Journal on Solid-State Circuits, vol. 27, pp. 288-299, March 1992.
• 3: Stephen Walters, Computer-Aided Prototyping for ASIC-Based Systems, IEEE Design & Test, v.8 n.2, p.4-10, April 1991 [doi>10.1109/54.82034]
• 4: 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]
• 5: G. Saucier , D. Brasen , J. P. Hiol, Partitioning with cone structures, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.236-239, November 07-11, 1993, Santa Clara, California, United States
• 6: 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]
• 7: 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]
• 8: H. Schmit, L. Arnstein, D. Thomas, and E. Lagnese, "Behavioral Synthesis for FPGA-based Computing," Proceedings of IEEE Work.shop on FPGAs for Custom Computing Machines 199~,, pp. 125-131, 1994.
• 9: Wen-Jong Fang , Allen C.-H. Wu, A hierarchical functional structuring and partitioning approach for multiple-FPGA implementations, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.638-643, November 10-14, 1996, San Jose, California, United States
• 10: W.-J. Fang and Allen C.-H. Wu, "A Fine-Grained Synthesis Method for Logic Emulation Systems." Technical Reports, Computer Science Dept., Tsing Hua Univ., Taiwan, R.O.C., 1996.
• 11: R. Murgai, N. Shenoy, R. K. Brayton, and A. Sangiovanni- Vincentelli, "Improved Logic Synthesis Algorithms for Table Look Up Architectures," Proceedings of ICCAD91, pp. 564-567, 1991.
• 12: 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

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization

  J. Computer Applications

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