針對影像處理應用程式之執行緒層級的數值猜測之研究

Thread-level Value Speculation for Image-processing Applications

吳俊賜(Jun-Si Wu)

指導教授 ： 陳鵬升

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

摘要

執行緒層級推測技術(Thread Level Speculation)為一種讓程式極大限度利用平行化技術，達到效能提升之技術。TLS的中心思想為利用推測的方法打破程式中擁有相依關係的部分，使其可以平行化執行，並在執行完成後透過回復函式去檢查推測結果是否符合相依關係。若符合則會獲得平行執行之效能提升，反之出現錯誤必須呼叫相對應之復原函式恢復錯誤之部分，並重新執行相關執行緒，若發生錯誤則會降低平行執行之效能，錯誤率過高更可能導致整體平行執行效率過低的問題。
本篇論文中，提出了一個純軟體的執行緒層級推測模型，可以應用於部分特殊情形的應用程式，透過這個模型所提供的函式，使用者可以輕易使用，讓其程式達到平行化的效果。另外提供模型需花費的代價評估，讓使用者可以輕易評估其程式是否合適於我們的模型來平行化。實作是以POSIX thread(pthread) library為基礎，編譯器使用gcc，所以機器上擁有這兩樣東西，基本上就可以編譯並使用我們的模組達到平行化的效果。最後透過我們實驗數據部分，可以了解我們提供的純軟體的執行緒推測模型在多核星平台上，可以獲得多少的程式效能上提升。

關鍵字

平行化 ； 數值猜測 ； 執行緒層級推測技術

並列摘要

Thread-level speculation (TLS) is a technique to aggressively exploit the parallel of a program. TLS is a method of using predictive technology to break the program dependencies to achieve parallel execution. When the end of the execution, using a function to check whether the results are correct. If correct, we will get the benefit of the parallel execution. If misspeculation, we need to call the corresponding recovery function to recover to previous status, and re-execute the relevant work. Obviously, the misspeculation will reduce the effectiveness of the parallel execution.
In this thesis, we develop a programming model for software thread-level value speculation which can be used in image-processing applications. Using the functions provided by this model, users can easily parallelize programs. We also provide the cost model, so that users can easily estimate whether the program should use our model to parallel. The whole implementation is built upon the POSIX thread library. The experimental results show the proposed programming model can get performance benefits for the tested benchmark programs.

並列關鍵字

Parallel ； Value Speculation ； Thread-level Speculation

參考文獻

[1] Richard E.Woods Rafael C. Gonzalez. Digital image processing 3/e third edition. 2009.

[2] Yuan-Fu Sheiue, Wei-Cheng Chen, Ching-Huan Lee, and Peng-Sheng Chen. A practical software-based programming model for thread-level speculation. In APPLC 2012.

[4] Chen Tian, Min Feng, and Rajiv Gupta. Supporting speculative parallelization in the presence of dynamic data structures. In ACM Sigplan Notices, volume 45, ACM, 2010.

[7] Christopher J Rossbach, Owen S Hofmann, and Emmett Witchel. Is transactional programming actually easier? In ACM Sigplan Notices, volume 45, ACM, 2010.

[8] Richard M Yoo and Hsien-Hsin S Lee. Helper transactions: Enabling thread-level speculation via a transactional memory system. PESPMA 2008, page 63, 2008.