JPH0744508A - プログラム分割方法 - Google Patents

Abstract

(57)【要約】 【目的】逐次ソースプログラムを並列計算機向きに変換
する際に用いるプログラム分割方法において、代入文左
辺に現われる配列の分割方法が異なることによる結果不
正を起こさないこと、および代入文左辺に現われる配列
の添字式が異なるためにループ繰り返し範囲が拡大され
て無駄なループ繰り返しを実行するようなことがなく、
必要不可欠なループ繰り返しだけを実行し、性能向上を
図ることを目的とする。 【構成】各代入文の左辺の配列要素が割り付けられてい
るプロセッサでその代入文を実行するように、ループ内
の各代入文に対応するループ添字の和集合をリストベク
トルとし、ループ実行範囲をリストベクトルの範囲に絞
る。リストベクトルは、言語変換時に決定する方法と実
行時に計算するようなプログラムを追加する方法があ
る。ループ内の各代入文は、和集合のうち対応する部分
集合だけを実行するようにする。 【効果】結果不正を起こすことなく、無駄なループ繰り
返しもないようにできる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、並列計算機向け言語変
換システムにおけるプログラム分割方法に関し、特に、
データ分割指示（分散記憶型並列計算機の各プロセッサ
へのデータの割り付け方に関する指示）付きの逐次ソー
スプログラムを入力とし、分散記憶型並列計算機向きの
並列ライブラリの呼び出しを含むソースプログラムまた
はオブジェクトプログラムを生成するためのプログラム
分割方法に関する。

【０００２】

【従来の技術】計算速度の向上のために、プロセッサを
複数台並べて同時に動作させる並列計算機システムが考
案されてきた。並列計算機システムでは、通常、複数台
ある各プロセッサは、それぞれローカルメモリを備えて
いる。

【０００３】一方、従来のシングルプロセッサ向きにコ
ーディングされたソースプログラムは、単一メモリを仮
定している。従って、シングルプロセッサ向きにコーデ
ィングされたソースプログラムを並列計算機システムで
動作させる場合は、ソースプログラム中のデータ（配列
など）を複数のデータ群に分割して、並列計算機システ
ムの各プロセッサのローカルメモリに割り付けて計算を
行う必要がある。

【０００４】このとき、演算を各プロセッサに分配する
方法として、「代入文の左辺の変数が割り付けられてい
るプロセッサで、その代入文を実行する」という原則
で、ソースプログラムを並列化変換する。以後、このよ
うなシングルプロセッサ向きの逐次ソースプログラムの
並列化変換をプログラム分割と呼ぶ。

【０００５】以下、従来のプログラム分割の方式につい
て説明する。なお、ここではＤＯループを対象として説
明する。

【０００６】元の逐次ソースプログラムにおいて、代入
文がループ内で繰り返し計算される場合は、上記の原則
が成り立つように、ループ繰り返しの範囲を分割して、
それを各プロセッサに割り付ける。

【０００７】そのようなプログラム分割方法に関する説
明は、例えば、バサンス・バラサンダラム，ジオフェリ
・フォックス，ケン・ケネディ，ウルリッチ・クレマ共
著”データ分割とデータ分散に対する対話環境”（Ｖａ
ｓａｎｔｈ Ｂａｌａｓｕｎｄａｒａｍ，Ｇｅｏｆｆｒ
ｅｙ Ｆｏｘ，Ｋｅｎ Ｋｅｎｎｅｄｙ ａｎｄ Ｕｌ
ｒｉｃｈ Ｋｒｅｍｅｒ：”Ａｎ Ｉｎｔｅｒａｃｔｉ
ｖｅ Ｅｎｖｉｒｏｎｍｅｎｔ ｆｏｒ Ｄａｔａ Ｐ
ａｒｔｉｔｉｏｎｉｎｇ ａｎｄ Ｄｉｓｔｒｉｂｕｔ
ｉｏｎ”）（Ｆｉｆｔｈ Ｄｉｓｔｒｉｂｕｔｅｄ Ｍ
ｅｍｏｒｙ Ｃｏｍｐｕｔｉｎｇ Ｃｏｎｆｅｒｅｎｃ
ｅ，Ｃｈａｒｌｅｓｔｏｎ，ＳｏｕｔｈＣａｒｏｌｉｎ
ａ，Ａｐｒｉｌ９−１２，１９９０，ｐｐ１１６０−１
１７０）にある。

【０００８】この論文でのプログラム実行方式は、デー
タ・オーナー・コンピューツ・ルール（ｄａｔａ ｏｗ
ｎｅｒ ｃｏｍｐｕｔｅｓ ｒｕｌｅ）に基づいた、Ｓ
ＰＭＤ（Ｓｉｎｇｌｅ Ｐｒｏｇｒａｍ Ｍｕｌｔｉｐ
ｌｅ Ｄａｔａ）である。ここで、ＳＰＭＤとは、各プ
ロセッサが同じプログラムを持つことをいう。データ・
オーナー・コンピューツ・ルールとは、配列要素が割り
当てられているプロセッサのみが、その配列要素の定義
を実行するようにすることである。

【０００９】従って、プログラム分割決定方法では、デ
ータの分割の仕方とその分割単位のプロセッサへの割り
付けに基づいて、各代入文の左辺の配列要素が割り付け
られているプロセッサでその代入文を実行するようにプ
ログラム分割する。そのため、プログラム分割処理で
は、元の逐次ソースプログラムとデータ分割情報を入力
して、変更したソースプログラムとプログラム分割情報
を出力する。

【００１０】ここで、データ分割情報とは、下記の〜
の情報をいう。

【００１１】データの分割の仕方とその分割単位のプ
ロセッサへの割り付け方を示すデータ分割関数（配列要
素のインデックスから、データを割り付けたプロセッサ
番号への写像） 各配列要素のインデックスを元の逐次プログラムでの
グローバルインデックスから各プロセッサのローカルイ
ンデックスへ変換する局所化関数 上記局所化関数の逆関数で、ローカルインデックスか
らグローバルインデックスへ変換する大域化関数から成
る関数群 これらの関数群を適用して得られる、各プロセッサご
との配列要素のインデックスのグローバル表現とローカ
ル表現を格納するデータ分割テーブル

【００１２】プログラム分割情報とは、下記のおよび
の情報をいう。

【００１３】各代入文に対して、元のループ反復範囲
のうち、各プロセッサで分担実行すべきループ反復範囲
を示すために、ループインデックスの値の取り得る範囲
をプロセッサ番号を用いた式で表現したプログラム分割
式テーブル 各プロセッサごとに、実際に参照するループインデッ
クスの具体的な値で表現したプログラム分割値テーブル

【００１４】以下、従来法によるプログラム分割方法に
ついて詳しく説明する。

【００１５】まず、添字関数とローカル・イテレーショ
ン・セット（Ｌｏｃａｌ Ｉｔｅｒａｔｉｏｎ Ｓｅ
ｔ：以下、ＬＩＴＳと略す）について説明する。

【００１６】図２は、添字関数を説明するためのプログ
ラムの例である。同図において、２０１と２０２はルー
プを示している。多重ループ２０１において、Ａ（Ｓ
１，Ｓ２，…，Ｓｍ）は、配列Ａの参照（定義または使
用）である。各Ｓｋは、ループインデックス変数Ｉ１，
Ｉ２，…，Ｉｎおよびこの参照を包含するループ内で不
変な式を使って表現される添字式である。

【００１７】ここで、配列Ａ（Ｓ１，Ｓ２，…，Ｓｍ）
に対する添字関数ｆとは、ループインデックス変数Ｉ
１，Ｉ２，…，Ｉｎの値の組に対し、各次元の添字式Ｓ
１，Ｓ２，…，Ｓｍの値を決める関数をいう。すなわ
ち、この例では、 ｆ（Ｉ１，Ｉ２，…，Ｉｎ）＝（Ｓ１，Ｓ２，…，Ｓ
ｍ） である。

【００１８】添字関数ｆの逆関数ｉｎｖ＿ｆ（Ｄ１，Ｄ
２，…，Ｄｍ）＝（Ｉ１，Ｉ２，…，Ｉｎ）は、配列添
字の値の組Ｄ１，Ｄ２，…，Ｄｍに対して、その配列参
照を包含するループインデックス変数Ｉ１，Ｉ２，…，
Ｉｎの各々の値を決める関数である。

【００１９】すなわち、配列添字値Ｄ１，Ｄ２，…，Ｄ
ｍに関して、連立方程式：Ｓ１＝Ｄ１，Ｓ２＝Ｄ２，
…，Ｓｍ＝Ｄｍを、インデックス変数Ｉ１，Ｉ２，…，
Ｉｎについて解くことにより、添字関数ｆの逆関数ｉｎ
ｖ＿ｆが求められる。

