(57)【特許請求の範囲】
【請求項１】
入力されたプログラムを、複数のプロセッシングエレメントと通信ネットワークから成る並列計算機のためのプログラムに変換するプログラム変換装置であって、
前記入力されたプログラムの中に含まれるループの処理が前記複数のプロセッシングエレメントにより並列化可能かどうかを調べ、並列化可能であれば、オーバーラップエリアを設けることにより各プロセッシングエレメントが該ループの処理をローカルに実行できるかどうかを調べることにより、並列化可能でかつ各プロセッシングエレメントがローカルに実行できるループを含むループ部分を検出する検出手段と、
前記ループ部分の配列データを前記複数のプロセッシングエレメントに分散させて前記ループの処理を並列化し、各プロセッシングエレメントにオーバーラップエリアを割り当て、各プロセッシングエレメントが担当する配列要素の範囲をオーバーラップエリア分だけ広げることにより、各プロセッシングエレメントが自プロセッシングエレメント内の配列要素を用いて、割り当てられたオーバーラップエリア内の配列要素をローカルに計算して更新するコードを含むプログラムを生成する設定手段と
を備えることを特徴とするプログラム変換装置。
【請求項２】
前記検出手段は、前記並列化可能でかつ各プロセッシングエレメントがローカルに実行できるループが逐次ループに囲まれている部分を、前記ループ部分として検出することを特徴とする請求項１記載のプログラム変換装置。
【請求項３】
各プロセッシングエレメントが前記逐次ループを繰り返す毎に他のプロセッシングエレメントとの通信によりオーバーラップエリア内の配列要素を更新する必要があるような従来型のオーバーラップエリアのサイズと拡張パラメータの積を、各プロセッシングエレメントに割り当てるオーバーラップエリアのサイズと決定するサイズ決定手段をさらに備え、
前記設定手段は、前記サイズ決定手段が決めたサイズのオーバーラップエリアを各プロセッシングエレメントに割り当て、前記オーバーラップエリア内の配列要素をローカルに計算して更新するコードと、各プロセッシングエレメントが前記逐次ループを拡張パラメータ回繰り返す毎に他のプロセッシングエレメントとの通信を行って該オーバーラップエリア内の配列要素を更新するコードとを含むプログラムを生成することを特徴とする請求項２記載のプログラム変換装置。
【請求項４】
入力されたプログラムを、複数のプロセッシングエレメントと通信ネットワークから成る並列計算機のためのプログラムに変換するプログラム変換装置であって、
前記入力されたプログラムの中に含まれるループの処理が前記複数のプロセッシングエレメントにより並列化可能かどうかを調べ、並列化可能であれば、オーバーラップエリアを設けることにより各プロセッシングエレメントが該ループの処理をローカルに実行できるかどうかを調べることにより、並列化可能でかつ各プロセッシングエレメントがローカルに実行できるループが逐次ループに囲まれているループ部分を検出する検出手段と、
前記ループ部分の配列データを前記複数のプロセッシングエレメントに分散させて前記ループの処理を並列化したとき、２つのプロセッシングエレメント間で双方向の通信が発生する場合、該配列データの添字を前記逐次ループの繰り返しパラメータに依存する添字に変更することにより、各プロセッシングエレメント内における各配列要素の格納位置を、該逐次ループの繰り返し毎にプロセッシングエレメント間にまたがる方向にシフトさせて、プロセッシングエレメント間の通信を双方向から単一方向に変更する通信変更手段と、
前記配列データを前記複数のプロセッシングエレメントに分散させて前記ループの処理を並列化し、各プロセッシングエレメントにオーバーラップエリアを割り当て、前記通信変更手段により変更された添字を用いて、プロセッシングエレメント間における単一方向のデータ転送により該オーバーラップエリア内の配列要素を更新するコードを含むプログラムを生成する設定手段と
を備えることを特徴とするプログラム変換装置。
【請求項５】
前記通信変更手段は、前記配列データの添字と前記逐次ループの繰り返しパラメータの和を表すパラメータを用いて、前記繰り返しパラメータに依存する添字を生成することを特徴とする請求項４記載のプログラム変換装置。
【請求項６】
前記設定手段は、前記ループ部分の処理の終了後にシフトされた格納位置を元の位置に戻すようなコードを生成することを特徴とする請求項４または５記載のプログラム変換装置。
【請求項７】
入力されたプログラムを、複数のプロセッシングエレメントと通信ネットワークから成る並列計算機のためのプログラムに変換するプログラム変換装置であって、
前記入力されたプログラムの中に含まれるループの処理が前記複数のプロセッシングエレメントにより並列化可能かどうかを調べ、並列化可能であれば、オーバーラップエリアを設けることにより各プロセッシングエレメントが該ループの処理をローカルに実行できるかどうかを調べることにより、並列化可能でかつ各プロセッシングエレメントがローカルに実行できるループが逐次ループに囲まれているループ部分を検出する検出手段と、
前記ループ部分の配列データを前記複数のプロセッシングエレメントに分散させて前記ループの処理を並列化したとき、２つのプロセッシングエレメント間で双方向の通信が発生する場合、該配列データの添字を前記逐次ループの繰り返しパラメータに依存する添字に変更することにより、各プロセッシングエレメント内における各配列要素の格納位置を、該逐次ループの繰り返し毎にプロセッシングエレメント間にまたがる方向にシフトさせて、プロセッシングエレメント間の通信を双方向から単一方向に変更する通信変更手段と、
前記配列データを前記複数のプロセッシングエレメントに分散させて前記ループの処理を並列化し、各プロセッシングエレメントにオーバーラップエリアを割り当て、各プロセッシングエレメントが担当する配列要素の範囲をオーバーラップエリア分だけ広げ、前記通信変更手段により変更された添字を用いることにより、各プロセッシングエレメントが自プロセッシングエレメント内の配列要素を用いて、割り当てられたオーバーラップエリア内の配列要素をローカルに計算して更新するコードと、プロセッシングエレメント間における単一方向のデータ転送により該オーバーラップエリア内の配列要素を更新するコードとを含むプログラムを生成する設定手段と
を備えることを特徴とするプログラム変換装置。
【請求項８】
各プロセッシングエレメントが他のプロセッシングエレメントとの通信により前記オーバーラップエリア内の配列要素を更新した後、通信なしでｅ回続けて前記逐次ループのデータ更新を実行する実行モデルに基づき、該オーバーラップエリア内の単位領域あたりの計算時間と、プロセッシングエレメント間の１回のデータ転送の起動と終了に必要なオーバーヘッド時間と、該単位領域あたりのデータ転送時間とを用いて、該逐次ループ１回あたりの実行時間をｅの関数として表し、該実行時間が最小となるようなｅの値ｅ０を求め、得られたｅ０から該オーバーラップエリアのサイズを決定するサイズ決定手段をさらに備え、
前記設定手段は、前記サイズ決定手段が決めたサイズのオーバーラップエリアを各プロセッシングエレメントに割り当てることを特徴とする請求項２、４、または７記載のプログラム変換装置。
【請求項９】
複数のプロセッシングエレメントと通信ネットワークから成り、配列データを該複数のプロセッシングエレメントに分散させて逐次ループの並列処理を行う並列計算機であって、
各プロセッシングエレメントが、
前記配列データのうち自プロセッシングエレメントが担当する配列要素を格納するローカルエリアと、他のプロセッシングエレメントが担当し該他のプロセッシングエレメントから転送される配列要素を格納するオーバーラップエリアとを割り当てられ、該自プロセッシングエレメントが担当する配列要素の範囲をオーバーラップエリア分だけ広げたデータ格納手段と、
前記逐次ループの繰り返しにおいて、他のプロセッシングエレメントとの通信により前記オーバーラップエリア内の配列要素が更新された後、前記データ格納手段に格納された配列要素を用いて、前記ローカルエリアとオーバーラップエリア内の配列要素をローカルに計算して更新する処理手段と
を備えることを特徴とする並列計算機。
【請求項１０】
複数のプロセッシングエレメントと通信ネットワークから成り、配列データを該複数のプロセッシングエレメントに分散させて逐次ループの並列処理を行う並列計算機であって、
各プロセッシングエレメントが、
前記配列データのうち自プロセッシングエレメントが担当する配列要素を格納するローカルエリアと、他のプロセッシングエレメントが担当し該他のプロセッシングエレメントから転送される配列要素を格納するオーバーラップエリアとを割り当てられたデータ格納手段と、
前記データ格納手段内における各配列要素の格納位置を、前記逐次ループの繰り返し毎にプロセッシングエレメント間にまたがる方向にシフトさせることにより、前記自プロセッシングエレメントと前記他のプロセッシングエレメントの間の通信を双方向から単一方向に変更し、単一方向のデータ転送により該他のプロセッシングエレメントから転送された配列要素を用いて前記オーバーラップエリア内の配列要素を更新する処理手段と
を備えることを特徴とする並列計算機。
【請求項１１】
前記オーバーラップエリアのサイズは、各プロセッシングエレメントが他のプロセッシングエレメントとの通信により該オーバーラップエリア内の配列要素を更新した後、通信なしでｅ回続けて前記逐次ループのデータ更新を実行する実行モデルに基づき、該オーバーラップエリア内の単位領域あたりの計算時間と、プロセッシングエレメント間の１回のデータ転送の起動と終了に必要なオーバーヘッド時間と、該単位領域あたりのデータ転送時間とを用いて、該逐次ループ１回あたりの実行時間をｅの関数として表し、該実行時間が最小となるようなｅの値ｅ０を求めることにより、得られたｅ０から決定されることを特徴とする請求項９または１０記載の並列計算機。
【請求項１２】
複数のプロセッシングエレメントと通信ネットワークから成り、配列データを該複数のプロセッシングエレメントに分散させて逐次ループの並列処理を行う並列計算機におけるデータ更新方法であって、
各プロセッシングエレメントが、
前記配列データのうち自プロセッシングエレメントが担当する配列要素をメモリ内のローカルエリアに格納し、
他のプロセッシングエレメントが担当し該他のプロセッシングエレメントから転送される配列要素を、前記自プロセッシングエレメントが担当する配列要素の範囲をオーバーラップエリア分だけ広げた前記メモリ内のオーバーラップエリアに格納し、
前記逐次ループの繰り返しにおいて、他のプロセッシングエレメントとの通信により前記オーバーラップエリア内の配列要素が更新された後、前記メモリに格納された配列要素を用いて、前記ローカルエリアとオーバーラップエリア内の配列要素をローカルに計算して更新する
ことを特徴とするデータ更新方法。
【請求項１３】
複数のプロセッシングエレメントと通信ネットワークから成り、配列データを該複数のプロセッシングエレメントに分散させて逐次ループの並列処理を行う並列計算機におけるデータ更新方法であって、
各プロセッシングエレメントが、
前記配列データのうち自プロセッシングエレメントが担当する配列要素をメモリ内のローカルエリアに格納し、
他のプロセッシングエレメントが担当し該他のプロセッシングエレメントから転送される配列要素を前記メモリ内のオーバーラップエリアに格納し、
前記メモリ内における各配列要素の格納位置を、前記逐次ループの繰り返し毎にプロセッシングエレメント間にまたがる方向にシフトさせることにより、前記自プロセッシングエレメントと前記他のプロセッシングエレメントの間の通信を双方向から単一方向に変更し、単一方向のデータ転送により該他のプロセッシングエレメントから転送された配列要素を用いて前記オーバーラップエリア内の配列要素を更新する
ことを特徴とするデータ更新方法。
【請求項１４】
前記オーバーラップエリアのサイズは、各プロセッシングエレメントが他のプロセッシングエレメントとの通信により該オーバーラップエリア内の配列要素を更新した後、通信なしでｅ回続けて前記逐次ループのデータ更新を実行する実行モデルに基づき、該オーバーラップエリア内の単位領域あたりの計算時間と、プロセッシングエレメント間の１回のデータ転送の起動と終了に必要なオーバーヘッド時間と、該単位領域あたりのデータ転送時間とを用いて、該逐次ループ１回あたりの実行時間をｅの関数として表し、該実行時間が最小となるようなｅの値ｅ０を求めることにより、得られたｅ０から決定されることを特徴とする請求項１２または１３記載のデータ更新方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、分散メモリ型並列計算機によるプログラムの高速実行方法に係り、オーバーラップエリアを用いたデータ更新方法と、データ更新用のプログラムの変換を行うプログラム変換装置に関する。
【０００２】
【従来の技術】
今日、スーパーコンピュータ等の高速計算機を実現する方式として、複数のプロセッシングエレメント（以下、ＰＥまたはプロセッサと記す）を集め、それらをネットワークで一体化した並列計算機が注目を浴びている。このような並列計算機を用いて高い処理性能を実現する上で、データ通信のオーバーヘッドを削減することは重要な課題である。プロセッサ間のデータ通信のオーバーヘッドを削減するためのテクニックの１つとして、ある種のアプリケーションに対してオーバーラップエリアを用いる方法が効果的であることが知られている。
【０００３】
データ通信に要する時間はデータの総量よりもパケット通信の回数に大きく依存するので、通信の一括化あるいはメッセージのベクトル化（Ｓ．  Ｈｉｒａｎａｎｄａｎｉ，  Ｋ．  Ｋｅｎｎｅｄｙ，  ａｎｄ  Ｃ．  Ｔｓｅｎｇ．  “Ｃｏｍｐｉｌｅｒ  ｏｐｔｉｍｉｚａｔｉｏｎｓ  ｆｏｒ  Ｆｏｒｔｒａｎ  Ｄ  ｏｎ  ＭＩＭＤ  Ｄｉｓｔｒｉｂｕｔｅｄ−Ｍｅｍｏｒｙ  Ｍａｃｈｉｎｅｓ，”  ｉｎ  Ｐｒｏｃ．  Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ  ’９１  ｐｐ．８６−１００，  Ｎｏｖ．  １９９１．  ）は、通信オーバーヘッドを削減する上での重要なテクニックである。オーバーラップエリアはベクトルデータを受信するバッファエリアの特殊なケースで、各プロセッサにおいてローカルデータエリア（ローカルエリア）を囲むように割り当てられ、プロセッサ内部の計算に使われる。ただし、オーバーラップエリアのデータ値の決定は隣接するプロセッサによって行われる。
【０００４】
図２０は、ＨＰＦ（Ｈｉｇｈ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｆｏｒｔｒａｎ）で書かれたヤコビ法（Ｊａｃｏｂｉ  ｒｅｌａｘａｔｉｏｎ  ）のプログラムコード（ヤコビコード）を示している。図２０のヤコビコードにおいて、２次元配列ａの要素ａ（ｉ，ｊ）の値は隣接する４つの要素ａ（ｉ，ｊ＋１）、ａ（ｉ，ｊ−１）、ａ（ｉ＋１，ｊ）、ａ（ｉ−１，ｊ）の値を用いて更新されることが記述されている。ただし、配列ａのサイズはａ（２５６，２５６）で与えられており、ｉ＝１，２５６、ｊ＝１，２５６に相当する要素は更新されない。また、データ更新のＤＯループにおけるａ（２：２５５）等はＦｏｒｔｒａｎ  ９０の配列記述であり、ＤＯループの繰り返し回数はｔ回である。このコードはオーバーラップエリアを用いるデータ更新の典型的な例を示している。
【０００５】
図２１は、図２０のヤコビコードを実行するためのオーバーラップエリアの一例を示している。図２０のプログラムで指定されているデータ分散によれば、配列ａ（２５６，２５６）の要素は１６台のプロセッサｐ（ｘ，ｙ）（ｘ＝１，２，３，４、ｙ＝１，２，３，４）のローカルエリアに分割されて格納される。例えば、プロセッサｐ（２，２）は、配列ａのうちのａ（６５：１２８，６５：１２８）の範囲を担当することになる。図２１において、プロセッサｐ（２，２）のローカルエリアの周りの斜線部分は、ｐ（２，２）におけるオーバーラップエリアを示している。
【０００６】
プロセッサｐ（２，２）は、ａ（ｉ，ｊ）を計算する際に隣接するａ（ｉ，ｊ＋１）、ａ（ｉ，ｊ−１）、ａ（ｉ＋１，ｊ）、ａ（ｉ−１，ｊ）をローカルにアクセスできるように、オーバーラップエリアを含めてａ（６４：１２９，６４：１２９）相当の領域を持つ。
【０００７】
もし、オーバーラップエリアが無ければ、ＤＯループの中で隣接プロセッサからのデータ読出しが必要になり、小さいデータ量のデータ通信が多数発生することから、大きな通信オーバーヘッドとなる。しかし、オーバーラップエリアを持つことで、更新実行の前に一括データ転送を用いて最新データをオーバーラップエリア上にコピーすることが可能になる。したがって、データ更新をローカルに行うことができ、通信オーバーヘッドを削減できる。
【０００８】
このような目的で使用されるオーバーラップエリアは、例えば分散メモリ型並列計算機用の言語であるＶＰＰ  Ｆｏｒｔｒａｎ（進藤達也、岩下英俊、土肥実久、荻原純一．“ＡＰ１０００を対象としたＶＰＰＦｏｒｔｒａｎ  処理系の実現と評価”ＳＷｏＰＰ鞆の浦  ’９３ＨＰＣ研究会，Ｖｏｌ．  ９３−ＨＰＣ−４８−２，  ｐｐ．  ９−１６，  Ａｕｇ．  １９９３．）によって陽に指定することができる。また、ある種のコンパイラは最適化の１つの形態としてオーバーラップエリアの自動生成を行っている。
【０００９】
また、並列実行に伴うデータ転送のパターンは２種類に分類できる。１つは単一方向のデータ転送（ＳＤＤＴ：ｓｉｎｇｌｅ  ｄｉｒｅｃｔｉｏｎ  ｄａｔａ  ｔｒａｎｓｆｅｒ）であり、もう１つは双方向のデータ転送（ＢＤＤＴ：ｂｉ−ｄｉｒｅｃｔｉｏｎａｌ  ｄａｔａ  ｔｒａｎｓｆｅｒ）である。図２２はＳＤＤＴの例を示しており、図２３はＢＤＤＴの例を示している。
【００１０】
図２２および図２３において、プロセッサ（Ｐｒｏｃｅｓｓｏｒ  ）ｉ−１、ｉ、ｉ＋１、ｉ＋２は特定の次元上に並び、１つのプロセッサアレイを構成している。ＳＤＤＴは、この特定の次元上で時間の経過とともに、すべての転送データがプロセッサｉからプロセッサｉ＋１に向けて単一方向に送られる転送である。また、ＢＤＤＴはデータの転送が隣接するプロセッサ間で双方向になる転送である。これにより、あるデータはプロセッサｉからプロセッサｉ＋１に、またあるデータはプロセッサｉ＋１からプロセッサｉに送られる。
【００１１】
図２４は、１次元配列に関するヤコビ法のプログラムコードを示している。図２４のヤコビコードにおいて、１次元配列ａの要素ａ（ｉ）の値は、隣接する２つの要素ａ（ｉ−１）とａ（ｉ＋１）の値を関数ｆに入力したときの関数ｆの出力により更新される。ただし、配列ａのサイズはａ（２８）で与えられており、ａ（１）とａ（２８）は更新されない。また、データ更新の繰り返し回数はｔｉｍｅにより与えられている。
【００１２】
図２５は、図２４のプログラムの実行の際に、従来のオーバーラップエリアを用いてデータ更新を行う例を示している。図２５において、ＰＥ０、ＰＥ１、ＰＥ２、ＰＥ３は配列ａを分割して担当する４台のＰＥを表し、各ＰＥはそれぞれ９個の配列要素を格納する領域を持つ。ダーティなオーバーラップエリア（ｄｉｒｔｙ  ｏｖｅｒｌａｐ  ａｒｅａ）は古いデータを持ったオーバーラップエリアを表し、クリーンなオーバーラップエリア（ｃｌｅａｎ  ｏｖｅｒｌａｐ  ａｒｅａ）は隣接するＰＥと同じ最新のデータを持ったオーバーラップエリアを表し、ローカルエリアは各ＰＥが処理を担当するデータの領域を表す。
【００１３】
また、ＩＮＩＴは初期状態を表し、Ｕｐｄａｔｅはオーバーラップエリアを更新するための隣接ＰＥ間のデータ通信を表す。Ｉｔｅｒ１、２、３、４は、ＤＯループの各繰り返し（ｉｔｅｒａｔｉｏｎ  ）時におけるデータ更新の並列処理を表す。図２５では、オーバーラップエリアは各繰り返し毎にＢＤＤＴにより更新されている。
【００１４】
【発明が解決しようとする課題】
しかしながら、従来のオーバーラップエリアを用いたデータ更新方法には次のような問題がある。
【００１５】
並列計算機を構成する各プロセッサは、オーバーラップエリアのデータ値を用いた計算を行う前に、オーバーラップエリアのデータを最新の値に更新しなければならない。この更新は、プロセッサ間の通信を用いて隣接プロセッサから最新の値を読み出すことにより行われる。並列計算機では、一般に１回あたりの通信に対して、その立ち上げ時間のオーバーヘッドが大きい。このため、通信処理に要する時間は、データの転送量以上にデータ転送の回数に影響を受ける。オーバーラップエリアを用いた計算を行う度にオーバーラップエリアを更新すると、毎回通信立ち上げのオーバーヘッドを伴うことになる。
【００１６】
また、ＡＰ１０００（Ｈ．  Ｉｓｈｉｈａｔａ，  Ｔ．  Ｈｏｒｉｅ，  Ｓ．  Ｉｎａｎｏ，  Ｔ．  Ｓｈｉｍｉｚｕ，  ａｎｄ  Ｓ．  Ｋａｔｏ．  “Ａｎ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｏｆ  Ｈｉｇｈｌｙ  Ｐａｒａｌｌｅｌ  Ｃｏｍｐｕｔｅｒ  ＡＰ１０００，”  ｉｎ  Ｐｒｏｃ．  ＩＥＥＥ  Ｐａｃｉｆｉｃ  Ｒｉｍ  Ｃｏｎｆ．  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，  Ｃｏｍｐｕｔｅｒｓ，  ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ，  ｐｐ．  １３−１６，  Ｍａｙ  １９９１．  ）のようなトーラスネットワークで結合された並列計算機において、ＳＤＤＴはＢＤＤＴに比べてより優れた特性を持つ。なぜならば、ＳＤＤＴではデータ転送回数と隣接プロセッサ間での同期処理に伴うオーバーヘッドが削減されるからである。しかしながら、図２５のような従来のデータ更新処理では、隣接プロセッサ間でお互いにオーバーラップエリアのデータをやりとりしなければならず、データ転送パターンはＢＤＤＴとなる。ＢＤＤＴの場合、各プロセッサは両側の隣接プロセッサと同期を伴った通信を行って、処理を進めなければならない。このため、ＳＤＤＴよりデータ転送回数が多くなり、また同期処理に伴うオーバーヘッドも大きくなる。
【００１７】
本発明は、分散メモリ型並列計算機において、ＰＥ間の通信に伴うオーバーヘッドを削減するようなデータ更新方法と、そのようなデータ更新用のプログラムを生成するプログラム変換装置を提供することを目的とする。
【００１８】
【課題を解決するための手段】
図１は、本発明のプログラム変換装置の原理図である。図１のプログラム変換装置は、入力されたプログラムを、複数のＰＥと通信ネットワークから成る並列計算機のためのプログラムに変換する情報処理装置におけるプログラム変換装置であって、検出手段１、設定手段２、サイズ決定手段３、および通信変更手段４を備える。
【００１９】
検出手段１は、入力されたプログラムの中で、オーバーラップエリアを用いた最適化が可能なループを含むループ部分を検出する。
設定手段２は、そのループ部分の処理を行うＰＥにオーバーラップエリアを割り当て、そのオーバーラップエリア内のデータを計算するコードを生成して、変換後のプログラムを出力する。
【００２０】
サイズ決定手段３は、上記ループ部分の処理の実行時間を見積もって、上記オーバーラップエリアの最適なサイズを決定し、設定手段２は、サイズ決定手段３が決めたサイズのオーバーラップエリアを上記ループ部分の処理を行うＰＥに割り当てる。
【００２１】
通信変更手段４は、上記ループ部分の処理のデータ依存性を双方向から単一方向に変更して、単一方向のデータ転送（ＳＤＤＴ）を可能にする配列の添字を生成する。そして、設定手段２は、通信変更手段４が生成する配列の添字を用いて、単一方向のデータ転送によりデータを更新するコードを生成して、変換後のプログラムに付加する。
【００２２】
本発明の別のプログラム変換装置は、検出手段１および設定手段２を備え、入力されたプログラムを、複数のプロセッシングエレメントと通信ネットワークから成る並列計算機のためのプログラムに変換する。検出手段１は、入力されたプログラムの中に含まれるループの処理が上記複数のプロセッシングエレメントにより並列化可能かどうかを調べ、並列化可能であれば、オーバーラップエリアを設けることにより各プロセッシングエレメントがそのループの処理をローカルに実行できるかどうかを調べることにより、並列化可能でかつ各プロセッシングエレメントがローカルに実行できるループを含むループ部分を検出する。設定手段２は、ループ部分の配列データを上記複数のプロセッシングエレメントに分散させてループの処理を並列化し、各プロセッシングエレメントにオーバーラップエリアを割り当て、各プロセッシングエレメントが担当する配列要素の範囲をオーバーラップエリア分だけ広げることにより、各プロセッシングエレメントが自プロセッシングエレメント内の配列要素を用いて、割り当てられたオーバーラップエリア内の配列要素をローカルに計算して更新するコードを含むプログラムを生成する。
本発明のさらに別のプログラム変換装置は、検出手段１、設定手段２、および通信変更手段４を備え、入力されたプログラムを、複数のプロセッシングエレメントと通信ネットワークから成る並列計算機のためのプログラムに変換する。検出手段１は、入力されたプログラムの中に含まれるループの処理が上記複数のプロセッシングエレメントにより並列化可能かどうかを調べ、並列化可能であれば、オーバーラップエリアを設けることにより各プロセッシングエレメントがそのループの処理をローカルに実行できるかどうかを調べることにより、並列化可能でかつ各プロセッシングエレメントがローカルに実行できるループが逐次ループに囲まれているループ部分を検出する。通信変更手段４は、ループ部分の配列データを上記複数のプロセッシングエレメントに分散させてループの処理を並列化したとき、２つのプロセッシングエレメント間で双方向の通信が発生する場合、その配列データの添字を逐次ループの繰り返しパラメータに依存する添字に変更することにより、各プロセッシングエレメント内における各配列要素の格納位置を、逐次ループの繰り返し毎にプロセッシングエレメント間にまたがる方向にシフトさせて、プロセッシングエレメント間の通信を双方向から単一方向に変更する。設定手段２は、上記配列データを上記複数のプロセッシングエレメントに分散させてループの処理を並列化し、各プロセッシングエレメントにオーバーラップエリアを割り当て、通信変更手段４により変更された添字を用いて、プロセッシングエレメント間における単一方向のデータ転送によりオーバーラップエリア内の配列要素を更新するコードを含むプログラムを生成する。
図１の検出手段１、設定手段２、サイズ決定手段３、および通信変更手段４は、実施例の図２および３におけるホスト計算機１１に対応する。より詳しくは、これらの各手段の機能は図３に示されたコンパイラ２５の持つ各機能に相当し、コンパイラ２５はＣＰＵ（中央処理装置）２２により起動される。
【００２３】
【作用】
検出手段１は、入力されたプログラムをスキャンして、オーバーラップエリアを適用可能なループ部分を検出する。例えば、図２０、２４に示されるように、複数のＰＥによる並列処理が可能な計算処理が逐次ＤＯループに囲まれている部分が検出される。
【００２４】
設定手段２は、検出されたループ部分の処理を分担する各ＰＥにオーバーラップエリアを割り当て、そのオーバーラップエリア内のデータを計算により更新するコードを生成する。これにより、変換後のプログラムの実行時には、各ＰＥがローカルエリア内のデータだけでなく、オーバーラップエリア内のデータもローカルに計算して更新する。したがって、オーバーラップエリアのデータを更新するための通信回数が少なくなり、通信のオーバーヘッドが削減される。
【００２５】
サイズ決定手段３は、上記ループ部分の処理の実行時間を見積もり、例えば実行時間が最小になるように上記オーバーラップエリアのサイズを決定する。この最適なサイズのオーバーラップエリアを各ＰＥに割り当てれば、並列計算機の処理効率が向上する。
【００２６】
また、設定手段２は、ＢＤＤＴではなくＳＤＤＴによりデータを更新するコードを生成する。これにより、変換後のプログラムの実行時に、各ＰＥは配列の添字の上限と下限の両側の隣接ＰＥと通信を行う必要がなくなり、どちらか一方のＰＥと通信を行えばよい。したがって、通信を要しない側のＰＥとの同期処理が不要になり、同期に伴うオーバーヘッドが削減される。
【００２７】
通信変更手段４は、上記ループ部分の処理の配列データのデータ依存ベクトルを調べ、それが双方向の場合には単一方向に変更するような変換を施して、ＳＤＤＴを可能にする配列の添字を生成する。設定手段２は、変換後の配列の添字を用いてデータ更新のためのコードを生成する。
【００２８】
このように、図１のプログラム変換装置を用いて並列計算機用のプログラムを生成すれば、通信に伴うオーバーヘッドが少なくなる。
【００２９】
【実施例】
以下、図面を参照しながら、本発明の実施例について詳細に説明する。
図２は、本発明を実施する並列計算機の構成図である。図２の並列計算機はホスト計算機１１、ネットワーク１２、および複数のＰＥ（ＰＥ０、ＰＥ１、・・・、ＰＥｎ）から成るプロセッサアレイ１３を備える。ホスト計算機１１は並列計算機全体の制御や入出力処理を行い、プロセッサアレイ１３は並列処理を実行する。そして、ホスト計算機１１と各ＰＥは互いにネットワーク１２で結合されている。
【００３０】
図３は、ホスト計算機１１の構成図である。図３のホスト計算機１１は、入出力部２１、ＣＰＵ２２、およびメモリ２３が内部バス２４で結合された構成を持つ。ホスト計算機１１内では、ＣＰＵ２２がメモリ２５に格納されたコンパイラ２５を用いて、単一のプログラム２６を各ＰＥが並列実行するプログラムに変換（コンパイル）する。コンパイルされたプログラムコードは各ＰＥに入出力部２１を介してダウンロードされた後、各ＰＥにより実行される。プログラムコードのダウンロードや実行時におけるプロセッサ間のデータ転送には、ネットワーク１２が用いられる。
【００３１】
本発明の実施例では、大きく分けて２つの手法を用いる。１つは拡張オーバーラップエリアを用いる方法であり、もう１つはオーバーラップエリアのＳＤＤＴによる更新を可能にする方法である。
【００３２】
まず、図４から図９までを参照しながら、拡張オーバーラップエリアについて説明する。
拡張オーバーラップエリアとは、通常のオーバーラップエリアを複数倍したデータ格納領域である。これを用いることで、プログラム中の並列に実行されるループのうち、オーバーラップエリアが有効な処理が複数回実行されるループの場合に、オーバーラップエリアの更新のための通信の総数を減らすことができる。図２０のヤコビ法のプログラムを例にとって考えると、図２０に示すオーバーラップエリアの幅をｅ倍に拡張すれば、１回のデータ転送の後ｅ回のデータ更新を続けて行うことができる。
【００３３】
図４は、拡張オーバーラップエリアを用いて、図２４のヤコビコードを実行した場合のデータ更新を示している。図４においては、図２５に示すＰＥ０、ＰＥ１、ＰＥ２、ＰＥ３の従来型のオーバーラップエリアが３倍に拡張されており、これらのＰＥは拡張オーバーラップエリアを用いて並列処理を行う。ダーティなオーバーラップエリア、クリーンなオーバーラップエリア、ローカルエリア、ＩＮＩＴ、Ｕｐｄａｔｅ、およびＩｔｅｒ１、２、３、４の意味については、図２５と同様である。図４の拡張オーバーラップエリアでは、その一部のデータをローカルに計算することにより、データ更新を３回繰り返す毎に１回のデータ転送を行うだけで済む。
【００３４】
例えば、ＰＥ１は配列ａのうちａ（９：１６）の範囲の要素の更新を担当し、これらの要素をローカルエリアに保持するとともに、ａ（６：８）およびａ（１７：１９）の範囲の要素の格納領域を拡張オーバラップエリアとして持っている（ＩＮＩＴ）。ＰＥ１は、まずＰＥ０およびＰＥ２との間で通信を行って、拡張オーバラップエリアのデータを最新のものに更新する（Ｕｐｄａｔｅ）。
【００３５】
次に、ａ（６：１９）の範囲のデータを用いて１回目の計算を行い、ローカルエリアのデータａ（９：１６）と拡張オーバラップエリアのデータａ（７：８）およびａ（１７：１８）を更新する（Ｉｔｅｒ１）。次に、ａ（７：１８）の範囲のデータを用いて２回目の計算を行い、ローカルエリアのデータａ（９：１６）と拡張オーバラップエリアのデータａ（８）およびａ（１７）を更新する（Ｉｔｅｒ２）。次に、ａ（８：１７）の範囲のデータを用いて２回目の計算を行い、ローカルエリアのデータａ（９：１６）のみを更新する（Ｉｔｅｒ３）。
【００３６】
ここで、拡張オーバラップエリアのデータがすべてダーティ、つまり使用不可となったので、ＰＥ１は改めて隣接ＰＥとの間で通信を行って拡張オーバラップエリアを更新し、Ｉｔｅｒ４以降のデータ更新処理を同様に繰り返す。
【００３７】
図４において、データ更新の前の各要素ａ（ｉ）と更新後の各要素ａ（ｉ）とはそれぞれ物理的に異なるメモリ領域に格納される。つまり、各ＰＥにおいては、ローカルエリア、拡張オーバラップエリアともに、実際には更新前のデータ用と更新後のデータ用の２種類が用意されていることになる。しかしながら、これらのメモリ領域の区別は、プログラム２６のコンパイル時に自動的に行われる。
【００３８】
従来型のオーバーラップエリアと本発明による拡張オーバーラップエリアとを比較すると、オーバーラップエリアの更新のために転送されるデータの総量は同一である。しかし、通信のオーバーヘッド時間は転送データの総量よりも転送の回数に大きく依存するため、拡張オーバーラップを用いた方が通信のオーバーヘッドは小さくなる。
【００３９】
ところが、各ＰＥは自分がオーナーとなっているローカルエリアだけでなく、次の繰り返しで参照される拡張オーバーラップエリアの一部に対しても計算を行わなければならないため、隣接するＰＥのデータ更新の計算と処理が重複することになる。したがって、拡張されたオーバーラップエリアのサイズが大きければ大きいほど、処理の並列性が損なわれる。極端な例として、全ＰＥ分のデータを１つのＰＥが持つように拡張オーバーラップエリアを設定すれば、通信は全く不要になるが並列性は得られない。そこで、拡張オーバーラップエリアの最適サイズを決定するには、通信のオーバーヘッドと処理の並列性とのトレードオフが必要になる。
【００４０】
図５は、拡張オーバーラップエリアを実現するためにホスト計算機１１が行う拡張オーバーラップエリア設定処理のフローチャートである。図５の拡張オーバーラップエリア設定処理はコンパイラ２５による最適化処理の一部として行われる。最適化処理の入力は逐次プログラムであるプログラム２６と処理の開始指示（ディレクティブ）であり、出力は各ＰＥで実行すべきプログラムとなる。最適化処理によりプログラム２６が各ＰＥのプログラムに変換された後、そのプログラムと必要なデータが各ＰＥにダウンロードされ、並列実行される。
【００４１】
図５において処理が開始されると、まずホスト計算機１１はプログラム２６中に含まれる拡張オーバーラップエリアの適用箇所を検出する（ステップＳ１）。つまり、オーバーラップエリアを用いた最適化が可能な並列ループが逐次ループに囲まれている部分を、拡張オーバーラップエリアが有効に作用する箇所として検出する。ここで、並列ループとは、例えば図２０のライン６、７に記述されている演算のように、複数のＰＥで分担して並列に処理可能なループ処理を意味する。また、逐次ループとは、例えば図２０のライン５、８に記述されているＤＯループのように、逐次的に繰り返し行うループ処理を意味する。
【００４２】
図６は、図５のステップＳ１の処理の一例を示すフローチャートである。図６において処理が開始されると、まずホスト計算機１１はプログラム２６中に含まれるＤＯループを１つ選び（ステップＳ１−１）、その処理が並列化可能かどうかを調べる（ステップＳ１−２）。図２０の場合は、並列ループの部分がここで選ばれるＤＯループに相当する。並列化可能であれば、次にオーバーラップエリアが有効なＤＯループかどうかを調べる（ステップＳ１−３）。オーバーラップエリアが有効なＤＯループとは、オーバーラップエリアを設けることにより各ＰＥがローカルに実行できるような処理を意味する。オーバーラップエリアが有効であれば、次にそのＤＯループ（並列ループ）が逐次ループによりタイト（ｔｉｇｈｔ  ）に囲まれているかどうかを調べる（ステップＳ１−４）。ＤＯループがタイトに囲まれていれば、選んだＤＯループを拡張オーバーラップエリアの適用箇所として、メモリ２３の適当な領域に登録する（ステップＳ１−５）。
【００４３】
次に、他のＤＯループがあるかどうかを調べ（ステップＳ１−６）、他のＤＯループがあればステップＳ１−１以降の処理を繰り返し、なければ処理を終了する。ステップＳ１−２、Ｓ１−３、およびＳ１−４において、判定結果がＮＯの場合はステップＳ１−６の処理を行う。
【００４４】
図６の拡張オーバーラップエリア適用箇所検出処理の結果、例えば図２０や２３に示すような並列ループが適用箇所として登録される。
図５において、ホスト計算機１１はステップＳ１の処理の後、拡張オーバーラップエリアを用いた実行モデルを作成し、プログラムの実行時間の見積もりを行う（ステップＳ２）。ここで、一般の２次元配列に対する拡張オーバーラップエリアを例にとって、実行時間の見積もりの方法について述べる。
【００４５】
図７は、２次元配列を格納するＰＥのローカルエリアとその周りに設けた拡張オーバーラップエリアを示している。図７において、ｌはローカルエリアのサイズ（各次元における配列要素の個数）を表し、ｗは従来型のオーバーラップエリアのサイズ（幅）を表す。また、ｅは従来型のオーバーラップエリアを何倍に拡張するかを表すパラメータであり、拡張オーバーラップエリアのサイズ（幅）はｅｗと表される。
【００４６】
ここで、ローカルエリアあるいは拡張オーバーラップエリア内の単位領域（１要素）あたりの計算時間をａ、１回のデータ転送の起動と終了に必要なオーバーヘッド時間（ｐｒｏｌｏｇｕｅ  ａｎｄ  ｅｐｉｌｏｇｕｒ  ｔｉｍｅ）  をｃ、単位領域あたりのデータ転送に必要な時間をｄとする。このとき、データ転送時間は、ｃ＋ｄ×転送する領域の大きさにより与えられる。
【００４７】
拡張オーバーラップエリアを用いた最適化では、ｅ回のデータ更新（ｅイテレーション）に対してその最初にまとめて通信を行う。通信の対象になるデータは図７の斜線で示された拡張オーバーラップエリア部分である。この部分の面積（要素数）は、図７より４ｅｗ（ｅｗ＋ｌ）となる。また、通信はローカルエリアの左右上下と各頂点の方向（斜め方向）の配列要素を受け持つ８台のＰＥとの間で計８回行われる。したがって、ｅイテレーションに対して必要な全通信時間は、
８ｃ＋４ｄｅｗ（ｅｗ＋ｌ）                                  …（１）
となる。１イテレーションあたりの通信時間は（１）式をｅで割って求められ、
【００４８】
【数１】
0003626784.tif 000002
【００４９】
となる。
次に、データ更新のための計算に要する時間を見積もってみる。ローカルエリア内の計算要素数はｌ２  であるので、ローカルエリアの計算をｅイテレーション分行うのに必要な演算時間はａｅｌ２  となる。また、各イテレーションにおいて、拡張オーバーラップエリア内の更新される領域のサイズ（幅）をｋｗとすると、拡張オーバーラップエリア内の計算要素数は４ｋｗ（ｋｗ＋ｌ）となる。ここで、ｋは各イテレーションにおける拡張オーバーラップエリア内の更新部分が従来型のオーバーラップエリアの何倍に相当するかを表すパラメータである。通信を行わずにローカルにデータを更新する場合、拡張オーバーラップエリアは１イテレーション毎に外側から順にダーティになるので、拡張オーバーラップエリア内の更新部分の幅はｗずつ減少することになる。したがって、ｅイテレーションの間に拡張オーバーラップエリアの計算に費やされる計算時間は、
【００５０】
【数２】
0003626784.tif 000003
【００５１】
となる。
ｅ−ｋ回目のイテレーション時における拡張オーバーラップエリアの計算時間は４ａｋｗ（ｋｗ＋ｌ）で与えられるので、ｋが１からｅ−１までの場合の総和を求めたものが（３）式である。１イテレーションあたりの計算時間は、ｅイテレーションに対するローカルエリアの計算時間と拡張オーバーラップエリアの計算時間を加え、それをｅで割ることにより得られ、次のようになる。
【００５２】
【数３】
0003626784.tif 000004
【００５３】
（２）、（４）式より、拡張オーバーラップエリアを用いた場合の逐次ループ１回あたりの実行時間Ｔｉｔｅｒ（ｅ）はｅの関数として次のように表される。
【００５４】
【数４】
0003626784.tif 000005
【００５５】
実行時間の見積もりが終わると、ホスト計算機１１はその結果を用いて拡張オーバーラップエリアの最適なサイズを決定する（ステップＳ３）。拡張オーバーラップエリアの最適なサイズとは、実行時間が最小となるような拡張オーバーラップエリアのサイズを意味する。
【００５６】
例えば（５）式において、ｅ２  の項の係数をｓ、ｅの項の係数をｔ、１／ｅの項の係数をｕ、ｅについて０次の項をｖとおくと、（５）式は次のように書き換えられる。
【００５７】
Ｔｉｔｅｒ（ｅ）＝ｓｅ２  ＋ｔｅ＋ｕ／ｅ＋ｖ                        …（６）
図８は、（６）式のＴｉｔｅｒ（ｅ）とｅの関係を表したグラフである。図８に示されたＴｉｔｅｒ（ｅ）の最小値Ｔｉｔｅｒ（ｅ０  ）に対応するｅの値ｅ０  は、次式をｅについて解くことにより得られる。
【００５８】
【数５】
0003626784.tif 000006
【００５９】
こうして得られたｅ０  が、拡張オーバーラップエリアのサイズを最適にする拡張パラメータの値であり、そのときの拡張オーバーラップエリアのサイズはｅ０  ｗにより与えられる。
【００６０】
拡張オーバーラップエリアの最適なサイズが決まると、ホスト計算機１１はそのサイズの拡張オーバーラップエリアを各ＰＥに割り当てる（ステップＳ４）。図９は、図５のステップＳ４で行われる拡張オーバーラップエリア割当て処理の一例を示すフローチャートである。図９において処理が開始されると、ホスト計算機１１はまず各ＰＥのローカルエリアのデータサイズ（元のデータサイズ）に拡張オーバーラップエリアの最適サイズを加えて、新しいデータサイズとする（ステップＳ４−１）。拡張オーバーラップエリアの最適サイズは、ステップＳ３で求められた最適な拡張パラメータと従来型のオーバーラップエリアの幅の積で与えられる。図７の例では、最適サイズはｅ０  ｗである。次に、新しいデータサイズでデータ宣言をし直して（ステップＳ４−２）、処理を終了する。
【００６１】
これにより、各ＰＥの拡張オーバーラップエリアには、そのサイズ分だけの他のＰＥのローカルエリアのデータが割り当てられることになる。
ステップＳ４の処理が終了すると、ホスト計算機１１は拡張オーバーラップエリアの計算のためのプログラムコードを挿入する（ステップＳ５）。この処理により、並列ループのうち各ＰＥが担当する処理範囲を、拡張オーバーラップエリア分だけ広くした領域の計算をするようなコードが生成され、そのＰＥのプログラムに挿入される。
【００６２】
例えば、図４のＰＥ１が担当する配列のインデクスの範囲は本来９〜１６であるが、Ｉｔｅｒ１で７〜１８の範囲を対象に計算するコードを生成すれば、拡張オーバーラップエリア上にある値を用いてインデクス７、８、１７、１８の新しい値を求めることができる。同様に、Ｉｔｅｒ２で８〜１７の範囲を対象に計算することで、Ｉｔｅｒ１において新たに求めた拡張オーバーラップエリアの値を用いてインデクス８、１７の新しい値を求めることができる。
【００６３】
次に、拡張オーバーラップエリアの更新のためのプログラムコードを挿入する（ステップＳ６）。この処理により、並列ループを囲む逐次ループを拡張パラメータ回繰り返す毎に通信を行い、拡張オーバーラップエリアのデータを更新するようなコードが生成され、各ＰＥのプログラムに挿入される。
【００６４】
例えば、図４の場合には３回の逐次ループの繰り返し毎に通信が行われ、図７の場合にはｅ０  回の逐次ループの繰り返し毎に通信が行われることになる。ステップＳ６の後、ホスト計算機１１は処理を終了する。
【００６５】
次に、図１０から図１７までを参照しながら、オーバーラップエリアのＳＤＤＴによる更新について説明する。図２５のようにローカルエリアの両サイドにオーバーラップエリアを持つケースでも、データを１回更新する毎にデータレイアウトをＰＥ間にまたがって通信の方向にシフトしていくことで、一方向への通信に変換することができる。
【００６６】
図１０は、図２４のプログラムの実行の際に、ＳＤＤＴによりデータ更新を行う例を示している。図１０において、ダーティなオーバーラップエリア、クリーンなオーバーラップエリア、ローカルエリア、ＩＮＩＴ、Ｕｐｄａｔｅ、およびＩｔｅｒ１、２、３、・・・の意味については、図２５と同様である。
【００６７】
ＳＤＤＴによる方式では、データの格納されている位置が各繰り返し毎にトーラス状に一方向にシフトされる。ＢＤＤＴによりオーバーラップエリアを更新する従来の方式からＳＤＤＴによる方式に変換するには、双方向通信のうちの片方について、新しい値を計算するために必要なデータを隣接ＰＥから受け取るかわりに、その計算に必要なデータをその隣接ＰＥに送ってしまえばよい。この結果通信は一方向となり、オーバーラップエリアはローカルエリアの片側だけに設ければよいことになる。
【００６８】
例えば、初期状態において、ＰＥ１は配列ａのうちａ（９：１６）の範囲の要素をローカルエリアに保持するとともに、ａ（７：８）の範囲の要素の格納領域をオーバラップエリアとして持っている（ＩＮＩＴ）。そして、まずＰＥ０からデータを受け取ってオーバラップエリアのデータを更新するとともに、ａ（１５：１６）のデータをＰＥ２に送る（Ｕｐｄａｔｅ）。
【００６９】
次に、ａ（７：１６）の範囲のデータを用いて１回目の計算を行い、データａ（８：１５）を更新し（Ｉｔｅｒ１）、格納位置を通信方向に１だけシフトさせて格納する。このとき、当初ＰＥ１が持っていたデータａ（１６）は、ＰＥ２により並列に更新される。ここで、オーバラップエリアのデータがすべてダーティになったので、ＰＥ１は改めて隣接ＰＥとの間で単一方向の通信を行って拡張オーバラップエリアを更新し、Ｉｔｅｒ２のデータ更新処理を同様に行う。
【００７０】
このような処理を繰り返していくと、すべてのデータの格納位置がＰＥ０〜ＰＥ３にまたがってトーラス状に順にシフトされるので、Ｉｔｅｒ４のデータ更新の後に、ＰＥ３が持つａ（２７：２８）はＰＥ０のオーバラップエリアに転送される。
【００７１】
図１０のようなＳＤＤＴによるデータ更新の結果は、従来のＢＤＤＴによって更新した結果に一致する。また、ＢＤＤＴとＳＤＤＴとでは、データ転送の総量は同じであるが、転送の回数はＳＤＤＴを用いた方式はＢＤＤＴを用いた方式の半分で済む。したがって、ＳＤＤＴを採用することにより、データ転送の立ち上げに伴うオーバーヘッドと隣接ＰＥ間での同期処理のオーバーヘッドが削減される。
【００７２】
図１１は、ＳＤＤＴによるデータ更新の設定処理のフローチャートである。図１１の設定処理はコンパイラ２５による最適化処理の一部として、ホスト計算機１１により行われる。
【００７３】
図１１において処理が開始されると、まずホスト計算機１１は、プログラム２６中に含まれるＳＤＤＴによるデータ更新の適用箇所を検出する（ステップＳ１１）。つまり、オーバーラップエリアを用いた最適化が可能な並列ループが逐次ループに囲まれており、さらにオーバーラップエリアが各ＰＥのローカルエリアの両側（上下限）に付くような部分を、ＳＤＤＴによる更新が有効に作用する箇所として検出する。
【００７４】
次に、計算空間変換（ｃｏｍｐｕｔａｔｉｏｎａｌ  ｔｒａｎｓｆｏｒｍａｔｉｏｎ）を行う（ステップＳ１２）。この処理により、外側の逐次ループのカウントに合わせて計算するデータの位置をシフトさせ、ＳＤＤＴをオーバーラップエリアの更新に用いることを可能にする。
【００７５】
計算空間変換処理においては、すべてのデータ依存ベクトルがプロセッサアレイ１３の軸に沿った方向について正になるように、計算空間（ｃｏｍｐｕｔａｔｉｏｎａｌ  ｓｐａｃｅ  ）を決定するループネストが変換される。データ依存が距離ベクトルで表されるようなループに対しては、この計算空間変換はユニモジュラ変換（ｕｎｉｍｏｄｕｌａｒ  ｔｒａｎｓｆｏｒｍａｔｉｏｎ  ）（Ｍ．  Ｅ．  Ｗｏｌｆ  ａｎｄ  Ｍ．  Ｓ．  Ｌａｍ．  “Ａ  ｌｏｏｐ  ｔｒａｎｓｆｏｒｍａｔｉｏｎ  ｔｈｅｏｒｙ  ａｎｄ  ａｎ  ａｌｇｏｒｉｔｈｍ  ｔｏ  ｍａｘｉｍｉｚｅ  ｐａｒａｌｌｅｌｉｓｍ，”  ｉｎ  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎ  ｏｎ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ，  ｐｐ．  ４５２−４７１，  Ｏｃｔ．  １９９１．  ）のアプリケーションとして行うことができる。この場合、配列の次元をｍ、各次元におけるスキューのパラメータをそれぞれａ１  、ａ２  、・・・、ａｍ  として、変換行列Ｔは次式のような形になる。
【００７６】
【数６】
0003626784.tif 000007
【００７７】
（８）式のパラメータａ１  、ａ２  、・・・、ａｍ  を成分とするスキューベクトルＳは次のように定義される。
【００７８】
【数７】
0003626784.tif 000008
【００７９】
図１２は、図２４のプログラムの並列ループをＨＰＦのＦＯＲＡＬＬ構文で書き換えたプログラム（オリジナルプログラム）を示している。また、図１６は、このオリジナルプログラムのデータ依存を表す距離ベクトル（ｉ，ｊ）を示している。図１６において、ｉは時間軸を表し、図１２の逐次ループの繰り返しパラメータに相当する。また、ｊはＰＥ間にまたがった空間軸を表し、プロセッサアレイ１３においてＰＥの接続方向（ＰＥが並んでいる方向）に対応するメモリ空間の軸にマッピングされている。ｊは図１２のＦＯＲＡＬＬ構文のパラメータに相当する。
【００８０】
図１２のプログラムにおいては、オーバーラップエリアの更新のための通信はＢＤＤＴとなる。なぜならば、ｊ軸がＰＥの配列にマッピングされるとすると、ＰＥ間にまたがる方向では距離ベクトルが双方向になるからである。このプログラムのデータ依存を表す２つの距離ベクトルの組をＤとすると、
Ｄ＝｛（１，−１），（１，１）｝                          …（１０）
となる。
【００８１】
次に、このプログラムのループネストを、時間軸を除いてｆｕｌｌｙ  ｐｅｒｍｕｔａｂｌｅとするような変換マトリクスＴを求める。ここでは、配列の次元は１次元なので（８）式の変換マトリクスＴは２行２列のマトリクスとなり、
【００８２】
【数８】
0003626784.tif 000009
【００８３】
のように書ける。Ｔをこのようにおくと、距離ベクトル（１，−１）、（１，１）は、それぞれ次のように変換される。
【００８４】
【数９】
0003626784.tif 000010
【００８５】
（１２）式は距離ベクトル（１，−１）がＴにより距離ベクトル（１，ａ１  −１）に変換されることを表し、（１３）式は距離ベクトル（１，１）がＴにより距離ベクトル（１，ａ１  ＋１）に変換されることを表している。
【００８６】
ここで、ループネストをｆｕｌｌｙ  ｐｅｒｍｕｔａｂｌｅにするには、変換後の距離ベクトルの成分ａ１  −１とａ１  ＋１の両方が０以上になる必要がある。この条件は次式により表される。
【００８７】
ａ１  ＞１                                                  …（１４）
そこで、ｆｕｌｌｙ  ｐｅｒｍｕｔａｂｌｅとなる条件を満たす最小のａ１  の値として１を採用することにする。このとき、（１１）式のＴは次のようになる。
【００８８】
【数１０】
0003626784.tif 000011
【００８９】
また、（１２）、（１３）式から変換後の距離ベクトルはそれぞれ（１，０）、（１，２）となり、（９）式よりスキューベクトルＳ（この場合はスカラ）はＳ＝ａ１  ＝１となる。
【００９０】
図１７は、図１６の距離ベクトルに（１５）式の変換マトリクスＴを適用した後の距離ベクトルを示している。図１７では、すべての距離ベクトルのｊ成分が正となり、すべてのＰＥ間にまたがるデータ依存は一方向（ｓｉｎｇｌｅ  ｄｉｒｅｃｔｉｏｎ）  になっている。
【００９１】
ここで、図１２のプログラムの（ｉ，ｊ）に（１５）式のＴを適用すると変換後の（ｉ’，ｊ’）は次式のようになる。
【００９２】
【数１１】
0003626784.tif 000012
【００９３】
図１３は、（１６）式の（ｉ’，ｊ’）を用いて、図１２のプログラムの仮想配列ａを共有メモリのパラダイムで書き直したプログラムを示している。仮想配列ａに対応する実配列はＰＥ間にまたがって分散され、メモリ領域を静的に割り当てられている。
【００９４】
計算空間変換が終了すると、ホスト計算機１１は次にインデクス変換（ｉｎｄｅｘ  ｔｒａｎｓｆｏｒｍａｔｉｏｎ）を行う（ステップＳ１３）。この処理では、計算空間変換によりデータ依存が変化するのに合わせて、データレイアウトをシフトさせる。
【００９５】
データ依存の変化に伴って、各ＰＥのメモリ空間におけるデータレイアウトは計算処理のマッピングにアラインされなければならない。しかしながら、ＨＰＦのようなデータ並列言語で宣言される静的なデータレイアウトのままでは、このように計算する位置が変化していくようなマッピングにアラインさせることはできず、ＳＤＤＴが実現できない。そこで、仮想配列と実配列の間の対応関係を時間とともに変化させて、各ＰＥへのデータのアラインメントを逐次ループの各繰り返し毎にシフトしていかなければならない。
【００９６】
今、ｍ次元の仮想配列の添字ベクトルをＩｖ  ＝（Ｉｖ１，Ｉｖ２，．．．，Ｉｖｍ）、対応する実配列の添字ベクトルをＩｐ  ＝（Ｉｐ１，Ｉｐ２，．．．，Ｉｐｍ）とおくと、Ｉｖ  からＩｐ  へのインデクス変換は、（９）式のスキューベクトルＳと逐次ループの時間ステップｔを用いて次のように表される。
【００９７】
【数１２】
0003626784.tif 000013
【００９８】
ただし、更新前の仮想配列の添字に対しては時間ステップｔを用い、更新後の仮想配列の添字に対しては時間ステップｔ＋１を用いる。このようなインデクス変換を施せば、実配列のすべての要素の格納位置を各時間ステップ毎に移動させることが可能になる。ところが、仮想配列の上限と下限の要素は計算されず、そこに新しい値が代入されない限り更新されないので、それらの要素の値を保持しながら格納位置を移動させなければならない。そこで、インデクス変換を適用する前に、このような一貫性を保証するためのコードを挿入する。
【００９９】
図１４は、このような計算されない要素の値を保持するコードを図１３のプログラムに付加したプログラムを示している。図１４において、ｊ’＝ｉ’−１，ｉ’＋２６の各場合が仮想配列の下限と上限の各要素の処理に対応し、これらの要素の値を不変にするステートメントが挿入されている。
【０１００】
図１５は、図１４のプログラムにインデクス変換を適用した後のプログラムを示している。図１５において、Ａは仮想配列ａに対応する実配列を表す。このとき、インデクス変換におけるパラメータの変換は次のように表される。
【０１０１】
Ｊ  ←  ｊ’＋ｔ                                          …（１７）
ｔ  ←  ｉ’＋１  ｆｏｒ  ＬＨＳ（左辺）                      …（１８）
ｔ  ←  ｉ’ｆｏｒ  ＲＨＳ（右辺）                            …（１９）
ここで、（１７）の変換は、図１４の演算式中に現れるｊ’をｊ’＋ｔに変換した後に、プログラム中のすべてのｊ’をＪに置き換えることを意味する。また、（１８）の変換は演算式の左辺のｔにｉ’＋１を代入することを表し、（１９）の変換は演算式の右辺のｔにｉ’を代入することを表す。
【０１０２】
こうして、最終的に得られた図１５のプログラムでは、Ｊ＝ｉ’−１，ｉ’＋２６に対応する両端の要素の値を同一に保ったまま、各時間ステップ毎に１つずつそれらの位置が移動する。また、他の要素は各時間ステップ毎にその両隣の要素の値を用いて更新され、１つずつ位置を移動することになる。これにより、図１０に示すようなＳＤＤＴによるデータ更新が実現される。
【０１０３】
インデクス変換処理の後、ホスト計算機１１はデータレイアウトを復元するコードを挿入して（ステップＳ１４）、処理を終了する。データレイアウトの復元とは、ＳＤＤＴによるデータ更新においてシフトされた各要素の格納位置を、プログラマにより指定された元の位置に戻す処理を意味する。
【０１０４】
例えば図１０のデータ更新の場合は、逐次ループの各繰り返し毎に実配列の格納位置が１つずつ右にシフトしていくので、ｉｆ  回の繰り返しの後には元の位置からｉｆ  だけ右にずれた位置に移動している。そこで、逐次ループが終了した後にすべての要素を左にｉｆ  だけシフトさせて元の位置に戻してやれば、それ以降の処理においてシフトの影響を考慮する必要がなくなる。したがって、このような復元を行うコードを、図１５のプログラムにさらに付加しておく。
【０１０５】
図１０では、ＳＤＤＴを用いることによりオーバーラップエリアの１回の更新あたりのデータ転送の回数を削減している。しかしながら、計算によりオーバーラップエリアを更新するわけではないので、逐次ループの繰り返し毎に１回通信を行って、オーバーラップエリアを更新する必要がある。そこで、ＳＤＤＴによるデータ更新に前述の拡張オーバーラップエリアを適用すれば、通信に伴うオーバヘッドはさらに削減される。
【０１０６】
図１８は、拡張オーバーラップエリアとＳＤＤＴによるデータ更新の両方を用いる場合の設定処理のフローチャートである。図１８の設定処理もまた、コンパイラ２５による最適化処理の一部として、ホスト計算機１１により行われる。図１８において処理が開始されると、ホスト計算機１１はまず図５の拡張オーバーラップエリア設定処理を行い（ステップＳ２１）、次に図１１のＳＤＤＴによるデータ更新の設定処理を行って（ステップＳ２２）、処理を終了する。これにより、拡張オーバーラップエリアを用いてＳＤＤＴによりデータ更新を行うようなプログラムが生成される。
【０１０７】
図１９は、図２４のプログラムの実行の際に、拡張オーバーラップエリアとＳＤＤＴの両方を用いてデータ更新を行う例を示している。図１９において、ダーティなオーバーラップエリア、クリーンなオーバーラップエリア、ローカルエリア、ＩＮＩＴ、Ｕｐｄａｔｅ、およびＩｔｅｒ１、２、３、・・・の意味については、図２５と同様である。
【０１０８】
例えば、初期状態において、ＰＥ１は配列ａのうちａ（９：１６）の範囲の要素をローカルエリアに保持するとともに、ａ（５：８）の範囲の要素の格納領域を拡張オーバラップエリアとして持っている（ＩＮＩＴ）。そして、まずＰＥ０からデータを受け取って拡張オーバラップエリアのデータを更新するとともに、ａ（１３：１６）のデータをＰＥ２に送る（Ｕｐｄａｔｅ）。
【０１０９】
次に、ａ（５：１６）の範囲のデータを用いて１回目の計算を行い、データａ（６：１５）を更新し（Ｉｔｅｒ１）、格納位置を通信方向に１だけシフトさせて格納する。このとき、当初ＰＥ１が持っていたデータａ（１６）は、ＰＥ２により並列に更新される。次に、ａ（６：１５）の範囲のデータを用いて２回目の計算を行い、データａ（７：１４）を更新し（Ｉｔｅｒ２）、格納位置を通信方向に１だけシフトさせて格納する。このとき、ＰＥ１が持っていたデータａ（１５）は、ＰＥ２により並列に更新される。ここで、拡張オーバラップエリアのデータがすべてダーティになったので、ＰＥ１は改めて隣接ＰＥとの間で単一方向の通信を行って拡張オーバラップエリアを更新し、Ｉｔｅｒ３のデータ更新処理を同様に行う。
【０１１０】
図１９のデータ更新によれば、通信により拡張オーバラップエリアを更新した後、２回続けてデータ更新をローカルに行うことができる。したがって、図１０の場合と転送されるデータの総量は変わらないが、通信に伴うオーバーヘッドはより少なくなる。図１９の例では、図１０の各ＰＥのオーバーラップエリアの左側に２個のオーバーラップエリアを付加しているが、より多くの遇数個のオーバーラップエリアを付加した拡張オーバラップエリアを用いることもできる。
【０１１１】
【発明の効果】
本発明によれば、分散メモリ型並列計算機上でオーバーラップエリアを用いた並列処理を行う際に、通信とそれに伴う同期のオーバーヘッドが削減され、高速な並列処理が可能になる。
【図面の簡単な説明】
【図１】本発明の原理図である。
【図２】実施例の並列計算機の構成図である。
【図３】ホスト計算機の構成図である。
【図４】拡張オーバーラップエリアを用いたデータ更新を示す図である。
【図５】拡張オーバーラップエリア設定処理のフローチャートである。
【図６】拡張オーバーラップエリア適用箇所検出処理のフローチャートである。
【図７】２次元の拡張オーバーラップエリアを示す図である。
【図８】拡張パラメータと実行時間の関係を示す図である。
【図９】拡張オーバーラップエリア割当て処理のフローチャートである。
【図１０】単一方向のデータ転送を用いたデータ更新を示す図である。
【図１１】単一方向のデータ転送を用いたデータ更新の設定処理のフローチャートである。
【図１２】オリジナルプログラムを示す図である。
【図１３】計算空間変換後のプログラムを示す図である。
【図１４】計算されない要素を付加したプログラムを示す図である。
【図１５】インデクス変換後のプログラムを示す図である。
【図１６】オリジナルプログラムの距離ベクトルを示す図である。
【図１７】変換後の距離ベクトルを示す図である。
【図１８】設定処理のフローチャートである。
【図１９】拡張オーバーラップエリアと単一方向のデータ転送とを用いたデータ更新を示す図である。
【図２０】２次元配列のヤコビコードを示す図である。
【図２１】従来のオーバーラップエリアを示す図である。
【図２２】単一方向のデータ転送を示す図である。
【図２３】双方向のデータ転送を示す図である。
【図２４】１次元配列のヤコビコードを示す図である。
【図２５】従来のオーバーラップエリアを用いたデータ更新を示す図である。
【符号の説明】
１  検出手段
２  設定手段
３  サイズ決定手段
４  通信変更手段
１１  ホスト計算機
１２  ネットワーク
１３  プロセッサアレイ
２１  入出力部
２２  中央処理装置
２３  メモリ
２５  コンパイラ
２６  プログラム
ＰＥ０、ＰＥ１、ＰＥ２、ＰＥ３、ＰＥｎ  プロセッシングエレメント
【図１】
0003626784.tif 000014
【図２】
0003626784.tif 000015
【図３】
0003626784.tif 000016
【図４】
0003626784.tif 000017
【図５】
0003626784.tif 000018
【図６】
0003626784.tif 000019
【図７】
0003626784.tif 000020
【図８】
0003626784.tif 000021
【図９】
0003626784.tif 000022
【図１０】
0003626784.tif 000023
【図１１】
0003626784.tif 000024
【図１２】
0003626784.tif 000025
【図１３】
0003626784.tif 000026
【図１４】
0003626784.tif 000027
【図１５】
0003626784.tif 000028
【図１６】
0003626784.tif 000029
【図１７】
0003626784.tif 000030
【図１８】
0003626784.tif 000031
【図１９】
0003626784.tif 000032
【図２０】
0003626784.tif 000033
【図２１】
0003626784.tif 000034
【図２２】
0003626784.tif 000035
【図２３】
0003626784.tif 000036
【図２４】
0003626784.tif 000037
【図２５】
0003626784.tif 000038