不規則資料相依巢狀迴圈平行化技術之研究與分析

Abstract

本論文的主題為針對不規則資料相依迴圈(Non-uniform Data Dependence Loop)所設計之迴圈平行化方法。以往的研究中，大部份的平 行化方法通常都以規則相依的迴圈為處理對象，若迴圈相依不規則，則平 行化方法通常不適用或效果不佳[Dart 94][Lamp 74][Dhol 92][Berg 87] 。根據Zhiyu對陣列下標函數(array subscribts)與相依關係的探討[Shen 89]，有相當比例(約40%)的線性陣列下標函數是為耦合性陣列下標( coupled array subscripts)，且耦合性陣列下標與不規則的資料相依有 密切的相關性。因上述動機，本論文所探討的問題即為不規則資料相依迴 圈的平行化技術。本論文所提出的方法針對Chaudhary[Puny 94]的方法再 做進一步改進，以期為程式中的迴圈開發出更多的平行度。在我們所提出 的方法中，編譯器將自動依迴圈內之所有相依關係組特性分成迴圈主體可 能發生的四種實際狀況並選用適當的迴圈轉換(Loop Transformation 如 Interchange, Skewing等)以利於不規則相依迴圈平行化切割(Tiling transformation)，以期盡可能地開發出最大的平行度。我們針對 [Puny 94]所提出的改進可以改善原來方法中，狀況二與狀況三的平行化 效果；並使得本方法可以處理包含多組相依關係的迴圈型式，使得在實際 應用上更為可行。另外，本論文所提出的平行化方法實作在一個平行編譯 研究環境上(SUIF)，並以本實驗室另一組所發展之平行模擬環境來評估其 效果。這些初步的結果可作為不規則相依迴圈平行化編譯技術之參考。 The purpose of this thesis is to design a loop paralellization techniquefor non-uniform data dependence loops. In the past studies, most loop parallelizationtechniques are focused on the problem of uniform dependence loops. However, whenthe loop is non-uniform dependent these methods are either fail or inefficient[Dart 94][Lamp 74][Dhol 92][Berg 87]. According to the survey of the relationbetween array subscripts and data dependence by Zhiyu[Shen 89], there are almost40% of the linear array subscripts are coupled array subscripts which is tightlyrelated to non-uniform dependence relations. Due to the motivation mentioned above,we focus our loop parallelization technique on non-uniform dependence loops. Inour thesis, we proposed a further improved method based on Punyamurtula's[Puny 94]to expore more parallelism. In our method, compiler will choose proper loop transformations to make the benefit for loop parallelization(Tiling) according tothe four cases derived form all dependence relations in loop body so as to exporeparallelism as much as possible. Our approach improves the parallelism of case II and case III of method [Puny 94]. Furthermore, it also expand the problem domainto a more general loop model which includes multiple set of dependence relations.Besides, we build our method on a parallel compilation environment(SUIF) and evaluate the results on a parallel simulation environment which developed by ourlab. in another project. These preliminary results can be referenced for non-uniform dependence loop parallelization techniques.