【００２０】例として、ループ２０２では、配列参照Ａ
（Ｉ＋Ｊ，Ｊ−１）に対する添字関数ｆは、ｆ（Ｉ，
Ｊ）＝（Ｉ＋Ｊ，Ｊ−１）である。また、逆関数ｉｎｖ
＿ｆ（Ｃ，Ｄ）は、２つの連立方程式Ｉ＋Ｊ＝Ｃ；Ｊ−
１＝Ｄを、Ｉ，Ｊについて解くことにより、ｉｎｖ＿ｆ
（Ｃ，Ｄ）＝（Ｃ−（Ｄ＋１），Ｄ＋１）となる。すな
わち、配列要素添字（Ｃ，Ｄ）に対して、対応するルー
プインデックスの値として、Ｉ＝Ｃ−（Ｄ＋１），Ｊ＝
Ｄ＋１を得る。

【００２１】この逆関数を使うことにより、Ａ（５，
２）は、Ｉ＝５−（２＋１）＝２，Ｊ＝２＋１＝３のと
き参照されるが、Ａ（３，３）は、Ｉ＝３−（３＋１）
＝−１，Ｊ＝３＋１＝４であり、反復範囲外となるの
で、ループ２０２では参照されないことがわかる。

【００２２】ＬＩＴＳ（ローカル・イテレーション・セ
ット）とは、各代入文に対して、元のループ反復範囲の
うち、各プロセッサで分担実行すべきループ反復範囲
を、そのプロセッサでのループインデックスの値の取り
得る範囲として表現したものである。

【００２３】図３は、ＬＩＴＳを求める処理手順を示
す。ＬＩＴＳを求める処理１０８では、データ分割情報
１０５と中間語１０３を入力して、プログラム分割情報
１１０を出力する。

【００２４】ＬＩＴＳを求める処理の手順を説明する。
まず、配列のローカル・インデックス・セット（Ｌｏｃ
ａｌ Ｉｎｄｅｘ Ｓｅｔ：以下、ＬＩＸＳと略す）を
計算する処理３０１で、データ分割情報１０５のデータ
分割テーブル３０２（図１２）を参照して、各プロセッ
サごとのＬＩＸＳを得る。

【００２５】ＬＩＸＳとは、元のデータ（配列の要素）
が各プロセッサに割り付けられた場合、各プロセッサに
ある配列要素のインデックス値の集合である。このイン
デックスの値は、各プロセッサでのローカルな値であ
る。配列Ａに対するプロセッサｐでのＬＩＸＳを、ＬＩ
ＸＳ＿Ａ（ｐ）と表す。

【００２６】次に、ＬＩＸＳをグローバルインデックス
で表現し直す処理３０３で、データ分割情報１０５の大
域化関数３０４によって、ＬＩＸＳ＿Ａ（ｐ）をグロー
バルインデックスで表現したものＧＩＸＳ＿Ａ（ｐ）を
得る。これにより、各プロセッサでのローカルなインデ
ックス値であるＬＩＸＳ＿Ａ（ｐ）から、元のプログラ
ムにおけるインデックス値で表現されたグローバルイン
デックスの集合ＧＩＸＳ＿Ａ（ｐ）が得られる。

【００２７】次に、添字関数の逆関数を計算する処理３
０５では、中間語１０３から、代入文左辺配列Ａ（Ｓ
１，Ｓ２，…，Ｓｍ）に対して、添字関数の逆関数ｉｎ
ｖ＿ｆを計算する。

【００２８】そして、各プロセッサに対するループ仮想
反復範囲を計算する処理３０６で、各プロセッサｐにつ
いて、添字関数の逆関数ｉｎｖ＿ｆをＬＩＸＳ＿Ａ
（ｐ）に適用することによって、代入文左辺配列Ａ（Ｓ
１，Ｓ２，…，Ｓｍ）に対する、プロセッサｐでのロー
カルなループの仮想反復範囲ＶＬＩＴＳ＿Ａ（ｐ）を求
める。同様に、逆関数ｉｎｖ＿ｆをＧＩＸＳ＿Ａ（ｐ）
に適用することによって、グローバルなループの仮想反
復範囲ＶＧＩＴＳ＿Ａ（ｐ）を求める。

【００２９】ここで、ＶＬＩＴＳ＿Ａ（ｐ）やＶＧＩＴ
Ｓ＿Ａ（ｐ）は、元のループ繰り返し範囲を考慮せず
に、ＬＩＸＳ＿Ａ（ｐ）から求めた繰り返し範囲であ
る。従って、元のループ繰り返し範囲を外れている可能
性があり、そこで「仮想」と呼んでいる。

【００３０】最後に、処理３０７で、ループ仮想反復範
囲からＬＩＴＳを求める。この処理３０７は、詳しくは
以下の手順で行う。

【００３１】まず、中間語１０３から、ＶＧＩＴＳ＿Ａ
（ｐ）とループインデックスの全区間との積集合（ｉｎ
ｔｅｒｓｅｃｔｉｏｎ）を計算し、その結果をＧＩＴＳ
＿Ａ（ｐ）とする。ＧＩＴＳ＿Ａ（ｐ）は、着目してい
る代入文の配列Ａに対するプロセッサｐでのＧＩＴＳ
（グローバル・イテレーション・セット）を表す。ＧＩ
ＴＳとは、各代入文に対して、元のループ反復範囲のう
ち各プロセッサで分担実行すべきループ反復範囲を、元
のプログラムにおけるグローバルなループインデックス
の値の取り得る範囲として、表現したものである。

【００３２】仮想反復範囲ＶＬＩＴＳ＿Ａ（ｐ）は、Ｖ
ＧＩＴＳ＿Ａ（ｐ）と直接対応するものなので、ＶＧＩ
ＴＳ＿Ａ（ｐ）とＧＩＴＳ＿Ａ（ｐ）の差分（ｄｉｆｆ
ｅｒｅｎｃｅ）を、ＶＬＩＴＳ＿Ａ（ｐ）に反映して、
配列Ａに対するプロセッサｐでのローカル・イテレーシ
ョン・セットＬＩＴＳ＿Ａ（ｐ）を求める。そして、得
られたＬＩＴＳ＿Ａ（ｐ），ＧＩＴＳ＿Ａ（ｐ）は、プ
ログラム分割情報１１０のＰＲＧ分割式テーブル３０８
（図１３）に格納する。

【００３３】図４は、ＬＩＴＳを求めて、プログラム分
割する例を示している。４０１は、元の逐次ソースプロ
グラムである。４０２は、配列データ分割パターンであ
る。１１４は、プログラム分割後の各プロセシング・エ
レメント（Ｐｒｏｃｅｓｓｉｎｇ Ｅｌｅｍｅｎｔ：以
下、ＰＥと略す）のノードプログラムである。

【００３４】図３および図４を参照して、プログラム４
０１をプログラム分割する手順を説明する。このプログ
ラム４０１における配列Ａを、データ分割パターン４０
２に従って、４つのＰＥに割り付ける。

【００３５】まず、処理３０１では、データ分割パター
ンに従って、配列Ａについての各プロセッサのＬＩＸＳ
を求める。ここでは、 ＬＩＸＳ＿Ａ（ｐ）＝［１：２５，１：１００］，（ｐ
＝０，１，２，３） である。ここで、［］内に並んでいる複数個の値の区間
は左のものほど、外側のループのインデックスに対応し
ている。すなわち、「１：２５」の区間は外側のインデ
ックス変数Ｉのループに対応し、「１：１００」の区間
は内側のインデックス変数Ｊのループに対応している。

【００３６】処理３０３では、ＬＩＸＳ＿Ａ（ｐ）に対
応するＧＩＸＳ＿Ａ（ｐ）を求める。ここでは、 ＧＩＸＳ＿Ａ（１）＝（［１：２５］，［１：１０
０］） ＧＩＸＳ＿Ａ（２）＝（［２６：５０］，［１：１０
０］） ＧＩＸＳ＿Ａ（３）＝（［５１：７５］，［１：１０
０］） ＧＩＸＳ＿Ａ（４）＝（［７６：１００］，［１：１０
０］） となる。

【００３７】処理３０５では、添字関数の逆関数を計算
する。代入文の左辺配列参照Ａ（Ｉ−１，Ｊ）に対する
添字関数ｆは、ｆ（Ｉ，Ｊ）＝（Ｉ−１，Ｊ）であるか
ら、添字関数ｆの逆関数は、ｉｎｖ＿ｆ（Ｃ，Ｄ）＝
（Ｃ＋１，Ｄ）である。

【００３８】処理３０６で、この逆関数ｉｎｖ＿ｆをＬ
ＩＸＳ＿Ａ（ｐ）に適用することによって、Ａ（Ｉ−
１，Ｊ）に対するプロセッサｐでのループ仮想反復範囲
（元のループ反復でのローカルインデックスで表現した
範囲）ＶＬＩＴＳ＿Ａ（ｐ）を求めると、 ＶＬＩＴＳ＿Ａ（ｐ）＝ｉｎｖ＿ｆ（ＬＩＸＳ＿Ａ
（ｐ）） ＝ｉｎｖ＿ｆ（［１：２５］，［１：１００］） ＝（［２：２６］，［１：１００］） （ｐ＝１，２，３，４） となる。

