Browse Prior Art Database

Generalization of Min-Cut Partitioning to Tree Structures

IP.com Disclosure Number: IPCOM000036196D
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 7 page(s) / 45K

Publishing Venue

IBM

Related People

Vijayan, G: AUTHOR

Abstract

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.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 25% of the total text.

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...