Partitioning using second-order information and stochastic-gain functions

ABSTRACT

A probability-based partitioning algorithm, PROP, was introduced in [5] that achieved large improvements over traditional “deterministic” iterative-improvement techniques like FM [7] and LA [10]. While PROP's gain function has a greater futuristic component than FM or LA, it incorporates spatially local information—only information on the removal probabilities of adjacent nets of a cell is used in its gain computation. This prevents a higher-level view of non-local structures. Also, giving uniform weights to all nets, results in an inability to differentiate between the futuristic benefit of removing one net from another. In this paper, we present a more sophisticated partitioner DEEP-PROP that incorporates more non-local (second-order) structural information than PROP. The second-order information is incorporated into cell gains as well as variable net weights—the latter helps to focus future cell moves in a cluster around the currently moved cell and thus better utilizes the information that led to its selection. A lower-complexity version, VAR-PROP, that also uses dynamically assigned variable net weights, but based on first-order information, has also been developed. Both versions yield significant improvements over PROP on the ACM/SIGDA benchmark suite. DEEP-PROP yields mincut improvements of as much as 39% for large circuits and an average improvement of 20% over all circuits; it is about 3.8 times slower than PROP, which is very fast. VAR-PROP, which has a much lower computational complexity than DEEP-PROP, yields maximum and average mincut improvements over PROP of 27% and 12%, respectively, while being only about 1.14 times slower.

REFERENCES

• 1: Charles J. Alpert , Jen-Hsin Huang , Andrew B. Kahng, Multilevel circuit partitioning, Proceedings of the 34th annual conference on Design automation, p.530-533, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266275]
• 2: (22. Alp~ and A.B. Kahn~ "A hybrid rnullileveFge~efic approach for circuit partitioning" PID'sical Design gbrkshop, 1995, pp. 100- 105.
• 3: Jason Cong , Honching Peter Li , Sung Kyu Lim , Toshiyuki Shibuya , Dongmin Xu, Large scale circuit partitioning with loose/stable net removal and signal flow based clustering, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.441-446, November 09-13, 1997, San Jose, California, United States
• 4: Shantanu Dutt , Halim Theny, Partitioning around roadblocks: tackling constraints with intermediate relaxations, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.350-355, November 09-13, 1997, San Jose, California, United States
• 5: Shantanu Dutt , Wenyong Deng, A probability-based approach to VLSI circuit partitioning, Proceedings of the 33rd annual conference on Design automation, p.100-105, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240538]
• 6: Shantanu Dutt , Wenyong Deng, VLSI circuit partitioning by cluster-removal using iterative improvement techniques, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.194-200, November 10-14, 1996, San Jose, California, United States
• 7: 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
• 8: S. Hauck and G. Bordello, "An Evaluation of Bipartitioning Techniques", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 16, No. 8, pp. 849-866, August 1997.
• 9: B.W. Kemighan and S. Lin, "An efficient heuristic procedure for partitioning graphs", BellSystem Tech. Journal, vol. 49, February 1970, pp. 291-307.
• 10: B. Kfishnamurthy, "An improved mineut algorithm for partitioning VLSI networks", IEEE Trans. on Computers, vol. C-33, no. 5, May 1984, pp. 438-446.
• 11: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 12: Jianmin Li , John Lillis , Chung-Kuan Cheng, Linear decomposition algorithm for VLSI design applications, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.223-228, November 05-09, 1995, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing
  B.8 Performance and Reliability

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Experimentation, Performance