Shi, Zhimin (1994) Exploring linear speedup in parallel ATPG through special topology. Masters thesis, Memorial University of Newfoundland.
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.
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.
|Item Type:||Thesis (Masters)|
|Additional Information:||Bibliography: leaves 104-108.|
|Department(s):||Science, Faculty of > Computer Science|
|Library of Congress Subject Heading:||Digital integrated circuits--Testing; Integrated circuits--Very large scale integration; Parallel processing (Electronic computers)|
Actions (login required)