Multiple Experiment Environments for Testing.
Concurrent simulation (CS) has been used successfully as a replacement for serial simulation. Based on storing differences from experiments, CS saves storage, speeds up simulation time and allows excellent internal observation of events. In this paper, we introduce Multiple Domain Concurrent Simulation (MDCS) which like concurrent simulation, maintains efficiency by only simulating differences. MDCS also allows experiments to interact with one another and create new experiments through the use of domains. These experiments can be traced and observed at any point, providing insight into the origin and causes of new experiments. While many experiment scenarios can be created, MDCS uses dynamic spawning and experiment compression rather than explicit enumeration to ensure that the number of experiment scenarios does not become exhaustive. MDCS does not require any pre-analysis or additions to the circuit under test. Providing this capability in digital logic simulators allows more test cases to be run in less time. MDCS gives the exact location and causes of every experiment behavior and can be used to track the signature paths of test patterns for coverage analysis.We will describe the algorithms for MDCS, discuss the rules for propagating experiments and describe the concepts of domains for making dynamic interactions possible. We will report on the effectiveness of MDCS for attacking an exhaustive simulation problem such as Multiple Stuck-at Fault simulations for digital logic. Finally, the applicability of MDCS for more general experimentation of digital logic systems will be discussed.
Introduction
Concurrent Simulation(CS)[1, 2] has been proven
to be powerful and efficient for simulating single
stuck-at faults but inadequate for exhaustive applications
like Multiple Stuck-at Fault (MSAF)
simulations. It was developed as a speedup mechanism
over serial simulation, thus experiments are
independent and incapable of interacting with one
another. Cumulative behaviors which are combinations
of experiments cannot be created without
approaching exhaustive testing. This usually
requires either modifying the circuit [10] or
performing some back-tracing [14]. The methods
presented here leverage on the efficiencies of concurrent
simulation, but do allow scenarios of experiments
to be dynamically spawned should independent
experiments interact. Any experiment
that does not create a state difference from a parent
experiment is not propagated. This effectively
"compresses" experiments in the simulation.
CS[1] has a primary experiment that exhibits
the fault free or good behavior of a circuit. This
reference experiment exists during the entire sim-
ulation. Faulty experiments that differ or diverge
from the reference require additional independent
bursts of simulation time. Experiment behaviors
can be observed and contrasted since each experiment
propagated leaves a signature (its identifier).
Unfortunately, CS cannot allow independent experiments
to interact at all. It is a cost-effective
solution for serial simulation, where each fault inserted
creates a single experiment that can only
see fault effects it creates and the reference exper-
iment. As we will show, to modify it to accommodate
such functionality would defeat the overall
efficiency and would produce inaccurate observation
results.
Our simulation environment allows multiple domains
of experiments to be defined so that combinations
of independent experiments may be efficiently
simulated. It is not necessary to generate
every possible combination of experiments.
Only those experiments that arrive at the same
node in the network will be tested as candidates
for spawning of new behaviors. This eliminates
This work is sponsored by the National Science Foun-
dation, MIP-9528194 and the National Aeronautics and
Space AdministrationLangley Research Center NASA-JOVE.
a huge number of potential scenarios that could
arise from exhaustive testing. In addition, every
experiment in the simulation can be compressed
via the same mechanism of concurrent simulation
(i.e., only differences are propagated). Unlike CS
where there is only a single reference experiment,
we allow any number of independent experiments
to serve as parents.
Details on performing Multiple Stuck-at Fault
are presented here as evidence
of the framework's success for digital logic. We
were motivated to choose the MSAF application
because it demonstrates the large (even exhaus-
tive) number of experiments needed to be per-
formed. It is also a good test bed for verifying
the correctness of "compression" and interaction
features since digital logic outputs are limited to
a finite number of states (0,1,X,Z). Furthermore,
the availability of ISCAS benchmark circuits[3, 4]
made it possible for us to compare our performance
against other applications.
This paper is organized as follows. First, we will
provide necessary background information on CS.
We will then describe some of the inefficiencies of
trying to use CS for creating scenarios of experiment
combinations. Next, we introduce the concept
of domains, parent experiments as dynamic
references for compression, the use of identifiers
which are needed to observe experiments, and the
spawning of new experiments that display cumulative
behaviors. Once these fundamental methods
are understood, we will then present the Multiple
Domain Simulation algorithm.
2. Background
Since we leverage on many of the features of Concurrent
Simulation, we provide a brief discussion
of it here for background information. Consider
the following analogy: an engineer is assigned to
build an adder circuit. After developing the adder
design, the engineer is told she must now build a
calculator that does both addition and subtrac-
tion. If she took a "serial" approach, she would
start designing the adder circuitry all over again,
ignore the work she has already done, and then develop
the subtractor circuit independently of the
adder design. Likewise, in a concurrent approach,
the engineer would try to leverage on the adder
Multiple Experiment Environments for Testing 31 1101
I 1
I 2
Fault Sources I 1 I 2 Out1Gate Evaluations
R= no faults
Fig. 1. Conceptual copies indicate all the scenarios to be
evaluated
design as well as concentrate design efforts on the
new and different functionality required, such as
integrating a subtractor into the existing design.
In concurrent simulation, the simulation of identical
behaviors(reference and faulty) is performed
only once. Additional simulation time is dedicated
to those faulty experiments that are different.
Since the goal of CS is to produce simulation
results equivalent to simulating each fault
separately, it needs to create simulation scenarios
for any inserted fault and the reference case.
The main idea is to evaluate these scenarios, and
then propagate only those that create state dif-
ferences. There are many methods to implement
Reference Case
Fault C1
Fault C2
Fault C3
Fault C4
Current List
Look-Ahead List
Experiments
C
R 3 (1) R 3 (1)C (0)
R 3 (1) R 3 (1)
R
R 3 (1) R 3 (1)
R (1)
R 3 (1) R 3 (1)
R 3 (1)R (1)
The gate after evaluation of experiment C 1
R 3 (1)R (1)
The current list for evaluating fault scenario on
Input 1 of the gate.L 1
I 2
I 1
I 2
Fig. 2. Current and Lookahead Lists for processing experiments
in a Multiple List Traversal(MLT) algorithm
this scheme but the most efficient single CPU algorithm
is the Multiple List Traversal(MLT)[5].
Before describing the MLT implementation let us
present a basic concurrent fault simulation algorithm

