跳到主要內容

臺灣博碩士論文加值系統

(44.210.77.73) 您好!臺灣時間:2024/02/28 04:12
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:廖官榆
研究生(外文):Kuan-Yu Liao
論文名稱:利用圖形處理器高品質測試向量產生器
論文名稱(外文):GPU-Based High Quality ATPG
指導教授:李建模
指導教授(外文):Chien-Mo Li
口試委員:饒建奇李進福黃俊郎劉靖家
口試委員(外文):Jiann-Chyi RauJin-Fu LiJiun-Lang HuangJing-Jia Liou
口試日期:2014-06-20
學位類別:博士
校院名稱:國立臺灣大學
系所名稱:電子工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:英文
論文頁數:109
中文關鍵詞:圖形處理器測試品質自動測試向量產生器平行計算
外文關鍵詞:GPUtest qualityATPGparallel computing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:257
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
由於製程的演進,晶片測試面臨兩個重要的議題:複雜的缺陷表現行為以及自動測試向量產生器 (ATPG) 過於耗時。針對這兩個議題,我們提出利用圖形處理器 (GPU) 的高品質自動測試向量產生器的演算法。傳統利用中央處理器 (CPU) 的自動測試向量產生器通常仰賴非常快速的選擇,以及一次只針對一個錯誤產生一組測試向量。我們提出的自動測試向量產生器不同於傳統,可以同時針對多個錯誤以及多重的測試目標產生測試向量。我們所提出的方法實做了三個層面的平行化:裝置層面 (device-level) 的錯誤分區平行化、區塊層面 (block-level) 的電路分區平行化、以及字組層面 (word-level) 的搜尋分區平行化。這是一個可以同時產生上千個測試向量高度平行化的演算法。這個演算法的核心是一個「分裂成 W 個分身」 (Split-into-W-Clones) 的自動測試向量產生器。這個演算法把產生測試向量過程需要做的選擇轉換成平行的字組邏輯運算,而使得許多的選擇可以同時進行。我們更進一步利用圖形處理器來加速這個演算法。我們也提出三個延伸的應用來解決時序感知 (timing-aware) 與標準元件感知 (cell-aware) 相關的議題。實驗結果證明我們提出的演算法不論在品質、運算時間、以及測試向量長度大多優於目前業界的利用中央處理器的自動測試向量產生器。

Due to the scaling of the manufacturing technology, two issues are critical in testing modern chips: 1) complex defect behavior; and 2) long automatic test pattern generator (ATPG) runtime. To deal with these issues, a graphical processing unit (GPU) based ATPG framework is proposed. Unlike central processing unit (CPU) based ATPG, which relies on fast serial decision making and generates one test pattern at a time, the proposed framework is capable of targeting multiple test objectives and multiple faults at the same time. This framework provides a completely new approach to the current test issues. The framework implements three levels of parallelisms: NewTerm{device}-level fault partitioning, NewTerm{block}-level circuit partitioning, and NewTerm{word}-level search space partitioning. The result is a massively paralleled algorithm which can generate thousands of patterns simultaneously. Such parallelism has not been achieved on traditional CPU-based ATPG. The core of the framework is the NewTerm{Split-into-W-Clones} (SWK) parallel ATPG algorithm, which can generate test patterns that meet multiple objectives. SWK uses NewTerm{random split} to convert decisions into parallel bitwise logic operations so that multiple objectives can be tried at the same time. A GPU-based massively parallel technique is then proposed to accelerate SWK algorithm. Three extensions are also prospoed based on the framework to deal with timing-aware and cell-aware issues. Results show that the framework provides higher quality, shorter test length, and shorter runtime compared with state-of-the-art CPU-based commercial ATPG.

