Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Algorithms for Partitioning of VLSI Networks

IP.com Disclosure Number: IPCOM000045539D
Original Publication Date: 1983-Apr-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 4 page(s) / 73K

Publishing Venue

IBM

Related People

Burstein, M: AUTHOR

Abstract

Several algorithms are examined for partitioning of hypergraphs into two equal parts. Hypergraphs serve as a model of VLSI (very large-scale integration) logic network. The problem is to partition the set of components of a VLSI chip into two more or less equal parts minimizing the number of nets connecting components from different parts. This classical partitioning problem arises in many stages of VLSI design automation.

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

Page 1 of 4

Algorithms for Partitioning of VLSI Networks

Several algorithms are examined for partitioning of hypergraphs into two equal parts. Hypergraphs serve as a model of VLSI (very large-scale integration) logic network. The problem is to partition the set of components of a VLSI chip into two more or less equal parts minimizing the number of nets connecting components from different parts. This classical partitioning problem arises in many stages of VLSI design automation.

A hypergraph is nothing but a set of subsets of a given set, but it is considered as a generalization of the notion of a graph where an edge can be incident to more than two vertices. A hypergraph (1) is a pair (V,E), where V is a set of vertices and E is a family of nonempty subsets of V, called edges (repetitions are allowed). If C is a circuit, the hypergraph of C is defined as having the set of components of C as the vertex-set, and for each net a set of components connected by this net is an edge of the hypergraph.

Let H=(V,P) be a hypergraph. Let p and q be natural numbers such that p+q=n=/V/. A (p,q)- partition is a pair (A,B) of disjoint subsets (A,B Epsilon V,AB=0,AuB=V) with /A/=p, /B/=q. The cost of partition (A,B) is the number of edges having nonempty intersection with both A and B: cost(A,B)=/(eEpsilon E enA not equal 0, enB not equal 0/ Further, H = (V,E) always denotes a hypergraph; for UpsilonEpsilon V f(Upsilon,A) denotes the set of edges incident to Upsilon. Number of vertices contained in an edge Epsilon E is called a degree of e and is denoted d(e). Similarly, for UpsiloneV degree of Upsilon is d(Upsilon)=E(Upsilon). For AV and UpsilonEpsilonV, f(Upsilon,A) denotes the number of edges in the set (eEpsilonE(Upsilon)). For x,yEpsilonV D(x,y) will denote the number of edges containing both vertices x and y.

The partitioning problem can be formulated simply as follows:

Given a hypergraph H=(V,E) with n vertices, and numbers p, q, (p q=n) generate a (p,q) - partition of minimal cost. The problem is obviously NP- complete (2), so all the algorithms described will be heuristic and the cost of the resulting partitions for all of them may be arbitrarily far from minimal. We distinguish two categories of partitioning algorithms : algorithms producing partitions based solely on the hypergraph structure, i.e., constructive algorithms, and algorithms that start with a given partition and try to improve it, usually applying iterative routines; algorithms of the latter category will be called improvement algorithms. The algorithms presented here will generate partitions into equal size subsets, but they can be easily modified to generate general (p,q) - partitions.

H = (V,E) denotes a hypergraph. Three Constructive

Partitioning (CP) algoithms are presented for initial partition.

They all are based solely on connectivity considerations and differ only in the way of using them.

Complexity

Assuming the calculation of f(x,A) for xEpsilonX, A X takes

1

Page 2 of 4

ti...