Figure

1 shows a single NAND gate to be
simulated. The reference value is denoted by R i
for each input and output list, where i is the list
number. The conceptual copies in Figure 1, shown
as dashed NAND gates, indicate all the scenarios
that must be evaluated for the single stuck-at
faults inserted on the inputs of the NAND gate.
Each fault scenario is derived by replacing the reference
value with a faulty state value for the specified
input. For example, C 1 is a single stuck-at-1
fault on input I 1 of the NAND gate. From the
table of fault sources and their respective evaluations
in Figure 1, it can be seen that only one of
the four faults inserted will produce a state value
on the output different from that of the reference
output. Fault scenario C 1 produces a state of 0
on the output while, the reference produces a state
value of 1. Only C 1 is propagated. The absence of
the other fault experiments indicates that they are
behaving identically to the reference experiment.
The faults are physically stored on the input
or output list on which they are deposited, as
shown in Figure 2(A). Experiments are denoted
in the form identifier(statevalue). For exam-
ple, C 1 (1) is concurrent experiment 1 with a state
value of 1. The MLT algorithm is straightforward.
Each input along with the output list is traversed
and an experiment scenario is evaluated based on
the type of experiment encountered(reference or
fault). The output list must also be traversed
to properly insert any experiments propagated or
to update states for a specific experiment. The
MLT algorithm dynamically creates scenarios to
be evaluated by pointing to a single experiment
from each input and output list. These pointers
are stored in a current list denoted by L c . The reference
experiment is the first scenario to be eval-
uated. It is created by pointing at the reference
states on each list (see the first row of the table in

Figure

2). As the input and output lists are tra-
versed, the lowest experiment identifier from all
lists is chosen as the "next" experiment to be pro-
cessed. A lookahead list 1 maintains this information
so that when the MLT is ready to process another
experiment, it has already determined which
experiment is next. For example, in the table of
4 Lentz, Manolakos, Czeck and Heller

Figure

