擴充OpenMP以支援軟體實現執行緒層級推測技術之研究

OpenMP Extension for Software-based Thread-level Speculation

柯成儒(Cheng-Ju Ko)

指導教授 ： 陳鵬升

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

摘要

執行緒推測技術是一種利用多個執行緒去運行程式並且利用猜測技術來確定程式運行的正確性而達到平行運行的效能，當程式有相依性關係的資料存在的時候，我們並須要確保平行執行時的正確性，因此當我們程式執行完時檢查資料順序的正確性，如果正確的話就繼續往下執行，而我們也因此得到效能的提升，如果資料順序錯誤時，則我們要花費一些時間進入回復機制，讓資料重新執行並確保正確，因此如果當發生的資料錯誤的機率太高時，則可能會花太多時間在回覆機制上面，因此讓平行執行的效能失去。
對於一般使用者而言，要設計一個執行緒推測技術的模型並不是相當容易的，因為當中包含了一些同步、資料競爭的機制考量，因此在本論文中，我們利用OpenMP這個API以及GCC編譯器設計一個可以自動化產生平行程式碼的方法。
OpenMP為一個可以簡單讓使用者輕鬆讓程式平行化的模型，只要透過一些指令，就可以讓程式去執行平行化，目前我們僅針對 "pragma omp for" 結構在OpenMP裡面加入我們的執行緒推測技術模型，我們利用GCC中間表示的 gimple節點，將 "for-loop body" 的部分抓取出來，並加以修改插入我們需要的程式碼以及函式來完成執行緒猜測技術的模型。而使用者如要使用我們的模型時不需手動去修改出模型，只需要知道有相依性的資料變數並且標註我們自行建立的指令就可以使用執行緒推測技術模型。

關鍵字

執行緒推測技術 ； 平行化

並列摘要

Thread-level speculation (TLS) is a technique which uses multiple threads to execute programs and exploits speculation techniques to determine the correctness of the program. When a program exists data dependencies, we need to ensure the correctness of the parallel execution. If the dependencies are preserved, we will obtain benefits in this parallel execution. In contrast, if the dependencies are violated, we need to pay extra overheads to the recovery, and roll back to the status before the misspeculation. Therefore, when the probability of misspeculation is high, it may spend much time on the recovery and nullify the benefits from the parallel execution.
Writing a parallel program with TLS technique is complicated and difficult for general users, which includes synchronization, deadlocks, and data contention issues. In this thesis, we use OpenMP and GCC compiler to design a method to automatically generate TLS programs. We use OpenMP to create and manage threads. We also design new OpenMP clauses, and modify the GCC gimple intermediate representation (IR). Programmers who want to use TLS technique in OpenMP do not need to know how to write TLS programs, just need to find out the dependence variables and then insert the proposed new OpenMP clauses. The experimental results show when the time in a TLS region is short or the violation rate is high, the proposed TLS clause is not suitable for using the proposed OpenMP clause. The performance of the automatically generated codes in our implementation is quite close to the hand-coded version.

並列關鍵字

Thread-level Speculation ； GCC ； OpenMP

參考文獻

[2] Neil Vachharajani, Ram Rangan, Easwaran Raman, Matthew J Bridges, Guilherme Ottoni, and David I August. Speculative decoupled software pipelining. In Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, pages 49-59. IEEE Computer Society, 2007.

[4] Gcc, the gnu compiler collection. http://gcc.gnu.org/, .

[13] Lingxiang Xiang and Michael Lee Scott. Compiler aided manual speculation for high performance concurrent data structures. In Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 47-56. ACM, 2013.

[15] Bronis R. de Supinski. Progress on openmp speci cations. 2012.

[1] Xiao-Feng Li, Chen Yang, Zhao-Hui Du, and Tin-fook Ngai. Exploiting thread level speculative parallelism with software value prediction. In Advances in Computer Systems Architecture, pages 367-388. Springer, 2005.