(57)【特許請求の範囲】
【請求項１】
第１のスレッドを実行する第１の演算部と、
第２のスレッドを実行する第２の演算部と、
前記第１のスレッドに対応する第１の個別領域と、前記第２のスレッドに対応する第２の個別領域と、共有領域とを含む記憶部とを有し、
前記第１の演算部は、第１のデータを前記第１の個別領域に格納し、また、前記第１のデータへのアクセスを可能とするアドレス情報を前記共有領域に格納し、
前記第２の演算部は、第２のデータを前記第２の個別領域に格納し、前記共有領域に格納された前記アドレス情報に基づいて前記第１のデータにアクセスし、前記第１のデータおよび前記第２のデータに応じた第３のデータを生成する、
並列計算装置。
【請求項２】
前記第１の演算部は、少なくとも前記第２の演算部が前記第１のデータにアクセスするまで前記第１の個別領域から前記第１のデータを消去しないように、前記第１のスレッドと前記第２のスレッドとを同期させる、
請求項１記載の並列計算装置。
【請求項３】
前記第２の演算部は、第４のデータを前記第２の個別領域に格納し、また、前記第４のデータへのアクセスを可能とする他のアドレス情報を前記共有領域に格納し、
前記第１の演算部は、第５のデータを前記第１の個別領域に格納し、前記共有領域に格納された前記他のアドレス情報に基づいて前記第４のデータにアクセスし、前記第４のデータおよび前記第５のデータに応じた第６のデータを生成する、
請求項１または２記載の並列計算装置。
【請求項４】
前記第１の演算部および前記第２の演算部は、それぞれキャッシュメモリを有し、
前記アドレス情報と前記他のアドレス情報とは、前記共有領域において前記キャッシュメモリのキャッシュラインサイズに応じた距離だけ離して格納される、
請求項３記載の並列計算装置。
【請求項５】
第１のデータを生成することを示す第１のコードを記憶する記憶部と、
前記第１のコードを、第２のデータを生成する第１のスレッドと、第３のデータを生成し前記第２のデータと前記第３のデータとに基づいて前記第１のデータを生成する第２のスレッドとを起動することを示す第２のコードに変換する変換部とを有し、
前記第２のコードは、前記第１のスレッドから前記第１のスレッドに対応する第１の個別領域に前記第２のデータを格納すると共に、前記第２のスレッドから前記第２のスレッドに対応する第２の個別領域に前記第３のデータを格納する第１の命令を含み、
前記第２のコードは、前記第１のスレッドから共有領域に、前記第２のデータへのアクセスを可能とするアドレス情報を格納する第２の命令を含み、
前記第２のコードは、前記共有領域に格納された前記アドレス情報に基づいて前記第２のスレッドから前記第２のデータにアクセスする第３の命令を含む、
コンパイル装置。
【請求項６】
第１の演算部と第２の演算部と記憶部とを有する装置が行う並列処理方法であって、
前記第１の演算部を用いて第１のスレッドを起動し、
前記第２の演算部を用いて第２のスレッドを起動し、
前記第１の演算部から、前記記憶部に含まれる前記第１のスレッドに対応する第１の個別領域に第１のデータを格納し、また、前記記憶部に含まれる共有領域に前記第１のデータへのアクセスを可能とするアドレス情報を格納し、
前記第２の演算部から、前記記憶部に含まれる前記第２のスレッドに対応する第２の個別領域に第２のデータを格納し、
前記共有領域に格納された前記アドレス情報に基づいて前記第２の演算部から前記第１のデータにアクセスし、前記第２の演算部を用いて前記第１のデータおよび前記第２のデータに応じた第３のデータを生成する、
並列処理方法。
【請求項７】
コンピュータが行うコンパイル方法であって、
第１のデータを生成することを示す第１のコードを取得し、
前記第１のコードを、第２のデータを生成する第１のスレッドと、第３のデータを生成し前記第２のデータと前記第３のデータとに基づいて前記第１のデータを生成する第２のスレッドとを起動することを示す第２のコードに変換し、
前記第２のコードは、前記第１のスレッドから前記第１のスレッドに対応する第１の個別領域に前記第２のデータを格納すると共に、前記第２のスレッドから前記第２のスレッドに対応する第２の個別領域に前記第３のデータを格納する第１の命令を含み、
前記第２のコードは、前記第１のスレッドから共有領域に、前記第２のデータへのアクセスを可能とするアドレス情報を格納する第２の命令を含み、
前記第２のコードは、前記共有領域に格納された前記アドレス情報に基づいて前記第２のスレッドから前記第２のデータにアクセスする第３の命令を含む、
コンパイル方法。
【請求項８】
第１の演算部と第２の演算部と記憶部とを有するコンピュータに、
前記第１の演算部を用いて第１のスレッドを起動し、
前記第２の演算部を用いて第２のスレッドを起動し、
前記第１の演算部から、前記記憶部に含まれる前記第１のスレッドに対応する第１の個別領域に第１のデータを格納し、また、前記記憶部に含まれる共有領域に前記第１のデータへのアクセスを可能とするアドレス情報を格納し、
前記第２の演算部から、前記記憶部に含まれる前記第２のスレッドに対応する第２の個別領域に第２のデータを格納し、
前記共有領域に格納された前記アドレス情報に基づいて前記第２の演算部から前記第１のデータにアクセスし、前記第２の演算部を用いて前記第１のデータおよび前記第２のデータに応じた第３のデータを生成する、
処理を実行させる並列処理プログラム。
【請求項９】
コンピュータに、
第１のデータを生成することを示す第１のコードを取得し、
前記第１のコードを、第２のデータを生成する第１のスレッドと、第３のデータを生成し前記第２のデータと前記第３のデータとに基づいて前記第１のデータを生成する第２のスレッドとを起動することを示す第２のコードに変換する処理を実行させ、
前記第２のコードは、前記第１のスレッドから前記第１のスレッドに対応する第１の個別領域に前記第２のデータを格納すると共に、前記第２のスレッドから前記第２のスレッドに対応する第２の個別領域に前記第３のデータを格納する第１の命令を含み、
前記第２のコードは、前記第１のスレッドから共有領域に、前記第２のデータへのアクセスを可能とするアドレス情報を格納する第２の命令を含み、
前記第２のコードは、前記共有領域に格納された前記アドレス情報に基づいて前記第２のスレッドから前記第２のデータにアクセスする第３の命令を含む、
コンパイルプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は並列計算装置、コンパイル装置、並列処理方法、コンパイル方法、並列処理プログラムおよびコンパイルプログラムに関する。
【背景技術】
【０００２】
複数のプロセッサ（プロセッサコアと呼ばれるものを含む）を用いて複数のスレッドを並列に実行することができる並列計算装置が使用されることがある。並列計算装置を用いた並列処理の１つとして、異なる入力データに対する同種の演算を異なるスレッドで並列に実行することで、複数のスレッドそれぞれで中間データを生成し、複数のスレッドの中間データを集計して結果データを得る処理がある。上記の並列処理はリダクション処理と呼ばれることがある。並列計算装置に実行させるオブジェクトコードを生成するコンパイラの中には、並列処理用に作成されていないソースコードから、最適化を通じて、リダクション処理を行うオブジェクトコードを生成するものもある。
【０００３】
なお、複数のプロセッサと共有メモリとを用いて複数のスレッドを並列に実行させるスケジューリング方法が提案されている。提案のスケジューリング方法では、複数のスレッドを同期させる同期機構として、セマフォ、メッセージキュー、メッセージバッファ、イベントフラグ、バリア、ミューテックスなどを用いることができる。これら複数の種類の同期機構は、同期するスレッドのクラスに応じて使い分けられる。
【０００４】
また、共有メモリ型並列計算装置で実行可能なオブジェクトコードを生成するコンパイル装置が提案されている。提案のコンパイル装置は、ループ内の処理を複数のスレッドを用いて並列化するか否かが、実行時に動的に選択されるようなオブジェクトコードを生成する。生成されるオブジェクトコードは、ループ内の処理１回当たりの命令サイクル数と所定の並列化オーバヘッド情報とに基づいて、実行効率の向上が期待できるループ回数の閾値を算出する。オブジェクトコードは、実行時に決まるループ回数が閾値より大きい場合はループ内の処理を並列実行し、そうでない場合は逐次実行する。
【０００５】
また、並列にスレッドを実行可能な複数のコアと共有メモリとを有し、共有メモリ内の同じ記憶領域へのアクセスは排他的に行われる演算処理装置が提案されている。提案の演算処理装置は、同じ記憶領域のデータを更新しようとする２以上のスレッドがある場合、共有メモリにアクセスする前にそれら２以上のスレッドの間でリダクション処理を行わせる。リダクション処理では、各スレッドで生成された中間データが集計される。これにより、共有メモリの同じ記憶領域に対する排他的アクセスを減らすことができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００５−４３９５９号公報
【特許文献２】特開２００７−１０８８３８号公報
【特許文献３】特開２０１４−１０６７１５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
複数のスレッドそれぞれが生成した中間データは、例えば、当該スレッドに対して割り当てられるメモリ上の個別領域（例えば、スタック領域）に格納される。それら複数のスレッドの中間データを集計する第１の方法として、メモリ上の共有領域に結果データを格納する領域を確保し、各スレッドが当該スレッドの中間データを共有領域の結果データに反映させる方法が考えられる。しかし、第１の方法では、複数のスレッドからの結果データへのアクセスを排他的に行うことになり、排他制御のオーバヘッドが問題となる。
【０００８】
一方、複数のスレッドの中間データを集計する第２の方法として、各スレッドが当該スレッドの中間データを共有領域に格納し、何れかのスレッドが代表して複数のスレッドの中間データを集計する方法も考えられる。しかし、第２の方法では、結果データを格納する領域に加えて、中間データを格納する領域を共有領域に確保することになる。個別領域は各スレッドが他のスレッドを考慮せずに使用できるのに対し、共有領域は複数のスレッドによって共有されるためオペレーティングシステム（ＯＳ：Operating System）などの制御ソフトウェアによって割り当てが管理され得る。このため、中間データを格納する領域を確保するオーバヘッドが問題となる。特に、中間データが可変長配列などの可変長データである場合、動的に領域を確保するオーバヘッドが問題となる。
【０００９】
１つの側面では、複数のスレッドの中間データの集計を高速化できる並列計算装置、並列処理方法および並列処理プログラムを提供することを目的とする。また、１つの側面は、複数のスレッドの中間データの集計を高速化したコードを生成できるコンパイル装置、コンパイル方法およびコンパイルプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
１つの態様では、第１のスレッドを実行する第１の演算部と、第２のスレッドを実行する第２の演算部と、第１のスレッドに対応する第１の個別領域と、第２のスレッドに対応する第２の個別領域と、共有領域とを含む記憶部とを有する並列計算装置が提供される。第１の演算部は、第１のデータを第１の個別領域に格納し、また、第１のデータへのアクセスを可能とするアドレス情報を共有領域に格納する。第２の演算部は、第２のデータを第２の個別領域に格納し、共有領域に格納されたアドレス情報に基づいて第１のデータにアクセスし、第１のデータおよび第２のデータに応じた第３のデータを生成する。
【００１１】
また、１つの態様では、第１の演算部と第２の演算部と記憶部とを有する装置が行う並列処理方法が提供される。また、１つの態様では、第１の演算部と第２の演算部と記憶部とを有するコンピュータに実行させる並列処理プログラムが提供される。
【００１２】
また、１つの態様では、第１のデータを生成することを示す第１のコードを記憶する記憶部と、第１のコードを、第２のデータを生成する第１のスレッドと、第３のデータを生成し第２のデータと第３のデータとに基づいて第１のデータを生成する第２のスレッドとを起動することを示す第２のコードに変換する変換部とを有するコンパイル装置が提供される。第２のコードは、第１のスレッドから第１のスレッドに対応する第１の個別領域に第２のデータを格納すると共に、第２のスレッドから第２のスレッドに対応する第２の個別領域に第３のデータを格納する第１の命令を含む。第２のコードは、第１のスレッドから共有領域に、第２のデータへのアクセスを可能とするアドレス情報を格納する第２の命令を含む。第２のコードは、共有領域に格納されたアドレス情報に基づいて第２のスレッドから第２のデータにアクセスする第３の命令を含む。
【００１３】
また、１つの態様では、コンピュータが行うコンパイル方法が提供される。また、１つの態様では、コンピュータに実行させるコンパイルプログラムが提供される。
【発明の効果】
【００１４】
１つの側面では、複数のスレッドの中間データの集計を高速化できる。
【図面の簡単な説明】
【００１５】
【図１】第１の実施の形態の並列計算装置を示す図である。
【図２】第２の実施の形態のコンパイル装置を示す図である。
【図３】第３の実施の形態の情報処理システムを示す図である。
【図４】並列計算装置のハードウェア例を示すブロック図である。
【図５】コンパイル装置のハードウェア例を示すブロック図である。
【図６】並列化前の配列演算の例を示す図である。
【図７】並列化前のプログラム例を示す図である。
【図８】第１のリダクション処理の例を示す図である。
【図９】並列化後の第１のプログラム例を示す図である。
【図１０】第１のリダクション処理のタイミング例を示す図である。
【図１１】第２のリダクション処理の例を示す図である。
【図１２】並列化後の第２のプログラム例を示す図である。
【図１３】第２のリダクション処理のタイミング例を示す図である。
【図１４】並列計算装置とコンパイル装置の機能例を示すブロック図である。
【図１５】リダクション処理の手順例を示すフローチャートである。
【図１６】コンパイルの手順例を示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態を説明する。
【００１７】
図１は、第１の実施の形態の並列計算装置を示す図である。
第１の実施の形態の並列計算装置１０は、複数のスレッドを並列に実行できる計算装置である。並列計算装置１０は、ユーザが操作するクライアントコンピュータでもよいし、クライアントコンピュータからアクセスされるサーバコンピュータでもよい。
【００１８】
並列計算装置１０は、演算部１１，１２および記憶部１３を有する。演算部１１，１２は、例えば、ＣＰＵ（Central Processing Unit）やＣＰＵコアなどのプロセッサである。演算部１１，１２は、例えば、記憶部１３などのメモリに記憶されたプログラムを実行する。実行されるプログラムには、並列処理プログラムが含まれる。記憶部１３は、例えば、ＲＡＭ（Random Access Memory）などの揮発性の半導体メモリである。
【００１９】
第１の実施の形態では、演算部１１はスレッド１４ａを実行する。演算部１２はスレッド１４ｂを実行する。記憶部１３は、個別領域１３ａ，１３ｂおよび共有領域１３ｃを含む。個別領域１３ａは、スレッド１４ａに対応する領域であり、例えば、スレッド１４ａに対して割り当てられるスタック領域である。個別領域１３ｂは、スレッド１４ｂに対応する領域であり、例えば、スレッド１４ｂに対して割り当てられるスレッド領域である。共有領域１３ｃは、スレッド１４ａ，１４ｂから共通に使用できる。
【００２０】
スレッド１４ａは、そのアドレス空間に基づいて個別領域１３ａを使用する。スレッド１４ｂは、スレッド１４ａから独立したアドレス空間に基づいて個別領域１３ｂを使用する。スレッド１４ａはスレッド１４ｂを考慮せずに個別領域１３ａを使用でき、スレッド１４ｂはスレッド１４ａを考慮せずに個別領域１３ｂを使用できる。よって、個別領域１３ａ，１３ｂに動的に領域を確保するコストは比較的小さい。一方、共有領域１３ｃは、スレッド１４ａ，１４ｂから共通に使用されるため、ＯＳなどの制御ソフトウェアによって管理される。よって、共有領域１３ｃに動的に領域を確保するコストは比較的大きい。
【００２１】
スレッド１４ａは、中間データとしてデータ１５ａ（第１のデータ）を生成し、個別領域１３ａに格納する。スレッド１４ｂは、中間データとしてデータ１５ｂ（第２のデータ）を生成し、個別領域１３ｂに格納する。データ１５ａ，１５ｂの生成は並列に実行され得る。データ１５ａとデータ１５ｂとを集計することで、結果データとしてデータ１５ｄ（第３のデータ）が生成される。集計の演算としては、加算・減算・乗算などの算術演算、論理積・論理和などの論理演算、最大値選択・最小値選択などの選択演算などが挙げられる。データ１５ｄは、例えば、共有領域１３ｃに格納される。
【００２２】
ここで、個別領域１３ａに格納されたデータ１５ａは、スレッド１４ａによって独自に管理されており、原則としてスレッド１４ｂからアクセスされることは想定されていない。また、個別領域１３ｂに格納されたデータ１５ｂは、スレッド１４ｂによって独自に管理されており、原則としてスレッド１４ａからアクセスされることは想定されていない。これに対し、並列計算装置１０は、以下のようにして、個別領域１３ａのデータ１５ａと個別領域１３ｂのデータ１５ｂとを効率的に集計してデータ１５ｄを生成する。
【００２３】
スレッド１４ａは、個別領域１３ａのデータ１５ａへのアクセスを可能とするアドレス情報１５ｃを生成し、共有領域１３ｃに格納する。アドレス情報１５ｃは、例えば、データ１５ａが格納される領域またはデータ１５ａを含む一連のデータが格納される領域の先頭の物理アドレスである。アドレス情報１５ｃは、データ１５ａが生成された後に生成されてもよいし、データ１５ａが生成される前に生成されてもよい。
【００２４】
スレッド１４ｂは、共有領域１３ｃからアドレス情報１５ｃを読み出し、アドレス情報１５ｃに基づいて個別領域１３ａのデータ１５ａにアクセスする。そして、スレッド１４ｂは、個別領域１３ａのデータ１５ａと個別領域１３ｂのデータ１５ｂ、すなわち、スレッド１４ａ，１４ｂが生成した中間データを集計し、データ１５ｄを生成する。スレッド１４ｂは、例えば、生成したデータ１５ｄを共有領域１３ｃに格納する。
【００２５】
第１の実施の形態の並列計算装置１０によれば、演算部１１を用いてスレッド１４ａが起動され、演算部１２を用いてスレッド１４ｂが起動される。スレッド１４ａによって、個別領域１３ａにデータ１５ａが格納され、共有領域１３ｃにアドレス情報１５ｃが格納される。スレッド１４ｂによって、個別領域１３ｂにデータ１５ｂが格納される。そして、スレッド１４ｂによって、アドレス情報１５ｃに基づいてデータ１５ａにアクセスされ、データ１５ａ，１５ｂからデータ１５ｄが生成される。
【００２６】
これにより、中間データであるデータ１５ａ，１５ｂを共有領域１３ｃに格納する方法と比べて、共有領域１３ｃに動的に領域を確保するオーバヘッドを削減できる。また、スレッド１４ａがデータ１５ａをデータ１５ｄに反映させ、スレッド１４ｂがデータ１５ｂをデータ１５ｄに反映させる方法と比べて、スレッド１４ａ，１４ｂの間で排他制御を行わなくてよく、排他制御のオーバヘッドを削減できる。よって、スレッド１４ａが生成したデータ１５ａとスレッド１４ｂが生成したデータ１５ｂの集計を高速化できる。また、データ１５ｂを生成したスレッド１４ｂがデータ１５ａ，１５ｂの集計を行うため、新たなスレッドを起動しなくてよく、スレッド起動のオーバヘッドを削減できる。
【００２７】
［第２の実施の形態］
次に、第２の実施の形態を説明する。
図２は、第２の実施の形態のコンパイル装置を示す図である。
【００２８】
第２の実施の形態のコンパイル装置２０は、第１の実施の形態の並列計算装置１０に実行させるコードを生成する。コンパイル装置２０は、ユーザが操作するクライアントコンピュータでもよいし、クライアントコンピュータからアクセスされるサーバコンピュータでもよい。また、並列計算装置１０とコンパイル装置２０とが同一装置でもよい。
【００２９】
コンパイル装置２０は、記憶部２１および変換部２２を有する。記憶部２１は、例えば、ＲＡＭなどの揮発性の記憶装置、または、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性の記憶装置である。変換部２２は、例えば、ＣＰＵやＤＳＰ（Digital Signal Processor）などのプロセッサである。ただし、変換部２２は、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路を含んでもよい。プロセッサは、メモリに記憶されたプログラムを実行する。実行されるプログラムには、コンパイルプログラムが含まれる。複数のプロセッサの集合（マルチプロセッサ）を「プロセッサ」と呼ぶこともある。
【００３０】
記憶部２１は、コード２３（第１のコード）を記憶する。コード２３は、ソースコードでもよいし、ソースコードから変換された中間コードでもよいし、最適化前のオブジェクトコードでもよい。コード２３は、データ１５ｄ（第１のデータ）を生成することを示す命令２３ａを含む。変換部２２は、記憶部２１に記憶されたコード２３をコード２４に変換する。コード２４は、データ１５ａ（第２のデータ）を生成するスレッド１４ａ（第１のスレッド）と、データ１５ｂ（第３のデータ）を生成しデータ１５ａ，１５ｂに基づいてデータ１５ｄを生成するスレッド１４ｂ（第２のスレッド）とを起動することを示す。コード２４は、ソースコードでもよいし、中間コードでもよいし、オブジェクトコードでもよい。コード２４は、例えば、記憶部２１に格納される。
【００３１】
ここで、コード２３から変換されたコード２４は、命令２４ａ（第１の命令）と命令２４ｂ（第２の命令）と命令２４ｃ（第３の命令）と命令２４ｄ（第４の命令）とを含む。
命令２４ａは、スレッド１４ａからスレッド１４ａに対応する個別領域１３ａにデータ１５ａを格納し、また、スレッド１４ｂからスレッド１４ｂに対応する個別領域１３ｂにデータ１５ｂを格納することを示す。データ１５ａの格納とデータ１５ｂの格納とは並列に実行できる。命令２４ｂは、スレッド１４ａから共有領域１３ｃに、データ１５ａへのアクセスを可能とするアドレス情報１５ｃを格納することを示す。命令２４ｃは、共有領域１３ｃに格納されたアドレス情報１５ｃに基づいて、スレッド１４ｂから個別領域１３ａに格納されたデータ１５ａにアクセスすることを示す。命令２４ｄは、スレッド１４ｂによって、データ１５ａ，１５ｂを集計してデータ１５ｄを生成することを示す。
【００３２】
第２の実施の形態のコンパイル装置２０によれば、並列処理用に作成されていないコード２３から並列処理用のコード２４を生成することができる。これにより、コンピュータの演算能力を活用して計算を高速化することができる。また、各スレッドが生成した中間データの集計を高速化することができる。すなわち、データ１５ａ，１５ｂを共有領域１３ｃに格納する方法と比べて、共有領域１３ｃに動的に領域を確保するオーバヘッドを削減できる。また、スレッド１４ａがデータ１５ａをデータ１５ｄに反映させ、スレッド１４ｂがデータ１５ｂをデータ１５ｄに反映させる方法と比べて、スレッド１４ａ，１４ｂの間で排他制御を行わなくてよく、排他制御のオーバヘッドを削減できる。また、データ１５ｂを生成したスレッド１４ｂがデータ１５ａ，１５ｂの集計を行うため、新たなスレッドを起動しなくてよく、スレッド起動のオーバヘッドを削減できる。
【００３３】
［第３の実施の形態］
次に、第３の実施の形態を説明する。
図３は、第３の実施の形態の情報処理システムを示す図である。
【００３４】
第３の実施の形態の情報処理システムは、並列計算装置１００およびコンパイル装置２００を有する。並列計算装置１００とコンパイル装置２００とは、ネットワーク３０を介して接続されている。並列計算装置１００およびコンパイル装置２００はそれぞれ、ユーザが操作するクライアントコンピュータでもよいし、ネットワーク３０を介してクライアントコンピュータからアクセスされるサーバコンピュータでもよい。なお、並列計算装置１００は、第１の実施の形態の並列計算装置１０に対応する。コンパイル装置２００は、第２の実施の形態のコンパイル装置２０に対応する。
【００３５】
並列計算装置１００は、複数のＣＰＵコアを用いて複数のスレッドを並列に実行することができる、共有メモリ型のマルチプロセッサ装置である。コンパイル装置２００は、ユーザが作成したソースコードを、並列計算装置１００が実行可能なオブジェクトコードに変換する。その際、コンパイル装置２００は、並列処理用に作成されていないソースコードから、並列に動作する複数のスレッドを起動可能な並列処理用のオブジェクトコードを生成することができる。生成されたオブジェクトコードは、コンパイル装置２００から並列計算装置１００に送信される。ただし、第３の実施の形態ではプログラムをコンパイルする装置と実行する装置とを別装置としたが、同一装置であってもよい。
【００３６】
図４は、並列計算装置のハードウェア例を示すブロック図である。
並列計算装置１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７を有する。上記ユニットはバス１０８に接続される。
【００３７】
ＣＰＵ１０１は、プログラムの命令を実行するプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されたプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。ＣＰＵ１０１は、ＣＰＵコア１０１ａ〜１０１ｄを有する。ＣＰＵコア１０１ａ〜１０１ｄは、並列にスレッドを実行することができる。また、ＣＰＵコア１０１ａ〜１０１ｄは、それぞれＲＡＭ１０２よりも高速なキャッシュメモリを有する。ただし、ＣＰＵ１０１が有するＣＰＵコアの数は、２以上の任意の数でよい。なお、ＣＰＵ１０１ａ〜１０１ｄそれぞれを「プロセッサ」と呼ぶこともあるし、ＣＰＵ１０１ａ〜１０１ｄの集合またはＣＰＵ１０１を「プロセッサ」と呼ぶこともある。
【００３８】
ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムやＣＰＵ１０１が演算に用いるデータを一時的に記憶する揮発性の半導体メモリである。なお、並列計算装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数個のメモリを備えてもよい。
【００３９】
ＨＤＤ１０３は、ＯＳやミドルウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性の記憶装置である。プログラムには、コンパイル装置２００によってコンパイルされたものが含まれる。なお、並列計算装置１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の記憶装置を備えてもよく、複数の不揮発性の記憶装置を備えてもよい。
【００４０】
画像信号処理部１０４は、ＣＰＵ１０１からの命令に従って、並列計算装置１００に接続されたディスプレイ１１１に画像を出力する。ディスプレイ１１１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、プラズマディスプレイ（ＰＤＰ：Plasma Display Panel）、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなどを用いることができる。
【００４１】
入力信号処理部１０５は、並列計算装置１００に接続された入力デバイス１１２から入力信号を取得し、ＣＰＵ１０１に出力する。入力デバイス１１２としては、マウスやタッチパネルやタッチパッドやトラックボールなどのポインティングデバイス、キーボード、リモートコントローラ、ボタンスイッチなどを用いることができる。また、並列計算装置１００に、複数の種類の入力デバイスが接続されていてもよい。
【００４２】
媒体リーダ１０６は、記録媒体１１３に記録されたプログラムやデータを読み取る読み取り装置である。記録媒体１１３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。媒体リーダ１０６は、例えば、記録媒体１１３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００４３】
通信インタフェース１０７は、ネットワーク３０に接続され、ネットワーク３０を介してコンパイル装置２００などの他の装置と通信を行うインタフェースである。通信インタフェース１０７は、スイッチなどの通信装置とケーブルで接続される有線通信インタフェースでもよいし、基地局と無線リンクで接続される無線通信インタフェースでもよい。
【００４４】
なお、並列計算装置１００は、媒体リーダ１０６を備えていなくてもよく、ユーザが操作する端末装置から制御可能である場合には画像信号処理部１０４や入力信号処理部１０５を備えていなくてもよい。また、ディスプレイ１１１や入力デバイス１１２が、並列計算装置１００の筐体と一体に形成されてもよい。ＣＰＵコア１０１ａは、第１の実施の形態の演算部１１に対応する。ＣＰＵコア１０１ｂは、第１の実施の形態の演算部１２に対応する。ＲＡＭ１０２は、第１の実施の形態の記憶部１３に対応する。
【００４５】
図５は、コンパイル装置のハードウェア例を示すブロック図である。
コンパイル装置２００は、ＣＰＵ２０１、ＲＡＭ２０２、ＨＤＤ２０３、画像信号処理部２０４、入力信号処理部２０５、媒体リーダ２０６および通信インタフェース２０７を有する。上記ユニットはバス２０８に接続される。
【００４６】
ＣＰＵ２０１は、並列計算装置１００のＣＰＵ１０１と同様の機能を有する。ただし、ＣＰＵ２０１が有するＣＰＵコアの数は１つであってもよく、ＣＰＵ２０１はマルチプロセッサでなくてもよい。ＲＡＭ２０２は、並列計算装置１００のＲＡＭ１０２と同様の機能を有する。ＨＤＤ２０３は、並列計算装置１００のＨＤＤ１０３と同様の機能を有する。ただし、ＨＤＤ２０３が記憶するプログラムには、コンパイルプログラムが含まれる。
【００４７】
画像信号処理部２０４は、並列計算装置１００の画像信号処理部１０４と同様の機能を有する。画像信号処理部２０４は、コンパイル装置２００に接続されたディスプレイ２１１に画像を出力する。入力信号処理部２０５は、並列計算装置１００の入力信号処理部１０５と同様の機能を有する。入力信号処理部２０５は、コンパイル装置２００に接続された入力デバイス２１２から入力信号を取得する。
【００４８】
媒体リーダ２０６は、並列計算装置１００の媒体リーダ１０６と同様の機能を有する。媒体リーダ２０６は、記録媒体２１３に記録されたプログラムやデータを読み取る。ただし、記録媒体１１３と記録媒体２１３とが同一媒体であってもよい。通信インタフェース２０７は、並列計算装置１００の通信インタフェース１０７と同様の機能を有する。通信インタフェース２０７は、ネットワーク３０に接続されている。
【００４９】
なお、コンパイル装置２００は、媒体リーダ２０６を備えていなくてもよく、ユーザが操作する端末装置から制御可能である場合には画像信号処理部２０４や入力信号処理部２０５を備えていなくてもよい。また、ディスプレイ２１１や入力デバイス２１２が、コンパイル装置２００の筐体と一体に形成されてもよい。ＣＰＵ２０１は、第２の実施の形態の変換部２２に対応する。ＲＡＭ２０２は、第２の実施の形態の記憶部２１に対応する。
【００５０】
次に、並列計算装置１００に実行させる配列演算について説明する。
図６は、並列化前の配列演算の例を示す図である。
ここでは、入力データとしてｎ行ｍ列（ｎ，ｍはそれぞれ２以上の整数）の二次元配列４１（二次元配列ａ）が与えられるとする。また、二次元配列４１から、結果データとしてｎ行の配列４２（配列ｓｕｍ）が生成されるとする。
【００５１】
並列計算装置１００は、二次元配列４１のｉ行目（ｉ＝１，２，…，ｎ）の各列の値を合計し、合計値を配列４２のｉ行目に格納する。すなわち、並列計算装置１００は、ａ（１，１），ａ（１，２），…，ａ（１，ｍ）の合計値を、ｓｕｍ（１）に格納する。また、並列計算装置１００は、ａ（２，１），ａ（２，２），…，ａ（２，ｍ）の合計値を、ｓｕｍ（２）に格納する。また、並列計算装置１００は、ａ（ｎ，１），ａ（ｎ，２），…，ａ（ｎ，ｍ）の合計値を、ｓｕｍ（ｎ）に格納する。以下では説明を簡単にするため、ｎ＝４，ｍ＝８の比較的小さな入力データを一例として用いることがある。
【００５２】
並列計算装置１００は、ＣＰＵコア１０１ａ〜１０１ｄを用いて、上記の配列演算をリダクション処理として並列化することが可能である。並列計算装置１００は、二次元配列４１を複数の列集合に分割してＣＰＵコア１０１ａ〜１０１ｄに割り振る。例えば、ＣＰＵコア１０１ａが１，２列目を担当する。ＣＰＵコア１０１ｂが３，４列目を担当する。ＣＰＵコア１０１ｃが５，６列目を担当する。ＣＰＵコア１０１ｄが７，８列目を担当する。ＣＰＵコア１０１ａ〜１０１ｄはそれぞれ、二次元配列４１の中の割り振られた範囲の値を行毎に合計して中間データを生成する。ＣＰＵコア１０１ａ〜１０１ｄが生成した中間データを行毎に合計することで、配列４２を生成できる。
【００５３】
図７は、並列化前のプログラム例を示す図である。
ソースコード５１は、図６に示した配列演算を表したものである。コンパイル装置２００は、ソースコード５１をコンパイルし、並列計算装置１００に実行させるオブジェクトコードを生成する。ソースコード５１には、整数ｎ，ｍと、整数型のｎ行の配列ｓｕｍと、整数型のｎ行ｍ列の二次元配列ａが定義されている。また、ソースコード５１には、ループ変数ｉ，ｊが定義されている。また、ソースコード５１には、ループ変数ｊの値が１からｍまで１ずつ増加する外側ループと、ループ変数ｉの値が１からｎまで１ずつ増加する内側ループとを含む多重ループが定義されている。内側ループの中には、ａ（ｉ，ｊ）をｓｕｍ（ｉ）に加算する演算が定義されている。すなわち、ソースコード５１は、二次元配列４１の１列目からｍ列目までを逐次処理することを示している。
【００５４】
ここで、ソースコード５１には、多重ループの区間に対してＯｐｅｎＭＰの指示文が付加されている。ＯｐｅｎＭＰの指示文は、ユーザがソースコード５１に付加する並列化指示文である。コンパイル装置２００は、ＯｐｅｎＭＰの指示文を有効にするためのコンパイルオプションが指定された場合、ＯｐｅｎＭＰの指示文が付加された範囲について、ソースコード５１から並列処理用のオブジェクトコードを生成する。一方、コンパイル装置２００は、ＯｐｅｎＭＰの指示文を有効にするためのコンパイルオプションが指定されていない場合、ＯｐｅｎＭＰの指示文を無視し、ソースコード５１から逐次処理用のオブジェクトコードを生成する。
【００５５】
具体的には、ソースコード５１には、リダクション演算子を「＋」と指定しリダクション変数を「ｓｕｍ」と指定したリダクション指示文が付加されている。リダクション演算子「＋」は、複数のスレッドが並列に生成した中間データを、加算演算によって集計することを示す。他のリダクション演算子としては、「−」（減算）、「×」（乗算）、「．ＡＮＤ．」（論理積）、「．ＯＲ．」（論理和）、「ＭＡＸ」（最大値選択）、「ＭＩＮ」（最小値選択）、その他のユーザ定義演算子などが考えられる。リダクション変数「ｓｕｍ」は、最終的な結果データを格納する変数が配列ｓｕｍであることを示す。
【００５６】
次に、リダクション処理の実現方法として２通りの方法を説明する。
図８は、第１のリダクション処理の例を示す図である。
ここでは、並列計算装置１００がＣＰＵコア１０１ａ〜１０１ｄを用いて４個のスレッドを並列に実行する場合を考える。ＣＰＵコア１０１ａはスレッド＃０を起動する。ＣＰＵコア１０１ｂはスレッド＃１を起動する。ＣＰＵコア１０１ｃはスレッド＃２を起動する。ＣＰＵコア１０１ｄはスレッド＃３を起動する。
【００５７】
並列計算装置１００は、スレッド＃０に対応するスタック領域１２１ａをＲＡＭ１０２に確保する。スタック領域１２１ａは、スレッド＃０が生成したデータをローカルに記憶する記憶領域である。スタック領域１２１ａは、スレッド＃０がそのアドレス空間に基づいて、他のスレッドから独立して使用することができる。スタック領域１２１ａは、可変長のデータを格納する場合であってもＯＳから動的なメモリ割り当てを受けずに使用でき、使用コストが比較的小さい。同様に、並列計算装置１００は、スレッド＃１に対応するスタック領域１２１ｂをＲＡＭ１０２に確保する。並列計算装置１００は、スレッド＃２に対応するスタック領域１２１ｃをＲＡＭ１０２に確保する。並列計算装置１００は、スレッド＃３に対応するスタック領域１２１ｄをＲＡＭ１０２に確保する。
【００５８】
また、並列計算装置１００は、共有領域１２２をＲＡＭ１０２に確保する。共有領域１２２は、スレッド＃０〜＃３から共通してアクセス可能な記憶領域である。共有領域１２２は、可変長のデータを格納する場合にはＯＳから動的なメモリ割り当てを受けて使用することになり、スタック領域１２１ａ〜１２１ｄと比べて使用コストが大きい。また、２以上のスレッドが同時に共有領域１２２内の同一領域にアクセスする可能性があるため、共有領域１２２へのアクセスの際には排他制御が行われ得る。
【００５９】
上記の図６，７の配列演算を並列化する場合、スレッド＃０は、リダクション変数「ｓｕｍ」のコピーである配列４３ａ（配列ｓｕｍ０）をスタック領域１２１ａに生成する。同様に、スレッド＃１は、リダクション変数「ｓｕｍ」のコピーである配列４３ｂ（配列ｓｕｍ１）をスタック領域１２１ｂに生成する。スレッド＃２は、リダクション変数「ｓｕｍ」のコピーである配列４３ｃ（配列ｓｕｍ２）をスタック領域１２１ｃに生成する。スレッド＃３は、リダクション変数「ｓｕｍ」のコピーである配列４３ｄ（配列ｓｕｍ３）をスタック領域１２１ｄに生成する。また、並列計算装置１００は、リダクション変数「ｓｕｍ」のオリジナルである配列４２（配列ｓｕｍ）を共有領域１２２に生成する。配列４３ａ〜４３ｄのデータ型・次元・長さなどの属性は、配列４２と同じである。
【００６０】
スレッド＃０には、二次元配列４１の中の１，２列目が割り当てられる。スレッド＃０は、二次元配列４１全体に対する配列演算の部分集合である１，２列目に対する配列演算を行い、中間データを配列４３ａに格納する。すなわち、スレッド＃０は、ｉ＝１〜４それぞれについてａ（ｉ，１），ａ（ｉ，２）の合計値をｓｕｍ０（ｉ）に格納する。
【００６１】
同様に、スレッド＃１には、二次元配列４１の中の３，４列目が割り当てられる。スレッド＃１は、ｉ＝１〜４それぞれについてａ（ｉ，３），ａ（ｉ，４）の合計値をｓｕｍ１（ｉ）に格納する。スレッド＃２には、二次元配列４１の中の５，６列目が割り当てられる。スレッド＃２は、ｉ＝１〜４それぞれについてａ（ｉ，５），ａ（ｉ，６）の合計値をｓｕｍ２（ｉ）に格納する。スレッド＃３には、二次元配列４１の中の７，８列目が割り当てられる。スレッド＃３は、ｉ＝１〜４それぞれについてａ（ｉ，７），ａ（ｉ，８）の合計値をｓｕｍ３（ｉ）に格納する。
【００６２】
配列４３ａ〜４３ｄに格納される中間データの生成は、スレッド＃０〜＃３の間で並列に実行することができる。並列計算装置１００は、配列４３ａ〜４３ｄに格納された中間データを集計して、配列ｓｕｍに結果データを格納することになる。ここで、第１の方法によれば、並列計算装置１００は以下のように中間データを集計する。
【００６３】
スレッド＃０は、スタック領域１２１ａの配列４３ａに格納された値を、共有領域１２２の配列４２の値に加算する。すなわち、スレッド＃０は、ｉ＝１〜４それぞれについてｓｕｍ０（ｉ）をｓｕｍ（ｉ）に加算する。スレッド＃１は、スタック領域１２１ｂの配列４３ｂに格納された値を、共有領域１２２の配列４２の値に加算する。すなわち、スレッド＃１は、ｉ＝１〜４それぞれについてｓｕｍ１（ｉ）をｓｕｍ（ｉ）に加算する。スレッド＃２は、スタック領域１２１ｃの配列４３ｃに格納された値を、共有領域１２２の配列４２の値に加算する。すなわち、スレッド＃２は、ｉ＝１〜４それぞれについてｓｕｍ２（ｉ）をｓｕｍ（ｉ）に加算する。スレッド＃３は、スタック領域１２１ｄの配列４３ｄに格納された値を、共有領域１２２の配列４２の値に加算する。すなわち、スレッド＃０は、ｉ＝１〜４それぞれについてｓｕｍ３（ｉ）をｓｕｍ（ｉ）に加算する。
【００６４】
これにより、ｓｕｍ（ｉ）はｓｕｍ０（ｉ），ｓｕｍ１（ｉ），ｓｕｍ２（ｉ），ｓｕｍ３（ｉ）の合計になる。このように算出されたｓｕｍ（ｉ）は、ａ（ｉ，１）〜ａ（ｉ，８）の合計を意味する。よって、並列化しない場合と並列化した場合とで、配列４２に格納される結果データは原則として一致する（なお、配列４２の要素が浮動小数点数である場合など、変数の型によっては演算順序が変更された結果として演算誤差が生じる可能性はある）。ただし、第１の方法では、スレッド＃０〜＃３が配列４２の全ての行にアクセスする。このため、配列４２へのアクセスはスレッド＃０〜＃３の間で排他的に行うことになり、実質的に並列化されない。
【００６５】
図９は、並列化後の第１のプログラム例を示す図である。
ここでは説明を簡単にするため、図７に示したソースコード５１から生成される並列処理用のコードを、ソースコード形式で表している。ＯｐｅｎＭＰのリダクション指示文に基づく処理コードの生成は、実際には中間コードに対して行われる。
【００６６】
ソースコード５２は、図８に示した第１の方法に従ってソースコード５１を並列処理用に変換したものである。ソースコード５２には、ソースコード５１と同様に、整数ｎ，ｍと、整数型のｎ行の配列ｓｕｍと、整数型のｎ行ｍ列の二次元配列ａと、ループ変数ｉ，ｊが定義されている。また、ソースコード５２には、リダクション変数である配列ｓｕｍのコピーとして、整数型のｎ行の配列ｓｕｍ＿ｋが定義されている。配列ｓｕｍ＿ｋは、図８の配列ｓｕｍ０，ｓｕｍ１，ｓｕｍ２，ｓｕｍ３に対応する。なお、オリジナルの変数である配列ｓｕｍは、上位モジュールにおいて共有変数として定義されているものとする。一方、コピーされた変数である配列ｓｕｍ＿ｋは、このサブルーチン内にのみ現れるため、コンパイル時にプライベート変数と判定される。
【００６７】
また、ソースコード５２には、配列ｓｕｍ＿ｋを初期化するコードが挿入されている。配列ｓｕｍ＿ｋの初期値は、リダクション演算子に応じて決まる。例えば、配列ｓｕｍ＿ｋの各行の初期値は、「＋」や「−」の場合は０、「×」の場合は１、「．ＡＮＤ．」の場合は．ＴＲＵＥ．、「．ＯＲ．」の場合は．ＦＡＬＳＥ．、「ＭＡＸ」の場合は取り得る値の最小値、「ＭＩＮ」の場合は取り得る値の最大値である。
【００６８】
また、ソースコード５２には、ソースコード５１と同様に、ループ変数ｊの値が１からｍまで１ずつ増加する外側ループと、ループ変数ｉの値が１からｎまで１ずつ増加する内側ループとを含む多重ループが定義されている。ただし、内側ループの中には、ａ（ｉ，ｊ）を、ｓｕｍ（ｉ）に代えてｓｕｍ＿ｋ（ｉ）に加算する演算が定義されている。これは、複数のスレッドそれぞれが中間データを、オリジナルの共有変数ではなくそのコピーであるプライベート変数に格納することを示している。なお、図９に示したソースコード５２では、配列ａの列集合の分割については説明を省略している。
【００６９】
また、ソースコード５２には、プライベート変数である配列ｓｕｍ＿ｋに格納した中間データを、共有変数である配列ｓｕｍに集計するコードが挿入されている。具体的には、ｉ＝１〜ｎそれぞれについてｓｕｍ＿ｋ（ｉ）をｓｕｍ（ｉ）に加算するコードが、ソースコード５２に挿入されている。なお、図９に示したソースコード５２では、配列ｓｕｍにアクセスする際の排他制御については説明を省略している。
【００７０】
図１０は、第１のリダクション処理のタイミング例を示す図である。
第１の方法では、スレッド＃０〜＃３の中間データの集計は実質的に並列化されない。例えば、最初にスレッド＃０が配列４２をロックし、他のスレッドから配列４２へのアクセスを待たせる。スレッド＃０は、ｓｕｍ０（１）をｓｕｍ（１）に加算し、ｓｕｍ０（２）をｓｕｍ（２）に加算し、ｓｕｍ０（３）をｓｕｍ（３）に加算し、ｓｕｍ０（４）をｓｕｍ（４）に加算する。そして、スレッド＃０は配列４２のロックを解除する（Ｐ１０）。これにより、他のスレッドから配列４２へのアクセスが可能となる。
【００７１】
次に、スレッド＃２が配列４２をロックし、他のスレッドから配列４２へのアクセスを待たせる。スレッド＃２は、ｓｕｍ２（１）をｓｕｍ（１）に加算し、ｓｕｍ２（２）をｓｕｍ（２）に加算し、ｓｕｍ２（３）をｓｕｍ（３）に加算し、ｓｕｍ２（４）をｓｕｍ（４）に加算する。そして、スレッド＃２は配列４２のロックを解除する（Ｐ１２）。これにより、他のスレッドから配列４２へのアクセスが可能となる。
【００７２】
次に、スレッド＃１が配列４２をロックし、他のスレッドから配列４２へのアクセスを待たせる。スレッド＃１は、ｓｕｍ１（１）をｓｕｍ（１）に加算し、ｓｕｍ１（２）をｓｕｍ（２）に加算し、ｓｕｍ１（３）をｓｕｍ（３）に加算し、ｓｕｍ１（４）をｓｕｍ（４）に加算する。そして、スレッド＃１は配列４２のロックを解除する（Ｐ１１）。これにより、他のスレッドから配列４２へのアクセスが可能となる。
【００７３】
最後に、スレッド＃３が配列４２をロックする。スレッド＃３は、ｓｕｍ３（１）をｓｕｍ（１）に加算し、ｓｕｍ３（２）をｓｕｍ（２）に加算し、ｓｕｍ３（３）をｓｕｍ（３）に加算し、ｓｕｍ３（４）をｓｕｍ（４）に加算する。そして、スレッド＃３は配列４２のロックを解除する（Ｐ１３）。なお、スレッド＃０〜＃３がロックを獲得する上記の順序は一例であり、スレッド＃０〜＃３の実行状況によって変化する。
【００７４】
このように、中間データの集計時に配列４２をロックする方法では、スレッド＃０〜＃３は配列４２に逐次アクセスすることになる。すなわち、スレッド＃０〜＃３のうち先にロックを獲得したスレッドから順に中間データを配列４２に反映させ、他のスレッドはロックが解除されるのを待つことになる。よって、中間データの集計が並列化されず、時間を要するという問題がある。一方、配列４３ａ〜４３ｄをスタック領域１２１ａ〜１２１ｄではなく共有領域１２２に格納することで、スレッド＃０〜＃３が中間データ全体にアクセスできるようにし、ロックなしに中間データを集計できるようにする方法も考えられる。しかし、この方法では、配列４３ａ〜４３ｄが可変長である場合に、共有領域１２２に動的に領域を確保するオーバヘッドが発生するという問題がある。そこで、並列計算装置１００は、次に説明する第２の方法でリダクション処理を行うことができる。
【００７５】
図１１は、第２のリダクション処理の例を示す図である。
第１の方法と同様に、スレッド＃０は、配列４３ａ（配列ｓｕｍ０）をスタック領域１２１ａに生成する。スレッド＃１は、配列４３ｂ（配列ｓｕｍ１）をスタック領域１２１ｂに生成する。スレッド＃２は、配列４３ｃ（配列ｓｕｍ２）をスタック領域１２１ｃに生成する。スレッド＃３は、配列４３ｄ（配列ｓｕｍ３）をスタック領域１２１ｄに生成する。並列計算装置１００は、配列４２（配列ｓｕｍ）を共有領域１２２に生成する。
【００７６】
更に、並列計算装置１００は、ポインタ配列４４（ポインタ配列ａｄｒ）を共有領域１２２に生成する。ポインタ配列４４は、ＲＡＭ１０２上における配列４３ａ〜４３ｄそれぞれの位置を示すアドレス（例えば、配列４３ａ〜４３ｄそれぞれの先頭を示す物理アドレス）を格納する。スレッド＃０は、配列４３ａのアドレスを、ポインタ配列４４のスレッド＃０に対応する行に格納する。スレッド＃１は、配列４３ｂのアドレスを、ポインタ配列４４のスレッド＃１に対応する行に格納する。スレッド＃２は、配列４３ｃのアドレスを、ポインタ配列４４のスレッド＃２に対応する行に格納する。スレッド＃３は、配列４３ｄのアドレスを、ポインタ配列４４のスレッド＃３に対応する行に格納する。
【００７７】
スレッド＃０〜＃３による中間データの生成は、前述の第１の方法と同じである。第２の方法は、中間データの集計が第１の方法と異なる。並列計算装置１００は、配列４２の行集合を分割してスレッド＃０〜＃３に割り振る。スレッド＃０〜＃３はそれぞれ、配列４３ａ〜４３ｄに格納された中間データのうち割り当てられた行の中間データを集計し、結果データを配列４２に格納する。配列４２の行集合のうちスレッド＃０〜＃３がアクセスする行は互いに異なるため、中間データの集計を並列に実行することができる。その際、スレッド＃０〜＃３はそれぞれ、ポインタ配列４４に格納されたアドレスに基づいて、他のスレッドに対応するスタック領域にアクセスすることができる。
【００７８】
例えば、スレッド＃０が１行目を担当し、スレッド＃１が２行目を担当し、スレッド＃２が３行目を担当し、スレッド＃３が４行目を担当する。スレッド＃０は、スタック領域１２１ａからｓｕｍ０（１）を読み出す。また、スレッド＃０は、ポインタ配列４４を参照して、スタック領域１２１ｂからｓｕｍ１（１）を読み出し、スタック領域１２１ｃからｓｕｍ２（１）を読み出し、スタック領域１２１ｄからｓｕｍ３（１）を読み出す。スレッド＃０は、ｓｕｍ０（１），ｓｕｍ１（１），ｓｕｍ２（１），ｓｕｍ３（１）の合計値を共有領域１２２のｓｕｍ（１）に格納する。
【００７９】
同様に、スレッド＃１は、ポインタ配列４４を参照して、スタック領域１２１ａからｓｕｍ０（２）を読み出し、スタック領域１２１ｂからｓｕｍ１（２）を読み出し、スタック領域１２１ｃからｓｕｍ２（２）を読み出し、スタック領域１２１ｄからｓｕｍ３（２）を読み出す。スレッド＃１は、ｓｕｍ０（２），ｓｕｍ１（２），ｓｕｍ２（２），ｓｕｍ３（２）の合計値を共有領域１２２のｓｕｍ（２）に格納する。
【００８０】
スレッド＃２は、ポインタ配列４４を参照して、スタック領域１２１ａからｓｕｍ０（３）を読み出し、スタック領域１２１ｂからｓｕｍ１（３）を読み出し、スタック領域１２１ｃからｓｕｍ２（３）を読み出し、スタック領域１２１ｄからｓｕｍ３（３）を読み出す。スレッド＃２は、ｓｕｍ０（３），ｓｕｍ１（３），ｓｕｍ２（３），ｓｕｍ３（３）の合計値を共有領域１２２のｓｕｍ（３）に格納する。
【００８１】
スレッド＃３は、ポインタ配列４４を参照して、スタック領域１２１ａからｓｕｍ０（４）を読み出し、スタック領域１２１ｂからｓｕｍ１（４）を読み出し、スタック領域１２１ｃからｓｕｍ２（４）を読み出し、スタック領域１２１ｄからｓｕｍ３（４）を読み出す。スレッド＃３は、ｓｕｍ０（４），ｓｕｍ１（４），ｓｕｍ２（４），ｓｕｍ３（４）の合計値を共有領域１２２のｓｕｍ（４）に格納する。
【００８２】
これにより、ｓｕｍ（１）はａ（１，１）〜ａ（１，８）の合計になる。ｓｕｍ（２）はａ（２，１）〜ａ（２，８）の合計になる。ｓｕｍ（３）はａ（３，１）〜ａ（３，８）の合計になる。ｓｕｍ（４）はａ（４，１）〜ａ（４，８）の合計になる。よって、第２の方法によって配列４２に格納される結果データは、並列化しない場合や第１の方法と原則として一致する（なお、配列４２の要素が浮動小数点数である場合など、変数の型によっては演算順序が変更された結果として演算誤差が生じる可能性はある）。また、第２の方法では、スレッド＃０〜＃３は互いに配列４２の異なる行にアクセスするため、排他制御を行わずに中間データの集計を並列化できる。
【００８３】
ところで、ＣＰＵコア１０１ａ〜１０１ｄはそれぞれキャッシュメモリを有する。データにアクセスする場合、ＣＰＵコア１０１ａ〜１０１ｄはＲＡＭ１０２からキャッシュメモリにデータを読み込む。キャッシュメモリへのデータの読み込みは、キャッシュラインと呼ばれる一定のサイズ単位で行われる。一のＣＰＵコアと他のＣＰＵコアとが異なるデータにアクセスする場合であっても、ＲＡＭ１０２上の両者のデータの位置がキャッシュラインサイズよりも近い場合、一のＣＰＵコアのキャッシュメモリと他のＣＰＵコアのキャッシュメモリに両方のデータが読み込まれることになる。
【００８４】
このとき、キャッシュメモリ間のデータの一貫性の問題が生じる。一のＣＰＵコアがキャッシュメモリ上の一のデータを更新すると、他のＣＰＵコアは当該一のデータを含むキャッシュライン全体を破棄してＲＡＭ１０２から読み直すことになる。この問題は、キャッシュメモリのフォルスシェアリング（False Sharing）と呼ばれることがある。フォルスシェアリングが発生すると、データアクセスの性能が低下するおそれがある。
【００８５】
そこで、並列計算装置１００は、スレッド＃０〜＃３がポインタ配列４４にアドレスを格納するときにフォルスシェアリングが発生しないよう、アドレスを格納する行の間隔を空けるようにする。すなわち、あるスレッドのアドレスと他のスレッドのアドレスとが、キャッシュラインサイズよりも離れて格納されるようにする。例えば、キャッシュラインサイズが１２８バイト、アドレス１個のサイズが８バイトである場合、あるスレッドのアドレスと他のスレッドのアドレスとが１６行以上離れるようにする。
【００８６】
この場合、ポインタ配列４４はスレッド数×１６の長さをもつことになる。スレッド＃０はポインタ配列４４の１行目にアドレスを格納する。スレッド＃１はポインタ配列４４の１７行目にアドレスを格納する。スレッド＃２はポインタ配列４４の３３行目にアドレスを格納する。スレッド＃３はポインタ配列４４の４９行目にアドレスを格納する。それ以外の行は使用されない。これにより、異なるスレッドのアドレスが同じキャッシュラインに読み込まれるのを避け、フォルスシェアリングを回避できる。
【００８７】
なお、起動するスレッドの数が実行時に動的に決まる場合、最大のスレッド数に応じた長さのポインタ配列４４を共有領域１２２に静的に生成するようにしてもよい。最大のスレッド数は、ＣＰＵコア数と推定してもよい。例えば、ＣＰＵ１０１が４個のＣＰＵコア（ＣＰＵコア１０１ａ〜１０１ｄ）を有する場合、最大のスレッド数が４と推定される。これにより、コンパイル時にポインタ配列４４の領域の静的な割り付けが可能となり、共有領域１２２に動的に領域を確保するオーバヘッドを削減できる。
【００８８】
キャッシュメモリのフォルスシェアリングは、スレッド＃０〜＃３が配列４２にアクセする場合でも発生し得る。そこで、配列４２のうち一のスレッドが担当する行と他のスレッドが担当する行とが、キャッシュラインサイズ以上離されていることが好ましい。例えば、キャッシュラインサイズが１２８バイト、整数１個のサイズが８バイトである場合、各スレッドが配列４２の１６行以上を担当することが好ましい。
【００８９】
フォルスシェアリングを避けるため、並列計算装置１００は、配列４２の行数に応じて中間データの集計方法を選択するようにしてもよい。例えば、並列計算装置１００は、リダクション変数である配列４２の長さがスレッド数×１６行未満である場合、図８に示した第１の方法で中間データを集計する。一方、並列計算装置１００は、配列４２の長さがスレッド数×１６行以上である場合、第２の方法で中間データを集計する。
【００９０】
図１２は、並列化後の第２のプログラム例を示す図である。
ここでは説明を簡単にするため、図７に示したソースコード５１から生成される並列処理用のコードを、ソースコード形式で表している。ソースコード５３は、図１１に示した第２の方法に従ってソースコード５１を並列処理用に変換したものである。
【００９１】
ソースコード５３には、ソースコード５１，５２と同様に、整数ｎ，ｍと、整数型のｎ行の配列ｓｕｍと、整数型のｎ行ｍ列の二次元配列ａと、ループ変数ｉ，ｊが定義されている。また、ソースコード５３には、ソースコード５２と同様に、リダクション変数である配列ｓｕｍのコピーとして、整数型のｎ行の配列ｓｕｍ＿ｋが定義されている。
【００９２】
また、ソースコード５３には、整数型のｔｎ×１６行のポインタ配列ａｄｒが定義されている。ｔｎは、ターゲットのＣＰＵに応じて決まるスレッド数を示す。ポインタ配列ａｄｒは、ｓａｖｅ属性を付加することで共有変数として扱われる。また、ソースコード５３には、整数型のｎ行の配列ｖａｒが定義されている。また、ソースコード５３には、ポインタｐｔｒが定義されている。ポインタｐｔｒはデータの先頭を示すアドレスであり、ポインタｐｔｒが指すデータを配列ｖａｒとしてアクセスすることができる。
【００９３】
また、ソースコード５３には、配列ｓｕｍ＿ｋのアドレスをポインタ配列ａｄｒのｔｉｄ×１６＋１行目に格納するコードが挿入されている。ｔｉｄはスレッドＩＤを示す。これにより、スレッド＃０〜＃３のアドレスが１６行ずつ離れて格納される。また、ソースコード５３には、ソースコード５２と同様に、配列ｓｕｍ＿ｋを初期化するコードが挿入されている。また、ソースコード５３には、ソースコード５２と同様に、ループ変数ｊの値が１からｍまで１ずつ増加する外側ループと、ループ変数ｉの値が１からｎまで１ずつ増加する内側ループとを含む多重ループが定義されている。内側ループの中には、ａ（ｉ，ｊ）を、ｓｕｍ（ｉ）に代えてｓｕｍ＿ｋ（ｉ）に加算する演算が定義されている。なお、図１２では配列ａの列集合の分割については説明を省略している。
【００９４】
また、ソースコード５３には、プライベート変数である配列ｓｕｍ＿ｋに格納した中間データを、共有変数である配列ｓｕｍに集計するコードが挿入されている。具体的には、ループ変数ｊの値が０からｔｎ−１まで１ずつ増加する外側ループと、ループ変数ｉの値が１からｎまで１ずつ増加する内側ループとを含む多重ループが定義されている。外側ループと内側ループの間には、ポインタ配列ａｄｒのｊ×１６＋１行目のアドレスをポインタｐｔｒとして参照するコードが挿入されている。内側ループの中には、ポインタｐｔｒが指す配列ｖａｒのｉ行目をｓｕｍ（ｉ）に加算するコードが挿入されている。なお、図１２では配列ｓｕｍの行集合の分割については説明を省略している。
【００９５】
また、ソースコード５３には、中間データを集計するコードの前後にバリア同期を示す指示文が挿入されている。バリア同期は、複数のスレッドの間で処理が所定の箇所に到達するのを待ち合わせる同期処理である。中間データの集計を開始する直前にバリア同期が行われるため、スレッド＃０〜＃３は、スレッド＃０〜＃３全てが中間データの生成を完了するのを待って集計を開始することになる。これは、各スレッドは他のスレッドの中間データにアクセスするためである。また、中間データの集計を終了した直後にバリア同期が行われるため、スレッド＃０〜＃３は、スレッド＃０〜＃３全てが中間データの集計を完了するのを待って次の処理に進むことになる。これは、集計が完了する前にスタック領域１２１ａ〜１２１ｄから中間データが削除されてしまうのを防ぐためである。
【００９６】
バリア同期を実現する方法は幾つか考えられる。例えば、ＣＰＵコア１０１ａ〜１０１ｄがバリア同期をサポートしている場合、ＣＰＵコア１０１ａ〜１０１ｄそれぞれが有するレジスタに全ＣＰＵコア分のフラグを設ける方法が考えられる。あるＣＰＵコアが所定の箇所まで処理を進めると、処理を中断すると共に、他のＣＰＵコアに通知して当該ＣＰＵコアに対応するフラグを０から１に変更させる。各ＣＰＵコアは、ＣＰＵコア１０１ａ〜１０１ｄに対応する全てのフラグが１になると処理を再開する。また、ＣＰＵコア１０１ａ〜１０１ｄに対応するフラグを共有領域１２２に設ける方法も考えられる。
【００９７】
図１３は、第２のリダクション処理のタイミング例を示す図である。
第２の方法では、中間データの集計を並列化できる。まず、バリア同期によって、スレッド＃０〜＃３が中間データを生成し終えるのを待ち合わせる。スレッド＃０〜＃３が中間データを生成し終えると、スレッド＃０は、ポインタ配列４４を参照してｓｕｍ０（１）にアクセスし、ｓｕｍ０（１）をｓｕｍ（１）に加算する。スレッド＃０は、ポインタ配列４４を参照してｓｕｍ１（１）にアクセスし、ｓｕｍ１（１）をｓｕｍ（１）に加算する。スレッド＃０は、ポインタ配列４４を参照してｓｕｍ２（１）にアクセスし、ｓｕｍ２（１）をｓｕｍ（１）に加算する。スレッド＃０は、ポインタ配列４４を参照してｓｕｍ３（１）にアクセスし、ｓｕｍ３（１）をｓｕｍ（１）に加算する（Ｐ２０）。
【００９８】
また、スレッド＃０〜＃３が中間データを生成し終えると、スレッド＃０と並列に、スレッド＃１は、ポインタ配列４４を参照してｓｕｍ０（２）にアクセスし、ｓｕｍ０（２）をｓｕｍ（２）に加算する。スレッド＃１は、ポインタ配列４４を参照してｓｕｍ１（２）にアクセスし、ｓｕｍ１（２）をｓｕｍ（２）に加算する。スレッド＃１は、ポインタ配列４４を参照してｓｕｍ２（２）にアクセスし、ｓｕｍ２（２）をｓｕｍ（２）に加算する。スレッド＃１は、ポインタ配列４４を参照してｓｕｍ３（２）にアクセスし、ｓｕｍ３（２）をｓｕｍ（２）に加算する（Ｐ２１）。
【００９９】
また、スレッド＃０〜＃３が中間データを生成し終えると、スレッド＃０，＃１と並列に、スレッド＃２は、ポインタ配列４４を参照してｓｕｍ０（３）にアクセスし、ｓｕｍ０（３）をｓｕｍ（３）に加算する。スレッド＃２は、ポインタ配列４４を参照してｓｕｍ１（３）にアクセスし、ｓｕｍ１（３）をｓｕｍ（３）に加算する。スレッド＃２は、ポインタ配列４４を参照してｓｕｍ２（３）にアクセスし、ｓｕｍ２（３）をｓｕｍ（３）に加算する。スレッド＃２は、ポインタ配列４４を参照してｓｕｍ３（３）にアクセスし、ｓｕｍ３（３）をｓｕｍ（３）に加算する（Ｐ２２）。
【０１００】
また、スレッド＃０〜＃３が中間データを生成し終えると、スレッド＃０〜＃２と並列に、スレッド＃３は、ポインタ配列４４を参照してｓｕｍ０（４）にアクセスし、ｓｕｍ０（４）をｓｕｍ（４）に加算する。スレッド＃３は、ポインタ配列４４を参照してｓｕｍ１（４）にアクセスし、ｓｕｍ１（４）をｓｕｍ（４）に加算する。スレッド＃３は、ポインタ配列４４を参照してｓｕｍ２（４）にアクセスし、ｓｕｍ２（４）をｓｕｍ（４）に加算する。スレッド＃３は、ポインタ配列４４を参照してｓｕｍ３（４）にアクセスし、ｓｕｍ３（４）をｓｕｍ（４）に加算する（Ｐ２３）。
【０１０１】
そして、バリア同期によって、スレッド＃０〜＃３が中間データを集計し終えるのを待ち合わせる。スレッド＃０〜＃３が中間データを集計し終えると、スレッド＃０はスタック領域１２１ａから配列４３ａを削除してよい。スレッド＃１はスタック領域１２１ｂから配列４３ｂを削除してよい。スレッド＃２はスタック領域１２１ｃから配列４３ｃを削除してよい。スレッド＃３はスタック領域１２１ｄから配列４３ｄを削除してよい。
【０１０２】
次に、並列計算装置１００とコンパイル装置２００の機能について説明する。
図１４は、並列計算装置とコンパイル装置の機能例を示すブロック図である。
並列計算装置１００は、スタック領域１２１ａ〜１２１ｄ、共有領域１２２およびスレッド１２３ａ〜１２３ｄを有する。スタック領域１２１ａ〜１２１ｄおよび共有領域１２２は、ＲＡＭ１０２に確保した記憶領域として実現できる。スレッド１２３ａ〜１２３ｄは、ＣＰＵ１０１に実行させるプログラムモジュールとして実現できる。スレッド１２３ａ〜１２３ｄを実現するプログラムモジュールは、コンパイル装置２００によって生成される。スレッド１２３ａはＣＰＵコア１０１ａによって実行される。スレッド１２３ｂはＣＰＵコア１０１ｂによって実行される。スレッド１２３ｃはＣＰＵコア１０１ｃによって実行される。スレッド１２３ｄはＣＰＵコア１０１ｄによって実行される。
【０１０３】
スタック領域１２１ａは配列４３ａを記憶する。スタック領域１２１ｂは配列４３ｂを記憶する。スタック領域１２１ｃは配列４３ｃを記憶する。スタック領域１２１ｄは配列４３ｄを記憶する。共有領域１２２は、配列４２およびポインタ配列４４を記憶する。
【０１０４】
スレッド１２３ａは、スタック領域１２１ａに配列４３ａを生成し、配列４３ａのアドレスをポインタ配列４４に格納する。また、スレッド１２３ａは、二次元配列４１の列集合のうちスレッド１２３ａに割り当てられた列について配列演算を行い、中間データを配列４３ａに格納する。また、スレッド１２３ａは、ポインタ配列４４を参照して配列４３ａ〜４３ｄにアクセスし、配列４３ａ〜４３ｄの行集合のうちスレッド１２３ａに割り当てられた行についてリダクション演算を行い、結果データを配列４２に格納する。
【０１０５】
同様に、スレッド１２３ｂは、スタック領域１２１ｂに配列４３ｂを生成し、配列４３ｂのアドレスをポインタ配列４４に格納する。また、スレッド１２３ｂは、二次元配列４１の列集合のうちスレッド１２３ｂに割り当てられた列について配列演算を行い、中間データを配列４３ｂに格納する。また、スレッド１２３ｂは、ポインタ配列４４を参照して配列４３ａ〜４３ｄにアクセスし、配列４３ａ〜４３ｄの行集合のうちスレッド１２３ｂに割り当てられた行についてリダクション演算を行い、結果データを配列４２に格納する。
【０１０６】
スレッド１２３ｃは、スタック領域１２１ｃに配列４３ｃを生成し、配列４３ｃのアドレスをポインタ配列４４に格納する。また、スレッド１２３ｃは、二次元配列４１の列集合のうちスレッド１２３ｃに割り当てられた列について配列演算を行い、中間データを配列４３ｃに格納する。また、スレッド１２３ｃは、ポインタ配列４４を参照して配列４３ａ〜４３ｄにアクセスし、配列４３ａ〜４３ｄの行集合のうちスレッド１２３ｃに割り当てられた行についてリダクション演算を行い、結果データを配列４２に格納する。
【０１０７】
スレッド１２３ｄは、スタック領域１２１ｄに配列４３ｄを生成し、配列４３ｄのアドレスをポインタ配列４４に格納する。また、スレッド１２３ｄは、二次元配列４１の列集合のうちスレッド１２３ｄに割り当てられた列について配列演算を行い、中間データを配列４３ｄに格納する。また、スレッド１２３ｄは、ポインタ配列４４を参照して配列４３ａ〜４３ｄにアクセスし、配列４３ａ〜４３ｄの行集合のうちスレッド１２３ｄに割り当てられた行についてリダクション演算を行い、結果データを配列４２に格納する。
【０１０８】
なお、スレッド１２３ａは、図１３のスレッド＃０に対応する。スレッド１２３ｂは、図１３のスレッド＃１に対応する。スレッド１２３ｃは、図１３のスレッド＃２に対応する。スレッド１２３ｄは、図１３のスレッド＃３に対応する。
【０１０９】
コンパイル装置２００は、ソースコード記憶部２２１、中間コード記憶部２２２、オブジェクトコード記憶部２２３、フロントエンド部２２４、最適化部２２５およびバックエンド部２２６を有する。ソースコード記憶部２２１、中間コード記憶部２２２およびオブジェクトコード記憶部２２３は、ＲＡＭ２０２またはＨＤＤ２０３に確保した記憶領域として実現できる。フロントエンド部２２４、最適化部２２５およびバックエンド部２２６は、ＣＰＵ２０１に実行させるプログラムモジュールとして実現できる。
【０１１０】
ソースコード記憶部２２１は、ユーザが作成したソースコード（図７のソースコード５１など）を記憶する。ソースコードは、Ｆｏｒｔｒａｎなどの高級言語を用いて記述されている。ソースコードは、並列処理用に作成されていなくてもよい。また、ソースコードには、並列化を指示するＯｐｅｎＭＰ指示文が付加されていてもよい。中間コード記憶部２２２は、ソースコードから変換された中間コードを記憶する。中間コードは、コンパイル装置２００の内部で使用される中間言語を用いて記述されている。オブジェクトコード記憶部２２３は、ソースコードに対応する機械可読なオブジェクトコードを記憶する。オブジェクトコードは、並列計算装置１００によって実行される。
【０１１１】
フロントエンド部２２４は、コンパイルのフロントエンド処理を行う。すなわち、フロントエンド部２２４は、ソースコード記憶部２２１からソースコードを読み出し、読み出したソースコードを解析する。ソースコードの解析には、字句解析、構文解析および意味解析が含まれる。フロントエンド部２２４は、ソースコードに対応する中間コードを生成し、生成した中間コードを中間コード記憶部２２２に格納する。
【０１１２】
最適化部２２５は、中間コード記憶部２２２から中間コードを読み出し、実行効率の高いオブジェクトコードが生成されるように、中間コードに対して各種の最適化を行う。最適化には、複数のＣＰＵコアを利用した並列化が含まれる。最適化部２２５は、自動並列化機能を有する場合、中間コードの中から並列化可能な処理を検出し、複数のスレッドが並列に実行されるように中間コードを書き換える。また、ソースコードにＯｐｅｎＭＰ指示文が付加され、それを有効にするコンパイルオプションが指定されていた場合、最適化部２２５は、ＯｐｅｎＭＰ指示文が付加された処理を並列化するように中間コードを書き換える。特に、ソースコードにリダクション指示文が付加されている場合、最適化部２２５は、複数のスレッドがリダクション処理を行うように中間コードを書き換える。
【０１１３】
バックエンド部２２６は、コンパイルのバックエンド処理を行う。すなわち、バックエンド部２２６は、中間コード記憶部２２２から最適化済みの中間コードを読み出し、読み出した中間コードをオブジェクトコードに変換する。バックエンド部２２６は、中間コードからアセンブリ言語で記述されたアセンブリコードを生成し、アセンブリコードをオブジェクトコードに変換するようにしてもよい。バックエンド部２２６は、生成したオブジェクトコードをオブジェクトコード記憶部２２３に格納する。
【０１１４】
図１５は、リダクション処理の手順例を示すフローチャートである。
ここでは、コンパイル装置２００が生成したオブジェクトコードに基づいて起動されたスレッド１２３ａの処理について説明する。スレッド１２３ｂ〜１２３ｄも、同じオブジェクトコードに基づいて起動され、スレッド１２３ａと同様の処理を行う。
【０１１５】
（Ｓ１０）スレッド１２３ａは、スレッド１２３ａに対応するスタック領域１２１ａに、配列４２（配列ｓｕｍ）のコピーである配列４３ａ（配列ｓｕｍ＿ｋ）を生成する。
（Ｓ１１）スレッド１２３ａは、共有領域１２２のポインタ配列４４（ポインタ配列ａｄｒ）の中のスレッド１２３ａに対応する行に、配列４３ａの先頭のアドレスを格納する。スレッド１２３ａのスレッドＩＤをｔｉｄとすると、アドレスを格納する行は、例えば、ポインタ配列４４のｔｉｄ×１６＋１行目である。
【０１１６】
（Ｓ１２）スレッド１２３ａは、配列４３ａを初期化する。リダクション演算子が「＋」である場合、スレッド１２３ａは、配列４３ａの各行を０に初期化する。
（Ｓ１３）スレッド１２３ａは、中間データを生成し、生成した中間データを配列４３ａに格納する。例えば、スレッド１２３ａは、二次元配列４１の１〜４行目それぞれについて、スレッド１２３ａが担当する１，２列目の値を合計し、合計値を配列４３ａに格納する。
【０１１７】
（Ｓ１４）スレッド１２３ａは、バリア同期によって、スレッド１２３ｂ〜１２３ｄがステップＳ１３に相当する処理を完了するのを待ち合わせる。
（Ｓ１５）スレッド１２３ａは、スレッド１２３ａ〜１２３ｄのうちの１つを選択する。ここで選択したスレッドを、スレッド＃ｊと表記する。
【０１１８】
（Ｓ１６）スレッド１２３ａは、共有領域１２２のポインタ配列４４から、スレッド＃ｊに対応するアドレスを読み出す。スレッド＃ｊのスレッドＩＤをｊとすると、アドレスを読み出す行は、例えば、ポインタ配列４４のｊ×１６＋１行目である。
【０１１９】
（Ｓ１７）スレッド１２３ａは、配列４２のうちスレッド１２３ａが集計を担当する行を特定する。ここで特定した行を、行＃ｉと表記する。
（Ｓ１８）スレッド１２３ａは、ステップＳ１６で読み出したアドレスに基づいて、スレッド＃ｊに対応するスタック領域からｉ行目の中間データを読み出す。スレッド１２３ａは、読み出した中間データを、共有領域１２２の配列４２のｉ行目（ｓｕｍ（ｉ））に反映させる。リダクション演算子が「＋」である場合、スレッド１２３ａは、スレッド＃ｊに対応するスタック領域から読み出した値をｓｕｍ（ｉ）に加算する。
【０１２０】
（Ｓ１９）スレッド１２３ａは、ステップＳ１５でスレッド１２３ａ〜１２３ｄの全てを選択したか判断する。全てのスレッドを選択した場合はステップＳ２０に処理が進み、未選択のスレッドがある場合はステップＳ１５に処理が進む。
【０１２１】
（Ｓ２０）スレッド１２３ａは、バリア同期によって、スレッド１２３ｂ〜１２３ｄがステップＳ１５〜Ｓ１９に相当する処理を完了するのを待ち合わせる。
（Ｓ２１）スレッド１２３ａは、スタック領域１２１ａから配列４３ａを削除することを許可する。スレッド１２３ａは、リダクション処理を終了する。
【０１２２】
図１６は、コンパイルの手順例を示すフローチャートである。
（Ｓ３０）フロントエンド部２２４は、ソースコード記憶部２２１からソースコードを読み出し、ソースコードを解析して中間コードに変換する。フロントエンド部２２４は、中間コードを中間コード記憶部２２２に格納する。以下のステップＳ３１〜Ｓ３８において、最適化部２２５は、中間コードに対して並列化のための処理を行う。
【０１２３】
（Ｓ３１）最適化部２２５は、リダクション指示文で指定されたリダクション変数をコピーしたプライベート変数を、中間コードに追加する。プライベート変数のデータ型・配列長・次元などの属性は、オリジナルのリダクション変数と同じである。
【０１２４】
（Ｓ３２）最適化部２２５は、ポインタ配列を示す共有変数を中間コードに追加する。ポインタ配列の長さは、オブジェクトコードを実行させるＣＰＵの最大スレッド数（例えば、ＣＰＵコア数）とキャッシュラインサイズから決定する。
【０１２５】
（Ｓ３３）最適化部２２５は、ステップＳ３１のプライベート変数のアドレス（例えば、ＲＡＭ１０２の物理アドレス）をポインタ配列に格納するコードを、中間コードに追加する。アドレスを格納する行は、スレッドＩＤから算出されるようにする。
【０１２６】
（Ｓ３４）最適化部２２５は、ステップＳ３１のプライベート変数を初期化するコードを、中間コードに追加する。プライベート変数の初期値は、リダクション指示文で指定されたリダクション演算子から決定する。
【０１２７】
（Ｓ３５）最適化部２２５は、中間コードに含まれるリダクション変数へのアクセスを、ステップＳ３１のプライベート変数へのアクセスに置換する。
（Ｓ３６）最適化部２２５は、ポインタ配列に格納されている各スレッドに対応するアドレスを読み出すコードを、中間コードに追加する。
【０１２８】
（Ｓ３７）最適化部２２５は、ステップＳ３６のアドレスが指すプライベート変数に格納された中間データを用いてリダクション変数を更新するコードを、中間コードに追加する。リダクション変数の更新は、指定されたリダクション演算子によって行う。
【０１２９】
（Ｓ３８）最適化部２２５は、ステップＳ３６のコードの直前に、複数のスレッドの間でバリア同期を行うコードを追加する。また、ステップＳ３７のコードの直後に、複数のスレッドの間でバリア同期を行うコードを追加する。
【０１３０】
（Ｓ３９）バックエンド部２２６は、中間コード記憶部２２２から最適化済みの中間コードを読み出し、中間コードをオブジェクトコードに変換する。バックエンド部２２６は、オブジェクトコードをオブジェクトコード記憶部２２３に格納する。
【０１３１】
第３の実施の形態の情報処理システムによれば、ＣＰＵコア１０１ａ〜１０１ｄを用いてスレッド１２３ａ〜１２３ｄが起動され、スレッド１２３ａ〜１２３ｄに対応するスタック領域１２１ａ〜１２１ｄに分散して中間データが格納される。また、中間データの位置を示すアドレスが共有領域１２２に格納される。そして、共有領域１２２に格納されたアドレスに基づいて各スレッドからスタック領域１２１ａ〜１２１ｄがアクセスされ、スレッド１２３ａ〜１２３ｄによって並列に中間データが集計される。
【０１３２】
これにより、中間データを共有領域１２２に格納する方法と比べて、共有領域１２２に動的に中間データの領域を確保するオーバヘッドを削減できる。また、各スレッドが当該スレッドの中間データを共有領域１２２の結果データに反映させる方法と比べて、スレッド１２３ａ〜１２３ｄの間で排他制御を行わなくてよく、排他制御のオーバヘッドを削減できる。また、中間データの集計を並列化できる。また、中間データの集計を、中間データを生成したスレッド１２３ａ〜１２３ｄに実行させるため、新たなスレッドを起動しなくてよく、スレッド起動のオーバヘッドを削減できる。よって、スレッド１２３ａ〜１２３ｄによるリダクション処理を高速化することができる。
【０１３３】
なお、前述のように、第１の実施の形態の情報処理は、並列計算装置１０にプログラムを実行させることで実現できる。第２の実施の形態の情報処理は、コンパイル装置２０にプログラムを実行させることで実現できる。第３の実施の形態の情報処理は、並列計算装置１００およびコンパイル装置２００にプログラムを実行させることで実現できる。
【０１３４】
プログラムは、コンピュータ読み取り可能な記録媒体（例えば、記録媒体１１３，２１３）に記録しておくことができる。記録媒体として、例えば、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤおよびＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤおよびＤＶＤ−Ｒ／ＲＷが含まれる。プログラムは、可搬型の記録媒体に記録されて配布されることがある。その場合、可搬型の記録媒体からＨＤＤなどの他の記録媒体（例えば、ＨＤＤ１０３，２０３）にプログラムをコピーして実行してもよい。
【符号の説明】
【０１３５】
１０  並列計算装置
１１，１２  演算部
１３，２１  記憶部
１３ａ，１３ｂ  個別領域
１３ｃ  共有領域
１４ａ，１４ｂ  スレッド
１５ａ，１５ｂ，１５ｄ  データ
１５ｃ  アドレス情報
２０  コンパイル装置
２２  変換部
２３，２４  コード
２３ａ，２４ａ，２４ｂ，２４ｃ，２４ｄ  命令
【図１】
0006432450.tif 000002
【図２】
0006432450.tif 000003
【図３】
0006432450.tif 000004
【図４】
0006432450.tif 000005
【図５】
0006432450.tif 000006
【図６】
0006432450.tif 000007
【図７】
0006432450.tif 000008
【図８】
0006432450.tif 000009
【図９】
0006432450.tif 000010
【図１０】
0006432450.tif 000011
【図１１】
0006432450.tif 000012
【図１２】
0006432450.tif 000013
【図１３】
0006432450.tif 000014
【図１４】
0006432450.tif 000015
【図１５】
0006432450.tif 000016
【図１６】
0006432450.tif 000017