自動測試圖樣產生技術被廣泛運用於對測試電路產生測試圖樣。雖然自動測試圖樣產生技術的複雜度能在掃瞄鏈模式下降低，日漸增大的電路規模及複雜的錯誤模型使得自動測試圖樣產生技術越來越耗時。多核心及多電腦平行處理是目前加速自動測試圖樣產生技術的熱門作法。然而，平行化自動測試圖樣產生技術也帶來新的挑戰及問題，例如測試圖樣數量膨脹及測試圖樣產生結果不確定性。到目前為止，所提出的平行化圖樣產生技術皆無法完全解決這些副作用。
本論文提出多個具確定性且同時考慮規模性加速及測試圖樣品質之平行化圖樣產生技術。首先，我們提出一個能達到規模性加速並降低測試圖樣數量膨脹的技術。接著，我們提出一個能完全消除測試圖樣數量膨脹及提升測試圖樣效率的流程。最後，為了同時將規模性加速及測試圖樣品質納入考量，我們提出混合式平行化圖樣產生技術，能同時達到規模性加速並同時提升測試圖樣效率及增加錯誤涵蓋率。

Automatic test pattern generation (ATPG) is widely utilized to generate test patterns for circuit under test (CUT). Although the complexity of ATPG has been reduced under scan chain testing, increasing circuit size and more complex fault model makes ATPG more time-consuming. Multi-CPUs and multi-computers parallel techniques are the most popular ways to speed up ATPG. However, the parallelized ATPGs also brought new challenge and problems, such as test pattern inflation and non-determinism. As so far, there’s no previous work to fully solve these side effects.
This thesis proposes three deterministic parallel ATPG techniques to consider determinism, scalable speedup, and test quality. This dissertation starts with a new technique, which aims at achieve scalable speedup and reduces test pattern inflation. Next, we proposed an effective flow to fully eliminate test pattern inflation and enhance pattern effectiveness. Finally, to take both scalable speedup and test quality into consideration, we proposed a hybrid parallel ATPG approach which achieves scalable speedup but also enhances the fault coverage and pattern effectiveness.

口試委員審定書 i
誌謝 ii
中文摘要 iii
Abstract iv
Table of Contents vi
List of Figures x
List of Tables xii
Chapter 1 Introduction 1
1.1. Typical Serial ATPG 2
1.1.1 Pseudo-random ATPG 3
1.1.2 Deterministic ATPG 3
1.1.3 Fault dropping 4
1.1.4 Post-ATPG static pattern compaction 5
1.2. Parallel Processing Architecture 5
1.2.1. Shared memory systems 5
1.2.2. Message passing systems 6
1.3. Parallel Processing Approach 7
1.3.1. Fault parallelism 7
1.3.2. Search space parallelism 11
1.3.3. Heuristic parallelism 12
1.3.4. Circuit partitioning 14
1.4. Modern Parallel ATPG challenge 15
1.4.1. Determinism 15
1.4.2. Test pattern inflation 17
1.5. Overview of the Dissertation 18
1.5.1. Deterministic fault parallel ATPG 19
1.5.2. Deterministic search space partitioning TPG 19
1.5.3. Deterministic hybrid-parallel ATPG 19
1.6. Organization of the Dissertation 20
Chapter 2 Deterministic Fault Parallel ATPG 21
2.1. The Proposed Fault Parallel ATPG Methodology 21
2.1.1. Overview 22
2.1.2. The circular pipeline processing (CPP) Mode 24
2.1.3. Pipeline PR-ATPG 30
2.1.4. Parallel single-fault ATPG 36
2.1.5. Pipeline pattern compaction 37
2.1.6. Pipeline fault dropping 40
2.1.7. Pipeline reverse fault simulation 40
2.2. Experimental Results 40
2.2.1. Single-thread CPP-ATPG 41
2.2.2. CPP-ATPG speedup vs. thread count 44
2.2.3. CPP-ATPG test set quality 44
2.2.4. Idle time analysis 45
2.2.5. Test pattern count reduction 46
2.2.6. CPP-ATPG vs. parallelized s-ATPG 47
Chapter 3 Deterministic Search-Space Partitioning ATPG 51
3.1. Motivation 51
3.2. The Proposed Search-Space Parallel ATPG Methodology 52
3.2.1. Overview 53
3.2.2. High-level flow of search-space partitioning ATPG 57
3.2.3. Static search-space partitioning 59
3.2.4. Dynamic search-space allocation 63
3.2.5. Search space traveling 65
3.2.6. Pattern selection 68
3.2.7. Terminate condition 69
3.3. Experimental Results 69
3.3.1. Single-thread DSSP-ATPG 71
3.3.2. Fault coverage of DSSP-ATPG 71
3.3.3. Pattern count of DSSP-ATPG 73
3.3.4. Pattern effectiveness of DSSP-ATPG 74
3.3.5. The speedup of DSSP-ATPG 76
Chapter 4 Deterministic Hybrid-Parallel ATPG 79
4.1. Motivation 79
4.2. The Proposed Hybrid-Parallel ATPG Methodology 79
4.2.1. Overview 81
4.2.2. DHP-ATPG configuration 82
4.2.3. Task execution constraints 83
4.2.3. Deterministic ATPG flow of DHP-ATPG 87
4.3. The Guideline of Choosing DHP-ATPG Configuration 89
4.4. Experimental Results 90
4.4.1. Single-thread DHP-ATPG 91
4.4.2. Single-group DHP-ATPG 91
4.4.3. DHP-ATPG under different configurations 92
Chapter 5 Concluding Remarks 96
Bibliography 98

