Title

Automatic Test Pattern Generation On Parallel Processors

Title - Alternative

Parallel Comput.

Keywords

VLSI DESIGN; TEST GENERATION; COMBINATIONAL CIRCUITS; BACKTRACK SEARCH; ALGORITHMS; PARALLEL IMPLEMENTATION; EXPERIMENTAL RESULTS; ALGORITHM; Computer Science, Theory & Methods

Abstract

Test generation for combinational circuits is an important step in the VLSI design process. Unfortunately, the problem is highly computation-intensive and for circuits encountered in practice, test generation time can often be enormous. In this paper, we present a parallel formulation of the backtrack search algorithm called PODEM, which is a highly used algorithm for this problem. It is known that the sequential PODEM algorithm consumes most of its execution time in generating tests for 'hard-to-detect' (HTD) faults and is often unable to detect them even after a large number of backtracks. Our parallel formulation overcomes these limitations by dividing the search space and searching it concurrently using multiple processes. We present a number of experimental results and show that these match our theoretical results presented elsewhere. We show that the search efficiency of the parallel algorithm improves and even beats that of the sequential algorithm as the 'hardness' of a fault increases. We present speedup results and performance analyses of our formulation on a 128 processor Symult s2010 multicomputer. We also present preliminary results on a network of Sun workstations. Our results show that parallel search techniques provides good speedups as well as high fault coverage of the HTD faults in reasonable time when compared to the uniprocessor implementation. Our experimental validation of most of our theoretical results builds confidence in the following theoretical prediction: our parallel formulation of PODEM is highly scalable on a variety of commercially-available, large MIMD parallel processors (in additions to the ones with which we experimented).

Publication Title

Parallel Computing

Volume

17

Issue/Number

12

Publication Date

1-1-1991

Document Type

Article

Language

English

First Page

1323

Last Page

1342

WOS Identifier

WOS:A1991GV34200001

ISSN

0167-8191

Share

COinS