藉由多面體模型 (Polyhedral Model) 改善同質多核心系統之資料局部性

Abstract

在現今同質多核心(homogeneous multiprocessors)系統上，常用的平行編程模式(parallel programming model)有OpenMP與MPI等，其中又以OpenMP最為被廣泛地使用。另一方面，對於同質多核心系統而言，效能的瓶頸通常是在迴圈程式的記憶體存取上。因此，為提昇程式在同質多核心系統上的執行效能，程式開發者會藉由一些迴圈優化技術來提高程式執行的資料局部性(data locality)以減少外部記憶體(external memory)的存取次數，其中常見的技術有迴圈互換(loop interchange)與迴圈區塊化(loop tiling)等。為了執行這些優化的技術，迴圈程式碼都通常會先轉成抽象化中間表示式(intermediate representation, IR)；在執行完一連串優化技術後，再將IR轉回成程式碼或可執行檔。目前常見的IR表示方式有抽象語法樹 (abstract syntax tree, AST)與多面體模型(polyhedral model)等。對於迴圈程式碼而言，使用polyhedral model可以減少避免轉換順序之間造成的副作用(side-effect)，如程式碼變大及複雜度變高等問題。 在本論文中，我們針對迴圈程式的資料局部性的優化實作了一套迴圈程式原始碼到原始碼(source-to-source)的轉換框架(framework)。本論文開發之framework可自動找出OpenMP程式中的DOALL迴圈，並針對這些迴圈進行loop tiling以提昇資料局部性。根據模擬結果顯示，透過所開發之loop tiling技術，程式的執行效能平均可提昇14.1%。此外，藉由本論文開發之framework，程式開發者可以快速地發展在polyhedral model下所需之迴圈優化技術。

The parallel programming model on homogeneous multiprocessors includes OpenMP, MPI, and others. OpenMP is the most widely used in these common parallel programming models. On the other hand, the performance bottleneck on homogeneous multiprocessors is usually the memory access within a nested loop. Therefore, programmers would adopt some loop optimizations to enhance data locality and reduce external memory access times for the parallel execution on homogeneous multiprocessors. The common techniques of loop optimizations are loop interchange and loop tiling. The source code of the nested loops would usually translate to the intermediate representation (IR) for applying the loop optimizations. After a series of optimizations, IR would translate back to the source code or the executable program. The common IR includes abstract syntax tree, polyhedral model, and others. Using polyhedral IR could avoid causing side-effects between transformation orders, such as increasing the code size and enhancing the transformation complexity. In this thesis, we present the implementation of a polyhedral source-to-source transformation framework that could optimize the nested loops for the data locality improvement. The framework could find the DOALL loops automatically and adopt loop tiling to enhance the data locality. According to the simulation results, the programs could increase 14.1% performance in average by performing loop tiling. Moreover, programmers could develop loop optimizations quickly based on our polyhedral framework.