A SAT-based implication engine for efficient ATPG, equivalence checking, and optimization of netlists.
The paper presents a flexible and efficient approach to evaluating implications as well as deriving indirect implications in logic circuits. Evaluation and derivation of implications are essential in ATPG, equivalence checking, and netlist optimization. Contrary to other methods, the approach is based on a graph model of a circuit's clause description called implication graph. It combines both the flexibility of SAT-based techniques and high efficiency of structure based methods. As the proposed algorithms operate only on the implication graph, they are independent of the chosen logic. Evaluation of implications and computation of indirect implications are performed by simple and efficient graph algorithms. Experimental results for various applications relying on implication demonstrate the effectiveness of the approach.
Introduction
Recently, substantial progress has been achieved in the fields of
Boolean equivalence checking and optimization of netlists. Techniques
for deriving indirect implications, which were originally developed
for ATPG tools, play a key role in this development.
Indirect implications have been successfully applied in algorithms
for optimizing netlists. For this task, either a set of permissible
transformations is derived [1, 2, 3] or promising transformations
are applied and their permissibility is later verified by an
ATPG tool [4, 5, 6]. Furthermore, they are of great importance in
ATPG-based approaches to Boolean equivalence checking of both
combinational and sequential circuits [7, 8, 9, 10, 11] as they help
identify equivalent internal signals in the circuits to be compared.
In the late 1980s, Schulz et al. incorporated computation of indirect
implications into the ATPG tool SOCRATES[12]. Indirect
implications are indispensable when dealing with redundant faults
as they help to efficiently prune the search space of the branch-
and-bound search. In order to derive more indirect implications,
the originally static technique of SOCRATES, which the authors
refer to as (static) learning, has been extended to dynamic learning
[13, 14].
Recursive learning [7], proposed by Kunz et al. in 1992, was the
first complete algorithm for determining indirect implications. As
the problem of finding all indirect implications is NP-complete,
only small depths of recursion are feasible. Recently, it has
been shown that recursive learning can be adequately modelled
by AND-OR reasoning graphs [3]. Another complete method for
deriving indirect implications based on BDDs was suggested by
Mukherjee et al. [15]. Very recently, Zhao et al. presented an approach
that combines iterated static learning with recursive learning
constrained to recursion level one [16]. It is based on set algebra
and is similar to single pass deductive fault simulation.
Contrary to the above methods, which work on the structural
description of a circuit, other approaches use a Boolean satisfiability
based model. The SAT-model allows an elegant
problem formulation which can easily be adapted to various log-
ics. This abstraction, however, often impedes development of
efficient algorithms as structural information is lost. Larrabee
included a clause based formulation of Schulz's algorithm into
NEMESIS[17]. Her approach has been improved by the iterated
method of TEGUS [18]. The transitive closure algorithms suggested
by Chakradhar et al. rely on a relational model of binary
clauses [19]. Silva et al. proposed another form of dynamic learning
in GRASP [20] where indirect implications are determined by
a conflict analysis during the backtracking phase of a SAT-solver.
In many areas of logic synthesis and formal verification Binary
Decision Diagrams (BDD) have become the most widely used
data structure as they provide many advantageous properties, e.g.
canonicity and high flexibility. Besides their exponential memory
complexity, when used for ATPG, equivalence checking, and optimization
of large netlists, BDDs suffer from the drawback that
implications cannot be derived efficiently on this data structure.
For a given signal assignment it can only be decided if another signal
assignment is implied or not. So, finding all possible implications
from a given signal assignment is expensive because theoretically
all possible combinations of signal pairs have to be checked.
Therefore, BDD-based approachessuch as functional learning [15]
restrict their search to potential learning areas, which are identified
by non BDD-based implication. Consequently, structural or hybrid
approaches, i.e. BDDs combined with other methods, are predominant
in ATPG, equivalence checking and optimization of netlists.
Even though most of these approachesmake heavy use of implica-
tions, the data structures that are used for deriving and evaluating
implications are often suboptimal and inflexible. That is why we
propose a flexible data structure which is specifically optimized
with respect to implication.
In this paper, we introduce a framework for implication based
algorithms which inherits the advantages of structural as well as
SAT-based approaches. Our approach combines both the flexibility
and elegance of a SAT-based algorithm and the efficiency of
a structural method by working on a graph model of the clause
system, called implication graph. Its memory complexity is only
linear in the number of modules in the circuit. Due to structural
information available in the graph, fundamental problems such as
justification, propagation and particularly implication are carried
out efficiently on the graph. The search for indirect implications
reduces to graph algorithms that can be executed very fast and
are easily extended to exploit bit-parallelism. As the implication
graph can automatically be generated for any arbitrary logic, all
presented algorithms remain valid independent of the chosen logic.
This allows rapid prototyping of implication based tools for new
multi-valued logics.
The remainder of this paper is organized as follows. In Sec. 2,
we show how to derive the implication graph. Next, we discuss
how implications are evaluated and how indirect implications can
be computed in Sec. 3 and 4, respectively. In order to demonstrate
the high efficiency of our approach, experimental results for
various applications using the proposed implication engine are presented
in Sec. 5. Sec. 6 concludes the paper.
Implication graph
As performing implications is one of the most prominent and
time consuming tasks in ATPG, equivalence checking, and optimization
of netlists, it is of utmost importance to use a data structure
that is best suited. Unlike other graphical representations of
clause systems, our data structure represents all information contained
in both the structural netlist and the clause database. The implication
graphs used in NEMESIS[17] and TRAN[19] model only
binary clauses, clauses of a higher order are solely included in the
clause database.
Since our approach is generic in nature, any combinational circuit
can automatically be compiled into its implication graph rep-
resentation. Only information about a logic and its encoding as
well as the truth table descriptions of supported module types have
to be provided. The basic steps of compilation are given in Fig. 1.
First, all supported module types are individually compiled into
encoded
table clauses
module database
circuit
implication
subgraph
logic
encoding
module
optimization
implication graph

