跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/07/28 14:47
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:潘俊翰
研究生(外文):Jiun-Han Pan
論文名稱:靜態學習之改進及其在路徑導向決策演算法的應用
論文名稱(外文):Improved Static Learning and Its Application to PODEM
指導教授:黃俊郎黃俊郎引用關係
指導教授(外文):Jiun-Lang Huang
口試委員:呂學坤溫宏斌
口試委員(外文):Shyue-Kung LuHung-Pin Wen
口試日期:2015-07-30
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電子工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:60
中文關鍵詞:路徑導向決策演算法蘊含學習自動化測試圖樣產生技術加速測試效率
外文關鍵詞:PODEMimplication learningspeed-uptest efficiency
相關次數:
  • 被引用被引用:0
  • 點閱點閱:80
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
由於製程技術的演進以及錯誤模型的增加,自動化測試圖樣產生技術的加速一直都是一個很重要的議題。雖然在過去有許多利用學習的加速技術被提出來縮短測試圖樣的產生時間,然而大部份的技術都是應用於D演算法,較少套用在路徑導向決策演算法(PODEM)上。
本篇論文提出一個以靜態學習改進的學習演算法: 雙向蘊含學習法 (bidirec-tional implication learning),此學習法相較於原本的靜態學習可以找到更多會導致邏輯矛盾的條件,並嘗試將此學習流程套用在路徑導向決策演算法上以達到加速的目的。
實驗中使用ISCAS89, ITC99中的大電路以及兩個業界電路來驗證此技術,而從實驗結果可以觀察出在測試圖樣產生的過程中,回溯修正(backtrack)的次數能有效的降低並能縮短圖樣產生的時間。相較於原本的決策演算法,此技術平均可以降低62%的運算時間。


Reducing the automatic test pattern generation (ATPG) time is a crucial issue due to the increasing design complexity and the shrinking device feature sizes – more transistors to test and more fault models to cover. Although several learning-based ATPG acceleration techniques have been proposed, most of them are not applicable to PODEM.
In this thesis we first propose an improved static learning technique called bidirec-tional implication learning. This improved learning technique can explore more necessary assignments in a circuit. Next we apply this technique to PODEM in order to avoid con-flicts; this reduces useless backtracks in sub search space that has no solution and thus speed up the test generation process.
The proposed techniques are validated using ISCAS89, ITC99 benchmark circuits and 2 modern industry designs. The experiment results show that the required back-tracks are significantly reduced and the average runtime reduction is 62%.


口試委員會審定書 #
誌謝 i
中文摘要 ii
ABSTRACT iii
TABLE OF CONTENTS iv
LIST OF FIGURES vi
LIST OF TABLES viii
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Previous Works 1
1.3 Organization of the Thesis 4
Chapter 2 Preliminaries 5
2.1 Fault Model 5
2.1.1 Stuck-at fault model 5
2.1.2 Fault Collapsing 6
2.2 Automatic Test Pattern Generation 7
2.2.1 Generation Phase 8
2.2.2 Dynamic Compaction Phase 9
2.2.3 Fault Simulation Phase 9
2.2.4 Path-Oriented Decision Making (PODEM) 10
2.3 Unique Path Sensitization 12
Chapter 3 A Study of Learning-based ATPG Methodologies 13
3.1 Introduction 13
3.2 Static Learning 13
3.3 Dynamic Learning 17
3.4 SAT-based learning 18
Chapter 4 Proposed Learning-based PODEM 19
4.1 Bidirectional Implication Learning 19
4.1.1 Motivation 19
4.1.2 Flowchart 21
4.1.3 Backward Implication and Learning Criteria 22
4.2 Learning-based PODEM 26
4.2.1 Motivation 26
4.2.2 Learning-based Fault Activation 27
4.2.3 Learning-based Fault Propagation 30
Chapter 5 Experiment Results 34
5.1 Static Learning vs. Bidirectional Implication Learning 35
5.2 Backtrack Reduction 36
5.2.1 Single-fault Test Generation 36
5.2.2 The Influence of Implied Objectives’ Ordering 40
5.3 Speed-up 41
Chapter 6 Conclusions 47
REFERENCE 48


