| In this thesis, we investigate new parallel algorithms for sequential circuit fault simulation using overlapping test set partitions and new parallel genetic algorithms for simulation-based sequential circuit test generation.; In the first part of the thesis, we propose six parallel algorithms for scalable parallel test set partitioned fault simulation (SPITFIRE). The test set partitioning inherent in the algorithms overcomes the good circuit logic simulation bottleneck that exists in traditional fault partitioned approaches to parallel fault simulation. Since the test sequence is partitioned, both the good and faulty circuit simulation costs are scaled down. First, single-stage and two-stage synchronous parallel algorithms are presented. Next, these algorithms are improved using an asynchronous approach where detected faults are broadcast to all processors, thereby reducing the load on each processor. A monotonically decreasing schedule for the threshold for communicating detected faults in the asynchronous algorithms is shown to perform very well. To correct any pessimism that may exist with single-stage and two-stage algorithms, a pipelined synchronous algorithm and a hybrid asynchronous pipelined algorithm are presented. It is shown that, in the hybrid asynchronous pipelined parallel algorithm, there is no pessimism in the fault coverage. Furthermore, the combination of a stage of asynchronous communication followed by pipelining results in very minimal redundant work and is therefore very scalable and nearly optimal. A theoretical analysis comparing the various algorithms is also given to provide an insight into these algorithms.; In the second part of the thesis, we present four parallel genetic algorithms for simulation-based sequential circuit test generation. Simulation-based test generators are more capable of handling the constraints of complex design features than deterministic test generators. The first three algorithms are based upon a sequential algorithm that targets a group of faults simultaneously. The first algorithm is PGATEST1, which uses data decomposition to distribute the computation of the fitness of different members of a population among various processors. It produces the same result as the sequential algorithm. The second algorithm, PGATEST2, uses a parallel search strategy where each processor executes the sequential genetic algorithm with a different seed, and uses migration to share information between processors. This parallel algorithm has the potential of obtaining a better quality result than the serial algorithm. The third algorithm, PGATEST3, is a subpopulation based version of PGATEST2, where subpopulations are distributed across processors, and information is migrated from one processor to another. The fourth algorithm, PSTRAT, uses a fault-oriented approach to test generation, as opposed to a fault-sample based approach that was used in the PGATEST algorithms. In this algorithm decisions related to the progress of the genetic algorithm are taken globally, with faults being dynamically allocated to various processors in every pass through the genetic algorithm to obtain optimal load balance.; All implementations were done using the MPI communication library and are therefore portable to many parallel platforms. All algorithms provide excellent performance in terms of speedup and quality on both shared-memory and distributed-memory parallel platforms. |