Figure

1: Deriving the implication graph
encoded truth tables. Then, these tables are optimized by a two-level
logic optimizer, e.g. ESPRESSO. This step is explained in
Sec. 2.1. Next, a set of clauses is extracted from the optimized ta-
ble, which is shown in Sec. 2.2. As shown in Sec. 2.3, the set of
clauses is transformed into an implication subgraph that is stored in
the module database. Then, for every module in the circuit the appropriate
generic subgraph is taken from the module database and
personalized with the input and output signals of the given module.
Finally, all identical nodes are merged into a single node resulting
in the complete implication graph.
The following sections only consider the 3-valued logic L
f0;1;Xg in order to present the basic ideas of our approach. Generation
of an implication graph for an arbitrary multi-valued logic,
e.g. the 10-valued logic L 10 known from robust path delay ATPG,
is discussed in [21].
2.1 Encoding
A signal variable x 2L 3 requires two encoding bits c x and c
x for
its internal representation. The complete scheme of encoding for
L 3 is shown in Table 1. In order to easily detect inconsistencies,
encoding interpretation
x
signal x is 1
signal x is unknown
conflict at signal x

Table

1: 3-valued logic and its encoding
conflicting signal assignments are denoted by c
property is expressed in the following definition:
DEFINITION 1 An assignment is called non-conflicting iff c x -
c
holds for all signal variables x.
Based on this encoding, the truth tables of all supported module
types are converted into encoded tables. For example, the truth
table of a 2-input AND-gate found in Table 2 is
converted into the encoded table of Table 2. This encoded table can
truth table
a b c
encoded table
c a c
a c b c
c
optimized table
c a c
a c b c
c

Table

