2000-09-20 iwasawa

基本並列化処理 機能仕様ver.0

目次

０．並列化可否検出対象

１．データフロー解析

　１.１ 領域解析(region analysis)

　１.２ 依存解析(dependence analysis)

　１.３ 領域情報と依存情報の関係

２．ループの並列化変換

　２.１ インダクション変数

　２.２ 変数配列の拡張(private化)

　２.３ リダクション演算の変換

３．ループの構造変換

（３.１ ループ展開（短ループ解消，loop peeling(皮むき)，インダクション条件展開） ）

　３.２ loop alignment (ループ半周シフト)

　（３.３ ループの斜め変換）

　（３.４ ループの密多重化（外側ループのループ分割） ）

　３.５ ループ交換

　（３.６ ループ外側展開）

（３.７ ループ融合）

（３.８ ループ一重化）

４．基本並列化フェーズの全体制御方式

５．インタフェース仕様・モジュール仕様にむけて検討すべき項目

０．並列化可否検出対象

フェーズIでは，同期や通信無しで，ループの各繰り返しを並列に実行できるいわゆるdo-all型のループを検出（基本的変換を含む）し，並列に実行可能なオブジェクトコードを生成可能であるHIRに並列化変換を施す．次のループは並列化変換の対象外とする．

（１）四重ループ以上（解析時間と解析精度から）

（２）入出力を含む

（３）ループ外飛び出し(ループ飛び込み)がある

（４）ユーザ定義関数(手続き)呼び出しがある

（５）対象外の型(構造体，ポインタ)のデータの使用

検出結果はIRのループノードに反映させる．

（１）ループノードの属性

ループノードの属性として，次のフラグをたてる．これらについて考慮されればそのまま逐次に実行させることもできる．

・ 繰り返しに関して並列に実行可否

・ 当該ループの実行に必要な作業配列の有無

・ 特殊な並列化関数（総和，最大値検索，将来的には同期，通信）の有無

（２）並列処理の外側でループ繰り返しをカウントする作業変数r（初期値＝０，増分値＝１）の導入

ループボディの最後にr = r+1を置くが，これは，ループ繰り返しに関するプロセス生成時に並列実行の外側で計算し，ループボディで参照できるようなオブジェクトを生成して欲しい．

並列処理内部では，rはループ繰り返しを表し，ループボディの最後に更新されるものとして，他のインダクション変数の計算などに用いる．

１．データフロー解析

データフロー情報として，「領域情報」と「依存情報」という分け方をした．基本的にはどちらもデータの定義使用の情報を表すので表現方法が違うだけとも言えるが，多少性格が異なり，この両方を使うことになる．

領域情報はフローグラフに沿って，必要な実行パス上でのデータ参照領域を表す．最小単位がフローグラフのノードである基本ブロック，ループ繰り返し１回分，ループ全繰り返し，関数全体，というようにパスの範囲を広げて，広範囲にわたってフローセンシィティブな情報を積み上げていく．与えられたループの並列化可否やcase型の並列化可否の判定を行うのに適している．手続き間解析を行うにも実際的である．ただし，そのままのソースに対する判断は下せるが，ソース（中間語）での位置の情報が無いため，並列不可部分の局所化などの文の移動や演算を切り出すような変換を行うには十分な情報がない．手続き間解析や外側ループの並列性の解析に有効である．

一方，依存解析はソース(中間語)の一次子や文に対応する情報があるため，生成した依存グラフにグラフ理論のアルゴリズムを用いて，連結成分や強連結成分を検出したり，依存を削除するために文を挿入・移動する時の位置も的確に見出すことができる．ただし，依存グラフを作成した段階で，制御構造は明示的には見えなくなるため，アークに付加情報として制御フローの情報を（後に書く確定／不確定やdominate情報）を載せることになる．

