Browse Prior Art Database

CPLACE: A Standard Cell Placement Program

IP.com Disclosure Number: IPCOM000100054D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 2 page(s) / 86K

Publishing Venue

IBM

Related People

Villarrubia, PG: AUTHOR

Abstract

Disclosed is a program that uses the min-cut (*) technique in an iterative improvement mode to implement a high performance standard cell placement program. The uniqueness of the approach lies in the use on the min-cut technique in an iterative improvement environment. Most conventional uses of min-cut operate in an abstract environment.

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

CPLACE: A Standard Cell Placement Program

       Disclosed is a program that uses the min-cut (*)
technique in an iterative improvement mode to implement a high
performance standard cell placement program.  The uniqueness of the
approach lies in the use on the min-cut technique in an iterative
improvement environment.  Most conventional uses of min-cut operate
in an abstract environment.

      CPLACE is an application program designed to generate
placements of VLSI chips.  The placement problem consists of
assigning physical locations to circuit elements that are listed in a
logic specification.  The circuits must be placed in such a way as to
minimize wiring.  For large designs, there are many legal placements,
so many that it is not practical to evaluate even a small percentage
of them. As a result, a heuristic is generally employed to create a
placement.  CPLACE uses a partitioning heuristic known as min-cut.
The method of employing this heuristic to create a placement program
is not trivial.  CPLACE uses the min-cut technique in a unique way
that combines the advantages of constructive and iterative
improvement techniques.

      Placement techniques generally fall into two categories:
           1)  Constructive.
           2)  Iterative Improvement.
CPLACE uses a technique for placement that is a hybrid of these two.
The result is that the best of both techniques can be exploited.
Constructive approaches are fast and allow for maximum movement
flexibility.  Iterative improvement techniques generally make highly
accurate incremental improvements to a currently legal placement,
thus allowing for the maximum potential for obtaining optimal
placements.  CPLACE uses both of these techniques by maintaining a
legal placement at all times.  Improvements are made by employing the
min-cut partitioning technique in local areas.  During partitioning,
the local area of placement being operated on is converted into an
abstract representation.  Moves are made in the abstract.  Upon
completion of the partitioning, the resultant abstract placement for
the local area is mapped back into a real placement.

      The CPLACE algorithm is built upon the following four
operations:
           1)   Partition - divide a list of logic elements
                into two lists such that the amount of logic
                in each list is the same and the number of
                connections between the two lists is
          ...