- 學位論文
Investigation of Polyhedral Transformations on CPU and GPU
探討在CPU與GPU上之多面體轉換最佳化
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
多面體模型是一個對迴圈優化和平行化功能強大的數學架構，此模型已經發展了幾十年。由於豐富的數學理論背景，多面體模型變得受歡迎。目前有許多基於多面體模型所開發的架構，這些架構可以與編譯器技術結合以對迴圈程式碼做轉換以及分析。在這篇論文中，我們的目標是探討多面體轉換如何適用於不同的異質多核心平台。為了發現更多多面體轉換潛在的適用性，我們選擇對於多面體模型較少相關研究的Android RenderScript和OpenCL作為我們的目標。 RenderScript是Android作業系統的一個部分，它提供了針對異質計算的低層級API，我們藉由整合LLVM Polly到RenderScript online JIT compiler (libbcc)以達到經由多面體轉換的內核層級優化。在實驗中，我們重新用RenserScript改寫了PolyBench並且比較優化前和優化後的效能差異。 OpenCL是另一個可以在異質平台上編寫程式的架構。在這篇論文中，我們針對OpenCL的內核函數來進行多面體轉換的實驗研究。在實驗中，我們應用PolyBench/GP來評估優化後的性能。 通過實驗結果，多面體轉型超乎我們所預期的可以廣泛地應用。
並列摘要
The polyhedral model which is a powerful mathematical framework for loop nested optimization and parallelization has been developed for decades. It becomes popular because of the abundant mathematical theory background. There are many frameworks developed based on the polyhedral model, and these frameworks could be combined with compiler techniques for transformations of loop nested program codes and analysis. In this thesis, we aim to investigate how polyhedral transformations could be applied on different heterogeneous multi-core platforms. To discover more potential applicability of polyhedral transformations, we choose RenderScript on Android platform and OpenCL which have less research about polyhedral model as our target. RenderScript is a component of Android operating system, it provides low-level APIs for heterogeneous computing. We perform kernel level optimization with polyhedral transformation by integrating LLVM Polly into RenderScript online JIT compiler (libbcc). In the experiment, we re-program PolyBench benchmark in RenderScript and compare the performance differences after the optimizations on Android 4.1.1 Jelly Bean, average we could speed up 58% in execution time. OpenCL is another framework for writing programs which could be executed on heterogeneous platforms. In this thesis, we have an experimental research about performing polyhedral transformation on OpenCL kernel function. In the experiment, we apply PolyBench/GPU benchmark to evaluate the performance after the optimization. In loop tiling, we get 58% improvement in average. In loop interchange, we get over 2 times speed up. Through the experimental result, polyhedral transformation is more widely applicable than we expect.
參考文獻
[1] M.-W. Benabderrahmane, L.-N. Pouchet, A.Cohen, and C. Bastoul, “The poly- hedral model is more widely applicable than you think,” in Compiler Construc-tion. Springer, 2010, pp. 283–303.
[4] C. Bastoul, “Efficient code generation for automatic parallelization and optimiza- tion,” in ISPDC2 IEEE International Symposium on Parallel and Distributed Computing, 2003, pp. 23–30.
[5] S. Grauer-Gray, L. Xu, R. Searles, S. Ayalasomayajula, and J. Cavazos, “Auto- tuning a high-level language targeted to gpu codes,” in Innovative Parallel Com-puting (InPar), 2012. IEEE, 2012, pp. 1–10.
[7] T. Grosser, H. Zheng, R. Aloor, A. Simburger, A. Groblinger, and L.-N. Pouchet, “Polly-polyhedral optimization in llvm,” in Proceedings of the First International Workshop on Polyhedral Compilation Techniques (IMPACT), vol. 2011, 2011.
[10] G. Rudy, “Cuda-chill: A programming language interface for gpgpu optimiza- tions and code generation,” Ph.D. dissertation, The University of Utah, 2010.