Contents
中文口試委員審定書 i
英文口試委員審定書 ii
中文摘要 iii
Abstract iv
1 Introduction 1
1.1 Motivation 3
1.1.1 Test solutions for complex defect behaviors 4
1.1.2 ATPG runtime for targeting complex test metrics 7
1.2 Goal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Background 15
2.1 Test Quality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 ATPG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Timing-Aware ATPG . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Timing-Unaware ATPG . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3 Parallel ATPG . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 GPU Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
v
3 SWK ATPG Algorithm 23
3.1 SWK Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.1 SWK signal encoding . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.2 Difference between SWK and traditional ATPG . . . . . . . . . . 25
3.2 SWK Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.1 Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.2 Backtrace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.3 Assign Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.4 Backtrack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2.5 Initialize Multiple Objectives . . . . . . . . . . . . . . . . . . . 43
3.2.6 Dynamic Test Compaction . . . . . . . . . . . . . . . . . . . . . 45
3.2.7 Static Test Compaction . . . . . . . . . . . . . . . . . . . . . . . 47
3.2.8 Complex Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4 Parallelism Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4 GPU Parallelization 56
4.1 GPU Porting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.1.1 GPU Memory Allocation . . . . . . . . . . . . . . . . . . . . . . 58
4.1.2 GPU Memory Access Optimization . . . . . . . . . . . . . . . . 59
4.2 Test Generation Kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.1 Word-Level Parallel Test Generation for a Block . . . . . . . . . 60
4.2.2 Block-Level Parallel Test Generation for a Kernel . . . . . . . . 63
4.2.3 Device-Level Parallel Test Generation for a CUT . . . . . . . . . 65
4.3 Fault Simulation Kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.5 Parallelism Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
vi
5 High Quality Test Generation 74
5.1 Test Selection for Small Delay Defects . . . . . . . . . . . . . . . . . . . 75
5.1.1 Fault Dropping Criterion . . . . . . . . . . . . . . . . . . . . . . 76
5.1.2 Upper and Lower Bound Analysis . . . . . . . . . . . . . . . . . 77
5.1.3 Build Dictionary . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.1.4 Greedy Selection . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.1.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . 81
5.1.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2 Timing-Aware Test Generation . . . . . . . . . . . . . . . . . . . . . . . 83
5.2.1 Test Generation Kernel . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.2 Fault Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.2.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.3 Gate Exhaustive Transition Test Generation . . . . . . . . . . . . . . . . 92
5.3.1 GET Coverage and GET SDQL . . . . . . . . . . . . . . . . . . 95
5.3.2 Test Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.3.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6 Conclusion 103
Reference 105