2: AND-gate: truth table - encoded table - optimized
table
be interpreted as specifying the on-set as well as the off-set of two
Boolean functions c c and c
c . Conflicting assignmentsbelong to the
don't-care-set, as they are explicitly checked for by the implication
engine. Exploiting these don't-cares, functions c c and c
c in the
encoded table are optimized by ESPRESSO.
2.2 Clause description
The characteristic function describing the AND-gate with respect
to the given encoding can easily be given in its Conjunctive
Normal Form (CNF) by analyzing the individual rows of the optimized
table of Table 2. Every row in this table corresponds to a
clause contained in the CNF. Here, the CNF comprises the three
clauses :c
a - c
c , :c
c , and :c a -:c b - c c . That is, all valid
value assignments to the inputs and outputs of the AND-gate are
implicitly given by the non-conflicting satisfying assignments to
the characteristic equation:
CNF , (:c
a -c
2.3 Building the implication graph
By exploiting the following equivalencies the clause description
of Eq. (1) is converted into the corresponding implication graph.
x-y
It is sufficient to provide equivalencies for binary and ternary
clauses only, as any clause system of a higher order can be decomposed
into a system of binary and ternary clauses [21]. Having
transformed all clauses into binary and ternary clauses, the sub-graphs
shown in Fig. 2 are used for representation of these clauses.
These graphs contain two types of nodes. While the first type rep-
:y
:y
y
z
x

Figure

2: Implication subgraph for a binary and a ternary clause
resents the encoded signal values, the second one symbolizes the
conjunction operation. The latter type is depicted by - or a shaded
triangle. Every ternary clause has three associated -nodes that
uniquely represent the ternary clause in the implication graph.
Coming back to the 2-input AND-gate, its CNF-description is
transformed into the implication graph shown in Fig. 3. Every bit
of the encoding for a signal x is represented by a corresponding
node in the implication graph, e.g. node c a (c
a ) in Fig. 3 gives bit
c a (c
a ) of signal a. As we require non-conflicting assignments, literals
x ) can be replaced by c
x only nodes corresponding
to non-negated encoding bits are contained in Fig. 3.
So far, the implication graph only captures the logic functionality
of a circuit. Since structural information is indispensable for
some tasks, such as justification and propagation, we provide this
information within the implication graph by marking its edges with
three different tags f , b, and o. Edges that denote an implication
from an input to an output signal of a module are marked with f
(forward edge). Relations from output to input signals are tagged
with b (backward edge). All other edges, e.g. input to input relations
and indirect implications, are given tag . The
tags for the 2-input AND-gate are found in Fig. 3. By means of
these tags, a directed acyclic graph (DAG) can be extracted from
the implication graph. If all edges but the forward edges are re-
moved, we obtain a DAG that forms the base of an efficient algorithm
for backtracing and justification.
For a simple circuit, the three different circuit descriptions introduced
above are presented in Ex. 2.1. Please observe that most
clause based approaches work on a CNF in L 2 . Our approach operates
on a CNF of variables encoded with respect to a given logic,
here L 3 .
denoting other edges have been omitted in later examples.
c
c
c
c
a
c c
c a
f
f
f
f

Figure

