A Communication Overhead and Load Balanced Awarearallel ATPG

自動化圖樣產生技術是個已知複雜度為NP 的問題。為了要縮短測試圖樣的生時間，有很多技術被提出來加快自動化產生圖樣技術。本篇論文提出一個可行執行的自動化圖樣產生技術，目標在加快自動化產生圖樣技術。平行化圖樣產生技術採用多處理器的架構，將產生圖樣的工作平均分給各處理器，平行產生測試圖樣。此外，考慮平行化圖樣產生技術可能造成的問題，先，為了減少潛在性的測試圖樣膨脹，本論文提出一個改良式工作分配演算。除此之外，為了降低溝通費用，本論文採用主僕式訊息溝通架構，簡化溝通複雜度。實驗中使用ISCAS89、 ITC99 和一個業界電路驗證此技術能夠有效短圖樣產生時間。Automatic test pattern generation is known to be an NP hard problem. To solveuch a time-consuming problem, many techniques have been proposed to speed upTPG (automatic test pattern generation) engines. This thesis proposes a parallelTPG methodology to speed up test generation process.he proposed methodology distributes the overall fault list among N processorsnd each processor generates test patterns for its own fault list. We call this approachs static fault partitioning. The main considerations of fault partitioned ATPG withistributed memories include keeping low communication overhead and avoiding testattern inflation. To avoid test pattern inflation, an efficient static fault partitioninglgorithm is proposed. On the other hand, to reduce inter-process communicationverhead, the mater-slave architecture is adopted and a smart dynamic load balancingechnique is also proposed.he proposed technique is validated using ISCAS89, ITC99 benchmark circuitsnd a modern industry design.口試委員會審定書 i謝 ii文摘要 iiibstract ivable of Contents vist of Figures viiiist of Tables ixhapter 1 Introduction 10hapter 2 Preliminaries 12.1. Typical ATPG Flow 12.2. Performance Analysis of Parallel Implementation 13.3. Parallel Processing Architecture 14.3.1. Share-Memory Systems 14.3.2. Message Passing Systems 15hapter 3 A Study of Parallel and Distributed ATPG Methodologies 17.1. Introduction 17.2. Prior Works in Parallel and Distributed ATPG Methodologies 17.2.1. Fault Parallelism 17.3.2. Search Space Parallelism 20.3.3. Heuristic Parallelism 22.3.4. Circuit Partitioning 24hapter 4 Proposed Distributed ATPG Methodology 26.1. Introduction 26.2. Master-Slave Architecture 27.3. Static Fault Partitioning 28.3.1. Motivation 28.3.2. The Improved Fault Partition Partitioning 29.3.3. Analysis of Improved Static Fault Partitioning 34.4. Parallel Test Pattern Generation Algorithm 35.4.1. The Slave Process 35.4.2. The Master Process 37.4.3. Dynamic Load Balance 38hapter 5 Experimental Results 40.1. Test Generation Results with Single Processor 40.2. Parallel Test Generation vs. Serial Test Generation 41.3. Proposed Fault Partitioning vs. Conventional Fault Partitioning 43hapter 6 Conclusions 46ibliography 4