C程式到執行緒層級推測技術的程式模型之自動化轉換技術之研究

Automatic Translation of C Programs to Thread-level Speculation Programming Model

李京桓(Ching-Huan Lee)

指導教授 ： 陳鵬升

國立中正大學/工學院/資訊工程學系/碩士(2012年)

摘要

執行緒層級推測技術(Thread level Speculation)是一種程式在運行時，積極利用執行緒去平行執行的技術。TLS採用的推測的方式去猜測彼此具有相依性關係的執行去所使用到的值，並在執行完該次工作後，檢查運算後的結果是否產生相依性關係的錯誤。若檢查過後，並不存在相依性關係的問題，則我們會因此得到平行執行時所產生的效能提昇。不過，當檢查該次執行的結果顯示執行緒之間存在著相依性關係的錯誤時，則該執行緒必須執行復原函式，使該執行緒回到為執行狀態，並且重新執行該執行緒。因此當程式執行期間，若是檢查到存有相依性關係的錯誤，則會額外增加該程式執行所花時間。當產生過多的推測錯誤時，則有可能將所有平行化的效能全數抵銷。在本篇論文中，我們開發了一個TLS編譯器，可以將循序執行的程式碼透過註解的標記，自動轉換成相對應的TLS程式碼。將編譯器directives標記在循序執行的程式碼中，表示該段程式區段需要轉換成TLS的執行方式。而我們實做在Mercurium這套編譯器開發工具，我們實做了一個pPass使它可以辨識我們所設計的directives和clauses，並且將標記了我們所設計的directives和clauses的程式碼區段轉換成相對應的TLS programming model。目前，我們所提供的編譯器directives和clauses僅支援for迴圈結構，而在我們的實驗結果可以看到在for迴圈結構中具有大量運算的benchmark，我們可以得到較好的執行效能。反之，我們會得到負向提昇。

關鍵字

平行化

並列摘要

Thread-level speculation (TLS) is a technique to aggressively exploit parallelism of applications at runtime. TLS speculatively executes dependent threads, and checks whether dependence relationships are violated at runtime. If no dependence violation occurs during the execution, we get performance benefits from the parallel execution. However, if the dependence relationships among threads are violated, it needs to do recovery operation to roll back to the status before the thread execution, and then re-executes the thread. Therefore, the mis-speculation will suffer significant perfor-mance penalty. When more speculated errors occur, they may nullify the benefits of parallel execution. In this thesis, we develop a TLS compiler to automatically translate annotated sequential programs into the corresponding TLS programs. Compiler directives are used to annotate the code fragments that are expected to be executed by TLS technology. Our compiler is implemented based on Mercurium compiler infrastructure and we implement a pass that makes it to recognize our proposed directives and clauses, and then converts the labeled code fragments into the corresponding C code of TLS pro-gramming model. Presently, we only provide compiler directives and clauses for the for-loop construct. For the tested benchmark programs, the experimental results show that our compiler can make performance benefits for the computation-intensive benchmark programs.

並列關鍵字

Automatic speculative multithreading

參考文獻

[7]. João Cachopo, António Rito-Silva,“Versioned boxes as the basis for memory transactions”, Sci. Comput. Program., 63(2):172–185, 2006

[12]. Chen Tian, Changhui Lin, Min Feng, Rajiv Gupta, “Supporting speculative pa-rallelization in the presence of dynamic data structures”, PLDI '10 Proceedings of the 2010 ACM SIGPLAN conference on Programming language design and im-plementation, ACM, 2010

[1]. M atthew R. Guthaus, Jeffrey S. Pingenberg, Dap Emst, Todd M. Austin, Trevor Mudge and Richard B. Brown, “MiBench: A free, commercially representative embedded benchmark suite”, Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop on, pp. 3 – 14, 2 Dec. 2001

[2]. Website, Mercurium C/C++ source-to-source compiler, http://nanos.ac.upc.edu/projects/mcxx, 2011

[3]. Sergio Aldea, Diego R. Llanos and Arturo González-Escribano, “Towards a compiler framework for thread-level speculation”, Parallel, Distributed and Network-Based Processing (PDP), 2011 19th Euromicro International Confe-rence on, pp. 267 – 271, 2011