Files in this item



application/pdf9124467.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


Title:Parallel algorithms for test generation and fault simulation
Author(s):Patil, Srinivas
Doctoral Committee Chair(s):Banerjee, Prithviraj
Department / Program:Engineering, Electronics and Electrical
Discipline:Engineering, Electronics and Electrical
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Electronics and Electrical
Abstract:With increase in complexity of digital circuits, it has become extremely important to detect faults to ensure correct operation of a digital circuit. Since test generation and fault simulation for circuits of VLSI complexity can take a prohibitive amount of time, speeding up test generation and fault simulation algorithms by either using better uniprocessor heuristics or by using the tremendous computing power available on multiprocessors thus becomes important. The design and analysis of parallel algorithms for test generation and fault simulation are the focus of this thesis research.
We first categorize various parallel processing techniques available for test generation and fault simulation. We then propose a parallel search method to overcome the deficiencies of inaccurate search heuristics. We show that this method not only results in faster execution of the test generation algorithm but also results in a better quality of the solution. We also propose a performance model to evaluate the parallel search technique.
We then propose fault partitioning techniques to speed up test generation for faults which are relatively easy to detect. The objective of the fault partitioning techniques is to maximize concurrency without affecting the quality of the overall solution. We propose load balancing techniques which try to minimize the processor idle time with very low communication overhead. We propose a performance model which takes into account the various trade-offs in exploiting parallelism in a test generation/fault simulation environment.
Finally, we present a parallel test generation system for sequential circuits. A parallel search technique is used to accelerate test generation for hard to detect faults, and a circuit partitioned approach is used to accelerate fault simulation.
Issue Date:1991
Rights Information:Copyright 1991 Patil, Srinivas
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9124467
OCLC Identifier:(UMI)AAI9124467

This item appears in the following Collection(s)

Item Statistics