基本的な方針として，領域解析によって，２章に記した変換により並列化できそうなループと，loop alignment , loop exchangeによって並列化できそうなものに目星をつけ，問い合わせ的に依存解析を行って，変換可否を判定する．どの変数や配列に依存解析を行うべきかも，領域解析で検出する．

１.１ 領域解析(region analysis)

フローグラフのパスに従い，そのパスで定義・使用される領域を定義する．当該ループがそのままで独立に並列実行可能か否かを判定するのに使える．また，共通領域が正しく検出できれば，分散型並列システムにおける送受信データを見つけることができる．（ただし，これは，フローグラフのパスに対応した情報なので実際のソースプログラム上のどこに送信・受信処理を挿入するのか，といった情報は領域情報からだけでは十分ではない．）

並列化可否を判断するために，次の５種類の参照(定義使用)情報が必要であると考える.EUSEとDDEF，LIVEはフローセンシティブな情報であり，MODとUSEはフローインセンセティブな情報である．

(1) MOD (modify)：与えられたパスの範囲で更新される可能性のあるデータの集合

(2) USE (use) ：与えられたパスの範囲で使用される可能性のあるデータの集合

(3) DDEF (definite definition) ：与えられたパスの範囲で必ず更新されるデータの集合

(4) EUSE (exposed use) ：与えられたパスの範囲で更新される前に使用される可能性のあるデータの集合

(5) LIVE (live) ：与えられたパスの後の実行で使用される可能性があるデータの集合

与えられたパスとは，最小単位がフローグラフのノードであり，そこからデータを対象ループ１回分，対象ルプの前繰り返しまで集約して並列実行を阻害するループ運搬依存の有無を判断する．次に例を示す．

A.基本ブロックにおける参照情報

基本ブロックの中では，制御が分岐することがなく，配列が領域を持つこともないので，MODとDDEFは等しくなる．

B.参照情報の統合

(1) Case1 : Node1 が，IF-THEN-ELSE structureのTHENノードでnode2がELSEノードである時は次のような規則で情報を融合する．ソースのELSE節やTHEN節が無い場合はどちらかの集合はφとする． (+は積集合を表し，* は和集合を表す．)

MOD1 (at node1) + MOD2 (at node2)

USE1 (at node1) + USE2 (at node2)

EUSE1 (at node1) + EUSE2 (at node2)

DDEF1 (at node1) *DDEF2 (at node2)

LIVE1 (at node1) + LIVE2 (at node2)

(2) Case2 : 元のフローグラフには存在しないが，(１)の融合処理を行った後に，ノードがシーケンスに接続する状態が発生する．このような場合は，次の規則で情報を集約する．(−は，共通部分を削除することを意味する．)

MOD1 (at node1) + MOD2 (at node2)

USE1 (at node1) + USE2 (at node2)

EUSE1 (at node1) +（ EUSE2 (at node2) - DDEF1 (at node1) ）

DDEF1 (at node1) + DDEF2 (at node2)

（LIVE1(at node1) - DDEF2 (at node2) ）+ LIVE2 (at node2)

			MOD1+MOD2 DDEF1＋DDEF2 USE1+USE2 EUSE1+ ( EUSE2−DDEF1 ) ( LIVE1−DDEF2 ) + LIVE2
		Fig.3 join process

(3) Case 3 : 上記２種類の処理により．最内側のループについて，繰り返し１回分の参照情報を得ることができる．その情報から次のような規則でループの全繰り返しに情報を拡張する．方法は(2)と同様である．

MOD (at node in loop) →_i=ini MOD(i)

USE (at node in loop) →_i=ini USE(i)

EUSE (at node in loop) →_i=ini { EUSE(i) −_j=ini DDEF(j) }

DDEF (at node in loop) →_i=ini DDEF(i)

LIVE (at node in loop) →_i=ini { LIVE(i) −_j=i+1DDEF(j) }

for (i=1 ; i<n ; i++) {

x[i]=x[i]+a[i] ;

}

