進階搜尋


下載電子全文  
系統識別號 U0026-2108201208405100
論文名稱(中文) 需求導向支援資料競爭偵測之快取記憶體
論文名稱(英文) A Debug-Capable Data Cache for Demand-Driven Data Race Detection
校院名稱 成功大學
系所名稱(中) 電腦與通信工程研究所
系所名稱(英) Institute of Computer & Communication
學年度 100
學期 2
出版年 101
研究生(中文) 李俊成
研究生(英文) Chun-Cheng Li
學號 q36994045
學位類別 碩士
語文別 英文
論文頁數 39頁
口試委員 指導教授-陳中和
口試委員-蘇文鈺
口試委員-陳培殷
口試委員-紀新洲
口試委員-林泰吉
中文關鍵字 電子系統層級設計  多核心系統  快取資料一致性  多執行緒程式除錯  資料競爭偵測 
英文關鍵字 multi-core system  cache coherency  multithread program debugging  data race detection  multipurpose cache organization 
學科別分類
中文摘要 為了能讓多核心晶片系統能有較佳的效能表現,應用程式通常會是多執行緒的結構。然而這些執行緒間或多或少會有一些資料交換的需求出現,這個時候程式的設計者就必須要有一些適當的同步機制去避免有超過一個以上的執行緒同時去存取相同的記憶體位置,因為當有超過一個以上的執行緒能同時去存取記憶體位置時,其執行結果就可能是無法預期的;這種多個執行緒同時去存取記憶體的相同位置的現象,我們就稱之為資料競爭。
資料競爭是多執行緒程式結構中常見的一種錯誤,當程式具有一定的規模時,要用人工的方式偵測此種錯誤是非常困難的,因此,陸續有人提出了自動偵測的想法,然而在這些想法中,以軟體方式為主的偵測方式會在程式執行時嚴重影響到執行效率,以硬體方式為主的偵測方式雖然不會大幅的影響程式在執行的速度,但是需要龐大的額外硬體來支援偵測的行為;本論文的目標是要發展一套有效率的資料競爭偵測方式,在不大幅影響程式執行的速度以及不使用大量外加的硬體資源的條件下,去達到動態偵測資料競爭的目的。
因此,我們提出了 Debug-Capable Data Cache的概念,利用現存的快取記憶體去記錄資料競爭偵測所需要的資訊,再使用一些簡單的硬體利用所記錄的資訊去偵測資料競爭的發生,如此,即使沒有大量的外加硬體輔助也能在不影響程式運行的情況下達到動態偵測資料競爭的目的。
英文摘要 Detecting access violation of lock discipline in a parallel program is crucial in software development. In this thesis, we introduce a debug-capable data cache (DCD cache), a novel approach to reconfigure on-chip data cache to function simultaneously as a regular data cache and a dynamic data race detector. Detection of data races is based on a lockset algorithm which tracks variable’s states and lock information. The key idea of DCD cache is that instead of storing the variable’s state and lock information in an extra storage beside the data cache, we store this information into part of the data cache when needed. The DCD cache can be configured to work simultaneously as a data cache and the data race detector, namely the debugging mode, or exclusively as a data cache in normal mode operation. The DCD cache is much more accurate and effective than previous state-of-the-art hardware-assisted race detectors by using an improved cache coherency protocol “MOESI+F” and three techniques to eliminate false positive events effectively. The cache coherency “MOESI+F” can efficiently pass share variables (dirty or clean) and lockset information among the L1 caches and the false alarm pruning techniques can improve the correctness of data race detection.
We evaluate the DCD cache by 11 SPLASH2 benchmarks and with 110 randomly injected races, respectively. Our results show that the DCD cache can detect not only the benign races in the native SPLASH2 benchmarks but also all injected bugs in the tested SPLASH2 benchmarks. Comparing with other related hardware-based methods, this work has demonstrated the advantages and feasibility of utilizing the existing data cache for data race detection.
論文目次 Chapter 1- Introduction 1
Chapter 2- Related Work 4
2.1 Hardware-Based Data Race Detecting Mechanisms 4
2.2 Multipurpose Cache Organizations 5
2.3 Cache coherency 5
Chapter 3- System Framework 6
3.1 Debug-Capable Data Cache Architecture 6
3.2 Debug Coprocessor (DCP) 9
Chapter 4- Cache Coherency Policy 11
4.1 MESIF 11
4.2 MOESI 11
4.3 MOESI+F 12
Chapter 5- False Alarm Pruning Strategy 14
5.1 Synchronization of Barrier 14
5.2 Intra-Cache False Sharing Problem 15
5.3 Ambiguous State Transformation 15
Chapter 6- Data Operations of Debugging Mode 21
Chapter 7- Accuracy of Debug-Capable Data Cache 23
7.1 Debug-Capable Data Cache Displacement Issue 23
7.2 Collision of Bloom Filter 23
Chapter 8- Experimental Result 25
8.1 Experimental Setup 25
8.2 Exhibition of Data Race Detection 26
8.3 Effectiveness of Finding Existing Races and Injected Race 28
8.4 Effective of False Alarm Pruning Technique 32
8.5 Impact of Candidate Set Granularity 35
Chapter 9- Conclusion 36
References 37
參考文獻 [1] L. Lamport, “Time, Clocks and Ordering of Events in A Distributed System,” Communications of the ACM, vol. 21, no. 7, pp. 558-565, 1978.
[2] Young-Joo Kim and Daeyoung Kim, “An Empirical Analysis of Intel Thread Checker for Detecting Races in OpenMP Programs,” IEEE/ACIS International Conference on Computer and Information Science, 2008.
[3] A. Muzahid, D. Suarez, S. Qi, and J. Torrellas, “SigRace: Signature-Based Data Race Detection,” Proceeding of the 36th Annual International Symposium on Computer Architecture (ISCA 09), pp. 325-336, Austin, TX, US, June 2009.
[4] S. Savage, M. Burrow, G. Nelson, P. Sobalvarro, and T. Anderson, “Eraser: A dynamic data race detector for multithreaded programs,” ACM Transaction on Computer Systems (TCS), vol. 15, no. 4, pp. 391-411, New York, NY, USA, Nov. 1997.
[5] M. Prvulovic, “CORD: Cost-effective (and nearly overhead-free) Order-Recording and Data race detection,” Proceeding of the 12th International Symposium on High Performance Computer Architecture (HPCA 06), Austin, TX, US, Feb. 2006.
[6] M. Prvulovic and J. Torrellas, “ReEnact: Using Thread-Level Speculation Mechanisms to Debug Data Races in Multithreaded Codes,” Proceeding of the 30th Annual International Symposium on Computer Architecture (ISCA 03), pp. 110-121, San Diego, California, USA, Jun. 2003.
[7] P. Zhou, R. Teodorescu, and Y. Zhou, “HARD: Hardware-Assisted Lockset-based Race Detection,” Proceeding of the 13th International Symposium on High Performance Computer Architecture (HPCA 07), Phoenix, Arizona, US, Feb. 2007.
[8] D. Chiou, P. Jain, L. Rudolph, and S. Devadas, “Application-Specific Memory Management for Embedded Systems Using Software-Controlled Caches,” Proc. IEEE Design Automation Conf., pp. 416-419, June 2000.
[9] Chun-Hung Lai, Fu-Ching Yang, and Ing-Jer Huang, “A Trace-Capable Instruction Cache for Cost-Efficient Real-Time Program Trace Compression in SoC,” IEEE Transactions on Computers, VOL. 60, NO. 12, December 2011.
[10] Po-Hao Hsu and Shao-Yi Chien, “Reconfigurable Cache Memory Architecture for Integral Image and Integral Histogram Applications,” IEEE Signal Processing Systems (SiPS), pp.151-156, Oct. 2011.
[11] B. F. Qian and L. M. Yan, “The Research of the Inclusive Cache used in Multi-Core Processor,” International Conference on Electronic Packaging Techonology and High Desity Packaging (ICEPT-HDP 2008), Jul. 2008.
[12] H. Hum and et al, “Forward State for use in Cache Coherency in a Multiprocessor System,” US Patent No. 6922756 B2, Jul. 2005.
[13] AMD 64 Architecture Programmer’s Manual Vol 2 ‘System Programming’.
[14] Shan Lu, Soyeon Park, Eunsoo Seo, and Yuanyuan Zhou, “Learning from Mistakes – A Comprehensive Study on Real World Concurrency Bug Characteristics,” ASPLOS’08, March 2008.
[15] B. Lucia, J. Devietti, L. Ceze, and K. Strauss, “Atom-Aid: Detecting and Surviving Atomicity Violations,” Micro, IEEE, 2009, pp.73-83.
[16] D. C. Black, J. Donovan, B. Bunton, and A. Keist, “SystemC: From the Ground up 2nd Edition,” Springer Media Inc., 2010.
[17] “OSCI TLM-2.0 Language Reference Manual,” Open SystemC Initiative (OSCI), Jul. 2009.
[18] S. C. Woo and et al., “The SPLASH-2 Programs: Characterization and Methodological Considerations,” Proceeding of the 22th Annual International Symposium on Computer Architecture (ISCA 95), pp. 24-36, Santa Margherita Ligure, Italy, Jun. 1995.
[19] T.-Y Jiang, “RaceWeir: A Multi-Core Virtual Platform with GDB Support and Hardware-SSITED Data Race Detection,” 2011 master thesis of National Cheng Kung University, Tainan, Taiwan, Feb, 2011.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2015-09-03起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2015-09-03起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw