請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46273完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 王凡(Farn Wang) | |
| dc.contributor.author | Guan-Cheng Chen | en |
| dc.contributor.author | 陳冠成 | zh_TW |
| dc.date.accessioned | 2021-06-15T05:01:06Z | - |
| dc.date.available | 2010-08-02 | |
| dc.date.copyright | 2010-08-02 | |
| dc.date.issued | 2010 | |
| dc.date.submitted | 2010-07-27 | |
| dc.identifier.citation | [1] The openmp architecture review board. http://openmp.org/wp/about-openmp/.
[2] S. V. Adve, M. D. Hill, B. P. Miller, and R. H. B. Netzer. Detecting data races on weak memory systems. In ISCA, pages 234–243, 1991. [3] V. Balasundaram and K. Kennedy. Compile-time detection of race conditions in a parallel program. In ICS, pages 175–185, 1989. [4] R. Brown and I. Sharapov. High-scalability parallelization of a molecular modeling application: Performance and productivity comparison between openmp and mpi implementations. International Journal of Parallel Programming, 35(5):441–458, 2007. [5] J.-D. Choi and S. L. Min. Race frontier: Reproducing data races in parallel-program debugging. In PPOPP, pages 145–154, 1991. [6] M. Christiaens and K. De Bosschere. Trade, a topological approach to on-the-fly race detection in java programs. In JVM’01: Proceedings of the 2001 Symposium on JavaTM Virtual Machine Research and Technology Symposium, pages 15–15, Berkeley, CA, USA, 2001. USENIX Association. [7] R. Hood, K. Kennedy, and J. M. Mellor-Crummey. Parallel program debugging with on-the-fly anomaly detection. In SC, pages 74–81, 1990. [8] A. Jannesari and W. F. Tichy. On-the-fly race detection in multi-threaded programs. In PADTAD ’08: Proceedings of the 6th workshop on Parallel and distributed systems, pages 1–10, New York, NY, USA, 2008. ACM. [9] V. Kahlon and C. Wang. Universal causality graphs: A precise happens-before model for detecting bugs in concurrent programs. 2010. [10] G. Krawezik and F. Cappello. Performance comparison of mpi and openmp on shared memory multiprocessors. Concurrency and Computation: Practice and Experience, 18(1):29–61, 2006. [11] B. Kuhn, P. Petersen, and E. O’Toole. Openmp versus threading in c/c++. Concurrency - Practice and Experience, 12(12):1165–1176, 2000. [12] A. Lal and T. W. Reps. Reducing concurrent analysis under a context bound to sequential analysis. In A. Gupta and S. Malik, editors, CAV, volume 5123 of Lecture Notes in Computer Science, pages 37–51. Springer, 2008. [13] L. Lamport. Time, clocks, and the ordering of events. Communications of the ACM, 21(7):558–565, July 1978. [14] Z. Letko, T. Vojnar, and B. Kˇrena. Atomrace: data race and atomicity violation detector and healer. In PADTAD ’08: Proceedings of the 6th workshop on Parallel and distributed systems, pages 1–10, New York, NY, USA, 2008. ACM. [15] M. Musuvathi. Systematic concurrency testing using chess. In S. Ur, editor, PADTAD, page 10. ACM, 2008. [16] M. Musuvathi and S. Qadeer. Chess: Systematic stress testing of concurrent software. In G. Puebla, editor, LOPSTR, volume 4407 of Lecture Notes in Computer Science, pages 15–16. Springer, 2006. [17] R. H. B. Netzer and B. P. Miller. Improving the accuracy of data race detection. In PPOPP, pages 133–144, 1991. [18] R. H. B. Netzer and B. P. Miller. What are race conditions? some issues and formalizations. LOPLAS, 1(1):74–88, 1992. [19] R. O’Callahan and J.-D. Choi. Hybrid dynamic data race detection. SIGPLAN Not., 38(10):167–178, 2003. [20] E. Pozniansky and A. Schuster. Efficient on-the-fly data race detection in multithreaded c++ programs. SIGPLAN Not., 38(10):179–190, 2003. [21] S. Qadeer and J. Rehof. Context-bounded model checking of concurrent software. In In TACAS, pages 93–107. Springer, 2005. [22] A. Strey. A comparison of openmp and mpi for neural network simulations on a sunfire 6800. In G. R. Joubert, W. E. Nagel, F. J. Peters, and W. V. Walter, editors, PARCO, volume 13 of Advances in Parallel Computing, pages 201–208. Elsevier, 2003. [23] R. N. Taylor. A general-purpose algorithm for analyzing concurrent programs. Commun. ACM, 26(5):362–376, 1983. [24] F. Wang. Redlib. http://sourceforge.net/projects/redlib/. [25] F. Wang. Redlib for the formal verification of embedded systems. In ISOLA ’06: Proceedings of the Second International Symposium on Leveraging Applications of Formal Methods, Verification and Validation, pages 341–346, Washington, DC, USA, 2006. IEEE Computer Society. [26] Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: efficient detection of data race conditions via adaptive tracking. In SOSP ’05: Proceedings of the twentieth ACM symposium on Operating systems principles, pages 221–234, New York, NY, USA, 2005. ACM. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46273 | - |
| dc.description.abstract | 多執行緒程式靠著額外的執行緒在多核心的系統上進行平行運算可以加速計算的進行。由於多執行緒程式有著競賽情況的隱憂，為了保證多執行緒系統的正確性，如何避免資料發生競賽情況是很重要的。
我們在這篇論文中提出了一個以模型為基礎的測試流程。我們用了自己定義的模型產生技術來為多執行緒的系統建立相對應的模型。然後我們會在模型模擬器上測試我們的模型。在模擬過程中，我們設計了一個選擇執行程序的策略來導致資料發生競賽情況。在潛在的競賽情況被發現之後，我們接著分析產生競賽情況模型的程式執行序列。分析的結果會產生對競賽情況有高風險的變數，接著我們會去保護這些變數。我們會找出這些應該被分別存取的變數，然後重新測試，我們就可以定位出程式中的錯誤，然後提出一個建議給程式使用者。 | zh_TW |
| dc.description.abstract | Multi-threaded programming speeds computation up by executing threads in parallel on multi-core. Preventing data race conditions is important to guarantee the correctness of multi-threaded systems. A model-based testing technique for race conditions is proposed in this paper. We construct models for multi-threaded systems in OpenMP with techniques. Then we run test with our strategy on the models with a model simulator. A process execution strategy is designed for inducing data race in simulations. After the potential race condition detected, we will do fault localization by analyzing the execution sequence first. After analyzing, we will protect those chosen variables one at a time. After protecting variables and running tests again, we will localize the fault in original program. Then we can give a suggestion to the program user. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T05:01:06Z (GMT). No. of bitstreams: 1 ntu-99-R97943151-1.pdf: 4760137 bytes, checksum: 252b58a44fb341e5e0186b89aaaaccfb (MD5) Previous issue date: 2010 | en |
| dc.description.tableofcontents | 口試委員會審定書i
誌謝iii 中文摘要v Abstract vii 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Research Goal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5 Thesis Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Background 5 2.1 OpenMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Race Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Model Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Model Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8 2.4.1 Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8 2.4.2 Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9 2.4.3 Variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9 3 Model Construction 13 3.1 Basic Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Strategy to OpenMP Schedule . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.1 dynamic scheduling . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.2 static scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Strategy to OpenMP Reduction . . . . . . . . . . . . . . . . . . . . . . . 19 4 Race Detection 23 4.1 Execution Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 Golden Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.3 Trace Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.4 Input Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.5 Switch Bound Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.6 Score Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5 Fault Localization 33 5.1 Variable Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.2 Risky Variable Protection . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6 Implementation 39 7 Experiments and Results 43 7.1 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 7.2 Results of Race Detection . . . . . . . . . . . . . . . . . . . . . . . . . . 43 7.3 Results of Fault Localization . . . . . . . . . . . . . . . . . . . . . . . . 47 8 Conclution and FutureWork 51 | |
| dc.language.iso | en | |
| dc.title | 平行程式之競賽情況偵測與錯誤定位 | zh_TW |
| dc.title | Race Detection and Fault Localization of Multi-threaded Programs | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 98-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳俊壯(Chun-Chuang Chen),黃鐘揚(Chung-Yang Huang),雷欽隆(Chin-Laung Lei),陳郁方(Yu-Fang Chen) | |
| dc.subject.keyword | 競賽情況偵測,OpenMP,錯誤定位,多執行緒程式, | zh_TW |
| dc.subject.keyword | race detection,OpenMP,fault localization,multi-threaded program, | en |
| dc.relation.page | 58 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2010-07-28 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
| 顯示於系所單位： | 電子工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-99-1.pdf 目前未授權公開取用 | 4.65 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。