JPH09319722A

JPH09319722A - 並列化コンパイル方法

Info

Publication number: JPH09319722A
Application number: JP12806596A
Authority: JP
Inventors: Toshio Suganuma; 俊夫菅沼; Hideaki Komatsu; 秀昭小松
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1996-05-23
Filing date: 1996-05-23
Publication date: 1997-12-12

Abstract

(57)【要約】【課題】並列化コンパイラが、コンパイル時に、ソース
プログラム中のリダクション・ループを有効に検出し
て、これを並列計算機が効率的に実行できる目的プログ
ラムに変換する方法を提供する。【解決の手段】並列化コンパイル方法において、ソース
プログラム中のループに存在する代入文をマスクするｉ
ｆ文などの条件式の構造を解析するステップと、このル
ープ中に存在する代入文の構造を解析するステップと、
変数のデータ依存関係から、代入文の構造をマージする
ステップと、条件式の構造及びマージされた代入文の構
造に基づき、変数のデータ依存関係及び代入文中の演算
子を参照して、リダクションを検出するステップとを有
する並列化コンパイル方法である。

Description

【発明の詳細な説明】

【０００１】

【発明の属する利用分野】本発明は、並列計算機用のコ
ンパイラに係り、特に、ソースプログラム中のリダクシ
ョンの検出及びその処理に関するものである。

【０００２】

【従来の技術】近年、複数のプロセッサを有する並列計
算機が実用化されつつある。この計算機は、それぞれの
プロセッサを同時に動作させることにより、高い処理能
力を実現する。並列計算機は、図１に示すように、プロ
セッサ、ローカルメモリ、データ転送装置からなるプロ
セッサ要素を複数有していて、それぞれのプロセッサ要
素はバスを介して接続されている。Ｃ言語やＦＯＲＴＲ
ＡＮなどの高水準言語で記述されたソースプログラムを
並列計算機で効率的に実行するためには、ソースプログ
ラムを並列計算機用の目的プログラムに翻訳する並列化
コンパイラ(Parallelizing Compiler)が必要となる。こ
の並列化コンパイラの重要な役割は、ソースプログラム
中の並列実行可能な記述を正確に検出できること及びこ
の実行を効率的にそれぞれのプロセッサ要素に分散する
ことである。

【０００３】ところで、数値計算プログラムなどにおい
て、リダクションは頻繁に現れる構文の一つである。リ
ダクションとは、交換法則及び結合法則の成立する演算
子であって、同種のものに基づいて、ある配列データか
ら単一の結果を求める操作をいう。例えば、多数の配列
データの中からその最大値、最小値またはインデックス
値を求めるという操作は、典型的なリダクション演算で
ある。ここで、交換法則及び結合法則の成立する演算子
とは、「＋」、「＊」、「max」または「min」などをい
う。また、同種な演算子であるから、異なる演算子を含
む演算はリダクションではなく、同一の演算子、例えば
演算子「＋」のみで構成された演算をいう。

【０００４】リダクションは、単一プロセッサでそれを
実行する場合には、逐次的に実行される計算ループであ
る。しかしながら、並列計算機において、それは並列実
行可能な記述である。従って、リダクションが検出でき
た場合、まず、各プロセッサ要素毎に、自己のローカル
メモリに記憶されている配列データをもとにしてローカ
ルな計算がそれぞれ実行される。次に、これらのローカ
ルな結果はあるプロセッサ要素に転送され、そのプロセ
ッサが、これらのローカルな結果を集計して最終結果を
求める。最後に、それぞれのプロセッサ要素中に記憶さ
れているデータの同一性を保証するために、求められた
最終結果はそれぞれのプロセッサ要素に再度転送され
る。このように、リダクションの計算を逐次的に実行す
るよりも、それぞれのプロセッサ要素ごとに分散処理す
る方が、実行時間は格段に短い。従って、並列化コンパ
イラがソースプログラム中のリダクション構文を正しく
検出することは、並列計算機が高速に実行できる目的プ
ログラムを生成するという点で非常に重要である。

【０００５】従来、このリダクションは、イディオム・
リコグニションにより、検出されていた。このイディオ
ム・リコグニションとは、パターン・マッチング、すな
わち、ソースプログラム中のある記述が、予め想定され
たパターンと一致するかどうかを調べ、一致する場合に
のみリダクションとして検出する方法である。このパタ
ーンは、ある特定の代入文、ループ、及びそのループ中
の条件文で表現されている。実際のソースプログラム中
に存在するあるループが、このイディオム・リコグニシ
ョンにより、例えば、配列データの最大値を求めるリダ
クションと認識された場合、並列化コンパイラは、この
ループを最大値を求めるための並列実行の手順を示す実
行時ルーチンの呼び出しに変換する。そして、実行時
に、このリダクションは、このルーチンに基づいて並列
に実行される。

【０００６】従来の方法であるイディオム・リコグニシ
ョンでは、並列化コンパイラの開発者がプログラム中で
頻繁に使用される一般的な表現として想定したパターン
と厳密に一致するもののみをリダクションとして検出し
ていた。従って、リダクションの表現が想定されたパタ
ーンと少しでも相違する場合には、この表現はリダクシ
ョンとして検出されない。ところが、実際のプログラム
において存在するリダクションは、ループ中に条件式が
複雑に絡み合って表現されている場合が多く、またその
バリエーションも非常に多い。従って、従来の方法で
は、想定されたパターン以外の複雑な表現を有するリダ
クションに対しては、それが本質的にリダクションであ
るにも関わらず認識できなかった。

