跳到主要內容

臺灣博碩士論文加值系統

(18.97.9.169) 您好!臺灣時間:2025/02/18 20:10
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳敬元
研究生(外文):Ching-Yuan Chen
論文名稱:基於錯誤效應驅動決策樹以提高自動測試圖樣生成演算法之效能以及其實作範例
論文名稱(外文):D-Drive History Tree to Enhance ATPG Efficiency and its Implementation Examples
指導教授:黃俊郎黃俊郎引用關係
指導教授(外文):Jiun-Lang Huang
口試日期:2017-07-24
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電子工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2017
畢業學年度:105
語文別:英文
論文頁數:57
中文關鍵詞:決策樹錯誤驅動回溯修正測試壓縮路徑導向決策演算法自動化測試圖樣產生
外文關鍵詞:decision treeD-drivebacktracktest compactionPODEMtest pattern generation
相關次數:
  • 被引用被引用:0
  • 點閱點閱:182
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
西元一九六六年,自動化測試圖樣產生演算法的始祖—錯誤效應演算法(D-Algorithm)首次發表。自此,大量的研究成果隨之而來,並在演算法加速以及產生圖樣品質上取得巨大的成果。即便如此,在演算法加速以及測試品質上仍存有許多進步空間 。
我們提出錯誤效應驅動決策樹以取代傳統算法中的決策樹。其紀錄每一次錯誤驅動(D-drive)程序中候選以及選中以傳遞錯誤效應之邏輯閘。該決策樹有助於減少測試圖樣產生過程中衍生多餘的邏輯值指定(Redundant Signal Assignment),並提供更精細錯誤驅動策略的可能性。這意味著更好的算法加速以及測試圖樣品質。於本論文中,我們提供兩個基於錯誤效應驅動決策樹的實作範例—深度優先 (DF-PODEM)以及錯誤效應傳播最大化之路徑導向決策演算法(PM-PODEM)。前者達到最高32%之演算法加速,而後者達到最高11%之測試圖樣壓縮率。根據實驗結果,兩個測試圖樣產生演算法皆提供更好的算法加速、測試涵蓋率(Test Coverage)、以及測試圖樣壓縮率。
值得注意的是,錯誤效應驅動決策樹相當易於整合至現有各式自動化測試圖樣系統,同時也易於擴展以達到更好的算法加速以及針對各式品質指標的測試圖樣品質優化。
Since the first publication of D-algorithm (DALG) in 1966, lots of following works on automatic test pattern generation (ATPG) algorithm have been proposed to achieve higher speed-up and quality of generated test set. Though big progress has been made through decades, it still has lots of room for improvement in speed-up and generated test quality of ATPG.
In this thesis, we propose D-drive History Tree (D-Tree) to replace the assignment decision tree in the conventional ATPG, which keeping track of all the candidates and the chosen gate(s) to propagate fault effect for each D-drive process. This D-tree helps eliminate the possibility of producing redundant signal assignments (RSAs) and makes more sophistical D-drive strategies possible, thus enhance the ATPG efficiency and/or the test quality. Two implementation examples based on PODEM algorithm—Depth-First PODEM (DF-PODEM) and Propagation Maximization PODEM (PM-PODEM) are proposed to show its power to immediate boost both performance and/or pattern quality of ATPG. DF-PODEM turns out to achieve up to 32% speed-up, along with higher fault coverage and/or compacted test length, on ISCAS''89 and ITC''99 benchmark circuits. PM-PODEM achieve up to 11% shorter test length, along with higher fault coverage and/or lower run-time, on the same set of circuits under test (CUT).
Also, as to be shown, D-tree could not only easily be integrated with pre-existed ATPG-improving strategies, but also quite flexible thus could easily be extended to gain even higher speed-up and higher quality specifically for different quality metrics.
口試委員會審定書#
誌謝i
中文摘要ii
ABSTRACTiii
CONTENTSiv
LIST OF FIGURESvii
LIST OF TABLESix
Chapter 1Introduction1
1.1Motivation1
1.1.1Importance of ATPG in VLSI Design Flow1
1.1.2On improving ATPG System2
1.2Previous Work3
1.2.1On the acceleration of TPG process3
1.2.2On enhancing test compactness5
1.3Organizations of the Thesis6
Chapter 2Preliminaries8
2.15-Valued Logic System8
2.2Automatic Test Pattern Generation10
2.2.1TPG stage11
2.2.2Dynamic compaction stage12
2.2.3Static compaction stage13
2.2.4Preprocessing stage13
2.3D-Drive13
2.4Redundant Signal Assignment14
2.4.1Scenario I: Justification-induced RSAs15
2.4.2Scenario II: D-drive-induced RSAs16
2.4.3Scenario III: Backtrack-induced RSAs17
2.5Objectives18
2.5.1Necessary objectives19
2.5.2Benefit on justifying multiple objectives20
Chapter 3D-Drive History Tree22
3.1D-tree23
3.1.1Data Structure23
3.1.2Basic Operations25
3.1.3On avoiding RSA27
3.2D*-Tree27
3.2.1Date Structure29
3.2.2Basic Operation30
Chapter 4Proposed ATPG33
4.1Depth-first PODEM33
4.1.1Depth-first D-drive candidate derivation33
4.1.2Completeness of DF-PODEM35
4.1.3DF-PODEM Example38
4.2Propagation Maximization PODEM41
4.2.1Objective derivation for Multiple D-drive41
4.2.2PM-PODEM Example44
Chapter 5Experiment Result46
Experimental Results for DF-PODEM47
5.147
5.1.1Results on Hard-to-detect faults48
5.2Experimental Results for PM-PODEM49
Chapter 6Conclusion53
REFERENCE54

