(57)【特許請求の範囲】
【請求項１】
第１の生成手段と第２の生成手段と第３の生成手段と第４の生成手段とを有するコンパイル処理装置で実行されて、ローカルメモリを持つ複数のプロセッサエレメントから構成される分散メモリ型並列計算機で実行されるソースプログラムをコンパイルするコンパイル処理方法であって、
上記第１の生成手段が、ソースプログラムの持つループ関数ごとに、配列アクセスの添字からデータ依存関係を解析し、該ループ関数が並列実行可能か否かを解析して、並列実行可能なループ関数についてはループ分割情報を生成し、
上記第２の生成手段が、上記配列アクセスの要素が全てのプロセッサエレメントのローカルメモリに展開されることを想定して、上記並列実行可能なループ関数ごとに、上記配列アクセスの添字から各プロセッサエレメントについてのデータアクセス範囲を解析して、そのデータアクセス範囲情報を生成し、
上記第３の生成手段が、上記配列アクセスの要素が全てのプロセッサエレメントのローカルメモリに展開されることを想定して、上記ループ分割情報と上記データアクセス範囲情報とに基づいて、各プロセッサエレメントと他のプロセッサエレメントとの間で必要となるデータ転送を解析して、転送対象と転送位置と転送先とを指定するデータ転送情報を生成し、
上記第４の生成手段が、上記ループ分割情報に従って分割されるループ関数を持つオブジェクトコードを生成するとともに、上記データ転送情報に従って作成されるデータ転送命令及びデータ受信命令を持つオブジェクトコードを生成することを、
特徴とするコンパイル処理方法。
【請求項２】
請求項１記載のコンパイル処理方法において、
上記第３の生成手段は、後方で使用されるデータについては、その値が確定した時点から転送開始に入るようにと転送位置を決定するよう処理することを、
特徴とするコンパイル処理方法。
【請求項３】
請求項１又は２記載のコンパイル処理方法において、
上記第３の生成手段は、プロセッサエレメントにより個別更新される配列部分については、その配列部分を他の全てのプロセッサエレメントに転送するようにと転送先を決定するよう処理することを、
特徴とするコンパイル処理方法。
【請求項４】
請求項１又は２記載のコンパイル処理方法において、
上記第３の生成手段は、特定のプロセッサエレメントのみが必要とするデータについては、そのデータをそのプロセッサエレメントにのみ転送するようにと転送先を決定するよう処理することを、
特徴とするコンパイル処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ローカルメモリを持つ複数のプロセッサエレメントから構成される分散メモリ型並列計算機用のオブジェクトコードを生成するコンパイル処理方法に関し、特に、完全自動並列化を実現するコンパイル処理方法に関する。
【０００２】
【従来の技術】
分散メモリ型並列計算機は、図１０に示すように、メモリを有する演算器（プロセッサエレメント／ＰＥ）がネットワーク機構で複数結合された形式のアーキテクチャを持つ計算機である。この分散メモリ型並列計算機では、自ＰＥ上のデータについては、通常のアクセス方式でアクセスすることが可能であるが、他のＰＥ上のデータについては、ネットワーク機構を経由してアクセスしなければならない。
【０００３】
このようなメモリアーキテクチャを対象にコンパイラで自動並列化を行う場合、データをＰＥ上に非常にうまく分散して配置する必要があるが、現在のコンパイラの自動並列化機能では、手続き部分については自動並列化を実現できるものの、データの自動分散配置を行うことは非常に難しいというのが実情である。
【０００４】
この問題点を解決するために、ＰＥ間で共有される仮想的なメモリ空間を、各ＰＥのメモリとネットワーク機構を用いて仮想的に構成することが行われている。この仮想的なメモリ空間は仮想グローバル空間と呼ばれ、各ＰＥ毎に分かれた通常のメモリ空間はローカル空間と呼ばれている。図１１に、このメモリアーキテクチャを図示する。
【０００５】
この仮想グローバル空間は、全てのＰＥからアクセスすることが可能であるが、ネットワーク機構を介するため、アクセス速度が遅い。これに対して、ローカル空間は、自ＰＥからだけアクセスすることが可能であり、他ＰＥからアクセスすることは不可能であるが、アクセス速度は速い。
【０００６】
これから、コンパイラの自動並列化において、データの自動分散配置の問題点を回避するために、仮想グローバル空間を使用する構成を採ると、データへのアクセス速度が遅くなり、性能が著しく低下するという問題点が出ることになる。一方、性能を重視して、ローカル空間を使用すると、自動並列化において困難なデータの自動分散配置を実現する技術を構築しなければならないという問題点がある。
【０００７】
そこで、従来では、自動並列化を行うために、ユーザに対してデータの分散配置形態を指示させて、この指示に基づいてデータを分散配置する構成を採って、自動並列化機能で、なるべくローカル空間を使用するようにしつつ、ローカル空間を使用できない部分だけ、仮想グローバル空間を使用するようにして並列化を行うという構成を採っている。
【０００８】
【発明が解決しようとする課題】
しかしながら、このような従来技術に従っていると、ユーザがデータの分散配置を指示しなければならないことから、完全な自動並列化になっていないという問題点があった。そして、プログラムの内容によって仮想グローバル空間を使用せざるを得ない場合があり、当たり外れが激しく、コンスタントな性能向上を期待できないという問題点があった。そして、データを分散配置することから、並列化の対象となるループが、回転間のデータ依存関係の無いものに限定されてしまうという問題点もあった。
【０００９】
本発明はかかる事情に鑑みてなされたものであって、ローカルメモリを持つ複数のプロセッサエレメントから構成される分散メモリ型並列計算機用のオブジェクトコードを完全自動並列化でもって生成する新たなコンパイル処理方法の提供を目的とする。
【００１０】
【課題を解決するための手段】
図１に本発明の原理構成を図示する。
図中、１はデータ処理装置であって、本発明を実現するコンパイラ１０を展開するものである。
【００１１】
このコンパイラ１０は、ソースプログラムをコンパイルすることで分散メモリ型並列計算機用のオブジェクトコードを生成するものであって、ソースプログラムを字句の列に変換して、その字句列からソースプログラムの文法的な構造を再構成し、更に意味解析を実行する字句・構文解析部１１と、字句・構文解析部１１の解析結果を使って、オブジェクトコードを生成するコード生成部１２と、字句・構文解析部１１とコード生成部１２との間に位置して、コード生成の最適化を行う最適化部１３と、全体の制御処理を実行する制御部１４とを備える。
【００１２】
この最適化部１３は、本発明を実現するために、ソースプログラムの持つループ関数ごとに、配列アクセスの添字からデータ依存関係を解析し、該ループ関数が並列実行可能か否かを解析して、並列実行可能なループ関数についてはループ分割情報を生成する第１の解析部１５と、配列アクセスの要素が全てのプロセッサエレメントのローカルメモリに展開されることを想定して、並列実行可能なループ関数ごとに、配列アクセスの添字から各プロセッサエレメントについてのデータアクセス範囲を解析して、そのデータアクセス範囲情報を生成する第２の解析部１６と、配列アクセスの要素が全てのプロセッサエレメントのローカルメモリに展開されることを想定して、第１の解析部１５の生成したループ分割情報と第２の解析部１６の生成したデータアクセス範囲情報とに基づいて、各プロセッサエレメントと他のプロセッサエレメントとの間で必要となるデータ転送を解析して、転送対象と転送位置と転送先とを指定するデータ転送情報を生成する第３の解析部１７とを備える。
【００１３】
そして、コード生成部１２は、第１の解析部１５の解析結果と第３の解析部１７の解析結果とに基づいて、ループ分割情報に従って分割されるループ関数を持つオブジェクトコードを生成するとともに、データ転送情報に従って作成されるデータ転送命令及びデータ受信命令を持つオブジェクトコードを生成していくように処理する。
【００１４】
このように構成される本発明では、第１の解析部１５は、ソースプログラムの持つ手続き部分のみを処理対象として、それらの手続き部分が並列化できるのか否かを解析して、並列実行可能な手続き部分については、各プロセッサエレメントに担当させる部分を解析する。すなわち、ソースプログラムの持つデータの配列については並列化対象としない。これから、各プロセッサエレメントは、オブジェクトコードがローディングされると、データについては、ソースプログラムに記述される配列宣言文に従って、データファイルからその全てをコピーして持つことになる。
【００１５】
一方、第２の解析部１６は、各プロセッサエレメントの担当する手続き部分に対してデータを共通に割り当てつつ、第１の解析部１５で解析される各プロセッサエレメントの担当する手続き部分のデータアクセス範囲を解析し、これを受けて、第３の解析部１７は、各プロセッサエレメントの担当する手続き部分に対してデータを共通に割り当てつつ、第２の解析部１６で解析されるデータアクセス範囲と、分割された手続き部分のプログラム記述とに基づき、プロセッサエレメント間で転送すべきデータの転送形態を解析する。
【００１６】
例えば、第３の解析部１７は、プロセッサエレメントにより個別更新される配列部分については、その配列部分を他の全てのプロセッサエレメントに転送するようにと転送先を決定することで、ローディング後のデータの整合性を保つように処理する。また、後方で使用されるデータについては、その値が確定した時点から転送開始に入るようにと転送位置を決定することで、データ転送処理と演算処理とを重ね合わせてデータ転送処理を隠蔽するように処理する。また、特定のプロセッサエレメントのみが必要とするデータについては、そのデータをそのプロセッサエレメントにのみ転送するようにと転送先を決定することで、転送コストの削減を図るように処理するのである。
【００１７】
このように、本発明のコンパイラ１０では、分散メモリ型並列計算機でデータ処理を実行する場合に、手続き部分のみを自動的に並列化し、データについては、分散配置させずに全プロセッサエレメントがそのコピーを持つ構成を採って、必要に応じてデータを一致させつつ、必要なデータをやり取りする構成を採ることで、完全自動並列化を実現するものである。
【００２１】
【発明の実施の形態】
以下、実施の形態に従って本発明を詳細に説明する。
図２に、本発明のコンパイラ１０が実行する最適化処理の処理構成を図示する。
【００２２】
この図に示すように、本発明のコンパイラ１０は、最適化処理に入ると、先ず最初に、手続き部並列化解析処理を実行する。この手続き部並列化解析処理では、ソースプログラムの持つ手続き部（主にＤＯループである）が並列化できるのか否かを解析して、並列化できるＤＯループについては、ループ分割情報を生成する。すなわち、本発明のコンパイラ１０では、ソースプログラムの持つデータについては分割しない構成を採るのである。
【００２３】
この手続き部並列化解析処理を終了すると、続いて、データアクセス範囲解析処理を実行する。このデータアクセス範囲解析処理では、ソースプログラムの持つデータについては分割しないという前提の下に、手続き部並列化解析処理で求められた並列化できるＤＯループのデータアクセス範囲を解析して、データアクセス範囲情報を生成する。
【００２４】
このデータアクセス範囲解析処理を終了すると、続いて、最適データ転送解析処理を実行する。この最適データ転送解析処理では、ソースプログラムの持つデータについては分割しないという前提の下に、データアクセス範囲解析処理で生成されたデータアクセス範囲情報と、手続き部並列化解析処理で生成されたループ分割情報とに基づき、プロセッサエレメント間で転送すべきデータの転送情報を生成してから、その転送情報を最適化することで最適なデータ転送形態を決定する。
【００２５】
図３に、この最適化処理の更に詳細な処理フローを図示する。
すなわち、本発明のコンパイラ１０は、最適化処理に入ると、手続き毎に、この処理フローに示すように、手続き部並列化解析処理に入って、先ず最初に、ソースプログラムに記述されるデータフローを解析し、続いて、ソースプログラムに記述される制御フローを解析し、続いて、ＤＯループ毎に、配列アクセスの添字からデータ依存関係を解析し、続いて、これらの解析結果に基づき、ＤＯループが並列実行可能か否かを解析して、並列実行可能なＤＯループについてはループ分割情報を生成する。
【００２６】
そして、手続き部並列化解析処理を終了すると、データアクセス範囲解析処理に入って、配列アクセスの要素が全てのプロセッサエレメントのローカルメモリに展開されることを想定して、並列実行可能なＤＯループ毎に、配列アクセスの添字から各プロセッサエレメントについてのデータアクセス範囲を解析して、そのデータアクセス範囲情報を生成する。
【００２７】
そして、データアクセス範囲解析処理を終了すると、最適データ転送解析処理に入って、配列アクセスの要素が全てのプロセッサエレメントのローカルメモリに展開されることを想定して、先ず最初に、ＤＯループ毎に、生成したループ分割情報とデータアクセス範囲情報とに基づいて、各プロセッサエレメントと他のプロセッサエレメントとの間で必要となるデータ転送を解析して、転送対象／転送位置／転送先を指定するデータ転送情報を生成し、続いて、その生成したデータ転送情報を最適化する。
【００２８】
この最適化処理を実行すると、本発明のコンパイラ１０は、生成したループ分割情報に従って分割されるＤＯループを持つオブジェクトコードを生成するとともに、生成した最適化データ転送情報に従って作成されるデータ転送命令及びデータ受信命令を持つオブジェクトコードを生成する。
【００２９】
次に、具体例に従って、本発明のコンパイラ１０が実行する最適化処理について説明する。
図４に、ソースプログラムの一例を図示する。
【００３０】
このソースプログラムは、１０１個のデータ要素を持つ配列ａと、１００個のデータ要素を持つ配列ｂと、１０１個のデータ要素を持つ配列ｃと、１００個のデータ要素を持つ配列ｄとを定義して、先ず最初に、
ｂ（ｉ）＝ｓｑｒｔ（ａ（ｉ＋１））      ｉ＝１〜１００
に従って、データ要素ａ（ｉ＋１）の平方根で定義されるデータ要素ｂ（ｉ）を求めることで配列ｂを算出し、続いて、
ｃ（ｉ）＝ａ（ｉ＋１）＋ｂ（ｉ）        ｉ＝１〜１００
に従ってデータ要素ｃ（ｉ）を求めることで配列ｃを算出し、続いて、配列ｂを用いるサブルーチン「ｓｕｂ（ｂ）」を呼び出した後、それに続いて、
ｄ（ｉ）＝ｃｏｓ（ｃ（ｉ＋１））        ｉ＝１〜１００
に従って、データ要素ｃ（ｉ＋１）のコサイン関数値で定義されるデータ要素ｄ（ｉ）を求めることで配列ｄを算出していくプログラムである。
【００３１】
このようなソースプログラムをコンパイルする場合、分散メモリ型並列計算機が４台のプロセッサエレメントで構成されるときには、本発明のコンパイラ１０は、最適化処理に入ると、配列ａ／配列ｂ／配列ｃ／配列ｄについては分割しないようにしながら、配列ｂを求めるＤＯループと、配列ｃを求めるＤＯループと、配列ｄを求めるＤＯループについては、並列化が可能であることを解析して、それらのＤＯループを４台のプロセッサエレメントで並列処理すべく、「ｉ＝１〜２５」、「ｉ＝２６〜５０」、「ｉ＝５１〜７５」、「ｉ＝７６〜１００  」という添字のグループに分割する。
【００３２】
続いて、「ｉ＝１〜２５」を実行するプロセッサエレメントは、配列ｂの算出にあたって、自エレメントに展開される配列ａのデータ要素ａ（２）  〜ａ（２６）を使用し、配列ｃの算出にあたって、自エレメントに展開される配列ａのデータ要素ａ（２）  〜ａ（２６）と、自エレメントで算出した配列ｂのデータ要素ｂ（１）  〜（２５）とを使用し、配列ｄの算出にあたって、自エレメントで算出した配列ｃのデータ要素ｃ（２）  〜（２５）と、隣接プロセッサエレメントの算出した配列ｃのデータ要素ｃ（２６）とを使用するということを解析する。
【００３３】
また、「ｉ＝２６〜５０」を実行するプロセッサエレメントは、配列ｂの算出にあたって、自エレメントに展開される配列ａのデータ要素ａ（２７）〜ａ（５１）を使用し、配列ｃの算出にあたって、自エレメントに展開される配列ａのデータ要素ａ（２７）〜ａ（５１）と、自エレメントで算出した配列ｂのデータ要素ｂ（２６）〜（５０）とを使用し、配列ｄの算出にあたって、自エレメントで算出した配列ｃのデータ要素ｃ（２７）〜（５０）と、隣接プロセッサエレメントの算出した配列ｃのデータ要素ｃ（５１）とを使用するということを解析する。
【００３４】
また、「ｉ＝５１〜７５」を実行するプロセッサエレメントは、配列ｂの算出にあたって、自エレメントに展開される配列ａのデータ要素ａ（５２）〜ａ（７６）を使用し、配列ｃの算出にあたって、自エレメントに展開される配列ａのデータ要素ａ（５２）〜ａ（７６）と、自エレメントで算出した配列ｂのデータ要素ｂ（５１）〜（７５）とを使用し、配列ｄの算出にあたって、自エレメントで算出した配列ｃのデータ要素ｃ（５２）〜（７５）と、隣接プロセッサエレメントの算出した配列ｃのデータ要素ｃ（７６）とを使用するということを解析する。
【００３５】
また、「ｉ＝７６〜１００  」を実行するプロセッサエレメントは、配列ｂの算出にあたって、自エレメントに展開される配列ａのデータ要素ａ（７７）〜ａ（１０１）  を使用し、配列ｃの算出にあたって、自エレメントに展開される配列ａのデータ要素ａ（７７）〜ａ（１０１）  と、自エレメントで算出した配列ｂのデータ要素ｂ（７６）〜（１００）  とを使用し、配列ｄの算出にあたって、自エレメントで算出した配列ｃのデータ要素ｃ（７６）〜（１００）  と、自エレメントに展開される配列ｃのデータ要素ｃ（１０１）  の初期値とを使用するということを解析する。
【００３６】
そして、サブルーチン「ｓｕｂ（ｂ）」の実行前に、各プロセッサエレメントが配列ｂを持つ必要があることを解析して、その「ｓｕｂ（ｂ）」の前までに、各プロセッサエレメントで生成された配列ｂの配列部分を、他の全てのプロセッサエレメントに転送することを指示するデータ転送情報を生成する。なお、サブルーチンの他、ソースプログラムに入出力命令が記述されているときや、多重ＤＯループが記述されているときなどには、このように、各プロセッサエレメントで生成された配列部分を他の全てのプロセッサエレメントに転送していく必要が起こる。
【００３７】
更に、配列ｄの算出前に、「ｉ＝１〜２５」を実行するプロセッサエレメントが、「ｉ＝２６〜５０」を実行するプロセッサエレメントからデータ要素ｃ（２６）を受け取る必要があり、「ｉ＝２６〜５０」を実行するプロセッサエレメントが、「ｉ＝５１〜７５」を実行するプロセッサエレメントからデータ要素ｃ（５１）を受け取る必要があり、「ｉ＝５１〜７５」を実行するプロセッサエレメントが、「ｉ＝７６〜１００  」を実行するプロセッサエレメントからデータ要素ｃ（７６）を受け取る必要があることを解析して、その配列ｄの算出時点に、「ｉ＝２６〜５０」を実行するプロセッサエレメントの持つデータ要素ｃ（２６）を、「ｉ＝１〜２５」を実行するプロセッサエレメントに転送し、「ｉ＝５１〜７５」を実行するプロセッサエレメントの持つデータ要素ｃ（５１）を、「ｉ＝２６〜５０」を実行するプロセッサエレメントに転送し、「ｉ＝７６〜１００  」を実行するプロセッサエレメントの持つデータ要素ｃ（７６）を、「ｉ＝５１〜７５」を実行するプロセッサエレメントに転送することを指示するデータ転送情報を生成する。
【００３８】
本発明のコンパイラ１０が、ここで最適化処理を終了して、データ転送情報についてはこれ以上の最適化処理を実行しないときには、この最適化処理に従って生成されるオブジェクトコードが４台のプロセッサエレメントにローディングされることで、各プロセッサエレメントは、図５に示すようなデータ処理を実行する。
【００３９】
すなわち、ＰＥ１ないしＰＥ４で示される４台のプロセッサエレメントは、配列ａ／配列ｂ／配列ｃ／配列ｄのデータ要素の実体を図示しないデータファイルから読み込むことで、ソースプログラムの記述する配列宣言文の指すデータのコピーを展開する。
【００４０】
そして、コンパイラ１０の最適化処理で生成されたＤＯループの分割情報により、ＰＥ１のプロセッサエレメントは、並列実行処理に従いつつ、
ｂ（ｉ）＝ｓｑｒｔ（ａ（ｉ＋１））      ｉ＝１〜２５
に従って、データ要素ｂ（ｉ）を求め、
ｃ（ｉ）＝ａ（ｉ＋１）＋ｂ（ｉ）        ｉ＝１〜２５
に従ってデータ要素ｃ（ｉ）を求め、
ｄ（ｉ）＝ｃｏｓ（ｃ（ｉ＋１））        ｉ＝１〜２５
に従ってデータ要素ｄ（ｉ）を求める。
【００４１】
また、コンパイラ１０の最適化処理で生成されたＤＯループの分割情報により、ＰＥ２のプロセッサエレメントは、並列実行処理に従いつつ、
ｂ（ｉ）＝ｓｑｒｔ（ａ（ｉ＋１））      ｉ＝２６〜５０
に従って、データ要素ｂ（ｉ）を求め、
ｃ（ｉ）＝ａ（ｉ＋１）＋ｂ（ｉ）        ｉ＝２６〜５０
に従ってデータ要素ｃ（ｉ）を求め、
ｄ（ｉ）＝ｃｏｓ（ｃ（ｉ＋１））        ｉ＝２６〜５０
に従ってデータ要素ｄ（ｉ）を求める。
【００４２】
また、コンパイラ１０の最適化処理で生成されたＤＯループの分割情報により、ＰＥ３のプロセッサエレメントは、並列実行処理に従いつつ、
ｂ（ｉ）＝ｓｑｒｔ（ａ（ｉ＋１））      ｉ＝５１〜７５
に従って、データ要素ｂ（ｉ）を求め、
ｃ（ｉ）＝ａ（ｉ＋１）＋ｂ（ｉ）        ｉ＝５１〜７５
に従ってデータ要素ｃ（ｉ）を求め、
ｄ（ｉ）＝ｃｏｓ（ｃ（ｉ＋１））        ｉ＝５１〜７５
に従ってデータ要素ｄ（ｉ）を求める。
【００４３】
また、コンパイラ１０の最適化処理で生成されたＤＯループの分割情報により、ＰＥ４のプロセッサエレメントは、並列実行処理に従いつつ、
ｂ（ｉ）＝ｓｑｒｔ（ａ（ｉ＋１））      ｉ＝７６〜１００
に従って、データ要素ｂ（ｉ）を求め、
ｃ（ｉ）＝ａ（ｉ＋１）＋ｂ（ｉ）        ｉ＝７６〜１００
に従ってデータ要素ｃ（ｉ）を求め、
ｄ（ｉ）＝ｃｏｓ（ｃ（ｉ＋１））        ｉ＝７６〜１００
に従ってデータ要素ｄ（ｉ）を求める。
【００４４】
このとき、コンパイラ１０の最適化処理で生成されたデータ転送情報により、ＰＥ１のプロセッサエレメントは、図６上段に示すように、サブルーチン「ｓｕｂ（ｂ）」の実行に入る前に、自エレメントで算出した配列ｂのデータ要素ｂ（１）  〜ｂ（２５）を、ＰＥ２／ＰＥ３／ＰＥ４のプロセッサエレメントに転送し、ＰＥ２のプロセッサエレメントは、図６下段に示すように、サブルーチン「ｓｕｂ（ｂ）」の実行に入る前に、自エレメントで算出した配列ｂのデータ要素ｂ（２６）〜ｂ（５０）を、ＰＥ１／ＰＥ３／ＰＥ４のプロセッサエレメントに転送し、ＰＥ３のプロセッサエレメントは、図７上段に示すように、サブルーチン「ｓｕｂ（ｂ）」の実行に入る前に、自エレメントで算出した配列ｂのデータ要素ｂ（５１）〜ｂ（７５）を、ＰＥ１／ＰＥ２／ＰＥ４のプロセッサエレメントに転送し、ＰＥ４のプロセッサエレメントは、図７下段に示すように、サブルーチン「ｓｕｂ（ｂ）」の実行に入る前に、自エレメントで算出した配列ｂのデータ要素ｂ（７６）〜ｂ（１００）  を、ＰＥ１／ＰＥ２／ＰＥ３のプロセッサエレメントに転送していく。
【００４５】
そして、コンパイラ１０の最適化処理で生成されたデータ転送情報により、ＰＥ１のプロセッサエレメントは、ＰＥ２／ＰＥ３／ＰＥ４のプロセッサエレメントから、配列ｂのデータ要素ｂ（２６）〜ｂ（５０）と、配列ｂのデータ要素ｂ（５１）〜ｂ（７５）と、配列ｂのデータ要素ｂ（７６）〜ｂ（１００）  とを受け取ることを確認すると、サブルーチン「ｓｕｂ（ｂ）」の実行に入り、ＰＥ２のプロセッサエレメントは、ＰＥ１／ＰＥ３／ＰＥ４のプロセッサエレメントから、配列ｂのデータ要素ｂ（１）  〜ｂ（２５）と、配列ｂのデータ要素ｂ（５１）〜ｂ（７５）と、配列ｂのデータ要素ｂ（７６）〜ｂ（１００）  とを受け取ることを確認すると、サブルーチン「ｓｕｂ（ｂ）」の実行に入り、ＰＥ３のプロセッサエレメントは、ＰＥ１／ＰＥ２／ＰＥ４のプロセッサエレメントから、配列ｂのデータ要素ｂ（１）  〜ｂ（２５）と、配列ｂのデータ要素ｂ（２６）〜ｂ（５０）と、配列ｂのデータ要素ｂ（７６）〜ｂ（１００）  とを受け取ることを確認すると、サブルーチン「ｓｕｂ（ｂ）」の実行に入り、ＰＥ４のプロセッサエレメントは、ＰＥ１／ＰＥ２／ＰＥ３のプロセッサエレメントから、配列ｂのデータ要素ｂ（１）  〜ｂ（２５）と、配列ｂのデータ要素ｂ（２６）〜ｂ（５０）と、配列ｂのデータ要素ｂ（５１）〜ｂ（７５）とを受け取ることを確認すると、サブルーチン「ｓｕｂ（ｂ）」の実行に入っていく。
【００４６】
そして、コンパイラ１０の最適化処理で生成されたデータ転送情報により、ＰＥ２のプロセッサエレメントは、サブルーチン「ｓｕｂ（ｂ）」の実行が終了すると、図８上段に示すように、ＰＥ１のプロセッサエレメントが配列ｄの算出に入る前に、その算出で必要となる配列ｃのデータ要素ｃ（２６）を転送し、ＰＥ４のプロセッサエレメントは、サブルーチン「ｓｕｂ（ｂ）」の実行が終了すると、図８上段に示すように、ＰＥ３のプロセッサエレメントが配列ｄの算出に入る前に、その算出で必要となる配列ｃのデータ要素ｃ（７６）を転送し、ＰＥ３のプロセッサエレメントは、サブルーチン「ｓｕｂ（ｂ）」の実行が終了すると、図８下段に示すように、ＰＥ２のプロセッサエレメントが配列ｄの算出に入る前に、その算出で必要となる配列ｃのデータ要素ｃ（５１）を転送していく。
【００４７】
このようにして、本発明のコンパイラ１０では、分散メモリ型並列計算機において、手続き部分のみを自動的に並列化し、データについては、分散配置させずに全プロセッサエレメントがそのコピーを持つ構成を採って、必要に応じてデータを一致させつつ、必要なデータをやり取りする構成を採ることで、完全自動並列化を実現するものである。
【００４８】
この実施例では、配列ｄの算出で必要となる配列ｃの境界部分のデータ要素については、そのデータ要素のみをプロセッサエレメント間で転送していくという最適化されたデータ転送方法を用いる構成を開示した。この構成に従うと転送コストの削減を図ることができるが、このような最適化を行わずに、配列ｃの全データ要素を転送対象とするデータ転送方法を採ることも可能である。
【００４９】
また、分散メモリ型並列計算機がデータ転送処理と演算処理とを並列処理できる機能を持つ場合には、後方で使用されるデータについては、その値が確定した時点から転送開始に入るようにと転送位置を最適化することで、データ転送処理と演算処理とを重ね合わせてデータ転送処理を隠蔽することが可能である。
【００５０】
例えば、図４のソースプログラムをコンパイルする場合、図９に示すように、サブルーチン「ｓｕｂ（ｂ）」の実行時点で、その演算に必要となる配列ｂのデータ要素の転送を実行するのではなくて、配列ｂのデータ要素の値が確定した時点から転送処理に入るようにし、また、配列ｄの算出時点で、その算出に必要となる配列ｃのデータ要素の転送を実行するのではなくて、その配列ｃのデータ要素の値が確定した時点から転送処理に入るようにすることで、データ転送処理を隠蔽するのである。
【００５１】
この本発明のコンパイラ１０を用いることで、データ処理実行に必要となる全データを、各プロセッサエレメントのローカルメモリに展開し、データ処理実行に必要となる手続きを分割して、各プロセッサエレメントのローカルメモリに展開し、そして、各プロセッサエレメントが、自ローカルメモリに展開される手続きに従い、自ローカルメモリに展開されるデータを使ってデータ処理を実行するという分散メモリ型並列計算機上での新たなプログラム実行方法を実現できるようになる。
【００５２】
この新たなプログラム実行方法では、各プロセッサエレメントは、自ローカルメモリに展開されるデータのアクセス範囲を限定するよう処理する。そして、各プロセッサエレメントは、手続きの実行途中で、自ローカルメモリに展開されるデータを更新し、そのデータを、そのデータを必要とする他プロセッサエレメントに転送していくよう処理することになる。
【００５３】
なお、この新たなプログラム実行方法は、本発明のコンパイラ１０を用いることで実現できるものであるが、本発明のコンパイラ１０を用いなくても実現可能である。
【００５４】
【発明の効果】
以上説明したように、本発明のコンパイラでは、分散メモリ型並列計算機でデータ処理を実行する場合に、手続き部分のみを自動的に並列化し、データについては、分散配置させずに全プロセッサエレメントがそのコピーを持つ構成を採って、必要に応じてデータを一致させつつ、必要なデータをやり取りする構成を採る。
【００５５】
これにより、完全自動並列化を実現できるようになる。そして、プログラマのノウハウによらないで完全自動並列化を実現できるようになることから、当たり外れがなくなり、コンスタントな性能向上を期待できるようになる。そして、データを分散配置することから、並列化の対象となるループの範囲が拡大できるようになる。
【図面の簡単な説明】
【図１】本発明の原理構成図である。
【図２】本発明のコンパイラが実行する最適化処理の処理構成図である。
【図３】最適処理の詳細な処理フローである。
【図４】ソースプログラムの一例である。
【図５】本発明のコンパイル処理説明図である。
【図６】本発明のコンパイル処理説明図である。
【図７】本発明のコンパイル処理説明図である。
【図８】本発明のコンパイル処理説明図である。
【図９】本発明のコンパイル処理説明図である。
【図１０】分散メモリ型並列計算機の説明図である。
【図１１】メモリアーキテクチャの説明図である。
【符号の説明】
１    データ処理装置
１０  コンパイラ
１１  字句・構文解析部
１２  コード生成部
１３  最適化部
１４  制御部
１５  第１の解析部
１６  第２の解析部
１７  第３の解析部
【図１】
0003588394.tif 000002
【図２】
0003588394.tif 000003
【図３】
0003588394.tif 000004
【図４】
0003588394.tif 000005
【図５】
0003588394.tif 000006
【図６】
0003588394.tif 000007
【図７】
0003588394.tif 000008
【図８】
0003588394.tif 000009
【図９】
0003588394.tif 000010
【図１０】
0003588394.tif 000011
【図１１】
0003588394.tif 000012