【００３９】また、逆関数ｉｎｖ＿ｆをＧＩＸＳ＿Ａ
（ｐ）に適用することによってＶＧＩＴＳ＿Ａ（ｐ）を
求めると、 ＶＧＩＴＳ＿Ａ（１）＝ｉｎｖ＿ｆ（ＧＩＸＳ＿Ａ
（１））＝（［２：２６］，［１：１００］） ＶＧＩＴＳ＿Ａ（２）＝ｉｎｖ＿ｆ（ＧＩＸＳ＿Ａ
（２））＝（［２７：５１］，［１：１００］） ＶＧＩＴＳ＿Ａ（３）＝ｉｎｖ＿ｆ（ＧＩＸＳ＿Ａ
（３））＝（［５２：７６］，［１：１００］） ＶＧＩＴＳ＿Ａ（４）＝ｉｎｖ＿ｆ（ＧＩＸＳ＿Ａ
（４））＝（［７７：１０１］，［１：１００］） となる。

【００４０】処理３０７では、ＶＧＩＴＳ＿Ａ（ｐ）と
元のループの反復の全範囲（［２：９９］、［２：１０
０］）との積集合（ｉｎｔｅｒｓｅｃｔｉｏｎ）の結果
として、ＧＩＴＳ＿Ａ（ｐ）を求めると、 ＧＩＴＳ＿Ａ（１） ＝ＶＧＩＴＳ＿Ａ（１）∩（［２：９９］，［２：１００］） ＝（［２：２６］，［２：１００］） ＧＩＴＳ＿Ａ（２） ＝ＶＧＩＴＳ＿Ａ（２）∩（［２：９９］，［２：１００］） ＝（［２７：５１］，［２：１００］） ＧＩＴＳ＿Ａ（３） ＝ＶＧＩＴＳ＿Ａ（３）∩（［２：９９］，［２：１００］） ＝（［５２：７６］，［２：１００］） ＧＩＴＳ＿Ａ（４） ＝ＶＧＩＴＳ＿Ａ（４）∩（［２：９９］，［２：１００］） ＝（［７７：９９］，［２：１００］） となる。

【００４１】ＶＧＩＴＳ＿Ａ（ｐ）とＧＩＴＳ＿Ａ
（ｐ）に相違があるのは、ｐ＝３の場合の（［７７：１
０１］、［１：１００］）対（［７７：９９］、［２：
１００］）だけである。この相違（反復範囲の縮小）
を、ＶＬＩＴＳ＿Ａ（ｐ）に反映して、最終的なＬＩＴ
Ｓ＿Ａ（ｐ）を求めると、 ＬＩＴＳ＿Ａ（１）＝（［２：２６］，［２：１０
０］） ＬＩＴＳ＿Ａ（２）＝（［２：２６］，［２：１０
０］） ＬＩＴＳ＿Ａ（３）＝（［２：２６］，［２：１０
０］） ＬＩＴＳ＿Ａ（４）＝（［２：２６−２］，［２：１０
０］）＝（［２：２４］，［２：１００］） となる。

【００４２】以上、ＬＩＴＳを求める処理１０８の結果
として、配列Ａの宣言とＤＯループ反復範囲は、各ＰＥ
のノードプログラム１１４で示すようになる。

【００４３】一般に、ＬＩＴＳは、各代入文ごとに変わ
り得る。従来法では、下記の２つの場合しか扱っていな
い。２つの場合とは、同一ループ内の各代入文が同一Ｇ
ＩＴＳである場合と、各代入文が異なるＧＩＴＳであっ
ても、ループ分割可能であり、ループ分割した結果、ル
ープ内の各代入文が同一ＧＩＴＳになる場合である。

【００４４】図５は、同一ループ内の各代入文が異なる
ＧＩＴＳで、ループ分割可能な例を示している。５０１
は、元の逐次ソースプログラムである。５０２は配列Ａ
のデータ分割パターンで、５０３は配列Ｂのデータ分割
パターンである。１１４は、プログラム分割の結果得ら
れる各ＰＥのノードプログラムである。

【００４５】逐次ソースプログラム５０１をプログラム
分割するとき、配列Ａはデータ分割パターン５０２に従
って４つのＰＥに割り付け、配列Ｂはデータ分割パター
ン５０３に従って、データ分割せずに全配列データを４
つのＰＥに割り付ける。配列Ａに対する代入文と配列Ｂ
に対する代入文は依存関係がないので、ループ５００は
ループ分割でき、各代入文ごとにループを生成する。

【００４６】各ＰＥのノードプログラム１１４におい
て、配列Ａへの代入のためのループ５１０と、配列Ｂへ
の代入のためのループ５２０では、ループ制御変数Ｉの
ループ繰り返し範囲は、それぞれ１から４までと１から
１６までになる。

【００４７】また、別の論文、シーマ・ヒラナンダニ，
ケン・ケネディ，チョウ・ウンスク共著”ＭＩＭＤ分散
メモリ型計算機に対するＦＯＲＴＲＡＮ Ｄ コンパイ
ル方式”（Ｓｅｅｍａ Ｈｉｒａｎａｎｄａｎｉ，Ｋｅ
ｎ Ｋｅｎｎｅｄｙ ａｎｄＣｈａｕ−Ｗｅｎ Ｔｓｅ
ｎｇ：”Ｃｏｍｐｉｌｉｎｇ ＦＯＲＴＲＡＮ Ｄｆｏ
ｒ ＭＩＭＤ Ｄｉｓｔｒｉｂｕｔｅｄ−Ｍｅｍｏｒｙ
Ｍａｃｈｉｎｅｓ”）（ＣＯＭＭＵＩＣＡＴＩＯＮＳ
ＯＦ ＴＨＥ ＡＣＭ，Ａｕｇｕｓｔ１９９２，Ｖｏ
ｌ．３５，Ｎｏ．８，ｐｐ６６−８０）では、ループ内
にある各代入文に対して、各代入文のＬＩＴＳの和集合
ＵＬＩＴＳ（このとき、ＵＬＩＴＳは等差数列になるよ
うにする）をとり、各代入文はＵＬＩＴＳのうち対応す
る元のＬＩＴＳだけを実行するようにしている。

【００４８】図６は、同一ループ内の各代入文が、異な
るＧＩＴＳを持つ場合のプログラム分割例を示してい
る。６０１は、元の逐次ソースプログラムである。６０
２は、配列データ分割パターンである。１１４は、プロ
グラム分割の結果得られる各ＰＥのノードプログラムで
ある。

【００４９】逐次ソースプログラム６０１をプログラム
分割するとき、配列Ａはデータ分割パターン６０２に従
って、４つのＰＥに割り付ける。

【００５０】代入文６０４はＬＩＴＳ＿Ａ（ｐ）＝
［１：４］、代入文６０５はＬＩＴＳ＿Ａ（ｐ）＝［１
３：１６］なので、これらの和集合ＵＬＩＴＳ＿Ａ
（ｐ）＝［１：４］∪［１３：１６］となる。ループ繰
り返し範囲は、この和集合が連続する範囲である［１：
１６］とする。プログラム分割の結果、各ＰＥのノード
プログラムは１１４に示すものとなる。

【００５１】

【発明が解決しようとする課題】ところで、上記従来技
術では、ループ内にある複数の代入文の左辺に現われる
配列の分割方法が異なる場合、各代入文ごとに、ＬＩＴ
Ｓに対応するＧＩＴＳが異なるにもかかわらずＬＩＴＳ
を共有することになる。従って、各プロセッサで、各代
入文間の実行順序が元の逐次プログラムでの実行順序と
異なることがあり、結果が不正となる可能性がある。

【００５２】図７は、同一ループ内にある複数代入文の
左辺に現われる配列の分割方法が各々異なるために、各
プロセッサのループの各回で、代入文間の実行順序が逐
次の実行順序と異なる例を示している。７０１は、元の
逐次ソースプログラムである。７０２と７０３は、配列
データ分割パターンである。１１４は、プログラム分割
の結果得られる各ＰＥのノードプログラムである。

【００５３】逐次ソースプログラム７０１をプログラム
分割するとき、配列Ａのデータ分割パターン７０２と、
配列Ｂのデータ分割パターン７０３より、代入文７０４
に対するＬＩＴＳ＿Ａ（ｐ）＝［１：４］、代入文７０
５に対するＬＩＴＳ＿Ｂ（ｐ）＝［１：４］となる。従
って、ループ７００におけるループ制御変数Ｉのループ
繰り返し範囲は、１から４までとなる。

【００５４】これは、プロセッサＰＥ１では、Ｉ＝１の
ときＡ（１）とＢ（１）の計算を、Ｉ＝２のときＡ
（２）とＢ（５）の計算を、それぞれ実行することにな
る。

【００５５】ところが、Ｂ（５）の計算では、Ｉ＝４で
定義されるＡ（４）を使用しなければならないので、Ｂ
（５）の計算において未定義のＡ（４）を使用すること
になり、結果が不正になる。

【００５６】さらに、図６のように代入文左辺に現われ
る配列の添字式が異なる場合に、前述のようにループ繰
り返し範囲を拡大すると、実際には代入文が実行されな
いループ繰り返しも回ることになる（例えば、図６のノ
ードプログラム１１４のＤＯループでＩ＝５〜１２のと
き）ので、無駄なループ繰り返しがあり性能向上が図れ
ない。

