臺灣博碩士論文加值系統

本論文提出一個基於共享記憶體多核心處理器系統下，使用錯誤分配概念之平行化測試圖樣產生器，不同於之前所提出的方法 [6, 7, 8]，我們消除了平行執行時所產生圖樣數量膨脹的問題，我們所提出的平行化測試圖樣產生器，能夠產生具確定性且無任何圖樣數量膨脹的結果，此外我們產生出的結果不因使用的核心個數而改變，使得平行化測試圖樣產生器更容易驗證其正確性，在我們的測試實驗中，大部分的電路 (s35932, s38417, s38584, b15s, b17s, D1, D2) 都可以使用我們的方法得到良好的加速 (3.5x ~ 9.6x 在使用8 cores的環境下)。

This thesis proposed a new fault partitioning parallel ATPG for shared-memory multi-core systems. Based on a pipelined fault processing principle and process synchronization, the proposed ATPG introduces no test inflation and achieves high parallelism. Furthermore, the returned test set is deterministic, even with respect to the number of utilized CPU cores; this simplifies the debugging process. Experimental results show that it achieves good speedup (3.5x ~ 9.6x with 8 cores) on the benchmarks circuits (s35932, s38417, s38584, b15s, b17s, D1, D2).

口試委員會審定書 i
誌謝 ii
中文摘要 iii
Abstract iv
Table of Contents v
List of Figures viii
List of Tables x
Chapter 1 Introduction 11
Chapter 2 Preliminaries 13
2.1. Determinism 13
2.2. Typical Serial ATPG 15
2.2.1 Generation Phase 16
2.2.2 Dynamic Compaction Phase 17
2.2.3 Fault Simulation Phase 18
2.3. Shared-Memory Multi-Core Systems 19
2.3.1 Shared Cache Architecture 20
2.3.2 False Sharing 20
Chapter 3 A Study of Parallel ATPG Methodologies 23
3.1. Fault Partitioning 23
3.2. Heuristic Partitioning 24
3.3. Search Space Partitioning 25
3.4. Circuit Partitioning 25
Chapter 4 Proposed Parallel ATPG Methodology 27
4.1. Proposed Deterministic Parallel ATPG 27
4.1.1 Zero pattern count inflation 27
4.1.2 Flowchart 29
4.2. Concept of Parallelism and Determinism 30
4.2.1 Generation Phase 31
4.2.2 Dynamic Compaction Phase 32
4.2.3 Fault Simulation Phase 34
4.3. Implementation 35
4.3.1 Hardware Friendly Data Structure 35
4.3.2 Synchronous Variables 36
4.3.3 Generation Phase 39
4.3.4 Confirmed Fault Selection 41
4.3.5 Dynamic Compaction Phase 45
4.3.6 Fault Simulation Phase 47
Chapter 5 Experimental Results 50
5.1. Speedup 51
5.2. Idle Ratio 53
5.3. Run Time Overhead 54
5.4. Physical Memory Overhead 56
5.5. Determinism 57
Chapter 6 Discussion 58
6.1. Super-Linear Speedup 58
6.2. Non-Deterministic Parallel ATPG 60
6.2.1 Speedup 61
6.2.2 Pattern count inflation 63
6.3. Fault List Order 64
Chapter 7 Conclusions 66
Bibliography 67

[1]R. Bocchino, V. Adve, S. Adve, and M. Snir, “Parallel programming must be deterministic by default”, Technical Report UIUCDCS-R-2008-3012, University of Illinois at Urbana-Champaign, 2008.
[2]E. A. Lee, The problem with threads, Computer, 2006.
[3]P. Goel, “An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits”, IEEE Transactions on Computers, vol. 30, no. 3, pp. 676-683, March 1981.
[4]H. Fujiwara and T. Shimono, “On the Acceleration of Test Generation Algorithms“, Proc. Int’l Fault-Tolerance Computing Symp., pp.98-105, 1983.
[5]J. P. Roth, “Diagnosis of Automata Failures: A Calculus and a Method,” IBM Journal of Research and Development, vol. 10, no. 4, pp278-291, 1966.
[6]X. Cai, P. Wohl, J.A. Waicukauski and P. Notiyath, “Highly efficient parallel ATPG based on shared memory”, International Test Conference, 2010.
[7]J. M. Wolf, L. M. Kaufman, R. H. Klenke, J. H. Aylor, and R. Waxman, “An analysis of fault partitioned parallel test generation”, IEEE Transactions on Computer-Aided Design, 15(5):517–534, May 1996.
[8]R. Butler, B. Keller, S. Paliwal, R. Scchoonover, and J. Swenton, “Design and implementation of a parallel automatic test pattern generation algorithm with low test vector count”, International Test Conference, pages 530–537, 2000.
[9]S. Chandra, J.H. Patel, “Test generation in a parallel processing environment,” Proc. Int. Conf. Computer Design, Oct. 1988..
[10]S. Patil and P. Banerjee, “A Parallel Branch-and-Bound Algorithm for Test Generation”, Proc. 26th ACMI/IEEE Design Automation Conf., CS Press, Los Alamitos, Calif., June 1989, pp. 339-334.
[11]Consolacion Gil, Julio Ortega, “Parallel Test Generation Using Circuit Partitioning and Spectral Techniques”, Proceedings of the Sixth Euromicro Workshop on Parallel and Distributed Processing, 1998.
[12]Tian Tian, Chiu-Pi Shih, “Software Techniques for Shared-Cache Multi-Core Systems”, http://software.intel.com/en-us/articles, 2011
[13]J. A. Waicukauski, E. B. Eichielberger, D. O. Forlenza, E. Lindbloom and T. McCarthy, "Fault Simulation for Structured VLSI", VLSI Systems Design, Vol. 6, No. 12, pp. 20-32, Dec. 1985.