廖世偉臺灣大學:資訊工程學研究所王穎杰Wang, Ying-JieYing-JieWang2010-05-172018-07-052010-05-172018-07-052009U0001-0708200914080700http://ntur.lib.ntu.edu.tw//handle/246246/183354雖然多核心處理器架構越來越普遍，但是在這種架構上撰寫程式並有效發揮每個處理單元的運算能力仍然是一件困難的事情。數個研究主題目標在於解決此類問題，自動平行化即是其中強而有力但同時也是相當困難的解決方法之一。ffine partitioning 提供了一種有系統的方法，能夠在多核心處理器的架構上找到近似於最佳的計算與資料分解法。 Affine partitioning 是一個強大的統一常論，它的架構融合了許多高階的優化方法，例如: 迴圈調換，迴圈反轉，迴圈融合，迴圈分離等許多方法。基於這個統一的架構，能夠在一個由仿射資料參考所組成的巢狀迴圈中找到最大的平行度同時將程式中的通訊降到最小。這篇論文中，我們提出一個GCC編譯器中的分析過程，我們稱為” affine calculator pass”，這個分析過程將affine partitioning 演算法和GCC編譯器整合，達到了自動平型化的目標。我們成功的編譯了數個以C語言撰寫的程式，這些程式由包含不同型態的陣列存取以及不同類型的資料相依的巢狀迴圈所組成。完成編譯後輸出的是一個執行檔，每個執行檔都使用了GOMP 函式庫來達到充分利用處理器的每個運算處理單元。Multicore processors have become pervasive in these days. But, it is still difficult to program these architectures to effectively utilize the computation power of multiple processing units. There are several research topics addressing this issue, one of the strong and at the same time very hard approaches is automatic parallelization. Affine partitioning provides a systematic framework to find asymptotically optimal computation and data decomposition for multicore processors. Affine partitioning is a powerful unifying theory, the framework uniformly models a large class of high level optimizations such as loop interchange, reversal, skewing, fusion, fission, re-indexing, scaling. Based on this unified framework, that maximize parallelism while minimizing communication in programs with arbitrary loop nestings and affine data accesses. In this papaer, we proposed a compiler pass in GCC called “affine calculator pass” which integrates affine partitioning framework and GCC to achieve the goal of automatic parallelization. We have successfully compiled some programs in C language which composed of different types of array access dependencies in arbitrary nested loop. And the outputs of the compilation are executables. Each of these executables can execute in parallel using GOMP library to utilize the processing units of multicore processor.Acknowledgements Ihinese Abstract IIbstract III ist of Figures Vontents VIhapter 1 Motivation and Introduction 1 1.1. Motivation 1 1.2. Introduction 2hapter 2 Background 4 2.1. Basic Concepts 4 2.1.1. Linear 4 2.1.2. Affine 4 2.1.3. Polyhedron, Polytope 5 2.2. Introduction to Affine Calculator 6 2.2.1. Affine Partitioning 6 2.2.2. GCC(Gnu Compiler Collection) 13 2.2.3. The GIMPLE Tree in GCC 14hapter 3 Overview 16 3.1. Parsing Time 17 3.2. Parse the Affine Expression and Mapping It 18 3.3. Add COND_EXPR 19 3.4. Add OpenMP Directives 21hapter 4 Experiment Result 25 4.1. Four Case Studies 25 4.1.1. Simple 25 4.1.2. Matrix Multiplication 27 4.1.3. Btrix 27 4.1.4. Black and White 28hapter 5 Conclusion 30hapter 6 Future Work 31ppendix 32 Matrix Multiplication 32 Btrix 35 Black and White 41eferences 45application/pdf641280 bytesapplication/pdfen-US自動平行化編譯器Auto parallelizationCompilerGCCAffine partitioningOpenMPthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/183354/1/ntu-98-R96922078-1.pdf