(4) Case4 : フェーズIIなどの将来手続き間解析も行うことを考えると，(１)〜(３)の処理により，一つの関数手続き全体に渡る参照情報を作成することができ，これにより，引数の別名解析を行えば,グローバルデータと引数に関して手続き呼び出しにおける参照情報を作成し，それを呼び出し元の情報をマージさせることができる．

(1)〜(3)の領域情報の集約の例を次のFig.4，Fig.5，Fig.6に示す．

１.２ 依存解析(dependence analysis)

依存解析では，出力として依存グラフを作ることになる．一番細かいレベルでは，ノードは一次子を表すが，変換の種類によっては，ノードは一つの文を表すように変換した方が扱いやすい．たとえば，並列化不能部分の局所化のための文の移動など．これらのノードが表すデータアクセスにおいて，複数箇所で同一アドレスをアクセスする場合，その全ての２つの組み合わせで，どちらが先に発生するかを有向線分で結んだグラフが，依存グラフである．

依存情報の種類としては，次の４種あるが，当面は(１)〜(３)までを考慮する．

(１) flow(true) dependence

(２) anti dependence

(３) output dependence

(４) input dependence

(メモリ分散型アーキテクチャに対して自動的に送受信命令を挿入しようとすると必要になると思う．)

(５)ループ運搬依存

ループのバッグエッジを通る依存関係である．このバックエッジを何回通るかを依存の距離，または何回ループ運搬依存と定義することもある．現実にはループ繰り返しに一次線形で係数は定数である場合しか解析できる見通しはない．

a.依存の有無

配列の添え字についてループ繰り返し範囲で同じ要素(アドレス)をアクセスするか？

GCDテスト

b.依存の方向，回数

ディオファントスの整数方程式を解く．(Banerjeeテスト)

しかし，この方程式を一般的に(汎用的に？)解くような方法を採用しても，よく論文や教科書にあるようなa[2*i-1]とa[4*i-7] 10≦i≦20とか，a[3*i-5]とa[6*i] 30≦i≦100などというのは現実のプログラムではほとんどありえない．フェーズIで目指している並列化変換を合わせて必要な情報は次のとおりである．（データ通信も自動的に挿入したり，通信の最適化まで行おうとすると，もっと定量的な情報が必要になる．）

・ 依存の方向(どちらが始点でどちらが終点か？)

・ 依存の方向の不変／可変（ループの途中で依存の方向がかわるか？極端な例だと一方がループ可変添え字で他方がループ不変添え字の場合など）

・ バッグエッジを通るのはただ1回か，それ以上か（それ以上になることがありうるか？条件文の下に変数定義がある場合の変数など．）

→ ループ２回にまたがり連続してアクセス1回の場合はloop alignment(ループ半周シフト)やレジスタ割り当てに使える．

(６)連続／不連続

情報の確からしさ？を示す指標が場合によっては必要になる．基本的にコンパイラの変換はオリジナルの文脈を守るために安全側に倒すので，一般に可能性がある依存は全て検出する．そこで，その依存が確実に存在する依存関係なのか，可能性がある依存関係なのかを示す．これは，条件分岐によりループ運搬依存の始点と終点が，ループ出口をdominateしていない場合と，添え字の解析ができない場合と主に２つの要因がある．

さらに不確定な場合で，次の場合を特定するための区分けが必要である．（言葉が適切ではないかもしれないが (７)始点と終点が互いにdominateしているか否かを表す支配／非支配）

loop ( condition ) {

・・・

if ( condition ) {

s=s+x(i); ループ内で他にｓの定義・使用はない．

}

}

これは，並列処理においても総和型と認識できれば並列処理できるが，依存の種類からだけだとループｎ回運搬される不確定フローと逆依存が検出され何もできなくなる．部分和にリダクション命令を使うのが目的である．

１.３ 領域情報と依存情報の関係と繰り返しに関する並列化可否