【００５７】本発明は、逐次ソースプログラムを並列計
算機向きに変換する際に用いるプログラム分割方法にお
いて、代入文左辺に現われる配列の分割方法が異なるこ
とによる結果不正を起こさないこと、および代入文左辺
に現われる配列の添字式が異なるためにループ繰り返し
範囲が拡大されて無駄なループ繰り返しを実行するよう
なことがなく、必要不可欠なループ繰り返しだけを実行
し、性能向上を図ることを目的とする。

【００５８】

【課題を解決するための手段】上記目的を達成するた
め、本発明は、逐次ソースプログラムを入力して、分散
記憶型並列計算機向きの並列化ソースプログラムまたは
オブジェクトプログラムを生成する言語変換システムに
おいて、該逐次ソースプログラム中のループに対し、各
プロセッサが分担して計算するループ繰り返し範囲を求
めるプログラム分割方法であって、上記逐次ソースプロ
グラム中で宣言されているデータの各プロセッサへの割
り付け方を示すデータ分割指示情報を入力するステップ
と、各プロセッサごとに、ループ内の各代入文の代入先
のデータが該プロセッサに割り付けられているときのル
ープインデックスの和集合をリストベクトルとして保持
するステップと、該プロセッサでのループ実行回数をそ
のリストベクトルの要素数とするとともに、ループ内の
代入文に現れるループインデックスを上記リストベクト
ルの参照に置き換えるステップとを備えたことを特徴と
する。

【００５９】前記リストベクトルは、言語変換時に決定
できる場合は、言語変換時に決定してその値を並列化プ
ログラムに登録し、プログラム中で参照できるようにす
るとよい。また、実行時にリストベクトルを計算する処
理を、並列化プログラムに含めるようにしてもよい。

【００６０】さらに、本発明は、逐次ソースプログラム
を入力して、分散記憶型並列計算機向きの並列化ソース
プログラムまたはオブジェクトプログラムを生成する言
語変換システムにおいて、該逐次ソースプログラム中の
ループに対し、各プロセッサが分担して計算するループ
繰り返し範囲を求めるプログラム分割方法であって、上
記逐次ソースプログラム中の配列の各プロセッサへの割
り付け方を示すデータ分割指示情報を入力するステップ
と、該データ分割指示情報に基づいて、ループ内の各代
入文ごとに、その代入文に対して元のループ反復範囲の
うち各プロセッサで分担実行すべきループ反復範囲を示
すループインデックスの集合であるグローバル・イテレ
ーション・セットを求めるステップと、各プロセッサご
とに、ループ内のすべての代入文に対応する上記グロー
バル・イテレーション・セットの和集合を求め、該和集
合の要素をソートしてリストベクトルとして保持するス
テップと、各プロセッサでのループ反復回数を上記リス
トベクトルの要素数とするとともに、ループ内の代入文
の配列の添字式中のループインデックスを上記リストベ
クトルの参照に置き換えるステップとを備えたことを特
徴とする。

【００６１】また、逐次ソースプログラムを入力して、
分散記憶型並列計算機向きの並列化ソースプログラムま
たはオブジェクトプログラムを生成する言語変換システ
ムにおいて、該逐次ソースプログラム中のループに対
し、各プロセッサが分担して計算するループ繰り返し範
囲を求めるプログラム分割方法であって、上記逐次ソー
スプログラム中の配列の各プロセッサへの割り付け方を
示すデータ分割指示情報を入力するステップと、該デー
タ分割指示情報に基づいて、ループ内の各代入文ごと
に、その代入文に対して元のループ反復範囲のうち各プ
ロセッサで分担実行すべきループ反復範囲を示す下限
式、上限式、および増分式を求めるステップと、上記下
限式、上限式、および増分式を用いて、各代入文に対応
するループ反復範囲を示すループインデックス値の集合
を算出する文を生成するステップと、各プロセッサごと
に、ループ内のすべての代入文に対応する上記ループイ
ンデックス値の集合の和集合を求め、該和集合の要素を
ソートしてリストベクトルとして設定する文を生成する
ステップと、各プロセッサでのループ反復回数を上記リ
ストベクトルの要素数とするとともに、ループ内の代入
文の配列の添字式中のループインデックスを上記リスト
ベクトルの参照に置き換えるステップとを備えたことを
特徴とする。

【００６２】さらに、任意のループインデックスに対し
て、前記リストベクトルの該ループインデックス番目の
要素が前記ループ内の代入文のグローバル・イテレーシ
ョン・セットに含まれるときのみその代入文を実行する
ように変更してもよい。

【００６３】

【作用】本発明によれば、各プロセッサごとに、ループ
内の各代入文の代入先のデータが該プロセッサに割り付
けられているときのループインデックスの和集合をリス
トベクトルとして求めている。従って、代入文ごとのＧ
ＩＴＳ（グローバル・イテレーション・セット）の和集
合をループ繰り返しの範囲とすることになり、従来例の
ようにＧＩＴＳが異なるにもかかわらずＬＩＴＳ（ロー
カル・イテレーション・セット）を共有するようなこと
がないので、結果不正にならない。

【００６４】また、各代入文のＬＩＴＳが互いに排反で
ＬＩＴＳが非連続になる場合でも、リストベクトルの要
素数の回数だけループ繰り返しを行うようにしており、
さらにリストベクトルの値がＧＩＴＳに含まれるときの
みその代入文を実行するようにしているので、無駄なル
ープ繰り返しを行なうことがない。

【００６５】

【実施例】以下、本発明の実施例を図１および図８から
図２４を用いて説明する。

【００６６】図１は、本発明に係るプログラム分割方法
を適用した自動並列化変換システムにおける処理手順の
概要を示す。

【００６７】自動並列化処理１００では、まず構文解析
処理１０２で、データ分割指示付きソースプログラム１
０１を入力し、これを中間語１０３に変換し、辞書１０
４に登録して、データ分割情報１０５を設定する。

【００６８】プログラム分割処理１０６（図８，図９）
は、この中間語１０３とデータ分割情報１０５を入力
し、プログラム分割処理方法判定部１０７で判定して、
単一文におけるプログラム分割処理１０８（図３）、ま
たはリストベクトルによるプログラム分割処理１０９
（図１０，図１１）を実行し、結果をプログラム分割情
報１１０として格納し、中間語１０３と辞書１０４を変
更、追加する。

【００６９】次に、このプログラム分割情報１１０、中
間語１０３、およびデータ分割情報１０５を入力し、非
局所データの有無を解析して、非局所データ解析情報１
１２を設定し、プロセッサ間通信生成処理１１１を行
い、中間語１０３を変更する。非局所データとは、自プ
ロセッサのローカルメモリに無いデータ（すなわち、他
のプロセッサから通信により得ることが必要であるデー
タ）のことである。

【００７０】最後に、この中間語１０３と辞書１０４、
およびデータ分割情報１０５とプログラム分割情報１１
０を入力して、ノードプログラム生成処理１１３を行
い、各プロセッサで動作させるノードプログラム１１４
を出力する。

【００７１】次に、図１のプログラム分割処理１０６に
おいて用いている各種の情報について説明する。

【００７２】図１２は、データ分割情報１０５に設定さ
れるデータ分割テーブル３０２を示す。データ分割テー
ブル３０２は、ソースプログラム中の各配列の各次元に
おけるＧＩＸＳとＬＩＸＳとを格納（詳しくは、ＧＩＸ
ＳやＬＩＸＳへのポインタを格納）するテーブルであ
る。

【００７３】データ分割テーブル３０２は、配列名１２
０１と、配列の各次元へのポインタＤＩＭｐ１２０２か
ら成る。ポインタＤＩＭｐ１２０２で指された各次元の
情報は、次元番号１２０３と、ＧＩＸＳ（図１５）への
ポインタＧＩＸＳｐ１２０４と、ＬＩＸＳ（図１５）へ
のポインタＬＩＸＳｐ１２０５と、次の次元へのポイン
タＤＩＭｐ１２０２から成る。

【００７４】図１３は、プログラム分割情報１１０のＰ
ＲＧ（プログラム）分割式テーブル３０８を示す。ＰＲ
Ｇ分割式テーブル３０８は、プログラム分割対象の各ル
ープの分割に関するデータを格納するテーブルである。

【００７５】すなわち、ＰＲＧ分割式テーブル３０８
は、ループ番号１３０１と、次のループに関するデータ
へのポインタ１３０２と、処理番号１３０３と、ＬＩＴ
Ｓ（図１５）へのポインタＬＩＴＳｐ１３０４と、ルー
プに含まれる文へのポインタ１３０５からなる。処理番
号１３０３とは、そのループに係るプログラム分割処理
が、単一代入文に対する方法か、静的リストベクトルに
よる方法か、または動的リストベクトルによる方法かを
示す番号である。各方法の手順は、後述する。

【００７６】ポインタ１３０５で指されるループ内の文
に関するデータは、文番号１３０６と、この文に対する
ＧＩＴＳ（図１５）へのポインタＧＩＴＳｐ１３０７
と、次の文へのポインタ１３０５から成る。

