Transition Fault Testing using pattern shifting - The sequential Pseudocode

Program - Transition fault testing using pattern shifting
Serial version of the program is described here in detail
This is the program i had written for testing delay transition faults. I am trying to parallelize this program.

DELAY TESTING
OBJECTIVE
slow to raise and slow to fall patterns are to be tested.
to test a slow to rise fault- apply a sa1 pattern (for a modified netlist) followed by a sa0 pattern (for unmodified netlist)
to test a slow to fall fault - apply a sa0 pattern (for a modified netlist) followed by a sa1 pattern (for unmodified netlist)

                     pattern 1   pattern 2
 Slow to rise    sa1         sa0      
 Slow to fall    sa0         sa1   

pattern 1 - patterns for modified netlist
pattern 2 - patterns for unmodified netlist

Testing for faults
A. fault pattern generation
1. For each wire - Slow to rise/fall (s2r,s2f)
1. Generate pattern1 and pattern2.
2. for each pattern 1
for each pattern2
shift pattern1 by 1 bit and compare with each pattern2.
if this shifted pattern is compatible with a pattern2 then merge them together, the slow-to-rise/fall fault is detected.
if none of patterns in pattern2 match with pattern1, get the next pattern in pattern1 and repeat the process.
3. If all pattern1s are exhausted and still the fault is not detected then mark the wire as undetected.
4. get the next wire and repeat the process.
B. Compaction
2. In the end of the day you have patterns for wires whose s2r and s2f faults are detected in a file, compact the faults to reduce the number of test patterns.
compaction:
Read all the patterns in the output file into an array
for each pattern
while patterns exist
compare pattern with the patterns succeding it,
if compatible replace the pattern with merged pattern and continue comparing


COMPARSION OF PATTERNS - shift comparison
1. Two sets of patterns
2. Get a pattern from set 1
3. shift the pattern by 1 bit
4. Compare the pattern 1 with all patterns in set 2
5. When a match is found, fetch next pattern from set 1 and repeat the steps

Comparison of patterns - compaction
1. Two sets of patterns
2. Get a pattern from set 1
3. compare wiht a pattern from set 2
4. if compatible, merge and continue comparison


The program flow
1. Calls perl to create a file "circuit_name.sa0.flt" that has all the wires in a standard stuck at 0 representation.
2. For each wire
1. Read a wire /0 from the above created file and create a wire /1 representation for that wire.
2. Modify the netlist - make the wire under consideration an output and add it in the end of the netlist - we have the modified netlist
3. Test for slow to rise fault - put the tested faults into a file (circuit.ttest)
4. Test for slow to fall fault - put the tested faults into a file (circuit.ttest)
5. Compact the faults present in circuit.ttest and put the resulting compacted patterns into the same file.


Test for slow to rise fault
1. open fault file and put "wire /1" into the fault file and close - (test for wire sa1)
2. call atalanta for the fault file - generates pattern1 faults into the default output file (circuit.test).
3. call file_parser().  - parse the default output file of atalanta (circuit.test) to read the pattern1s into a 2D array.
1. If fault patterns (pattern1s) are not generated, the fault is undetected, proceed to test for slow to fall fault for the wire
4. if pattern1s are generated, generate pattenrn2s
open fault file and put "wire /0" into the fault file and close (test for wire sa0)
call atalanta to generate pattern2s
call file_parser() to read the pattern2s into another 2D array.
5. Pattern1 and Pattern2s are available in 2D arrays.
6. For each pattern 1
For each pattern 2
call compare_test() in mode 0
if compatible, get the merged pattern and break - fault is detected
else continue.
7. If fault is detected, put the wire and the merged pattern into a file (circuit.ttest) and proceed to test for slow to fall fault
8. If fault is not detected then the fault is undetected, proceed to test for slow to fall fault

Test for slow to fall fault 
1. open fault file and put "wire /0" into the fault file and close - (test for wire sa0)
2. call atalanta for the fault file - generates pattern1 faults into the default output file (circuit.test).
3. call file_parser().  - parse the default output file of atalanta (circuit.test) to read the pattern1s into a 2D array.
1. If fault patterns (pattern1s) are not generated, the fault is undetected, proceed to test for slow to fall fault for the wire
4. if pattern1s are generated, generate pattenrn2s
open fault file and put "wire /1" into the fault file and close (test for wire sa1)
call atalanta to generate pattern2s
call file_parser() to read the pattern2s into another 2D array.
5. Pattern1 and Pattern2s are available in 2D arrays.
6. For each pattern 1
For each pattern 2
call compare_test() in mode 0
if compatible, get the merged pattern and break - fault is detected
else continue.
7. If fault is detected, put the wire and the merged pattern into a file (circuit.ttest) and proceed to test for slow to fall fault
8. If fault is not detected then the fault is undetected, proceed to test for slow to fall fault.

Compact the faults present in the output fault file (circuit.ttest)
1. call file_parser_ttest(). To read all the patterns into a 2D array
2. For each pattern (patternA) in the array
while next patterns(patternB) exist
compare patternA with the patternB.
If compatible, merge them together and store it in patternA.
else continue comparison with the next patternB.
if patternB are exhausted, get next patternA and repeat the compaction
3. when all patternAs are compacted, write the patterns into the output file (circuit.ttest)

FUNCTIONS USED
1. A Call to a function written in perl. Reads the netlist and extracts the wires, appends with a /0 and writes into a fault file.

2. func:
void atalanta_call(char *)
Desc: Forks a new process which calls the atalanta tool. The parent waits till the child completes completes. Atalanta generates a file which holds test patterns for the fault under test.

3. file_parser()
Reads the file genereated by atalanta and stores the patterns into a 2D array- Parallelization possible

4. compare_patterns()
two modes of operation: mode 0, mode 1 -  mode 0 is used to shift compare (used in shift pattern testing), mode 1 is used to compare (used in compaction).
pattern matching techniques possible - look into it.

5. copy_files()
copies one file into another.

6. file_parser_ttest()
reads the circuit.ttest patterns into a 2D array used for compaction.

The complete program is explained here. The next step is analyse the program for parallelizability.
Things to be taken into consideration for parallelization.
STEP 1
1. Decomposition into tasks that can be run in parallel.
2. For the tasks identify dependencies, shared address space, message passing operations.
3. Take into consideration the granularity of the code executing in parallel.
STEP 2
1. Assignment of the tasks to different threads
2. Look into efficient utilization of cache.