・ 変数について

対象ループのある繰り返しで次の条件のいずれかに当てはまる場合はループ運搬依存があり，並列化不可となる．

(1) MOD集合とEUSE集合に共通する変数がある→ループ運搬フロー依存がある

Fig.6の例では，MODとEUSEに共通する変数は，インダクション変数iとqがあり，これらに関してループ運搬フロー依存があることがわかる．

(2) MOD集合とUSE集合に共通する変数がある→ループ運搬逆依存がある

Fig.6の例では，MODとUSEには共通する変数KCがある．

(3) MOD集合に変数がある→ループ運搬出力依存がある．

・ 配列について

基本的には，変数と同様だが,上記の条件を満たしても添え字の値により参照範囲が異なるため次の場合はループ運搬依存がないと判定する．

(4) ループの各繰り返しで，(1)〜(3)の条件を満たした参照範囲が同一で，かつこの参照範囲がループ可変で各繰り返しでは重なりが無い → ループ独立

(5) 対象ループの全繰り返しで，参照範囲に重なりが無い．→ 無関係

以上が並列化可否の判定の原則であるが，これを適用すると厳しすぎる．結果として並列化可能と判定できるループがほとんどなくなってしまう．そこで，次の２章に示す並列化変換といくつかのループ構造変換を行って，並列化可能ループを検出する．

Fig.6の例だと，MODとEUSEに共通するのはインダクション変数iとｑである．iについては，2章で述べるインダクション変数変換により並列化可能とすることができるが，qについては，ループのｎ回にまたがるループ運搬フロー依存があり，これが並列化阻害要因となる．

実際にはqの定義や使用の発生する条件を調べると静的にもループ運搬フロー依存がないことがわかるが，フェーズIではそこまで解析することはできない．フェーズIIで実行時の情報(プロファイルを作る)を用いるような解析方法を取り入れた場合は対象とする．

２．ループの並列化変換

ここに挙げた３つの変換は最低限行わないと，逐次に記述されたプログラムから並列化可能なループを見つけるのは実質的には不可能である．

２.１ インダクション変数変換

(1) 適用条件

インダクションという言葉を使ってしまったが，スカラ最適化で言うところのインダクション変数と少し異なる．ここでは，ループ繰り返し回数を用いて表現できる変数(等差級数や等比級数)のことである．したがって，条件文の下にあるi=i+1のような基本インダクション変数やその家族は対象としない．

基本最適化で検出された基本インダクション変数のうち，対象ループ内でループ出口をdominateしているただ一つの定義をもつ基本インダクション変数とその家族を対象とする．

(2) 変換処理

並列化対象ループに初期値0，増分値１の基本インダクション変数rとその計算コードを生成する．

このeの計算は並列実行の外側で計算し，結果を並列処理プロセス？に対するパラメタのようにしたい．

(1)で検出したインダクション変数とその家族を，帰納的な計算式からこのrを用いた繰り返しに独立な計算式に変換する．

i=i+1 → i = r + i₀ (ループ直前のiの値) ループの入り口にある

i = r +1+ i₀ (ループ直前のiの値) ループの出口前にある

ループの途中にある場合も考えられるので，ループの出口に統一したい．定義点から出口までの参照には右辺式を伝播させる．

j=c*i+k → j = c* ｒ+ k+ c*i₀ (ループ直前のiの値)

j=j+k → j=k*ｒ+ j₀ (ループ直前のjの値)

j=c*j → j=c**r* j₀ (ループ直前のjの値)

Fig.6の例のある，MODとEUSEに共通するインダクション変数iに関がこの変換対象であり，帰納的な定義からループの繰り返しに独立な定義にすることができる．

２.２ 変数・配列の拡張(private化)

(1)適用条件

a. 対象ループの全繰り返しのDDEFとUSEの両方に含まれている変数

（→ LIVEにある場合は最終回の値を元の変数に代入する終値保証が必要である．