【００７７】図１４は、プログラム分割情報のＰＲＧ
（プログラム）分割値テーブル８０８を示す。ＰＲＧ分
割値テーブル８０８は、プログラム分割対象の各ループ
の分割に関するデータを格納するテーブルである。上記
の図１３のＰＲＧ分割式テーブルと同様のデータを格納
するが、図１３のＰＲＧ分割式テーブルでは式の形式で
各ループのＬＩＴＳや各文のＧＩＴＳを格納するのに対
し、図１４のＰＲＧ分割値テーブル８０８では具体的な
値で格納する。

【００７８】ＰＲＧ分割値テーブル８０８は、ループ番
号１３０１、次のループへのポインタ１３０２、および
プロセッサごとのＬＩＴＳに関するテーブルへのポイン
タ１４０１を備えている。

【００７９】ポインタ１４０１で指されたプロセッサご
とのＬＩＴＳに関する情報は、プロセッサ（ＰＥ）番号
１４０２、次のプロセッサのＬＩＴＳ情報へのポインタ
１４０１、ＬＩＴＳ（図１５）へのポインタＬＩＴＳｐ
１３０４、リストベクトルＬ１４０４へのポインタＬＩ
ＳＴｐ１４０３、およびループ内に含まれる文へのポイ
ンタ１３０５から成る。

【００８０】ポインタ１３０５で指されるループ内の文
に関する情報は、文番号１３０６、ＧＩＴＳ（図１５）
へのポインタＧＩＴＳｐ１３０７、および次の文へのポ
インタ１３０５から成る。

【００８１】リストベクトルは各ループに対応して設け
られる１次元配列である。その配列の要素数は、対応す
るループの繰り返し回数である。リストベクトルの各要
素には、ループ内の各代入文のＧＩＴＳがソートして格
納される。リストベクトルについては、後の具体例など
で詳述する。

【００８２】図１５は、上述したポインタＧＩＸＳｐ１
２０４，ＬＩＸＳｐ１２０５，ＬＩＴＳｐ１３０４，Ｇ
ＩＴＳｐ１３０７で指されるテーブルを示す。

【００８３】これらは共通のテーブルで表わすことがで
き、それは、先頭プロセッサの範囲式へのポインタｐｒ
ｅ＿ＲＡＮＧＥｐ１５０１、中間プロセッサに対する範
囲式へのポインタｍｉｄ＿ＲＡＮＧＥｐ１５０２、終端
プロセッサに対する範囲式へのポインタｐｏｓｔ＿ＲＡ
ＮＧＥｐ１５０３から成る。

【００８４】範囲式は、下限式へのポインタ１５０４、
上限式へのポインタ１５０５、増分式へのポインタ１５
０６、および非連続で等差数列で表現できない範囲式同
士をリストでつなぐための次の範囲式へのポインタ１５
０７から成る。

【００８５】次に、図１のプログラム分割処理１０６に
ついてさらに詳細に説明する。ここでは、プログラム分
割処理として、静的プログラム分割処理および動的プロ
グラム分割処理の２つの処理方式を説明する。静的プロ
グラム分割処理とは、ソースプログラムのコンパイル時
にループの繰り返し範囲が確定できる場合のプログラム
分割処理である。動的プログラム分割処理とは、そのプ
ログラムを実行したときにループの繰り返し範囲を確定
するプログラム分割処理である。

【００８６】まず、静的プログラム分割処理について説
明する。

【００８７】図８は、プログラム分割処理部１０６にお
ける静的プログラム分割処理の処理手順を示す。プログ
ラム分割処理部１０６は、中間語１０３、辞書１０４、
およびデータ分割情報１０５を入力して、処理を開始す
る。

【００８８】まず、終了判定部８０１でプログラムが終
りであるか否かを判定する。終りであれば、プログラム
分割処理１０６は終了となる。そうでなければ、ソース
プログラム中の次のループをみつける処理８０２を行
う。

【００８９】ループがみつかったら、そのループ内の代
入文が単一か複数かの判定８０３を行う。そのループ内
に代入文が１つしかないなら、従来方法でプログラム分
割すればよいから、まずデータ分割情報１０５にあるデ
ータ分割テーブル３０２（図１２）と大域化関数３０４
を参照して代入文のＧＩＴＳを計算し、計算結果をプロ
グラム分割情報１１０にあるＰＲＧ分割式テーブル３０
８（図１３）ヘ書き込む処理１０８（図３）を行う。

【００９０】さらに、ＬＩＴＳを計算して、計算結果と
プログラム分割処理番号０とをＰＲＧ分割式テーブル３
０８（図１３）ヘ書き込む処理を行い、再び処理８０１
に戻る。プログラム分割処理番号０は、プログラム分割
処理が、単一代入文に対する方法であることを明示する
ためのものである。

【００９１】一方、ループが複数の代入文を含む場合
は、ループ分割可否判定部８０４で、ループを分割する
ことが可能か否か判定する。ループ分割可能なら、図５
で説明したのと同様にしてループ分割処理８０５を行
い、再びループ分割した各ループについて判定８０３を
行う。

【００９２】ループ分割不可能なら、データ分割情報１
０５のデータ分割テーブル３０２（図１２）と大域化関
数３０４を参照して、各代入文のＧＩＴＳを計算する処
理１０８（図３）を実行し、結果をＰＲＧ分割式テーブ
ル３０８（図１３）へ書き込む。そして、各代入文のＧ
ＩＴＳが同一であるか否かの判定８０６を行う。

【００９３】この結果、同一ＧＩＴＳであれば、単一代
入文のときと同様になり、ＬＩＴＳを計算する処理１０
８（図３）を行い、ＰＲＧ分割式テーブル３０８（図１
３）へ計算結果とプログラム分割処理番号０を書き込
む。

【００９４】各代入文のＧＩＴＳが異なるなら、ＰＲＧ
分割式テーブル３０８（図１３）を参照して、静的リス
トベクトル計算処理生成８０７（図１０）を実行し、結
果をＰＲＧ分割値テーブル８０８（図１４）へ書き込
む。そして、再び、判定８０１に戻る。静的リストベク
トル計算処理生成８０７の詳細は後述する。

【００９５】次に、動的プログラム分割処理について説
明する。

【００９６】図９は、動的プログラム分割処理の処理手
順を示す。同図の処理手順は、図８の静的プログラム分
割処理の処理手順とほぼ同じであるが、下記の点が異な
る。すなわち、図８の静的リストベクトル計算処理生成
部８０７（図１０）に代えて、動的リストベクトル計算
処理生成部９０１（図１１）とし、プログラム分割情報
１１０のプログラム分割式テーブル３０８（図１３）を
入力して、中間語１０３に新たに動的リストベクトル計
算処理を行う中間語を追加するようにしている。動的リ
ストベクトル計算処理生成部９０１の詳細は後述する。

【００９７】図１０は、静的リストベクトル計算処理生
成の詳細な処理手順を示す。静的リストベクトル計算処
理生成部８０７は、中間語１０３と、プログラム分割情
報１１０のＰＲＧ分割式テーブル３０８（図１３）を入
力し、中間語１０３を変更し、プログラム分割情報１１
０に、ＰＲＧ分割値テーブル８０８（図１４）を追加す
る。

【００９８】まず、プログラム分割情報１１０のＰＲＧ
分割式テーブル３０８（図１３）の処理番号を１に設定
し、このＰＲＧ分割式テーブル３０８（図１３）のルー
プ番号および文番号をＰＲＧ分割値テーブル８０８（図
１４）へ複写する処理１００１を行う。処理番号を１に
設定するのは、プログラム分割処理が静的リストベクト
ルによる方法であることを明示するためである。

【００９９】次に、ＰＲＧ分割式テーブル３０８（図１
３）のＧＩＴＳから、各プロセッサごとに、具体的なＧ
ＩＴＳの値を計算する処理１００２を実行して、計算結
果をＰＲＧ分割値テーブル８０８（図１４）へ格納す
る。

【０１００】次に、リストベクトルとして、元のループ
繰り返し回数の大きさ（要素数）の配列を、プロセッサ
台数分用意する処理１００３を行う。リストベクトル
は、ＰＲＧ分割値テーブル８０８（図１４）内に用意す
る。

【０１０１】その後、以下の処理１００４を行う。すな
わち、プロセッサ番号ｐごとに、ＰＲＧ分割値テーブル
８０８（図１４）の各代入文のＧＩＴＳの和集合を計算
する。そして、重複を除いたその和集合の要素数をｎと
するとき、各要素を、プロセッサ番号ｐに対応するリス
トベクトルＬｐ（１：ｎ）に、格納する。格納する際に
は、元のループの増分値が正なら昇順に、負なら降順に
ソートして格納するようにする。

【０１０２】次に、対象ループの繰り返し範囲ＬＩＴＳ
を［１：ｎ：１］とし、各代入文の中間語を「Ｌｐ
（Ｉ）が各代入文のＧＩＴＳに含まれるときのみ、その
文を実行する」ような中間語に変更する処理１００５を
行う。なお、ループの繰り返し範囲［ｌ：ｕ：ｄ］は、
ｌが下限、ｕが上限、ｄが増分値を表すものとする。Ｉ
は、対象ループのループインデックス変数（ループ制御
変数）である。

