Asynchronous parallel algorithms for test set partitioned fault simulation.
We propose two new asynchronous parallel algorithms for test set partitioned fault simulation. The algorithms are based on a new two-stage approach to parallelizing fault simulation for sequential VLSI circuits in which the test set is partitioned among the available processors. These algorithms provide the same result as the previous synchronous two stage approach. However, due to the dynamic characteristics of these algorithms and due to the fact that there is very minimal redundant work, they run faster than the previous synchronous approach. A theoretical analysis comparing the various algorithms is also given to provide an insight into these algorithms. The implementations were done in MPI and are therefore portable to many parallel platforms. Results are shown for a shared memory multiprocessor.
Introduction
Fault simulation is an important step in the electronic design
process and is used to identify faults that cause erroneous
responses at the outputs of a circuit for a given test set. The
objective of a fault simulation algorithm is to find the fraction
of total faults in a sequential circuit that is detected by a given
set of input vectors (also referred to as fault coverage).
In its simplest form, a fault is injected into a logic circuit by
setting a line or a gate to a faulty value (1 or 0), and then the effects
of the fault are simulated using zero-delay logic simula-
tion. Most fault simulation algorithms are typically of O(n 2 )
time complexity, where n is the number of lines in the circuit.
Studies have shown that there is little hope of finding a linear-time
fault simulation algorithm [1].
In a typical fault simulator, the good circuit (fault-free cir-
cuit) and the faulty circuits are simulated for each test vec-
tor. If the output responses of a faulty circuit differ from those
of the good circuit, then the corresponding fault is detected,
and the fault can be dropped from the fault list, speeding up
simulation of subsequent test vectors. A fault simulator can
This research was supported in part by the Semiconductor Research Corporation
under Contract SRC 95-DP-109 and the Advanced Research Projects
Agency under contract DAA-H04-94-G-0273 and DABT63-95-C-0069 administered
by the Army Research Office.
be run in stand-alone mode to grade an existing test set, or it
can be interfaced with a test generator to reduce the number
of faults that must be explicitly targeted by the test generator.
In a random pattern environment, the fault simulator helps in
evaluating the fault coverage of a set of random patterns. In
either of the two environments, fault simulation can consume
a significant amount of time, especially in random pattern test-
ing, for which millions of vectors may have to be simulated.
Thus, parallel processing can be used to reduce the fault simulation
time significantly. We propose in this paper two scalable
asynchronous parallel fault simulation algorithms with
the test vector set partitioned across processors. This paper is
organized as follows. In Section 2, we describe the various
existing approaches to parallel fault simulation and we motivate
the need for a test set partitioned approach to parallel fault
simulation. In Section 3, we discuss our approach to test sequence
partitioning. In Section 4, we present the various algorithms
that have been implemented including the two proposed
asynchronous algorithms. A theoretical analysis of the
sequential and parallel algorithms proposed is given in Section
5 to provide a deeper insight into the algorithms. The results
are presented in Section 6, and all algorithms are compared.
Section 7 is the conclusion.
Parallel Fault Simulation
Due to the long execution times for large circuits, several
algorithms have been proposed for parallelizing sequential
circuit fault simulation [2]. A circuit partitioning approach to
parallel sequential circuit fault simulation is described in [3].
The algorithm was implemented on a shared-memory multi-
processor. The circuit is partitioned among the processors,
and since the circuit is evaluated level-by-level with barrier
synchronization at each level, the gates at each level should be
evenly distributed among the processors to balance the work-
loads. An average speedup of 2.16 was obtained for 8 proces-
sors, and the speedup for the ISCAS89 circuit s5378 was 3.29.
This approach is most suitable for a shared-memory architecture
for circuits with many levels of logic.
Algorithmic partitioning was proposed for concurrent fault
simulation in [4][5]. A pipelined algorithm was developed,
and specific functions were assigned to each processor. An
estimated speedup of 4 to 5 was reported for 14 processors,
based on software emulation of a message-passing multicomputer
[5]. The limitation of this approach is that it cannot take
advantage of a larger number of processors.
Fault partitioning is a more straightforward approach to
parallelizing fault simulation. With this approach [6][7], the
fault list is statically partitioned among all processors, and
each processor must simulate the good circuit and the faulty
circuits in its partition. Good circuit simulation on more than
one processor is obviously redundant computation. Alterna-
tively, if a shared-memory multiprocessor is used, the good
circuit may be simulated by just one processor, but the remaining
processors will lie idle while this processing is performed,
at least for the first time frame. Fault partitioning may also
be performed dynamically during fault simulation to even out
the workloads of the processors, at the expense of extra inter-processor
communication [6]. Speedups in the range 2.4-3.8
were obtained for static fault partitioning over 8 processors
for the larger ISCAS89 circuits having reasonably high fault
coverages (e.g., s5378 improvements
were obtained for these circuits with dynamic fault partitioning
due to the overheads of load redistribution [6]. However,
in both the static and dynamic fault partitioning approaches,
the shortest execution time will be bounded by the time to perform
good circuit logic simulation on a single processor.
One observation that can be made about the fault partitioning
experiments is that larger speedups are obtained for circuits
having lower fault coverages [6][7]. These results highlight
the fact that the potential speedup drops as the number of
faults simulated drops, since the good circuit evaluation takes
up a larger fraction of the computation time. The good circuit
evaluation is not parallelized in the fault partitioning ap-
proach, and therefore, speedups are limited. For example, if
good circuit logic simulation takes about 20 percent of the total
fault simulation time on a single processor, then by Am-
dahl's law, one cannot expect a speedup of more than 5 on any
number of processors.
Parallelization of good circuit logic simulation, or simply
logic simulation, is therefore very important and it is known to
be a difficult problem. Most implementations have not shown
an appreciable speedup. Parallelizing logic simulation based
on partitioning the circuit has been suggested but has not been
successful due to the high level of communication required between
parallel processors.
Recently, a new algorithm was proposed, where the test
vector set was partitioned among the processors [8]. We will
call this algorithm, SPITFIRE1. Fault simulation proceeds
in two stages. In the first stage, the fault list is partitioned
among the processors, and each processor performs fault simulation
using the fault list and test vectors in its partition. In
the second stage, the undetected fault lists from the first stage
are combined, and each processor simulates all faults in this
list using test vectors in its partition. Obviously, the test set
partitioning strategy provides a more scalable implementa-
tion, since the good circuit logic simulation is also distributed
over the processors. Test set partitioning is also used in the
parallel fault simulator Zamlog [9], but Zamlog assumes that
independent test sequences are provided which form the par-
tition. If only one test sequence is given, Zamlog does not
partition it. If, for example, only 4 independent sequences
are given, it cannot use more that 4 processors. Our work
does not make any assumption on the independence of test sequences
and hence is scalable to any number of processors.
It was shown in [8] [10] that the synchronous two-stage al-
gorithm, SPITFIRE1, performs better than fault partitioned
parallel approaches. Other synchronous algorithms, SPIT-
FIRE2 and SPITFIRE3, which are extensions of the SPIT-
FIRE1 algorithm, were presented in [10]. SPITFIRE3, in
particular, is a synchronous pipelined approach which helps
in overcoming any pessimism that may exist in a single or
two stage approach. We propose in this paper, two new asynchronous
algorithms, based on the test set partitioning strategy
for parallel fault simulation. We will demonstrate that
the asynchronous algorithms perform better than their synchronous
counterparts and shall provide reasons for the same.
The first algorithm, SPITFIRE4, is a two stage algorithm, and
it is a modification of the SPITFIRE1 algorithm described
above. It leaves the first stage unchanged, but the second stage
is implemented with asynchronous communication between
processors. The second algorithm, SPITFIRE5, obviates the
need for two stages. The entire parallel fault simulation strategy
is accomplished in one stage with asynchronous communication
between processors.
3 Test Sequence Partitioning
Parallel fault simulation through test sequence partitioning
is illustrated in Figure 1. We use the terms test set and
test sequence interchangeably here, and both are assumed to
be an ordered set of test vectors. The test set is partitioned
Example: A Test Sequence of 5n vectors on 5 Processors
Test Sequence
Processors
3n

Figure

1. Test Sequence Partitioning
among the available processors, and each processor performs
the good and faulty circuit simulations for vectors in its partition
only, starting from an all-unknown (X) state. Of course,
the state would not really be unknown for segments other than
the first if we did not partition the vectors. Since the unknown
state is a superset of the known state, the simulation will be
correct but may have more X values at the outputs than the serial
simulation. This is considered pessimistic simulation in
the sense that the parallel implementation produces an X at
some outputs which in fact are known 0 or 1. From a pure
logic simulation perspective, this pessimism may or may not
be acceptable. However, in the context of fault simulation,
the effect of the unknown values is that a few faults which are
detected in the serial simulation are not detected in the parallel
simulation. Rather than accept this small degree of pes-
simism, the test set partioning algorithm tries to correct it as
much as possible.
To compute the starting state for each test segment, a few
vectors are prepended to the segment from the preceding seg-
ment. This process creates an overlap of vectors between successive
segments, as shown in Figure 1. Our hypothesis is that
a few vectors can act as initializing vectors to bring the machine
to a state very close to the correct state, if not exactly the
same state. Even if the computed state is not close to the actual
state, it still has far fewer unknown values than exist when
starting from an all-unknown state. Results in [8] showed that
this approach indeed reduces the pessimism in the number of
fault detections. The number of initializing vectors required
depends on the circuit and how easy it is to initialize. If the
overlap is larger than necessary, redundant computations will
be performed in adjacent processors, and efficiency will be
lost. However, if the overlap is too small, some faults that are
detected by the test set may not be identified, and thus the fault
coverage reported may be overly pessimistic.
4 Parallel Test Partitioned Algorithms
We now describe four different algorithms for test set partitioned
parallel fault simulation. The first two algorithms are
parallel single-stage and two-stage synchronous approaches
which have been proposed earlier[8][10]. The third and
fourth algorithms are parallel two-stage and single-stage asynchronous
approaches.
4.1 SPITFIRE0: Single Stage Synchronous Algorith

In this approach, the test set is partitioned across the processors
as described in the previous section. This algorithm is
presented as a base of reference for the various test set partitioning
approaches to be described later. The entire fault list is
allocated to each processor. Thus, each processor targets the
entire list of faults using a subset of the test vectors. Each processor
proceeds independently and drops the faults that it can
detect. The results are merged in the end.
4.2 SPITFIRE1: Synchronous Two Stage Algorithm
The simple algorithm described above is somewhat inefficient
in that many faults are very testable and are detected by
most if not all of the test segments. Simulating these faults on
all processors is a waste of time. Therefore, one can filter out
these easy-to-detect faults in an initial stage in which both the
set and the test set are partitioned among the processors.
This results in a two stage algorithm. In the first stage, each
processor targets a subset of the faults using a subset of the
test vectors, as illustrated in Figure 2. A large fraction of the
F
F
F
F
F
5224Partitioning in Stage 1
U
Partitioning in Stage 2
U
U
U
U
Figure

2. Partitioning in SPITFIRE1
detected faults are identified in this initial stage, and only the
remaining faults have to be simulated by all processors in the
second stage. This algorithm was proposed in [8]. The overall
algorithm is outlined below.
1. Partition test set T among p processors:
g.
2. Partition fault list F among p processors:
g.
3. Each processor P i performs the first stage of fault simulation
by applying T i to F i . Let the list of detected faults
and undetected faults in processor P i after fault simulation
be C i and U i respectively.
4. Each processor P i sends the detected fault list C i to processor
5. Processor P 1 combines the detected fault lists from
other processors by computing
now broadcasts the total detected fault list
C to all other processors.
7. Each processor P i finds the list of faults it needs to target
in the second stage G
8. Reset the circuit.
9. Each processor P i performs the second stage of fault
simulation by applying test segment T i to fault list G i .
10. Each processor P i sends the detected fault list D i to processor
11. Processor P 1 combines the detected fault lists from
other processors by computing
. The result
after parallel fault simulation is the list of detected
faults C
S D, and it is now available in processor P 1 .
Note that G
equivalent expression
for G i . The reason that a second stage is necessary
is because every test vector must eventually target every undetected
fault if it has not already been detected on some other
processor. Thus, the initial fault partitioning phase is used to
reduce redundant work that may arise in detecting easy-to-
detect faults. It can be observed though that one has to perform
two stages of good circuit simulation with the test segment
on any processor. However, the first stage eliminates
a lot of redundant work that might have been otherwise per-
formed. Hence, the two-stage approach is preferred. The test
set partitioning approach for parallel fault simulation is subject
to inaccuracies in the fault coverages reported only when
the circuit cannot be initialized quickly from an unknown state
at the beginning of each test segment. This problem can be
avoided if the test set is partitioned such that each segment
starts with an initialization sequence.
The definitive redundant computation in the above approach
is the overlap of test segments for good circuit simu-
lation. However, if the overlap is small compared to the size
of the test segment assigned to a processor, then this redundant
computation will be negligible. Another source of redundant
computation is in the second stage when each processor
has to target the entire list of faults that remains (excluding the
faults that were left undetected in that processor). In this situ-
ation, when one of the processors detects a fault, it may drop
the fault from its fault list, but the other processors may continue
targeting the fault until they detect the fault or until they
complete the simulation (i.e., until the second stage of fault
simulation ends). This redundantcomputationoverheadcould
be reduced by broadcasting the fault identifier, corresponding
to a fault, to other processors as soon as the fault is detected.
However, the savings in computation might be offset by the
overhead in communication costs.
4.3 SPITFIRE4: A Two Stage Asynchronous Algorith

We will now describe an asynchronousversion of the Algorithm
SPITFIRE1. Consider the second stage of fault simulation
in Algorithm SPITFIRE1. All processors have to work
on almost the same list of undetected faults that was available
at the end of the first stage (except faults that it could not detect
in Stage 1). It would therefore be advantageous for each
processor to periodically communicate to all other processors
a list of any faults that it detects. Thus, each processor asynchronously
sends a list of new detected faults to all other processors
provided that it has detected at least MinFaultLimit
new faults. Each processor periodically probes for messages
from other processors and drops any faults that may be received
through messages. This helps in reducing the load on
a processor if it has not detected these faults yet. Thus, by
allowing each processor to asynchronously communicate detected
faults to all other processors, we dynamically reduce the
load on each processor.
It should be observed that in the first stage of Algorithm
SPITFIRE1, all processors are working on different sets of
faults. Hence, there is no need to communicate detected faults
during Stage 1, since this will not have any effect on the work-load
on each processor. It would make sense therefore to communicate
all detected faults only at the end of Stage 1. The
asynchronous algorithm used for fault simulation in Stage 2
by any processor P i is outlined below.
For each vector k in the test set T i
FaultSimulate vector k
(NumberOfNewFaultsDetected ? MinFaultLimit) then
Send the list of newly detected faults to all
Processors using a buffered asynchronous send
while (CheckForAnyMessages())
Receive new message using a blocking receive
Drop newly received faults (if not dropped earlier)
while
end for
The routine CheckForAnyMessages() is a non-blocking
probe which returns a 1 only if there is a message pending to
be received.
4.4 SPITFIRE5: A Single Stage Asynchronous Algorith

It is possible to employ the same asynchronous communication
strategy used in the algorithm SPITFIRE4 for the algorithm
SPITFIRE0. In the latter algorithm, all processors start
with the same list of undetected faults, which is the entire list
of faults F . Only faults which each processor may detect get
dropped, and each processor continues to work on a large set
of undetected faults. Once again, it would make sense for each
processor to communicate detected faults periodically to other
processors provided that it has detected at least MinFaultLimit
new faults.
The value of MinFaultLimit is circuit dependent. It also depends
on the parallel platform that may be used for parallel
fault simulation. For a very small circuit with mostly easy to
detect faults, it may not make sense to set MinFaultLimit too
small, as this may result in too many messages being commu-
nicated. On the other hand, if the circuit is reasonably large,
or if faults are hard to detect, the granularity of computation
between two successive communication steps will be large.
Therefore, it may make sense to have a small value of Min-
FaultLimit. Similarly, it may be more expensive to communicate
often on a distributed parallel platform such as a network
of workstations. However, this factor may not matter as much
on a shared memory machine. Our results were obtained on a
shared memory multiprocessor where the value of MinFault-
Limit was empirically chosen to be 5 as we will show. This
means that whenever any processor detects at least 5 faults, it
will communicate the new faults detected over to other processors
to possibly reduce the load on other processors that may
still be working on these faults.
It is therefore important to ensure that the computation to
communication ratio be kept high and hence depending on
the parallel platform used, one needs to arrive at a compromise
at the frequency at which faults are communicated between
processors. One may also use the number of vectors
in the test set that have been simulated, say MinVectorLimit,
as a control parameter to regulate the frequency of synchro-
nization. This may be useful towards the end of fault simulation
when there faults are detected very slowly. One can also
use both parameters, MinFaultLimit and MinVectorLimit, sim-
ulaneously and communicate faults if either control parameter
is exceeded. As long as the granularity of the computation is
large enough compared to the communication costs involved,
one can expect a good performance with an asynchronous ap-
proach. If we assume that communication costs are zero, then
one would ideally communicate faults as soon as they are detected
to other processors. If the frequency of communication
is reduced, then one may have to perform more redundant
computation.
There is a tradeoff between algorithms SPITFIRE4 and
SPITFIRE5. As we can see in SPITFIRE4, we have a completely
communication independent phase in Stage 1 followed
by an asynchronous communication intensive phase. However
in SPITFIRE5, we have only one stage of fault simula-
tion. This means that the good circuit simulation with test set
T i on processor P i needs to be performed only once. Thus, although
we may have continuous communication in algorithm
SPITFIRE5, we may obtain substantial savings by performing
only one stage of fault simulation. We will see in the next
section that this is indeed the case.
The same approach for asynchronous communication that
was discussed in the previous section is used for this algo-
rithm. However, the asynchronous communication is applied
to the first and only stage of fault simulation that is used for
this algorithm.
5 Analysis of Algorithms
A theoretical analysis of the various algorithms is now pre-
sented. We first provide an analysis of serial fault simulation
and then extend the analysis for various test set partitioning
approaches and for a fault partitioning approach.
5.1 Analysis of Sequential Fault Simulation
We first provide an analysis for a uniprocessor and then
proceed to an analysis for a multiprocessor situation.
Let us assume that there are N test vectors in the test set f
g. Usually in fault simulation, many faults are
detected early, and then the remaining faults are detected more
slowly. Let us assume that the fraction of faults detected by
vector k in the test set is given by ffe \Gamma-(k\Gamma1) , i.e. the fraction
of faults detected at each step falls exponentially. (Tradition-
ally one assumes that the fraction of faults left undetected after
the k'th vector has been simulated is given by ff 1 e \Gamma-k [3] [11].
Hence, the fraction of faults detected by vector k is given by
which is of
the form ffe \Gamma-(k\Gamma1) . ) Then the fraction of faults detected at
this stage after (n-1) vectors have been simulated is given by
1\Gammae \Gamma- . Hence, the number of undetected faults
remaining, U(n) when the n'th vector has to be simulated is
given by
the total number of faults in the circuit. Let us assume that
fl is the unit of cost for execution in seconds per gate evalu-
ation. Assume that a fraction ffi of the total number of gates
G in the circuit is being simulated for each fault. Then the
cost for simulating all the faulty circuits left with the n'th vector
is fl ffiGU(n). Assume that a fraction fi of the gates G are
simulated for the good circuit logic simulation for each vector.
(Usually ffi !! fi. This is because, for fault simulation, only
the events that are triggered in the fanout cone starting from
the node where the fault was inserted need to be processed.)
Then the fault simulation cost for simulation of the n'th vector
is given by fl(fiG ffiGU(n)). Thus the total fault simulation
cost on a uniprocessor, T 1 (N; F; G), for simulating N vectors
is given by
Since N is large, we may approximate 1\Gammae \Gamma-N by 1. We then
find that T 1 (N; F;
Neglecting r in relation to N , we obtain
5.2 Analysis of Algorithm SPITFIRE0
In a single stage test set partitioned parallel algorithm, each
processor simulates N
vectors where o is the vector overlap
between processors. Each processor also starts with the
same number of faults F . In a single stage synchronous algo-
rithm, communication occurs only in the end where all processors
exchange all detected faults. This can be neglected
in comparison to the total execution time. Therefore, the total
execution cost T p;sync;1stage (N; F; G; o) can be approximated
as,
G;
The above formula shows that this approach is scalable but
that one has to pay for the redundant computation performed
with the vector overlap factor o.
5.3 Analysis of a Fault Partitioning Algorithm
In a fault partitioning algorithm, each processor simulates
N vectors and targets F
faults. Hence, the execution cost in
this case is of the form
F
This formula demonstrates that the fault partitioned approach
is not scalable since the first term, which corresponds to the
good circuit logic simulation performed, does not scale across
the processors. Eventually, this factor will bound the speedup
as the number of processors is increased.

Table

1. Uniprocessor Execution Times
Pri- Pri- Random Test Set Actual Test
mary mary Size 10000 from an ATPG tool
Inp- Out- Flip Time Faults Test Set Time Faults
Circuit Faults Gates uts puts Flops (secs) Detected Size (secs) Detected

Table

2. Execution Time on 8 processors of SUN-SparcCenter1000E shared memory multiprocessor
Random Test Test
Faults Execution Time (secs) Faults Execution Time (secs)
Circuit Faults Detected SPF0 SPF1 SPF4 SPF5 Detected SPF0 SPF1 SPF4 SPF5
s526 555 52 16.7 10.4 13.3 8.2 445 8.5 5.1 3.0 2.3
div16 2141 1640 19.2 26.0 24.8 13.4 1801 53.7 28.3 21.1 13.2
pcont2 11300 6829 113.8 137.7 140.7 104.4 6837 116.3 110.3 75.5 52.6
piir8 19920 15004 285.8 271.3 265.0 230.9 15069 51.1 48.4 44.3 33.6
5.4 Analysis of Algorithm SPITFIRE5
For a single stage asynchronous algorithm, we may assume
that, due to communication, all processors are aware of all detected
faults before a test vector is input. We assume for the
purposes of analysis that MinF aultLimit = 1. This means
that a processor broadcasts the new faults that it has dropped
every time it detects at least 1 fault. If the faults detected by all
processors at each stage are all different, then the number of
faults detected after (n-1) vectors have been simulated is given
by In this case,
G;
where C p;async;1stage (N; F communication cost
involved. In reality, some faults are multiply detected by
more than one processor, and the factor pff in the above formula
will be smaller. Also, since there is some delay in
each processor obtaining information about faults dropped on
other processors, this factor may be even smaller. Also, if
MinF aultLimit is large, this delay may be even longer, and
the factor pff would have to be scaled down further. A smaller
value of pff indicates a longer execution time. Let us assume
that the communication cost is of the form- 1 +- 2 l where - 1 is
the startup cost in seconds, - 2 is the cost in seconds per computer
word, and l is the length of the message. Since F ffr(1 \Gamma
are detected after the n'th vector has been simulated
by each of the p processors, the total cost of communication
is given by C p;async;1stage (N; F
Note that if MinF aultLimit is large, then the number of
messages is smaller, and the term (- 1 (N=p would be
scaled down. However, the term (- would remain
unchanged, since that is the total amount of data that is
communicated. Clearly, there is a tradeoff involved in increasing
the value of MinF aultLimit.
5.5 Analysis of SPITFIRE1 and SPITFIRE4
It is easy to show, using similar analysis, that the total
execution cost for the two stage algorithms, SPITFIRE1
and SPITFIRE4, can be obtained by replacing F by F ( 1
e \Gamma-( N
by counting the good circuit simulation cost
twice, in the formulas for the execution cost for the algorithms
SPITFIRE0 and SPITFIRE5 respectively. It is apparent that
in the two stage algorithms, we have effectively reduced the
faulty circuit simulation term but could pay a small price in
having to perform two stages of good circuit logic simulation.
In addition, the \Gammapff term helps in reducing the execution time
for the asynchronous two stage algorithm.
We see from the above discussion that the asynchronous algorithms
would possibly have the lowest execution time over

Table

3. Execution Time and Speedups on SUN-SparcCenter1000E with Algorithm SPITFIRE5 on Random
Test
Random Test Set Execution Times(seconds) and Speedups
Uniprocessor 2 Processors 4 Processors 8 Processors
Circuit Time Time Speedup Time Speedup Time Speedup
s526 57.39 28.50 2.01 14.76 3.88 8.25 6.95
mult16 143.3 64.36 2.23 33.21 4.31 20.37 7.03
div16 110.6 48.95 2.25 24.76 4.46 13.38 8.26

Table

4. Execution Time and Speedups on SUN-SparcCenter1000E with Algorithm SPITFIRE5 on ATPG
Test
ATPG Test Set Execution Times(seconds) and Speedups
Uniprocessor 2 Processors 4 Processors 8 Processors
Circuit Time Time Speedup Time Speedup Time Speedup
s526 10.92 5.70 1.91 4.03 2.70 2.26 4.83
pcont2 324.4 168.27 1.93 96.15 3.37 52.56 6.17
piir8 127.4 74.10 1.72 45.1 2.82 33.6 3.79
their synchronous counterparts. There are two factors contributing
to this. The first is the N
term which corresponds
to the partitioning of the test set across processors. The second
is the \Gammapff term corresponding to the fact that a processor
now has information about the faults that the other processors
have dropped due to asynchronous communication.
Between the two asynchronous algorithms, the single stage
asynchronous algorithm may win over the two stage algorithm
simply because only one stage of good circuit logic simulation
is performed in this case. The communication cost factor
will depend on the platform being used and may have a
different impact on different parallel platforms. However, as
long as the overall communication cost is small compared to
the overall execution cost, the single stage asynchronous algorithm
should run faster than all other approaches.
6 Experimental Results
The four algorithms described in the paper were implemented
using the MPI [12] library. The implementation is
portable to any parallel platform which provides support for
the MPI communication library. Results were obtained on a
SUN-SparcCenter 1000E shared memory multiprocessor with
8 processors and 512 MB of memory. Results are provided for
8 circuits, viz., s5378, s526, s1423, am2910, pcont2, piir8o,
mult16, and div16. The circuits were chosen because the test
sets available for them were reasonably large. The mult16
circuit is a 16-bit two's complement multiplier; div16 is a
16-bit divider; am2910 is a 12-bit microprogram sequencer;
pcont2 is an 8-bit parallel controller used in DSP applica-
tions; and piir8 is an 8-point infinite impulse response filter.
s5378, s526, and s1423 are circuits taken from the ISCAS89
benchmark suite. Parallel fault simulation was done with a
random test set of size 10,000 (i.e. a sequence of 10,000 randomly
generated input test vectors) and with actual test sets
obtained from an Automatic Test Pattern Generation (ATPG)
tool [13]. This shows the performance of the parallel fault
simulator both in a random test pattern environment and in a
grading environment. Table 1 shows the characteristics
of the circuits used, and the timings on a single processor for
both types of input test sets. The number of faults detected are
also shown.

Table

2 shows the execution times in seconds on 8 proces-
sors, on the SUNSparcCenter 1000E, obtained using all four
algorithms discussed in the previous section. SPF0, SPF1,
SPF4 and SPF5 refer to the algorithms SPITFIRE0, SPIT-
FIRE1, SPITFIRE4, and SPITFIRE5, respectively. The
same number of faults are detected by all algorithms. How-
ever, there may be a pessimism is the number of fault detected
which can be eliminated by using the pipelined approach in
the algorithm SPITFIRE3 [10].
A value of 5 was used for MinFaultLimit in SPF4 and SPF5,
MinFaultLimit
Execution Times(secs)
s526 2.43 2.26 2.33
div16 12.88 13.20 13.32

Table

5. Execution Times with SPITFIRE5 on 8 processors
for varying MinFaultLimit
as will be explained in the next paragraph. It can be seen from
the table that the execution times get progressively smaller, in
general, as we proceed from SPF0 to SPF1 to SPF4 to SPF5.
Sometimes SPF0 is better than SPF1, and sometimes SPF1 is
better than SPF4. The lowest execution time is shown in bold.
It can be seen that SPF5 always has the lowest execution time
for all algorithms. This shows that the algorithm SPITFIRE5
provides the best performance. We thus see that performing
the single stage of fault simulation and simultaneously
allowing asynchronous communication between processors
provides substantial savings in terms of execution time.

Tables

3 and 4 show the execution times and speedups obtained
with the random test sets and the ATPG test sets, respectively
on 1, 2, 4, and 8 processors for the algorithm SPIT-
FIRE5. It can be seen that the algorithm is highly scalable
and provides excellent speedups. The combined effect of test
set partitioning coupled with asynchronous communication of
detected faults has resulted in superlinear speedups in some
cases. The results from an experiment to determine the value
of MinFaultLimit are shown in Table 5. The experiment was
performed with 3 values of MinFaultLimit, viz., 2, 5, and 10,
using the actual test sets obtained from a test generator. It was
observed that the best performance was obtained with a value
of 5 for most circuits on 8 processors.
7 Conclusion
Parallel fault simulation has been a difficult problem due
to the limited scalability and parallelism that previous algorithms
could extract. Parallelization in fault simulation is
limited by the serial logic simulation of the fault-free ma-
chine. By partitioning the test sets across processors, we have
achieved a scalable parallel implementation and have thus
avoided the serial logic simulation bottleneck. By performing
asynchronous communication, we have dynamically reduced
the load on all processors, and the redundant computation
that may have otherwise occurred. We have thus presented
two asynchronous algorithms for parallel test set partitioned
fault simulation. Both asynchronous algorithms provide
better performance than their synchronous counterparts
on a shared memory multiprocessor. The single stage asynchronous
test set partitioned parallel algorithm was shown to
provide better performance than the two stage test set partitioned
asynchronous parallel algorithm, although the two
stage synchronous algorithm was better than the single stage
synchronous algorithm.



--R

"Is there hope for linear time fault simulation,"
Parallel Algorithms for VLSI Computer-Aided De- sign
"Parallel test generation for sequential circuits on general-purpose multiprocessors,"
"Fault simulation in a pipelined multiprocessor system,"
"Concurrent fault simulation of logic gates and memory blocks on message passing multicomput- ers,"
"A parallel algorithm for fault simulation based on PROOFS,"
"ZAMBEZI: A parallel pattern parallel fault sequential circuit fault simulator,"
"Overcoming the serial logic simulation bottleneck in parallel fault simulation,"
"Zamlog: A parallel algorithm for fault simulation based on Zambezi,"
"SPITFIRE: Scalable Parallel Algorithms for Test Partitioned Fault Simulation,"
"Distributed fault simulation with vector set partitioning,"
Portable Parallel Programming with the Message Passing Interface.
"Automatic test generation using genetically-engineered distinguishing se- quences,"
--TR
Parallel test generation for sequential circuits on general-purpose multiprocessors
Concurrent fault simulation of logic gates and memory blocks on message passing multicomputers
Parallel algorithms for VLSI computer-aided design
Using MPI
<italic>Zamlog</italic>
A parallel algorithm for fault simulation based on PROOFS
Overcoming the Serial Logic Simulation Bottleneck in Parallel Fault Simulation
Automatic test generation using genetically-engineered distinguishing sequences
ZAMBEZI

--CTR
Victor Kim , Prithviraj Banerjee, Parallel algorithms for power estimation, Proceedings of the 35th annual conference on Design automation, p.672-677, June 15-19, 1998, San Francisco, California, United States
circuit analysis computing;synchronous two stage approach;test set partitioned fault simulation;MPI;dynamic characteristics;shared memory multiprocessor;redundant work;sequential VLSI circuits;circuit CAD;software portability;Message Passing Interface;asynchronous parallel algorithms