Browse Prior Art Database

O(NlogN) Net Based Logic Partitioning Algorithm for Timing Driven Floorplanning

IP.com Disclosure Number: IPCOM000121117D
Original Publication Date: 1991-Jul-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 4 page(s) / 191K

Publishing Venue

IBM

Related People

Relis, Y: AUTHOR

Abstract

This article describes a net based timing driven partitioning algorithm. It differs from most, if not all, existing partitioning algorithms in two ways. First, unlike standard partitioning algorithms which are circuit based in the sense that they are driven by placing circuits with many common connections in the same partition, this algorithm is NET driven in the sense that it defines partitions based on placing all circuits on a net in the same partition whenever feasible. Secondly, rather than balancing connectivity and timing considerations, as is generally the approach, it orders nets by timing criticality considerations and takes the "greedy approach" of clustering nets from the most to the least critical.

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

O(NlogN) Net Based Logic Partitioning Algorithm for Timing Driven
Floorplanning

      This article describes a net based timing driven
partitioning algorithm.  It differs from most, if not all, existing
partitioning algorithms in two ways.  First, unlike standard
partitioning algorithms which are circuit based in the sense that
they are driven by placing circuits with many common connections in
the same partition, this algorithm is NET driven in the sense that it
defines partitions based on placing all circuits on a net in the same
partition whenever feasible.  Secondly, rather than balancing
connectivity and timing considerations, as is generally the approach,
it orders nets by timing criticality considerations and takes the
"greedy approach" of clustering nets from the most to the least
critical.  While this approach would seem to lead to partitions which
are poor from the point of view of connectivity as compared to the
connectivity based partitioning algorithms, a comparison between
these two approaches has not shown this to occur.

      As mentioned, the algorithm requires an ordering of the nets
based on timing considerations.  The ordering used is based on the
net importance factor or NIF [1].  As described in [1], this factor
takes both global and local timing considerations into account.
Other orderings can be used. Ordering the nets requires sorting which
is O(NlogN) where N=#nets.

      Once the nets have been ordered based on their criticality, the
partitioning process proceeds.  Initially, each circuit is assigned a
unique group number and each group is assigned a size of one, and a
group area equal to the area of the circuit.  Then starting with the
most critical net, all the circuits on this net are assigned the same
group number G.  G is not a new number but rather the group number of
one of the circuits in the group.  If the group size of each circuit
on a net is one, then the group number is the group number of the
source of the net. Otherwise, it is the group number of the group
with the largest group size.  The group size for G then becomes the
sum of the group sizes of the groups on the net.  All circuits in
groups joined to the net are assigned the new group number G.  Always
assigning all circuits a group number of the net which has the
largest group size insures that the group number of a circuit is
changed not more than log(C) times (C = number of circuits) and,
hence, the total time devoted to updating group numbers is O(C log C)
at most.  This can be seen by the following reasoning:

      A circuit C1 will only have its group number changed if a group
of size greater or equal to the size of the group C1 is in, is
on the same net as C1.  Thus, the size of the group C1 will be
in has to at least double if its group number changes.  On the other
hand if C1 is in the largest group already, while the group might not
double, the group associated with C1 has not changed either.  Thus,
e...