Min-cost partitioning on a tree structure and applications

ABSTRACT

We introduce a generalization of the min-cut partitioning problem, called Min-Cost Tree Partitioning, in which the nodes of an hypergraph G are to be mapped on to the vertices of a tree structure T, and the cost function to be minimized is the cost of routing the hyperedges (i.e., the nets) of G on the edges of T. We discuss several interesting VLSI design applications for this problem. We describe an iterative improvement heuristic for solving this problem.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Inderpal Bhandari , Mark Hirsch , Daniel Siewiorek, The Min-cut shuffle: toward a solution for the global effect problem of Min-cut placement, Proceedings of the 25th ACM/IEEE conference on Design automation, p.681-685, June 12-15, 1988, Atlantic City, New Jersey, United States
• 3: A. E. Dunlop, "A Procedure for Placement of Standard Cell VLS! Circuits,', IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. CAD-4, 1985.
• 4: 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
• 5: B.W. Kernighan and S. Lin, "An efl3cient heuristic procedure for partitioning graphs," Bell System Technical Journal, Vol. 49, February 1970.
• 6: B. Krishnamurthy, "An Improved Min..Cut Algorithm for Partitioning VLS! Networks," IEEE Transactions on Computers Vol. C-33, No. 5, May 1984, pp 438-446.
• 7: D. Lapotin and S. W. Director, "Mason: A Global Floorplanning Approach for VLSI Design," }EEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. CAD-5, 1986, pp 477-489.

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.6 LOGIC DESIGN

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Theory, Verification