[1]K.-W. Yeh, J.-L. Huang, H.-J. Chao, and L.-T. Wang, “A circular pipeline processing based deterministic parallel test pattern generator,” in Proc. IEEE Int. Test Conf., Sept. 2013, pp. 1–8.
[2]X. Cai, P. Wohl, and D.Martin, “Fault sharing in a copy-on-write based atpg system,” in Proc. IEEE Int. Test Conf., Oct. 2014, pp. 1–8.
[3]X. Cai and P. Wohl, “A distributed-multicore hybrid atpg system,” in
Proc. IEEE Int. Test Conf., Sept. 2013, pp. 1–7.
[4]X. Cai, P. Wohl, J. Waicukausi, and P. Notiyath, “Highly efficient parallel ATPG based on shared memory,” in Proc. IEEE Int. Test Conf., Nov.2010, pp. 1–7.
[5]Chun-Hao Chang, K.-W. Yeh, Jiun-Lang Huang, and Laung-Terng Wang, “Sdc-tpg: A deterministic zero-inflation parallel test pattern generator,” in Proc. IEEE Int. Asian Test Symp., Nov.2015, pp. 43–48.
[6]J. C. Y. Ku, R. H.-M. Huang, L. Y. Z. Lin, and C. H.-P. Wen,“Suppressing test inflation in shared-memory parallel automatic test pattern generation,” in Proc. IEEE Asia South Pacific Des. Autom. Conf., Jan. 2014, pp. 664–669.
[7]K.-W. Yeh, M.-F. Wu, and J.-L. Huang, “A low communication and load balanced parallel ATPG with improved static fault partition method,” in Proc. Int. Conf. Algorithms Architectures Parallel Process., Jun. 2009, pp. 362–371.
[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,” in Proc. IEEE Int. Test Conf., Oct. 2000, pp. 530–537.
[9]J. Sienicki, M. L. Bushnell, P. Agrawal, and V. D. Agrawal, “An adaptive distributed algorithm for sequential circuit test generation,” in Proc. IEEE EURO-DAC, Sept. 1995, pp. 236–241.
[10]M. Aquado, E. de la Torre, M. Miranda, and C. Lopez-Barrio, “Distributed implementation of an ATPG system using dynamic fault allocation,” in Proc. IEEE Int. Test Conf., Oct. 1993, pp. 409–418.
[11]S. Patil and P. Banerjee, “Performance trade-offs in a parallel test generation/fault simulation environment,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 10, no. 12, pp. 1542–1558, Dec. 1991.
[12]J. M. Wolf, L. M. Kaufman, R. H. Klenke, J. H. Aylor, and R. Waxman,“An analysis of fault partitioned parallel test generation,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 15, no. 5, pp. 517–534, May 1996.
[13]S. Patil and P. Banerjee, “Fault partitioning issues in an integrated parallel test generation/fault simulation environment,” in Proc. IEEE Int. Test Conf., Aug. 1989, pp. 718–726.
[14]R. H. Klenke, L. Kaufman, J. H. Aylor, R. Waxman, and P. Narayan,“Workstation based parallel test generation,” in Proc. IEEE Int. Test Conf., Oct. 1993, pp. 419–428.
[15]S. Patil and P. Banerjee, “A parallel branch-and-bound algorithm for test generation,” in Proc. IEEE DAC, Jun. 1989, pp. 339–344.
[16]R. H. Klenke and J. H. Aylor, “Parallel-processing techniques for automatic test pattern generation,” IEEE Trans. Comput., vol. 25, no. 1, pp. 71–84, Jan. 1992.
[17]K.-Y. Liao, C.-Y. Chang, and J. C.-M. Li, “A parallel test pattern generation algorithm to meet multiple quality objectives,” IEEE Trans.Comput.-Aided Design Integr. Circuits Syst., vol. 30, no. 11, pp. 1767–1772, Nov. 2011.
[18]A. Czutro, I. Polian, M. Lewis, P. Engelke, S. M. Reddy, and B. Becker,“TIGUAN: Thread-parallel integration test pattern generator utilizing satisfiability analysis,” in Proc. IEEE VLSI Des., Jan. 2009, pp. 227–232.
[19]I. Pomeranz and L. N. Reddy, “COMPACTEST: A method to generate compact test sets for combinational circuits,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 12, no. 7, pp. 1040–1049, Jul. 1993.
[20]S. Chandra, J.H. Patel, “Test generation in a parallel processing environment,” Proc. Int. Conf. Computer Design, Oct. 1988.
[21]J. A. Waicukauski, E. B. Eichelberger, D. O. Forlenza, E. Lindbloom, and T. McCarthy, “Fault simulation for structured vlsi,” in Proc. IEEE VLSI Syst. Des., 1985, pp. 20–32.
[22]S. Sehsu, “On improved diganosis program,” IEEE Trans. Electron. Comput., vol. 14, no. 1, pp. 76–79, Feb. 1965.
[23]P. Goel, “An implication enumeration algorithm to generate tests for combinational logic circuits,” IEEE Trans. Electron. Comput., C– 30(1):215–222, Mar. 1981.
[24]H. Fujiwara and T. Shimono, “On the acceleration of test generation algorithm,” IEEE Trans. Comput., C–32(12):1137–1144, Dec. 1983.
[25]D. R. Butenhof., Programming with POSIX threads. Addison-Wesley Longman Publishing Co., Inc., 1997.