Reference
[Aitken 99] R. C. Aitken. “Extending the pseudo-stuck-at fault model to provide
complete iddq coverage”. Proceedings IEEE VLSI Test Symposium,
1999:128–134.
[Alampally 11] S. Alampally, R. Venkatesh, P. Shanmugasundaram, R. A. Parekhji,
and V. Agrawal. “An efficient test data reduction technique through
dynamic pattern mixing across multiple fault models”. Proceedings
IEEE VLSI Test Symposium, 2011:285–290.
[Cai 10] X. Cai, P. Wohl, J. A. Waicukauski, and P. Notiyath. “Highly efficient
parallel atpg based on shared memory”. Proceedings IEEE International
Test Conference, 2010:1–7.
[Chang 13] C.-Y. Chang, K.-Y. Liao, S.-C. Hsu, J.-M. Li, and J.-C. Rau. “Compact
test pattern selection for small delay defect”. IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems, 32(6),
2013:971–975.
[Cho 05] K. Y. Cho, S. Mitra, and E. McCluskey. “Gate exhaustive testing”.
Proceedings IEEE International Test Conference, 2005:770–777.
[Friedman 74] A. D. Friedman. “Diagnosis of short-circuit faults in combinational
circuits”. IEEE Transactions on Computers, 1974:746–752.
[Fujiwara 83] H. Fujiwara and T. Shimono. “On the acceleration of test generation
algorithms”. IEEE Transactions on Computers, 100(12), 1983:1137–
1144.
[Galiay 80] J. Galiay, Y. Crouzet, and M. Vergniault. “Physical versus logical fault
models mos lsi circuits: Impact on their testability”. IEEE Transactions
on Computers, 29(6), 1980:527–531.
[Goel 81] P. Goel. “An implicit enumeration algorithm to generate tests for combinational
logic circuits”. IEEE Transactions on Computers, 100(3),
1981:215–222.
[Goel 09] S. K. Goel, N. Devta-Prasanna, and R. P. Turakhia. “Effective and
efficient test pattern generation for small delay defect”. Proceedings
IEEE VLSI Test Symposium, 2009:111–116.
[Gulati 08] K. Gulati and S. P. Khatri. “Towards acceleration of fault simulation
using graphics processing units”. Proceedings IEEE Design Automation
Conference, 2008:822–827.
105
[Gupta 04] P. Gupta and M. S. Hsiao. “Alaptf: A new transition fault model and
the atpg algorithm”. Proceedings IEEE Internation Test Conference,
2004:1053–1060.
[Hamzaoglu 98] I. Hamzaoglu and J. Patel. “New techniques for deterministic test pattern
generation”. Proceedings IEEE VLSI Test Symposium, 1998:446–
452.
[Hapke 09] F. Hapke, R. Krenz-Baath, A. Glowatz, J. Schloeffel, H. Hashempour,
S. Eichenberger, C. Hora, and D. Adolfsson. “Defect-oriented cellaware
atpg and fault simulation for industrial cell libraries and designs”.
Proceedings IEEE International Test Conference, 2009:1–10.
[Jahangiri 05] J. Jahangiri and D. Abercrombie. “Value-added defect testing techniques”.
IEEE Transactions on Design and Test of Computers, 22(3),
2005:224–231.
[Kirkland 87] T. Kirkland and M. R. Mercer. “A topological search algorithm for
atpg”. Proceedings IEEE Design Automation Conference, 1987:502–
508.
[Klenke 92] R. H. Klenke, R. D. Williams, and J. H. Aylor. “Parallel-processing
techniques for automatic test pattern generation”. IEEE Transactions
on Computers, 25(1), 1992:71–84.
[Kochte 10] M. A. Kochte, M. Schaal, H.-J. Wunderlich, and C. G. Zoellin. “Efficient
fault simulation on many-core processors”. Proceedings IEEE
Design Automation Conference, 2010:380–385.
[Lee 06] H. Lee, S. Natarajan, S. Patil, and I. Pomeranz. “Selecting high-quality
delay tests for manufacturing test and debug”. Proceedings IEEE International
Defect and Fault Tolerance in VLSI Systems Symposium,
2006:59–70.
[Lee 02] S. Lee, B. Cobb, J. Dworak, M. Grimaila, and M. Mercer. “A new
atpg algorithm to limit test set size and achieve multiple detections of
all faults”. Proceedings IEEE Design, Automation and Test in Europe,
2002:94.
[Li 10] M. Li and M. S. Hsiao. “Fsimgp&;#710; 2: An efficient fault simulator with
gpgpu”. Proceedings IEEE Asian Test Symposium, 2010:15–20.
[Liao 11] K.-Y. Liao, C.-Y. Chang, and J.-M. Li. “A parallel test pattern generation
algorithm to meet multiple quality objectives”. IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems,
30(11), 2011:1767–1772.
[Liao 13] K.-Y. Liao, S.-C. Hsu, and J. C.-M. Li. “Gpu-based n-detect transition
fault atpg”. Proceedings IEEE Design Automation Conference,
2013:28.
[Liao 14] K.-Y. Liao, A.-F. Lin, J. C.-M. Li, m. S. Hsiao, and L.-T. Wang. “Gpubased
timing-aware test generation for small delay defects”. Poster of
IEEE European Test Symposium, 2014.
[Lin 06] X. Lin, K.-H. Tsai, C. Wang, M. Kassab, J. Rajski, T. Kobayashi,
R. Klingenberg, Y. Sato, S. Hamada, and T. Aikyo. “Timing-aware
atpg for high quality at-speed testing of small delay defects”. Proceedings
IEEE Asign Test Symposium, 2006:139–146.
[Lin 08] Y.-T. Lin, O. Poku, N. Bhatti, and R. Blanton. “Physically-aware ndetect
test pattern selection”. Proceedings IEEE Design, Automation
and Test in Europe, 2008:634–639.
[Liu 12] Y. Liu and Q. Xu. “On modeling faults in finfet logic circuits”. Proceedings
IEEE Internaional Test Conference, 2012:1–9.
[Ma 95] S. Ma, P. Franco, and E. McCluskey. “An experimental chip to evaluate
test techniques: Experimental results”. Proceedings IEEE International
Test Conference, 1995:676–683.
[Malaiya 82] Y. K. Malaiya and S. Y. H. Su. “A new fault model and testing technique
for cmos devices”. Proceedings IEEE International Test Conference,
1982:25–34.
[Maxwell 92] P. Maxwell, R. Aitken, V. Johansen, and I. Chiang. “The effectiveness
of iddq, functional, and scan tests: How many fault coverages do we
need?” Proceedings IEEE International Test Conference, 1992:676–
683.
[Maxwell 91] P. C. Maxwell, R. C. Aitken, V. Johansen, and I. Chiang. “The effect of
different test sets on quality level prediction: When is 80% better than
90%?” Proceedings IEEE International Test Conference, 1991:358.
[McCluskey 00] E. J. McCluskey and C.-W. Tseng. “Stuck-fault tests vs. actual defects”.
Proceedings IEEE International Test Conference, 2000:336–
342.
[Mei 74] K. C. Y. Mei. “Bridging and stuck-at faults”. IEEE Transactions on
Computers, 1974:720–727.
[Mitra 04] S. Mitra, S. Eichenberger, E. Volkerink, and E. J. McCluskey. “Delay
defect screening using process monitor structures”. Proceedings IEEE
VLSI Test Symposium, 2004:43–43.
[Meuhldorf 76] E. Muehldorf. “Designing lsi logic for testability”. Proceedings IEEE
International Test Conference, 1976:45–49.
[Nigh 97] P. Nigh, W. Needham, K. Butler, P. Maxwell, and R. Aitken. “An
experimental study comparing the relative effectiveness of functional,
scan, iddq and delay-fault testing”. Proceedings IEEE VLSI Test Symposium,
1997:459–464.
[Patil 90] S. Patil and P. Banerjee. “A parallel branch and bound algorithm for
test generation”. IEEE Transactions on Computer-Aided Design of
Integrated Circuits and Systems, 9(3), 1990:313–322.
[Peng 10] K. Peng, J. Thibodeau, M. Yilmaz, K. Chakrabarty, and M. Tehranipoor.
“A novel hybrid method for sdd pattern grading and selection”.
Proceedings IEEE VLSI Test Symposium, 2010:45–50.
[Qiu 04] W. Qiu, L.-C. Wang, D. Walker, D. Reddy, X. Lu, Z. Li, W. Shi, and
H. Balachandran. “K longest paths per gate (klpg) test generation for
scan-based sequential circuits”. Proceedings IEEE Test Conference,
2004:223–231.
[Rearick 06] J. Rearick. “A survey of test problems and solutions”. Proceedings
IEEE Internaltional Test Conference, 2006:1–10.
[Roth 76] J. P. Roth. “Method of testing for shorts”. IBM Technical Disclosure
Bulletin, 1976:3108–3109.
[Roth 66] J. P. Roth. “Diagnosis of automata failures: A calculus and a method”.
IEEE Transactions on Computers, 1981:676–683.
[Sato 05] Y. Sato, S. Hamada, T. Maeda, A. Takatori, Y. Nozuyama, and S. Kajihara.
“Invisible delay quality-sdqm model lights up what could not be
seen”. Proceedings IEEE International Test Conference, 2005:9–12.
[Schulz 88] M. H. Schulz, E. Trischler, and T. M. Sarfert. “Socrates: A highly
efficient automatic test pattern generation system”. IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems, 7(1),
1988:126–137.
[Seshu 65] S. Seshu. “On an improved diagnosis program”. IEEE Transactions
on Electronic Computers, (1), 1965:76–79.
[Shao 02] Y. Shao, I. Pomeranz, and S. M. Reddy. “On generating high quality
tests for transition faults”. Proceedings IEEE Asign Test Symposium,
2002:1–8.
[Smith 85] G. Smith. “Model for delay faults based upon paths”. Proceedings
IEEE International Test Conference, 1985:342–349.
[Smith 87] S. P. Smith, B. Underwood, and M. R. Mercer. “An analysis of several
approaches to circuit partitioning for parallel logic simulation”.
IEEE Transactions on International Conference on Computer Design,
1987:664–667.
[Venkataraman 04] S. Venkataraman, S. Sivaraj, E. Amyeen, S. Lee, A. Ojha, and
R. Guo. “An experimental study of n-detect scan atpg patterns on
a processor”. Proceedings IEEE VLSI Test Symposium, 2004:23–28.
[Wadsack 78] R. L. Wadsack. “Fault modeling and logic simulation of cmos and mos
integrated circuits”. Bell System Technical Journal, 1978:1449–1474.
[Waicukauski 87] J. Waicukauski, E. Lindbloom, B. K. Rosen, and V. Iyengar. “Transition
fault simulation”. IEEE Transactions on Design and Test of
Computers, 4(2), 1987:32–38.
[Waicukauski 89] J. A. Waicukauski and E. Lindbloom. “Failure diagnosis of structured
vlsi”. IEEE Transactions on Design and Test of Computers,
6(4), 1989:49–60.
[Yilmaz 08b] M. Yilmaz, K. Chakrabarty, and M. Tehranipoor. “Interconnectaware
and layout-oriented test-pattern selection for small-delay defects”.
Proceedings IEEE International Test Conference, 2008:1–10.
[Yilmaz 08a] M. Yilmaz, K. Chakrabarty, and M. Tehranipoor. “Test-pattern grading
and pattern selection for small-delay defects”. Proceedings IEEE
VLSI Test Symposium, 2008:233–239.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