__ Page 1 of 7 __
**Generalization of Min-Cut Partitioning to Tree Structures **

Disclosed is a heuristic to solve a generalization of the min-cut partitioning
problem. The generalized min-cut problem is that of mapping the nodes of an
hypergraph G onto the vertices of a tree structure T, and the cost function to be
minimized is the cost of global routing of the hyperedges of G on the edges of T.
We refer to this as the Min- Cost Tree Partitioning (MCTP) problem.

The MCTP problem can be used to model different kinds of partitioning
problems in VLSI layout design. The main theme in all these applications is the
idea of simultaneous partition of logic into many blocks or macros, so as to
minimize a global cost function of the connectivity between the blocks. Notation,
Definitions, and Problem Statement 4C A weighted hypergraph G is given by
a set U of nodes and a set H of hyperedges. Each hyperedge h e H is a subset
of U. The size of a node u e U is given by s(u), and the weight of a hyperedge h
e H is given by w(h). We also refer to hyperedges as nets. 4D Let I(u) = {h e
H ¯ u e h}, which is the set of all nets that touch the node u. 4E A weighted
tree T is given by a set V of vertices, and a set E of edges. The size of a vertex v
e V is given by S(u), and the weight of an edge e e E is given by W(e).

A mapping or assignment M of the nodes U of a hypergraph G to the vertices
V of a tree T is a function M:U T V, i.e., M(u), for a node u of the hypergraph, is
the vertex in T into which it is mapped. By extension, for a subset X U, we
define M(X) = {M(u) ¯ u e X}. Also define M-1(v) = {u ¯ M(u) = v}.

A mapping M is said to be feasible if the total size of the
nodes of G assigned to a vertex of Y does not exceed the size of
that vertex, i.e., for all v e V,
S s(u) & S(v).

ueM-1(v)

Given a subset Y of the vertices of the tree T, stree(Y) is defined to be the
smallest subtree of T containing all the vertices in Y (see the figure). In other
words, stree(Y) is the Steiner subtree of T for the vertices in the subset Y. A
linear time algorithm for finding stree(Y) will be described in the section,
"Procedures and Functions Comprising the Heuristic".

Given a mapping M, the routing subtree route(h,M) of a hyperedge (net) h, is
thus given by route(h,M) = stree(M(h)). Note that route (h,M) is the smallest
subtree of T which connects all the vertices that have been assigned one or more
nodes of the hyperedge h. The routing subtree for an hyperedge is unique, and
gives the global route for the hyperedge (net) on the tree T, for a given mapping
M of the nodes of G onto the vertices of T.

Given a mapping M, the cost of an hyperedge h, denoted as cost
(h,M), is defined as the product of the weight of the hyperedge with
the sum of the weights of the edges in the routing subtree
route(h,M), i.e.,
cost(h,M) = w(h) x S W(e)

eeroute(h,M)

1

__ Page 2 of 7 __
Note that cost(h,M) is simply the contribution of the hyperedge h to the total
weighted flow on the edges of the tree T.

Given a...