(57)【特許請求の範囲】
【請求項１】
分散メモリーと並列プロセッサ構造を有するコンピュータ上で実行するためデータ並列言語で書かれたプログラムをコンパイルするための、次の段階を含む最適化コンパイル方法：
前記プログラムのアレイ分散型グラフ表現を作成する段階と、
前記プログラムの多次元アレイ値オブジェクトを各々整列させてこれらオブジェクト各々の軸の各々が対応するＮ次元テンプレートの軸と整列しかつ前記対応する軸に沿った前記テンプレートのストライドの整数倍のストライドを有するようにする段階であって、Ｎは最大の次数を有するプログラムオブジェクトの次数とすることと、
前記テンプレートの１つまたはそれ以上の軸にわたって前記アレイ値オブジェクトの少なくとも幾つかを複製してブロードキャスト通信の総量を最小化する段階と、
前記プログラムの各アレイ値オブジェクトの各軸上の原点について前記テンプレートの対応する軸の原点に対するオフセット整列を求め、前記軸の各々について前記オブジェクト間のオフセット通信の総量を最小化する段階と、
反復制御フローに関係するオブジェクトのオフセット整列を動的に再調整して前記制御フローの全ての反復について加算したときの前記軸の各々に於ける前記オブジェクト間のオフセット通信の総量を最小化する段階。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は分散メモリーと並列プロセッサ構造を有するコンピュータ上で実行するためのデータ並列言語（本明細書においては「アレイ並列言語」とも称する）で書かれたプログラムのコンパイルに関し、より特定すれば、並列演算のオペランドを実行可能コード内で相互に整列させるのに必要な剰余通信量を減少させるためのコンパイラ最適化技術の改良に関する。
【０００２】
【従来の技術】
ＦＯＲＴＲＡＮ９０などのデータ並列言語を分散メモリー並列プロセッサ型コンピュータでコンパイルする際、アレイなどの集合データオブジェクトはプロセッサメモリーに分散される。この割り当てが並列演算のオペランドを相互に整列させるのに必要とされる剰余通信量を決定する。一般的な方法は割り当てを２段階に分割することで、第１にカルテシアン指数空間内の中小テンプレートにオブジェクトを全て割り当てる「整列」相、第２にテンプレートをプロセッサに割り当てる「分散」相からなる。整列相ではプログラム内のアレイオブジェクトを相互に全て配置して再整列にかかる通信コストを減少させるようにする。次に、分散相ではテンプレートに併せて整列したオブジェクトをプロセッサに分散する。つまり、２段階割り当て方法では言語の問題を処理装置の問題と切り離し、結果としてデータオブジェクトの整列が装置に依存しないことが理解されよう。
【０００３】
【発明が解決しようとする課題】
コンパイル最適化の重要な目標は「完了時間」（「ランタイム」と称することもある）を減少させるデータ及び作業割り当てを生成することである。完了時間は計算と通信の２つの要素を有する。通信はさらに、「固有」及び「剰余」通信の２つの独立したクラスに分けられる。固有通信は約分などの計算演算で発生し、演算の本質的部分としてデータの移動を必要とする。一方の剰余通信はオペランドが同一のプロセッサに割り当てられていないような計算に必要とされる非局部的なデータ参照で発生する。
【０００４】
【課題を解決するための手段】
本発明は整列の問題に焦点を当てている。つまり、本開示を要約すると、そのデータオブジェクトが前述の形式のコンピュータのプロセッサに対して同一に割り当てられるのはオブジェクトが整列している場合に限られると仮定することになる。述語「再整列」は誤整列による剰余通信をあらわし、最適化の目標は再整列コストを最小限に抑えるアレイ整列を提供することであると理解されるべきである。
【０００５】
数名の研究者は静的配列を考案した。事実、本発明は本発明の発明者が発表した静的配列の業績を拡張して移動性の（ｍｏｂｉｌｅ）配列を取り扱えるように拡張したものである。クノーブ、ルーカス、デリー（Ｋｎｏｂｅ，  Ｌｕｋａｓ，  ａｎｄ  Ｄａｌｌｙ  ）による動的配列案とは異なり、本発明はオブジェクトの整列がループ誘導変数（ＬＩＶ）のアフィン関数であるようなループにおける移動性の配列に関するものである。
【０００６】
本発明は分散メモリーと並列プロセッサ構造を有するコンピュータ上で実行するためのデータ並列言語で書かれたプログラムをコンパイルするための最適化コンパイラを提供する。このコンパイル方法には、（１）コンパイルしようとするプログラムのアレイ分散型グラフ表現を生成することと、（２）そのプログラムの多次元的アレイ評価した各々のオブジェクトを整列させて、これらのオブジェクト各々の夫々の軸が対応するＮ次元テンプレートの軸と整列するようになし、また対応する軸に沿ってテンプレートの間隔の整数倍のストライドを有するようにし（ここでＮは最大の次数を有するプログラムオブジェクトの次数である）、（３）テンプレートの１つまたはそれ以上の軸を横断してアレイ評価オブジェクトの幾つかまたは全部を複製（ｒｅｐｌｉｃａｔｅ）  しブロードキャスト通信の総量を最小化することと、（４）前記テンプレートの対応する軸の原点に対してアレイ評価オブジェクト各々の原点について、テンプレートの各軸上でオフセット整列を見つけ出し、テンプレートの軸の各々についてアレイ評価オブジェクト間のオフセット通信の総量を最小化することと、（６）反復制御の流れに関係するオブジェクトのオフセット整列を動的に再調整して前記制御の流れの反復毎に加算した場合前記軸の各々に於けるオブジェクト間でのオフセット通信の総量を最小化することによる。
【０００７】
【実施例】
図１は分散メモリーと並列プロセッサ構造を有するコンピュータのプロセッサ上にアレイ並列言語で表現されるようなプログラムオブジェクトを割り当てるための標準的２相コンパイラのモデルを模式的に図示している。
【０００８】
図２は分散メモリー並列プロセッサ構造を有するコンピュータで実行するためのアレイ並列言語で書かれたプログラムをコンパイルするために本発明で用いる段階の基本的順序を示す。
【０００９】
図３は簡単なＦＯＲＴＲＡＮ９０のプログラムである。
【００１０】
図４は高性能ＦＯＲＴＲＡＮ指令（Ｈｉｇｈ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｆｏｒｔｒａｎ  ｄｉｒｅｃｔｉｖｅｓ）を用いることによる図３に図示したプログラムの移動性の整列を示す。
【００１１】
図５Ａと図５Ｂは「ｄｏ」ループのそれぞれ第１と第５の反復での図３に図示したプログラムのための移動性の整列を示す。
【００１２】
図６は図３に図示したプログラムのための整列分散グラフ（ＡＤＧ）である。
【００１３】
図７は図３に図示したプログラムの代表的部分についてのＡＤＧ辺の反復空間のラベルつけを示す。
【００１４】
図８は図８に含まれるプログラム断片についてのＡＤＧ辺のデータ重み付けのラベルつけを示す。
【００１５】
図９は図７及び図８に含まれるプログラム断片について本発明で提供する移動性のオフセット整列を示す。
【００１６】
本明細書は次のような構成になっている。第１節では基本的概要を提供する。第２節は整列の記法を形式化し移動性の整列を定義する。また整列の問題を取り扱うためのグラフモデルも導入する。第３節は移動性のストライドの整列を扱う。第４節では固定長と可変長のオブジェクトについてと、ループのネスト（入れ子）構造について、移動性のオフセット整列を取り扱う。第５節では複製したオフセット整列の処理を説明する。第６節では幾つかのさらなる観察結果を提供する。第７節では本発明で整列を最適化するために用いているグラフモデルのさらに詳細な説明を提供する。
【００１７】
１．概要
図１に図示したように、「整列」はデータアレイ２１のいずれか１つの要素の各々をテンプレート２２のセルに割り当てる割り当て方法である。テンプレート２２はプログラム内の最高次数のアレイオブジェクトと同じだけの次数を有するため概念的には無限のカルテシアン格子である。実際に、プログラム内のアレイオブジェクト全部を相互に配置する一枚の「グラフ用紙」で、テンプレート２２の各々の次元を表わすことができる。コンパイル方法の整列相はプログラムのアレイオブジェクト２１を全部テンプレート２２に整列させる。次に分散相でテンプレート２２の各々のセルを標的マシン２３の実際のプロセッサへと割り当てる。
【００１８】
図２を参照すると、本発明のコンパイル方法は一連の段階からなることがわかる。第１に、原始プログラムの整列分散グラフ（ＡＤＧ）を段階３１で生成する。次に、データオブジェクトは段階３２で、その軸とストライドをテンプレートの軸及びストライドに対して全ての軸で同時に整列させる。次に、ＡＤＧの各々のポートがテンプレートの軸に対して１つづつ複製するかまたは複製しないかを識別すべきかの決定を段階３３で行なう。複製した終点を有する全ての辺は後述するような理由から破棄することができるためＡＤＧの簡略化が行なえることがある。後でわかるように、複製のラベルつけ段階３３はプログラム実行中のブロードキャスト通信のコストを最小化するものである。コンパイル処理のこの相の間に発見した全ての複製の範囲を求める必要はない。実際に、複製した整列の範囲は後続の格納最適化相の間に生成することができる（段階３５参照）。複製ラベル付けのあと、オフセット整列（移動性の何らかの整列を含む）がテンプレートの軸１つづつについて決定される。この後、段階３５で示したように、テンプレートに整列したデータオブジェクトは最適な格納のため標的マシンのプロセッサの分散に併せて分散される。最後に、コード生成段階３６で標的マシン用の実行可能コードが生成される。
【００１９】
２．整列の問題
Ａをｄ次元のアレイとし、ｆ１  からｆｔ  を整数評価関数とすれば、
Ａ（ｉ１，．．．，ｉｄ  ）＃Ｔ［ｆ１（ｉ１，．．．，ｉｄ  ），．．．，ｆｔ  （ｉ１，．．．，ｉｄ  ）］
は、Ａの特定の要素がｔ次元のテンプレートＴの特定の要素と整列されていることをあらわしている。場合によっては複数のテンプレートを用いることもあるが、本明細書では単一のテンプレートに対する整列を考えることにする。つまり、テンプレート名を無視することができるので、式をいくらか簡略化して、Ａ（ｉ）＃［ｆ（ｉ）］とすることができる。ここでｉはｄベクトル、ｆはｄベクトルからｔベクトルへの関数である。
【００２０】
ここで、データアレイの各々の軸がテンプレートの別の軸に割り当ててあり、アレイの要素がテンプレート軸に沿って等しい間隔で並んでいるような整列を考えてみると、このような整列は３つの要素を有することが明らかとなろう。３つの要素とは、「軸」（テンプレート軸へのアレイ軸の割り当て）、「ストライド」（テンプレート軸各々に沿ったアレイ要素の間隔）、「オフセット」（テンプレート軸各々に沿ったアレイ原点の位置）である。従ってｆｋ  の各々は定数ｏｋ  またはｓｋ  ｉａｋ＋ｏｋ  の形の単一アレイ指数の関数のどちらかである。アレイはテンプレートへ１対１で整列させてある。後でわかるように、この表記法は後述の第５節で、幾つかのテンプレート軸にわたってアレイを複製し得るような１対多整列に拡張する。
【００２１】
アレイ評価オブジェクト（略してオブジェクト）は要素的または転換的なアレイの演算によって、さらにアレイの一部に対する整列ごとに作成される。本発明のコンパイル処理はプログラム変数の各々についてではなく、プログラムの各オブジェクトについて整列を求める。ループ内のオブジェクトの整列はループ誘導変数の関数であるから、このような整列は「移動自在」であると本明細書で称する。
【００２２】
２．１．例
以下に各種の整列の例を挙げる。
【００２３】
例１（オフセット整列）：
Ａ（１：Ｎ−１）＝Ａ（１：Ｎ−１）＋Ｂ（２：Ｎ）
というステートメントを考えてみる。整列がＡ（ｉ）＃［ｉ］かつＢ（ｉ）＃［ｉ］なら、もっとも近い隣への１単位のシフトが必要である。しかしＡ（ｉ）＃［ｉ］かつＢ（ｉ）＃［ｉ−１］なら、ステートメントは通信なしで実行可能である。
【００２４】
例２（ストライド整列）：
Ａ（１：Ｎ）＝Ａ（１：Ｎ）＋Ｂ（２：２＊Ｎ：２）
というステートメントを考えてみる。整列がＡ（ｉ）＃［ｉ］かつＢ（ｉ）＃［ｉ］なら、ＡとＢの一部を一緒に取り出すには一般的通信が必要である。しかし整列がＡ（ｉ）＃［２ｉ］かつＢ（ｉ）＃［ｉ］なら、通信を回避できる。
【００２５】
例３（軸性列）：
Ｂ＝Ｂ＋置換（Ｃ）
というステートメントを考えてみる。ここでＢとＣは２次元アレイとする。整列がＢ（ｉ１，ｉ２  ）＃［ｉ１，ｉ２  ］かつＣ（ｉ１，ｉ２  ）＃［ｉ１，ｉ２  ］なら、Ｃの置換には一般的通信が必要である。しかし整列がＢ（ｉ１，ｉ２  ）＃［ｉ１，ｉ２  ］かつＣ（ｉ１，ｉ２  ）＃［ｉ２，ｉ１  ］なら、オペランドは整列し、通信は必要ない。
【００２６】
例４（移動性のオフセット整列）図３のプログラムを考えてみる。Ａ（ｉ１，ｉ２  ）＃ｋ  ［ｉ１，ｉ２  ］かつＶ（ｉ１  ）＃ｋ  ［ｋ，ｉ１−ｋ＋１  ］なら、最適化して実行できる。記号の＃ｋ  はＬＩＶｋ  に配列が依存していることを強調するために用いている。
【００２７】
例５（移動性のストライド整列）：次のようなコード断片を考えてみる。
0003594656.tif 000002
さらに、Ａ（ｉ）＃ｋ  ［ｉ］かつＢ（ｉ）＃ｋ  ［ｉ］と仮定する。ストライド整列Ｖが静的なら、Ｖのどの整列も反復あたりの一般的通信コストが２回で、等しく良好である。しかし移動性のストライド整列Ｖ（ｉ）＃ｋ  ［ｋｉ］では反復あたりの一般的通信が１回と、通信コストが下がる。
【００２８】
２．２．整列分散グラフ
本発明を実現するために重要なツールは「整列分散グラフ」または略してＡＤＧと呼ばれる変更注釈を加えたデータの流れ図である。この節ではＡＤＧを定義し整列の問題をどのようにＡＤＧ上の最適化の問題として記述すべきかを示す。
【００２９】
図６は図３に図示したプログラムのためのＡＤＧである。ＡＤＧ内のノードは計算をあらわし、辺はデータの流れをあらわす。整列は辺の終点に関係するのでこれを「ポート」と呼ぶことにする。ノードはこれのオペランドと結果を表わすポートの相対的整列を制限する。辺はポートが異なる整列を有する場合剰余通信コストを担う。目標はノードの制約を満たし全体的な辺のコストを最小化するポートについての整列を提供することである。例えば、図９に図示した図６のＡＤＧの一部において剰余通信コストを担う唯一の辺は変換ノード４２と併合ノード４３をつなぐ辺４１である。辺４１はオブジェクトのオペランドを位置（ｋ−１，−ｋ＋１）から（ｋ，−ｋ＋２）への再整列を必要とするため剰余通信コストが存在する。
【００３０】
２．２．１．辺
ＡＤＧは各々の（静的）定義またはオブジェクトの使用についてポートを有している。辺はオブジェクトの定義と使用を結合する。複数の定義または使用は後述するとおり併合と論理出力数（ファンアウト）で扱う。つまり各々の辺は正確に２つのポートを有する。整列相の目的は各々のポートを図９に示すように整列にラベル付けすることである。再整列に必要な全ての通信は辺に関係する。辺の２つのポートが異なる整列を有する場合、辺は整列とプログラム実行中にその辺に沿って流れるデータの総量に依存するコストを被る。
【００３１】
２．２．２．ノード
あらゆるアレイ演算は、各オペランドに１つのポートと結果に１つのポートを有するＡＤＧのノードである。図６は５１に示すような要素幅での加算をあらわす「＋」ノードの例と、入力がアレイで出力がアレイ５２と５３の一部となる「部分」ノードと、入力がアレイとアレイの一部を置換するための新しいオブジェクトで、出力が変更されたアレイである「部分割り当て」ノード５４を含む。部分割り当ては前出のサイトロンら（Ｃｙｔｒｏｎ  ｅｔ  ａｌ．  ）が「更新」と称しているものである。
【００３２】
図６は、値の一回の使用で複数の定義に到達し得る場合には、４３と５５に示すように、各々の定義ごとに１つのポートと使用に対して１つのポートを有する「併合ノード」をＡＤＧが含むことも示している。このノードは前出のサイトロンら（Ｃｙｔｒｏｎ  ｅｔ  ａｌ．  ）のいわゆるφ関数に対応する。逆に、一回の定義が複数の使用に達するような場合には、ＡＤＧは５７と５８に示すような「ファンアウト・ノード」を含む。ファンアウト・ノードは、定義した位置から使用する位置へオブジェクトを通信するための最適なファンアウト・ツリーを求めるためのいわゆる「シュタイナー最適化」の機会をあらわしているが、その対象の詳細は本発明の範囲を超えている。最後に、ループを有するプログラムのためのＡＤＧは図６の４２、６１、６２、６３、６４、６５で示すように、後述するような反復空間を制限する「変換ノード」と、反復の結果を条件分岐するために６６、６７で示すような分岐ノードをともに含んでいる。
【００３３】
ノードはポートの整列を制限する。要素幅の演算をあらわすノード例えば「＋」ノード５１などは、これのポート全部が同一の配列を有するように制限している。併合、分岐、ファンアウト・ノードも同じ制約がある。
【００３４】
Ａが２次元テンプレート内の２次元アレイだとすると、ノード「置換（Ａ）」（図示していない）は出力が入力と対向する軸整列を有するように制限しており、アレイを置換するのに必要なあらゆる通信をノードそれ自体にではなく入力または出力の辺に割り当てている。部分及び部分割当ノードはアレイ全体の位置に対する部分の位置を記述するような制約を果している。例えば、部分Ａ（１０：５０：２）のノードが出力に入力と同じ軸、入力のストライドの２倍、かつＡとＡのオフセットを足したものの１０倍に等しいオフセットを有するように制限している。
【００３５】
２．２．３．反復空間
後にわかるように、ＡＤＧはデータの流れをあらわしており制御の流れをあらわしてはいない。通信コストを正確にモデル化するには、プログラム実行中に特定の辺をデータが複数回流れることがあり、毎回データオブジェクトの大きさが異なる場合があると考える必要がある。
【００３６】
ｋループの入れ子（ネスト）内部の辺はｋ次元の反復空間とラベルをつけてあり、その要素はＬＩＶが取る値のベクトルである。辺にあるデータオブジェクトの寸法とポートにあるデータオブジェクトの整列は両方ともＬＩＶの関数であるから、反復空間で変化することがある。
【００３７】
すでに指摘したように、ループの内部、外部、または周辺にデータを抱えている全ての辺では、２つのポートの反復空間の間の関連性を記述するための、図６で４２、６１、６２、６３、６４、６５として表わしたような変換ノードが存在する。「ｄｏ  ｉ＝ｌ：ｈ；ｓ」ループ内のループバック変換ノードは、ｉ＋ｓの関数として入力の整列がｉの関数として出力の整列に等しくなるように制限している。例えば、図６に示したような（ｋ／ｋ＋１）変換ノードを考えてみる。入力（「ｋ」）ポートでの２ｋ＋３と出力（「ｋ＋１」）ポートでの２ｋ＋１のオフセット整列はノードの制限を満たしている。このループの入り口にある（−／１）変換ノードは入力位置（ｋに依存しない）がｋ＝１での出力位置と等しくなるように制限している。
【００３８】
２．３．コストモデル
図７から図９を参照してＡＤＧに関する代表的なプログラムの通信コストについてより詳細な説明を行なう。「位置」は規則に適合した整列の符号化である。さらに、２つの位置ｐとｑの間の「距離ｄ（ｐ，ｑ）」はアレイの位置をｐからｑに変換する要素当たりのコストを与える常に正の数である。つまり、全ての位置の組は距離関数ｄのもとの距離空間である。
【００３９】
本明細書ではｐ＝ｑのときｄ（ｐ，ｑ）＝０かつｄ（ｐ，ｑ）＝１となる「ディスクリート換算」を使用する。さらに、ｐとｑが格子上の点であってｄ（ｐ，ｑ）がこれらの間のＬ１  （またはマンハッタン）距離となるような格子換算も使用する。ディスクリート換算は、軸またはストライドの何らかの変化には一般的通信が必要なことから軸とストライドの整列をモデル化する。一方格子換算はオフセット整列をモデル化する。グリッド換算が「分離可能」つまり多次元格子の２点間の距離が一次元格子内でこれらに対応する座標間の距離の和に等しいことに注意すべきである。この特性により、オフセット整列の問題はテンプレート２２の各々の軸とは切り離して解決することができる。
【００４０】
プログラムの通信コストは次のようにモデル化される。ΕをＡＤＧ辺の組とし、Ιｘｙを辺（ｘ，ｙ）の反復空間とする。Ιｘｙのベクトルｉについて、ωｘｙ（ｉ）  を辺の重みつまり反復ｉにおける辺（ｘ，ｙ）でのデータオブジェクトの寸法であるとする。最後に、πをそのプログラムに適当な移動性の整列、即ち、各ポートｘについて、πｘ  （ｉ）  をノードの制約を全て満たすような反復ｉでのｘについての整列とする。よって反復ｉにおける辺（ｘ，ｙ）の再整列コストはωｘｙ（ｉ）  ・ｄ（πｘ  （ｉ），πｙ  （ｉ））で、プログラムの全再配列コストは、
【数１】
0003594656.tif 000003
となる。目標はノードの制約の対象となる通信コストを最小化するようにπを選択することである。
【００４１】
２．４．移動性の整列関数にかかる制限
これまでは移動性の整列が取り得る形態が制約されないものと仮定してきた。理論上、これらの整列はＬＩＶの恣意的関数であるが、分析することは不可能である。従って、加工性の点から、本発明では移動性の整列がＬＩＶのアフィン関数となるように制限している。つまり、深さｋのループのネスト内部にあって、ＬＩＶがｉ１，．．．，ｉｋ  のオブジェクトについての整列関数は、α０  ＋α１  ｉ１  ＋．．．．＋αｋ  ｉｋ  の形を取る。ここで係数ベクトルα＝（α０，．．．，αｋ  ）が求めなければならないものだとする。この整列はｉ＝（１，ｉ１，．．．，ｉｋ  ）とするとベクトル表記でαｉＴ  と簡潔に表現することができる。αとｉはどちらも（ｋ＋１）ベクトルである。理解されるように、これは全てのループの外部にあるオブジェクトについて定数項α０  を減少させる。
【００４２】
同様にして、オブジェクトの範囲はＬＩＶ内でアフィンとなるように制限されるので、オブジェクトの大きさはＬＩＶ内の多項式となる。
【００４３】
３．移動性のストライド整列
ディスクリート換算を用いてストライドの変化によって発生する通信コストをモデル化する。辺のポートにあるストライドをαｉＴ  およびα’ｉＴ  とする。α＝α’なら、ポートは全ての反復で整列していることになる。逆に、定数項α０  とα’０は異なっているがそれ以外の全ての要素が等しいとき、ポートは常に不斉整列にある。これ以外の全ての場合では、辺のポートはほとんど常に不斉整列である。つまり、α＝α’でない限りあらゆる反復でオブジェクトは不斉整列していると考えられる。
【００４４】
式（１）の距離関数がＬＩＶとは不関であることから、反復空間にわたる加算の外部へ移動することができ、これによって辺（ｘ，ｙ）の通信コストを重みと距離の積として表現することが出来るようになる。距離は（ｋ＋１）ベクトルのディスクリート換算だが、重みは全反復にわたって各々の反復でのオブジェクトの大きさについての和、すなわちＷ＝Σｉ  ∈Ｉｘｙωｘｙ（ｉ）  である。重みはＬＩＶ内の多項式で表わされることから、和は閉じた項で評価できる。
【００４５】
４．移動性のオフセット整列
オフセット整列αｉＴ  を有するオブジェクトを考える。問題は分離可能なので、オフセットは一度に１つのテンプレート軸に対して決定することができる。コード内にループが存在しなければ、静的オフセット整列についての先の解決法に解決法を帰納することができる。前出のシャターヘら（Ｃｈａｔｔｅｒｊｅｅ  ｅｔ  ａｌ．  ）を参照されたい。
【００４６】
剰余通信に対する辺（ｘ，ｙ）の分散は、
【数２】
0003594656.tif 000004
但し、πｘ  ＝α、πｙ  ＝α’、またＩｘｙは辺に関係する反復空間である。ωｘｙ（ｉ）  が定数であっても、式（２）の絶対値は閉じた形を複雑にする。従って、このコスト関数を最小化するためのアルゴリズムを提供するのではなく、解法が簡潔な式でこれを近似する方が望ましい。
【００４７】
４．１．線型プログラミングによるオフセット整列
周知のように、格子換算についての静的オフセット整列の問題は線型プログラミングに還元できる。例えば、整数πｘ  をポートｘのオフセット整列とする。次に剰余通信コスト（即ち最小化すべき関数）がＣ（π）＝Σ（ｘ，ｙ）  ∈Ｅ  Ｃｘｙ（π）だとすると、結果的に、
【数３】
0003594656.tif 000005
となる。
【００４８】
想起されるだろうが、ＡＤＧ内のノードは線型等式の制約を導入する。つまり目的関数から絶対値を除去するには、変数θｘｙがＡＤＧの全ての辺（ｘ，ｙ）に導入され、２つの不等式の制約が追加される。つまり、
θｘｙ＋πｘ  −πｙ  ≧０
θｘｙ−πｘ  ＋πｙ  ≧０
これはθｘｙ≧｜πｘ  −πｙ  ｜を補償するものであるから、前出の等式の目的関数は、
【数４】
0003594656.tif 000006
となる。
【００４９】
最適化においてθｘｙ＝｜πｘ  −πｙ  ｜であるため、変換した等式はもとの等式と等しい。理解されるように、変換によって｜Ｅ｜の新しい変数と２｜Ｅ｜の新しい制約が導入される。
【００５０】
線型プログラムから得られるオフセットが小数であれば、整数に丸められる。丸めた解は必ずしも最適な整数解ではない。実際に一般的には、線型プログラミング（ＬＰ）の解を丸めることで適切さすらも保存されないことがある。しかし、格子換算を伴うオフセット整列の場合には、丸めが合理的な解法であることが示される。明らかに、オフセットを丸めて全てのノードの制約を満たすようにするのが簡単である。さらに、テンプレート２２（図１）は辺のコストが連続的な実数値をとるオフセットの連続関数であるような連続的Ｌ１  換算空間へのディスクリート近似と考えられる。丸めていないＬＰはこの問題を正確に最適化するので、ディスクリート最適化は丸めに対してそれほど敏感ではないと思われる。利便のため、このアルゴリズムを丸め線型プログラミングまたは略してＲＬＰと称することにする。さらに言及すれば、混合した整数線型プログラミングの使用による実験もこの条件下では非常に効率が良いと思われる。
【００５１】
４．２．固定長オブジェクトと移動性のオフセット整列のための１回だけネストしたループ
この節では辺（ｘ，ｙ）のデータの重みが定数で、かつ（Ｗｌｏｇ  ）が１に等しく、Ｉｘｙ＝ｌ：ｈ：ｓと仮定する。（α−α’）ｉＴ  を辺（ｘ，ｙ）のスパンと呼ぶことにする。間隔［ｌ，ｈ］でスパンの符号が変化しないなら、前述の式（２）の和と絶対値は互換性がある。言い換えれば、前述の条件下で、Ｃｘｙ＝｜Σｉ  ∈ｌ：ｈ：ｓ  （α−α’）ｉＴ  ｜、またこれの閉じた形態は次のようになる。
【数５】
0003594656.tif 000007
【００５２】
式（３）の絶対値の内側の項は辺（ｘ，ｙ）から測った平均距離である。これは辺あたり１つの新しい変数を有するＲＬＰに還元できる。
【００５３】
しかし一般に、反復空間内でスパンの符号が変化することがあるので、和と絶対値の互換はエラーの潜在的発生源である。従って、エラーを限定するには、反復空間をｍ個の等しい部分範囲Ｉ１，．．．，Ｉｍ  に分割し、各々の部分範囲が一組の連続した反復に対応するようにする。通信コストは次のように分解される：
【数６】
0003594656.tif 000008
【００５４】
従ってどの部分範囲内でもスパンの符号が変化しないと仮定すると近似的コストモデルが導かれ、
【数７】
0003594656.tif 000009
【００５５】
ｍを固定するには式（５）の外側の和を明示的に拡張し、式（４）を用いて各々の内側の和を評価する。明らかに、多くとも１つの部分範囲で、スパンは極性を変化することがあるので、部分範囲の和の少なくとも（ｍ−１）が正しいことになる。結果として、これらの和は辺あたりｍ個の新しい変数を有するＲＬＰに還元できる。ＲＬＰ解で可能なエラーは、ＲＬＰ近似解での通信コストが多くとも（１＋２／ｍ２  ）の係数によるもっとも可能性のある解でのコストを超過していることから制限されることになる。さらに、所望なら、この制限エラーは不等間隔を用いることでさらに減少することができる。
【００５６】
上述の議論は移動性のオフセット整列の問題を解くために可能な幾つかのアルゴリズムを示唆している。これには次のことが含まれる：
１．展開：全ての反復を部分範囲として定義し、ＲＬＰを用いる。明らかとなるように、これはループを展開するのと等価である。これは正確だが反復回数が小さい場合を除けば明らかに非実用的である。
２．状態空間の検索：反復空間を単一の部分範囲として近似し、ＲＬＰを適用する。この解法を初期の推論に用いることで、例えばもっとも急峻な下降で、正確なコストの式（４）を最適化する。
３．ゼロ交差の追跡：反復空間を２個の等しい部分範囲に分割してＲＬＰを用いる。ρｘｙが範囲内にゼロ交差を有する場合にはこれを特定して、部分範囲の境界をこの点と一致するように移動する。しかるのち新しいＲＬＰを解き、収れんするまで反復する。これは各々が２｜Ｅ｜個の新しい変数を有する一連の固定長問題を解くものである。この方法の収れんは保障されない。
４．再帰的精製：反復空間を単一の部分範囲で近似し、ＲＬＰを使用する。解を検証してρｘｙがゼロ交差を有する部分範囲（辺あたり多くて１個）を求める。ゼロ交差で各々の部分範囲を２つに分割し、新しいＲＬＰの式を立てて解く。何らかの停止条件が満たされるまで精製を続ける（例えば、これ以上精製すべき部分範囲がなくなるまで、または目的関数が改善しなくなるまで、または利用可能な時間を超過するまで）。理解されるようにこの技術では一連の次第に大きくなる問題を解く必要がある。
５．固定分割：反復空間を３つの部分範囲に分割してＲＬＰを使用する。得られる解は最適範囲の２２％以内となるように保障される。これには３｜Ｅ｜個の新しい変数を有する単一の問題を解く必要がある。エラー境界が区画数の逆関数として変化することに注意すべきである。例えば、５分割ではエラー境界が５％に減少する。このアルゴリズムは速度、信頼性、品質のバランスがよくとれていることから好適である。
【００５７】
４．３．移動性の整列のための１回だけネストしたループ内の可変長オブジェクト
ここで、Ｉｘｙ＝ｌ：ｈ：ｓ、また反復ｉでの辺（ｘ，ｙ）のデータの重みは、β０  とβ１  を整数の定数とおいて、β０  ＋β１  ｉであると仮定する。辺の通信コストは、
【数８】
0003594656.tif 000010
さらに次のモーメントを定義する：
【数９】
0003594656.tif 000011
【００５８】
このあと、［ｌ，ｈ］でスパンの符号が変化しなければ、辺（ｘ，ｙ）の通信コストは
【数１０】
0003594656.tif 000012
である。
【００５９】
これは、１回ネストしたループでの可変長オブジェクトの整列係数は４．２節で求めたように求めることができることを表わしている。
【００６０】
４．４．ループのネスト
本発明の最適化の方法は次のようにループのネストに対して一般化できる。すでに指摘したように、各々のＬＩＶの指数範囲を３つの部分範囲に適当に分割する。分解のカルテシアン積は反復空間を３ｋ  個の部分範囲に分割しその各々についてスパンに於ける極性が変化しないものと仮定する。つまり、各々の部分範囲でのコストを加算し、これによって近似コストの１つの項を得る。これで４．２節のように近似コスト最小化について解くことができるようになる。
【００６１】
深さがｋのループのネストでは、問題は３のｋ乗｜Ｅ｜個の変数を有する。従って、上述の技術は深いループのネストだとうまく伸縮しない。しかし、すくなくともＦＯＲＴＲＡＮ９０のコンパイルでは、アレイ演算と「ｆｏｒａｌｌ」ループを用いて逐次型言語でのループコードに相当するものを並列に表現しているので、問題になるとは思われない。
【００６２】
カルテシアン積の公式化では不完全かつ台形のループネストを極めて自然に取り扱える。これの鍵はループネストの異なるレベルをつなぐ変換器ノードにある。
【００６３】
５．複製
ここまで、本明細書ではアレイ値オブジェクト２１からテンプレート２２（図１）への１対１割り当てとして整列を取り扱ってきた。この定義を一般化して、１対多の割り当てを含むようにすると、「複製」の概念を取り入れることができる。より特定すれば、複製は１つの位置ではなく一組の位置をとるようなオフセット整列であると定義される。このことについてのこれからの議論では考えられる位置の組み合わせを３つ組ｌ：ｈ：ｓとなるように制限する。
【００６４】
理解されるように、ｔ次元のテンプレートに整列させたｄ次元のオブジェクトはｄ個の「体軸」（これは軸と、ストライドと、オフセットの整列を必要とする）と、（ｔ−ｄ）個の「空間軸」（これはオフセット整列のみを必要とする）とを有する。本明細書で使用している複製の概念では、オブジェクトの空間軸に沿ったオフセット整列を対応するテンプレートの軸の正規断面とすることができる。記号「＊」を用いてテンプレート軸全体にわたる複製をあらわすことにする。例えば、Α（ｉ）  ＃［ｉ，１０］はΑを第２のテンプレート軸に沿った１つの位置に整列させ、Α（ｉ）  ＃［ｉ，１０：２０：２］はΑを第２のテンプレート軸の部分集合と整列させ、Α（ｉ）  ＃［ｉ，＊］は第２のテンプレート軸の全てにわたってΑを複製する。固定オフセットから複製したオフセットへデータが流れる全ての辺でブロードキャスト通信が発生する。
【００６５】
５．１．複製のラベル付け
オフセット整列は「複製のラベル付け」と呼ばれる相から始まり、その目的はＡＤＧのどのポートが複製した位置を有するかを決定することである。この節で複製のラベル付けのために提案しているアルゴリズムは、複製されたかまたは複製されていないかのラベル付けをポートに行なうが、複製の範囲を求めるものではない。その代わり、すでに指摘したように、複製に続く格納最適化相で複製した整列の範囲を精製するのが望ましい。
【００６６】
複製の供給源は３つある：
１．「拡散」演算が複製を発生する場合、
２．参照テーブルがプロセッサ全体にわたって複製されるなら、ベクトル値サブスクリプトが指す参照テーブルを用いるほうが効率的である（しかしこのようなテーブルの複製はプログラマーの許諾を得て行なうことを推奨する）場合、
３．空間字区内に移動性のオフセット整列を有する読み出し専用オブジェクトが複製の間に実現される場合。
【００６７】
これらの供給源が与えられれば、目標は複製すべき他のオブジェクトを決めて、プログラム実行中のブロードキャスト通信を最小化することである。この問題は２つのラベルをとり得る（複製した／複製していない）グラフのラベル付けの問題としてモデル化でき、最小カットの問題として効率的に解けることを示すことができる。
【００６８】
次のような簡単なプログラム、
0003594656.tif 000013
は、複製ラベル付けが有用な理由を示している。この例では、Ａが複製されなければ反復毎にブロードキャストが発生し、一方複製された場合には（ループに入るときに）一回だけブロードキャストが発生する。これは本発明の方法で発見された解である。
【００６９】
複製のラベル付けのあと、複製した終点を有する全ての辺をＡＤＧから破棄し（図６）、これによって第４節で説明したように複製していないポートについてオフセットを見つけ出すことができる。ＡＤＧの簡略化の証明は、テール（後部）を複製した辺では通信を必要としないが、ヘッド（前部）を複製した辺は（複製していない）尾部のオフセットに関わらず同じ量の通信を必要とするということである。
【００７０】
５．２．ネットワークフローによるラベル付け
想起されるように、オフセットは、Ｎ次元のテンプレート２２（図１）の各々の軸について独立的に決定される。ここでＮは最大の次数を有するプログラムアレイの次数である。よって、任意の時刻にラベル付けしようとしている軸を「現在の軸」と称する。ＡＤＧ（図６）の全てのポートは「複製した（Ｒ）」または「複製していない（Ｎ）」のどちらかのラベルをつける必要がある。さらに、このラベル付けに於ける制約は次の通りである：
１．現在の軸が体軸であるポートはラベルＮを有すること
２．現在の軸に沿った拡散のためのノードは入力ポートをＲ、出力ポートをＮとラベル付けすること
３．現在の軸で移動性の整列を有する読み出し専用オブジェクトのポートと、現在軸が空間軸であるポートはラベルＲを有すること
４．サブルーチンの境界にあるポートや複製した参照テーブルを表わすポートなど他の幾つかのポートは特定のラベルを有すること
５．他の全てのノードでは、全てのポートが同じラベルでなければならない。
【００７１】
図８に図示したように、ＡＤＧの各辺はテールを複製しておらずヘッドを複製した（時間に対しての）予想相通信コストをあらわす重みを有している。この辺の重みは全部の反復にわたる通信オブジェクトの大きさの総和である。
【００７２】
オブジェクトはラベル付けの制約を満たすようなラベル付けを求めるべきだが、同時にＮからＲへ向かうポートの辺の重みの和を最小化すべきでもある。詳細については後述するように、これは標準的なネットワークフローの技術で解くことができる最小カットの問題である。
【００７３】
法則１：最適化複製ラベル付けはネットワークフローで発見可能である
証明：ＡＤＧからわずかに変更した版であって重み付けし方向を有するグラフＧは、Ｇの頂点が次のようになるように定義することが出来る：現在軸の拡散を除くＡＤＧの各ノードはＧの頂点である。ノードがＮまたはＲとラベルをつけたポートを有していれば、Ｇの頂点は同じラベルを有する（現在軸の拡散を除くどのノードもラベルの違う２つのポートを有することはできない）。現在軸の拡散各々は各ポートに対して１つずつ、Ｇの２つの頂点に対応し、入力ポートの頂点はラベルをＲとし、出力ポートの頂点はラベルをＮとする。最後に、ＧはラベルＮを有する新しい供給源側頂点ｓとラベルＲを有する新しい排出側頂点ｔを有する。Ｇの辺は次のようになる：ＡＤＧの各々の方向性のある辺は同じ重みを有するＧの辺に対応する。また、供給源ｓからラベルＮを有する全ての頂点に向かって無限大の重みの方向性を持った辺と、ラベルＲを有する全ての頂点から排出口ｔへ無限の重みの方向性の辺とが存在する。
【００７４】
上記で定義した重み付けしてあり方向性を有するグラフＧでの「切断（ｃｕｔ）」は、これの頂点をｓ∈Ｘまたｔ∈Ｘバーで２つの組ＸとＸバーに分割することである。切断のコストは前方においてこれと交差する辺の全体の重み、即ちｘ∈Ｘかつｙ∈Ｘバーとなる方向性の辺（ｘ，ｙ）の全ての重みである。
【００７５】
全ての複製ラベル付けは切断であり、ラベル付けのコストが切断のコストと同じである。有限コストの切断はどれも複製ラベル付けである（無限コストの辺はどれも前方でこれと交差することができるためである）から、最小コスト切断は最適化複製ラベル付けである。パパジミトリューら（Ｐａｐａｄｉｍｉｔｒｉｏｕ  ｅｔ  ａｌ．）の最大フロー／最小カットの法則、「組み合わせによる最適化：アルゴリズムと複雑さ」プレンティス・ホール出版社、１９８２年（法則６．２）（Ｔｈｅ  ｍａｘ  ｆｌｏｗ／ｍｉｎ  ｃｕｔ  ｔｈｅｏｒｅｍ  ｏｆ  Ｐａｐａｄｉｍｉｔｒｉｏｕ  ｅｔ  ａｌ．，  ”Ｃｏｍｂｉｎａｔｏｒｉａｌ  Ｏｐｔｉｍｉｚａｔｉｏｎ：Ａｌｇｏｒｉｔｈｍｓ  ａｎｄ  Ｃｏｍｐｌｅｘｉｔｙ．”，  Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ，  Ｉｎｃ．，  １９８２，  （Ｔｈｅｏｒｅｍ  ６．２）  ）では、最小カットのコストが供給源から排出口への最大フローの値と同じであることを示している。
【００７６】
最大フローと最小カットはどちらも低次多項式時間に於て既知の幾つかのアルゴリズムのどれによっても発見可能である。特に、この最大フロー／最小カット問題は線型プログラミングを用いて解くことができる。前述の本発明の実施は移動性のオフセット整列を求めるための線型プログラミングパッケージにすでに依存しているので、このことは本発明にとって理想的である。線型プログラミングによる解法は他の方法に比べれば漸近的に効率が低いが、この目的に対しては十分なはずである。
【００７７】
６．さらなる観察結果
ループ内での複製と移動性のオフセットを求めるためのコンパイラ最適化についてこれまで説明してきた。最適な複製ラベル付けがネットワークフローで発見可能であることも示した。さらに、移動性の整列について、解の質にエラー領域を持つ丸め線型プログラミングへの近似的還元を提示した。
【００７８】
理論的には、本発明による移動性のオフセット整列を求めるための枠組は、利用者が定義するランタイム関数を取り扱うように拡張することが可能である。これを実現する１つの方法は、オフセット整列にこのような関数を組み込み、道の距離のシフトとして位置の不適合を取り扱うことである。これによって第４節で説明した技術に類似した技術を用いて、利用者が定義するランタイム関数について移動性のオフセット整列の問題を解くことができる。
【００７９】
以上の開示ではループプログラムを中心に取り扱ってきたが、任意の制御の流れを取り扱うことのできる枠組みを提供している。より特定すれば、既知の静的単一割り当ての形態を任意の制御の流れ図でプログラムするために組立てることができる。つまり、任意の制御の流れが存在すれば、制御依存グラフ（前出のサイトロンらを参照）を用いてＡＤＧの全ての辺ｅに実行確率Ｐ（ｅ）を割り当てて「予想される再配列コスト」を最小化することができる。
【数１１】
0003594656.tif 000014
【００８０】
【発明の効果】
以上に鑑み、本発明がデータ並列言語で書かれたプログラムのコンパイルに使用されるコンパイラで有利に用いることのできる効率的かつ有効な整列技術を提供していることは明らかであろう。
【図面の簡単な説明】
【図１】分散メモリーと並列プロセッサ構造を有するコンピュータのプロセッサ上にアレイ並列言語で表現されるようなプログラムオブジェクトを割り当てるための標準的２相コンパイラのモデルを模式的に図示したものである。
【図２】分散メモリー並列プロセッサ構造を有するコンピュータで実行するためのアレイ並列言語で書かれたプログラムをコンパイルするために本発明で用いる段階の基本的順序を示す。
【図３】簡単なＦＯＲＴＲＡＮ９０のプログラムである。
【図４】高性能ＦＯＲＴＲＡＮ指令（Ｈｉｇｈ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｆｏｒｔｒａｎ  ｄｉｒｅｃｔｉｖｅｓ  ）を用いることによる図３に図示したプログラムの移動性の整列を示す。
【図５】「ｄｏ」ループのそれぞれ第１と第５の反復での図３に図示したプログラムのための移動性の整列を示す。
【図６】図３に図示したプログラムのための整列分散グラフ（ＡＤＧ）である。
【図７】図３に図示したプログラムの代表的部分についてのＡＤＧ辺の反復空間のラベルつけを示す。
【図８】図８に含まれるプログラム断片についてのＡＤＧ辺のデータ重み付けのラベルつけを示す。
【図９】図７及び図８に含まれるプログラム断片について本発明で提供する移動性のオフセット整列を示す
【符号の説明】
２１    データアレイ、２２    テンプレート
【図１】
0003594656.tif 000015
【図２】
0003594656.tif 000016
【図３】
0003594656.tif 000017
【図４】
0003594656.tif 000018
【図５】
0003594656.tif 000019
【図６】
0003594656.tif 000020
【図７】
0003594656.tif 000021
【図８】
0003594656.tif 000022
【図９】
0003594656.tif 000023