Multiway FPGA partitioning by fully exploiting design hierarchy

ABSTRACT

In this paper, we present a new integrated synthesis and partitioning method for multiple-FPGA applications. Our approach bridges the gap between HDL synthesis and physical partitioning by fully exploiting the design hierarchy. We propose a novel multiple-FPGA synthesis and partitioning method which is performed in three phases: (1) fine-grained synthesis, (2) functional-based clustering, and (3) hierarchical set-covering partitioning. This method first synthesizes a design specification in a fine-grained way so that functional clusters can be preserved based on the structural nature of the design specification. Then, it applies a hierarchical set-covering partitioning method to form the final FPGA partitions. Experimental results on a number of benchmarks and industrial designs demonstrate that I&slash;O limits are the bottleneck for CLB utilization when applying a traditional multiple-FPGA synthesis method on flattened netlists. In contrast, by fully exploiting the design structural hierarchy during the multiple-FPGA partitioning, our proposed method produces fewer FPGA partitions with higher CLB and lower I&slash;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: Pak K. Chan , Martine D. F. Schlag , Jason Y. Zien, Spectral-based multi-way FPGA partitioning, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.133-139, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201331]
• 3: Pak K. Chan , Martine D. F. Schlag, Parallel placement for field-programmable gate arrays, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611825]
• 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: COX,C.E.AND BLANZ, W. E. 1992. GANGLION- A fast field-programmable gate array implementation of a connectionist classifier. IEEE J. Solid-State Circuits 27 (Mar.), 288-299.
• 6: Wen-Jong Fang , Allen C.-H. Wu , Ti-Yen Yen, A real-time RTL engineering-change method supporting on-line debugging for logic-emulation applications, Proceedings of the 34th annual conference on Design automation, p.101-106, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266043]
• 7: 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
• 8: 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
• 9: Daniel D. Gajski , Nikil D. Dutt , Allen C.-H. Wu , Steve Y.-L. Lin, High-level synthesis: introduction to chip and system design, Kluwer Academic Publishers, Norwell, MA, 1992
• 10: Dennis J.-H. Huang , Andrew B. Kahng, Multi-way system partitioning into a single type or multiple types of FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.140-145, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201332]
• 11: 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
• 12: JONG, C. Y. 1996. Multi-way circuit partitioning for cost and delay minimizations. Master's Thesis. Tsinghua Univ. Press, Beijing, China.
• 13: KRING,C.AND NEWTON, A. R. 1991. A cell-replicating approach to mincut-based circuit partitioning. In Proceedings of the IEEE International Conference on Computer-Aided Design (Santa Clara, CA, Nov.) IEEE Computer Society Press, Los Alamitos, CA, 2-5.
• 14: 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]
• 15: 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]
• 16: MURGAI, R., SHENOY, N., BRAYTON,R.K.,AND SANGIOVANNI-VINCENTELLI, A. 1991. Improved logic synthesis algorithms for table look up architectures. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD '91, Santa Clara, CA, Nov. 11-14) IEEE Computer Society Press, Los Alamitos, CA, 564-567.
• 17: Kalapi Roy-Neogi , Carl Sechen, Multiple FPGA partitioning with performance optimization, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.146-152, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201333]
• 18: 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
• 19: Prashant Sawkar , Donald Thomas, Multi-way partitioning for minimum delay for look-up table based FPGAs, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.201-210, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217530]
• 20: SCHMIT, H., ARNSTEIN, L., THOMAS, D., AND LAGNESE, E. 1994. Behavioral synthesis for FPGA-based computing. In Proceedings of the IEEE Workshop on Custom Computing Machines (Napa Valley, CA, Apr.) IEEE Computer Society Press, Los Alamitos, CA, 125-131.
• 21: VAN DEN BOUT, D. E. 1993. The anyboard: Programming and enhancements. In Proceedings of the IEEE Workshop on FPGAs for Custom Computing Machines (Napa Valley, CA, Apr.) IEEE Computer Society Press, Los Alamitos, CA, 68-77.
• 22: WALTERS, S. 1991. Computer-aided prototyping for ASIC-based systems. In Proceedings of the IEEE International Conference on Design and Test of Computers (June) IEEE Computer Society Press, Los Alamitos, CA, 4-10.
• 23: 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:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

General Terms:
Design, Experimentation, Performance

Keywords:
fine-grained synthesis, functional clustering, multi-way partitioning, multiple-FPGA synthesis