PROP: a recursive paradigm for area-efficient and performance oriented partitioning of large FPGA netlists

ABSTRACT

In this paper, we introduce a new recursive partitioning paradigm PROP which combines (p)artitioning, (r)eplication, (o)ptimization, to be followed by another recursion of (p)artitioning, etc. We measure the quality of partitions in terms of total device cost, logic and terminal utilization, and critical path delay. Traditionally, the minimum lower bound into which a given netlist can be partitioned is determined by disregarding the logic interconnect while distributing the logic nodes into a minimum number of devices. PROP paradigm challenges this assumption by demonstrating feasible partitions of some large netlists such that the number of device partitions is smaller than minimum lower bounds postulated initially. Overall, we report consistent reductions in the total number of partitions for a wide range of combinational and sequential circuit benchmarks while, on the average, reducing critical path delay as well.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Jason Cong , M'Lissa Smith, A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design, Proceedings of the 30th international conference on Design automation, p.755-760, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165119]
• 4: C. Kring and A. R. Newton. A Cell-Replicating Approach to Mincut- Based Circuit Partitioning. In IEEE ICCAD-91, pages 2-5, November 1991.
• 5: 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
• 6: 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]
• 7: Pak K. Chan , Martine D. F. Schlag , Jason Y. Zien, Spectral K-way ratio-cut partitioning and clustering, Proceedings of the 30th international conference on Design automation, p.749-754, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165117]
• 8: Charles J. Alpert , So-Zen Yao, Spectral partitioning: the more eigenvectors, the better, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.195-200, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217529]
• 9: Minshine Shih , Ernest S. Kuh, Quadratic Boolean programming for performance-driven system partitioning, Proceedings of the 30th international conference on Design automation, p.761-765, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165121]
• 10: 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]
• 11: Bernhard M. Riess , Konrad Doll , Frank M. Johannes, Partitioning very large circuits using analytical placement techniques, Proceedings of the 31st annual conference on Design automation, p.646-651, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196602]
• 12: 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
• 13: Honghua Yang , D. F. Wong, Efficient network flow based min-cut balanced partitioning, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.50-55, November 06-10, 1994, San Jose, California, United States
• 14: Jason Cong , Wilburt Labio , Narayanan Shivakumar, Multi-way VLSI circuit partitioning based on dual net representation, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.56-62, November 06-10, 1994, San Jose, California, United States
• 15: 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]
• 16: 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]
• 17: 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]
• 18: L. T. Liu, M. T. Kuo, C. K. Cheng, and T. C. Hu. Performance- Driven Partitioning using a Replication Graph Approach. In 32th DAC, ACM/IEEE, pages 206-210, June 1995.
• 19: Roman Kužnar , Baldomir Zajc , Franc Brglez, A unified cost model for min-cut partitioning with replication applied to optimization of large heterogeneous FPGA partitions, Proceedings of the conference on European design automation, p.271-276, September 19-23, 1994, Grenoble, France
• 20: 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]
• 21: R. Ku~nar. Latest Partitioning Results Update and Directories. Available from http://www.cbl.ncsu.edu/fcuznar/, August 1995. For an autoreply on up-to-date access to all benchmark directories, send e-mail to benchmarksOcbl.ncsu.edu.
• 22: S. Dey, F. Brglez, and G. Kedem. Circuit Partitioning for Logic Synthesis. IEEE Journal of Solid-State Circuits, 26(3):350 - 363, March 1991.
• 23: Xilinx. User Guide and Tutorials. Xilinx Incorporation, 2100 Logic Drive, San Jose, California, 1991.
• 24: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 25: E. M. Sentovich et. al. SIS: A System for Sequential Circuit Synthesis. Dept. of Electrical Engineering and Computer Science, University of California, Berkeley, CA 94720, 1992.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

General Terms:
Algorithms, Measurement, Performance, Theory

Keywords:
partitioning, FPGA, optimization, resynthesis, critical path delay