應用於立體視訊執行緒管線平行之驗證感知設計方法

A Verification-aware Design Methodology for Thread Pipelining Parallelization on Stereoscopic Video Applications

簡國安(Guo-An Jian)

指導教授 ： 郭峻因 ； 陳鵬升

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

摘要

本論文提出一個驗證感知的設計方法，此方法為開發人員提供了一個系統化而且可靠的方法來進行循序程式的執行緒管線平行化，相較於傳統的設計流程，本文主張在進行平行化之前先建構一個行為模型的程式，再以此行為模型做為橋樑，幫助開發人員逐步利用執行緒管線平行化技術，因此，本文所提之設計方法也將驗證機制整合到設計流程之中，為了證明該方法之實用性，我們將此方法應用到三維景深產生器的執行緒管線平行化，接著此平行三維景深產生器將進一步整合到三維視訊播放系統以便針對驗證開銷及系統效能進行評估，結果顯示，透過五級管線的平行系統，在D1及HD720解析度下可分別達到33.72 fps及12.22 fps的處理速度，在此同時，本文所提之驗證方法在進行平行程式的驗證時，可將驗證過程所造成的效能下降幅度在D1及HD720解析度下分別控制在23％及21.1％，另一方面，本文也開發出執行緒層級超純量管線平行化方法來進一步提升三維視訊播放系統的平行度，最後，平行三維視訊播放系統可針對HD720解析度的視訊資料達到63.66 fps的處理速度。

關鍵字

驗證 ； 三維景深圖產生 ； 管線 ； 平行計算 ； 行為模型

並列摘要

This dissertation proposes a verification-aware design methodology that provides developers with a systematic and reliable approach to performing thread-pipelining parallelization on sequential programs. In contrast to traditional design flow, a behavior-model program is constructed before parallelizing as a bridge to help developers gradually leverage the technique of thread-pipelining parallelization. The proposed methodology integrates verification mechanisms into the design flow. To demonstrate the practicality of the proposed methodology, we applied it to the parallelization of a 3D depth map generator with thread pipelining. The parallel 3D depth map generator was further integrated into a 3D video playing system for evaluation of the verification overheads of the proposed methodology and the system performance. The results show the parallel system can achieve 33.72 fps in D1 resolution and 12.22 fps in HD720 resolution through a five-stage pipeline. When verifying the parallel program, the proposed verification approach keeps the performance degradation within 23% and 21.1% in D1 and HD720 resolutions, respectively. On the other hand, a thread-level superscalar-pipelining approach is also developed to parallelize the 3D video playing system. The parallel 3D video playing system can achieve a processing speed of 63.66 fps for HD720 resolution video.

並列關鍵字

verification ； 3D depth map generation ； pipeline ； parallel computing ； behavior model

參考文獻

[2] W. Thies, V. Chandrasekhar, and S. Amarasinghe, “A Practical Approach to Exploiting Coarse-Grained Pipeline Parallelism in C Programs”, Proceedings of IEEE/ACM International Symposium on Microarchitecture, pp. 356-369, December 2007.

[4] G. R. Andrews, “Parallel Programs: Proofs, Principles, and Practice”, Communications of the ACM, vol. 24, no. 3, pp. 140-145, March 1981.

[5] R. M. Keller, “Formal Verification of Parallel Programs”, Communications of the ACM, vol. 19, no. 7, pp. 371-384, July 1976.

[7] G. J. Holzmann, “The Model Checker Spin”, IEEE Transaction on Software Engineering, vol. 23, no.5, pp. 279-295, May 1997.

[8] G. J. Holzmann and D. Bosnacki, “The Design of a Multicore Extension of the SPIN Model Checker”, IEEE Transactions on Software Engineering, vol. 33, no. 10, pp. 659-674, October 2007.