Browse Prior Art Database

Procedure for Partitioning the Nodes of a Graph

IP.com Disclosure Number: IPCOM000059994D
Original Publication Date: 1986-Feb-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 3 page(s) / 52K

Publishing Venue

IBM

Related People

Barnes, ER: AUTHOR [+4]

Abstract

In the problem of laying out a large circuit network on a chip, the problem is simplified by dividing the circuits into several smaller groups which are pairwise weakly connected. See, for example, [1, 2, 3, 4]. When this can be done, an optimal placement for the individual groups of circuits results in a near optimal placement for the entire network. It is common practice to model the network as a graph and to determine the individual groups of circuits by a graph-partitioning algorithm. In this publication, a fast algorithm for partitioning the nodes of a graph is described. Let G be an undirected graph on n nodes N = _1,...,n_. Consider the problem of partitioning N into k subsets S1,..., Sk of specified sizes S1 = m1,..., Sk = mk, so as to minimize the number of edges connecting nodes in distinct groups.

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 53% of the total text.

Page 1 of 3

Procedure for Partitioning the Nodes of a Graph

In the problem of laying out a large circuit network on a chip, the problem is simplified by dividing the circuits into several smaller groups which are pairwise weakly connected. See, for example, [1, 2, 3, 4]. When this can be done, an optimal placement for the individual groups of circuits results in a near optimal placement for the entire network. It is common practice to model the network as a graph and to determine the individual groups of circuits by a graph-partitioning algorithm. In this publication, a fast algorithm for partitioning the nodes of a graph is described. Let G be an undirected graph on n nodes N = _1,...,n_. Consider the problem of partitioning N into k subsets S1,..., Sk of specified sizes S1 = m1,..., Sk = mk, so as to minimize the number of edges connecting nodes in distinct groups. Let A = (aij) denote the adjacency matrix for the graph and let x1,..., xk denote characteristic vectors for the groups. Then: xj = (x1j,...,xnj)T , j = 1,...,k, where xij = 1 if ieSj and xij = 0 if ieSj .

(Image Omitted)

This problem has an infinite number of constraints, but it can be solved approximately by a column-generating technique. Given D, increase each ai by a small amount _ so that AD = A+D is positive definite. Now use Cholesky factorization to determine Q such that AD = QQT . Clearly the solution of problem (2) is not changed if A is replaced by AD . So we make this replacement. Let q1,...,qn denote the rows of Q. It is helpful to think of these points as valuations on the nodes of G in En . Suppose we have obtained an initial partition N = S1 n ... n Sk which we wish to improve. Most existing algorithms attempt to improve an initial partition by searching for subsets of nodes in one set that can be exchanged for a subset of equal size in another set
[5]. Usually this is a very expensive procedure. For example, if n nodes are partitioned into two equal sized subjects, there are approximately n n 2 interchanges of subsets that can be made. Determining an interchange that will improve an existing partition may require a very long search. We will now describe a fast procedure for finding suitable subsets to interchange. For simplicity we give the details of the method only for the case of partitioning into groups of equal sizes. However, we state the method for the general case. Let Rj = {qr reSj} denote the set of q points cor...