A network flow approach for hierarchical tree partitioning

ABSTRACT

Network flow approaches have been used for partitioning with successin the past. However, most of them can not deal with size constraintsdirectly in partitioning. Instead, they incorporate the sizeconstraints implicitly in the objective function. This paper presentsa new network flow approach for partitioning circuits into treehierarchies. We formulate a linear program for the hierarchicaltree partitioning problem by spreading metrics proposed in [Divide-and-conquer approximation algorithms via spreading metrics, Fast approximate graph partitioning algorithms].The size constraints in partitioning can be formulated directly aslinear constraints. Motivated by the duality between the linear programsfor partitioning and network flow problems, we devise aheuristic algorithm based on network flow and spreading metriccomputations. Experimental results demonstrate that the new algorithmcan generate better solutions for MCNC benchmarks.

REFERENCES

• 1: C.-K. Cheng and T. C. Hu, "Maximum concurrent flows and minimum cuts," Algorithmica, Vol. 8, 1992, pp. 233-249.
• 2: E.W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik, Vol. 1, 1959, pp. 269-271.
• 3: G. Even , J. Naor , S. Rao , B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.62, October 23-25, 1995
• 4: Guy Even , Joseph (Seffi) Naor , Satish Rao , Baruch Schieber, Fast approximate graph partitioning algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.639-648, January 05-07, 1997, New Orleans, Louisiana, United States
• 5: L.R. Ford and D. R. Fulkerson, "Maximal flow through a network," Canadian Journal of Mathematics, Vol. 8, No. 3, 1956.
• 6: M. Iri, "On an extension of the maximum flow minimum cut theorem to multicommodity flows," Journal of the Operations Research Society of Japan, Vol. 5, No. 4, 1967, pp. 697-703.
• 7: David R. Karger, Minimum cuts in near-linear time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.56-63, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237829]
• 8: M.-T. Kuo, "Circuit partitioning in hierarchical design," Technical Report CS96-509, University of California, San Diego, CA, 1996.
• 9: Ming-Ter Kuo , Lung-Tien Liu , Chung-Kuan Cheng, Network partitioning into tree hierarchies, Proceedings of the 33rd annual conference on Design automation, p.477-482, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240609]
• 10: Kevin Lang , Satish Rao, Finding near-optimal cuts: an empirical evaluation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.212-221, January 25-27, 1993, Austin, Texas, United States
• 11: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 12: D. W. Matula and F. Shahrokhi, "The maximum concurrent flow problem and sparest cuts," Technical Report, Southern Methodist University, 1986.
• 13: K. Onaga, "A multi-commodity theorem," Transactions of the Institute of Electronics and Communication Engineers of Japan, Vol. 53-A, No. 7, 1970, pp. 350-356.
• 14: R. C. Prim, "Shortest connection networks and some generalizations," Bell System Technical Journal, Vol. 36, 1959, pp. 1389-1401.
• 15: S. Rao, Personal Communications, May 1996.
• 16: Gopalakrishnan Vijayan, Generalization of Min-Cut Partitioning to Tree Structures and its Applications, IEEE Transactions on Computers, v.40 n.3, p.307-314, March 1991 [doi>10.1109/12.76407]
• 17: C.-W. Yeh, C.-K. Cheng, and T.-T Y. Lin, "Circuit clustering using a stochastic flow injection method," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 14, No. 2, 1995, pp. 154-162.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

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