【０１０３】最後に、代入文の配列添字を、Ｌｐ（Ｉ）
となるような中間語に変える処理１００６を行う。

【０１０４】図１１は、動的リストベクトル計算処理生
成の詳細な処理手順を示す。動的リストベクトル処理生
成部９０１は、中間語１０３、およびプログラム分割情
報１１０を入力する。

【０１０５】初めに、プログラム分割情報１１０のＰＲ
Ｇ分割式テーブル３０８（図１３）の処理番号を２に設
定する処理１１０１を実行する。これは、プログラム分
割処理が、動的リストベクトルによる方法であることを
明示するためである。

【０１０６】次に、ループ内の代入文の数をｍとし、配
列ＧＩＴＳｋ（ｋ＝１，…，ｍ）を宣言し、辞書１０４
に登録する処理１１０２を行う。各配列ＧＩＴＳｋ（ｋ
＝１，…，ｍ）の大きさ（要素数）は、それぞれ、ＰＲ
Ｇ分割式テーブル３０８（図１３）の各ＧＩＴＳｋ（ｋ
＝１，…，ｍ）の要素数の大きさと同じとする。

【０１０７】そして、各代入文（ｋ＝１，…，ｍ）ごと
に、ＰＲＧ分割式テーブル３０８（図１３）内のＧＩＴ
Ｓｋの範囲式を参照して、ループ中間語を生成し、中間
語１１０４をループ内の文となるように、ループ中間語
につなぐ処理１１０３を実行する。中間語１１０４と
は、「各代入文（ｋ＝１，…，ｍ）に対応する配列ＧＩ
ＴＳｋのインデックスＩを１だけ増やし、このときのル
ープインデックスの値をＧＩＴＳｋ（Ｉ）へ格納する」
である。言い替えると、処理１１０３では、各代入文
（ｋ＝１，…，ｍ）ごとのＧＩＴＳの具体的な値を求め
て配列ＧＩＴＳｋ（Ｉ）へ格納する処理を行うような中
間語を生成する処理を行う。

【０１０８】それから、処理１１０３で求めた同一ルー
プ内の全代入文に対する配列ＧＩＴＳｋ（ｋ＝１，…，
ｍ）を入力とし、これらの和集合をとって、重複を除く
要素数ｎを返し、分割対象ループの増分値が正なら昇順
に負なら降順にマージソートしてリストベクトルの配列
Ｌに設定するサブルーチンを、処理１１０３で追加した
ＤＯループ中間語の直後に追加する処理１１０５を実行
する。これにより、リストベクトルＬを設定する中間語
が、上記処理１１０３で生成した中間語の後に追加され
たことになる。

【０１０９】その後、各代入文の配列ＧＩＴＳｋを参照
するためのインデックス変数を初期化する中間語を生成
して、上記処理１１０５で生成した中間語の後に追加す
る処理１１０６を実行する。

【０１１０】以上、処理１１０３、１１０５、１１０６
で新たに生成した中間語を、ユーザのＤＯループ中間語
の直前に挿入する処理１１０７を実行する。

【０１１１】次に、ユーザのＤＯループ繰り返しの範囲
を［１：ｎ：１］（［下限：上限：増分値］の意）と
し、ループ内の各代入文の中間語を「Ｌ（Ｉ）が各代入
文のＧＩＴＳに含まれるときのみ、その文を実行する」
ような中間語に変える処理１００５を行う。Ｉは、対象
ループのループインデックス変数（ループ制御変数）で
ある。

【０１１２】最後に、各代入文の配列のインデックスを
Ｌ（Ｉ）となるような中間語に変える処理１００６を行
う。

【０１１３】以上で、動的リストベクトル計算処理を終
える。静的リストベクトル計算処理は、リストベクトル
の具体的な値を求めて、それを参照するようにプログラ
ムを変える。これに対し、動的リストベクトル計算処理
は、プログラムの実行時にリストベクトルの値を求める
ような中間語を追加する。すなわち、リストベクトルの
具体的な値は、プログラムの実行時に求められ、その値
が参照される。

【０１１４】次に、上述の図１および図８〜図１１で説
明した自動並列化処理１００によって、図７の逐次ソー
スプログラム７０１についてプログラム分割処理１０６
を行う具体例を説明する。

【０１１５】図１６は、図７の逐次ソースプログラム７
０１の配列Ａのデータ分割テーブル３０２を示す。配列
Ａ（０：１７）は、図１の構文解析処理１０２におい
て、図７のデータ分割パターン７０２に従ってデータ分
割される。

【０１１６】配列Ａに対するＧＩＸＳとＬＩＸＳは、具
体的には以下のようになる。なお、配列Ａに対するプロ
セッサｐでのＧＩＸＳをＧＩＸＳ＿Ａ（ｐ）と表わす。

【０１１７】 ＧＩＸＳ＿Ａ（１）＝｛０，１，２，３，４｝ ＧＩＸＳ＿Ａ（２）＝｛５，６，７，８｝ ＧＩＸＳ＿Ａ（３）＝｛９，１０，１１，１２｝ ＧＩＸＳ＿Ａ（４）＝｛１３，１４，１５，１６，１
７｝ ＬＩＸＳ＿Ａ（ｐ）＝｛０，１，２，３，４，５｝ （ｐ＝１，２，３，４） これをデータ分割テーブル３０２に書き込むと図１６に
なる。ＬＩＸＳｐ１２０５は、全プロセッサで共通の範
囲式１６０１を指す。なお、説明の便宜のため、図１５
のポインタ１５０４，１５０５，１５０６は、図１６で
はポインタでなく式（あるいは値）そのものを記載して
いる。以下の図１７〜図１９でも同様とする。

【０１１８】図１７は、図７の逐次ソースプログラム７
０１の配列Ｂのデータ分割テーブル３０２を示す。配列
Ｂ（０：１７）は、図１の構文解析処理１０２におい
て、図７のデータ分割パターン７０３に従ってデータ分
割される。

【０１１９】配列Ｂに対するＧＩＸＳとＬＩＸＳは、具
体的には以下のようになる。

【０１２０】 ＧＩＸＳ＿Ｂ（１）＝｛１，５，９，１３，１７｝ ＧＩＸＳ＿Ｂ（２）＝｛２，６，１０，１４｝ ＧＩＸＳ＿Ｂ（３）＝｛３，７，１１，１５｝ ＧＩＸＳ＿Ｂ（４）＝｛０，４，８，１２，１６｝ ＬＩＸＳ＿Ｂ（ｐ）＝｛０，１，２，３，４，５｝ これをデータ分割テーブル３０２に書き込むと図１７に
なる。

【０１２１】図１の構文解析処理１０２において図１６
および図１７のデータ分割テーブル３０２を作成した
後、図８（または図９）のプログラム分割処理１０６を
行う。プログラム分割処理１０６では、図７の逐次ソー
スプログラム７０１のループ７００が複数代入文を含む
ため、判定８０３を介して、ループ分割可否判定８０４
を行う。ループ７００はループ分割できないので、各代
入文７０４、７０５のＧＩＴＳを計算する処理１０８を
行う。

【０１２２】その結果、文７０４のＧＩＴＳは、 ＧＩＴＳ＿Ａ（１）＝｛１，２，３，４｝ ＧＩＴＳ＿Ａ（２）＝｛５，６，７，８｝ ＧＩＴＳ＿Ａ（３）＝｛９，１０，１１，１２｝ ＧＩＴＳ＿Ａ（４）＝｛１３，１４，１５，１６｝ ＧＩＴＳ＿Ａ（ｐ）＝｛４ｐ−３，４ｐ−２，４ｐ−
１，４ｐ｝ （ｐ＝１，２，３，４） となる。

【０１２３】また、文７０５のＧＩＴＳは、 ＧＩＴＳ＿Ｂ（１）＝｛１，５，９，１３｝ ＧＩＴＳ＿Ｂ（２）＝｛２，６，１０，１４｝ ＧＩＴＳ＿Ｂ（３）＝｛３，７，１１，１５｝ ＧＩＴＳ＿Ｂ（４）＝｛４，８，１２，１６｝ ＧＩＴＳ＿Ｂ（ｐ）＝｛ｐ，４＋ｐ，８＋ｐ，１２＋
ｐ｝ （ｐ＝１，２，３，４） となる。

【０１２４】図８の処理１０８では、これらの文７０
４、７０５のＧＩＴＳを表す式を、ＰＲＧ分割式テーブ
ル３０８へ書き込む。図１８は、ＧＩＴＳを表す式を書
き込んだＰＲＧ分割式テーブル３０８を示す。

【０１２５】ポインタ１３０７が指す範囲式が、全プロ
セッサに対するＧＩＴＳを表す式になる。具体的には、
文７０４では範囲式１８０１、文７０５では範囲式１８
０２と共通になる。すなわち、プロセッサ番号をｐとす
ると、文７０４ではＧＩＴＳの範囲が［４ｐ−３：４
ｐ：１］となり、文７０５では［ｐ：１２＋ｐ：４］と
なる。

