Exploring linear speedup in parallel ATPG through special topology

Shi, Zhimin (1994) Exploring linear speedup in parallel ATPG through special topology. Masters thesis, Memorial University of Newfoundland.

[English] PDF (Migrated (PDF/A Conversion) from original format: (application/pdf)) - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (11MB) [English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. (Original Version)

Abstract

In digital system design, test pattern generation requires a considerable amount of computing time. Using a level-sensitive scan design, test pattern generation can be confined to the combinational circuits. It has been shown that the problem of test pattern generation for combinational circuits is NP-complete. Although many excellent algorithms have been developed to generate test patterns, they still do not keep pace with VLSI technology. Research is ongoing in the development of parallel processing techniques for test pattern generation, but there has been little research into what kind of topology has the greatest potential to speed up test pattern generation. -- In this work, simulation software was developed for measurement of the speedup, and three topologies are proposed to explore the parallelism for automatic test pattern generation. These topologies are: modified complete binary tree (MCBTA), autonomous modified complete binary tree (AMCBTA), and square array structure (SQARRAY). The empirical results for these topologies show that a special topology has the potential capability to speed up test pattern generation and super-linear speedup can often result if an autonomous structure is adopted.

Actions (login required)

View Item