Title

Automatic Test Pattern Generation On Parallel Processors

Keywords

backtrack search algorithms; combinational circuits; experimental results; parallel implementation; test generation; VLSI design

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). © 1991 Elsevier Science Publishers B.V. All rights reserved.

Publication Date

1-1-1991

Publication Title

Parallel Computing

Volume

17

Issue

12

Number of Pages

1323-1342

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/S0167-8191(05)80001-8

Socpus ID

0026381246 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0026381246

This document is currently not available here.

Share

COinS