【０００７】

【発明が解決しようとする課題】このように、従来のリ
ダクションの検出方法を用いた並列化コンパイラでは、
コンパイル時において、リダクションを有効に検出する
ことができなかった。従って、本来的に並列実行が可能
な演算が、そのようにコンパイルされずに、逐次的に実
行される目的プログラムとして生成される場合があっ
た。それゆえに、並列計算機が効率的にこの演算を実行
することが困難な場合が生じていた。

【０００８】そこで、本発明の目的は、効率的に並列実
行され得るような目的プログラムを生成できる並列化コ
ンパイラを提供することである。

【０００９】また、本発明の別の目的は、ソースプログ
ラム中のリダクション表現を正しく検出することであ
る。

【００１０】さらに、本発明の別の目的は、このように
して検出されたリダクションの実行時間を効果的に短縮
することである。

【００１１】

【課題を解決するための手段】かかる問題点に鑑み、第
１の発明は、複数のプロセッサを有する並列計算機用
に、ソースプログラムを翻訳して目的プログラムを生成
する並列化コンパイル方法において、ソースプログラム
中のループに存在する代入文をマスクする条件式の構造
を解析するステップと、この代入文の構造を解析するス
テップと、変数のデータ依存関係から、代入文の構造を
マージするステップと、条件式の構造及びマージされた
代入文の構造に基づき、変数のデータ依存関係及び代入
文中の演算子を参照して、リダクションを検出するステ
ップとを有する並列化コンパイル方法を提供する。

【００１２】上記リダクションを検出するステップは、
代入文の右辺式の状態に応じて、以下のように場合分け
される。まず、代入文の右辺式が表現式の場合には、変
数のうちのリカレンス変数のデータ依存関係を参照する
と共に、代入文が交換法則及び結合法則が成立する演算
子であって、同種の演算子であることを参照して、リダ
クションを判断する。また、代入文の右辺式が単一の変
数の場合には、条件文の構造に基づき、リダクションを
判断する。

【００１３】条件式の構造を解析するために、それぞれ
の条件式をノードに対応させ、それぞれの代入文を葉に
対応させた表現木を生成する。この条件式のモデルに基
づいて、コンパイラは、ループ全体の構造がリダクショ
ンを構成し得るものであるかどうかを解析する。

【００１４】代入文の構造を解析するために、代入文を
構成するそれぞれの要素（例えば、変数、演算子など）
をノードに対応させた表現木を、ループ中に存在する条
件式の構造を示す表現木の葉ごとに生成する。この代入
文のモデルに基づいて、コンパイラは、代入文の構造が
リダクションを構成し得るものであるかどうかを解析す
る。

【００１５】また、第２の発明は、複数のプロセッサ要
素を有する並列計算機用に、ソースプログラムを翻訳し
て目的プログラムを生成する並列化コンパイル方法にお
いて、あるリダクション変数で制御されるリダクション
を検出するステップと、リダクションをプロセッサ毎に
ローカルな中間結果を並列に計算するために、リダクシ
ョン変数をプロセッサ毎のプライベートな変数に変換す
るステップと、プロセッサ毎に並列に計算されたローカ
ルな結果を集計するために、リダクション通信を生成す
るステップとを有する並列化コンパイル方法を提供す
る。

【００１６】この第２の発明におけるリダクション通信
を生成するステップは、単一のループ中に複数のリダク
ションが存在する場合、それぞれのプロセッサが計算し
た複数の前記リダクションに関するローカルな結果を集
計するために、複数のリダクションに関するローカルな
結果をベクトル化して通信するように構成してもよい。

【００１７】また、第３の発明は、上記の構成を有する
並列化コンパイル方法を用いたコンパイル・プログラム
を記憶した記憶媒体を提供する。

【００１８】さらに、第４の発明は、上記の創世を有す
る並列化コンパイル方法によりコンパイルされた目的プ
ログラムを実行する並列計算機を提供する。

【００１９】

【作用】リダクションは、代入文自身に構造的な特徴が
あるため、この構造を解析することが必要である。しか
しながら、その代入文の変数が他の代入文と、どのよう
なデータ依存関係があるかを解析することも必要であ
る。第１の発明では、ループ中の条件式の関係を把握
し、かつ各代入文の関係を把握することによって、リダ
クションであるかどうかを判断する。データ依存関係に
着目して代入文の構造をマージするため、代入文の表現
に依存しない構造モデルを生成することができる。

【００２０】また、第２の発明では、リダクションは本
来的に並列実行が可能である点に着目して、リダクショ
ン変数を各プロセッサ毎にローカルなプライベート変数
に置き換えている。

【００２１】

【発明の実施の形態】以下、本発明における好ましい実
施例について説明する。本実施例における並列化コンパ
イラは、図１に示すようにそれぞれのプロセッサ要素毎
にローカルメモリを有するようなシステムを対象にして
いる。そして、このコンパイラの目的は、このようなシ
ステム上で効率的に実行できる目的プログラムを生成す
ることである。

