(3.210.184.142) 您好!臺灣時間:2021/05/09 10:21
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:薛元富
研究生(外文):Hsueh, Yuan-Fu
論文名稱:軟體實現執行緒層級推測技術之程式設計模型之研究
論文名稱(外文):A Practical Programming Model forSoftware Thread-Level Speculation
指導教授:陳鵬升陳鵬升引用關係
指導教授(外文):Chen, Peng-Sheng
口試委員:陳鵬升薛智文張榮貴林迺衛
口試委員(外文):Chen, Peng-ShengHsueh, Chih-WenChang, Rong-GueyLin, Nai-Wei
口試日期:2011-07-22
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:英文
論文頁數:78
中文關鍵詞:程式設計模型推測技術
外文關鍵詞:TLSprogrammingmodel
相關次數:
  • 被引用被引用:0
  • 點閱點閱:204
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:12
  • 收藏至我的研究室書目清單書目收藏:0
執行緒層級推測技術(TLS)是一項在程式運行時積極去利用平行執行的技術。TLS會用推測的方式去執行有相依性的執行緒,並且在之後去檢查看看運行時是否有任何的相依性有出現錯誤。如果執行完後執行緒的相依性都沒有出錯的話,那麼我們將會獲得因平行執行所產生的效能提升。反之如果執行緒的相依性出錯時,出錯的執行緒將會需要去執行相對應的復原函式來恢復錯誤的部分,並且與這個執行緒有相關的其他執行緒也會需要被重新執行。一旦程式執行時推測錯誤的話,那麼這次的程式執行效能提升將會減少,而且出錯次數過多的話很可能會讓整個平行執行的效能提升消失不見。
在這篇論文中,我們提出一個純軟體的執行緒層級推測技術之程式設計模組,我們也針對不同的資料相依性提供一些不同的設計方式,這樣的話可以有效的降低執行時偵測相依性出錯與推測錯誤的負擔,同時我們所提出的方法也降低程式執行時各個執行緒之間同步化的代價。我們的整個實作是以POSIX thread(pthread) library與GCC atomic built-in function這二個為基礎做出來的,因此只要機器平台上有這二個東西就可以編譯出我們的模組。在最後實驗數據的部分則顯示了使用我們程式模組的標準程式是可以在多核心平台上獲得效能的提升。

Thread-level speculation (TLS) is a technique to aggressively exploit the parallelism of applications at runtime. TLS speculatively executes the dependent threads, and defer checking whether dependencies are violated or not at runtime. If dependencies are preserved, we will obtain the performance benefits as a result of the parallel execution. In contrast, if dependencies are violated, appropriate recovery codes require to be executed to roll back to the status before the misspeculation, and then the related dependent threads require to be re-executed. For TLS, misspeculation will pay high penalties and frequent misspeculation may nullify the benefits from the parallelization.
In this thesis, we develop a programming model for software TLS. We also propose several strategies to reduce the cost of detecting dependence violations and misspeculation. The approaches are also developed to minimize the synchronization overheads among threads at runtime. The whole implementation is built upon POSIX thread library and GCC atomic built-in functions. The experimental results show that the proposed programming model and implementation can get performance improvement on multicore systems for the tested benchmark programs.

