(57)【特許請求の範囲】
【請求項１】
並列して配置されるプロセッサ毎にメモリを有し、処理要求のコードが入力されると、該コードの処理対象のデータを各プロセッサのメモリに分散配置し、該プロセッサはそれぞれのメモリ空間に配置されたデータを用いて並列処理を行う並列処理装置の処理コードを最適化する処理コード最適化装置であって、
処理要求されたコード内にある複数の処理ループについて、夫々の処理ループが他の処理のデータに依存しているかを解析するデータ依存解析手段と、
前記データ依存解析手段の解析結果を元に、データ依存の関係がない各々の処理ループについて、各プロセッサのメモリ空間に同じデータ分散処理を行う処理ループを連続させる様、要求されたコードの処理順序の変更を行う処理手段と、
を有する事を特徴とする処理コード最適化装置。
【請求項２】
並列して配置されるプロセッサ毎にメモリを有し、処理要求のコードが入力されると、該コードによる処理対象のデータを各プロセッサのメモリに分散配置し、該プロセッサはそれぞれのメモリ空間に配置されたデータを用いて並列処理を行う並列処理装置の処理コードを最適化する処理コード最適化装置であって、
処理要求されたコード内によある処理ループについて、処理ループ内の各ステートメントのデータ依存関係を解析するデータ依存解析手段と、
前記データ依存解析手段の解析結果を元に、コード内に含まれる処理ループのうち、処理ループ内にデータ依存せず、別次元にデータ分散配置されるステートメントが並存する処理ループに対し、これらのステートメントを別々の処理ループで処理する様、要求されたコードの処理順序の変更を行う処理手段と、
を有する事を特徴とする処理コード最適化装置。
【請求項３】
並列して配置されるプロセッサ毎にメモリを有し、処理要求のコードが入力されると、該コードの処理対象のデータを各プロセッサのメモリに分散配置し、該プロセッサはそれぞれのメモリ空間に配置されたデータを用いて並列処理を行う並列処理装置の処理コードを計算機が最適化する処理コード最適化方法であって、
前記計算機が、
処理要求されたコード内にある複数の処理ループについて、夫々の処理ループが他の処理のデータに依存しているかを解析するデータ依存解析ステップと、
前記データ依存解析ステップの解析結果を元に、データ依存の関係がない各々の処理ループについて、各プロセッサのメモリ空間に同じデータ分散配置を行う処理ループを連続させる様、要求されたコードの処理順序の変更を行う処理ステップと、
を実行する事を特徴とする処理コード最適化方法。
【請求項４】
並列して配置されるプロセッサ毎にメモリを有し、処理要求のコードが入力されると、該コードによる処理対象のデータを各プロセッサのメモリに分散配置し、該プロセッサはそれぞれのメモリ空間に配置されたデータを用いて並列処理を行う並列処理装置の処理コードを計算機が最適化する処理コード最適化方法であって、
前記計算機が、
処理要求されたコード内にある処理ループについて、処理ループ内の各ステートメントのデータ依存関係を解析するデータ依存解析ステップと、
前記データ依存解析ステップの解析結果を元に、コード内に含まれる処理ループのうち、処理ループ内にデータ依存せず、別次元にデータ分散配置させるステートメントが並存する処理ループに対し、これらのステートメントを別々の処理ループで処理する様、要求されたコードの処理順序の変更を行う処理ステップと、
を実行する事を特徴とする処理コード最適化方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、グローバルデータレイアウト最適化方法に関する。近年、高速処理のできる計算機（例えば、スーパーコンピュータ）を実現する方式として、並列計算機が注目を浴びている。この中でも、分散メモリ型並列計算機は、その拡張性から特に注目を浴びている。
【０００２】
この分散メモリ型並列計算機では、各プロセッサに、どのようにデータを分散配置（データレイアウト）させるかが、その並列性を活かすための重要な課題となっている。そこで、最適なデータ分散配置の手法の開発が要望されていた。
【０００３】
【従来の技術】
従来、科学技術計算系の処理には、例えば、分散メモリ型並列計算機が使用されていた。このような分散メモリ型並列計算機で使用する科学技術計算系のプログラムは、通常、プログラム内のＤＯループに大半の処理時間が費やされることが知られていた。
【０００４】
従来の並列化では、前記ＤＯループの中から、各イテレーション（繰り返し処理）を並列実行できるもの（並列ＤＯループ）を抽出し、各イテレーションをプロセッサに割り付けて並列実行させていた。
【０００５】
これを分散メモリ型並列計算機で実現するために、並列ＤＯループで、演算の対象にされる並列データは、各プロセッサに分散される。従来、このデータレイアウトを、プログラムに対して静的に１種類を自動的に決める方式、或いは各ループ毎に、最適なデータレイアウトと異なるループ間でのデータの再分散を人手で直接記述する方法が提案されていた。
【０００６】
【発明が解決しようとする課題】
前記のような従来のものにおいては、次のような課題があった。
一般に、プログラムは、複数のＤＯループから構成され、それぞれのループ毎に、好ましいデータレイアウトが異なる可能性がある。そのようなプログラムに対して、唯一のデータレイアウトで、全てのループを実行させようとしても、データレイアウトと、ループの並列性が一致していない場合には、高い性能は望めない。
【０００７】
また、人手で、全てを指定する方式は、プログラムの開発に時間がかかり、また、プログラマの熟練が必要である。
本発明は、このような従来の課題を解決し、分散メモリ型並列計算機で並列演算を行う際、データレイアウトを自動化し、かつ最適なデータレイアウトを実現して分散メモリ型並列計算機の性能を向上させることを目的とする。
【０００８】
【課題を解決するための手段】
図１は本発明の原理説明図であり、図１中、１はホスト計算機、２はディスク装置、３は通信ネットワーク、ＰＥ０、ＰＥ１・・・はプロセッサ（プロセッサエレメント）を示す。
【０００９】
本発明は前記の目的を達成するため、分散メモリ型並列計算機を、ホスト計算機１と、ディスク装置２と、通信ネットワーク３と、複数のプロセッサＰＥ０、ＰＥ１・・・で構成した。
【００１０】
また、前記各プロセッサＰＥ０、ＰＥ１・・・には、それぞれＣＰＵ（中央処理装置）と、メモリを設け、ホスト計算機１には、データ依存解析部１−１、並列化部１−２、データレイアウト部１−３、コード発生部１−４等を設けた。
【００１１】
【作用】
前記構成に基づく本発明の作用を、図１に基づいて説明する。
先ず、ホスト計算機１では、ディスク装置２に格納されているプログラムを読み出す。そして、データ依存解析部１−１が読み出したプログラムを解析して、データ依存を調べ、並列化部１−２で並列化する。
【００１２】
また、データレイアウト部１−３では、データレイアウトの処理を行い、コード発生部１−４が、各プロセッサＰＥ０、ＰＥ１・・・用のコードに変換する（コンパイル）処理を行う。
【００１３】
次に、ホスト計算機１から通信ネットワーク３を経由して、各プロセッサＰＥ０、ＰＥ１・・・に、プログラムをダウンロードする。
この場合、ホスト計算機１からダウンロードされたプログラムは、各プロセッサＰＥ０、ＰＥ１・・・のメモリ内に格納される。前記メモリ内のデータ領域に関しては、ホスト計算機１におけるコンパイル結果に従ったデータレイアウトで配置される。
【００１４】
その後、各プロセッサＰＥ０、ＰＥ１では、各ＣＰＵがメモリ内のプログラムを実行する。また、必要ならば、データ再分散のための通信が通信ネットワークを用いて行われる。
【００１５】
前記ホスト計算機１では、次のようにして、グローバルデータレイアウトの最適化を行う。
（１）  ：好ましいデータレイアウトが等しい処理ループ（ＤＯループ等）のコードが連続するように実行順序を変更しても、プログラムの意味が変わらない場合、プログラムの実行順序を変更する。このようにすれば、データ分散のための通信回数を減らすことができる。
【００１６】
（２）  ：２つ以上の処理ループで、２次元以上の同一の配列、例えば、Ａ（ｉ，ｊ）をアクセスする際、それぞれのループにとって好ましいデータレイアウト（分散割り付けを行いたい次元）が異なる場合に、プロファイル情報（処理実行時の計測結果）を基に、最も性能に影響するループにとって好ましいデータレイアウトに合わせて並列化する。
【００１７】
このようにすれば、処理速度の向上が可能となる。また、データの再分散に伴うデータ移動のオーバーヘッドを避けることができる。
（３）  ：２つ以上の処理ループで、２次元以上の同一の配列をアクセスする際、それぞれのループにとって好ましいデータレイアウトが異なる場合に、両方の次元を分散して、全てのループを並列化する。
【００１８】
このようにすれば、処理速度の向上が可能となる。また、データの再分散に伴うデータ移動のオーバーヘッドを避けることができる。
（４）  ：逐次実行すべきループの場合、プロセッサに分散したデータに合わせて、演算すべきデータを持つプロセッサ上で逐次実行する。このようにすれば、１プロセッサに全てのデータを集めるオーバーヘッドを避けることができる。
【００１９】
（５）  ：処理ループの分散（ループディストリビューション）を、各ループに好ましいデータレイアウトを求める作業の前処理として行う。そして、前処理において、一つの処理ループの中に、好ましいデータレイアウトの異なる処理（ステートメント）が複数ある場合、これらを、ループ分散処理により、ループ毎に別のデータレイアウトを割り付ける。
【００２０】
このようにすれば、ループ毎に、別のデータレイアウトを割り付けて高速処理を行うことが可能となる。
（６）  ：ループの分散を、グローバルデータレイアウトの最適化処理として用い、これにより、或る配列の要素が、どのプロセッサに含まれるか等の条件判断の処理を、ループの外で実行させるように分散する。
【００２１】
このようにすれば、前記条件判断をループの繰り返し毎に行う必要が無くなり、全体での処理時間が短縮できる。すなわち、処理の高速化が可能となる。
以上のようにして、分散メモリ型並列計算機で並列演算を行う際、データレイアウトを自動化し、かつ最適なデータレイアウトを実現して分散メモリ型並列計算機の性能を向上させることが可能となる。
【００２２】
【実施例】
以下、本発明の実施例を図面に基づいて説明する。
図２〜図１２は、本発明の実施例を示した図であり、図２〜図１２中、１はホスト計算機、２はディスク（Ｄｉｓｋ）装置、３は通信ネットワーク、ＰＥ０、ＰＥ１・・・ＰＥｎはプロセッサ（プロセッサエレメント）、ＣＰＵは中央処理装置を示す。
【００２３】
本実施例は、分散メモリ型並列計算機により、科学技術計算（数値計算）を並列処理で実行する例であり、その際、ホスト計算機において、グローバルデータレイアウト最適化処理を行うものである。以下、詳細に説明する。
【００２４】
§１：分散メモリ型並列計算機の説明・・・図２参照
図２は分散メモリ型並列計算機のブロック図である。図示のように、分散メモリ型並列計算機は、ホスト計算機１、ディスク装置（例えば、磁気ディスク装置）２、通信ネットワーク３、及び複数のプロセッサＰＥ０、ＰＥ１、ＰＥ２・・・ＰＥｎ等で構成されている。
【００２５】
そして、前記各プロセッサＰＥ０、ＰＥ１、ＰＥ２・・・ＰＥｎには、それぞれ、ＣＰＵと、メモリを備えている。前記ディスク装置２は、プログラムや、処理対象のデータを格納するものであり、通信ネットワーク３は、ホスト計算機１と各プロセッサ間の通信を行うものである。
【００２６】
また、各プロセッサＰＥ０、ＰＥ１、ＰＥ２・・・ＰＥｎでは、ＣＰＵがメモリのデータを使用して、ホスト計算機１から割り当てられたデータの処理を行う。
【００２７】
§２：分散メモリ型計算機の処理説明・・・図３参照
図３は分散メモリ型計算機の処理フローチャートである。以下、図３に基づいて、前記分散メモリ型並列計算機の処理を説明する。なお、Ｓ１〜Ｓ３は各処理ステップを示す。
【００２８】
先ず、ホスト計算機１では、ディスク装置２に格納されているプログラム（例えば、Ｆｏｒｔｒａｎプログラム）を読み出して並列化し、各プロセッサＰＥ０、ＰＥ１、ＰＥ２・・・ＰＥｎ用のコードに変換する（コンパイル）処理を行う（Ｓ１）。
【００２９】
次に、ホスト計算機１から通信ネットワーク３を経由して、各プロセッサＰＥ０、ＰＥ１、ＰＥ２・・・ＰＥｎに、プログラムをダウンロードする。この場合、ホスト計算機１からダウンロードされたプログラムは、各プロセッサエレメントＰＥ０、ＰＥ１、ＰＥ２・・・ＰＥｎのメモリ内に格納される。
【００３０】
また、データ領域は、前記メモリ内に確保しておく。そして、前記メモリ内のデータ領域に関しては、ホスト計算機１におけるコンパイル結果に従ったデータレイアウトで配置される（Ｓ２）。
【００３１】
その後、各プロセッサＰＥ０、ＰＥ１、ＰＥ２・・・ＰＥｎでは、各ＣＰＵがメモリ内のプログラムを実行する。また、必要ならば、データ再分散のための通信が通信ネットワークを用いて行われる（Ｓ３）。
【００３２】
§３：コンパイル処理の説明・・・図４参照
図４はコンパイル処理フローチャートである。以下、図４に基づいて、コンパイル処理を説明する。なお、この処理は、ホスト計算機が行う処理（図２のＳ１の処理）であり、Ｓ１１〜Ｓ１８は各処理ステップを示す。
【００３３】
先ず、ホスト計算機１は、処理対象のデータについて、データ依存を解析し（Ｓ１１）、ループディストリビューション（処理ループの分散）による前処理を行う（Ｓ１２）。その後、各ループネストに対するデータレイアウトを決定する（Ｓ１３）。
【００３４】
そして、ホスト計算機１は、プログラム全体を通して、全てのデータレイアウトが等しいか否かを判断する（Ｓ１４）。その結果、データレイアウトが等しくなければ、実行順序の入れ換えにより再分散を減らす（Ｓ１５）。そして、再分散が必要な部分を対象として、再分散のオーバーヘッドに対して十分な処理粒度があるか否かを判断する（Ｓ１６）。
【００３５】
その結果、十分な処理粒度がなければ、複数のデータレイアウトを活かす分割方法を採用する（Ｓ１７）。また、シーケンシャルループ（逐次実行型ループ）について、データが存在するプロセッサ上で処理を行うためのコードを生成する（Ｓ１８）。
【００３６】
また、前記Ｓ１４の処理で、データレイアウトが等しい場合、及び前記処理Ｓ１６で、十分な処理粒度がある場合には、前記Ｓ１８の処理を行う。
以下、前記分散メモリ型並列計算機が行うグローバルデータレイアウト最適化処理を詳細に説明する。なお、以下に説明するグローバルデータレイアウト最適化処理は、ホスト計算機１が実行するプログラム（プロセッサで使用するプログラムとは異なる）に、各種の判断情報、データ等を与えておき、前記プログラムの実行により自動的に判断して処理を行う。
【００３７】
§４：データレイアウト最適化のためのコード例の説明・・・図５参照
図５は実施例の処理説明図１であり、図５のＡ図はデータレイアウト最適化のためのコード例を示した図、図５のＢ図は、配列Ａ（Ｉ，Ｊ）の説明図である。
【００３８】
データレイアウト最適化のためのコード例として、例えば、図５のＡ図に示したようなコード例がある。このコード例は、ＤＯループによる処理を示しており、２次元配列のデータを用いて処理を行う例である。
【００３９】
この例のＤＯループには、▲１▼のループと、▲２▼のループと、▲３▼のループがある。例えば、前記▲１▼のループにおいて、Ａ（Ｉ，Ｊ）は、ＩとＪからなる２次元の配列（処理対象のデータの配列）であり、「ＤＯ  １００  Ｉ＝１，Ｎ」は、前記配列Ａ（Ｉ，Ｊ）のＩ＝１からＮまで実行することを示している。
【００４０】
また、「ＤＯＡＬＬ  １００  Ｊ＝１，Ｎ」は、Ｊ側に対して並列実行可能なＤＯループであり、Ｊ＝１からＮまで実行することを示している。
すなわち、前記▲１▼のループでは、Ｉ、Ｊからなる２次元の配列Ａ（Ｉ，Ｊ）に対して、Ｉについて１からＮまで演算し、次にＪについて１からＮまで演算し（２重のループによる処理）、その演算結果のデータを、配列Ａ（Ｉ，Ｊ）のＩ、及びＪのデータとする処理である。
【００４１】
前記配列Ａ（Ｉ，Ｊ）は、例えば、図５のＢ図に示したように、縦方向（１次元側）をＩ、横方向（２次元側）をＪとした２次元配列のデータである。
▲２▼のループでは、「ＤＯＡＬＬ  ２００  Ｉ＝１，Ｎ」がＩについて並列処理可能であり、Ｉについて１からＮまで実行することを示している。また、「ＤＯ２００  Ｊ＝１，Ｎ」はＪについて１からＮまで実行することを示している。
【００４２】
なお、ｆ（Ａ（Ｉ，Ｊ））は、データ依存を示しており、前記▲１▼のループで演算した結果のデータを使用して演算を実行することを示す。
▲３▼のループでは、「ＤＯ  ３００  Ｉ＝１，Ｎ」がＩについて１からＮまで実行することを示しており、「ＤＯＡＬＬ  ３００  Ｊ＝１，Ｎ」が、Ｊ方向に並列実行可能であり、Ｊについて１からＮまで実行することを示している。
【００４３】
なお、この場合もｆ（Ａ（Ｉ，Ｊ））は、データ依存を示しており、前記▲１▼のループで演算した結果のデータを使用して演算を実行することを示す。なお、１〜１４はステートメント番号である。
【００４４】
§５：データ依存と、望ましいレイアウトの説明・・・図６参照
図６は実施例の処理説明図２であり、Ａ図はオリジナルオーダでの実行順序、Ｂ図はリオーダリング後（変更後）の実行順序を示している。
【００４５】
図６において、レイアウト１は、図５のＡ図に示した▲１▼のループ（Ｌｏｏｐｓ１００）と、▲３▼のループ（Ｌｏｏｐｓ３００）からなるデータレイアウトのグループであり、１次元目が（１次元側Ｉのデータ）が分散されている。また、レイアウト２は、▲２▼のループ（Ｌｏｏｐｓ２００）からなるデータレイアウトのグループであり、２次元目（２次元側Ｊのデータ）が分散されている。
【００４６】
図６のＡ図では、図５のコードに関するデータレイアウトのグループと、ループ間のデータ依存（実線によるアーク）を表している。ここで点線は、元々のプログラムの実行順序（Ｌｏｏｐｓ１００→Ｌｏｏｐｓ２００→Ｌｏｏｐｓ３００の順序）を表している。
【００４７】
この場合、先ず、前記▲１▼のループであるＬｏｏｐｓ１００を実行し、次に▲２▼のループであるＬｏｏｐｓ２００を実行し、その後、▲３▼のループであるＬｏｏｐｓ３００を実行する。
【００４８】
このような順序で処理を実行すると、レイアウト１とレイアウト２の間を２度横切る必要があり、その度に、データの再分散が必要である。例えば、レイアウト１の内部だけの処理であれば、データの再分散は必要ないが、レイアウト１からレイアウト２へ移って処理を行う場合には、データの再分散が必要となる。
【００４９】
また、レイアウト２からレイアウト１へ移って処理を行う場合にも、データの再分散が必要となる。
前記のように、データレイアウトのグループを横切る場合には、データの再分散が必要になる。この例では、点線は２回、データレイアウトのグループを横切っている。
【００５０】
しかし、データ依存の関係を壊さない限り、プログラムの意味は保たれるので、プログラムの実行順序を変更することができる。この例では、図６のＢ図に示したように実行順序を変更（Ｌｏｏｐｓ１００→Ｌｏｏｐｓ３００→Ｌｏｏｐｓ２００の順序）することができる。
【００５１】
これにより、点線はデータレイアウトのグループの境界を、１回しか横切らなくなる。その結果、データの再分散の回数が減少する。また、データ再分散のための通信の回数も減少する。
【００５２】
以上のように、望ましいデータレイアウトが、等しいＤＯループのコードが連続するように実行順序を変更しても、プログラムの意味が変わらない場合に、実行順序を変更することで、データ再分散のための通信の回数を減らすことができる。
【００５３】
なお、この処理は、ホスト計算機１が実行するプログラムに、判断情報（プログラムの意味が変わるか否か等の情報）を与えておくことにより、自動的に判断して実行順序の変更を行う。
【００５４】
§６：並列処理の実行時間の比較・・・図７、図８参照
図７は並列処理の実行時間比較図１（Ａ：例１、Ｂ：例２）、図８は並列処理の実行時間比較図２（Ｃ：例３）である。
【００５５】
以下、図７、図８に基づいて、図５に示したコードの各ループ実行時間が占める割合と、データレイアウトが全体の性能に与える影響を説明する。なお、図７、図８の例１、例２、例３において、縦軸のＰ１は、ループ２００の合計処理時間、Ｐ２はループ１００、３００の合計処理時間を示す。
【００５６】
また、横軸のＱ１は並列化しないで、シーケンシャルに実行した場合、Ｑ２は１次元側を選択（分散）した場合（ループ２００の中で並列化できるようにデータレイアウトを変更した場合）、Ｑ３は２次元側を選択（分散）した場合（ループ１００、３００の中で並列化できるようにデータレイアウトを変更した場合）、Ｑ４は両方を選択（１ｓｔディメンジョン、及び２ｎｄディメンジョンの両方を選択）した場合を示している。
【００５７】
例１、例２、例３は、図５のコードに関して、配列Ａ（Ｉ，Ｊ）の１次元側の分散（Ｉの分散）が有効な並列ループ（ループ２００）と、配列Ａ（Ｉ，Ｊ）の２次元側の分散（Ｊの分散）が有効な並列ループ（ループ１００とループ３００）の実行時間比によって、どのレイアウトが全体の実行時間の高速化に影響を及ぼすかを示している。
【００５８】
また、この例では、９台のプロセッサを使用した場合と、２５台のプロセッサを使用した場合での並列化を示している。以下、各例について説明する。
（１）  ：例１の説明・・・図７のＡ図参照
例１は、それぞれの実行時間比が、５０％対５０％の場合であり、９台のプロセッサで実行した場合の処理時間を示している。Ｑ１の場合、Ｐ１が５０％でＰ２が５０％であるが、Ｑ２の場合はＰ１が５．５％に短縮され、Ｑ３の場合は、Ｐ２が５．５％に短縮される。更に、Ｑ４ではＰ１、Ｐ２が両方共１６．６％に短縮される。
【００５９】
従って、例１では、Ｑ４のように、両方の次元を分散するのが最も高速になることが分かる。
（２）  ：例２の説明・・・図７のＢ図参照
例２は、ループ２００の実行時間が２０％の場合であり、９台のプロセッサで実行した場合の処理時間を示している。Ｑ１の場合、Ｐ１が２０％でＰ２が８０％であるが、Ｑ２の場合はＰ１が２．２％に短縮され、Ｑ３の場合はＰ１が２０％、Ｐ２が８．９％に短縮される。更に、Ｑ４ではＰ１が２６．７％、Ｐ２が６．７％に短縮される。
【００６０】
従って、例２では、Ｑ３のように、２次元側を分散するのが最も高速になることが分かる。
（３）  ：例３の説明・・・図８参照
例３は、ループ２００の実行時間が２０％の場合を、２５台のプロセッサで実行した場合の処理時間を示している。Ｑ１の場合、Ｐ１が２０％でＰ２が８０％であるが、Ｑ２の場合はＰ１が０．８％に短縮され、Ｑ３の場合はＰ１が２０％、Ｐ２が３．２％に短縮される。更に、Ｑ４ではＰ１が１６％、Ｐ２が４％に短縮される。
【００６１】
従って、例３では、Ｑ４のように、１次元側と、２次元側の両方を分散するのが最も高速になることが分かる。
（４）  ：結論
以上のように、プロファイル情報（どのループがどのくらい時間がかかっているかの計測結果の情報）を基に、最適なデータの分散を決定することができる。すなわち、一度処理を実行することにより、プロファイル情報を得て、そのプロファイル情報に基づいて、前記のようにデータの分散をするかを決定する。このようにすれば、処理時間の短縮化が実現する。
【００６２】
また、前記プロファイル情報を用いない場合、両方の次元（１次元、及び２次元）を分散し、全てのループから並列性を引き出すようにして、データの分散を決定すれば良い。
【００６３】
これにより、好ましいデータのレイアウトが異なるループ間の実行時間の割合が等しい場合は最適となり、比率が異なっても、プロセッサの数が大きくなるに従って、最適な場合に近づく。
【００６４】
なお、この処理は、ホスト計算機１が実行するプログラムに、判断情報（プロファイル情報等）を与えておくことにより、自動的に判断して実行順序の変更を行う。
【００６５】
§７：逐次実行型ループによる処理例の説明・・・図９参照
図９は逐次実行型ループのコード例である。図９において、１〜１１はステートメント番号である。また、「ＤＯ  ２７０  Ｊ＝１，Ｍ」は、ＤＯループであり、Ｊ＝１からＭまで実行することを示している。
【００６６】
更に、「ＤＯ  ２７０  Ｉ＝Ｉ１Ｐ，Ｉ２Ｍ」は、ＤＯループであり、Ｉ＝Ｉ１Ｐ、Ｉ２Ｍについて実行することを示している。また、ＲＸ（Ｉ，Ｊ）、ＲＹ（Ｉ，Ｊ）はＩ、及びＪからなる２次元の配列を示している。
【００６７】
この処理例では、▲１▼で示したループと、▲２▼で示したループは、逐次実行型のループであり、並列処理はできない。すなわち、▲１▼のループと、▲２▼のループは、データ依存があり、シーケンシャルな処理であるから、▲１▼のループを実行した後、▲２▼のループを処理する必要がある。
【００６８】
§８：逐次実行型ループのデータ分散と、通信量の説明・・・図１０参照
図１０は、逐次実行型ループのデータ分散と通信量の説明図であり、図１０のＡ図は例１（１次元目を分散）、Ｂ図は例２（２次元目を分散）を示す。
【００６９】
この例は、前記図９に示した逐次実行型ループを複数のプロセッサ（プロセッサ０、プロセッサ１）で処理する例であるが、並列処理ではなく、逐次型処理（シーケンシャルな処理）である。このようにするのは、並列処理と、並列処理の間で逐次型ループの処理を行う場合、同じシステムで実行するからである。
【００７０】
このような場合でも、プロセッサ間の通信量を出来るだけ少なくすることが必要になる。この例では、前記図９に示したコード例の実行に際し、プロセッサ０と、プロセッサ１に、データを分散して処理を行う。この場合、図の矢印は、データ依存による処理順序を示しており、特に、太い実線の矢印は、データ依存によって引き起こされるプロセッサ間に跨がるデータ通信を示している。
【００７１】
例えば、データ依存により、プロセッサ０からプロセッサ１に処理が移る場合は、プロセッサ０からプロセッサ１へのデータ通信により処理結果のデータを送る（データ依存をキャリーする）ことでプロセッサ１が処理を行う。また、プロセッサ１からプロセッサ０に処理が移る場合は、プロセッサ１からプロセッサ０へのデータ通信により処理結果のデータを送る（データ依存をキャリーする）ことでプロセッサ０が処理を行う。
【００７２】
このように、プロセッサ０とプロセッサ１にデータを分散配置して処理を行うと、１つのプロセッサから他のプロセッサへ処理が移る場合に、プロセッサ間でデータ通信を行う必要がある。
【００７３】
この場合、もし、配列ＲＸ（Ｉ，Ｊ）と、ＲＹ（Ｉ，Ｊ）の１次元目が分散（Ｉ側が分散）されているなら、図１０のＡ図に示したように、内側ループがデータ依存をキャリーする。
【００７４】
また、配列ＲＸ（Ｉ，Ｊ）と、ＲＹ（Ｉ，Ｊ）の２次元目が分散（Ｊ側が分散）されているならば、図１０のＢ図に示したように、外側ループがデータ依存をキャリーする。前記例１では、プロセッサの数をＰとした場合、総データ通信数は、Ｐ×Ｍであり、例２では、総データ通信数は、Ｐ−１である。
【００７５】
プロセッサ間に跨がるデータ依存によって引き起こされるオーバーヘッドは、この装置データ通信数によって評価することができる。１台のプロセッサに、全てのデータを集めて処理を行う場合のオーバーヘッドより、分散したデータで逐次実行した方が、オーバーヘッドが小さいと判断した場合に、分散したデータで逐次実行する。
【００７６】
§９：ループ分割例１の説明・・・図１１参照
図１１はループ分割例１を示した図であり、Ａ図はループ分割前のコード例、Ｂ図はループ分割後のコードを示す。
【００７７】
図１１において、ステートメント１の「ＤＯ  ２００  Ｊ＝Ｋ，Ｌ」はＤＯループであり、Ｊ＝Ｋ、Ｌについて実行することを示している。また、ステートメント３の「Ｃ＝Ｃ＋ＤＡＢＳ（Ａ（Ｊ，Ｉ））」、及びステートメント４の「Ｒ＝Ｒ＋ＤＡＢＳ（Ａ（Ｉ，Ｊ））」はボディであり、Ｊについて、前記のように実行することを示している。
【００７８】
このループ分割は、並列化の前処理として行うものであり、前記ボディを分割する。先ず、図１１のＡ図に示したＤＯループは、並列実行可能であるが、ステートメント３にとって好ましいデータ分散と、ステートメント４にとって好ましいデータ分散では異なっている。
【００７９】
ステートメント３にとって好ましいデータ分散は、配列Ａ（Ｊ，Ｉ）の１次元目を分散（Ｊ側を分散）することであり、ステートメント４にとって好ましいデータ分散は、配列Ａ（Ｉ，Ｊ）の２次元目を分散（Ｊ側を分散）することである。
【００８０】
このようなコンフリクト（矛盾）は、ルーブ分割により解消することができる。図１１のＢ図はループ分割した結果のコードを示している。この場合、ステートメント３の「Ｃ＝Ｃ＋ＤＡＢＳ（Ａ（Ｊ，Ｉ））」と、ステートメント４の「Ｒ＝Ｒ＋ＤＡＢＳ（Ａ（Ｉ，Ｊ））」を分割して、図１１のＢ図に示した▲１▼と▲２▼の処理とする。
【００８１】
このようなループ分割を行うことにより、各ループ毎に、好ましいデータレイアウトを割り付けることが可能になる。なお、前記前処理を行った後、前記▲１▼と▲２▼のループについて並列化処理を行う。
【００８２】
§１０：ループ分割例２の説明・・・図１２参照
図１２はループ分割例２（図１１に示したコードの疑似コード）を示した図であり、Ａ図はループ分割前のコード例、Ｂ図はループ分割後のコードを示す。
【００８３】
図１２において、ステートメント１の「ＤＯ  ２００  Ｊ＝Ｋ，Ｌ」はＤＯループであり、Ｊ＝Ｋ、Ｌについて演算を行うことを示している。また、ステートメント３の「ＩＦ・・・ＤＡＢＳ（Ａ（Ｊ，Ｉ））」は、プロセッサが、配列Ａ（Ｊ，Ｉ）を持っていたら、Ｃ＝Ｃ＋ＤＡＢＳ（Ａ（Ｊ，Ｉ））の処理を実行することを示している。
【００８４】
更に、ステートメント４の「ＩＦ・・・ＤＡＢＳ（Ａ（Ｉ，Ｊ））」は、プロセッサが、配列Ａ（Ｉ，Ｊ）を持っていたら、Ｒ＝Ｒ＋ＤＡＢＳ（Ａ（Ｉ，Ｊ））の処理を実行することを示している。
【００８５】
従って、前記図１２に示した▲１▼のループを実行する場合には、プロセッサは、繰り返しの度に、前記ステートメント３、及び４の判定処理を行うことが必要である。このため処理が遅くなる。
【００８６】
この点を解決するため、前記▲１▼のループを分割し、図１２のＢ図に示したように、前記判定処理をループの外に置くようにして分割する。この分割時には、ステートメント５の「ＩＦ・・・２２０」の処理において、前記判定処理を行えば、繰り返し処理の場合にも１回の判定処理で済む。
【００８７】
すなわち、前記分割後のコードによれば、ループのイテレーションで、配列Ａのオーナーのチェックが行われる。このチェックのコードを、ループディストリビューションにより、ループの外側で行うことができるようになる。
【００８８】
この例で、変数ＬＯＷＥＲと、ＵＰＰＥＲは、各プロセッサにおけるローカルなループの上限と下限を表している。
【００８９】
【発明の効果】
以上説明したように、本発明によれば次のような効果がある。
（１）  ：前記のように、グローバルデータレイアウト最適化処理を行うことにより、データ再分散に伴う通信のオーバーヘッドを小さくすることができる。従って、ＤＯループの演算を、分散メモリ型並列計算機上で、高速に実行することが可能になる。
【００９０】
（２）  ：分散メモリ型並列計算機で並列演算を行う際、データレイアウトを自動化し、かつ最適なデータレイアウトを実現して分散メモリ型並列計算機の性能を向上させることができる。
【００９１】
(3) ：実行順序を変更することで、データ分散のための通信回数を減らすことができる。従って、データ再分散に伴う通信のオーバーヘッドが小さくなり、処理の高速化が可能になる効果がある。
【００９２】
(4) ：最も性能に影響するループにとって好ましいデータレイアウトに合わせて並列化しているので、処理速度の向上が可能となる。また、データの再分散に伴うデータ移動のオーバーヘッドを避けることができる効果がある。
【００９３】
(5) ：両方の次元を分散して、全てのループを並列化しているので、処理速度の向上が可能となる。また、データの再分散に伴うデータ移動のオーバーヘッドを避けることができる効果がある。
【００９４】
(6) ：１プロセッサに全てのデータを集めるオーバーヘッドを避けることができる効果がある。
(7) ：前処理において、ループ分散処理により、ループ毎に別のデータレイアウトを割り付けるので、ループ毎に、別のデータレイアウトを割り付けて高速処理を行うことが可能となる効果がある。
【００９５】
(8) ：条件判断の処理を、ループの外で実行させるように分散しているので、条件判断をループの繰り返し毎に行う必要が無くなり、全体での処理時間が短縮できる効果がある。
【図面の簡単な説明】
【図１】本発明の原理説明図である。
【図２】実施例における分散メモリ型並列計算機のブロック図である。
【図３】実施例における分散メモリ型並列計算機の処理フローチャートである。
【図４】実施例におけるコンパイル処理フローチャートである。
【図５】実施例の処理説明図１である。
【図６】実施例の処理説明図２である。
【図７】実施例における並列処理の実行時間比較図１である。
【図８】実施例における並列処理の実行時間比較図２である。
【図９】実施例における逐次実行型ループのコード例である。
【図１０】実施例における逐次実行型ループのデータ分散と通信量の説明図である。
【図１１】実施例におけるループ分割例１である。
【図１２】実施例におけるループ分割例２である。
【符号の説明】
１  ホスト計算機
２  ディスク装置
３  通信ネットワーク
ＰＥ０、ＰＥ１  プロセッサ（プロセッサエレメント）
ＣＰＵ  中央処理装置
１−１  データ依存解析部
１−２  並列化部
１−３  データレイアウト部
１−４  コード発生部
【図１】
0003628718.tif 000002
【図２】
0003628718.tif 000003
【図３】
0003628718.tif 000004
【図４】
0003628718.tif 000005
【図５】
0003628718.tif 000006
【図６】
0003628718.tif 000007
【図７】
0003628718.tif 000008
【図８】
0003628718.tif 000009
【図９】
0003628718.tif 000010
【図１０】
0003628718.tif 000011
【図１１】
0003628718.tif 000012
【図１２】
0003628718.tif 000013