【００２２】図２は、本実施例における並列化コンパイ
ラのリダクションの検出からリダクション通信の最適化
までの基本的な動作フローを示す図である。まず、ルー
プ中からリダクションを検出する（ステップ２１）。次
に、この検出されたリダクションを効率的に並列実行が
可能なループに変換する（ステップ２２）。最後に、こ
の変換に基づくリダクション通信を生成し、これを最適
化する（ステップ２３）。

【００２３】なお、以下の説明においては、適宜、次の
サンプル・プログラムを用いて、リダクションの検出か
ら通信を最適化するまでを説明する。このプログラム
は、配列rxmの絶対値の最小値を求めるものである。

【数１】 do 200 j = 1, m do 200 i = 1, n if (mod(i,2) = 1) then sum = sum + rm(i,j) ・・・・・・ (a) if ((abs(rx(i,j)) < abs(rxm)) .and. (mod(j,2) = 1)) then rxm = rx(i,j) ・・・・・・ (b) irxm = i ・・・・・・ (c) sum = sum + rx(i,j) ・・・・・・ (d) endif endif 200 continue

【００２４】リダクションの検出（ステップ２１）リダクションの検出は、図３に示すように、さらに３つ
のサブ・ステップから構成されている。まず、ループ中
の各代入文をマスクしているマスク表現に関するモデル
を作成する。つまり、各代入文について、それを実行す
るための条件に関する表現木を生成する（ステップ３
１）。

【００２５】ここでマスク表現とは、ｉｆ文などの条件
文のように、ある代入文の実行の前提となる条件をい
う。この表現木のノードは、論理積の各項によって表現
されている。表現木の生成において、「if,elseif,els
e」といったそれぞれの制御文をトラバースする度に、
新しいノードを生成していく。

【００２６】図４は、ループ本体の代入文とこれから生
成される条件式の表現木の関係を示す図である。表現木
の各ノードはマスク表現としての条件式（例えば、条件
Ｃ１及びその否定＾Ｃ１）に対応し、表現木の各葉は代
入文（Ｓ１、Ｓ２など）に対応している。表現木をルー
ト（Ｃ１または、＾Ｃ１）からある葉までトラバースす
ると、その中間ノードの条件式の積が、葉の各代入文の
実行を束縛するマスク表現となる。例えば、葉｛Ｓ２、
Ｓ３｝に関するマスク表現は、以下のようになる。

【数２】Ｃ１ and ＾Ｃ２ and Ｃ３

【００２７】上記のサンプル・プログラムに関して、こ
のような規則に基づき条件式の表現木を生成すると図５
のようになる。

【００２８】次に、ループ中の代入文の表現木を生成す
る（ステップ３２）。ステップ３１において生成された
マスク表現の表現木の葉毎に、その葉に対応する代入文
の表現木を生成する。この代入文の表現木は、そのノー
ドが代入文を構成するそれぞれの要素に対応付けられて
いる。

【００２９】ここで、代入文の要素とは、代入文を構成
する変数、演算子等をいう。例えば、ｓ＝ｓ＊ａ（ｉ）
という代入文においては、「ｓ」、「ｓ」、「＊」、
「ａ（ｉ）」が代入文の要素である。例えば、図６
（ａ）に示すプログラムの代入文の表現木は、図６
（ｂ）のようになる。代入文Ｓ₁、Ｓ₂のマスクとなる条
件式Ｃを表現式のルートとして、それぞれのノードに代
入文の要素を対応させている。

【００３０】上記のサンプルプログラムに関して、この
ような規則に基づき代入文の表現木を作成すると図７の
ようになる。

【００３１】変数のデータ依存関係に基づき、ステップ
３２で得られた代入文の表現木をマージする（ステップ
３３）。図６の例では、２つの代入文Ｓ₁、Ｓ₂に関して
変数ｓは、図６（ｂ）の点線で示す矢印δ₀、δ₁よう
な、true（defからuse）のデータ依存関係を有してい
る。従って、このデータ依存グラフは、図６（ｃ）のよ
うに強連結グラフを形成している。

【００３２】このようなデータ依存関係は、強連結コン
ポーネント(strongly connected component)と呼ばれ、
これが、リダクションを検出する単位となる。強連結コ
ンポーネントを構成する各代入文が、同一の条件式表現
木のノードを共有するならば、ループに独立なデータ依
存関係（図５(b)ではδ₀の矢印）を消去するように、代
入文の表現木をマージする。このようにして、図６
（ｂ）の表現木はマージされて、図６（ｃ）の表現木が
得られる。なお、マスク表現が異なる代入文間ではこの
ようなマージは行わない点に留意されたい。この操作を
すべての代入文において実行する。

【００３３】このような規則のもとで生成した上記サン
プル・プログラムの代入文のデータ依存関係を示す表現
木が図８である。なお、この図においては、代入文
(b)、(c)は記載が省略されている。この図が示すよう
に、サンプル・プログラム中の代入文(a),(b),(c),(d)
に対する表現木（図７参照）におけるデータ依存関係を
調べる。代入文(a),(d)はその間のデータ依存関係から
強連結コンポーネントを構成しているが、条件式表現を
共有しないため、この表現木のマージは行われない。

【００３４】ここで重要なことは、リダクションは、本
質的に、それを構成する代入文の間に強連結コンポーネ
ントとなるようなデータ依存関係（図６（ｃ）参照）が
あるということである。この性質に着目して、本アルゴ
リズムでは強連結コンポーネントに着目して、これらの
代入文の表現木をマージさせる。データ依存関係に着目
して代入文の構造をマージするため、代入文の表現に依
存しない構造モデルを基準にリダクションを判断するこ
とができる。