Chapter 1 Introduction
1.1 Contrubution
1.2Organization
Chapter 2 Programming Mode
2.1 Target applications and architectures
2.2 Execution flow
2.2.1 Main thread and assistance thread
2.2.2 Main thread and work thread
2.3 Speculation execution
2.3.1 Type 1
2.3.2 Type 2
2.3.3 Type 3
2.3.4 Type 4
2.3.5 Type 5
2.3.6 Type 6
Chapter 3 Implementation
3.1 Program analysis
3.2 Construction of global buffer
3.3 Creation of assistance and work thread
3.4 Transformation from loop construct to TLS region
3.5 Modification of main thread
Chapter 4 Experiment
4.1Experimental environment
4.2 Performance
Chapter 5 Related Work
Chapter 6 Conclusion
Reference
Appendix
[1]ChenTian, MinFeng, and Rajiv Gupta, “Supporting speculative parallelization in the presence of dynamic data structures,” In proceedings of the 2010 ACM SIGPLAN conference on Programming language design and implementation ( PLDI’10). New York, NY, USA: ACM, 2010, pp. 62–73.
[2]Website, “Gcc, the gnu compiler collection,” http://gcc.gnu.org, 2011.
[3]Website, “Atomic – gcc wiki,” http://gcc.gnu.org/wiki/Atomic, 2011.
[4]Ram Rangan, NeilVachharajani, ManishVachharajani, David Isaac August,“Decoupled Software Pipelining with the Synchronization Array,” In proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques(PACT’04).IEEE Computer Society Washington, DC, USA, 2004, pp. 177-188.
[5]JianHuang,“The SImulator for Multithreaded Computer Architecture,” Technical Report No: Advanced Research in Computing Technology and Compilers (ARCTiC)-00-05.
[6]ArunRaman, Hanjun Kim, Tomas R Mason, Tomas B Jablin, David Isaac August, “Speculative Parallelization Using Software Multi-threaded Transactions,”In proceedings of the 15th edition of Architectural support for programming languages and operating systems (ASPLOS’10).New York, NY, USA: ACM, 2010, pp. 65-76.
[7]Neil Vachharajani, RamRangan, Easwaran Raman, Matthw John Bridges, GuilhermeOttoni, and David Isaac August. August,“Speculative decoupled software pipelining,”In proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques(PACT’07).IEEE Computer Society Washington, DC, USA, 2007, pp. 49-59.
[8]CosminEugenOancea Alan Mycroft,“Software Thread-Level Speculation –An Optimistic Library Implementation,” In proceedings of the 1st international workshop on Multicore software engineering(IWMSE’08).New York, NY, USA: ACM, 2008, pp. 23-32.
[9]Jenn-Yuan Tsai, Pen-Cung Yew,“The Superthreaded Architecture: Thread Pipelining with Run-Time Data Dependence Checking and Control Speculation,” In proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques (PACT’96). IEEE Computer Society Washington, DC, USA, 1996, pp.35.
[10]John Mellor-Crummey and Michael L Scott,“Algorithms for scalable synchronization on shared-memory multiprocessors,” In ACM transactions on Computer Systems(TOCS) Vol. 9 Issue 1, Feb 1991. New York, NY, UAS: ACM, 1991, pp. 21-65.
[11]C. E. Oancea and A. Mycroft,“A Lightweight In-Place Model for Software Thread-Level Speculation,” In Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures (SPAA’09), New York, NY, UAS: ACM, 2009, pp.223-232.
[12]Y. Luo, V. Packirisamy, W. Hsu, A. Zhai, N. Mungre, A. Tarkas, “Dynamic Performance Tuning for Speculative Threads,” In proceedings of the 36th annual international symposium on Computer architecture (ISCA’09).New York, NY, UAS: ACM, 2009, pp.462-473.
[13]Christopher J.F. Puckett, Clark Verbrugge, Allan Kielstra, “libspmt: A Library for Speculative Multithreading,” In Sable Technical Report No. 2007-1.
[14]ShengyueWang, Xiaoru Dai, Kiran S Yellajyosula, Antonia Zhai, Pen-Chung Yew,“Loop Selection for Thread-Level Speculation,” In Proceedings of the 18 th International Workshop on Languages and Compilers for Parallel Computing (LCPC2005).
[15]Ravi Rajwar, MauriceHerlihy, Konrad Lai, “Virtualizing Transactional Memory,” In proceedings of the 32nd annual international symposium on Computer Architecture (ISCA’05). IEEE Computer Society Washington, DC, USA, 2005, pp. 494-505.
[16]Website, “POSIX Threads Programming,”https://computing.llnl.gov/tutorials/pthreads/
[17]PolychronisXekalakis, NikolasIoannou, MarceloCintra,“Combining Thread Level Speculation, Helper Threads, and Runahead Execution,” In proceedings of the 23rd international conference on Supercomputing (ICS’09). New York, NY, UAS: ACM, 2009, pp. 410-420.
[18]AnasuaBhowmik, Manoj Franklin,“A general compiler framework for speculative multithreading,” InProceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures (SPAA’02). New York, NY, UAS: ACM, 2002, pp. 99-108.
[19]GuilhermeOttoni, RamRangan, AdamStoler, David Isaac August,“Automatic Thread Extraction with Decoupled Software Pipelining,” In proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture (MICRO’05).IEEE Computer Society Washington, DC, USA, 2005, pp. 105-118.
[20]G.R. Joubert, W.E. Nagel, F.J. Peters, O. Plata, P. Tirado, E. Zapata, ”The Mitosis Speculative Multithreaded Architecture,” In proceedings of the Parallel Computing: Current Future Issues of High-End Computing, Proceedings of the International Conference (ParCo 2005).
[21]PeterRundberg, Per Stenstrom,“An All-Software Thread-Level Data Dependence Speculation System for Multiprocessors,” The journal of Instruction-Level Parallelism, 1999, vol. 3, pp. 2002.
[22]WeiJen Chen. Hyperion: A Software Library for Speculative Multithreading.
[23]Jin Lin, Tong Chen, Wei-Chung Hsu, Pen-Chung Yew, Roy Dz-Ju, Tin-FookNgai, and Sun Chan, “A compiler framework for speculative analysis and optimizations,” In Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation (PLDI’03), June 2003, pp. 289-299.
[24]Jin Lin, Tong Chen, Wei-Chung Hsu, Pen-Chung Yew, Roy Dz-Ju, Tin-FookNgai, and Sun Chan, “A compiler framework for speculative optimizations,” ACM Transaction on Architecture and Code Optimization (TACO), Vol. 1, No. 3, September 2004, pp. 247-271.
[25]Peng-Sheng Chen, Ming-Yu Hung, Yuan-Shin Hwang, Roy Dz-ChingJu, JenqKuen Lee, “Compiler support for speculative multithreading architecture with probabilistic points-to analysis,”In Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP’03), June 2003, pp.25-36.
[26]Ram Rangan, Neil Vachharajani, Manish Vachharajani, and David I. August, “Decoupled software pipelining with the synchronization array,” In Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques (PACT’04), 2004.
[27]M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown,“MiBench: A free, commercially representative embedded benchmark suite,” In Proceedings of the 4th IEEE International Workshop on Workload Characterization, 2001.
[28]Christian Bienia, Sanjeev Kumar, Jaswinder Pal Singh, and Kai Li,“The PARSEC benchmark suite: characterization and architectural implications,” In Proceedings of the 17th International Conference on Parallel architectures and compilation techniques (PACT '08), 2008, pp. 72-81.
[29]Christopher J. F. Pickett and Clark Verbrugge,“SableSpMT: a software framework for analysing speculative multithreading in Java,” In Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering (PASTE'05), 2005, pp.59-66.
[30]Christopher J. F. Pickett,“Software speculative multithreading for Java,” In Companion to the 22nd ACM SIGPLAN conference on Object-oriented programming systems and applications companion (OOPSLA'07),2007, pp.929-930.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
系統版面圖檔 系統版面圖檔