請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43465
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 黃俊郎 | |
dc.contributor.author | Chun-Hao Chang | en |
dc.contributor.author | 張峻豪 | zh_TW |
dc.date.accessioned | 2021-06-15T02:22:03Z | - |
dc.date.available | 2013-08-26 | |
dc.date.copyright | 2011-08-26 | |
dc.date.issued | 2011 | |
dc.date.submitted | 2011-08-17 | |
dc.identifier.citation | [1] R. Bocchino, V. Adve, S. Adve, and M. Snir, “Parallel programming must be deterministic by default”, Technical Report UIUCDCS-R-2008-3012, University of Illinois at Urbana-Champaign, 2008.
[2] E. A. Lee, The problem with threads, Computer, 2006. [3] P. Goel, “An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits”, IEEE Transactions on Computers, vol. 30, no. 3, pp. 676-683, March 1981. [4] H. Fujiwara and T. Shimono, “On the Acceleration of Test Generation Algorithms“, Proc. Int’l Fault-Tolerance Computing Symp., pp.98-105, 1983. [5] J. P. Roth, “Diagnosis of Automata Failures: A Calculus and a Method,” IBM Journal of Research and Development, vol. 10, no. 4, pp278-291, 1966. [6] X. Cai, P. Wohl, J.A. Waicukauski and P. Notiyath, “Highly efficient parallel ATPG based on shared memory”, International Test Conference, 2010. [7] J. M. Wolf, L. M. Kaufman, R. H. Klenke, J. H. Aylor, and R. Waxman, “An analysis of fault partitioned parallel test generation”, IEEE Transactions on Computer-Aided Design, 15(5):517–534, May 1996. [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”, International Test Conference, pages 530–537, 2000. [9] S. Chandra, J.H. Patel, “Test generation in a parallel processing environment,” Proc. Int. Conf. Computer Design, Oct. 1988.. [10] S. Patil and P. Banerjee, “A Parallel Branch-and-Bound Algorithm for Test Generation”, Proc. 26th ACMI/IEEE Design Automation Conf., CS Press, Los Alamitos, Calif., June 1989, pp. 339-334. [11] Consolacion Gil, Julio Ortega, “Parallel Test Generation Using Circuit Partitioning and Spectral Techniques”, Proceedings of the Sixth Euromicro Workshop on Parallel and Distributed Processing, 1998. [12] Tian Tian, Chiu-Pi Shih, “Software Techniques for Shared-Cache Multi-Core Systems”, http://software.intel.com/en-us/articles, 2011 [13] J. A. Waicukauski, E. B. Eichielberger, D. O. Forlenza, E. Lindbloom and T. McCarthy, 'Fault Simulation for Structured VLSI', VLSI Systems Design, Vol. 6, No. 12, pp. 20-32, Dec. 1985. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43465 | - |
dc.description.abstract | 本論文提出一個基於共享記憶體多核心處理器系統下,使用錯誤分配概念之平行化測試圖樣產生器,不同於之前所提出的方法 [6, 7, 8],我們消除了平行執行時所產生圖樣數量膨脹的問題,我們所提出的平行化測試圖樣產生器,能夠產生具確定性且無任何圖樣數量膨脹的結果,此外我們產生出的結果不因使用的核心個數而改變,使得平行化測試圖樣產生器更容易驗證其正確性,在我們的測試實驗中,大部分的電路 (s35932, s38417, s38584, b15s, b17s, D1, D2) 都可以使用我們的方法得到良好的加速 (3.5x ~ 9.6x 在使用8 cores的環境下)。 | zh_TW |
dc.description.abstract | This thesis proposed a new fault partitioning parallel ATPG for shared-memory multi-core systems. Based on a pipelined fault processing principle and process synchronization, the proposed ATPG introduces no test inflation and achieves high parallelism. Furthermore, the returned test set is deterministic, even with respect to the number of utilized CPU cores; this simplifies the debugging process. Experimental results show that it achieves good speedup (3.5x ~ 9.6x with 8 cores) on the benchmarks circuits (s35932, s38417, s38584, b15s, b17s, D1, D2). | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T02:22:03Z (GMT). No. of bitstreams: 1 ntu-100-R98943082-1.pdf: 982769 bytes, checksum: 6f08809252211e3a8c057d501e36110f (MD5) Previous issue date: 2011 | en |
dc.description.tableofcontents | 口試委員會審定書 i
誌謝 ii 中文摘要 iii Abstract iv Table of Contents v List of Figures viii List of Tables x Chapter 1 Introduction 11 Chapter 2 Preliminaries 13 2.1. Determinism 13 2.2. Typical Serial ATPG 15 2.2.1 Generation Phase 16 2.2.2 Dynamic Compaction Phase 17 2.2.3 Fault Simulation Phase 18 2.3. Shared-Memory Multi-Core Systems 19 2.3.1 Shared Cache Architecture 20 2.3.2 False Sharing 20 Chapter 3 A Study of Parallel ATPG Methodologies 23 3.1. Fault Partitioning 23 3.2. Heuristic Partitioning 24 3.3. Search Space Partitioning 25 3.4. Circuit Partitioning 25 Chapter 4 Proposed Parallel ATPG Methodology 27 4.1. Proposed Deterministic Parallel ATPG 27 4.1.1 Zero pattern count inflation 27 4.1.2 Flowchart 29 4.2. Concept of Parallelism and Determinism 30 4.2.1 Generation Phase 31 4.2.2 Dynamic Compaction Phase 32 4.2.3 Fault Simulation Phase 34 4.3. Implementation 35 4.3.1 Hardware Friendly Data Structure 35 4.3.2 Synchronous Variables 36 4.3.3 Generation Phase 39 4.3.4 Confirmed Fault Selection 41 4.3.5 Dynamic Compaction Phase 45 4.3.6 Fault Simulation Phase 47 Chapter 5 Experimental Results 50 5.1. Speedup 51 5.2. Idle Ratio 53 5.3. Run Time Overhead 54 5.4. Physical Memory Overhead 56 5.5. Determinism 57 Chapter 6 Discussion 58 6.1. Super-Linear Speedup 58 6.2. Non-Deterministic Parallel ATPG 60 6.2.1 Speedup 61 6.2.2 Pattern count inflation 63 6.3. Fault List Order 64 Chapter 7 Conclusions 66 Bibliography 67 | |
dc.language.iso | en | |
dc.title | 基於共享記憶體多核心系統上具確定性之平行化自動測試圖樣產生技術 | zh_TW |
dc.title | A Deterministic Parallel ATPG for Shared-Memory Multi-Core Systems | en |
dc.type | Thesis | |
dc.date.schoolyear | 99-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 李建模,王行健,劉靖家,溫宏斌 | |
dc.subject.keyword | 自動測試圖樣產生技術,平行計算,確定性平行化程式, | zh_TW |
dc.subject.keyword | automatic test pattern generation,parallel computing,deterministic parallel program, | en |
dc.relation.page | 68 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2011-08-17 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-100-1.pdf 目前未授權公開取用 | 959.74 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。