【００３５】なお、代入文が強連結コンポーネントを構
成するからといって、それを一律にリダクションと判断
することはできない。その他にも、ループ全体を解析す
る必要がある。しかしながら、このステップで、強連結
コンポーネントを見つけ出すことにより、リダクション
の検出の候補を生成することができる。

【００３６】上記の条件式の表現木及びデータ依存関係
に基づきマージされた代入文の表現木からリダクション
を構成しているかどうかを判定する（ステップ３４）。
すなわち、上記のステップでリダクションの候補となり
える記述が、実際にリダクションを構成しているかどう
かを判断するのである。この判断において重要なこと
は、変数のデータ依存関係及び代入文中の演算子の記述
を参照している点である。

【００３７】この判断は、データ依存グラフの右辺式の
状態により、以下の２つのケースに分けられる。すなわ
ち、マージされた代入文の表現木における右辺が表現式
であるか、単一の変数参照であるかである。

【００３８】ケースＡ．右辺式が、単一の変数参照では
なく、表現式である場合例えば、図６（ｄ）のように、ルート（＝）の右側が表
現式である場合である。この場合には、以下の４つの要
件の全てを具備する場合に、リダクションと判断され
る。

【００３９】（１）グラフのリカレンス変数(recurrenc
e valiable)がグラフの右辺に存在することが必要であ
る。ここでリカレンス変数とは、グラフの左辺の変数か
ら正方向のtrueのデータ依存関係のある右辺の参照変数
をいう。図６の例では、δ₁の矢印の先である参照変数
ｓが該当する。

【００４０】（２）グラフにおいて、上記リカレンス変
数（δ₁の矢印先の変数ｓ）のノードからそのルート
（＝）までトラバースした場合に、その中間に存在する
ノードの演算子の全てが、交換法則及び結合法則が成立
する演算子で、かつ同種の演算子として閉じていること
が必要である。ここで、交換法則及び結合法則が成立す
る演算子とは、「＋、＊、max、min」などの演算子であ
る。また、同種の演算子とあるから、中間ノードに異種
の演算子が存在してはいけない。図６（ｄ）において
は、中間ノードには、「＊」と「＋」という異なる演算
子が存在するため、この要件を具備しない。従って、図
６（ａ）の表現は、リダクションではないことがわか
る。

【００４１】（３）条件式の表現木におけるある葉に対
応するグラフＧ₀が、強連結コンポーネントの一部であ
る場合、その強連結コンポーネントに属する他のグラフ
Ｇ₁についても、条件（２）で得られた演算子と同種の
もので閉じていることが必要である。すなわち、グラフ
Ｇ₀とグラフＧ₁が同じ強連結コンポーネントに属し、論
理条件の表現木のノードを共有していなかったために、
ステップ３３でマージされなかった場合には、両グラフ
の中間ノードに同一の演算子が存在している必要があ
る。Ｇ₁が存在する場合には、異なる条件式でガードさ
れている複数の代入文がリダクションを構成している。

【００４２】（４）上記リカレンス変数のノードが、グ
ラフの強連結コンポーネントの外部ノードとのデータ依
存関係がないことが必要である。

【００４３】ケースＢ．グラフの右辺式がループ不変で
はない単一の変数参照である場合この場合には、グラフの対応する論理条件式の表現木の
ノードを、そのルートまでたどって、ノードの各論理式
Ｃとグラフの形をチェックする。具体的には、次の６つ
の要件を全て満たす場合に、リダクションと判断され
る。これらの要件は、リダクションのうち、条件文を使
って表現されたMAXVAL,MINVAL,MACLOC,MINLOCのリダク
ションを検出するためのものである。従って、それぞれ
の意味から以下の要件が導出される。換言すると、ｚ＝
Ｅという形をした代入文に対して、以下のような形をし
た論理式を有する条件文が存在するかどうかを調べてい
る。

【数３】ｆ（ｚ）relop ｆ（Ｅ）但し、ｆ：エレメンタル（elemental）な関数 relop：＜、≦、＞、≧等の比較演算子

【００４４】（１）グラフの左辺変数ノードに対して、
外部ノードとのデータ依存関係がない。

【００４５】（２）ノードの論理式Ｃが「or」で結合さ
れた論理式でない。

【００４６】（３）論理式Ｃが不等号で表現された論理
式である。

【００４７】（４）論理式Ｃの不等号の両辺が単一の変
数参照、またはその変数にエレメンタル(elemental)な
演算が施された項である。エレメンタルな演算が施され
ている場合には、両辺に対して同一の演算子が適用され
ている。なお、ここで、エレメンタルな演算とは、スカ
ラーの引数に対して、スカラーの結果を返すような演算
をいう。配列に対しては、そのそれぞれの配列要素に対
してこの演算が適用される。例えば、「abs」、「sqr
t」、「sin」、「cos」などが挙げられる。

【００４８】（５）論理式Ｃの不等号のいずれかの辺の
変数（インデックス変数も含む）が、グラフの右辺変数
と同一である。変数が一致しない場合には、論理式Ｃの
不等号における変数のデータ依存関係を遡ることによっ
て、グラフの右辺変数と同一になる代入文の右辺が存在
する。

