Abstract
有愈來愈多的程式語言,如Fortran 90及APL,在語言本身提供很豐富的矩 陣運算及矩陣算式的程式庫.這些矩陣運算成為資料平行語言中很重要的 部份,因為它可以提供給編譯器對於程式進行最佳化及平行化的機會.在這 篇論文中,一個十分創新的方式被提出用來將連續的矩陣運算或矩陣算式 合成一個單獨的資料存取函數.我們是利用類似數學上函數合成的方式,將 許多矩陣運算加以合成.此方法不僅可以合成多維數及多算式的矩陣運算, 同時可以處理masked矩陣運算及多來源矩陣運算.事實上,我們提出第一個 可以同時處理Fortran 90中的RESHAPE,EOSHIFT, MERGE, CSHIFT, TRANSPOSE, MERGE, Array Section movement, Array Reduction, 及 Where Construct的矩陣運算合成方式. 同時我們將矩陣運算用數學的方 式加以模式化,進而證明矩陣運算合成可以減少程式所需記憶載入,存入, 及執行時間.矩陣運算合成目前實作成一個以WWW為基礎的系統,稱為 SYNTOOL.以允許使用者可以經由瀏覽器及網際網路來使用此系統. 在 實驗方面,我們將矩陣運算合成運用於共享式及分散式計憶體多處理機系 統.在共享式計憶體多處理機系統中,實驗的結果可以達到1.21到2.96的加 速倍率.這數據是在Sequent上使用矩陣運算合成來最佳化一些科學及工程 應用程式所達到.同時在SGI Power Challenge上亦得到很好的結果.在另 外一方面,我們亦將矩陣運算合成運用於分散式計憶體多處理機系統,實驗 的平台包括8-node DEC, IBM SP2, 16-node nCUBE.經由此實驗,我們證明 矩陣運算合成在分散式計憶體系統中亦可達到很好的效果.除此之外,我們 提出了區段對齊的概念將自動資料對齊和矩陣運算合成的技術加以整合. 此論文中提出矩陣運算合成並證明其可以用來最佳化Fortran 90及資料平 行語言使其在共享式計憶體系統及分散式計憶體系統都能有效的提昇程式 執行的效能. An increasing number of programming languages, such as Fortran 90 and APL, are providing a rich set of intrinsic array functions and array expressions. These constructs which constitute an important part of dataparallel languages provide excellent opportunities for compiler optimizations. In this thesis, an innovative new approach is proposed tocombine consecutive array operations or array expressions into a composite access function of the source arrays. Our scheme is based on the composition of access functions, which is analogous to a compositionof mathematic functions. Our new scheme can handle not only data movements of arrays with different number of dimensions and with multiple-clause array operations but also masked array expressions and multiple-source array operations. As a result, the proposed scheme is the first synthesis scheme which can collectively synthesize Fortran 90 RESHAPE, EOSHIFT, MERGE, CSHIFT, TRANSPOSE, MERGE, array section move, array reduction operations, and WHERE constructs. We also model the array operations mathematically so as to prove that the synthesis schemereduces the number of stores, loads, and the execution time during computation. Our synthesis engine is implemented as a web-based tool, called Syntool, to allow testing of our systems via internet.For the shared-memory system, experimental results show speedups from 1.21 to 2.95 over the base code for code fragments from real applications on a Sequent multiprocessor machine, and also show comparable performance improvements on an 8-node SGI Power Challenge by incorporating our proposed optimizations. On the other hand, experimental results show significant performance improvement over the base codes for HPF code fragments from real applications on distributed-memory machines by incorporating our synthesis optimizations. Ourexperiments are done on 8-node DEC alpha Farm, 16-node IBM SP-2, and 16-node nCUBE/2 machines. The array operation synthesis scheme is demonstrated to be effective for programs running on parallel distributed memory machines.We also address the issue how to integrate the array operation synthesis scheme into the automatic alignment process. We propose a new array alignment concept, called segmented alignment, to help to incorporate array operation synthesis scheme into automatic data alignment.The synthesis scheme proposed in this thesis is shown to be an effectivescheme to optimize array operations of Fortran 90 and data parallel programs on both shared-memory and distributed-memory parallel machines.