【０１２６】次に、図８の判定８０６で、各代入文が同
一ＧＩＴＳか否か判定する。ここでは異なるＧＩＴＳで
あるから、リストベクトル計算処理生成１０９を実行す
る。上述したように、リストベクトル計算処理生成とし
ては、静的リストベクトル計算処理生成８０７（図１
０）の場合と、動的リストベクトル計算処理生成８０７
（図１１）の場合とがある。

【０１２７】初めに、静的リストベクトル計算処理生成
８０７を行う場合について図１０を参照して説明する。

【０１２８】まず、処理１００１で、プログラム分割式
テーブル３０８（図１８）の処理番号１３０３を１に設
定し、ＰＲＧ分割式テーブル３０８（図１８）から、Ｐ
ＲＧ分割値テーブル８０８（図１９）を生成し、ループ
番号１３０１、および文番号１３０６をコピーする。続
いて、処理１００２で、各プロセッサごとに各代入文７
０４、７０５のＧＩＴＳの値１９０１、１９０２を算出
し格納する。

【０１２９】次に、処理１００３で、リストベクトル１
４０４をプロセッサ台数分用意する。ここでは、プロセ
ッサが４台あるから、それに対応してリストベクトルＬ
ｐ（ｐ＝１，２，３，４）を用意する。

【０１３０】そして、処理１００４で、ＧＩＴＳ＿Ａ
（ｐ）１９０１とＧＩＴＳ＿Ｂ（ｐ）１９０２の和集合
をとり、リストベクトルＬｐ１９０３にソートして格納
する。図１９のリストベクトル１４０４は、処理１００
４を行った結果を示す。

【０１３１】次に、処理１００５で、ループ繰り返しの
範囲ＬＩＴＳ１９０４を設定する。この例では、各リス
トベクトルの要素数は７であるから、どのプロセッサも
［１：７：１］とする。そして、図１０の処理１００５
で説明したように、Ｉをループインデックス（ループ制
御変数）として、Ｌｐ（Ｉ）が各代入文のＧＩＴＳに含
まれるときのみにその代入文が実行されるように中間語
を変更する。また、処理１００６で、代入文の配列添字
をＬｐ（Ｉ）とするように中間語を変更する。

【０１３２】結果として、静的プログラム分割処理後の
プログラムは、図２０になる。

【０１３３】図２０において、実行文の最初の文２００
１で、自分のプロセッサ番号（ｐ＝１，…，４）を得
る。なお、文２００１の生成は図１のノードプログラム
生成１１３で行う。

【０１３４】図２０のプログラムでは、ＤＯループの繰
り返し範囲を、１，２，…，ｎｐとしている。これは上
記の処理１００５により、ループ繰り返し範囲を、各プ
ロセッサごとの各代入文のＧＩＴＳの和集合の要素数ｎ
ｐとしたものである。また、各代入文２００４，２００
５は、それぞれ条件文２００２，２００３によって、実
行すべきループ繰り返し回だけを処理するようにガード
をかけている。これは、上記の処理１００５によって、
Ｌｐ（Ｉ）が各代入文のＧＩＴＳに含まれるときのみに
その代入文が実行されるようにしたものである。

【０１３５】さらに、代入文２００４，２００５では、
図７の元の代入文７０４，７０５で配列要素を定義また
は参照するためのインデックスＩをＬｐ（Ｉ）に置き換
えている。これは上記の処理１００６により、代入文２
００４，２００５の配列添字を、リストベクトル内のＧ
ＩＴＳを表わす配列要素に変換したものである。

【０１３６】以上で、図７の逐次ソースプログラム７０
１を静的プログラム分割した後のプログラム（図２０）
が得られた。この後、プロセッサ間通信生成（図１の処
理１１１）とノードプログラム生成（図１の処理１１
３）を行い、ＰＲＧ分割値テーブル８０８（図１９）を
参照して、最終的な並列ノードプログラム１１４（図２
１）を得る。

【０１３７】図２１の並列ノードプログラム１１４にお
いて、配列Ａのデータ分割関数をｆＡ、配列Ｂのデータ
分割関数をｆＢ、配列Ａの局所化関数をｇＡ、配列Ｂの
局所化関数をｇＢとしている。また、静的に得られた全
プロセッサのプログラム分割情報が、ＤＡＴＡ文によっ
てすべてプログラム内に置かれている。

【０１３８】なお、このＤＡＴＡ文の内容をファイルと
してとっておき、そこから必要な所を読み込むようにし
てもよい。また、共有メモリをもつ場合には、共有メモ
リ上にＤＡＴＡ文の内容をとっておき、各プロセッサが
自分に必要な所を読み込むようにしてもよい。そのよう
にすることにより、各プロセッサが、すべてのプロセッ
サの情報をもつ必要がなくなる。

【０１３９】次に、動的リストベクトル計算処理生成を
行う場合について説明する。図２２は、図７の逐次ソー
スプログラム７０１を動的プログラム分割処理した後の
プログラムを示す。図１１のフローチャートおよび分割
処理後の図２２のプログラムを参照して、動的リストベ
クトル計算処理生成について具体的に説明する。

【０１４０】まず、処理１１０１で、ＰＲＧ分割式テー
ブル３０８の処理番号１３０３を２に設定する。次に、
処理１１０２で、図７の逐次プログラム７０１のループ
７００内の各代入文７０４，７０５に対するＧＩＴＳの
配列を宣言する。その宣言文が、図２２の宣言部２２０
１の配列ＧＩＴＳＡ（４），ＧＩＴＳＢ（４）である。
実行文の最初に、自分のプロセッサ番号を得る文２００
１を生成する処理は、上述の静的プログラム分割処理と
同様に、図１のノードプログラム生成１１３で行う。

【０１４１】処理１１０３で、まず代入文７０４に対す
るＧＩＴＳＡを求めるために、ＰＲＧ分割式テーブル３
０８（図１８）のＧＩＴＳ１８０１に基づいて、ループ
２２０２を生成する。そして、そのループ２２０２のル
ープインデックスＩを配列ＧＩＴＳＡに順に格納する。
これにより、代入文７０４に対するＧＩＴＳを配列ＧＩ
ＴＳＡに格納する文が、生成されたことになる。

【０１４２】同様にして、代入文７０６に対するＧＩＴ
ＳＢを求めるために、ＰＲＧ分割式テーブル３０８（図
１８）のＧＩＴＳ１８０２に基づいてループ２２０３を
生成し、ループインデックスＩを配列ＧＩＴＳＢに順に
格納する。これにより、代入文７０６に対するＧＩＴＳ
を配列ＧＩＴＳＢに格納する文が、生成されたことにな
る。

【０１４３】次に、処理１１０５により文２２０４を生
成する。文２２０４は、配列ＧＩＴＳＡとＧＩＴＳＢの
和集合をとって、重複を除いた要素数ｎを返し、これら
をマージしてリストベクトルＬに格納するサブルーチン
をコールする文である。

【０１４４】さらに、処理１１０６により文２２０５を
生成する。文２２０５は、配列ＧＩＴＳＡ，ＧＩＴＳＢ
を前から順に参照するために用いる配列インデックス
Ｊ，Ｋを１に初期化する文である。

【０１４５】そして、処理１１０７により、上記の文２
２０２，２２０３，２２０４，２２０５をリストベクト
ル計算処理生成プログラムとして中間語１０３に追加す
る。

【０１４６】処理１００５，１００６は、各代入文にガ
ードをかけ、配列のインデックスを変更する処理であ
り、静的リストベクトル計算処理生成の場合と同様であ
る。

【０１４７】以上で、図７の逐次ソースプログラム７０
１を動的プログラム分割した後のプログラム（図２２）
が得られる。この後、プロセッサ間通信生成（図１の処
理１１１）とノードプログラム生成（図１の処理１１
３）を行い、プログラム分割式テーブル３０８（図１
８）を参照して、最終的な並列ノードプログラム１１４
（図２３）を得る。

【０１４８】従来方法では、同一ループ内に複数の代入
文がある場合、各代入文のＬＩＴＳの和集合をループ繰
り返しの範囲として採用していた。このため、ループ内
にある複数の代入文の左辺に現われる配列の分割方法が
異なる場合（例えば、図７で説明したような場合）に
は、各代入文ごとにＬＩＴＳに対応するＧＩＴＳが異な
るにもかかわらずＬＩＴＳを共有することになり、結果
不正になる可能性があった。

【０１４９】上記実施例によれば、プロセッサごとに各
代入文のＧＩＴＳの和集合をループ繰り返し範囲とする
ので結果不正にはならない。

【０１５０】また、従来方法では、代入文の左辺に現わ
れる配列の添字式が異なる場合、各プロセッサで無駄な
ループ繰り返しを行う可能性があった。すなわち、従来
法では各代入文のＬＩＴＳが互いに排反でＬＩＴＳが非
連続になる場合、ＬＩＴＳが等比数列で表現できる（連
続）範囲に拡大すると、どの代入文も実行しないような
無駄なループ繰り返しがあった。