【００４９】（６）論理式Ｃの不等号の他方の辺の変数
（インデックス変数も含む）が、グラフの左辺変数と同
一である。または、データ依存関係を遡ることによっ
て、グラフの左辺変数と同一となる代入文の右辺が存在
する。この時、不等号の向き、インデックス変数であっ
たかを参照することにより、「maxval」、「minval」、
「maxloc」、「minloc」などのリダクションと判定され
る。または、条件（５）でインデックス変数とグラフの
右辺変数が同一だった場合には、同一の条件式を共有
し、ノードＣにおいて「maxval」または「minval」と判
定されている他のグラフが存在する。この場合は、この
判定に従って、「maxloc」、「minloc」と判定される。

【００５０】サンプル・プログラム中のリダクションの
候補が、実際にリダクションを構成しているかを調べ
る。すなわち、それぞれの表現木に対して、上記２種類
のケースのどちらかを適用し、判定が行われる。代入文
(a)の表現木に対しては、その右辺式が単一の変数参照
ではなく、表現式の形である。従って、ケースＡが適用
される。この場合、図８に示すように、表現木(a)の右
辺のリカレンス変数sumからスタートして、そのルート
（＝）までたどってみると、中間ノードの演算子は
「＋」だけである。従って、交換法則及び結合法則が成
立する演算子で閉じていることがわかる。また、表現式
(a)と条件式ノードを共有していないが、同じ強連結成
分に属する表現木(d)が存在する。従って、この表現木
(d)についても調べる必要がある。この場合、同様に上
記の演算子で閉じていることがわかる。従って、表現木
(a),(d)で和のリダクションを構成していると認識され
る。

