Browse Prior Art Database

Algorithm for Overlap Elimination in Floorplans

IP.com Disclosure Number: IPCOM000102670D
Original Publication Date: 1990-Dec-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 3 page(s) / 140K

Publishing Venue

IBM

Related People

Vijayan, G: AUTHOR

Abstract

This article describes an algorithm for eliminating/reducing the overlaps in a chip floorplan of a set of movable or replaced entities of fixed or flexible shapes.

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

Algorithm for Overlap Elimination in Floorplans

       This article describes an algorithm for
eliminating/reducing the overlaps in a chip floorplan of a set of
movable or replaced entities of fixed or flexible shapes.

      Given an overlapping floorplan of a set of blocks and the
dimensions of the chip, the goal is to find a non-overlapping
floorplan within the chip dimensions, which respects the relative
placement of the blocks in the overlapping floorplan.  The blocks are
assumed to have rectangular shapes.  A block may be preplaced, i.e.,
it is not allowed to move from its preplaced location, or it may be
movable.  A movable block may have a fixed shape or a flexible shape
of a given area that satisfies given lower and upper bounds on its
aspect ratio (height/width ratio).

      A perturbation of a movable block is defined to be a small
change in either the location or the aspect ratio of the block.  The
algorithm described below uses 18 different types of perturbations.
Four of these are location perturbations: move left, right, up and
down.  The remaining 14 are aspect ratio perturbations.  These aspect
ratio perturbations differ in the dimension being contracted (the
orthogonal dimension is correspondingly expanded to keep the area of
the block constant), and the location of the center point of the
moved block.  A perturbation of a block is said to be allowed if its
application does not violate the predefined aspect ratio bounds of
the block, or pushes an edge of the block outside the chip boundary.

      The cost of a floorplan is defined to be the amount of pair
wise overlapping area among the blocks of the floorplan.  The goal of
the algorithm is to reduce this cost to zero.  The strategy used by
the algorithm is a combination of steepest descent and randomization.
The algorithm always tries to perturb the block with the most
overlap, as long as this perturbation decreases the amount of
overlap.  In the event that there is no positive gain perturbation of
this block, the algorithm resorts to randomization to climb out of
the local minimum in the cost function.  The idea behind this
strategy is to perturb the areas in the floorplan which have
overlaps, while keeping relatively untouched those areas which are
free from overlaps.  Such a technique minimizes the departure of the
output floorplan from the input floorplan, thus helping maintain the
relative placement of the blocks in the input floorplan.

      The algorithm performs a certain number of pre-specified
passes.  In each pass a preset number of perturbations are executed.
The input to the first pass is the floorplan with overlaps.  The
input to each subsequent pass is the floorplan with the least amount
of overlap seen at any point in the previous pass.  In order to
facilitate convergence to a floorplan with zero overlaps, the amount
of change in the perturbations is reduced from one pass to the next.
In other words, the perturbations...