2, after the reference case is evaluated, the
look-ahead list indicates that input 1 contains the
next lowest faulty experiment identifier of all the
three lists. Therefore, the next experiment to be
processed will be the experiment for fault C 1 . The
experiment C 1 is created by pointing to any
states present on any list. If present on a
list L i , the fault state of C 1 is used to replace the
reference value on L i , while using the reference
value for any other list on which the fault does
not appear. Figure 2A demonstrates this by the
dashed lines. These lines show the experiments selected
to create L c for generating the experiment
for C 1 . C 1 is selected from list L 1 . Since C 1 does
not appear on any other list, the current list will
point to the reference experiments on these input
and output lists. This will create a scenario that
will evaluate 1). Thus the
evaluated state of C 1 equals zero. Notice that the
MLT also maintains a pointer for the output list
to quickly determine whether the faulty experiment
is already present or whether a comparison
against the output reference value should be per-
formed. This same information is also depicted in
the table row labeled C 1 in Figure 2. After evaluating
this case and comparing the state value of
to that of the Reference state R 3 (1), we see
that there is a difference and that the experiment
should be propagated to the output. Since
the current list indicates that the output list does
not contain storage for experiment C 1 already, the
MLT allocates space and updates the output list.
This is shown in Figure 2B.
To summarize, the MLT traverses all the lists,
all inputs and output lists simultaneously. It does
a look-ahead to determine which experiment is
coming up next on each list so it can quickly determine
if the same fault ID is present on more than
1 input or whether it is already present on the
output. The look-ahead information is stored in a
circular linked list. The experiment scenario to be
evaluated is derived from the look-ahead informa-
tion. The lowest identifier (the reference value on
each list is used to determine the reference state
on the output. The next higher id is then chosen
from the lookahead information and used to create
a scenario for that specific fault experiment.

Figure

3 describes the high level algorithm for the
simultaneous list traversal portion of the MLT algorithm
and the table of Figure 2 enumerates all
the scenarios.
Events can be scheduled in the future due to
any triggered experiment. (i.e., any experiment
that is active for the current simulation time). Let
concurrent experiment with identifier
k, with an current state value of V 0 .
3. Issues Associated with Exhaustive Scenario

Since efficient simulation algorithms [2, 6, 11] only
look at single stuck-at fault (SSF) scenarios versus
the reference experiment behavior, experiment
interaction for combinations of SSFs is not possi-
ble. For an MLT implementation of CS, modifications
would be necessary to accommodate building
scenarios of multiple stuck-at faults to simu-
late. Recall, the basic MLT algorithm only substitutes
the reference value with a single faulty value.
Fault scenarios do not interact, nor are they aware
of each others' existence. Despite this, to implement
MSAF with the CS MLT would require that,
for every fault inserted in the network, an N way
combination of every fault with every other fault
be inserted. This would represent, each 2 way,
3 way.N way combination of a fault with every
other fault.
In general, given a network with N inputs and
one single stuck-at fault deposited on every input
that can combine with single-stuck-at faults
on another input, the number of multiple stuck-at
fault sources which must be inserted can be determined
by equation 1, where N equals the number
of faults in the set; i is the multiplicity of faults.
(1)
This shows that the amount of storage for
all these combinations of fault scenarios would
greatly reduce the efficiency of CS by increasing
list lengths and thus list traversal times. Further-
more, when these fault scenarios are inserted, they
must be assigned a state value to be used by that
experiment. Typically, the state value chosen is
that of the single stuck-at fault value on the same
line, when two or more faults have not yet in-
teracted. Figure 4 demonstrates this. There are
Multiple Experiment Environments for Testing 5
Initialize network and time wheel
While (an event exists on time wheel for T, where T= current time)
For each element E i
apply Reference or Concurrent fault state value changes
For each input and output list
if (an R experiment is triggered)
call evaluation code for E i using all reference (non-faulty) state values
schedule a new event for time propagation delay, if necessary
For each Ck present at
update current and look-ahead lists
experiment identifiers present
on all inputs and output lists of
For each Input and output List, L j for
If L j does not contain experiment CID then
Insert a pointer to R i (statevalue) into the
current list L c for list L j
else
Insert a pointer to C i (statevalue) into L c for list L j
Update the lookahead list L o by inserting a pointer
to the next identifier present on L j
Using the state values from experiments pointed at by L c
begin evaluation of experiments
For scheduled Ck experiments for Time T
call evaluation code for
if (Ck
if (Ck is not on present on the output list)
propagate fault Ck as a fault effect
schedule event for Ck at time T propagation delay
else Ck
converge Ck
End For each element E i
End While
Fig. 3. Multiple List Traversal Algorithm (MLT)
three single stuck-at faults inserted, one on each
input. Combinations of all two-way and three-way
combinations must be stored when faults are
inserted. A by-product of creating the multiple
stuck-at experiments in this manner is the
degradation of observation. All experiments are
assigned unique identifiers, so that when propa-
gated, it can be traced and observed. The presence
of any specific identifier on an input or output
list should indicate that the experiment has
propagated there. Therefore if a MSAF identifier
is seen, one would expect it to indicate that the
MSAF has been propagated. For instance, in Figure
4, it appears that a three-way MSAF C 1 C 2 C 3
occurred at the output of gate E 1 . In fact, this
identifier was only carried forward because it is a
copy of the two-way stuck-at C 1 C2. The distinction
of whether an identifier's presence is due to
a single-stuck-at experiment or a MSAF can not
be determined without further detailed analysis
or back-tracing. It should be clear from the figure
that it is not possible for a three-way stuck-at
to occur at the output of this gate since C 3 is a
6 Lentz, Manolakos, Czeck and Heller
I 1
I 2
I 1
I 2
I 1
R
R
R
R
R
R
Fig. 4. Storage problems associated with MSAF simulation using Concurrent Simulation.
stuck-at on the primary input of E 2 . These issues
are eliminated in a Multiple Domain Simula-
tion. MDCS creates a separation of experiments
into classes called domains and eliminates both
the storage problem and observation impairment.
4. Defining the Experiments Through Domain

In developing an algorithm that allowed independent
experiments to interact while still performing
the single set of fault experiments, it was important
that the method avoid modifying the circuit
by adding additional hardware[10] and avoid
back-tracing for observing events or performing
analysis[14]. To achieve this, the concept of Domains
is introduced. Domains separate the original
independent experiments into classes. Different
experiments contained within the same domain
are by definition not allowed to interact with
one another. They are analogous to the independent
single-stuck-at fault sources. These experiments
define the original parent experiments.
For fault simulation, a single domain may contain
a set of single-stuck-at fault experiments,
ng. Each experiment C i within
A will be evaluated independently and will never
know of the presence of any other experiment C j
within A. In other words, single domain simulation
is the same as traditional concurrent fault
simulation. If another domain B is added, then
experiments contained in domain B are simulated
independently. However, interactions between experiments
contained in A are allowed to interact
and cause cumulative behaviors with those experiments
in domain B. This is an example of a two-
domain simulation, where two sets of experiments
in domains A and B, are simulated independently
and any interactions that may occur between experiments
in different domains are also simulated.
Interacting experiments that cause new behaviors
not displayed by any "parent" are propagated or
"spawned". Experiments fitting this description
are called "offspring" experiments.
By using domains, MDCS achieves efficiency
in experiment storage and, as will be discussed
later, also helps screen experiments before they
are simulated, thus saving processing time. Domains
minimize storage since only the original set
of single stuck-at faults is inserted and does not
require additional storage for defining potential
combinations of MSAFs. MSAFs experiments will
be created dynamically only if two or more fault
experiments meet at a node within the network.
As an example, if two sets of SSFs, each containing
faults were to be simulated for 2 way
stuck-at scenarios, MDCS would define two domains
and insert N experiments in each domain
for a total of 2 \Theta N parent experiments. Each
fault in the original sets of SSFs would be simulated
in addition to any two-way stuck-at that
may arise. We emphasize only two-way stuck-ats
that may arise because the input patterns may
Multiple Experiment Environments for Testing 7
never provide the stimulus to make these potential
interactions occur.
In addition to storing the fault experiments, it
is still necessary to store the reference experiment.
In general, the number of parent experiments necessary
for a simulation using Multiple Domain al-
is:
where m equals the number of defined domains
and n i equals the number of experiments contained
in domain i.
4.1. Creating Dynamic Scenarios of Experiments
It has already been mentioned that different experiments
within domains are not allowed to interact
with each other. It could be said that these
experiments do not "see" each other. However,
it is desired that experiments from different domains
should be allowed to interact and see one
another. This means experiments need to know
about the presence of other experiments from different
domains should they ever propagate to the
same node in a network. From this requirement,
a set of rules were derived to determine which experiments
should be checked for cumulative new
behaviors when this situation does occur. Experiments
that satisfy these rules will be called
combinable[9]. Other combinations of experiments
that may be present but are not combinable will
not be simulated.
Since MDCS is a discrete-event simulator algo-
rithm, it only processes those experiments that are
triggered, (active for the current simulation time).
Therefore, one requirement for a combinable scenario
of experiments is that it contain at least one
trigger.
In general, a scenario consisting of two or more
experiments is created and simulated if the following
are satisfied:
ffl There must be at least one trigger present in
a scenario for it to be evaluated.
ffl Experiments do not share any common domains
ffl Experiments in the scenario that do have common
domains must be related.
Either as a parent and offspring experiment

Or the scenario must contain the same experiments
from common domains.

Figure

5 describes the relationship of domains
and experiments in a simulation. The reference
is always considered to be a parent experiment to
any other experiment and is therefore combinable
with all other experiments. The reference is the
basic experiment to which all other experiment
behavior is compared. In addition, offspring experiments
should be compared to their parents for
similar behavior. If a parent experiment is present
and its state value is identical to the evaluated sce-
nario, it will be used to suppress the propagation
of the offspring created. If experiments are not related
as parent and offspring, then they may be related
by an identical experiment in a common do-
main. For instance, in Figure 5, A
are not related as a parent and offspring. They
are however, related by the fact that experiment
is common to both experiments. Namely, experiment
number 1 from Domain B is contained
within both A Although experiments
share a common domain
B, they are not related and therefore no combina-
R
Common domain
B is the same
experiment
Common domain B does not
contain the same experiments
and therefore this is not a valid
scenario.
Unrelated:
{
{
Offspring
(Multiple
Parent
experiments
Fig. 5. Experiments can be related, either as a parent
offspring relationship or by identical experiments sharing
common domains. Related experiments generate valid
combinations.
8 Lentz, Manolakos, Czeck and Heller
Insert single stuck-at faults into the network and assign a domain for each multiplicity:
For an event, scheduled for current time T
Evaluate the R experiment and update the new state value, Routput
on the output list for element E.
Locate all triggers present on all input lists and store them on a list called a trigger list.
Begin generation of valid combinations of experiments.
valid scenario must contain a trigger and be combinable.)
Take an experiment from one input list and determine which other experiments from
different inputs of E may be combined by using the rules of combinability.
If the experiments are related as:
(parent AND offspring)
(related by a common experiment in the same domain)
(the experiments do not share any common domains)
then
If any experiment in the scenario is present on the trigger list
then the scenario is valid and can be evaluated.
Build the current list L C to simulate the scenario.
Evaluate the experiment by calling its evaluation function.
Begin Parent Checking to see if the scenario can be compressed
to a parent experiment present on the output.
If Ck
where k is the experiment identifier for Ck
and no other parent experiments are present on the output
with a state value matching Ck (V 0 ).
then diverge Ck (V 0 ) as an offspring experiment.
End Parent Checking
Continue generation of combinations until no more valid combinations of experiments are found.
End generation of valid combinations of experiments.
Fig. 6. High Level Algorithm For MDCS
tion of these experiments will be simulated. Notice
that experiments such as A 2 and B 1 could
combine since they do not share any common do-
main. A high level algorithm is presented here to
summarize the major portions of the algorithm.
4.2. High Level Description of the Multiple Domain
Algorithm
The high level algorithm described in Figure 6 is
similar to the MLT algorithm in the manner that
a simulation scenario is built via a Current List,
evaluated and compared to a reference experi-
ment. In MLT, the simulation case was created by
selecting all identical experiments present on the
inputs and outputs of a gate. Experiments were
located through their unique concurrent identifiers
(CID) and state values were retrieved. On
inputs and outputs where no matching CID could
be found, the Reference experiment state value
was used. In MDCS, the simulation cases are created
by generating valid combinations of experi-
ments, opposed to using only a single experiment
and the reference. This is the most complex aspect
of building a multiple domain environment.
There are many checks for compatibility of experiments
that utilizes the domain information stored
within the C k experiment.
Recall that in Concurrent Fault Simulation, the
reference was the only parent experiment that
all other experiments were compared against. In
Multiple Experiment Environments for Testing 9
MDCS, many parent experiments have been de-
fined. The reference, and many single stuck-at
experiments. Consequently, a parent experiment
will sometimes be referred to as a dynamic
reference experiment, since when present, it will
be used in lieu of the reference for comparisons
against any offspring being processed.
As an element evaluation begins, the Current
periments from the lists of element E i . In order
periment must be present in L c , i.e., there must
exist an event for the experiment at the current
time. MDCS filters out any experiment not triggered
for the current event time T . An additional
list of "triggers" is maintained for this specific pur-
pose. Using this Trigger information, it is possible
to drastically reduce the number of combinations
that MDCS must explicitly simulate.
In

Figure

7, two domains are defined, each containing
a reference value and two stuck-at values.
Faults in domains A and B are injected at I 1 and
I 2 respectively. There is a potential of nine possible
combinations of experiments, three experiments
on I 1 versus the three experiments on I 2 .
As will be shown, only three out of the nine cases
must be evaluated using the MDCS algorithm.
According to the algorithm, the reference experiment
is the first to be processed, but notice it
is not triggered. Therefore, the activity is due
to a triggered faulty experiment. When the triggered
experiment A 2 is encountered, it must be
processed independently (as a SSF) and then all
the combinable experiments present on the other
input must be processed against A 2 . All the sce-
R (0)
R (0)
(1)
A 3 (1)
R (0)
I 1
I 2
Satisfy rules of
combinability ?
(1)
Propagate as an
offspring
(1)
A 3A (1)A (1)
R (0)
yes: evaluate no: invalid yes: evaluate
Experiment
Scenario
Propagate ?
Fig. 7. Applying MDCS to Multiple Stuck-at Fault Sim-
ulation
narios of A 2 (1) versus experiments from L 2 are
depicted in the table of Figure 7. Out of these
three cases, two of them must be evaluated because
they meet the rules of combinability. The
result from these evaluations will be propagated to
the output only if the experiment produces a different
state value from any parent present on the
output list L 3 . Since L 3 only contains one experiment
(the reference experiment), the results from
all evaluated scenarios are compared to it. Row
L 3 in the table of Figure 7 shows the results of
the evaluations. Case 1 is performing traditional
CS (i.e., simulating the SSF A 2 (stuck \Gamma at \Gamma 1) on
input I 1 . This case is compressed since it matches
the reference state on the output. Only case 3
produces a state value not equal to the reference
on the output, R(0), therefore this experiment is
propagated to the output of the element. Note
that the diverged experiment A 2 B 1 (1) displays a
new behavior that would not have been seen by
simulating each parent experiment A 2 (1) or B 1 (1)
independently. Therefore, an offspring experiment
has been spawned.
The previous example was shown to provide insight
into the method for generating scenarios.
The output contained only a reference experiment
and there were no other experiments to compare
the newly evaluated scenarios against. Let
us now demonstrate the MDCS algorithm when
other parent experiments besides the reference are
present at the output. Figure 8 shows the presence
of an experiment (shown in gray
that arrived on the output before the current simulation
time. If the gate were to be evaluated,
all the same scenarios as shown in the table of

Figure

7 would still be generated. The difference
however, would be that case 3 would see B 1 (1)
on L 3 as a parent and check its state value for
comparison. Upon verifying that the interaction
on the output, no propagation
would occur. This is an example of what
is called parent checking, where experiments are
compressed to dynamic parents opposed to being
propagated.
5. Circuit Example
Consider Figure 9 in order to demonstrate the
storage savings in the MDCS algorithm. This is
Czeck and Heller
R (0)
R (0)
(1)
A 3 (1)
R (0)
I 1
I
(1)
Fig. 8. Using Parent checking on the output before propagating
any offspring. Experiment B 1
arrived previous to
the current event.
the same circuit as given in Figure 4, only now
showing all the parent experiments that MDCS
would store. There are three domains, A; B; C in

Figure

9. Each domain is defined as containing
a single stuck-at-1 fault source for each primary
input of an element. In this case, domain A, B
and C contain values for input I 1 of gate E 1 , I 2 of
I 1 of E 2 respectively. Domain definition is
very flexible. There are no restrictions on the assignment
of domains to signal lines. For instance,
all three domains could have contained faults to
be inserted on the same input but this would not
have been a very interesting case. Using a reference
state value of zero, the network is initialized
with four parent experiments at E 1 and E 2 . These
are the reference R and the three single stuck-at-1
faults A 1 (1),B 1 (1) and C 1 (1).

Table

1. Combinations generated for using MDCS include
the two SSF and a MSAF Experiment A 1 B 1 .
Case 1 Case 2 Case3 Case 4
I 1 R(0) A 1
(1)
I 2 R(0)
evaluated
(1)
All experiments for E 1 are triggered. The resulting
combinations are shown in Table 1 along02
=Triggered Experiment
R
R
R
R
R
R (1) C (1)Fig. 9. Simulating a Digital Logic Network with three
domains.
with the contributing parent experiments from
each input that produced them. After the signals
have propagated to their respective
outputs, only the reference and those experiments
that have spawned a new behavior have
been propagated. The creation of all MSAFs in
MDCS are reported along with detection statistics

6. Results
In order to demonstrate the potential of MDCS
for practical applications, a proof-of-concept prototype
was developed. We used the CREATOR
Concurrent Fault Simulator [6] as a reference and
compared it to our MDCS version for correctness
and for measuring overhead associated with our
algorithms. These test cases are based on the
ISCAS benchmark circuits [3, 4] widely used for
evaluating fault simulation techniques.
Experimental results are presented for fault
(single stuck-at and two-way stuck-at) simulations
that were performed using the MDCS scheme. Although
MDCS is portable to many platforms, the
results presented here were gathered using a VAX
8800 uni-processor machine. The waveforms (test
input patterns) were generated using CONTEST
[13].

Table

2 contains the information necessary to
describe the benchmark circuits used. The circuit
number, ISCAS name, number of gates, primary
inputs, primary outputs, number of flip-
flops, number of single stuck-at faults inserted,
and number of input patterns used are provided.
The circuits will be referenced by their number
from the first column of Table 2 for all graphs.
The first letter of the circuit indicates whether it
is sequential (S) or combinational (C). The combinational
circuits are taken from the ISCAS85
[3] benchmark set and the sequential circuits were
taken from the ISCAS89 [4] set.
We simulated all the original set of single stuck-at
faults plus the combination of potential two-way
stuck-at faults. We say "potential" two-way
faults because MDCS is not performing exhaustive
experimentation, but rather, investigating the
whole space for interactions, given a set of input
patterns. The results clearly demonstrate the experiment
compression feature of MDCS. Not only
Multiple Experiment Environments for Testing 11

Table

2. ISCAS benchmark circuit descriptions, ordered in ascending number of faults inserted.
Number Circuit # of Gates PInputs POutputs Flops Faults Patterns
9 S526 214 3 6 21 599 1496
14 C6288 2417
are the original single stuck-ats simulated as independent
experiments, but if two or more different
experiments arrive on different inputs to a gate,
then they are tested for interactions. An interaction
is counted any time two experiment scenarios
are tested for new behavior. This number can include
redundant counts for the same combinations
of faults due to feedback paths or the application
of a new waveform pattern. In contrast, an offspring
experiment is one where an interaction creates
a new behavior that must be propagated.
Given this information, we wanted to find out
the overhead in going from single to a multiplicity
of 2 faults (and from one domain to two). The
CPU times are plotted in Figure 10. Th times
show that adding the potential of experiment interaction
is fairly cost effective. We know from
the basic CS algorithm that many single stuck-at
faults are compressed using the reference. The
same phenomenon exhibited by MDCS indicates
that the other parent experiments must be playing
an important role in curtailing the total number
of experiments simulated. Otherwise, the complexity
in the algorithm would be overwhelming as
more experiments become explicit. Circuit C6288
had the largest overhead due to the fact that our
code was optimized for sequential circuits. Newer
revisions of the algorithm will address this problem

The upper bound of all possible two-way experiment
scenarios that could arise in an exhaustive
simulation was computed by:
This value is shown for each benchmark in the
column called "Total # of Possible MSAF" in Table
3. The column titled "Total # of SSF+MSAF
experiments possible" is the total number of scenarios
that could possibly arise. This includes the
original single stuck-at faults as well as all possible
double fault experiments. This was computed
by:
, where N is the number of single
stuck-at fault sources.
ng l e
ng l e+MSAF
CPU
Circuit Number
Fig. 10. CPU time for MDCS single stuck-at simulations
and single plus double MSAF.
12 Lentz, Manolakos, Czeck and Heller

Table

3. Two Domain Simulation (Single and Double) fault simulation performance.
Number Circuit # of SSF Total # Total # CPU time (sec) Storage
Name inserted of Possible SSF + MSAF SSF SSF+MSAF in Kbytes
MSAF experiments
possible
Ring 6 15 21 0.10
9 S526 599 179101 179700 414.63 695.93 103
14 C6288 7744 29980896 29988640 783.34 2145.32 728

Table

4. Interactions eliminated due to parent checking.
No. Circuit Total Poss. # of Interactions Offspring # of Interactions
Name MSAF that Occurred Propagated Eliminated
Ring
9 S526 179101 1202 53 1149
14 C6288 29980896 52351 972 51379
Unlike other techniques [10], MDCS is not
physically inserting all possible fault scenarios or
adding additional circuitry. Rather, MDCS allows
sets of single stuck-ats to be inserted and then uses
test patterns as the stimulus for MSAFs to manifest
themselves as interacting experiments. The
original purpose for MDCS was not to be used
exclusively as a single stuck-at fault simulator,
but rather as a test environment for efficiently
creating experiment scenarios and observing experiment
behavior. However, it is still interesting
to compare the overhead of the algorithm to
other simulators. Comparing the MDCS underlying
concurrent implementation (single stuck-at
faults) to the PROOFS simulator[11], the MDCS
Multiple Experiment Environments for Testing 13
CPU times for the benchmarks were much better
than one would have expected from a concurrent
simulation algorithm. This comparison is based
on the 32 bit word data as reported in[11]. Although
PROOFS demonstrates a massive speed-up
over a version of concurrent simulation, the
MDCS version of CS uses the MLT for element
processing thus closing the gap between the two
algorithms. Most commercial concurrent simulators
use a two-list traversal[15] mechanism for implementing
their concurrent fault simulation and
this certainly would impede the speed as reported
in PROOFS [11].
One way to measure the performance of MDCS
is to investigate the number of experiment interactions
that occurred and whether or not they generated
offspring.

Table

4 shows the statistics gathered on interactions
and their relation to the number of offspring
experiments. The occurrence of interactions of
two or more experiments have an overhead associated
with them. For every interaction, a test
must be done to determine whether a parent experiment
(the reference or other parent) already
exists on the output and exhibits the same be-
havior. behaving experiments are com-
pressed, while different behaviors must be propagated
and therefore become offspring. Offspring
experiments are a measure of how many new scenarios
were propagated. MDCS results show that
despite the fact that the number of interacting scenarios
can be large, MDCS can eliminate most of
them through parent checking. The column of table
4 titled, "# of Interactions that Occurred", is
a count of the number of times two or more experiments
were tested for cumulative new behaviors.
The column called "Offspring Propagated" indicates
how many of the interactions actually generated
new offspring experiments. Finally, the difference
between "# of Interactions that Occurred"
and and "Offspring Propagated", is shown in the
column called "# number of Interactions Elimi-
nated". This column reflects the number of those
interacting scenarios that were converged (com-
pressed) due to parent checking.

Figure

11 shows that parent checking is very ef-
fective. Each column of the graph represents the
percentage of interactions that were eliminated
for each circuit simulated. This not only proves
that MDCS curtails the number of experiments
spawned, but also that the experiment compression
factor is extremely high. This also has a
tremendous impact on storage as shown in the last
column of Table 3.
6.1. Extension to Larger Domains
Digital logic simulation is an excellent test-bed for
MDCS because there is a limited number of logic
state values an output can assume. As the number
of domains was increased to three and then
four, it was found that more interactions could be
represented by a parent experiment and therefore
compressed. CPU time for larger multiplicity of
faults grew slightly and remained relatively constant
for multiplicities after four.
6.2. Future Directions
Since it was demonstrated that MDCS can efficiently
create scenarios that can interact, an area
of further research interest involves utilizing the
function list[2, 7] for creating multiple instances of
a model in a single simulation. In fault simulators
such as MDCS and CREATOR[6], the function
list stores the various Activity Functions that allow
a model to assume different behaviors during
the simulation. For instance, an AND gate could
be forced to act like an OR gate at various times
to model some intermittent fault scenario. Including
this functionality in the Multiple Domain algorithm
will provide the simulator with the ability
to create scenarios from combinations of activity
functions dynamically and efficiently. In Figure
12, a two input AND gate is shown.
The Reference Experiment on the function
list[2] contains the activity function for the fault-free
experiment, denoted by R 14 . Faulty behaviors
are inserted as single stuck-ats when faults
are loaded into the simulator. The MDCS algorithm
will create and simulate all the single
stuck-at fault experiments by creating current
lists for simulating the
reference experiment, L
for simulating input I 1 stuck-at 1, and L
The
presence of an activity function on the function
list causes the model to be evaluated by substi-
14 Lentz, Manolakos, Czeck and Heller
INTERACTIONS
ELIMINATED
Fig. 11. Demonstrating the efficiency of experiment com-
pression. Percentage of experiments that were eliminated
from the simulation.
tuting the stuck-at value on the appropriate input
or output list. For example, activity function F 1
will cause the AND gate to be evaluated with input
I inputs use the reference
state values.
The Multiple Domain algorithm traverses the
function list to dynamically create fault scenarios
of any multiplicity. In the example of Figure 12,
the behaviors of activity functions F 1 and F 2 will
be tested for interaction against any fault experiments
present on the input lists. If a new behavior
is detected that is different from the contributing
activity functions, then a new activity function is
created and an offspring experiment is spawned.
Activity functions in the MDCS show much
promise for scenario experimentation. The activity
functions need not be limited to fault behaviors
and may possess more complex model functions
such as those used in scenario control in virtual
environments[8].R 11
R 12
I
Function List
AND(I I )
activity
Fig. 12. The Function list containing activity functions
which allows a model to assume multiple behaviors.
7. Limitations
By utilizing dynamic reference (parent) exper-
iments, scenarios are compressed into implicit
classes, thus reducing the number of explicit experiments
that must be stored and propagated.
All these features not currently available in other
discrete-event simulators can be implemented in
a CPU and storage efficient manner. However,
one area of concern is the difficulty in establishing
appropriate reference experiments beyond the
four state simulator, in an application beyond digital
logic simulation, such as software programs.
In fault simulation, since there are only 4 possible
outcomes (0,1,Z,X), offspring experiments are
curtailed because their state behaviors can only
assume one of these four values. In considering
more complex models, where perhaps the model
can be an equation, the number of valid output
states could be enormous. The algorithm will
have to develop a method of choosing appropriate
parent experiments to serve as the most appropriate
behavior for comparison. One method
under investigation is to use valid ranges for specific
variables. These are either provided by the
user or derived from the model being simulated.
Experiments that produce behavior states within
the range are compressed while those outside the
boundaries are propagated.
8. Conclusions
This paper introduced a framework intended to
attack large simulation problems where the number
of experiments can approach exhaustive test-
ing. By using a Multiple Domain Concurrent Simulation
algorithm, a methodology was presented
for experimentation without explicit representation
of all scenarios. In addition, dynamic interactions
are allowed to create new cumulative behaviors
(offspring), which can be observed through-out
the simulation. Any offspring experiments
that were spawned during a simulation were detected
using input patterns generated from CON-
TEST[13] and GENTEST.
An advantage of using MDCS is the flexibility
and ease of defining experiments. No modifications
need to be made to the network and no scenarios
(multiple stuck-at faults) need be inserted.
Multiple Experiment Environments for Testing 15
Instead, domains are used to insert sets of single
stuck-at faults and only those faults that create
new behaviors are ever propagated. The algorithms
developed for this framework where verified
by performing Multiple Stuck-at Fault Simulation
for digital logic circuits. This application
was chosen because it demonstrates all the
features in a MDCS, namely experiment interac-
tion, compression, and spawning of new behaviors.
Benchmark testing and evaluation using the ISCAS
benchmark circuits [3, 4] were performed for
multiple stuck-at fault simulations. Our results
indicate that MDCS does not create a combinatorial
explosion of experiment combinations that
need to be stored and simulated. This was evident
through the number of experiments converged to
a parent.
Another interesting feature that is worth noting
is the ability to compare the activity of one
pattern against another. For instance, because
MDCS generates interactions based on pattern
stimulus, the more interactions a pattern created
seemed to indicate the robustness in exercising the
circuit. Signatures of specific patterns could easily
be determined and compared for redundancy
in test pattern development.
Future directions under investigation include
using behavioral models, VHDL or other types
of models such as HCSM[8] or even BDDs[16] in
the Multiple Domain Environment, such that dynamic
interactions will be possible within these
models. The current MDCS implementation can
use VHDL models, but the experiment interaction
feature inherent in our framework has not yet been
implemented for VHDL models. Using a function
list in our framework also shows much promise in
simulation applications where orchestrating scenarios
is important. It allows many different behaviors
to be captured in a single model entity
and through the MDCS list traversal mechanism,
we can compress and propagate behaviors only of
interest.
Finally, this methodology shows promise for
evaluating the effectiveness of patterns. Coverage
and detection of different pattern sets can be
performed and help derive new patterns that will
be more robust in detecting complex interacting
behaviors.

Acknowledgements

The Authors would like to thank Dr. Pierluca
Montesorro for his continued support on the CREATOR
simulator, Dr. Fabio Somenzi and Dr.
Vishwani Agrawal for their help with benchmarking
and Dr.Chung Len Lee for his valuable suggestions

Notes
1. Note: This list is also known as the obligation list.



--R

"The Concurrent Simulation of Nearly Identical Digital Networks"
"MOZART: A Concurrent Multi-Level Simulator"
"A Neutral Netlist of 10.Combinational Benchmark Circuits and a Target Translator in FORTRAN"
"Combina- tional Profiles of Sequential Benchmarks for Sequential Test Generation"
"Switch-Level Concurrent Fault Simulation based on a General Purpose List Traversal Mechanism"
"Creator: General and Efficient Multilevel Concurrent Fault Simulation"
"Creator: New Advanced Concepts in Concurrent Simulation"
"HCSM: A framework for Behavior and Scenario Control in Virtual Environments"
"Multiple Domain Concurrent Simulation of Interacting Experiments and Its application to Multiple Stuck-at Fault Simulation"
"Multiple-fault Simulation and Coverage of Deterministic Single-Fault Test
"PROOFS: A Fast, Memory Efficient Sequential Circuit Fault Sim- 16.Lentz, Manolakos, Czeck and Heller ulator"
"The Comparative and Concurrent Simulation of Discrete-Event Experiments"
"A Directed Search Method for Test Generation Using a Concurrent Simulator"
"Sequential circuit fault simulation by fault information tracing algorithm: fit"
"An Efficient Method of Fault Simulation for Digital Circuits Modeled from Boolean Gates and Memories"
"Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams"
He earned his M.
--TR

--CTR
Karen Panetta Lentz , Jamie Heller , Pier Luca Montessoro, System Verification Using Multilevel Concurrent Simulation, IEEE Micro, v.19 n.1, p.60-67, January 1999
Zainalabedin Navabi , Shahrzad Mirkhani , Meisam Lavasani , Fabrizio Lombardi, Using RT Level Component Descriptions for Single Stuck-at Hierarchical Fault Simulation, Journal of Electronic Testing: Theory and Applications, v.20 n.6, p.575-589, December  2004
Maria Hybinette , Richard M. Fujimoto, Cloning parallel simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.11 n.4, p.378-407, October 2001
Maria Hybinette, Just-in-time cloning, Proceedings of the eighteenth workshop on Parallel and distributed simulation, May 16-19, 2004, Kufstein, Austria
scenario;interactive experimentation;concurrent fault simulation;multiple stuck-at