【００５１】代入文(b)の表現木に対しては、その右辺
式が単一の変数参照であるため、上記のケースＢが適用
される。この場合、条件式表現木のノードをそのルート
まで遡って、Ｃ３，Ｃ２，Ｃ１をトラバースする。Ｃ２
は、代入文rxm=rx(i,j)に対して、abs(rxm)≧abs(rx(i,
j)という表現であるから、上記の要件を満たすことがわ
かる。従って、これは配列vxに対しては絶対値が最小で
ある値を求めるリダクションであると認識される。代入
文(c)は、その右辺の変数が、条件式Ｃ２における配列
変数rxのインデックス変数となっており、かつ絶対値の
最小値を求めるリダクションが存在することから、これ
は、その時のインデックス変数を求めるリダクションで
あると認識される。

【００５２】以上のステップにより、上記のサンプル・
プログラムが示すループは、代入文(b)が配列rxに対す
る絶対値の最小値、代入文(c)がその時のループインデ
ックス、代入文(a),(d)が配列rm及びrxに対する総和を
求めるリダクションであることが検出される。

【００５３】リダクションを並列化が可能なループに変
換（ステップ２２）次に、リダクションループは、複数のプロセッサで高速
に実行可能となるように、並列化が可能なループに変換
される。ここで、ステップ２１により検出されたリダク
ション構文は、一般的には、少なくとも一つの代入文を
有するインパーフェクト(imperfect)なループで表現さ
れており、必ずしも、リダクション自身で単独なリダク
ションループを形成しているとは限らない。このような
一般的な表現も考慮して、リダクションの計算を複数の
プロセッサで効率よく実行するためには、リダクション
を含むループの変換手順を決定する必要がある。このた
めには、リダクションの対象となる各配列オペランドに
対する通信解析を行うことが必要である。

【００５４】図９は、リダクションのループ変換のため
の動作フロー図である。まず、リダクションの通信解析
を行う（ステップ９１）。ここでは、ループ内のデータ
の依存関係及びその配列のデータを分割する方法の指定
に基づいてプロセッサ間で生じる通信を解析する。

【００５５】この通信解析（ステップ９１）に基づき、
通信が必要であり、かつ配列オペランドがプリフェッチ
が可能であるかどうかを判断する（ステップ９２）。

【００５６】ステップ９１による判断が、「Yes」の場
合には、この配列を対象とする全てのリダクション、及
び配列対象はないが、配列を実行時マスクの条件式オペ
ランドとして有するリダクションに対して、新たなルー
プを生成する（ステップ９３）。この新たなループは、
プリフェッチ可能なループのネストレベルにおいて、こ
れらのオペランドを対象とするリダクションを代入文と
して有している。このループは、全てのリダクション変
数をプライベート変数とすること、すなわちプライベー
ト化することによって、プロセッサ毎にローカルな演算
を実行するループとなるため、並列実行が可能となる。
このループは、プリフェッチのために配列データの個々
の要素を通信として送受信する代わりに、リダクション
のセマンティックスを検出したことから、個々のプロセ
ッサによって求められたローカルな結果のみを通信する
ことにより、効率化させたと考えることができる。

【００５７】なお、ここでプライベート変数とは、ルー
プの繰り返しの中で、その定義と参照が閉じているもの
をいう。

【数４】

【００５８】上式で、変数ｘはループのそれぞれの繰り
返しの中で定義され、その同じ繰り返し（イタレーショ
ン）の中でのみ参照されているプライベート変数であ
る。ソースプログラムを並列化する場合、各イタレーシ
ョンごとに分割して、それを異なるプロセッサに与える
が、プライベート変数は、各プロセッサ毎のローカルな
変数として取り扱うことができるので、その計算におい
てはプロセッサ間通信が生じることがない。このよう
に、ループ中で使用される変数を、一時的にプロセッサ
毎のプライベート変数として扱うことは、イタレーショ
ン間の並列計算を正しく実行することを保証することが
でき、かつ通信のオーバーヘッドを低減させることがで
きるため重要である。

【００５９】ステップ９１による判断が、「No」の場
合、すなわち、通信が必要ない場合、または配列オペラ
ンドがプリフェッチできない場合には、オリジナルのル
ープのリダクション変数をプライベート化する（ステッ
プ９４）。これにより、リダクションのオペレーション
によってループの有する並列性が損われることはない。
従って、ループが並列化できない場合は、その原因はル
ープの中の他の代入文におけるデータの依存関係にある
こととなる。このような場合が生じるのは、ループその
ものに並列性がない場合に限られる。ループが並列化で
きた場合には、そのループのネストレベルの外側で、リ
ダクションのグローバルな計算のための通信コールを挿
入する。

【００６０】サンプル・プログラムについて説明する
と、リダクションの対象配列rx及びrmは、ループ中の左
辺の配列変数が存在しないため、これらの配列オペラン
ドに対する通信を解析すると、通信が必要ないことがわ
かる。従って、新たなループを生成せずに、オリジナル
のループ中の全てのリダクション変数rxm,irxm,sumをプ
ライベート化するような変換が施され、並列化が可能な
ループとなる。この場合、ループの計算分割は、リダク
ションの対象配列である変数rxまたは変数rmに基づいて
行われる。

【００６１】リダクション変数のプライベート化及びそ
れに続くループの並列化は、それがリダクションである
と検出されたことで、はじめて可能となる点に特に留意
されたい。この変数のプライベート化により上記のサン
プルプログラムは、以下のように変換される。なお、こ
のプログラム中のアンダー・スコア付きの変数（例え
ば、_rxm）は、全てプライベート化されたリダクション
変数を表す。また、始めの３行は、プライベート化され
たリダクション変数の初期値設定である。さらにループ
は既に並列化された形になっており、ループの繰り返し
範囲が分割されている。

【００６２】

【数５】 _rxm = largest_val _irxm = 0 _sum = 0 do 200 j = lb1, ub1 do 200 i = lb2, ub2 if (mod(i,2) = 1) then _sum = _sum + rm(i,j) ・・・・・・ (a) if ((abs(rx(i,j)) < abs(_rxm)) .and. (mod(j,2) = 1)) then _rxm = rx(i,j) ・・・・・・ (b) _irxm = i ・・・・・・ (c) _sum = _sum + rx(i,j) ・・・・・・ (d) endif endif 200 continue

【００６３】リダクション通信の生成及びその最適化
（ステップ２３）並列化されたリダクション・ループに対して、通信の生
成が行われる。ある単一のループが複数のリダクション
演算を含んでいるというケースは、実際のソースプログ
ラムにおいて非常によく見られる。このような場合、そ
れぞれのリダクション毎にプロセッサ間通信を独立して
実行することは効率的ではない。それよりも、複数のリ
ダクションについて、それぞれのプロセッサが求めたロ
ーカルな中間結果をまとめてベクトル化し、１回の通信
イベントで送受信する方が好ましい。実行時のシステム
全体の同期ポイントを減らすことができるからである。

【００６４】リダクション通信は、３つのステップで実
行される。すなわち、（１）リダクションのローカルな
計算ループの分割情報(local iteration set:LIS)に基
づいて、参加するプロセッサグループを求めるステッ
プ、（２）プロセッサグループのメンバーであるプロセ
ッサ間で通信を行い、あるプロセッサへと結果を集計す
るステップ、及び（３）このプロセッサで計算された最
終結果をプロセッサグループのメンバーへ転送するステ
ップ、である。

【００６５】上記の３ステップは、プログラムとしては
以下の式のように記述することができる。なおここで、
gidとは、プロセッサグループを示している。

【数６】 gid=lis2gid(LIS) call reduce (gid, &reduce_function, reduction_variable) call broadcast (gid, reduction_variable)

【００６６】一般的に、複数のリダクション通信をマー
ジする場合、プロセッサの分割方法はリダクションごと
に異なる。従って、それぞれのプロセッサグループgid
1、gid2の和集合を計算し、この和集合のプロセッサグ
ループに対して通信を実行すればよい。

【数７】gid= gid1 ∪ gid2

【００６７】また、リダクションのためのローカル変
数、グローバル変数の組だけでなく、各リダクションに
対するプロセッサグループ及びリダクション演算子につ
いてもベクトル化する。この場合、このベクトルの集計
はマルチリダクション関数を起動する。すなわち、ある
プロセッサグループの中で、ベクトル化された変数のそ
れぞれに対して、指定された異なるリダクション演算を
実行することで、通信回数を減らし、効率的に実行す
る。

【００６８】図１０は、マルチリダクション関数のプロ
グラムリストの例である。このプログラムリストは、整
数型変数のケースのみを示しているが、他のタイプの変
数の場合についても容易に対応させることができる。こ
こで、in1は、ローカル入力データ、in2をグローバル入
力データとしている。ここで示されているように、ベク
トル化された各要素に対するリダクション演算は、指定
されたプロセッサグループに対するメンバーチェックを
まず実行し、このチェックを満たすプロセッサのみが演
算を実行する。チェックを満たさないプロセッサは演算
を実行せずに、入力データをそのまま出力する。このよ
うに、リダクションのための通信イベントのパケット内
のデータ使用率を向上させ、かつ通信イベントの回数を
減らすことにより、並列計算機の実行速度を向上させて
いる。

【００６９】同一ループ内に存在する複数のリダクショ
ン通信をマージする効果は、次のように説明できる。２
つのリダクション通信のためのプロセッサグループをgi
d1、gid2で表し、その和集合をgid0とした場合、２つの
リダクションをマージすることなく、別々にリダクショ
ン通信が行われたケースは次のようになる。

【００７０】

【数８】 call reduce (gid1, SUM, s1, ・・・) call broadcast (gid1, s1, ・・・ ) call reduce (gid2, MAXVAL, s2, ・・・ ) call broadcast (gid2, s2, ・・・ )

【００７１】一方、リダクションをマージした場合のリ
ダクション通信は次のようになる。 #d

【数９】 call reduce (gid0, (gid1, gid2), (SUM, MAXVAL), (s1,s2), ・・・ ) call broadcast (gid0, (gid1, gid2), (s1, s2) ・・・ )

【００７２】マージされた通信では、プロセッサグルー
プの組、リダクション演算の組及びリダクション変数の
組が引数として渡され、和集合のプロセッサグループgi
d0の間で通信が行われる。それぞれのプロセッサは、引
数として渡されたgid1、gid2に対してメンバーチェック
を行い、それぞれのリダクション及び通信に参加するか
を決定する。上記式中の「reduce」及び「broadcast」
は、ｎプロセッサに対して、log(n)で通信を行うことが
でき、それぞれのプロセッサを葉とした場合の木構造の
height reductionと考えることができる。

【００７３】ここでgid0、gid1、gid2のそれぞれのプロ
セッサ数をｐ、ｎ、ｍとすると、ｐ≦ｎ＋ｍであるか
ら、ｐ、ｍ、ｎ＞１の場合には、以下のようになる。

【数１０】 log(p)≦log(n+m)≦log(nm)＝log(n)+log(m)

【００７４】従って、通信時間を比較すると、

【数１１】 reduce(gid0)≦reduce(gid1)＋reduce(gid2) が成立する。

【００７５】マージされたリダクション通信は、gid1、
gid2が互いにdisjointな場合において、全てのプロセッ
サへのブロードキャスト通信が少なくとも１回少なくて
すむ。また、gid1、gid2が同一プロセッサグループに存
在する場合には、通信時間は半分になる。一般的には、
gid1、gid2は互いに部分的にプロセッサを共有してお
り、この関係は図１１のように考えられる。図１１は、
リダクション演算がプロセッサを共有する場合におけ
るプロセッサを葉とする木構造の高さ縮約(height redu
ction)を示す図である。

【００７６】上述のサンプル・プログラムのループは、
通信を最適化することなく通信を生成すると、３つのリ
ダクションのそれぞれに対して通信を生成するため、３
回の通信の同期ポイントが生じる。しかしながら、それ
ぞれのリダクションの計算分割から得られるプロセッサ
グループの和集合をとり、この拡大された和集合のプロ
セッサのグループに対して通信を行うことにより、１回
の通信にマージすることができる。リダクションは一つ
のループにまとめられており、計算分割は一種類だけと
なる。従って、この例では和集合を取る必要はない。こ
の計算分割からプロセッサグループを実行時に求め、複
数のリダクションを実行するための情報をベクトルとし
て実行時ルーチンに渡す。これによって、このプロセッ
サグループに属するプロセッサ間で、複数のリダクショ
ンを一回の通信で処理できるように最適化される。

【００７７】以下のプログラムは、上記のサンプル・プ
ログラムの最終的な形を示している。最後の３行がそれ
ぞれ、実行時に計算分割からプロセッサグループ(gid)
を求め、このグループに属するプロセッサ間において３
種類のベクトルとして渡されたリダクションを実行し、
そして、集められたリダクションの結果を全プロセッサ
にブロードキャストする実行時ルーチンの呼び出しとな
っている。

【００７８】

【数１２】 _rxm = largest_val _irxm = 0 _sum = 0 do 200 j = lb1, ub1 do 200 i = lb2, ub2 if (mod(i,2) = 1) then _sum = _sum + rm(i,j) ・・・・・・ (a) if ((abs(rx(i,j)) < abs(_rxm)) .and. (mod(j,2) = 1)) then _rxm = rx(i,j) ・・・・・・ (b) _irxm = i ・・・・・・ (c) _sum = _sum + rx(i,j) ・・・・・・ (d) endif endif 200 continue gid = lis2gid (LIS) call reduce (gid, 3, (abs-minval, abs-minloc, sum), (rxm, irxm, sum), (_rxm, _irxm, _sum)) call broadcast (gid, (rxm, irxm, sum))

【００７９】本実施例では、リダクションループ中に多
くの条件式が存在するために従来の方法では検出できな
かったような複雑な表現のリダクションさえも正確にリ
ダクションとして検出できる。また、リダクション変数
をプライベート化することにより、並列実行が可能なよ
うに変形できるか、またはそれができなくとも、リダク
ションの存在がループ並列化を阻害する要件とならない
ように変形することが可能となる。さらに、ループ中に
複数のリダクションが存在する場合にも、通信コールを
ベクトル化することで、通信イベントの回数を減らし、
効率的な通信が可能となった。本実施例に示す方法は、
数値計算プログラム、特に繰り返し法によって近似解を
求めるアルゴリズムなどにおいて非常に有効である。

【００８０】最後に、本実施例における並列化コンパイ
ル方法はコンパイル・プログラムとして記憶媒体中に格
納しておいてもよい。

【００８１】

【効果】本発明を用いた並列化コンパイラは、ソースプ
ログラムに頻繁に現れるループパターンであるリダクシ
ョンをソースプログラム中から正確に抽出して、効率的
に並列実行可能な目的プログラムを生成することができ
る。従って、並列計算機は、そのようにしてコンパイル
された目的プログラムを高速に実行することができる。

【図面の簡単な説明】

【図１】並列計算機の構成図である。

【図２】リダクションの検出からリダクション通信の最
適化までの基本的な動作フロー図である。

【図３】リダクションの検出における動作フロー図であ
る。

【図４】ループ本体の代入文とこれから生成される条件
式の表現木の関係を示す図である。

【図５】サンプル・プログラムの条件式に関する表現木
である。

【図６】代入文の表現木の例である。

【図７】サンプル・プログラムの代入文に関する表現木
である。

【図８】サンプルプログラムのデータ依存関係を示す表
現木である。

【図９】リダクションのループ変換のための動作フロー
図である。

【図１０】マルチリダクション関数のプログラムリスト
の例である。

【図１１】は、リダクション演算がプロセッサを共有
する場合におけるプロセッサを葉とする木構造の高さ縮
約(height reduction)を示す図である。

───────────────────────────────────────────────────── フロントページの続き (72)発明者小松秀昭神奈川県大和市下鶴間1623番地14 日本アイ・ビー・エム株式会社東京基礎研究所内

Claims

【特許請求の範囲】

【請求項１】複数のプロセッサを有する並列計算機用
に、ソースプログラムを翻訳して目的プログラムを生成
する並列化コンパイル方法において、前記ソースプログラム中のループに存在する代入文をマ
スクする条件式の構造を解析するステップと、前記ループ中に存在する前記代入文の構造を解析するス
テップと、変数のデータ依存関係から、前記代入文の構造をマージ
するステップと、前記条件式の構造及びマージされた前記代入文の構造に
基づき、前記変数のデータ依存関係及び前記代入文中の
演算子を参照して、リダクションを検出するステップと
を有することを特徴とする並列化コンパイル方法。
【請求項２】前記リダクションを複数の前記プロセッサ
が並列実行が可能なループに変換するステップをさらに
有することを特徴とする請求項１に記載の並列化コンパ
イル方法。
【請求項３】前記リダクションを検出するステップは、前記代入文の右辺式が表現式の場合には、前記変数のう
ちのリカレンス変数のデータ依存関係を参照し、かつ前
記代入文が交換法則及び結合法則が成立する演算子であ
って、同種の演算子であることを参照して、リダクショ
ンを判断することを特徴とする請求項１または２に記載
の並列化コンパイル方法。
【請求項４】前記リダクションを検出するステップは、前記代入文の右辺式が単一の変数の場合には、前記条件
文の構造に基づき、リダクションを判断することを特徴
とする請求項１または２に記載の並列化コンパイル方
法。
【請求項５】前記条件式の構造を解析するステップは、それぞれの前記条件式をノードに対応させ、それぞれの
前記代入文を葉に対応させた表現木を生成することを特
徴とする請求項１、２、３または４に記載の並列化コン
パイル方法。
【請求項６】前記代入文の構造を解析するステップは、前記条件式の構造を解析するステップにおいて生成され
た表現木の葉ごとに、前記代入文を構成するそれぞれの
要素をノードに対応させた表現木を生成することを特徴
とする請求項５に記載の並列化コンパイル方法。
【請求項７】検出された前記リダクションを制御するリ
ダクション変数をそれぞれの前記プロセッサ毎のプライ
ベートな変数に変換するステップをさらに有することを
特徴とする請求項１に記載された並列化コンパイル方
法。
【請求項８】複数のプロセッサを有する並列計算機用
に、ソースプログラムを翻訳して目的プログラムを生成
する並列化コンパイル方法において、あるリダクション変数で制御されるリダクションを検出
するステップと、前記リダクションを前記プロセッサ毎に並列に計算して
ローカルな結果を得るために、前記リダクション変数を
前記プロセッサ毎のプライベートな変数に変換するステ
ップと、前記プロセッサ毎に並列に計算された前記ローカルな結
果を集計するために、リダクション通信を生成するステ
ップとを有することを特徴とする並列化コンパイル方
法。
【請求項９】前記リダクション通信を生成するステップ
は、単一のループ中に複数の前記リダクションが存在す
る場合、それぞれの前記プロセッサが計算した複数の前
記リダクションに関するローカルな結果を集計するため
に、複数の前記リダクションに関するローカルな結果を
ベクトル化して通信する請求項８に記載の並列化コンパ
イル方法。
【請求項１０】請求項１乃至９に記載の並列化コンパイ
ル方法を用いたコンパイル・プログラムを記憶した媒
体。
【請求項１１】請求項１乃至９に記載の並列化コンパイ
ル方法によりコンパイルされた目的プログラムを実行す
る並列計算機。