[1] J. P. Roth, “Diagnosis of Automata Failures: A Calculus and a Method,” IBM Jour-
nal of Research and Development, vol. 10, no. 4, pp. 278-291, 1966.
[2] P. Goel, “An Implicit Enumeration Algorithm to Generate Tests for Combinational
Logic Circuits,” IEEE Transactions on Computers, vol. 30, no. 3, pp. 676-683, 1981.
[3] H. Fujiwara and T. Shimono, “On the Acceleration of Test Generation Algo-
rithms,“ IEEE Transactions on Computers, vol. 32, no. 12, pp. 98-105, 1983.
[4] 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.
[5] R. Butler, B. Keller, S. Paliwal, R. Scchoonover, and J. Swenton, “Design and im-
plementation of a parallel automatic test pattern generation algorithm with low test
vector count,” International Test Conference, pp. 530-537, 2000.
[6] J. M. Wolf, L. M. Kaufman, R. H. Klenke, J. H. Taylor, and R. Waxman, “An anal-
ysis of fault partitioned parallel test generation,” IEEE Transactions on Computer-
Aided Design, vol. 15, no. 5, pp. 517-534, 1996.
[7] M. Schulz, E. Trischler and T. Sarfert, “SOCRATES: A highly efficient automatic
test pattern generation system,” International Test Conference, pp. 1016-1026, 1987.
[8] 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.
[9] J. Rajski and H. Cox, “A Method to Calculate Necessary Assignments in Algorith-
mic Test Pattern Generation,” International Test Conference, pp. 25-34, 1990.
[10] 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.
[11] 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.
[12] J.P. Marques-Silva and K.A. Sakallah, “Dynamic Search-Space Pruning Tech-
niques in Path Sensitization,” Design Automation Conference, pp. 705-711, 1994.
[13] 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.
[14] L. Xin, “Speeding-up Test Pattern Generation by Means of Heuristic Learning,” I-
ndustrial and Information Systems (IIS), pp. 269-272, 2010.
[15] S. Chandra, J.H. Patel, “Test generation in a parallel processing environment,”
International Conference on Computer Design, pp. 11-14, 1988.
[16] S. Patil and P. Banerjee, “A Parallel Branch-and-Bound Algorithm for Test Gene-ra-
tion”, Design Automation Conference, pp. 339-334, 1989.

[17] Consolacion Gil, Julio Ortega, “Parallel Test Generation Using Circuit Partitioning
and Spectral Techniques”, Euromicro Workshop on Parallel and Distributed Pro
cessing, pp. 264-270, 1998.
[18] M. Abramovici, J. J. Kulikowski, P. R. Menon, and D. T. Miller, “SMART and
FAST: Test generation for VLSl scan-design circuits,” IEEE Design & Test, vol. 3, no. 4, pp. 43-54, 1986.
[19] E. Trischler, “ATWIG, An automatic test pattern generator with inherent guid-ance,”
International Test Conference, pp. 80-87, 1984.
[20] 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.
[21] W. Kunz and D. Pradhan, “Recursive Learning: An Attractive Alternative to the
Decision Tree for Test Generation in Digital Circuits,” International Test Confer-
ence, pp. 816-825, 1992.
[22] D. Tille, S. Eggersgluss, R. Krenz-Baath, J. Schloeffel, R. Drechsler, “Improving
CNF representations in SAT-based ATPG for industrial circuits using BDDs,” Eu
ropean Test Symposium, pp.176-181, 2010.
[23] K. Chandrasekar and M. S. Hsiao, “Decision Selection and Learning for an ‘all-
solutions ATPG engine’,” International Test Conference, pp. 607-616, 2004.
[24] 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.
[25] I. Hamzaoghr and J. H. PateI, “New Techniques for Deterministic Test Pattern
Generation,” IEEE VLSI Test Symposium, pp. 446-452, 1998.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文