Hierarchical partitioning

ABSTRACT

Partitioning of digital circuits has become a key problem area during the last five years. Benefits from new technologies like Multi-Chip-Modules or logic emulation strongly depend on partitioning results. Most published approaches are based on abstract graph models constructed from flat netlists, which consider only connectivity information. The approach presented in this paper uses information on design hierarchy in order to improve partitioning results and reduce problem complexity. Designs up to 150k gates have been successfully partitioned by descending and ascending the hierarchy. Compared to a standard k-way iterative improvement partitioning approach results are improved by up to 65% and runtimes are decreased by up to 99%.

REFERENCES

• AlKa94: 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
• AwPe90: Awerbuch, B.; Peleg, D.; "Sparse Partitions", IEEE Annual Symposium on Foundations of Computer Science, pp. 503-513, 1990
• BrSa94: Brasen D.; Saucier G.; "FPGA Partitioning for Critical Paths", Proceedings of the European Design Automation Conference, pp. 99-103, 1992
• BuHe89: 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]
• ChLi95: Chou, N.-C.; Liu, L.-T.; Cheng, C.-K.; Dai, W.-J.; Lindelof, R.; "Local Ratio Cut and Set Covering Partitioning for Huge Logic Emulation Systems", IEEE Transactions on Computer Aided Design, vol 14, no. 9, pp. 1085-1092, 1995
• CoLi94: Jason Cong , Zheng Li , Rajive Bagrodia, Acyclic multi-way partitioning of Boolean networks, Proceedings of the 31st annual conference on Design automation, p.670-675, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196609]
• CoSm93: 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]
• DiHo93: Ding C.; Ho C.; "A New Optimization Driven Clustering Algorithm for Large Circuits", Proceedings of the European Design Automation Conference, pp. 28-32, 1993
• FiMa82: 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
• Field95: Carol A. Fields, Creating hierarchy in HDL-based high density FGPA design, Proceedings of the conference on European design automation, p.594-599, September 18-22, 1995, Brighton, England
• FoFu62: Ford, J. R. and Fulkerson, D. R.; "Flows in Networks", Princeton University Press, 1962
• GaPr90: Garbers, J.; Prvmel, H.J.; Steger, A.; "Finding Clusters in VLSI Circuits", International Conference on Computer Aided Design, pp. 520523, 1990
• HaKa91: Hagen, L.; Kahng, A; "Fast Spectral Methods for Ratio Cut Partitioning and Clustering", International Conference on Computer Aided Design, pp. 10-13, 1991
• HaKa92: Hagen L.; Kahng, A.B.; "New Spectral Methods for Ratio Cut Partitioning and Clustering", IEEE Transactions on Computer Aided Design, vol. 11, no. 9, pp. 1074-1085, 1992
• HwGa95: Hwang J.; Gamal, A; "Min-Cut Replication in Partitioned Networks", IEEE Transactions on Computer Aided Design, vol. 14, no. 1, pp. 96-106, 1995
• KeLi69: Kernighan B.; Lin S.; "An Efficient Heuristic Procedure for Partitioning Graphs", The Bell System Technical Journal, pp. 291-307, 1969
• KhMa95: Shoab A. Khan , Vijay K. Madisetti, System Partitioning of MCMs for Low Power, IEEE Design & Test, v.12 n.1, p.41-52, March 1995 [doi>10.1109/54.350690]
• KrNe91: Kring C.; Newton A.; "A Cell-Replicating Approach to Mincut-Based Circuit Partitioning", International Conference on Computer Aided Design, pp. 2-5, 1991
• KuBr94: 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]
• LiSh93: Lung-Tien Liu , Minshine Shih , Nan-Chi Chou , Chung-Kuan Cheng , Walter Ku, Performance-driven partitioning using retiming and replication, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.296-299, November 07-11, 1993, Santa Clara, California, United States
• MuBr91: Murgai R.; Brayton R.; Sangiovanni-Vincentelli A.; "On Clustering for Minimum Delay/Area", Proceedings of the Design Automation Conference, pp. 6-8, 1991
• ObGl95: U. Ober , M. Glesner, Multiway netlist partitioning onto FPGA-based board architecture, Proceedings of the conference on European design automation, p.150-155, September 18-22, 1995, Brighton, England
• Pla90: David A. Plaisted, A heuristic algorithm for small separators in arbitrary graphs, SIAM Journal on Computing, v.19 n.2, p.267-280, April 1990 [doi>10.1137/0219018]
• RiDo94: 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]
• RiSc95: B. M. Riess , A. A. Schoene, Architecture driven k-way partitioning for multichip modules, Proceedings of the 1995 European conference on Design and Test, p.71, March 06-09, 1995
• Rubi87: Steven M. Rubin, Computer aids for VLSI design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• Saab93: Saab Y.; "Post-Analysis Based Clustering Dramatically Improves The Fiduccia-Mattheyses Algorithm", pp. 22-27, 1993
• San89: 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]
• ScUl72: D. M. Schuler , E. G. Ulrich, Clustering and linear placement, Papers on Twenty-five years of electronic design automation, p.50-56, June 1988 [doi>10.1145/62882.62885]
• ShKu93: 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]
• Spiek92: Frits C. R. Spieksma, A branch-and-bound algorithm for the two-dimensional vector packing problem, Computers and Operations Research, v.21 n.1, p.19-25, Jan. 1994 [doi>10.1016/0305-0548(94)90059-0]
• WeCh90: Wei Y.; Cheng C.; "A Two-Level Two-Way Partitioning Algorithm", International Conference on Computer Aided Design, pp. 516-519, 1990
• YaWo94: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

General Terms:
Algorithms, Design, Performance

Keywords:
Partitioning, Clustering, FPGAs, Logic Emulation, Design Hierarchy