Development of Parallel Distributed Computing System for ATPG Program K. Han Electrical and Computer Engineering Auburn University ABSTRACT I present an approach about how to increase the speed-up ratio in parallel test generation based on a general system for distributed test generation. I implement a general purpose system for distributed computing using MPI. HITEC/PROOFS, an existing fault simulation and test generation package, is plugged into the system and together they form a distributed fault simulation and test generation framework. The experimental results on the ISCAS circuit demonstrate that this approach leads to considerable speed-up compared to running the package on a single computer. This approach is convenient to use since most of the work to achieve parallelization is transparent to the user. 1. INTRODUCTION Generation of test vectors for the VLSI devices used in contemporary digital systems is becoming much more difficult as these devices increase in size and complexity. Automatic Test Pattern Generation (ATPG) techniques are commonly used to generate these tests. Since ATPG is an NP complete problem with complexity exponential to circuit size, the application of parallel processing techniques to accelerate the process of generating test vectors is an active research area. In recent years, besides the research to increase the efficiency of the test generation system in a single processor [1], a lot of researches all over the world have been devoted to study the parallel test generation algorithms. Some approaches based on fault parallelism, heuristic parallelism, searching space parallelism, function parallelism, circuit parallelism, etc, has been proposed. Many prototype parallel systems have been implemented, such as the parallel system using grouping circuit faults according to primary input fan-out cones [2], the system using heuristic parallelism [3], the system using searching space parallelism to deal with hard-to-detect faults [4], and the system using the parallelism of faults [5], searching space [6], and circuit [7] for sequential circuits. All of these systems belong to small-scale parallelism, with 5~16 processors. Their common characteristic is to emphasize on dynamic load balance among processors. It is difficult to increase the speed-up ratio with dynamic load balance in MPP (N>=128). So a research paid much attention to static load balancing that would increase the speed-up ratio of parallel test generation and avoid the high communication overhead, and proposed an optimal parallel test algorithm based on static fault partitioning in MPP [8]. However, it is definitely more convenient and cost-effective to do distribute computing with existing general purpose software packages instead of specially designed parallel software. This project intends to transform general-purpose software to perform distributed computing. I present a distributed system implemented with MPI.2. THE HITEC/PROOFS PACKAGE HITEC/PROOFS [9] is a gate-level, sequential circuit fault simulation and test generation package from the University of Illinois. It runs on the UNIX platform, and it is not specifically designed for parallel computing. It targets single stuck-at faults in synchronous sequential circuits described in the ISCAS89 benchmark format. The HITEC/PROOFS package consists of two main programs and four pre-processing programs. A thorough analysis of their inputs and outputs as well as the data flow is essential to constructing system. The four pre-processing programs levelize the circuit (level), create a complete fault list (faultlist), collapse the fault list (equiv), and calculate the dominators in a circuit (dominators), respectively. The two main programs are the test generator (testgen) and the fault simulator (faultsim). The fault simulator can be executed as a stand-alone program to fault grade a set of test vectors provided by the user, or in conjunction with the test generator to identify all faults detected by each test sequence generated by it. It also needs the levelized circuit description and the collapsed fault list (circuit.eqf) generated by the equiv program. The test generator takes as inputs the levelized circuit description, collapsed fault list, and the output of the dominators program. The outputs are circiut.grs that contains runtime, efficiency and other statistics; circuit.atp that contains the result test set; and circuit.red that contains untestable faults. 3. MESSAGE PASSING WITH MPI To build a distributed computing framework with general purpose software, we need to create an engine to facilitate message passing among processes as well as undertake processes management such as spawning new processes. MPI [10] is simply a function that explicitly transmits data from one process to another. It is a powerful and very general method of expressing parallelism. It can be used to create extremely efficient parallel programs, and message passing is currently the most widely used method of programming many types of parallel computers. I implement this project using the master/slave architecture. The master deals with task allocation and message management. The slaves deal with actual execution of the algorithm and finding the test vectors. The master keeps checking for messages being received from slaves. The communication primitives and process spawning are implemented with MPI. 4. SYSTEM ARCHITECTURE 4.1 Partitioning In test generation, it is usually assumed that there is only one fault at a time. There is no interaction among different faults in the fault list. This single fault assumption makes it possible to partition the original test generation problem using the data parallel approach.I partition the original fault list (circiuf.fault) and into pieces and distribute each sub-list to an instance of test generator, which then work on each partitioned fault lists separately and simultaneously. Other input files like the circuit description don’t need to be partitioned, because they don’t represent workload. The results from these processes can then be collected and combined to produce the final result. For test generation, I combine the results by combining all circuit.ref files into one file, and all circuit.atp files into one file then eliminate all the duplicate entries from this file. Load balancing is also an important issue in distributed computing. In this project static load balance is not used. I