請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46932
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 廖世偉(Shih-Wei Liao) | |
dc.contributor.author | Jia-Zon Chang | en |
dc.contributor.author | 張家榮 | zh_TW |
dc.date.accessioned | 2021-06-15T05:43:33Z | - |
dc.date.available | 2020-08-19 | |
dc.date.copyright | 2010-08-20 | |
dc.date.issued | 2010 | |
dc.date.submitted | 2010-08-20 | |
dc.identifier.citation | [1] DragonEgg - Using LLVM as a GCC backend. http://dragonegg.llvm.org/, 2009.
[2] LLVMBitcodeFileFormat.http://llvm.org/docs/BitCodeFormat.html, 2010. [3] LLVMLanguageReferenceManual.http://llvm.org/docs/LangRef.html, 2010. [4] Valgrind project. Helgrind: a thread error detector. http://valgrind.org/docs/manual/hg-manual.html, 2010. [5] S. Adve, M. Hill, B. Miller, and R. Netzer. Detecting data races on weak memory systems. ISCA ’91: Proceedings of the 18th annual international symposium on Computer architecture, Apr 1991. [6] R. Agarwal and S. Stoller. Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables. PADTAD ’06: Proceedings of the 2006 workshop on Parallel and distributed systems: testing and debugging, Jul 2006. [7] E. Ayguade ́, N. Copty, A. Duran, J. Hoeflinger, Y. Lin, F. Massaioli, X. Teruel, P. Unnikrishnan, and G. Zhang. The Design of OpenMP Tasks. IEEE Transactions on Parallel and Distributed Systems, 20(3):404–418, 2009. [8] D. Bailey. FFTs in external of hierarchical memory. Supercomputing ’89: Proceed- ings of the 1989 ACM/IEEE conference on Supercomputing, Aug 1989. [9] M.Bond,K.Coons,andK.McKinley.PACER:proportionaldetectionofdataraces. PLDI ’10: Proceedings of the 2010 ACM SIGPLAN conference on Programming language design and implementation, Jun 2010. [10] C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: pre- venting data races and deadlocks. OOPSLA ’02: Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, Nov 2002. [11] C. Boyapati and M. Rinard. A parameterized type system for race-free Java pro- grams. OOPSLA ’01: Proceedings of the 16th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, Nov 2001. [12] M. Burrows and K. R. M. Leino. Finding stale-value errors in concurrent pro- grams: Research Articles. Concurrency and Computation: Practice & Experience, 16(12):1161–1172, 2004. [13] G.-I. Cheng, M. Feng, C. Leiserson, K. Randall, and A. Stark. Detecting data races in Cilk programs that use locks. SPAA ’98: Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, Jun 1998. [14] J.-D. Choi, K. Lee, A. Loginov, R. O’Callahan, V. Sarkar, and M. Sridharan. Ef- ficient and precise datarace detection for multithreaded object-oriented programs. PLDI ’02: Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, Jun 2002. [15] J.-D. Choi, A. Loginov, and V. Sarkar. Static Datarace Analysis for Multithreaded Object-Oriented Programs. Jan 2001. [16] M. Christiaens and K. D. Bosschere. Accordion Clocks: Logical Clocks for Data Race Detection. Euro-Par 2001 Parallel Processing, 2150:494–503, 2001. [17] J. W. Cooley and J. W. Tukey. An Algorithm for the Machine Calculation of Com- plex Fourier Series. Mathematics of Computation, 19(90):297–301, 1965. [18] D. L. Detlefs, K. R. M. Leino, G. Nelson, and J. B. Saxe. Extended Static Checking. Dec 1998. [19] A. Dinning and E. Schonberg. An empirical comparison of monitoring algorithms for access anomaly detection. PPOPP ’90: Proceedings of the second ACM SIG- PLAN symposium on Principles & practice of parallel programming, Feb 1990. [20] T. Elmas, S. Qadeer, and S. Tasiran. Goldilocks: Efficiently Computing the Happens-Before Relation Using Locksets. Formal Approaches to Software Testing and Runtime Verification, 4262:193–208, Nov 2006. [21] D. Engler and K. Ashcraft. RacerX: effective, static detection of race conditions and deadlocks. SOSP ’03: Proceedings of the nineteenth ACM symposium on Operating systems principles, Dec 2003. [22] C. Flanagan and S. Freund. Type-based race detection for Java. PLDI ’00: Proceed- ings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, Aug 2000. [23] C. Flanagan and S. Freund. Atomizer: a dynamic atomicity checker for multi- threaded programs. POPL ’04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, Jan 2004. [24] C. Flanagan and S. Freund. FastTrack: efficient and precise dynamic race detection. PLDI ’09: Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, Jun 2009. [25] C. Flanagan and S. Freund. Adversarial memory for detecting destructive races. PLDI ’10: Proceedings of the 2010 ACM SIGPLAN conference on Programming language design and implementation, Jun 2010. [26] C. Flanagan and S. Freund. The RoadRunner Dynamic Analysis Framework for Concurrent Programs. PASTE ’10: Proceedings of the 9th ACM SIGPLAN- SIGSOFT workshop on Program analysis for software tools and engineering, Jun 2010. [27] C. Flanagan, S. Freund, and J. Yi. Velodrome: a sound and complete dynamic atomicity checker for multithreaded programs. PLDI ’08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, Jun 2008. [28] C. Flanagan and K. R. M. Leino. Houdini, an Annotation Assistant for ESC/Java. Proceedings of the International Symposium of Formal Methods Europe on Formal Methods for Increasing Software Productivity, 2021:500–517, 2001. [29] W. Gropp, E. Lusk, and A. Skjellum. Using MPI: portable parallel programming with the message-passing interface. MIT Press, page 307, 1994. [30] D. P. Helmbold and C. E. Mcdowell. A Taxonomy of Race Detection Algorithms. Sep 1994. [31] T.Henzinger,R.Jhala,andR.Majumdar.Racecheckingbycontextinference.PLDI ’04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, Jun 2004. [32] C. Hoare. Quicksort. The Computer Journal, 5(1):10–16, Jan 1962. [33] P. Joshi, C.-S. Park, K. Sen, and M. Naik. A randomized dynamic program analysis technique for detecting real deadlocks. PLDI ’09: Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, Jun 2009. [34] L. Lamport. Time, clocks, and the ordering of events in a distributed system. Com- munications of the ACM, 21(7), Jul 1978. [35] C. Lattner and V. Adve. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. CGO ’04: Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, Mar 2004. [36] R. Lienhart and J. Maydt. An extended set of Haar-like features for rapid object detection. 1:900–903, 2002. [37] D. G. Lowe. Distinctive Image Features from Scale-Invariant Keypoints. Interna- tional Journal of Computer Vision, 60(2):91–110, 2004. [38] D. Marino, M. Musuvathi, and S. Narayanasamy. LiteRace: effective sampling for lightweight data-race detection. PLDI ’09: Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, Jun 2009. [39] F. Mattern. Virtual Time and Global States of Distributed Systems. Proceedings of the International Workshop on Parallel and Distributed Algorithms, pages 215–226, Apr 1988. [40] M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. PLDI ’06: Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, Jun 2006. [41] S. Narayanasamy, Z. Wang, J. Tigani, A. Edwards, and B. Calder. Automatically classifying benign and harmful data racesallusing replay analysis. PLDI ’07: Pro- ceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, Jun 2007. [42] G. Naumovich, G. Avrunin, and L. Clarke. An efficient algorithm for computing MHP information for concurrent Java programs. ESEC/FSE-7: Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIG- SOFT international symposium on Foundations of software engineering, Nov 1999. [43] N. Nethercote and J. Seward. Valgrind: a framework for heavyweight dynamic binary instrumentation. PLDI ’07: Proceedings of the 2007 ACM SIGPLAN confer- ence on Programming language design and implementation, Jun 2007. [44] R. Netzer and B. Miller. What are race conditions?: Some issues and formalizations. Letters on Programming Languages and Systems (LOPLAS, 1(1), Mar 1992. [45] D. Novillo. OpenMP and automatic parallelization in GCC. GCC Developers’ Summit, 2006. [46] R. O’Callahan and J.-D. Choi. Hybrid dynamic data race detection. PPoPP ’03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, Jun 2003. [47] OpenMP Architecture Review Board. OpenMP Application 3 Program Interface. May 2008. [48] C.-S. Park and K. Sen. Randomized active atomicity violation detection in con- current programs. SIGSOFT ’08/FSE-16: Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering, Nov 2008. [49] P. Petersen and S. Shah. Openmp support in the intelR thread checker. OpenMP Shared Memory Parallel Programming, 2716:1–12, 2003. [50] E. Pozniansky and A. Schuster. Efficient on-the-fly data race detection in multi- threaded C++ programs. PPoPP ’03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, Jun 2003. [51] E. Pozniansky and A. Schuster. MultiRace: efficient on-the-fly data race detection in multithreaded C++ programs. Concurrency and Computation: Practice & Expe- rience, 19(3):327–340, 2007. [52] C. Praun and T. Gross. Object race detection. OOPSLA ’01: Proceedings of the 16th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, Nov 2001. [53] T. K. Ralphs and M. Gu ̈zelsoy. The Symphony Callable Library for Mixed Integer Programming. Proceedings of the Ninth INFORMS Computing Society Conference, 29:61–76, 2005. [54] A. Sasturkar, R. Agarwal, L. Wang, and S. Stoller. Automated type-based analysis of data races and atomicity. PPoPP ’05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, Jun 2005. [55] S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: a dy- namic data race detector for multithreaded programs. Transactions on Computer Systems (TOCS, 15(4), Nov 1997. [56] E. Schro ̈dinger. An Undulatory Theory of the Mechanics of Atoms and Molecules. Phys. Rev., 28(6):1049–1070, Dec 1926. [57] K.SerebryanyandT.Iskhodzhanov.ThreadSanitizer:dataracedetectioninpractice. WBIA ’09: Proceedings of the Workshop on Binary Instrumentation and Applica- tions, Dec 2009. [58] A. Srivastava and A. Eustace. ATOM: a system for building customized program analysis tools. PLDI ’94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, Aug 1994. [59] N. Sterling. Warlock: A static data race analysis tool. Winter USENIX, pages 97– 106, Jan 1993. [60] W. C. Swope, H. C. Andersen, P. H. Berens, and K. R. Wilson. A computer simula- tion method for the calculation of equilibrium constants for the formation of physi- cal clusters of molecules: Application to small water clusters. Journal of Chemical Physics, 76(1):637–649, 1982. [61] R. N. Taylor. Complexity of analyzing the synchronization structure of concurrent programs. Acta Informatica, 19(1):57–84, 1983. [62] P. Viola and M. Jones. Rapid object detection using a boosted cascade of simple features. Computer Vision and Pattern Recognition, 2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on, 1:511–518, 2001. [63] S. Wu and U. Manber. AGREP - A Fast Approximate Pattern-matching Tool. Pro- ceedings of the Winter 1992 USENIX Conference, pages 153–162, 1991. [64] L. Wu-Jay. Data-Race Detection and Lock-Mechanism Validation for OpenMP Pro- grams on GCC. 2009. [65] Y. Yu, T. Rodeheffer, and W. Chen. RaceTrack: efficient detection of data race conditions via adaptive tracking. SOSP ’05: Proceedings of the twentieth ACM symposium on Operating systems principles, Oct 2005. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46932 | - |
dc.description.abstract | 近年來,多核心的處理器架構已經被廣為採用並成為業界的主流設 計。為了能夠有效的利用多核心處理器所帶來的效能,多執行緒程式 已經成為軟體開發上的必備的技巧。除了使用 POSIX threads (Pthreads) API 外,簡單、易讀且富有可攜性的多執行緒程式開發標準也被廣泛 的使用,而 OpenMP 便是其中的佼佼者。然而在享受多執行緒程式開 發所帶來的效能地同時卻延伸出一些棘手的問題,其中之一便是 data race。在這篇論文中,我們設計了一個應用在 OpenMP 程式上,動態 與靜態偵測 data race 的工具。
首先,我們利用 GCC 分析並編譯 OpenMP 程式,分析的結果可以 用來減少之後在執行期所需的檢測。接著再利用 LLVM 在透過觀察與 分析程式的行為進行更近一步的偵測。 | zh_TW |
dc.description.abstract | Multicore processors have become mainstream. Therefore, to exploit sil- icon resource effectively, multithreaded programming is critical. In addi- tion to the traditional POSIX threads API, other multithreaded APIs such as OpenMP have been proposed. OpenMP provide an interface that is easy to use, highly reliable, and portable. However, the effective exploitation of re- sources by multithreaded programming comes with cost. For instance, data races result in incorrect execution sometimes and are expensive to be elim- inated. We present a novel data race detection tool to address this cost of multithreaded programming.
Specifically, we develop a plugin for GCC compiler to analyze the OpenMP constructs from the source and compile the OpenMP program. The results from the static analysis can be used to reduce the necessary instrumentation later. Next, we utilize the LLVM compiler infrastructure to observe and ana- lyze the runtime behaviors for further data race detection. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T05:43:33Z (GMT). No. of bitstreams: 1 ntu-99-R97944011-1.pdf: 846370 bytes, checksum: 23aa84def2fe33df8745c0b15377655e (MD5) Previous issue date: 2010 | en |
dc.description.tableofcontents | 致謝 iii
中文摘要 v Abstract vii Contents ix List of Figures xi List of Tables xiii 1 Introduction 1 2 Background of Dynamic Data Race Detection Algorithm 5 2.1 Happens-BeforeRelation.......................... 6 2.2 VectorClocks................................ 6 2.3 FastTrack Algorithm ……………………… 8 3 The Dynamic Analysis Framework ThreadTracer 11 3.1 ThreadTracer APIs ...…………………… 15 3.2 Optimizations and Features......................... 20 3.2.1 Composition of Tracers ...................... 20 3.2.2 Replay ............................... 20 3.2.3 Sampling .............................. 20 3.2.4 Real-to-Shadow Variable Map Lookup Cache . . . . . . . . . . . 21 3.2.5 ArrayElementAccess ....................... 22 3.3 Compare RoadRunner and ThreadTracer .............. 23 4 Static Data Race Detector for OpenMP 25 4.1 OpenMP Program Structure Graph..................... 27 4.2 High-Level MHPG ............................. 30 4.3 Low-Level MHPG ............................. 33 4.4 May-Happen-in-Parallel (MHP) Set .................... 36 4.5 Require-Instrumented-Statement (RIS) Set. . . . . . . . . . . . . . . . . 37 5 Implementation 41 6 Experiments 43 6.1 Evaluation of Dynamic Data Race Detector . . . . . . . . . . . . . . . . 45 6.2 Evaluation of Dynamic Data Race Detector with Static Approach . . . . . 47 6.3 Evaluation of Real-to-Shadow Map Lookup Cache . . . . . . . . . . . . 50 6.4 Evaluation of Sampling........................... 50 7 Related Work 53 7.1 Static Data Race Detection ......................... 53 7.2 Dynamic Data Race Detection ....................... 54 7.3 Dynamic Analysis Framework ....................... 55 8 Conclusions and Future Work 57 Bibliography 59 | |
dc.language.iso | en | |
dc.title | 在 GCC 與 LLVM 上實作以 OpenMP 程式為主動態與靜態混 合之 Data Race 偵測 | zh_TW |
dc.title | Static and Dynamic Data Race Detection for OpenMP Programs on GCC and LLVM | en |
dc.type | Thesis | |
dc.date.schoolyear | 98-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 洪士灝(Shih-Hao Hung),郭大維(Tei-Wei Kuo),施吉昇(Chi-Sheng Shih),楊佳玲(Chia-Lin Yang),蔡欣穆(Hsin-Mu Tsai) | |
dc.subject.keyword | OpenMP,GCC,LLVM,data race,多線程,動態分析,靜態分析, | zh_TW |
dc.subject.keyword | OpenMP,GCC,LLVM,data race,multithread,dynamic analysis,static analysis, | en |
dc.relation.page | 66 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2010-08-20 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊網路與多媒體研究所 | zh_TW |
顯示於系所單位: | 資訊網路與多媒體研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 826.53 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。