3: Implication graph for 2-input AND-gate
2.4 Advantages
Using the proposed implication graph as a core data structure in
CAD algorithms has many advantages.
(1) Important tasks such as implication and justification can be
carried out on the implication graph in the same manner for any
arbitrary logic. The peculiarities of the chosen logic are included
in the graph. Implication and derivation of indirect implications
reduce to efficient graph algorithms as will be shown in Sec. 3.3
and 4.4.
(2) Most SAT-based algorithms use a static order for variable assignments
during their search for a satisfying assignment [17, 19].
Furthermore, these algorithms assign values to internal signals during
justification. Since PODEM, it has been well known that assigning
values only to primary input signals helps to reduce the
search space. Obviously, primary inputs are a special property of
the given instance of SAT which is not exploited by algorithms for
solving arbitrary SAT problems. The algorithm of TEGUS tries to
mimic PODEM by ordering the clauses in a special manner [18].
Our approach does not need such techniques, as structural information
is provided by edge tags.
(3) Algorithms working on the implication graph can easily exploit
bit-parallelism as the status of every node can be represented
by one bit only. For example, on a 64-bit machine 64 value assignments
can be processed in parallel, making bit-parallel implication
very efficient.
Sequential circuits are often modelled as an iterative logic array
(ILA). In this model the time domain is unfolded into multiple
copies of the combinational logic block. These logic blocks
can be compiled into the corresponding implication graphs. Using
bit-parallel techniques, a 64-bit machine allows to keep 64 time-frames
without increasing the size of the implication graph.
3 How to perform implications
3.1 Structure based
Structure based implication is a special form of event-driven
simulation. Contrary to ordinary simulation, which starts at the
primary inputs, implication is started at an arbitrary signal in the
circuit. Therefore, it has to proceed towards the primary outputs
as well as the primary inputs such that implications are often categorized
into forward and backward implications. Obviously, this
technique requires many table lookups for evaluating the module
functions. This becomes particularly costly for multi-valued log-
ics, e.g. the ones used in path delay ATPG.
3.2 Clause based
Clause based implication relies on Boolean Constraint Propagation
(BCP). BCP corresponds to an iterative application of the
Example 2.1 Circuit descriptions: structural - clauses - implication
graph
a
c
d
e
f
ffl CNF for
(:c
d -c
e -c
(:c a -c d
a -:c
c -c
ffl Implication graph for
f
f
f
f
f
f
f
f
f
f
f
f
f
c d c e
c
f
c
c
d
c
e
c
a
c
c
c c
c a c b
unit clause rule proposed by Davis et al. in 1960 [22]. In BCP,
unary clauses are used to simplify other clauses until no further
simplification is possible or some clause becomes unsatisfied. Implication
is started by adding a unary clause, which represents the
initial signal assignment, to the CNF. All unary clauses computed
by BCP correspond to implications from the initial assignment as
they force the corresponding signals to a certain logic value. The
most time consuming task in BCP is the search for clauses that can
be simplified by the unit clause rule. This search is not necessary
when working on the implication graph since clauses that share
common variables are connected in the graph.
3.3 Implication graph based
Implication graph based implication is simple and efficient, as it
only requires a partial traversal of the implication graph. Implying
from a signal assignment means that first the corresponding nodes
are marked in the implication graph. Then, the implication procedure
traverses the implication graph obeying the following rule:
Starting from an initial set S I of marked nodes, all successor
nodes s j are marked
ffl if node s j is a -node and all its predecessors are marked.
ffl if node s j represents an encoding bit and at least one predecessor
is marked .
This rule is applied until no further propagation of marks is possible

All nodes that have been marked represent signal values that can
be implied from the initial assignment given by S I . Conflicting signal
assignments are easily detected during implication, since they
cause both nodes c x and c
x to be marked.
Let us use the circuit of Ex. 2.1 for the sake of explanation. Assigning
logical value 0 to signal e corresponds to marking node
c
e in the implication graph. After running the implication proce-
dure, the following nodes are marked: c
c and c
f . To finally
obtain the implied signal values with respect to the given logic, the
marked nodes are decoded according to the given encoding, i.e. we
determine
Deriving indirect implications
Contrary to direct implications, detection of indirect implications
requires a special analysis of the logic function of a circuit as
they represent information on the circuit that is not obvious from
its description. Most methods for computation of indirect implications
are subject to order dependency. That is, some indirect implications
can only be found if certain other indirect implications
have already been discovered. In order to avoid this problem, it has
been suggested to iterate their computation [18].
4.1 Structure based
The SOCRATES algorithm [12] was the first to introduce computation
of indirect implications using the following tautologies:
While Eq. (4) (law of contraposition) may generate a candidate for
an indirect implication, Eq. (5) identifies a fix value.
Indirect implications are primarily computed in a pre-processing
phase. The idea is to temporarily set a given signal to a certain
logic value. Then, all possible direct implications from this signal
assignment are computed. For all implied signal values, it is
checked if the contrapositive cannot be deduced by direct implications
(learning criterion). In this case, the contrapositive is an indirect
implication. As indirect implications cannot be represented
within the data structure used to describe the circuit, structural algorithms
have to store them in an external data structure. This adds
additional complexity to structure based algorithms.
4.2 Clause based
Clause based computation [17, 18] is similar to the structural algorithm
of Sec. 4.1. Each free literal a contained in the CNF is
temporarily set to 1. Then BCP is used to derive all possible direct
implications, i.e. unary clauses. For all generated unary clauses
b, it is checked if the contrapositive :b ! :a is an indirect im-
plication. In this case, the corresponding clause b -:a is added
to the clause database. Thereby, indirect implications enrich the
data structure used for representing the circuit functionality. Once
an indirect implication has been added to the clause database, it
does no longer require any special attention. This is one important
advantage of clause based algorithms over structure based approaches
[18].
4.3 AND-OR enumeration
A different approach, known as recursive learning, has been
taken by Kunz et al. [3, 7]. Indirect implications are deduced by an
search [23] for all possible implications resulting from
a signal assignment. This search is performed by recursively injecting
and reversing signal assignments, which correspond to the
different possibilities for justifying a gate, followed by deriving all
direct implications. Signal values that are common to all justifications
of a gate yield indirect implications. Only a simple structural
algorithm for executing implications is applied.
Let us illustrate the principles of the AND-OR enumeration with
the circuit of Ex. 2.1 and the AND-OR tree found in Fig. 4. The
level 2
level 0
initial assignment f
level 1

Figure

4: AND-OR enumeration
root node of the AND-OR tree reflects the initial assignment, it
is of the AND-type 2 . In our example, a logical 0 is assigned to
signal f . As no further signal values can be implied, OR-node
is the only successor of the root node. The justifications for
0g. In order to derive an
indirect implication, we have to search for implied signal values
that are common to both justifications. Here, implied for
both justifications. This is represented by a new OR-node
level 0 of the AND-OR tree. In general, new OR-nodes in level 0
correspond to indirect implications. Further examination of gates
in level 2, which have become unjustified because of setting b to 0,
does not yield additional indirect implications.
4.4 Implication graph based
An implication graph based method for computing indirect implications
inherits all advantages of clause based techniques but
eliminates the costly search process required during BCP-based
implication. Moreover, our approach integrates computation of indirect
implications based on the law of contraposition and AND-OR
enumeration into the same framework.
In general, an AND-node (marked by an arc) represents a signal assignment
due to justification of an unjustified gate, whereas an OR-node
denotes a signal value that can be implied from a chosen justification. Justified
gates correspond to OR-leaves and unjustified gates to internal OR-nodes
in the AND-OR graph [3].
4.4.1 Reconvergence analysis
The basic idea of determining indirect implications by a search
for reconvergencies is shown in Fig. 5. While implication c a ! c b
c
a
indirect
direct
c
c
x
c x
c
a
c a -

Figure

5: Learning by contraposition on the implication graph
is deduced by direct implication, c
a forms an indirect impli-
cation. The -node can only be passed if both of its predecessors
are marked, i.e. it forms a reconvergent -node during implication.
If we start implication at node c
b , however, we cannot pass the -
node, as its other predecessor c x is not marked. Applying the law
of contraposition to c a ! c b , we deduce c
a such that c
a is
implied from c
b .
This observation is expressed in the following lemma:
assignment. A reconvergent
structure
c y ) in the implication graph yields an indirect implication
c
x only if
ffl c x is a fanout node in the implication graph.
ffl a node c y is marked via a -node and both predecessors
of the -node have been marked by implying along disjoint
paths in the implication graph. (Proof: [21])
Using Lemma 1 it can be shown that the search for reconver-
gencies in the implication graph detects all indirect implications,
which are found by clause and structural based approaches.
implications found by BCP on the (en-
coded) clause description can be identified by a search for the reconvergent
structures defined in Lemma 1. (Proof: [21])
We explain the reconvergence analysis with the implication
graph of Ex. 2.1. Let's assume that fanout node c b is marked.
Then, the implication procedure of Sec. 3.3 is invoked. As both
c d and c e have been marked, the succeeding -node and c f are
marked, too. The -node has been reached via two disjoint paths
in the graph (indicated by the dashed and solid line, respectively)
such that the contrapositive c
b forms an indirect implication.
This indirect implication is included into the graph in form of the
grey edge leading from node c
f to node c
b .
Applying our graph analysis offers the following advantages:
(1) The search for reconvergence regions in the implication graph
reduces the set of candidate signals that may yield an indirect im-
plication. Clause based methods have to temporarily assign a value
to all literals contained in the CNF.
(2) Reconvergence analysis is carried out very fast by an adapted
version of the algorithm presented in [24].
(3) Our method does not require a learning criterion such as the
approach of [12].
4.4.2 Extended reconvergence analysis
Contrary to the reconvergence analysis of Sec. 4.4.1, the extended
reconvergence analysis detects conditional reconvergencies
at signal nodes. As it corresponds to an AND-OR search in the
implication graph, we need the following definitions:
clause C= c 1 -c 2 -c n is called unjustified
do not evaluate to 1 and at least one
complement :c i of a literal c i is 1.
Unjustified ternary clauses are found in the implication graph without
effort. They are represented by -nodes that have exactly one
of their two predecessors marked.
unspecified literals in a
that is unjustified, and let V 1
denote the assigned values. Then, the set of non-conflicting assignments
is called a justification
of clause C, if the value assignments in J makeC evaluate to 1.
In a clause based framework a complete set of justifications J c for
an unjustified clause C is easily given by J
1gg. For our approach, set J c is even simpler, as only
ternary clauses can be unjustified. 3 Therefore, J c always consists
of exactly two justifications.
We will now explain how these two justifications can be derived
in the implication graph with Fig. 6. The given ternary clause
c y c x
c
z
c
x
c z
c
y

Figure

Unjustified ternary clause c x -c y -c z due to assignment
c
z is unjustified due to an assignment of c
is indicated by the two -nodes that have exactly one predecessor
Here, the ternary clause can be justified by setting c z
or c y to 1. If we consider that the subgraph denoting the ternary
clause c x - c y - c z is a straightforward graphical representation of
the following formulae
c
x -c
x -c
y -c
it becomes apparent that both possible justifications in J c are found
in the consequents of those implications which have the literal
making the clause unjustified, i.e. c
x , in their antecedent. These
consequents correspond to the successors of the two -nodes.
Let us now explain how the extended reconvergence analysis
corresponds to an efficient AND-OR search on the implication
graph with help of Fig. 7 showing the implication graph of Ex. 2.1.
An initial assignment of c
clause C
unjustified. Next, the possible justifications J a
are determined as the successors of the two -
nodes a 1 and a 2 belonging to clause C a . These -nodes correspond
to AND-nodes J a 1 and J a 2 in the AND-OR tree, respec-
3 If a binary clause is unjustified according to Definition 2, it reduces
to a unary clause. Unary clauses represent necessary assignments (implied
signal values) for the given signal assignment.
tively. So as to distinguish between the consequences of the two
justifications, each one is assigned a different color. Thus, node
c
marker (represented by dashed lines in
Fig. 7) and all signals that can be implied from c
are marked
green. The same is done for c
using a red marker (dotted
lines in Fig. 7). Nodes that are assigned both colors, i.e. nodes
where the markers reconverge, can be implied independent of the
chosen justification. These nodes can therefore be elevated to the
previous level in the AND-OR tree. In our example, only node
c
b is marked by both colors and we derive the indirect implication
c
b . Further analysis of unjustified clauses C b and C g in level
2 of the AND-OR tree does not yield additional indirect implications

This example indicates that the trace of the extended reconvergence
analysis is identical to the AND-OR tree generated by AND-OR
enumeration if marked -nodes are converted to AND-nodes
and marked signal nodes to OR-nodes. Obviously the extended
reconvergence analysis is capable of determining all indirect implications
given enough colors, i.e. it is complete.
An efficient procedure implementing this extended reconvergence
analysis is given in [21]. It takes advantage of the implication
graph by encoding the colors locally at the nodes using only
bit slices of a full machine word. Thus, subtrees of the AND-OR
tree are stored in parallel in different bit-levels. Additionally, a bit-parallel
version of the implication algorithm introduced in Sec. 3.3
is used. Our algorithm supports a depth of r levels in the AND-OR
tree on a 2 r -bit architecture. On a DECAlphaStation, for example,
a maximal depth of 6 levels is available.
Let us briefly summarize the advantages of our
(1) The implication graph model allows the full word size to be
exploited by means of bit-parallel techniques. The search for indirect
implications, requires efficient set operations as an OR-node
may only be elevated if it is a successor of both AND-nodes belonging
to an unjustified clause. These set operations are carried
out effectively on the implication graph by performing local bit-operations
at signal nodes such that no separate data structure is
needed. Please note, that the advantage of efficient set operations
remains, if we extend our algorithm to handle arbitrary depths of
AND-OR enumeration, which has already been done.
(2) The notion of unjustified gates necessary in [3, 7] reduces to
the simple concept of unjustified ternary clauses. Due to this concept
and the uniformity of our description, AND-OR enumeration
can easily be performed for arbitrary logics applying the same pro-
cedure. This has already been done for logic L 10 . On the contrary,
higher valued logics are complicated to deal with in the structural
approach of [7, 3].
(3) Detected indirect implications can be included into the graph
immediately, which often facilitates the computation of other indirect
implications.
(4) Some indirect implications are easily computed by the law of
contraposition while requiring a high depth of AND-OR search.
As our approach integrates both methods into one framework, indirect
implications can be identified by the best suited technique.
5 Experimental results
The implication engine, presented in this paper, has been implemented
in a C language library of functions that has been applied
successfully to several CAD problems. Please note, that some of
c d c e
c
f
c
c
d
c
e
c
a
c
c
c c
c a c b
level 2
level 1
level 0
J a
initial assignment fc
c
c
c
c
c
c
a 3 a 1
J a
a 2

Figure

7: Extended reconvergence analysis on the implication graph
the presented results have already been published in papers dealing
with application specific issues. The underlying implication
engine was not discussed. We have included these results in order
to show the efficiency of our flexible approach. While the experiments
for ATPG and netlist optimization were carried out on
a DECStation3000/600, the experiments for equivalence checking
were performed on a DECAlphaStation250 4=266 . ATPG and netlist
optimization rely on an earlier version of our implication engine,
that does not support the techniques of Sec. 4.4.2. So far, these advanced
techniques have only been used for equivalence checking.

Table

3 presents results for ATPG considering various fault models
[25, 26, 27]. Due to the flexibility of the implication graph
non-robust robust stuck-at
c5315 342117 643.4 81435 5251.8 5291 1.2
c7552 277244 1499.4 86252 5746.0 7419 5.2

Table

3: Result of test pattern generation
the various logics (L 3 required for the different fault
models could easily be handled. Table 3 gives the number of tested
faults and CPU time required for performing ATPG for non-robust
and robust path delay faults as well as stuck-at faults in combinational
circuits (or sequential circuits with enhanced scan design).
The excellent quality of the achieved results can be seen from fur-
circuit # gates # literals delay time
before after before after before after [s]
c1908 488 402 933 803 41.2 33.9 1364
red.: 8.1% 3.2% 18.8% -

Table

4: Results of delay optimization
ther tables in [25, 26, 27] where an extensive comparison to other
state-of-the-art tools is made.
Results for optimization of mapped netlists with respect to delay
are provided in Table 4. The basic idea and the approach, that
applies our implication engine to verify the permissibility of circuit
transformations, is described in [6]. The number of gates, literals,
and the circuit delay before and after optimization, as well as the
required CPU time are given.
Results for equivalence checking of netlists are presented in Table
5. It lists the total time required for equivalence checking, i.e.
circuit time[s] level max
total indirect implications
c432 1.3 1.2 1

Table

5: Results for verifying against redundancy free circuits
ATPG plus computation of indirect implications, and the time consumed
by the latter in columns 2 and 3, respectively. The maximal
depth of AND-OR search necessary for successful verification is
also given in column 4. We provide these early results in order
to show that our implication engine forms a suitable data structure
for building an efficient equivalence checker. Our straightforward
approach adopts the basic idea of the well-known equivalence
checker HANNIBAL [28] but does not include its advanced heuris-
tics, e.g. observability implications and heuristics for candidate se-
lection. Nevertheless, the results shown in Table 5 are comparable
to the ones reported in [28]. This indicates that our implication
engine is well suited for equivalence checking. Please note, that it
is easily incorporated into state-of-the-art implication based or hy-
brid, i.e. BDDs combined with implications, equivalence checkers
such that these approaches can benefit, too.
6 Conclusion
In this paper we have proposed an efficient implication engine
working on a flexible data structure called implication graph. It
has been shown that indirect implications can be effectively computed
by analysis of the graph. Experimental results confirm the
efficiency and flexibility of our approach.
In the future, our preliminary equivalence checker will be extended
by deriving observability implications directly on the implication
graph. Furthermore, we will investigate how a hybrid
technique using BDDs and the implication graph can be advantageous
for equivalence checking.

Acknowledgements

The authors are very grateful to Prof. Kurt J. Antreich for many
valuable discussions and his advice. They like to thank Bernhard
Rohfleisch and Hannes Wittmann for using the implication engine
in the netlist optimization tool and developing the path delay ATPG
tool, respectively.



--R

"Multi-level logic optimization by implication analysis,"
"LOT: Logic optimization with testability - new transformations using recursive learning,"
"And/or reasoning graphs for determining prime implicants in multi-level combinational networks,"
"Combinational and sequential logic optimization by redundancy addition and removal,"
"Perturb and simplify: Multi-level boolean network optimizer,"
"Logic clause analysis for delay optimization,"
"Recursive learning; a new implication technique for efficient solutions to cad problems - test, veri- fication, and optimization,"
"Advanced verification techniques based on learning,"
"A novel framework for logic verification in a synthesis environment,"
"Verilat: Verification using logic augmentation and transformations,"
"Aquila: An equivalence verifier for large sequential circuits,"
"Socrates: A highly efficient automatic test pattern generation system,"
"Improved deterministic test pattern generation with applications to redundancy identification,"
"Accelerated dynamic learning for test pattern generation in combinational circuits,"
"Functional learning: A new approach to learning in digital circuits,"
"Static logic implication with application to redundancy identification,"
"Test pattern generation using boolean satisfiability,"
"Com- binational test generation using satisfiability,"
"A transitive closure algorithm for test generation,"
"Grasp - a new search algorithm for satisfiability,"
"A sat-based implication engine,"
"A computing procedure for quantification theory,"

"A method of fault simulation based on stem regions,"
"A formal non-heuristic atpg approach,"
"Bit parallel test pattern generation for path delay faults,"
"Path delay atpg for standard scan designs,"
"Hannibal: An efficent tool for logic verification based on recursive learning,"
--TR
Artificial intelligence
Perturb and simplify
Multi-level logic optimization by implication analysis
Advanced verification techniques based on learning
Logic clause analysis for delay optimization
Path delay ATPG for standard scan design
A formal non-heuristic ATPG approach
VERILAT
GRASPMYAMPERSANDmdash;a new search algorithm for satisfiability
A Computing Procedure for Quantification Theory
Bit parallel test pattern generation for path delay faults
Static logic implication with application to redundancy identification

--CTR
Joo Marques-Silva , Lus Guerra e Silva, Solving Satisfiability in Combinational Circuits, IEEE Design & Test, v.20 n.04, p.16-21, January
F. Lu , M. K. Iyer , G. Parthasarathy , L.-C. Wang , K.-T. Cheng , K. C. Chen, An Efficient Sequential SAT Solver With Improved Search Strategies, Proceedings of the conference on Design, Automation and Test in Europe, p.1102-1107, March 07-11, 2005
Alexander Smith , Andreas Veneris , Anastasios Viglas, Design diagnosis using Boolean satisfiability, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.218-223, January 27-30, 2004, Yokohama, Japan
Paul Tafertshofer , Andreas Ganz, SAT based ATPG using fast justification and propagation in the implication graph, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.139-146, November 07-11, 1999, San Jose, California, United States
Sean Safarpour , Andreas Veneris , Rolf Drechsler , Joanne Lee, Managing Don't Cares in Boolean Satisfiability, Proceedings of the conference on Design, automation and test in Europe, p.10260, February 16-20, 2004
Ilia Polian , Bernd Becker, Multiple Scan Chain Design for Two-Pattern Testing, Journal of Electronic Testing: Theory and Applications, v.19 n.1, p.37-48, February
Christoph Scholl , Bernd Becker, Checking equivalence for partial implementations, Proceedings of the 38th conference on Design automation, p.238-243, June 2001, Las Vegas, Nevada, United States
Ilia Polian , Hideo Fujiwara, Functional constraints vs. test compression in scan-based delay testing, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
Lus Guerra e Silva , L. Miguel Silveira , Joa Marques-Silva, Algorithms for solving Boolean satisfiability in combinational circuits, Proceedings of the conference on Design, automation and test in Europe, p.107-es, January 1999, Munich, Germany
E. Goldberg , M. Prasad , R. Brayton, Using SAT for combinational equivalence checking, Proceedings of the conference on Design, automation and test in Europe, p.114-121, March 2001, Munich, Germany
Joo Marques-Silva , Thomas Glass, Combinational equivalence checking using satisfiability and recursive learning, Proceedings of the conference on Design, automation and test in Europe, p.33-es, January 1999, Munich, Germany
Ilia Polian , Hideo Fujiwara, Functional Constraints vs. Test Compression in Scan-Based Delay Testing, Journal of Electronic Testing: Theory and Applications, v.23 n.5, p.445-455, October   2007
Ilia Polian , Alejandro Czutro , Bernd Becker, Evolutionary Optimization in Code-Based Test Compression, Proceedings of the conference on Design, Automation and Test in Europe, p.1124-1129, March 07-11, 2005
Joo P. Marques-Silva , Karem A. Sakallah, Boolean satisfiability in electronic design automation, Proceedings of the 37th conference on Design automation, p.675-680, June 05-09, 2000, Los Angeles, California, United States
Ilia Polian , Bernd Becker, Scalable Delay Fault BIST for Use with Low-Cost ATE, Journal of Electronic Testing: Theory and Applications, v.20 n.2, p.181-197, April 2004
efficient ATPG;structure based methods;SAT-based implication engine;logic circuits;implication evaluation;indirect implications;implication graph;equivalence checking;graph algorithms;netlist optimization;automatic testing;graph model;circuit clause description