whileループやuntilループのようにループボディ実行中に最終回であることがわからない場合は，LIVEに含まれていると，適用対象外となって，並列化阻害要因となる．）

b. 対象ループの全繰り返しのMOD (DDEFにはない) とUSEの両方に含まれている変数で，EUSEとLIVEには含まれていないもの

（→ LIVEになければ終値を保証する必要はないので出口をdominateしてなくてもいい，）

ここでは変数と書いたが，外側ループについては，内側ループで作業的に使われている領域を持った配列も対象とする．

Fig.6の例では，DDEFとUSEには共通する変数KCがある．KCはDDEFに含まれており，ループ最終回の定義値を終値とすればよいことがわかるため，この変数がLIVEに含まれていても配列化することができる．

(2)変換処理

変数の場合は一次元の配列にする．添え字は前述の基本インダクション変数eを使う

配列の場合は次元を一つ増やす

LIVEに含まれている場合は，終値保証を行う中間語を生成する．(ループ最終回の代入文の値を元の変数や配列に代入する．)

変数の名称変換と拡張(private化)

・ 変数に関してフロー依存の連結成分を検出し，各連結成分ごとに，名称(異なる作業変数を割り当てる)をつける．すべての依存関係が確定していることが条件

・ 各連結成分ごとに，次の規則により2.1のインダクション変数rを用いて添え字を決める

ループ運搬フロー依存(確定)の始点となる定義変数は，r+1

ループ運搬フロー依存(確定)の終点となる参照変数はr

ループ運搬フロー依存(確定)の始点となることはない定義変数はｒ

ループ独立フロー依存(確定)の終点となる参照変数は，その始点となる定義変数の添え字と同じ．

・ 当該変数がEUSEにも含まれている場合，ループの外の定義が届いている参照については，

作業変数[０] = 元の変数 の初期値保証の代入文をループヘッダーに作る．

・ 当該変数がLIVEにも含まれている場合は，

元の変数＝作業変数[ループ繰り返し回数(+1)]の終値保証の代入文をループの直後に作る．

（先の条件により，必ず定義がループ出口をdominateしているはず）

変数がEUSEにも含まれる(ループ運搬フロー依存がある)場合は，拡張しても並列化することはできないが，後に示すloop-alignmentを行うためには，この並列化変換が必要になる．

内側ループで作業用に使われている配列を，外側ループで並列化する場合の拡張や適用条件についてまた検討していない．

２.３ リダクション演算の変換

総和，最大値(インデクス)検索，最小値(インデクス)検索

最内側ループについてはベクトルコンパイラでかなり広範囲に検出したのとほぼ同じ手法でよいと考えるが，多重ループでこのようなリダクション処理を行っている場合については，未検討．

検出したリダクション演算いついては，システム関数呼び出しの形式のHIRに変換する．

３．ループの構造変換

道具として用意すれば，望ましいループの構造変換を次に挙げる．ただし，フェーズIでは，同期／通信無しの並列化ループを検出するということから，loop-alignmentをとりあえず実現することを考える．将来的にはこの程度のレパートリは用意したほうがいい．（与えられたソースとターゲットマシンに応じてどれを適用するかの判断もフェーズIIへの検討課題となる．）ただし，単純なループ展開はデータフロー情報が不要であること，行って損になるケースが考えにくいこと(恐らくターゲットマシンに依らず)，から基本最適化として，並列化フェーズに入る前に実施されていることを期待する．

３.１ ループ展開（短ループ解消，loop-peeling(ループ皮むき)，インダクション条件展開）

３.２ loop-alignment (ループ半周シフト) →詳細はこちら(全国大会予稿)

３.３ ループの斜め変換(hyper line, hyper plane)

３.４ ループの密多重化（外側ループのループ分割）．

３.５ ループ交換

３.６ ループ外側展開

３.７ ループ融合

３.８ ループ一重化