J. P. Roth, “Diagnosis of Automata Failures: A Calculus and a Method,” IBM Journal of Research and Development, vol. 10, no. 4, pp. 278–291, July 1966.
P. Goel, "An implicit enumeration algorithm to generate tests for combinational logic circuits", IEEE Trans. Comput., vol. C-30, pp. 215-222, Mar. 1981.
H. Fujiwara and T. Shimono, "On the Acceleration of Test Generation Algorithms," in IEEE Transactions on Computers, vol. C-32, no. 12, pp. 1137-1144, Dec. 1983.
M. H. Schulz, E. Trischler, and T. M. Sarfert, "SOCRATES: A highly efficient automatic test pattern generation system," IEEE Transactions on Computer-Aided Design, vol. 7, no. I, pp. 126-137, January 1988.
U. Mahlstedt, T. Grüning, C. Özcan, and W. Daehn, “CONTEST: A Fast ATPG Tool for Very Large Combinational Circuits,” International Conference on Computer-Aided Design, pp. 222-225, 1990.
Rajski and H. Cox, "A method to calculate necessary assignments in algorithmic test pattern generation," in Proc. International Test Conference, pp. 25-34, 1990.
W. Kunz and D. K. Pradhan, “Accelerated Dynamic Learning for Test Generation in Combinational Circuits,” IEEE Transactions on Computer-Aided Design, vol. 12, no. 5, pp. 684-694, 1993.
W. Kunz and D. K. Pradhan, “Recursive Learning: A new implication technique for efficient solutions to CAD problems – Test, Verification and Optimization,” IEEE Transactions on Computer-Aided Design, vol. 13, no. 9, pp. 1143-1158, 1994.
J.P. Marques-Silva and K.A. Sakallah, “Dynamic Search-Space Pruning Techniques in Path Sensitization,” Design Automation Conference, pp. 705-711, 1994.
S. Bommu, K. Chandrasekar, R. Kundu, and S. Sengupta, “CONCAT: CONflict Driven Learning in ATPG for Industrial designs,” International Test Conference, pp. 1-10, 2008.
L. Xin, “Speeding-up Test Pattern Generation by Means of Heuristic Learning,” Industrial and Information Systems (IIS), pp. 269-272, 2010.
W. Kunz and D. Pradhan, “Recursive Learning: An Attractive Alternative to the Decision Tree for Test Generation in Digital Circuits,” International Test Conference, pp. 816-825, 1992.
D. Tille, S. Eggersgluss, R. Krenz-Baath, J. Schloeffel, R. Drechsler, “Improving CNF representations in SAT-based ATPG for industrial circuits using BDDs,” European Test Symposium, pp.176-181, 2010.
K. Chandrasekar and M. S. Hsiao, “Decision Selection and Learning for an ‘all-solutions ATPG engine’,” International Test Conference, pp. 607-616, 2004.
M. H. Schulz and E. Auth, “Improved Deterministic Test Pattern Generation with Applications to Redundancy Identification,” IEEE Transactions on Computer-Aided Design, vol. 8, no. 7, pp. 811-816, 1989.
I. Hamzaoghr and J. H. PateI, “New Techniques for Deterministic Test Pattern Generation,” IEEE VLSI Test Symposium, pp. 446-452, 1998.
J. H. Pan, K. W. Yeh and J. L. Huang, "A static bidirectional learning technique to accelerate test pattern generation," 2015 International SoC Design Conference (ISOCC), Gyungju, 2015, pp. 45-46.
X. Cai, P. Wohl, J.A. Waicukauski and P. Notiyath, “Highly efficient parallel ATPG based on shared memory,” International Test Conference, pp. 1-7, 2010.
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, pp. 530-537, 2000.
J. M. Wolf, L. M. Kaufman, R. H. Klenke, J. H. Taylor, and R. Waxman, “An analysis of fault partitioned parallel test generation,” IEEE Transactions on Computer-Aided Design, vol. 15, no. 5, pp. 517-534, 1996.
S. Chandra, J.H. Patel, “Test generation in a parallel processing environment,” International Conference on Computer Design, pp. 11-14, 1988.
S. Patil and P. Banerjee, “A Parallel Branch-and-Bound Algorithm for Test Generation”, Design Automation Conference, pp. 339-334, 1989.
Consolacion Gil, Julio Ortega, “Parallel Test Generation Using Circuit Partitioning and Spectral Techniques”, Euromicro Workshop on Parallel and Distributed Processing, pp. 264-270, 1998.
S. Hadjitheophanous, S. N. Neophytou and M. K. Michael, "Utilizing shared memory multi-cores to speed-up the ATPG process," 2016 21th IEEE European Test Symposium (ETS), Amsterdam, 2016, pp. 1-6.
P. Goel B. C. Rosales "PODEM-X: An automatic test generation system for VLSI logic structures" Proc. 18th Design Automation Conf. pp. 260-268 1981. 
S. B. Akers "on the role of independent fault sets in the generation of minimal test sets" 1987 Int. Test Conf. pp. 1100-1107 1987-Aug. 
I. Pomeranz, L. N. Reddy and S. M. Reddy, "COMPACTEST: a method to generate compact test sets for combinational circuits," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 7, pp. 1040-1049, Jul 1993.
J. F. McDonald C. Benmehrez "Test set reduction using the subscripted D-Algorithm" 1983 Int. Test Conf. pp. 115-121 1983-Aug. 
A. F. Yousif and Jun Gu, "Concurrent automatic test pattern generation algorithm for combinational circuits," Computer Design: VLSI in Computers and Processors, 1995. ICCD ''95. Proceedings., 1995 IEEE International Conference on, Austin, TX, 1995, pp. 286-291.
S. Eggersglü, R.Wille, and R. Drechsler, "Improved SAT-based ATPG: More constraints, better compaction," in International Conference on Computer-Aided Design, 2013, pp. 85-90.
S. Eggersglüb, K. Schmitz, R. Krenz-Bååth and R. Drechsler, "Optimization-based multiple target test generation for highly compacted test sets," 2014 19th IEEE European Test Symposium (ETS), Paderborn, 2014, pp. 1-6.
B. Davis, The Economics of Automatic Testing, McGraw-Hill, London, UK, 1982
O. H. Ibarra and S. K. Sahni, “Polynomially complete fault detection problems,” IEEE Transactions on Computer-Aided Design, vol. 24, no. 3, pp. 242-249, 1975.
Krishnaswamy, A. B. Ma and P. Vishakantaiah, "A study of bridging defect probabilities on a Pentium (TM) 4 CPU," International Test Conference, pp. 688-695, 2001.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top