Browse Prior Art Database

Hierarchical Placement Method

IP.com Disclosure Number: IPCOM000083080D
Original Publication Date: 1975-Mar-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 5 page(s) / 28K

Publishing Venue

IBM

Related People

Donath, WE: AUTHOR

Abstract

The placement of connected components on an array of locations is a recurring problem in the automatic design of circuit layouts; an extensive review of the methods was given by Hanan and Kurtzberg./1/ Two separate problems may be distinguished; for one, it is desirable to evaluate placements preparatory to wiring for wirability; secondly, a method is required for generating sequences of placements or partial placements, such that one optimizes whatever evaluation function is employed.

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

Page 1 of 5

Hierarchical Placement Method

The placement of connected components on an array of locations is a recurring problem in the automatic design of circuit layouts; an extensive review of the methods was given by Hanan and Kurtzberg./1/ Two separate problems may be distinguished; for one, it is desirable to evaluate placements preparatory to wiring for wirability; secondly, a method is required for generating sequences of placements or partial placements, such that one optimizes whatever evaluation function is employed.

The question exists whether the algorithms developed in the past, which are constructive or improvement type algorithms, actually approach the minimum in terms of any evaluation function. Preliminary work raised the possibility that both interchange and constructive methods in placements diverge from the optimum possible, as the size of the placement problem increases. In the present work, it is desired to investigate the possibility that the hierarchical structure of logic graphs/2/ is best exploited by a combination partitioning/placement method. This question was already investigated by Patel/3/, who reported encouraging results using a placement program using 2 levels of hierarchy.

A program is discussed herein which permits any number of levels of hierarchy; the hierarchy on the logic is automatically generated, while the hierarchy on the placement locations has to be manually defined. From that point on, however, the program does its placement automatically.

A general discussion is provided relating to the concept of "hierarchies". Consider a set of elements a(1)a(2)...a(n), which tend to be more or less "related". The elements are clustered into a disjoint set of sets of elements (i.e., clusters) to gather together groupings, which are "highly" related in some sense or another. These clusters may then be grouped into higher level clusters, which may also be grouped into still higher level clusters, and so on.

The clusters thusly defined constitute a "hierarchy" on the set of elements a(1)a(2)...a(n). A cluster of clusters (or of atomic elements) are denoted as the "parent" of the units clustered together, and each of the individual units as a "descendant" of that cluster. The "level" of a cluster may be defined recursively; the atomic element is, let us say, level 0; a parent has a level one larger than the maximum of any of its descendant levels. A "regular" hierarchy would be one where the descendants of the same parent have the same level. In this description only regular hierarchies will be considered.

A hierarchy is defined both on the set of circuit locations and on the set of circuits. It is required that the number of k-level clusters in the hierarchy on the circuits does not exceed those in the hierarchy on the locations. When the placement algorithm is described, it will be seen why this is the only necessary requirement for the placement algorithm to "work" (in order to work effectively, other consider...