Browse Prior Art Database

Logic Flow-Driven Partitioning

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

Publishing Venue

IBM

Related People

Relis, Y: AUTHOR

Abstract

This disclosure describes an essentially linear time algorithm for partitioning logic based on logic flow rather than net connectivity (1,2,3). Its value is that a) it insures that no logic path between start points (e.g., PIs and Regs) and stop points (e.g., Regs and POs) passes between any two partitions more than once, and b) it tends to place logic which is in a common cone of logic in the same partition.

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

Logic Flow-Driven Partitioning

       This disclosure describes an essentially linear time
algorithm for partitioning logic based on logic flow rather than net
connectivity (1,2,3).  Its value is that a) it insures that no logic
path between start points (e.g., PIs and Regs) and stop points (e.g.,
Regs and POs) passes between any two partitions more than once, and
b) it tends to place logic which is in a common cone of logic in
the same partition.

      These conditions are important in a number of situations.  One
instance is if logic flow diagrams are required in which there are
many sheets.  Such a partitioning scheme places related logic on each
sheet while permitting the designer to trace logic in a path in a
left to right manner through the sheets without backtracking. Another
case in which this is useful is if logic has to be partitioned for
simulation or synthesis since this reduces the number of partitions
that must be processed to perform operations on a path.  Still
another situation in which this approach would be of use is if logic
has to be partitioned so that due to timing constraints paths cannot
pass between partitions many times.

      The basic idea of the partitioning scheme is to use a modified
depth-first search.  The process is first described assuming there is
no feedback.  Starting from a primary input Ih of the logic, the
algorithm recursively proceeds from net sources to net sinks and
backtracks in the following manner.  Assume a circuit Ci has been
reached. Assume all its inputs have been processed and it has been
assigned to partition Pj.  The output net Nk of Ci with the highest
weight (to be discussed) and the sink Cl of Nk with the highest
weight (to be discussed) is selected.  The number of times Cl has
been reached is incremented by one. This is the weight of the sink
Cl.  Furthermore, the weight of each net which is an input to Cl is
incremented by one. This is the weight of the net.  Thus, the net and
sink weights are a measure of how much connectivity there is between
processed logic and the current circuit or net.

      If Cl has been reached as many times as it has inputs, then if
Cl is not a Reg it is assigned to a partition.  The partition it is
assigned to is one which contains the maximum number of its inputs
subject to the condition that the partition does not yet have the
maximum number of circuits allowed in a partition.  If all partitions
which contain its inputs are at their maximums, a new partition is
created and it is assigned to that partition.  C1 becomes the current
circuit, and the process is repeated starting from an output of Cl.
When all outputs of Cl have been processed the search will return to
Nk and its sinks.  Furthermore, Cl is marked as done.  Note that by
not assigning a Reg, all of whose inputs have been reached, to a
partition, at this time it helps to insure that logic in a cone is
processed before a new cone is started.

      If Cl...