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

Logic Partitioning by Incremental Clustering Based on Connectivity

IP.com Disclosure Number: IPCOM000039953D
Original Publication Date: 1987-Aug-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 3 page(s) / 22K

Publishing Venue

IBM

Related People

Cagle, JW: AUTHOR [+4]

Abstract

A method is described to maximize performance and minimize global traffic when implementing the logic in a very large scale integration (VLSI) design. VLSI physical design requires the logic network to be broken down into groups of blocks to make the layout problem less complex. The groups must be chosen such that functionally related logic remains together while achieving group sizes and interconnection counts that are practical for physical design. This benefits both density and performance by decreasing the amount of wiring from that required by a physically arbitrary partition. Block count in VLSI is too large to permit an exhaustive search through the possible groups, so an algorithmic approach is required. The type of partitioning algorithm presented here is a joining algorithm with a special clustering criterion.

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

Page 1 of 3

Logic Partitioning by Incremental Clustering Based on Connectivity

A method is described to maximize performance and minimize global traffic when implementing the logic in a very large scale integration (VLSI) design. VLSI physical design requires the logic network to be broken down into groups of blocks to make the layout problem less complex. The groups must be chosen such that functionally related logic remains together while achieving group sizes and interconnection counts that are practical for physical design. This benefits both density and performance by decreasing the amount of wiring from that required by a physically arbitrary partition. Block count in VLSI is too large to permit an exhaustive search through the possible groups, so an algorithmic approach is required. The type of partitioning algorithm presented here is a joining algorithm with a special clustering criterion. In addition to the goals set in the preceding paragraph, a major pitfall that must be avoided by joining algorithms is `snowballing.' In snowballing, one cluster dominates the joining process through a positive feedback mechanism. As the offending cluster grows, it becomes increasingly likely to gain yet another block, eventually consuming the entire network so no partitioning is achieved. The positive feedback must be avoided to permit a hierarchy of clusters to form. The control must be achieved in the joining criterion since arbitrary size limits result in a Rent's rule governed with its associated inferior wiring. The joining algorithm disclosed here solves these problems by means of a clustering ethic referred to hereafter as `connectivity', an efficient best-pair search routine and an incremental clustering process. Connectivity assures that good-pair choices are made for joining while preventing snowballing. The efficiency of the search routine permits all pairs to be searched in a practical amount of CPU time. Proceeding incrementally (clustering one pair, revising the network, then choosing the next pair) assures pair search accuracy. Each of these is detailed below. Connectivity is the basic criterion used to choose the best pair of objects in the network (blocks or clusters) for joining. The connectivity C(A,B) of object A and B is the decimal fraction of the nets connecting A and B divided by all nets connecting to A. Note that connectivity is directional: C(A,B) doesn't necessarily equal C(B,A). This implies that the joining of A to B is different from the joining of B to A, and both must be evaluated. Note further that the larger an

(Image Omitted)

object is, the more connected nets it is likely to have, and the lower its connectivity to other blocks is likely to be. The pair of objects A,B ch...