【０１５１】例えば、図６の逐次プログラム６０１で
は、配列Ａのデータ分割パターンが６０２のとき、並列
ノードプログラムは１１４に示すようになる。ここで、
元のプログラム６０１のループ内の各代入文６０４，６
０５のＬＩＴＳはそれぞれ［１：４］と［１３：１６］
なので、和集合が連続する範囲をとると［１：１６］に
なる。従来方法では、プログラム１１４に示すように、
この［１：１６］の範囲をＬＩＴＳとしていた。従っ
て、無駄なループ繰り返し（Ｉ＝５〜１２のとき）を行
うこととなる。

【０１５２】これに対し、図６の逐次プログラム６０１
に本実施例の方法（静的プログラム分割処理）を適用す
ると、図２４の並列ノードプログラム１１４になる。図
２４のプログラム１１４では、あらかじめリストベクト
ルＬｐに格納してあるＧＩＴＳによりループ内の代入文
の配列の添字を構成している。そして、ループは、この
リストベクトルの要素長の範囲をまわるようにしてあ
る。従って、代入文を実行するループ繰り返し回数は８
回であり、無駄なループ繰り返しはなくなり、性能が向
上する。

【０１５３】上記実施例によれば、各代入文のＧＩＴＳ
の和集合をリストベクトルとして静的にあるいは動的に
生成し、そのリストベクトルを参照することにより、各
プロセッサでのループ繰り返しに無駄なループ繰り返し
を含まないので性能が向上する。

【０１５４】

【発明の効果】以上説明したように、本発明によれば、
逐次ソースプログラムを並列計算機向きに変換する際に
用いるプログラム分割方法において、代入文左辺に現わ
れる配列の分割方法が異なることによる結果不正を起こ
さないようにできる。また、代入文左辺に現われる配列
の添字式が異なるためにループ繰り返し範囲が拡大され
て無駄なループ繰り返しを実行するようなことがなく、
必要不可欠なループ繰り返しだけを実行して性能向上を
図ることができる。

【０１５５】なお、上記実施例では、ＤＯループを例と
して説明しているが、当然に、他のループに適用するこ
ともできる。

【図面の簡単な説明】

【図１】本発明に係るプログラム分割方法を適用した自
動並列化変換システムにおける処理手順の概要図

【図２】添字関数とその逆関数についての説明図

【図３】ＬＩＴＳを求める処理図

【図４】ＬＩＴＳを求める例

【図５】ループ分割可能な例

【図６】異なるＧＩＴＳの例

【図７】配列データ分割パターンが異なる例

【図８】静的プログラム分割処理の手順を表すフローチ
ャート図

【図９】動的プログラム分割処理の手順を表すフローチ
ャート図

【図１０】静的リストベクトル計算処理生成の手順を表
すフローチャート図

【図１１】動的リストベクトル計算処理生成の手順を表
すフローチャート図

【図１２】データ分割テーブルの構成図

【図１３】ＰＲＧ分割式テーブルの構成図

【図１４】ＰＲＧ分割値テーブルの構成図

【図１５】ＧＩＸＳ，ＬＩＸＳ，ＧＩＴＳ，ＬＩＴＳテ
ーブルの構成図

【図１６】図７の例題プログラムにおける配列Ａのデー
タ分割テーブルを示す図

【図１７】図７の例題プログラムにおける配列Ｂのデー
タ分割テーブルを示す図

【図１８】図７の例題プログラムのＰＲＧ分割式テーブ
ルを示す図

【図１９】図７の例題プログラムのＰＲＧ分割値テーブ
ルを示す図

【図２０】図７の例題プログラムの静的プログラム分割
処理後のプログラムを示す図

【図２１】図７の例題プログラムの静的プログラム分割
処理による並列ノードプログラムを示す図

【図２２】図７の例題プログラムの動的プログラム分割
処理後のプログラムを示す図

【図２３】図７の例題プログラムの動的プログラム分割
処理による並列ノードプログラムを示す図

【図２４】図６の例題プログラムの静的プログラム分割
処理による並列ノードプログラムを示す図

【符号の説明】

１００…自動並列化処理、１０１…データ分割指示付き
ソースプログラム、１０２…構文解析処理、１０３…中
間語、１０４…辞書、１０５…データ分割情報、１０６
…プログラム分割処理、１０７…プログラム分割処理方
法判定部、１０８…単一文におけるプログラム分割処
理、１０９…リストベクトルによるプログラム分割処
理、１１０…プログラム分割情報、１１１…プロセッサ
間通信生成処理、１１２…非局所データ解析情報、１１
３…ノードプログラム生成処理、１１４…ノードプログ
ラム、３０２…データ分割テーブル、３０８…ＰＲＧ
（プログラム）分割式テーブル、８０８…ＰＲＧ（プロ
グラム）分割値テーブル。

Claims (6)

【特許請求の範囲】
1. 【請求項１】逐次ソースプログラムを入力して、分散記
   憶型並列計算機向きの並列化ソースプログラムまたはオ
   ブジェクトプログラムを生成する言語変換システムにお
   いて、該逐次ソースプログラム中のループに対し、各プ
   ロセッサが分担して計算するループ繰り返し範囲を求め
   るプログラム分割方法であって、 上記逐次ソースプログラム中で宣言されているデータの
   各プロセッサへの割り付け方を示すデータ分割指示情報
   を入力するステップと、 各プロセッサごとに、ループ内の各代入文の代入先のデ
   ータが該プロセッサに割り付けられているときのループ
   インデックスの和集合をリストベクトルとして保持する
   ステップと、 該プロセッサでのループ実行回数をそのリストベクトル
   の要素数とするとともに、ループ内の代入文に現れるル
   ープインデックスを上記リストベクトルの参照に置き換
   えるステップとを備えたことを特徴とするプログラム分
   割方法。
2. 【請求項２】請求項１に記載のプログラム分割方法にお
   いて、前記リストベクトルを言語変換時に決定すること
   を特徴とするプログラム分割方法。
3. 【請求項３】請求項１に記載のプログラム分割方法にお
   いて、前記リストベクトルを実行時に計算する処理を、
   変換結果の並列化プログラムに含めることを特徴とする
   プログラム分割方法。
4. 【請求項４】逐次ソースプログラムを入力して、分散記
   憶型並列計算機向きの並列化ソースプログラムまたはオ
   ブジェクトプログラムを生成する言語変換システムにお
   いて、該逐次ソースプログラム中のループに対し、各プ
   ロセッサが分担して計算するループ繰り返し範囲を求め
   るプログラム分割方法であって、 上記逐次ソースプログラム中の配列の各プロセッサへの
   割り付け方を示すデータ分割指示情報を入力するステッ
   プと、 該データ分割指示情報に基づいて、ループ内の各代入文
   ごとに、その代入文に対して元のループ反復範囲のうち
   各プロセッサで分担実行すべきループ反復範囲を示すル
   ープインデックスの集合であるグローバル・イテレーシ
   ョン・セットを求めるステップと、 各プロセッサごとに、ループ内のすべての代入文に対応
   する上記グローバル・イテレーション・セットの和集合
   を求め、該和集合の要素をソートしてリストベクトルと
   して保持するステップと、 各プロセッサでのループ反復回数を上記リストベクトル
   の要素数とするとともに、ループ内の代入文の配列の添
   字式中のループインデックスを上記リストベクトルの参
   照に置き換えるステップとを備えたことを特徴とするプ
   ログラム分割方法。
5. 【請求項５】逐次ソースプログラムを入力して、分散記
   憶型並列計算機向きの並列化ソースプログラムまたはオ
   ブジェクトプログラムを生成する言語変換システムにお
   いて、該逐次ソースプログラム中のループに対し、各プ
   ロセッサが分担して計算するループ繰り返し範囲を求め
   るプログラム分割方法であって、 上記逐次ソースプログラム中の配列の各プロセッサへの
   割り付け方を示すデータ分割指示情報を入力するステッ
   プと、 該データ分割指示情報に基づいて、ループ内の各代入文
   ごとに、その代入文に対して元のループ反復範囲のうち
   各プロセッサで分担実行すべきループ反復範囲を示す下
   限式、上限式、および増分式を求めるステップと、 上記下限式、上限式、および増分式を用いて、各代入文
   に対応するループ反復範囲を示すループインデックス値
   の集合を算出する文を生成するステップと、 各プロセッサごとに、ループ内のすべての代入文に対応
   する上記ループインデックス値の集合の和集合を求め、
   該和集合の要素をソートしてリストベクトルとして設定
   する文を生成するステップと、 各プロセッサでのループ反復回数を上記リストベクトル
   の要素数とするとともに、ループ内の代入文の配列の添
   字式中のループインデックスを上記リストベクトルの参
   照に置き換えるステップとを備えたことを特徴とするプ
   ログラム分割方法。
6. 【請求項６】請求項４または５に記載のプログラム分割
   方法において、さらに、任意のループインデックスに対
   して、前記リストベクトルの該ループインデックス番目
   の要素が前記ループ内の代入文のグローバル・イテレー
   ション・セットに含まれるときのみその代入文を実行す
   るように変更することを特徴とするプログラム分割方
   法。