Browse Prior Art Database

Find the Set of Minimal Cuts of a Transistor Network

IP.com Disclosure Number: IPCOM000117970D
Original Publication Date: 1996-Jul-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 7 page(s) / 278K

Publishing Venue

IBM

Related People

Donath, WE: AUTHOR [+2]

Abstract

Algorithms have been proposed for the minimal cut set problem, based on the search of connected components. Further improvement is achieved by employing an efficient pruning strategy. They may be applied to the early mode timing analysis.

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

Find the Set of Minimal Cuts of a Transistor Network

      Algorithms have been proposed for the minimal cut set problem,
based on the search of connected components.  Further improvement is
achieved by employing an efficient pruning strategy.  They may be
applied to the early mode timing analysis.

      For a simple CMOS two-input NAND gate, the n-fet network
consists of two n-transistors in series, while the p-fet network
consists of two p-transistors in parallel.  When two inputs switch
from 0 to 1 at the same time, two n-transistors in series switch on
simultaneously, and give rise to a delay worse than the switch delay
of any single input lbracket 1 rbracket.  When two inputs switch from
1 to 0 at the same time, two p-transistors in parallel switch on
simultaneously, and give rise to a delay better than the switch delay
of any single input.  In a general transistor network, the worst-case
late-mode delay may be obtained by finding a path and setting all its
transistors on, while the best-case (early-mode) delay may be
obtained by finding a cut and setting all its transistors on lbracket
2 rbracket.

      Therefore, the first step to derive the early-mode delay is to
find the set of all minimal cuts in the transistor network.  This
minimal cut set problem may be formulated as follows:  A
channel-connected network of n-fet(or p-fet) transistors is
represented by an undirected graph G=(V, E), (See the Figure for an
example), in which nets are represented as nodes, and transistors are
represented as edges between the source and drain nets.  Two special
nodes in G are identified:  an output node, o, and a power supply
node, p, which is the ground node in the n-fet case, and VDD in the
p-fet case.  A cut set is defined as a set of edges, with the removal
of which, G is partitioned into nc ge 2 connected components, and
nodes o and p are in different connected components.  When nc=2, the
set of edges between the two components form a minimal cut, since
every edge in this set will form a bridge between o and p, if taken
out of the cut set, (Fig. 1c).  Otherwise, a cut is called a
redundant cut, if a proper subset of the cut is also a cut.  This
includes cuts with nc gt 2 (Fig. 1d).  The minimal cut set problem is
to find all the minimal cuts in G.

The direct method of edge enumeration.

    The explicit enumeration method may be used to solve this problem
by forming all the subsets of E and then testing each subset whether
it is a minimal cut.  Since the number of subsets, 2 sup <vbar E vbar
> , may be extremely large, some means to speed up the enumeration is
absolutely needed.

The method of connected components (Algorithm MinCut1)

    By the definition of the minimal cut, G is partitioned into a
connected component containing o and a connected component containing
p.  Let us use O to denote the node set of the connected component
containing o.  Therefore, a necessary condition for an edge set to be
a minima...