(57)【要約】【課題】プログラムの大幅な書き換えを行うことなく、リンクドデータを扱うプログラムの並列化を実現する。【解決手段】分散メモリ並列計算機上でリンクドデータを扱うためのオブジェクトプログラムを生成するコンパイラ装置において、実際のデータを保持するノードである実ノードと、前記実際のデータは保持せずにリンク構造を保持するノードである仮想ノードとを生成し、前記実ノード及び前記仮想ノードを用いることにより、前記リンクドデータの前記分散メモリ並列計算機上での擬似的な分散配置を実現する。【選択図】図１
2010122954.tif 000002
【特許請求の範囲】
【請求項１】
分散メモリ並列計算機上でリンクドデータを扱うためのオブジェクトプログラムを生成するコンパイラ装置において、
実際のデータを保持するノードである実ノードと、前記実際のデータは保持せずにリンク構造を保持するノードである仮想ノードとを生成し、前記実ノード及び前記仮想ノードを用いることにより、前記リンクドデータの前記分散メモリ並列計算機上での擬似的な分散配置を実現することを特徴とするコンパイラ装置。
【請求項２】
請求項１に記載のコンパイラ装置において、
受け付けたソースプログラムの構文を解析することにより少なくとも、クラス名、分散対象リンクドデータのクラスであるか否か、メンバ名及び分散すべきメンバであるか否か、という情報を関連付けるテーブルであるクラス情報テーブルを生成する構文解析手段と、
前記実ノード及び前記仮ノードのクラスの基本クラスとなる、ベースノードのクラス宣言を生成するベースノード生成手段と、
前記クラス情報テーブルを参照し、分散対象となっているリンクドデータのクラスに対して、前記分散すべきメンバであるか否かの情報を用いて仮ノードの宣言をする仮ノード生成手段と、
前記クラス情報テーブルを参照し、分散対象となっているリンクドデータのクラスに対して、前記分散すべきメンバであるか否かの情報を用いて実ノードの宣言をする実ノード生成手段と、
前記クラス情報テーブルを参照し、前記実ノード及び前記仮ノードを、前記分散メモリ並列計算機の有する演算装置に割り付けるメモリ割付変形手段と、
関数呼出しの引数に現れる各分散メンバに関する情報を一時領域にコピーする文を生成し、前記一時領域を、全前記演算装置へブロードキャストする文を生成し、引数に現れる分散メンバを、対応する一時領域で置き換える関数呼出し変形手段と、
前記クラス情報テーブルを参照し、前記分散すべきメンバがアクセスされる各文に対して、通信コードおよびＩＦガードの生成を行うメンバアクセス変形手段と、
を備えることを特徴とするコンパイラ装置。
【請求項３】
請求項２に記載のコンパイラ装置において、前記メモリ割付変形手段は、前記割付けの対象のクラスが、前記分散対象リンクドデータのクラスである場合に、対応する仮ノードクラスのスコープ中のメンバ関数の返す値が、自らの演算装置のＩＤを保持するグローバル変数に一致すれば実ノードを、一致しなければ仮ノードを割付けることを特徴とするコンパイラ装置。
【請求項４】
請求項１乃至３の何れか１項に記載のコンパイラ装置において、ベースノードクラス内のオーナ決定関数をオーバーライドし、各リンクドノードのオーナを任意の方法で決定することができるようにメンバ関数を定義することを特徴とするコンパイラ装置。
【請求項５】
請求項１乃至４の何れか１項に記載のコンパイラ装置において、前記メモリ割付け変形手段は、実ノードの領域を毎回割付けるのではなく、予め「実ノードの配列」として割付けておいた領域の要素を順に割り当てるようにすることを特徴とするコンパイラ装置。
【請求項６】
分散メモリ並列計算機上でリンクドデータを扱うためのオブジェクトプログラムを生成する並列プログラム生成方法において、
実際のデータを保持するノードである実ノードと、前記実際のデータは保持せずにリンク構造を保持するノードである仮想ノードとを生成し、前記実ノード及び前記仮想ノードを用いることにより、前記リンクドデータの前記分散メモリ並列計算機上での擬似的な分散配置を実現することを特徴とする並列プログラム生成方法。
【請求項７】
請求項６に記載の並列プログラム生成方法において、
受け付けたソースプログラムの構文を解析することにより少なくとも、クラス名、分散対象リンクドデータのクラスであるか否か、メンバ名及び分散すべきメンバであるか否か、という情報を関連付けるテーブルであるクラス情報テーブルを生成する構文解析ステップと、
前記実ノード及び前記仮ノードのクラスの基本クラスとなる、ベースノードのクラス宣言を生成するベースノード生成ステップと、
前記クラス情報テーブルを参照し、分散対象となっているリンクドデータのクラスに対して、前記分散すべきメンバであるか否かの情報を用いて仮ノードの宣言をする仮ノード生成ステップと、
前記クラス情報テーブルを参照し、分散対象となっているリンクドデータのクラスに対して、前記分散すべきメンバであるか否かの情報を用いて実ノードの宣言をする実ノード生成ステップと、
前記クラス情報テーブルを参照し、前記実ノード及び前記仮ノードを、前記分散メモリ並列計算機の有する演算装置に割り付けるメモリ割付変形ステップと、
関数呼出しの引数に現れる各分散メンバに関する情報を一時領域にコピーする文を生成し、前記一時領域を、全前記演算装置へブロードキャストする文を生成し、引数に現れる分散メンバを、対応する一時領域で置き換える関数呼出し変形ステップと、
前記クラス情報テーブルを参照し、前記分散すべきメンバがアクセスされる各文に対して、通信コードおよびＩＦガードの生成を行うメンバアクセス変形ステップと、
を備えることを特徴とする並列プログラム生成方法。
【請求項８】
請求項７に記載の並列プログラム生成方法において、前記メモリ割付変形ステップにおいて、前記割付けの対象のクラスが、前記分散対象リンクドデータのクラスである場合に、対応する仮ノードクラスのスコープ中のメンバ関数の返す値が、自らの演算装置のＩＤを保持するグローバル変数に一致すれば実ノードを、一致しなければ仮ノードを割付けることを特徴とする並列プログラム生成方法。
【請求項９】
請求項６乃至８の何れか１項に記載の並列プログラム生成方法において、ベースノードクラス内のオーナ決定関数をオーバーライドし、各リンクドノードのオーナを任意の方法で決定することができるようにメンバ関数を定義することを特徴とする並列プログラム生成方法。
【請求項１０】
請求項６乃至９の何れか１項に記載の並列プログラム生成方法であって、前記メモリ割付け変形ステップにおいて、実ノードの領域を毎回割付けるのではなく、予め「実ノードの配列」として割付けておいた領域の要素を順に割り当てるようにすることを特徴とする並列プログラム生成方法。
【請求項１１】
分散メモリ並列計算機上でリンクドデータを扱うためのオブジェクトプログラムを生成するコンパイラ装置において、
実際のデータを保持するノードである実ノードと、前記実際のデータは保持せずにリンク構造を保持するノードである仮想ノードとを生成し、前記実ノード及び前記仮想ノードを用いることにより、前記リンクドデータの前記分散メモリ並列計算機上での擬似的な分散配置を実現するコンパイラ装置としてコンピュータを機能させることを特徴とする並列プログラム生成プログラム。
【請求項１２】
請求項１１に記載の並列プログラム生成プログラムにおいて、前記コンパイラ装置は、
受け付けたソースプログラムの構文を解析することにより少なくとも、クラス名、分散対象リンクドデータのクラスであるか否か、メンバ名及び分散すべきメンバであるか否か、という情報を関連付けるテーブルであるクラス情報テーブルを生成する構文解析手段と、
前記実ノード及び前記仮ノードのクラスの基本クラスとなる、ベースノードのクラス宣言を生成するベースノード生成手段と、
前記クラス情報テーブルを参照し、分散対象となっているリンクドデータのクラスに対して、前記分散すべきメンバであるか否かの情報を用いて仮ノードの宣言をする仮ノード生成手段と、
前記クラス情報テーブルを参照し、分散対象となっているリンクドデータのクラスに対して、前記分散すべきメンバであるか否かの情報を用いて実ノードの宣言をする実ノード生成手段と、
前記クラス情報テーブルを参照し、前記実ノード及び前記仮ノードを、前記分散メモリ並列計算機の有する演算装置に割り付けるメモリ割付変形手段と、
関数呼出しの引数に現れる各分散メンバに関する情報を一時領域にコピーする文を生成し、前記一時領域を、全前記演算装置へブロードキャストする文を生成し、引数に現れる分散メンバを、対応する一時領域で置き換える関数呼出し変形手段と、
前記クラス情報テーブルを参照し、前記分散すべきメンバがアクセスされる各文に対して、通信コードおよびＩＦガードの生成を行うメンバアクセス変形手段と、
を備えることを特徴とする並列プログラム生成プログラム。
【請求項１３】
請求項１２に記載の並列プログラム生成プログラムにおいて、前記メモリ割付変形手段は、前記割付けの対象のクラスが、前記分散対象リンクドデータのクラスである場合に、対応する仮ノードクラスのスコープ中のメンバ関数の返す値が、自らの演算装置のＩＤを保持するグローバル変数に一致すれば実ノードを、一致しなければ仮ノードを割付けることを特徴とする並列プログラム生成プログラム。
【請求項１４】
請求項１１乃至１３の何れか１項に記載の並列プログラム生成プログラムにおいて、前記コンパイラ装置は、ベースノードクラス内のオーナ決定関数をオーバーライドし、各リンクドノードのオーナを任意の方法で決定することができるようにメンバ関数を定義することを特徴とする並列プログラム生成プログラム。
【請求項１５】
請求項１１乃至１４の何れか１項に記載の並列プログラム生成プログラムにおいて、前記メモリ割付け変形手段は、実ノードの領域を毎回割付けるのではなく、予め「実ノードの配列」として割付けておいた領域の要素を順に割り当てるようにすることを特徴とする並列プログラム生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はプログラムの並列化に関し、より詳細には、コンパイラによるプログラムの並列化に関する。
【背景技術】
【０００２】
リンクドリスト、ツリー及びグラフ等の、リンクに基づくデータ構造(以下このようなデー構造からなるデータを、「リンクドデータ」と呼ぶ。)は、多くのプログラムの処理対象となっている。
【０００３】
通常、リンクドデータは、何らかのデータを保持する複数の「ノード」と、ノードとノードを接続する「リンク」から成る。そして、ほとんどの場合、リンクは、特定のオブジェクトのアドレスを保持する「ポインタ」として実現される。
【０００４】
他方、プログラムの扱うデータや処理が大規模化するにつれ、複数のＣＰＵによる「並列処理」を行うことが必要不可欠となってきている。
【０００５】
このような並列処理を実行するためのプログラムを生成するコンパイラの技術として、例えば特許文献１乃至３が挙げられる。これら、特許文献に記載の技術を用いることにより並列処理を行うプログラムを生成することができる。
【特許文献１】特開２０００−３４７８７９号公報
【特許文献２】特開平０７−０３６６８０号公報
【特許文献２】特許第３２４８４９１号公報
【非特許文献１】Jose M. Piquer and Christian Queinnec: Transpive: A distributed lisp system, La lettre du Transputer, no. 16, (Dec. 1992).
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ここで、上述のような並列処理を実現するにあたり、リンクドデータと並んで重要なデータ構造である「配列」を扱うプログラムは、ＨＰＦ（High Performance Fortran）に代表される並列言語を用いて容易に並列化することができる。しかし、それに対し、リンクドデータを扱うプログラムを並列化するにあたり上述のような技術では次のような問題が伴う。具体的には、リンクドデータを処理するプログラムを、以下の三種の並列計算機上で並列化する際には、それぞれ下に示すような問題が存在する。まず、その三種の概略を示す。
ａ）共有メモリ：扱える問題のサイズが限られる。
ｂ）分散メモリ：プログラムの大幅な書き換えが必要になる。
ｃ）分散共有メモリ：高い性能を得るのが難しい。
【０００７】
次に、上述の三種の並列計算機毎にそれぞれ、詳細に説明する。
【０００８】
まず、複数のＣＰＵが一つの主記憶を共有する「共有メモリ並列計算機」では、プログラムを並列化すること自体は比較的容易である。しかし、扱える問題のサイズ（リンクドデータの規模）が限られるという問題がある。
【０００９】
次に、それぞれ固有の主記憶を持つ複数のＣＰＵがインターコネクトにより接続された「分散メモリ並列計算機」では、問題サイズの制限は緩やかだが、プログラムの並列化が難しい。特に、ポインタが、異なるＣＰＵの主記憶上のアドレスを指すことは一般的には不可能である。そのため、分散メモリ並列計算機上でリンクドデータを分散配置するには、通常のポインタに依らない方法でリンクを表現する必要がある。そのような技術については、例えば非特許文献１に記載があるが、実現のためには、プログラムの大幅な書き換えが伴うという問題がある。
【００１０】
更に、分散メモリ並列計算機上に、ハードウェアまたはソフトウェアによって仮想的に共有メモリ環境を構築した「分散共有メモリ」を利用すると、容易な並列化と大きな問題サイズの両方を達成できる可能性はある。しかし、ハードウェアのサポートによる分散共有メモリを備える計算機は限られている。また、ソフトウェアによる分散共有メモリはオーバヘッドが大きく、実行性能の点で問題がある。これらの理由から、分散共有メモリを利用する並列化は、実用的とは言いがたい。
【００１１】
そこで、本発明はプログラムの大幅な書き換えを行うことなく、リンクドデータを扱うプログラムの並列化を実現することが可能な、コンパイラ装置、並列プログラム生成方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の第１の観点によれば、分散メモリ並列計算機上でリンクドデータを扱うためのオブジェクトプログラムを生成するコンパイラ装置において、実際のデータを保持するノードである実ノードと、前記実際のデータは保持せずにリンク構造を保持するノードである仮想ノードとを生成し、前記実ノード及び前記仮想ノードを用いることにより、前記リンクドデータの前記分散メモリ並列計算機上での擬似的な分散配置を実現することを特徴とするコンパイラ装置が提供される。
【００１３】
本発明の第２の観点によれば、分散メモリ並列計算機上でリンクドデータを扱うためのオブジェクトプログラムを生成する並列プログラム生成方法において、実際のデータを保持するノードである実ノードと、前記実際のデータは保持せずにリンク構造を保持するノードである仮想ノードとを生成し、前記実ノード及び前記仮想ノードを用いることにより、前記リンクドデータの前記分散メモリ並列計算機上での擬似的な分散配置を実現することを特徴とする並列プログラム生成方法が提供される。
【００１４】
本発明の第３の観点によれば、分散メモリ並列計算機上でリンクドデータを扱うためのオブジェクトプログラムを生成するコンパイラ装置において、実際のデータを保持するノードである実ノードと、前記実際のデータは保持せずにリンク構造を保持するノードである仮想ノードとを生成し、前記実ノード及び前記仮想ノードを用いることにより、前記リンクドデータの前記分散メモリ並列計算機上での擬似的な分散配置を実現するコンパイラ装置としてコンピュータを機能させることを特徴とする並列プログラム生成プログラムが提供される。
【発明の効果】
【００１５】
本発明によれば、プログラムの大幅な書き換えを行うことなく、リンクドデータを扱うプログラムの並列化を実現することが可能となる。
【発明を実施するための最良の形態】
【００１６】
次に、本発明の実施形態について図面を用いて詳細に説明する。
【００１７】
ここで、本発明の実施形態の概略は、実際にデータを保持する「実ノード」と、実際にはデータを保持せず、リンク構造を保持するために用いられる「仮ノード」の２種類のノードを用いることによって、分散メモリ並列計算機上で、リンクドデータの擬似的な分散配置を実現するというものである。
【００１８】
更に、本実施形態は、プログラマが簡単なディレクティブを逐次プログラムに挿入し、コンパイラがディレクティブの指示に従って並列化を行うことにより、プログラマの負担を軽減するというものである。
【００１９】
本発明の実施形態の基本的構成を図１に示す。
【００２０】
図１に示すように、本発明の実施形態であるコンパイラ２００は、ソースプログラム１００を入力される。そして、コンパイラ２００は、並列化されたオブジェクトプログラム３００を出力する。
【００２１】
ここで、ソースプログラム１００は、次のようなコンパイラディレクティブを含む。
・「#pragma distributed」
直後のクラスが分散対象であることを指示する。
・「#pragma not_dist」
分散対象のクラスのメンバのうち、分散しないもの（各プロセッサで複製を持つもの）を指示する。特に、非連続な領域（データ構造）を指すポインタであるようなメンバに対しては、必ずこの指定をしなければならない。ただし、当該クラス型の領域を指すポインタ（リンク）は、この指定をしない場合であっても、暗黙にnot_distディレクティブが指定されているものとみなされる。
・「#pragma pointee_size(n)」
分散対象のクラスのメンバのうち、not_distディレクティブを指定されておらず、かつポインタであるメンバに対し、その指示先の領域のサイズを指定する。
【００２２】
次に、コンパイラ２００について説明する。コンパイラ２００は、構文解析部２１０、
並列化部２２０、最適化部２３０、コード生成部２４０及びクラス情報テーブル２５０を有する。
【００２３】
構文解析部２１０は、ソースプログラム１００の構文解析を行い、クラス情報テーブル２５０を含む各種の情報テーブルを生成する。並列化部２２０は、必要に応じてプログラムの並列化を行う。最適化部２３０は、種々の最適化を適用する。コード生成部２４０は、オブジェクトプログラム３００を生成する。クラス情報テーブルは、クラス名や、メンバ情報等の関連付けを示すテーブルである。
【００２４】
更に、並列化部２２０は、ベースノード生成部２２１、仮ノード生成部２２２、実ノード生成部２２３、メモリ割付け変形部２２４、関数呼出し変形部２２５及びメンバアクセス変形部２２６を有する。
【００２５】
ベースノード生成部２２１は、実ノードおよび仮ノードのクラスの基本クラスとなる、ベースノードのクラス宣言を生成する。
【００２６】
仮ノード生成部２２２と実ノード生成部２２３は、並列化の対象とする当該リンクドデータのクラス宣言から、それぞれ仮ノード、実ノードのクラス宣言を生成する。
【００２７】
メモリ割付け変形部２２４は、並列化の対象とする当該リンクドデータに対するメモリ割付けの変形を行う。
【００２８】
関数呼出し変形部２２５は、並列化の対象とする当該リンクドデータのメンバが引数として現れる関数呼出しの変形を行う。
【００２９】
メンバアクセス変形部２２６は、並列化の対象とする当該リンクドデータのメンバに対するアクセスの変形を行う。
【００３０】
クラス情報テーブル２５０には、クラスに関する情報が記録される。特に、分散対象リンクドデータのクラス(すなわち、distributedディレクティブが指定されているクラス)のエントリでは、distributedフラグがＯＮに設定される。更に、分散すべきメンバ(すなわち、not_distディレクティブが指定されていないメンバ)のdist_dataフラグがＯＮに設定される。pointee_sizeディレクティブが指定されているメンバには、その値が記録される。クラス情報テーブル２５０の例は、図２に示す。
【００３１】
次に、図３及び図４のフローチャートを参照してコンパイラ２００の動作について説明する。
【００３２】
図５に示すリンクドリストを扱うC++プログラムを例に、本発明の実施形態の動作を説明する。
【００３３】
まず、コンパイラ２００にソースプログラム１００が入力される（ステップＳ４０１）。
【００３４】
次に、並列化部２２０の動作に先立ち、構文解析部２１０において、クラス情報テーブル２５０が生成される（ステップＳ４０３）。
【００３５】
（１）ベースノード生成部２２１
本実施形態におけるベースノード生成部２２１は、図６に示す「ベースノード」の宣言を追加する（ステップＳ４０５）。ベースノードは、
・オーナプロセッサを保持するメンバ「__owner」
・次に割付けられるノードのオーナプロセッサを決定する静的メンバ関数（以下、この関数をオーナ決定関数と呼ぶ。）「__nextOwner」
等を含む。
【００３６】
ここで、ＮＵＭは、プロセッサの台数を保持するグローバル変数とする。
【００３７】
「__nextOwner」は、呼ばれる度にプロセッサのＩＤをラウンドロビン方式で返す。
【００３８】
（２）仮ノード生成部２２２
クラス情報テーブル２５０でdistributedフラグがＯＮになっているクラスの各々に対して、次の条件に沿うように仮ノードの宣言を生成する（ステップＳ４０７）。なお、仮ノードの宣言の具体例を図７に示す。
・仮ノードのクラス名は、元のノードのクラス名に一致させる。
・ベースノードクラスを公開継承する。
・メンバおよびメンバ関数は、元のノードのクラス宣言におけるそれらのうち、クラス情報テーブル２５０においてdist_dataフラグがＯＦＦになっているメンバと、全てのメンバ関数とする。各メンバおよびメンバ関数のアクセス制限は、元ノードクラスに準ずるものとする。
【００３９】
元ノードクラスの各々のコンストラクタに対して、引数リストの末尾にint型引数を一つ追加したコンストラクタを定義する。追加されたint型引数を、コンストラクタ初期化子によって、ベースノードクラスのコンストラクタに渡す。コンストラクタ内の処理は元のコンストラクタに準ずる。なお、このコンストラクタの処理は必要に応じて、後続するメモリ割付け変形部２２４、関数呼出し変形部２２５、メンバアクセス変形部２２６において変形される。
【００４０】
デストラクタは元ノードクラスのデストラクタに準ずる。デストラクタも同様に、必要に応じて、後続するメモリ割付け変形部２２４、関数呼出し変形部２２５、メンバアクセス変形部２２６において変形される。
【００４１】
（３）実ノード生成部２２３
クラス情報テーブル２５０でdistributedフラグがＯＮになっている各クラスに対して、次の条件に沿うように実ノードの宣言を生成する（ステップＳ４０９）。なお、実ノードの宣言の具体例を図８に示す。
・実ノードのクラス名は、元のノードのクラス名の先頭に「__Substance_」を付加したものとする。
・仮ノードクラスを公開継承する。さらに、仮ノードクラスをフレンドクラスとする。
・メンバは、元のノードのクラス宣言におけるそれらのうち、クラス情報テーブル２５０においてdist_dataフラグがＯＮになっているものとする。コンストラクタ以外のメンバ関数は定義しない。各メンバのアクセス制限は、元ノードクラスに準ずる。
・元ノードクラスの各々のコンストラクタに対して、引数リストの末尾にint型引数を一つ追加したコンストラクタを定義する。追加されたint型引数を、コンストラクタ初期化子によって、仮ノードクラスのコンストラクタに渡す。コンストラクタ内部は空とする。
・デストラクタは定義しない。
【００４２】
（４）メモリ割付け変形部２２４
リンクドデータに対するメモリ割付け処理（ｎｅｗ演算子)の変形を行う（ステップＳ４１１）。具体的には、クラス情報テーブル２５０において、割付けの対象のクラスのdistributedフラグがＯＮになっている場合に、対応する仮ノードクラスのスコープ中のメンバ関数「__nextOwner」の返す値がＭＥ（自プロセッサのＩＤを保持するグローバル変数)に一致すれば実ノードを、一致しなければ仮ノードを割付ける。この割付は、ｉｆ構文を生成することにより行う。加えて、「__nextOwner」が返した値を、初期化子リストの末尾に付加する。これにより、各リンクドノードのオーナプロセッサは、割付けられた順にラウンドロビン方式で決定されることになる。メモリ割付け処理を含む、図５の元ノードクラスのメンバ関数func1は図９のように変形される。
【００４３】
（５）関数呼出し変形部２２５
関数呼出しの引数に現れる各分散メンバに対して、次の処理を行う（ステップＳ４１３）。
・処理対象となる当該分散メンバを一時領域にコピーする文を生成する。ただし、当該分散メンバがポインタ値をとる場合は、その指示先の領域をコピーの対象とする。特に、クラス情報テーブル２５０において当該分散メンバのpointee_sizeカラムに値が設定されている場合には、そのサイズの領域をコピーの対象とする。さらに、当該分散メンバのオーナプロセッサのみが以上の処理を実行するように、ＩＦガードを生成する。
・一時領域を、全プロセッサへブロードキャストする文を生成する。
・引数に現れる分散メンバを、対応する一時領域(当該分散メンバがポインタ値をとる場合、その先頭アドレス)で置き換える。
・当該分散メンバがポインタ値をとる場合のみ、その指示先の領域を当該分散メンバにコピーする文を生成する。特に、クラス情報テーブル２５０において当該分散メンバのpointee_sizeカラムに値が設定されている場合には、そのサイズの領域をコピーの対象とする。さらに、当該分散メンバのオーナプロセッサのみが以上の処理を実行するように、ＩＦガードを生成する。
【００４４】
図１０は、元ノードクラスのメンバ関数func3に、関数呼出し変形部２２５による変形を適用したコードである。
【００４５】
図１０の中に現れる関数Bcastは、第一引数を先頭アドレスとする、第三引数で指定されたサイズの領域を、第二引数で指定されたプロセッサからブロードキャストする関数である。ＭＰＩライブラリのMPI_Bcastなどによって実現できる。
【００４６】
（６）メンバアクセス変形部２２６
クラス情報テーブル２５０でdist_dataフラグがＯＮになっているメンバ(分散メンバ)がアクセスされる各文に対して、通信コードおよびＩＦガードの生成を行う。具体的には、以下の処理を行う（ステップＳ４１５）。
【００４７】
（６−１）当該文を実行するプロセッサ(実行プロセッサ)を決定する。通常、その文において定義されるデータのオーナプロセッサを実行プロセッサとして選ぶ。ただし、定義されるデータが、分散対象のリンクドデータでない場合、全プロセッサが実行プロセッサとなる。以下、実行プロセッサが単一である場合と実行プロセッサが全プロセッサである場合とで分けて説明する（ステップＳ４１７）。
【００４８】
（６−２ａ）実行プロセッサが単一である場合（ステップＳ４１７においてＹＥＳ）
実行プロセッサのみが当該文を実行するように、ＩＦガードを生成する（ステップＳ５０１）。
【００４９】
当該文で参照される各分散メンバに対して、次の処理を行う。
【００５０】
当該分散メンバを実行プロセッサへ送信する文を生成する（ステップＳ５０３）。ただし、当該分散メンバがポインタ値をとる場合、その指示先の領域を送信の対象とする。特に、クラス情報テーブル２５０において当該分散メンバのpointee_sizeカラムに値が設定されている場合には、そのサイズの領域を送信の対象とする。さらに、当該分散メンバのオーナプロセッサのみが以上の処理を実行するように、ＩＦガードを生成する。
【００５１】
当該分散メンバのオーナプロセッサから一時領域に受信する文を、当該文の直前に生成する（ステップＳ５０５）。
【００５２】
当該文に現れる分散メンバを、対応する一時領域(当該分散メンバがポインタ値をとる場合、その先頭アドレス)で置き換える（ステップＳ５０７）。
【００５３】
（６−２ｂ）実行プロセッサが全プロセッサである場合（ステップＳ４１７においてＮＯ）
当該文で参照される各分散メンバに対して、次の処理を行う。
【００５４】
当該分散メンバを一時領域にコピーする文を生成する（ステップＳ５０９）。ただし、当該分散メンバがポインタ値をとる場合、その指示先の領域をコピーの対象とする。特に、クラス情報テーブル２５０において当該分散メンバのpointee_sizeカラムに値が設定されている場合には、そのサイズの領域をコピーの対象とする。さらに、当該分散メンバのオーナプロセッサのみが以上の処理を実行するように、ＩＦガードを生成する。
【００５５】
一時領域を、全プロセッサへブロードキャストする文を生成する（ステップＳ５１１）。
【００５６】
当該文に現れる分散メンバを、対応する一時領域(当該分散メンバがポインタ値をとる場合、その先頭アドレス)で置き換える（ステップＳ５１３）。
【００５７】
図１１は、元ノードクラスのメンバ関数func2にメンバアクセス変形部２２６による変形を適用したコードであり、分散メンバがポインタ値をとらない場合の例である。図１２は、元ノードクラスのメンバ関数func3にメンバアクセス変形部２２６による変形を適用したコードであり、分散メンバがポインタ値をとる場合の例である。
【００５８】
図１１および図１２の中に現れる関数Isendは、第一引数を先頭アドレスとする、第三引数で指定されたサイズの領域を、第二引数で指定されたプロセッサへ、ノンブロッキングなやり方で送信する関数である。ＭＰＩライブラリのMPI_Isendなどによって実現できる。同じくRecvは、第一引数を先頭アドレスとする、第三引数で指定されたサイズの領域を、第二引数で指定されたプロセッサから受信する関数である。ＭＰＩライブラリのMPI_Recvなどによって実現できる。
【００５９】
次に、以上説明した本実施形態の変形例について説明する。
【００６０】
［１］ユーザ定義オーナ決定関数
distributedディレクティブが指定されているクラス内で「static int __nextOwner(void)」というシグネチャを持つメンバ関数を定義することにより、ベースノードクラス内のオーナ決定関数をオーバーライドし、各リンクドノードのオーナを任意の方法で決定することができる。
【００６１】
特に、互いに疎なリンクドデータであっても、ノードのクラス型が同じあれば同一のオーナ決定関数が使用されてしまう(同じ規則に基づいてオーナが決定される)ことを避けたい場合には、特別なオーナ決定関数をユーザが定義する必要がある。
【００６２】
［２］データ並列
メモリ割付け変形部２２４において、実ノードの領域を毎回割付けるのではなく、あらかじめ「実ノードの配列」として割付けておいた領域の要素を順に割り当てるようにする。
【００６３】
これにより、あるプロセッサにおける実ノードの領域は、連続した配列の要素として存在することになる。したがって、各プロセッサにおいて、自分がオーナであるノードだけを、他プロセッサとは独立して並列に処理したいとき、リンク構造の走査ではなく、通常のforループによる配列処理として実現することが可能になる。
【００６４】
［３］他言語における実装
本発明の適用範囲は、C++言語に限られるものではない。オブジェクト指向型言語であれば、上述した実施形態とほぼ同じ方法で実装することができる。Fortran 2003より古いFortranなどの、オブジェクト指向の機能を持たない言語では、実ノードと仮ノードを継承により実現することはできないが、分散メンバを全てポインタとして表現し、オーナプロセッサでのみメモリを割付けるようにすることで、ほぼ等価な機能を実現できる。
【００６５】
［４］ローカルブロック
第一の実施の形態におけるソースプログラム１００が、次のようなディレクティブを含むことを許す。
・「#pragma local(nd) { ... }」
指定したノードndのオーナプロセッサが、ブロック（以下、このブロックをローカルブロックと呼ぶ。）内の各文を、他プロセッサの動作とは独立して実行することを指示する。
・「#pragma local_func」
ローカルブロック内から呼ばれる関数に指定し、直後の関数(以下、この関数をローカル関数と呼ぶ。)内の各文を、他プロセッサの動作とは独立して実行することを指示する。
【００６６】
メモリ割付け変形部２２４, 関数呼出し変形部２２５およびメンバアクセス変形部２２６は、ローカルブロック内およびローカル関数内の各文を変形の対象としない。ただし、メンバアクセス変形部２２６は、ローカルブロックを囲む位置に、指定したノードのオーナプロセッサのみがブロック内の文を実行するようにＩＦガードを生成する。
【００６７】
ローカルブロックは、ブロック内で、指定されたオーナプロセッサ以外のプロセッサが保持するデータをアクセスせず、かつ、ブロック内で定義されるデータをオーナプロセッサ以外のプロセッサがアクセスしない場合にのみ指定することができ、より大きい粒度の並列処理を可能とする。特に、ローカルブロック内で、新たにリンクドノードを割付けることにより、他のプロセッサからは参照されない「ローカルな」部分構造を扱うことが可能になる。なお、ローカルな部分構造としては、例えばサブリスト、サブツリー及びサブグラフが挙げられる。
【００６８】
以上説明した本発明の実施形態は、リンクドデータを扱うプログラムの並列化に関し、以下のような効果を奏する。
【００６９】
第１の効果として、分散メモリ並列計算機上での並列実行が可能となる。なぜならば、
実ノードと仮ノードの２種類のノードを用いることにより、分散メモリ並列計算機上で、リンクドデータの擬似的な分散配置を実現できるからである。
【００７０】
第２の効果として、プログラマの負担が小さいことが挙げられる。なぜならば、逐次プログラムに簡単なディレクティブを挿入するだけでコンパイラによる並列化が行われるからである。
【００７１】
第３の効果は、ＭＰＩなどのメッセージパッシングライブラリを除き、外部の特別な仕組みを必要としないことである。なぜならば、各ノードが保持するオーナプロセッサの情報に基づき、必要な通信をコンパイラが検出・生成するからである。
【００７２】
なお、本発明の実施形態であるコンパイラは、ハードウェア、ソフトウェア又はこれらの組合せにより実現することができる。
【図面の簡単な説明】
【００７３】
【図１】本発明の実施形態の基本的構成を表す図である。
【図２】本発明の実施形態のクラス情報テーブル２５０の例を示す図である。
【図３】本発明の実施形態の基本的動作を表すフローチャートである（１／２）。
【図４】本発明の実施形態の基本的動作を表すフローチャートである（２／２）。
【図５】本発明の実施形態のリンクドリストを扱うC++プログラムの例を示す図である。
【図６】本発明の実施形態の「ベースノード」の宣言について示す図である。
【図７】本発明の実施形態の「仮ノード」の宣言について示す図である。
【図８】本発明の実施形態の「実ノード」の宣言について示す図である。
【図９】本発明の実施形態による変形後のメンバ関数func1を示す図である。
【図１０】本発明の実施形態による変形後のメンバ関数func3を示す図である。
【図１１】本発明の実施形態による分散メンバがポインタ値をとらない場合の、変形後のメンバ関数func2を示す図である。
【図１２】本発明の実施形態による分散メンバがポインタ値をとる場合の、変形後のメンバ関数func2を示す図である。
【符号の説明】
【００７４】
１００  ソースプログラム
２００  コンパイラ
２１０  構文解析部
２２０  並列化部
２２１  ベースノード生成部
２２２  仮ノード生成部
２２３  実ノード生成部
２２４  メモリ割付け変形部
２２５  関数呼出し変形部
２２６  メンバアクセス変形部
２３０  最適化部
２４０  コード生成部
２５０  クラス情報テーブル
３００  オブジェクトプログラム
【図１】
2010122954.tif 000003
【図２】
2010122954.tif 000004
【図３】
2010122954.tif 000005
【図４】
2010122954.tif 000006
【図５】
2010122954.tif 000007
【図６】
2010122954.tif 000008
【図７】
2010122954.tif 000009
【図８】
2010122954.tif 000010
【図９】
2010122954.tif 000011
【図１０】
2010122954.tif 000012
【図１１】
2010122954.tif 000013
【図１２】
2010122954.tif 000014