Browse Prior Art Database

Floorplanning Using Hierarchical Rules

IP.com Disclosure Number: IPCOM000118406D
Original Publication Date: 1997-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 213K

Publishing Venue

IBM

Related People

Hasan, ND: AUTHOR [+3]

Abstract

One of the most difficult aspects of hierarchical physical design is determining how to assign shapes and relative positions to macros at a given level of hierarchy to optimize considerations, such as area, wireability and timing. This disclosure describes an efficient algorithm for achieving such optimization.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 26% of the total text.

Floorplanning Using Hierarchical Rules

      One of the most difficult aspects of hierarchical physical
design is determining how to assign shapes and relative positions to
macros at a given level of hierarchy to optimize considerations, such
as area, wireability and timing.  This disclosure describes an
efficient algorithm for achieving such optimization.

      Floorplanning is the process of mapping entities of various
shapes onto a chip in a cost efficient manner where cost can reflect
such considerations as area, wireability, timing, power distribution,
etc.  The key difference between floorplanning and standard placement
is the wide variation in the shapes of the entities being placed.
Numerous algorithms have been applied to this problem.  Many of these
algorithms map the placement to a tree structure with the leaf nodes
representing the entities and each intermediate node representing a
bounding shape determined recursively by the shapes and relative
positions of lower level nodes (1,2,3,4).  Among algorithms which use
a tree structure are those which represent placements which can be
repeatedly bipartitioned (sliced) without having an entity which is
bisected by the partition (1,2,3).  Placements which can be
repeatedly sliced are said to have a slicing structure.

      This disclosure describes a floorplanner which generates
slicing structure floorplans.  It assumes that the entities are
rectangular.  It merges a number of concepts which have previously
been developed (3,5,6) to produce a highly effective fast
floorplanner.

Initial Placement

      The floorplanner limits placements of entities to ones which
can be represented by a balanced quad tree of height O(log N) (3)
where N is the number of entities and the leaves of the tree
represent potential locations for entities.  For instance, if there
are 28 entities, a tree with 64 leaf nodes will be created and the
entities are  initially randomly assigned to some of the leaves of
the tree.

      Once each entity is assigned to a leaf node, shape curves which
are based on the shape constraints of the entities are recursively
generated at each level of the hierarchy by merging the shape
functions at the prior level.  This proceeds until the root of the
tree is reached (5).  At the root the point on the shape curve which
allows the bounding rectangle of the placement to be as close as
possible to the target dimension for the layout is selected.  Once a
point on the shape curve has been selected, it determines the points
on the shape curves of the next lower level nodes.  Thus, the shapes
and relative positions of the areas associated with these next lower
level nodes can be determined.  This process is repeated recursively
until the leaves of the tree are reached and the entities are given
shapes and locations.  This takes O(N**2) time for N entities in
general (5).  For a balanced quad tree of height log N it takes
O(Nlog N) time.  A cost is th...