JPH07244647A

JPH07244647A - 間接参照ループの並列化方法、並列化装置、並列実行方法および並列実行装置

Info

Publication number: JPH07244647A
Application number: JP6062045A
Authority: JP
Inventors: Hiroshi Ota; 寛太田; Tetsuro Saito; 鉄郎斉藤; Masahiro Uminaga; 正博海永; Yasuhiko Saito; 靖彦斎藤
Original assignee: Hitachi Microcomputer System Ltd; Hitachi Ltd
Current assignee: Hitachi Microcomputer System Ltd; Hitachi Ltd
Priority date: 1994-03-07
Filing date: 1994-03-07
Publication date: 1995-09-19

Abstract

(57)【要約】【目的】一般的な間接参照ループの並列実行および並
列化を可能にし、特に、間接参照が左辺にある場合の並
列実行および並列化を可能とすることにある。【構成】配列の添字が配列になっている間接参照が代
入文の左辺に現われるループに対して、最終イタレーシ
ョン配列の宣言文をプログラム内に挿入し、該最終イタ
レーション配列の初期化文を挿入し、参照されている配
列要素が自プロセッサにあるか他プロセッサにあるかを
判定する文を挿入し、最終イタレーション配列にイタレ
ーションインデックスを記録する文を挿入し、他プロセ
ッサにある場合に該配列要素についての代入情報を代入
リストに登録する文を挿入し、該代入リストをプロセッ
サ間で交換する代入リスト交換文を挿入し、該交換され
た代入リストを用いて他プロセッサの配列要素の値を自
プロセッサの配列要素に代入する文を挿入する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、逐次処理計算機用に記
述された間接参照ループを含むプログラムを、分散メモ
リ型の並列計算機上で実行可能なプログラムに変換する
プログラム並列化方法及び装置と、間接参照ループの並
列実行方法及び装置に関する。

【０００２】

【従来の技術】複数のプロセッサから構成される並列計
算機システムにおいて、各プロセッサごとに固有のメモ
リを備えているものを、分散メモリ型並列計算機と呼ん
でいる。科学技術計算などに現われる大規模配列の処理
を分散メモリ型並列計算機で実行するときは、配列の各
要素を各プロセッサのメモリに分割して割り付け、各要
素に対する処理を各プロセッサで並列に実行するという
方式が、通常用いられる。このような方式を実現するプ
ログラムを作成する一つの方法は、並列化コンパイラを
用いることである。

【０００３】並列化コンパイラは、逐次処理用言語で記
述されたプログラムを並列計算機用プログラムに変換す
る言語プロセッサである。分散メモリ型並列計算機用の
並列化コンパイラは、配列要素や、ループの繰り返し
（以後、ループの繰り返し単位をイタレーションと呼
ぶ。例えば、ｉ＝２のイタレーションという。）を各プ
ロセッサへ分割して割り当て、必要ならばデータ転送文
や同期文を挿入して、各プロセッサ用のプログラムを生
成する。あるイタレーションで参照される配列要素が自
プロセッサに割り当てられている場合に、その配列要素
参照を「ｌｏｃａｌ参照」と呼び、また、他プロセッサ
に割り当てられている場合に「ｒｅｍｏｔｅ参照」と呼
ぶ。ｒｅｍｏｔｅ参照については、プロセッサ間通信に
よって配列要素の値を転送する必要がある。そこで考慮
しなければならないのは、分散メモリ型並列計算機では
プロセッサ間通信の起動に非常に時間が掛かることであ
る。通常、ＣＰＵ演算の数百ステップ以上の起動時間を
必要とする。したがって、個々のｒｅｍｏｔｅ参照毎に
通信を行っていたのでは、起動オーバーヘッドのために
性能が非常に低下してしまう。そのため、分散メモリ型
並列計算機では、複数の配列要素をまとめて転送して通
信回数を低減する工夫が、非常に重要である。

【０００４】配列要素参照がａ［ｉ＋１］のように単純
な線形添字を持つならば、ｒｅｍｏｔｅ参照される配列
要素の範囲をコンパイル時に決定でき、配列要素をまと
めて転送する文を比較的容易に生成できる。しかし、添
字がもっと複雑な場合には転送文の生成はより難しくな
る。特に問題となるのは以下に述べる間接参照の場合で
ある。間接参照とは添字が配列要素になっている配列要
素参照、例えばａ［ｐ［ｉ］］のような参照である。間
接参照を含むループのことを間接参照ループと呼ぶ。間
接参照ループは、有限要素法などで生じる粗行列の計算
やピボット交換付きガウス消去法などの現実の問題に頻
繁に現われる。間接参照ループの特徴は、添字の値が実
行時まで不明なため、ｒｅｍｏｔｅ参照される要素をコ
ンパイル時にまとめてデータ転送文を生成することが不
可能なことである。そのため、間接参照ループは添字が
線形であるようなループに比べて並列化が困難である。
間接参照ループの並列化方法に関する従来技術としては
ＫｏｅｌｂｅｌａｎｄＭｅｈｒｏｔｒａ， ”Ｃ
ｏｍｐｉｌｉｎｇＧｌｏｂａｌＮａｍｅ−Ｓｐａｃ
ｅＰａｒａｌｌｅｌＬｏｏｐｓｆｏｒＤｉｓｔ
ｒｉｂｕｔｅｄＥｘｅｃｕｔｉｏｎ”，ＩＥＥＥＴ
ｒａｎｓ．ｏｎＰａｒａｌｌｅｌａｎｄＤｉｓｔ
ｒｉｂｕｔｅｄＳｙｓｔｅｍｓ，Ｖｏｌ．２，Ｎ
ｏ．４，ｐｐ．４４０−４５１，１９９１年があ
る。そこでは、間接参照ループを、次のような並列実行
方法に基づくループに並列化した。その並列実行方法と
は、ｒｅｍｏｔｅ参照される配列要素の位置情報を含む
リストを作成する「ｉｎｓｐｅｃｔｏｒループ」を、プ
ログラムの最初で予め実行しておくものであった。添字
配列の値が全プログラムを通じて不変ならば、ｉｎｓｐ
ｅｃｔｏｒループは全プログラムを通じて１回だけ実行
すればよいことになる。後は、間接参照ループの度にそ
のリストに基づいてｒｅｍｏｔｅ参照される要素をまと
めて転送することができる。また別の従来技術として
は、窪田、三吉、大野、森、中島、富田、”分散メモリ
型並列計算機の自動並列化コンパイラ−Ｉｎｓｐｅｃｔ
ｏｒ／Ｅｘｅｃｕｔｏｒアルゴリズムの高速化−”，
並列処理シンポジウムＪＳＰＰ’９３，ｐｐ．４７−
５４がある。そこでは、前述の従来技術に基づいて、
添字配列が置換になっているなどの特殊な場合にｉｎｓ
ｐｅｃｔｏｒループを高速化する方法が提案されてい
る。

【０００５】

【発明が解決しようとする課題】従来の方法では、並列
化対象としている間接参照ループに特殊な条件があっ
た。すなわち、添字配列の値がプログラムを通じて不変
であることや、添字配列の値が置換になっていることな
どの制限があった。また、上記の従来技術には、並列化
された間接参照ループの形は示されていたが、間接参照
ループをそのような形に変換するための並列化手順は、
明確に述べられていなかった。さらに、従来の方法で
は、間接参照が代入文の左辺にある場合に生じる問題に
対処していなかった。すなわち、ｆｏｒ（ｉ＝０；ｉ＜Ｎ；ｉ＋＋）ａ［ｐ［ｉ］］＝ｂ［ｉ］；のようなループ（ここで、上記文はＣ言語によるもので
あり、ｉ＋＋はｉを順次増加することを意味する。ま
た、式の右辺は既知の値であり、左辺は、いわば未知の
値であり、右辺の既知の値によって決まる。）では、異
なるｉに対してｐ［ｉ］が同じ値を取ったときに、異な
るイタレーションが配列ａの同一の要素を書き換える。
それらのうち、最後のイタレーションによって書かれた
値のみがループ終了後の値として残る。例えば、ａ［ｐ
［２］］＝ｂ［２］でｐ［２］＝１２であり、ａ［ｐ
［６］］＝ｂ［６］でｐ［６］＝１２であったとする
と、ａ［１２］の値としてはｂ［６］が残る。このルー
プを並列実行する場合は、ループ終了後の各配列要素が
並列実行ではない逐次実行のときと同じ値を持つように
しなければならないが、従来の方法は、その問題に対処
していなかった。本発明の目的は、一般的な間接参照ル
ープの並列実行および並列化を可能とすることにある。
特に、間接参照が左辺にある場合の並列実行および並列
化を可能とすることにある。

【０００６】

【課題を解決するための手段】逐次処理プログラムまた
は共有メモリ型並列計算機用プログラムを分散メモリ型
並列計算機プログラムに変換するプログラム並列化方法
において、配列の添字が配列になっている間接参照を含
むループに対して、参照されている配列要素が自プロセ
ッサにあるか他プロセッサにあるかを判定する文を、該
間接参照ループ内に挿入するステップと、参照されてい
る配列要素が他プロセッサにある場合に該配列要素につ
いての情報をリストに登録する文を、該間接参照ループ
内に挿入するステップと、該リストをプロセッサ間で交
換するリスト交換文を、該間接参照ループの後に挿入す
るステップと、該交換されたリストを用いて他プロセッ
サの配列要素の値を自プロセッサの配列要素に代入する
文を、該リスト交換文の後に挿入するステップとを含む
ようにしている。また、配列の添字が配列になっている
間接参照ループを分散メモリ型並列計算機で並列実行す
る方法において、参照されている配列要素が自プロセッ
サにあるか他プロセッサにあるかを該間接参照ループ内
で判定するステップと、自プロセッサにある場合に該配
列要素への代入をするステップと、他プロセッサにある
場合に該配列要素についての情報を該間接参照ループ内
でリストに登録するステップと、該間接参照ループ終了
後に該リストをプロセッサ間で交換するステップと、該
交換されたリストを用いて他プロセッサの配列要素の値
を自プロセッサの配列要素に代入するステップとを含む
ようにしている。また、逐次処理プログラムまたは共有
メモリ型並列計算機用プログラムを分散メモリ型並列計
算機プログラムに変換するプログラム並列化装置におい
て、配列の添字が配列になっている間接参照を含むルー
プに対して、参照されている配列要素が自プロセッサに
あるか他プロセッサにあるかを判定する文を、該間接参
照ループ内に挿入する手段と、参照されている配列要素
が他プロセッサにある場合に該配列要素についての情報
をリストに登録する文を、該間接参照ループ内に挿入す
る手段と、該リストをプロセッサ間で交換するリスト交
換文を、該間接参照ループの後に挿入する手段と、該交
換されたリストを用いて他プロセッサの配列要素の値を
自プロセッサの配列要素に代入する文を、該リスト交換
文の後に挿入する手段とを備えるようにしている。ま
た、配列の添字が配列になっている間接参照ループを分
散メモリ型並列計算機で並列実行する装置において、参
照されている配列要素が自プロセッサにあるか他プロセ
ッサにあるかを判定する手段と、自プロセッサにある場
合に該配列要素への代入をする手段と、他プロセッサに
ある場合に該配列要素についての情報をリストに登録す
る手段と、該リストをプロセッサ間で交換する手段と、
該交換されたリストを用いて他プロセッサの配列要素の
値を自プロセッサの配列要素に代入する手段とを備える
ようにしている。また、プログラム並列化方法におい
て、配列の添字が配列になっている間接参照が代入文の
右辺に現われるループに対して、参照されている配列要
素が自プロセッサにあるか他プロセッサにあるかを判定
する文を、該間接参照ループ内に挿入するステップと、
他プロセッサにある場合に該配列要素についての位置情
報を位置リストに登録する文を、該間接参照ループ内に
挿入するステップと、該位置リストをプロセッサ間で交
換する位置リスト交換文を、該間接参照ループの後に挿
入するステップと、該交換された位置リストを用いて、
他プロセッサから参照されている配列要素の値を含む値
リストを作成する文を、該位置リスト交換文の後に挿入
するステップと、該値リストをプロセッサ間で交換する
値リスト交換文を、該値リスト作成文の後に挿入するス
テップと、該交換された値リストを用いて他プロセッサ
の配列要素の値を自プロセッサの配列要素に代入する文
を、該値リスト交換文の後に挿入するステップとを含む
ようにしている。また、並列実行する方法において、参
照されている配列要素が自プロセッサにあるか他プロセ
ッサにあるかを、該間接参照ループ内で判定するステッ
プと、自プロセッサにある場合に該配列要素への代入を
するステップと、他プロセッサにある場合に該配列要素
についての位置情報を該間接参照ループ内で位置リスト
に登録するステップと、該間接参照ループ終了後に該位
置リストをプロセッサ間で交換するステップと、該交換
された位置リストを用いて、他プロセッサから参照され
ている配列要素の値を含む値リストを作成するステップ
と、該値リストをプロセッサ間で交換するステップと、
該交換された値リストを用いて他プロセッサの配列要素
の値を自プロセッサの配列要素に代入するステップとを
含むようにしている。また、プログラム並列化方法にお
いて、配列の添字が配列になっている間接参照が代入文
の左辺に現われるループに対して、間接参照されている
配列の要素を最後に書き換えたイタレーションのインデ
ックスを記録する最終イタレーション配列の宣言文をプ
ログラム内に挿入するステップと、該最終イタレーショ
ン配列の初期化文を該間接参照ループの前に挿入するス
テップと、参照されている配列要素が自プロセッサにあ
るか他プロセッサにあるかを判定する文を、該間接参照
ループ内に挿入するステップと、最終イタレーション配
列にイタレーションインデックスを記録する文を、該間
接参照ループ内に挿入するステップと、他プロセッサに
ある場合に該配列要素についての代入情報を代入リスト
に登録する文を、該間接参照ループ内に挿入するステッ
プと、該代入リストをプロセッサ間で交換する代入リス
ト交換文を、該間接参照ループの後に挿入するステップ
と、該交換された代入リストを用いて他プロセッサの配
列要素の値を自プロセッサの配列要素に代入する文を、
該代入リスト交換文の後に挿入するステップとを含むよ
うにしている。また、プログラム並列化方法において、
配列の添字が配列になっている間接参照が加算代入文の
左辺に現われるループに対して、参照されている配列要
素が自プロセッサにあるか他プロセッサにあるかを判定
する文を、該間接参照ループ内に挿入するステップと、
他プロセッサにある場合に該配列要素についての代入情
報を代入リストに登録する文を、該間接参照ループ内に
挿入するステップと、該代入リストをプロセッサ間で交
換する代入リスト交換文を、該間接参照ループの後に挿
入するステップと、該交換された代入リストを用いて他
プロセッサの配列要素の値を自プロセッサの配列要素に
加算代入する文を、該代入リスト交換文の後に挿入する
ステップとを含むようにしている。また、並列実行する
方法において、参照されている配列要素が自プロセッサ
にあるか他プロセッサにあるかを、該間接参照ループ内
で判定するステップと、自プロセッサにある場合に該配
列要素への加算代入をするステップと、他プロセッサに
ある場合に該配列要素についての代入情報を該間接参照
ループ内で代入リストに登録するステップと、該間接参
照ループ終了後に該代入リストをプロセッサ間で交換す
るステップと、該交換された代入リストを用いて他プロ
セッサの配列要素の値を自プロセッサの配列要素に加算
代入するステップとを含むようにしている。

【０００７】

【作用】本発明の並列実行方法によれば、間接参照ルー
プの実行中にｒｅｍｏｔｅ参照に関する情報のリストを
作成するので、添字配列がプログラム内で変化する場合
でも並列実行可能である。また、左辺に間接参照がある
場合でも、配列要素を書き換えたイタレーションのイン
デックスが記録されているので、最後のイタレーション
によって書き換えられた値のみを、ループ終了後に残す
ことができる。また、本発明の並列化方法によれば、上
記の並列実行方法を実現するプログラムが生成できる。

【０００８】

【実施例】以下、図面を用いて本発明の実施例を説明す
る。図１は、本発明の一実施例に係わるプログラム並列
化方法の手順を示すフローチャートである。図１を参照
してプログラム並列化について説明する前に、本発明に
より並列化されたプログラムが動作する並列計算機の構
成、および、その並列計算機上での本発明による間接参
照ループの並列実行方法について説明する。図２は本発
明の適用対象である分散メモリ型並列計算機の構成の一
例である。この並列計算機は、本発明のプログラム並列
化方法によって並列化されたプログラムを実行する。並
列計算機は複数のプロセッサ２０１から２０ｎ、各プロ
セッサに付随するローカルメモリ２１１から２１ｎ、そ
してそれらを結合する相互結合ネットワーク２２から構
成される。各ローカルメモリ上のデータは、それが付随
するプロセッサからは直接参照できるが、他のプロセッ
サからは直接参照することはできない。あるプロセッサ
に付随するデータを他のプロセッサから参照するために
は、そのデータは相互結合ネットワーク２２を通じて転
送されなければならない。

【０００９】図３に間接参照ループの一例を示す。１行
目は実数型の１００００個の要素から成る配列ａ，ｂの
宣言文、２行目は整数型の１００００個の要素から成る
配列ｐの宣言文である。３行目から５行目までが間接参
照ループである。４行目の代入文の右辺の配列ｂの添字
が配列ｐになっている。このループを分散メモリ型並列
計算機で実行する場合、ループのイタレーションと配列
要素を分割して各プロセッサに割り当てる。例えば、プロセッサ１：イタレーション０から９９、配列ａ
［０］からａ［９９］、ｂ［０］からｂ［９９］、ｐ
［０］からｐ［９９］プロセッサ２：イタレーション１００から１９９、配
列ａ［１００］からａ［１９９］、ｂ［１００］からｂ
［１９９］、ｐ［１００］からｐ［１９９］以下同様のように割り当てる。ここでイタレーションの番号は変
数ｉの値で表している。このように割り当てれば、ある
イタレーションｉを実行するときに、配列要素参照ａ
［ｉ］とｐ［ｉ］は必ず自プロセッサに割り当てられて
いる。すなわちｌｏｃａｌ参照である。しかし、配列要
素参照ｂ［ｐ［ｉ］］については、自プロセッサに割り
当てられているとは限らない。すなわちｒｅｍｏｔｅ参
照の可能性がある。ｂ［ｐ［ｉ］］がｌｏｃａｌ参照か
ｒｅｍｏｔｅ参照かはｐ［ｉ］の値によって決まり、プ
ログラムの実行時まで確定しない。この状況を考慮しな
がら、この間接参照ループの並列実行方法について説明
する。なお、以下では、配列要素が割り当てられている
プロセッサを「所有者」と呼び、その要素を参照してい
るイタレーションが割り当てられているプロセッサを
「参照者」と呼ぶ（例えば、ｂ［ｐ［２］］＝ｂ［１２
０］のとき、要素ｂ［１２０］を参照しているｉ＝２の
イタレーションが割り当てられているプロセッサはプロ
セッサ１であり、この場合のプロセッサ１は参照者であ
る。）。また、間接参照されている配列要素のインデッ
クス、すなわち、ｐ［ｉ］の値（例えば、先の例でｐ
［２］の値１２０）のことを「所有者インデックス」、
イタレーションのインデックスｉ（例えば、先の例でｉ
＝２）のことを「参照者インデックス」と呼ぶ。

【００１０】図５は、図２の並列計算機上での、図３の
間接参照ループの本発明による並列実行方法の手順を示
すフローチャートである。本手順は、並列計算機の各プ
ロセッサ２０１から２０ｎが実行するものである。ま
ず、各プロセッサは、自身に割り当てられたイタレーシ
ョンの各々について、ステップ４００からステップ４０
３の処理を行う。全イタレーションについての処理が終
了した後で、ステップ４０４からステップ４０７の処理
を実行する。以下では各ステップの処理の詳細を述べ
る。ステップ４００は自身に割り当てられたイタレーシ
ョンのうち、未処理のものがまだあるかどうかの判定で
ある。未処理のイタレーションがあればステップ４０１
に進み、以下、そのイタレーションについての処理を行
う。ステップ４０１で間接参照ｂ［ｐ［ｉ］］がｌｏｃ
ａｌ参照かｒｅｍｏｔｅ参照かを判定する。ループの実
行時には添字配列ｐ［ｉ］の値は確定しているのでこの
判定が可能である。もしｌｏｃａｌ参照ならばステップ
４０２に進み、ｒｅｍｏｔｅ参照ならばステップ４０３
に進む。ステップ４０２でｌｏｃａｌ参照についての代
入を実行する。ｌｏｃａｌ参照されている配列要素は自
プロセッサ上にあるので、この代入に際してプロセッサ
間通信は必要ない。ステップ４０３ではｒｅｍｏｔｅ参
照についての位置情報を位置リストに登録する。ここで
位置情報とは、要素ｂ［ｐ［ｉ］］の所有者のプロセッ
サ番号（例えば、ｂ［ｐ［２］］＝ｂ［１２０］であれ
ば、所有者のプロセッサ番号は２である。）、所有者イ
ンデックスｐ［ｉ］の値（例えば、ｐ［２］＝１２０な
ら値は１２０である。）、および参照者インデックスｉ
の値（例えば、ｂ［ｐ［２］］なら、この値は２であ
る。）である。位置リストの構造は図６を用いて後述す
る。ステップ４００で未処理のイタレーションがもうな
ければステップ４０４に進み、以下、位置リストに基づ
いてｒｅｍｏｔｅ参照の後処理をする。ステップ４０４
に進んだ時点では、各プロセッサの位置リストには、自
身が参照者であるようなｒｅｍｏｔｅ参照についての位
置情報が登録されている。これを「参照者側位置リス
ト」と呼ぶ。ステップ４０４では、ｒｅｍｏｔｅ参照の
位置情報が参照者から所有者に渡るように、全プロセッ
サ間で位置リストを交換する。このとき参照者情報も渡
される。交換方法としては、例えば、Ｊｏｈｎｓｓｏｎ
ａｎｄＨｏ， ”ＯｐｔｉｍｕｍＢｒｏａｄｃａ
ｓｔｉｎｇａｎｄＰｅｒｓｏｎａｌｉｚｅｄＣｏ
ｍｍｕｎｉｃａｔｉｏｎｉｎＨｙｐｅｒｃｕｂｅ
ｓ”，ＩＥＥＥＴｒａｎｓ．ｏｎＣｏｍｐｕｔ
ｅｒｓ，Ｖｏｌ．３８，Ｎｏ．９，ｐｐ．１２４
９−１２６８，１９８９年に述べられている全対全
通信などの方法を用いれば良い。この交換により、各プ
ロセッサは、自身が所有者であるようなｒｅｍｏｔｅ参
照についての位置リストを持つようになる。これを「所
有者側位置リスト」と呼ぶ。ステップ４０５では、所有
者側位置リストに基づいて、自身が所有者となっている
ｒｅｍｏｔｅ参照の値を含む値リスト（これを「所有者
側値リスト」と呼ぶ）を作成する。値リストの構造は図
７を用いて後述する。ステップ４０６で、ｒｅｍｏｔｅ
参照の値が所有者から参照者に渡るように、値リストを
全プロセッサ間で交換する。この交換により、各プロセ
ッサは、自身が参照者であるようなｒｅｍｏｔｅ参照に
ついての値リストを持つようになる。これを「参照者側
値リスト」と呼ぶ。ステップ４０７で、参照者側値リス
トに基づいて、自身が参照者であるｒｅｍｏｔｅ参照に
ついて、ｂ［ｐ［ｉ］］の値を左辺の配列要素ａ［ｉ］
に代入する。以上の処理により、図３の間接参照ループ
の並列実行が完了した。

【００１１】次に、この並列実行方法で用いた位置リス
トや値リストの構造を説明する。図６は、参照者側位置
リストの構造を示す。所有者ごとにエントリを持つヘッ
ダ５００と、その各エントリからポインタでつながるリ
スト本体５０１によって構成される。ｒｅｍｏｔｅ参照
の各々に対して、リスト本体５０１の１エントリが対応
する。リスト本体５０１は所有者インデックスと参照者
インデックスを表す２個のフィールド５０４および５０
５から成る。ヘッダ５００には、所有者のプロセッサ番
号を表すフィールド５０２と、リスト本体に登録されて
いる対の数（登録数）を示すフィールド５０３が含まれ
る。例えば、図６の位置リストの一番最初の項目（斜線
部分）は、プロセッサ４番の持つ配列要素ｂ［６６］の
値が、このプロセッサの配列要素ａ［５］に代入される
べきことを表している。なお、所有者側位置リストの構
造は、参照者側位置リストの構造とほとんど同じである
が、ヘッダ５００内の所有者フィールド５０２が参照者
を表すフィールドに置き換わっている点だけが異なる。

【００１２】図７は、所有者側値リストの構造を示す。
位置リストと同様に、ヘッダ５１０とリスト本体５１１
から構成される。ヘッダ５１０のエントリは参照者ごと
に設ける。また、リスト本体５１１の内容は、転送すべ
き配列要素の値である。値の順序は、位置リスト内のイ
ンデックスの順序と一致するようにする。例えば、図７
の値リストの網かけ部分は、値１３．２が、プロセッサ
５番で参照されることを表している。１３．２という値
が、参照者側のどの配列要素に代入されるかは、値リス
トが参照者側に送られたときに、参照者側の位置リスト
との順序対応によって分かる。なお、参照者側値リスト
の構造は、所有者者側値リストの構造とほとんど同じで
あるが、ヘッダ５１０内の参照者フィールド５１２が所
有者を表すフィールドに置き換わっている点だけが異な
る。以上で、本発明による間接参照ループの並列実行方
法の説明を終わる。

【００１３】次に、本発明による間接参照ループの並列
実行方法のための並列実行装置について説明する。図８
は、そのような並列実行装置の一例を表す。各プロセッ
サ２０内に、演算部２３０、ｒｅｍｏｔｅ参照判定部２
３１、位置情報登録部２３２、ネットワーク制御部２３
３、値リスト作成部２３４、ｒｅｍｏｔｅ参照代入部２
３５、参照者側位置リスト２４０、所有者側位置リスト
２４１、所有者側値リスト２４２、参照者側値リスト２
４３を含む。各リスト２４０から２４３はローカルメモ
リ２１内に置くこともできる。ｒｅｍｏｔｅ参照判定部
２３１は図５のステップ４０１の処理を行う。すなわ
ち、演算部２３０から間接参照の所有者インデックスｐ
［ｉ］を受け取り、それがｌｏｃａｌ参照かｒｅｍｏｔ
ｅ参照かを判定する。位置情報登録部２３２は、図５の
ステップ４０３の処理を行う。すなわち、ｒｅｍｏｔｅ
参照についての位置情報を参照者側位置リスト２４０に
登録する。ネットワーク制御部２３３は図５のステップ
４０４およびステップ４０６の処理を行う。すなわち、
相互結合ネットワーク２２を通じて、位置リスト２４０
および２４１や値リスト２４２および２４３をプロセッ
サ間で交換する。値リスト作成部２３４は、図５のステ
ップ４０５の処理を行う。すなわち、所有者側位置リス
ト２４１に基づいて所有者側値リスト２４２を作成す
る。演算部２３０は通常の演算処理を行う。これには、
図５のステップ４０２におけるｌｏｃａｌ参照の代入実
行を含む。ｒｅｍｏｔｅ参照代入部２３５は図５のステ
ップ４０７の処理を行う。すなわち、参照者側値リスト
２４３用いて、自身が参照者であるｒｅｍｏｔｅ参照に
ついての代入を実行する。

【００１４】図１に戻って、本発明のプログラム並列化
方法の一実施例の詳細を説明する。本実施例の並列化方
法は、図３の形の間接参照ループを対象とする。すなわ
ち、次の条件を充たすループを対象とする。（１）ループの中身は１個の代入文である。（２）その代入文の両辺はそれぞれ１個の配列要素参照
である。両辺の配列は異なる。（３）左辺の配列の添字はループイタレーションのイン
デックスｉである。（４）右辺の配列の添字は、別の配列である。すなわ
ち、右辺は間接参照である。本並列化方法によって、図３の間接参照ループは図４に
示すような並列実行プログラム３０１に変換される。図
４のプログラムは図５に示した並列実行方法４０を実現
するものである。

【００１５】以下、図４のプログラムを参照しながら、
図１の並列化方法の詳細を説明する。ステップ１００
で、ループ内の代入文の前に、間接参照がｌｏｃａｌ参
照かｒｅｍｏｔｅ参照判定する文を挿入する。図４では
４行目に相当する。ここでｏｗｎｅｒ（ｐ［ｉ］）は、
インデックスの値ｐ［ｉ］から所有者プロセッサ番号を
求めるライブラリ関数である。また、＿ｓｅｌｆは自プ
ロセッサ番号を表す変数である。６行目のｅｌｓｅも本
ステップで挿入する。ステップ１０１で、ｒｅｍｏｔｅ
参照についての位置情報を位置リストに登録する文を、
ｅｌｓｅの後、すなわちｒｅｍｏｔｅ参照の場合に実行
される部分に挿入する。図４の７行目にあるｐｕｔ＿ｌ
ｏｃｉｎｆｏ（）というライブラリ手続き（図５のステ
ップ４０３の処理に対応する）の呼び出しが、その登録
文である。手続きの引数は、登録する情報、すなわち、
所有者プロセッサ番号ｏｗｎｅｒ（ｐ［ｉ］）、所有者
インデックスｐ［ｉ］、参照者インデックスｉである。
ステップ１０２からステップ１０５で、ループの後にｒ
ｅｍｏｔｅ参照の後処理を行う文を挿入する。後処理
は、ライブラリ手続き呼び出しの形をとる。ステップ１
０２では、位置リストを交換する文、すなわち、ライブ
ラリ手続きｅｘｃｈａｎｇｅ＿ｌｏｃｌｉｓｔ（）（図
５のステップ４０４の処理に対応する）の呼び出しを挿
入する。ステップ１０３では、値リストを作成する文、
すなわち、ライブラリ手続きｍａｋｅ＿ｖａｌｌｉｓｔ
（ｂ）（図５のステップ４０５の処理に対応する）の呼
び出しを挿入する。引数として、間接参照されている配
列ｂを与えている。ステップ１０４では、値リストを交
換する文、すなわち、ライブラリ手続きｅｘｃｈａｎｇ
ｅ＿ｖａｌｌｉｓｔ（）（図５のステップ４０６の処理
に対応する）の呼び出しを挿入する。ステップ１０
５では、参照者側でｒｅｍｏｔｅ参照に対する代入を実
行する文、すなわち、ライブラリ手続きｒｅｍｏｔｅ＿
ａｓｓｉｇｎ（ａ）（図５のステップ４０７の処理に対
応する）の呼び出しを挿入する。引数として、代入先の
配列ａを与えている。これらのライブラリ手続き呼び出
しは、図４の並列化後プログラムでは９行目から１２行
目に挿入されている。なお、図７の３行目のｅｐ１，ｅ
ｐ２は、各プロセッサに割り当てられたイタレーション
の範囲を表す変数であり、プロセッサごとに異なる値が
設定される。また、各プロセッサに割り当てられる配列
の範囲は、実際にはｅｐ１からｅｐ２までであるが、図
４では簡単のため、１，２行目の宣言文における配列の
サイズは１００００のままにしてある。

【００１６】以上で、本発明による間接参照ループの並
列化方法の説明を終わる。なお、本実施例および以後の
実施例では、並列化後プログラムをソースプログラムの
形式で示すが、本発明は並列化後プログラムがオブジェ
クトプログラム形式である場合でも同様に適用できる。
また、本実施例および以後の実施例では、並列化前プロ
グラムの例として図３のような逐次処理プログラムを用
いるが、並列化前プログラムが共有メモリ型並列計算機
用プログラムである場合でも、本発明は同様に適用でき
る。また、本実施例および以後の実施例では、１次元配
列および１重ループの場合を例として述べたが、多次元
配列や多重ループの場合でも同様に並列化できる。

【００１７】次に本発明の別の実施例として、代入文の
左辺に間接参照があるループの並列実行方法および並列
化方法について説明する。図９に左辺に間接参照がある
ループの一例を示す。ループ内の代入文の左辺の配列ａ
の添字が配列ｐになっている。このループでは、異なる
ｉに対してｐ［ｉ］が同じ値を取ったときに、異なるイ
タレーションが配列ａの同一の要素を書き換える。それ
らのうち、最後のイタレーションによって書かれた値の
みがループ終了後の値として残る。例えば、ａ［ｐ
［２］］＝ｂ［２］でｐ［２］＝１２であり、ａ［ｐ
［６］］＝ｂ［６］でｐ［６］＝１２であったとする
と、ａ［１２］の値としてはｂ［６］が残る。このルー
プを並列実行する場合は、ループ終了後の各配列要素が
逐次実行のときと同じ値を持つようにしなければならな
い。本発明の並列実行方法では、上記の問題を解決する
ために、左辺配列ａと同じサイズの整数配列を新たに設
ける。この配列を「最終イタレーション配列」と呼ぶ。
最終イタレーション配列の各要素は、左辺配列ａと同様
に各プロセッサに割り当てる。各要素は、配列ａの対応
する要素を最後に書き換えたイタレーションのインデッ
クス（上記の例では６になる）を保持する。

【００１８】図１１は、図９の間接参照ループの本発明
による並列実行方法の手順を示すフロートチャートであ
る。ステップ４２０で、最終イタレーション配列の各要
素に初期値を設定する。初期値は、イタレーションイン
デックスの最小値より１少ない値とする。図９のループ
の場合は初期値として−１を設定する。ステップ４２１
は自身に割り当てられたイタレーションのうち、未処理
のものがまだあるかどうかの判定である。未処理のイタ
レーションがあればステップ４２２に進み、以下、その
イタレーションについての処理を行う。ステップ４２２
で間接参照ａ［ｐ［ｉ］］がｌｏｃａｌ参照かｒｅｍｏ
ｔｅ参照かを判定する。もしｌｏｃａｌ参照ならばステ
ップ４２３に進み、ｒｅｍｏｔｅ参照ならばステップ４
２５に進む。ステップ４２３でｌｏｃａｌ参照について
の代入を実行する。代入を実行したイタレーションにつ
いては、ステップ４２４でそのインデックスｉを最終イ
タレーション配列に記録する。ステップ４２５ではｒｅ
ｍｏｔｅ参照についての代入情報を「代入リスト」に登
録する。ここで登録する代入情報とは、要素ａ［ｐ
［ｉ］］の所有者のプロセッサ番号、所有者インデック
スｐ［ｉ］の値、参照者インデックスｉの値、および右
辺配列要素ｂ［ｉ］の値である。

【００１９】ここで代入リストの構造を説明する。図１
２に代入リストの構造を示す。位置リストなどと同様
に、所有者ごとにエントリを持つヘッダ５２０と、その
各エントリからポインタでつながるリスト本体５２１に
よって構成される。リスト本体５２１は３個のフィール
ド５２４，５２５，および５２６から成り、各フィール
ドは、右辺の配列要素ｂ［ｉ］の値、所有者インデック
スｐ［ｉ］、参照者インデックスｉを表す。例えば、図
１２の代入リストの一番最初の項目（斜線部分）は、プ
ロセッサ４番の持つ配列要素ａ［３５］に対して、イタ
レーション３番によって２６．５という値が代入される
べきことを表している。

【００２０】図１１に戻って、ステップ４２１で未処理
のイタレーションがもうなければステップ４２６に進
み、以下、代入リストに基づいてｒｅｍｏｔｅ参照の後
処理をする。ステップ４２６では、全プロセッサ間で代
入リストを交換する。この交換により、各プロセッサ
は、自身が所有者であるようなｒｅｍｏｔｅ参照につい
ての代入リストを持つようになる。代入リストのリスト
本体５２１の各エントリについて、ステップ４２７から
ステップ４３０の処理を行う。ステップ４２７は、リス
ト本体５２１に未処理のエントリがあるかどうかの判定
である。未処理のエントリがなければ並列実行は終了で
ある。未処理のエントリがあればステップ４２８に進
み、以下、そのエントリについての処理を行う。ステッ
プ４２８では、エントリ内の参照者インデックス５２６
と、エントリ内の所有者インデックス５２５に対応する
最終イタレーション配列の要素値と、を比較する。例え
ば、エントリ内の参照者インデックスがｉ＝２であり、
所有者インデックスがｐ［２］＝１２であり、最終イタ
レーション配列ｌａｓｔにおいてｌａｓｔ［１２］＝６
であったとしたとき、２と６を比較する。もし前者が後
者以下ならば、代入リストのエントリは、最終イタレー
ション配列に記録されているイタレーションより前のイ
タレーションによる代入を表している。したがって、こ
の代入は実行してはならず、ステップ４２７にもどって
次のエントリの処理を行う。例えば、エントリ内の参照
者インデックスがｉ＝２であり、所有者インデックスが
ｐ［２］＝１２であり、最終イタレーション配列ｌａｓ
ｔにおいてｌａｓｔ［１２］＝６であったとしたとき、
２（前者）＜６（後者）なので、代入は実行しない。も
し前者が後者より大きければ、ステップ４２９に進む。
ステップ４２９ではｒｅｍｏｔｅ参照による代入を実行
する。例えば、エントリ内の参照者インデックスがｉ＝
６であり、所有者インデックスがｐ［６］＝１２であ
り、最終イタレーション配列ｌａｓｔにおいてｌａｓｔ
［１２］＝２であったとしたとき、６（前者）＞２（後
者）なので、代入を実行する。すなわち、代入リストエ
ントリの値フィールド５２４の内容を、所有者インデッ
クス５２５に対応する左辺配列ａの要素に代入する。ま
たステップ４３０で、所有者インデックス５２５に対応
する最終イタレーション配列の要素に、参照者インデッ
クス５２６を代入する。

【００２１】次に図１３を参照して、左辺に間接参照が
あるループに対する、本発明のプログラム並列化方法の
一実施例の詳細を説明する。本実施例の並列化方法は、
図９の形の間接参照ループを対象とする。すなわち、次
の条件を充たすループを対象とする。（１）ループの中身は１個の代入文である。（２）その代入文の両辺はそれぞれ１個の配列要素参照
である。両辺の配列は異なる。（３）右辺の配列の添字はループイタレーションのイン
デックスｉである。（４）左辺の配列の添字は、別の配列である。すなわ
ち、左辺は間接参照である。本並列化方法によって、図９の間接参照ループは図１０
に示すような並列実行プログラム３１１に変換される。
図１０のプログラムは図に示した並列実行方法を実現す
るものである。以下、図１０のプログラム３１１を参照
しながら、図１３の並列化方法の詳細を説明する。ステ
ップ１２０で、最終イタレーション配列ｌａｓｔの宣言
文を挿入する。図１０では３行目がその宣言文である。
また、ステップ１２１で、間接参照ループの直前に最終
イタレーション配列ｌａｓｔの初期化文を挿入する。図
１０では４行目のライブラリ手続きｉｎｉｔｉａｌｉｚ
ｅ（）（図１１のステップ４２０の処理に対応する）の
呼び出しが、その初期化文である。手続きの引数は、初
期化される配列ｌａｓｔと初期値−１である。ステップ
１２２でプログラムのループ内の代入文の前に、間接参
照がｌｏｃａｌ参照かｒｅｍｏｔｅ参照かを判定する文
を挿入する。図１０では６行目に相当する。９行目のｅ
ｌｓｅも本ステップで挿入する。ステップ１２３で、イ
タレーションインデックスを最終イタレーション配列に
記録する文を、ｅｌｓｅの前、すなわちｌｏｃａｌ参照
の場合に実行される部分に挿入する。図の８行目がその
文である。ステップ１２４で、ｒｅｍｏｔｅ参照につい
ての代入情報を代入リストに登録する文を、ｅｌｓｅの
後、すなわちｒｅｍｏｔｅ参照の場合に実行される部分
に挿入する。図１０の１０行目にあるｐｕｔ＿ａｓｇｎ
ｉｎｆｏ（）というライブラリ手続き（図１１のステッ
プ４２５の処理に対応する）の呼び出しが、その登録文
である。手続きの引数は、登録する情報、すなわち、所
有者プロセッサ番号ｏｗｎｅｒ（ｐ［ｉ］）、所有者イ
ンデックスｐ［ｉ］、参照者インデックスｉ、および右
辺配列要素ｂ［ｉ］である。ステップ１２５からステッ
プ１２６で、ループの後にｒｅｍｏｔｅ参照の後処理を
行う文を挿入する。ステップ１２５では、代入リストを
交換する文、すなわち、ライブラリ手続きｅｘｃｈａｎ
ｇｅ＿ａｓｇｎｌｉｓｔ（）（図１１のステップ４２６
の処理に対応する）の呼び出しを挿入する。図１０では
１２行目に挿入されている。ステップ１２６では、所有
者側でｒｅｍｏｔｅ参照の代入を実行する文、すなわ
ち、ライブラリ手続きｒｅｍｏｔｅ＿ａｓｓｉｇｎ＿１
（ａ）の呼び出しを挿入する。引数として、代入先の配
列ａを与えている。図１０では１３行目に挿入されてい
る。このライブラリは、図１１のステップ４２７からス
テップ４３０の処理を実行する。すなわち、代入リスト
の各エントリにつき、参照者インデックスと最終イタレ
ーション配列の要素値を比較して、前者が後者より大き
い場合にのみ代入を実行する。また、代入を実行したと
きには最終イタレーション配列にインデックスを記録す
る。以上で、本発明による左辺間接参照ループの並列化
方法の説明を終わる。

【００２２】次に本発明のまた別の実施例として、加算
代入文（意味は後述）の左辺に間接参照がある場合の並
列実行方法および並列化方法について説明する。本実施
例が対象とするループは次の条件を充たすものである。（１）ループの中身は１個の加算代入文である。（２）その代入文の両辺はそれぞれ１個の配列要素参照
である。両辺の配列は異なる。（３）右辺の配列の添字はループイタレーションのイン
デックスｉである。（４）左辺の配列の添字は、別の配列である。すなわ
ち、左辺は間接参照である。図１４に本実施例が対象とするループの一例を示す。４
行目が加算代入文である。それに含まれる加算代入演算
子’＋＝”は、左辺の要素に右辺の要素を足し込むこと
を表している。すなわち、ａ［ｐ［ｉ］］＝ａ［ｐ
［ｉ］］＋ｂ［ｉ］と同等である。このループのように
配列要素に値を次々に足し込んでいく処理は、数値計算
プログラムで頻繁に現われる。したがってこのループの
並列実行は、現実に非常に重要である。

【００２３】この形のループを並列実行する場合、加算
の交換結合法則が利用できるので、各イタレーションの
実行順序は任意で良い。そのため、前の実施例と違っ
て、最終イタレーション配列が必要ない。また、代入リ
ストの本体の参照者インデックスも必要ない。同様のこ
とは、代入演算子に含まれる演算が乗算などの場合にも
成り立つ。このループの並列実行方法は、基本的には図
１１に示したものと同じであるが、上記の理由により、
多くのステップが省略できる。省略できるのは、ステッ
プ４２０の最終イタレーション配列の初期化、ステップ
４２４およびステップ４３０の最終イタレーション配列
へのインデックスの記録、ステップ４２８のインデック
スの大小判定である。このループの並列化方法も、基本
的に図１３に示したものと同じであるが、いくつかのス
テップが省略できる。省略できるのは、ステップ１２０
の最終イタレーション配列の宣言文の挿入、ステップ１
２１の最終イタレーション配列の初期化文の挿入、ステ
ップ１２３のインデックス記録文の挿入である。

【００２４】図１５は、本並列化方法によって、図１４
の間接参照ループを並列化した並列実行プログラムであ
る。前実施例の図１０のプログラムと比較して、最終イ
タレーション配列に関する文がなくなっている。また、
７行目の代入リストへの登録ライブラリｐｕｔ＿ａｓｇ
ｎｉｎｆｏ＿２（図１１のステップ４２５の処理に対応
する）の引数に、参照者インデックスｉが含まれていな
い。９行目のｅｘｃｈａｎｇｅ＿ａｓｎｇｌｉｓｔ＿２
は参照者インデックスを含まない代入リストを、プロセ
ッサ間で交換するライブラリ手続き（図１１のステップ
４２６の処理に対応する）である。１０行目のｒｅｍｏ
ｔｅ＿ａｓｓｉｇｎ＿２は、所有者側でｒｅｍｏｔｅ代
入を実行するライブラリ手続き（図１１のステップ４２
７，４２９の処理に対応する）であるが、図１０のｒｅ
ｍｏｔｅ＿ａｓｓｉｇｎ＿１と違って、図１１のステッ
プ４２８のインデックス比較やステップ４３０のインデ
ックス記録は含まない。

【００２５】次に本発明のまた別の実施例として、複数
の文や複数の間接参照を含むループの並列化方法を説明
する。本並列化方法では、そのようなループを、これま
で述べてきた１個の間接参照を含むループの組み合わせ
に変換してから、並列化するものである。本実施例の並
列化方法は、次の条件を充たすループを対象とする。（１）ループ内に代入文または加算代入文のみを含む。
文が複数個あってもよい。（２）ループ内に間接参照が１個以上ある。（３）ループ外への制御の飛び出しやループ内への制御
の飛び込みがない。（４）各代入文の右辺は配列要素かスカラ変数から構成
される式である。（５）間接参照の添字配列は、ループ内で定義されな
い。（６）代入文の左辺に現われる間接参照配列が、ループ
内のそれ以外の個所で参照されていない。この条件を充たすループを以下では、「一般間接参照ル
ープ」と呼ぶ。また、これまでの実施例で対象としてい
たループを「基本間接参照ループ」と呼ぶ。本実施例で
は簡単のために、ループのインデックスは０から始まり
１ずつ増えるものとするが、そうでない場合でも同様の
方法が適用できる。図１６に本並列化方法の対象となる
ループの一例を示す。

【００２６】図１８は、本実施例の並列化方法の手順を
表す。図１８のステップ１４０からステップ１４５まで
によって、図１６の一般間接参照ループ３３０は図１７
に示すような基本間接参照ループの組み合わせ３３１に
分解される。

【００２７】以下、図１６，１７のプログラム３３０，
３３１を参照しながら、図１８の並列化方法の詳細を説
明する。ループ内の各間接参照について、ステップ１４
０からステップ１４５の処理を行う。ステップ１４０
は、元のループ内に間接参照があるかどうかの判定であ
る。間接参照がなければ元のループは既に分解されたの
でステップ１４６に進む。間接参照があればステップ１
４１に進み、以下、その間接参照についての処理を行
う。ステップ１４１で間接参照の値を保持するための一
時配列を生成する。一時配列のサイズはループのイタレ
ーションの数とし、型は間接参照配列の型とする。この
一時配列を以下では＿ｔｍｐ［］と書く。ステップ１４
２で間接参照が右辺にあるか左辺にあるかを判定する。
右辺ならばステップ１４３に進み、左辺ならばステップ
１４４に進む。ステップ１４３で、元のループの前に次
の基本間接参照ループを挿入する。ｆｏｒ（ｉ＝．．．）＿ｔｍｐ［ｉ］＝間接参照；ここでｉはループの制御変数を表す。例えば、図１６の
２行目の間接参照ｂ［ｑ［ｉ］］に対して、図１７の
１，２行目のループを挿入し、図１６の３行目の間接参
照ｅ［ｔ［ｉ］］に対して、図の３，４行目の基本間接
参照ループを挿入する。ステップ１４４で、元のループ
の後に次の基本間接参照ループを挿入する。ｆｏｒ（ｉ）間接参照＝＿ｔｍｐ［ｉ］；元の代入文に加算代入演算子’＋＝’が用いられていれ
ば、挿入した基本間接参照ループの代入文にも’＋＝’
を用いる。例えば、図１６の２行目の間接参照ａ［ｐ
［ｉ］］に対して、図１７の９，１０行目のループを挿
入し、図１６の３行目の間接参照ｄ［ｓ［ｉ］］に対し
て、図１７の１１，１２行目の基本間接参照ループを挿
入する。ステップ１４５で、元のループ内の間接参照
を、一時配列の参照＿ｔｍｐ［ｉ］で置き換える。もし
も間接参照が左辺にあるならば、それに対する代入演算
子が何であっても、’＝’に置き換える。このステップ
１４５により、図１６の元のループは、図１７の５行目
から８行目のように変換される。ステップ１４５までの
変換により、元のループ内から間接参照は消去され、代
わりにステップ１４３，１４５で間接参照ループが生成
された。生成されたループは以前の実施例で対象とした
基本間接参照ループであり、前述の方法で並列化でき
る。ステップ１４６では、生成された基本間接参照ルー
プの各々に対して、前述の方法に従って並列化を行う。
以上で、複数の間接参照を含むループの並列化が終了し
た。

【００２８】図１９に本発明の並列化方法を実行する並
列化コンパイラ６の構成を示す。並列化コンパイラ６
は、構文解析部６０、一般間接参照ループ分解部６１、
基本間接参照ループ並列化部６２、通常ループ並列化部
６３、コード生成部６４を含む。一般間接参照ループ分
解部６１には、一時配列生成部６１０、基本間接参照ル
ープ生成部６１１、間接参照置換部６１２が含まれる。
基本間接参照ループ並列化部６２には、ｒｅｍｏｔｅ／
ｌｏｃａｌ判定文挿入部６２０、情報登録文挿入部６２
１、リスト交換文挿入部６２２、ｒｅｍｏｔｅ代入実行
文挿入部６２３、値リスト作成文挿入部６２４、最終イ
タレーション配列生成部６２５が含まれる。構文解析部
６０は、並列化前プログラム３０を読み込んで、中間語
７０を生成する。中間語７０はコンパイラ内部でのプロ
グラムの表現であり、その形式は通常のコンパイラの場
合と特に変わらないので、ここでは詳細には述べない。

【００２９】一般間接参照ループ分解部６１は、図１８
のステップ１４０からステップ１４５までの処理を行
う。すなわち、一般間接参照ループを基本間接参照ルー
プの組み合わせに分解する。その中で、一時配列生成部
６１０は図１８のステップ１４１の処理を行う。すなわ
ち、元のループ内の間接参照に対して、一時配列を生成
する。また、基本間接参照ループ生成部６１１は、図１
８のステップ１４３およびステップ１４４の処理を行
う、すなわち、間接参照が右辺か左辺かに応じて、元の
ループの前または後に基本間接参照ループを生成する。
間接参照置換部６１２は図１８のステップ１４５の処理
を行う。すなわち、元のループ内の間接参照を、一時配
列生成部６１０が生成した一時配列の参照に置換する。

【００３０】基本間接参照ループ並列化部６２は、図１
８のステップ１４６の処理を行う。すなわち、基本間接
参照ループの種類に応じて、図１および図１３に示した
並列化を行う。その中で、ｒｅｍｏｔｅ／ｌｏｃａｌ判
定文挿入部６２０は、図１のステップ１００および図１
３のステップ１２２の処理を行う。すなわち、間接参照
がｒｅｍｏｔｅ参照かｌｏｃａｌ参照か判定する文をル
ープ内に挿入する。また、情報登録文挿入部６２１は図
１のステップ１０１および図１３のステップ１２４の処
理を行う。すなわち、位置リストや代入リストに情報を
登録する文をループ内に挿入する。リスト交換文挿入部
６２２は図１のステップ１０２および図１３のステップ
１２５の処理を行う。すなわち、位置リストや代入リス
トをプロセッサ間で交換する文をプログラムに挿入す
る。ｒｅｍｏｔｅ代入実行文挿入部６２３は図１のステ
ップ１０５および図１３のステップ１２６の処理を行
う。すなわち、交換したリストを用いてｒｅｍｏｔｅ参
照についての代入を実行する文を挿入する。値リスト作
成文挿入部６２４は図１のステップ１０３の処理を行
う。すなわち、右辺間接参照ループに対して、値リスト
を作成する文を位置リスト交換文の後に挿入する。最終
イタレーション配列生成部６２５は図１３のステップ１
２０とステップ１２１の処理を行う。すなわち、左辺間
接参照ループに対して、最終イタレーション配列の宣言
文や初期化文を挿入する。通常ループ並列化部６３は間
接参照ループでないループの並列化を行う。またコード
生成部６４は中間語７０を読み込んで並列化後プログラ
ム３１を生成する。これらの処理の内容は従来の並列化
コンパイラの場合と特に変わらないので、ここでは詳細
は述べない。

【００３１】

【発明の効果】本発明によれば、一般的な間接参照ルー
プのプログラムを分散メモリ型並列計算機用に並列化す
ることができる。また、間接参照が左辺にある場合の間
接参照ループのプログラムを分散メモリ型並列計算機用
に並列化することができる。また、分散メモリ型並列計
算機において、一般的な間接参照ループを並列実行する
ことができる。また、分散メモリ型並列計算機におい
て、間接参照が左辺にある場合の間接参照ループを並列
実行することができる。

【図面の簡単な説明】

【図１】本発明による間接参照ループの並列化方法の一
実施例のフローチャートを示す図である。

【図２】本発明の並列化方法によって並列化されたプロ
グラムを実行する分散メモリ型並列計算機の構成例を示
す図である。

【図３】並列化前の右辺間接参照ループの例を示す図で
ある。

【図４】図３の間接参照ループに対して、図１の並列化
方法を適用した結果の間接参照ループを示す図である。

【図５】本発明による右辺間接参照ループの並列実行方
法の一実施例のフローチャートを示す図である。

【図６】図５の並列実行方法で使用する位置リストの構
造を示す図である。

【図７】図５の並列実行方法で使用する値リストの構造
を示す図である。

【図８】図５の並列実行方法を実現する装置の構成例を
示す図である。

【図９】並列化前の左辺間接参照ループの例を示す図で
ある。

【図１０】図９の左辺間接参照ループに対して、本発明
の並列化方法を適用した結果のプログラムを示す図であ
る。

【図１１】本発明による左辺間接参照ループの並列実行
方法の一実施例のフローチャートを示す図である。

【図１２】図１１の並列実行方法で使用する代入リスト
の構造図を示す図である。

【図１３】本発明による左辺間接参照ループの並列化方
法の一実施例のフローチャートを示す図である。

【図１４】並列化前の加算代入間接参照ループの例を示
す図である。

【図１５】図１４の加算代入間接参照ループに対して、
本発明の並列化方法を適用した結果のプログラムを示す
図である。

【図１６】一般間接参照ループの例を示す図である。

【図１７】図１６の一般間接参照ループに対して本発明
の方法を適用して、基本間接参照ループの組み合わせに
分解した結果のプログラムを示す図である。

【図１８】本発明による一般間接参照ループの並列化方
法の一実施例のフローチャートを示す図である。

【図１９】本発明の間接参照ループ並列化方法を実行す
る並列化コンパイラの例を示す図である。

【符号の説明】

２２相互結合ネットワーク２０、２０１〜２０ｎプロセッサ２１、２１１〜２１ｎローカルメモリ２３０演算部２３１ｒｅｍｏｔｅ参照判定部２３２位置情報登録部２３３ネットワーク制御部２３４値リスト作成部２３５ｒｅｍｏｔｅ参照代入部２４０参照者側位置リスト２４１所有者側位置リスト２４２所有者側値リスト２４３参照者側値リスト５００、５１０、５２０ヘッダ５０１、５１１、５２１リスト本体

───────────────────────────────────────────────────── フロントページの続き (72)発明者海永正博神奈川県川崎市麻生区王禅寺1099番地株式会社日立製作所システム開発研究所内 (72)発明者斎藤靖彦神奈川県川崎市麻生区王禅寺1099番地株式会社日立製作所システム開発研究所内

Claims

【特許請求の範囲】

【請求項１】逐次処理プログラムまたは共有メモリ型
並列計算機用プログラムを分散メモリ型並列計算機プロ
グラムに変換するプログラム並列化方法において、配列の添字が配列になっている間接参照を含むループに
対して、参照されている配列要素が自プロセッサにある
か他プロセッサにあるかを判定する文を、該間接参照ル
ープ内に挿入するステップと、参照されている配列要素が他プロセッサにある場合に該
配列要素についての情報をリストに登録する文を、該間
接参照ループ内に挿入するステップと、該リストをプロ
セッサ間で交換するリスト交換文を、該間接参照ループ
の後に挿入するステップと、該交換されたリストを用いて他プロセッサの配列要素の
値を自プロセッサの配列要素に代入する文を、該リスト
交換文の後に挿入するステップとを含むことを特徴とす
るプログラム並列化方法。
【請求項２】配列の添字が配列になっている間接参照
ループを分散メモリ型並列計算機で並列実行する方法に
おいて、参照されている配列要素が自プロセッサにあるか他プロ
セッサにあるかを該間接参照ループ内で判定するステッ
プと、自プロセッサにある場合に該配列要素への代入をするス
テップと、他プロセッサにある場合に該配列要素についての情報を
該間接参照ループ内でリストに登録するステップと、該間接参照ループ終了後に該リストをプロセッサ間で交
換するステップと、該交換されたリストを用いて他プロセッサの配列要素の
値を自プロセッサの配列要素に代入するステップとを含
むことを特徴とする間接参照ループの並列実行方法。
【請求項３】逐次処理プログラムまたは共有メモリ型
並列計算機用プログラムを分散メモリ型並列計算機プロ
グラムに変換するプログラム並列化装置において、配列の添字が配列になっている間接参照を含むループに
対して、参照されている配列要素が自プロセッサにある
か他プロセッサにあるかを判定する文を、該間接参照ル
ープ内に挿入する手段と、参照されている配列要素が他プロセッサにある場合に該
配列要素についての情報をリストに登録する文を、該間
接参照ループ内に挿入する手段と、該リストをプロセッサ間で交換するリスト交換文を、該
間接参照ループの後に挿入する手段と、該交換されたリストを用いて他プロセッサの配列要素の
値を自プロセッサの配列要素に代入する文を、該リスト
交換文の後に挿入する手段とを備えることを特徴とする
プログラム並列化装置。
【請求項４】配列の添字が配列になっている間接参照
ループを分散メモリ型並列計算機で並列実行する装置に
おいて、参照されている配列要素が自プロセッサにあるか他プロ
セッサにあるかを判定する手段と、自プロセッサにある場合に該配列要素への代入をする手
段と、他プロセッサにある場合に該配列要素についての情報を
リストに登録する手段と、該リストをプロセッサ間で交換する手段と、該交換されたリストを用いて他プロセッサの配列要素の
値を自プロセッサの配列要素に代入する手段とを備える
ことを特徴とする間接参照ループの並列実行装置。
【請求項５】逐次処理プログラムまたは共有メモリ型
並列計算機用プログラムを分散メモリ型並列計算機プロ
グラムに変換するプログラム並列化方法において、配列の添字が配列になっている間接参照を複数個含むル
ープに対して、該ループを分解して各々が１個の間接参
照を含む複数のループの組み合わせに変換するステップ
と、該分解されたループの各々を請求項１の並列化方法
にしたがって並列化するステップとを含むことを特徴と
するプログラム並列化方法。
【請求項６】請求項５記載のプログラム並列化方法に
おいて、間接参照ループを分解して各々が１個の間接参照を含む
複数のループの組み合わせに変換するステップは、間接
参照の各々に対して、一時配列を生成するステップと、
該間接参照ループ内の該間接参照を該一時配列の参照に
置換するステップと、該間接参照と該一時配列要素を両
辺に持つ代入文を含む新たなループを、該間接参照ルー
プの前または後に生成するステップとを含むことを特徴
とするプログラム並列化方法。
【請求項７】逐次処理プログラムまたは共有メモリ型
並列計算機用プログラムを分散メモリ型並列計算機プロ
グラムに変換するプログラム並列化方法において、配列の添字が配列になっている間接参照が代入文の右辺
に現われるループに対して、参照されている配列要素が
自プロセッサにあるか他プロセッサにあるかを判定する
文を、該間接参照ループ内に挿入するステップと、他プロセッサにある場合に該配列要素についての位置情
報を位置リストに登録する文を、該間接参照ループ内に
挿入するステップと、該位置リストをプロセッサ間で交換する位置リスト交換
文を、該間接参照ループの後に挿入するステップと、該交換された位置リストを用いて、他プロセッサから参
照されている配列要素の値を含む値リストを作成する文
を、該位置リスト交換文の後に挿入するステップと、該値リストをプロセッサ間で交換する値リスト交換文
を、該値リスト作成文の後に挿入するステップと、該交換された値リストを用いて他プロセッサの配列要素
の値を自プロセッサの配列要素に代入する文を、該値リ
スト交換文の後に挿入するステップとを含むことを特徴
とするプログラム並列化方法。
【請求項８】請求項７記載のプログラム並列化方法に
おいて、位置リストに登録する位置情報は、参照されている配列
要素を所有するプロセッサのプロセッサ番号、該配列要
素のインデックス、該配列要素を参照しているループイ
タレーションのインデックスを含むことを特徴とするプ
ログラム並列化方法。
【請求項９】配列の添字が配列になっている間接参照
が代入文の右辺に現われるループを分散メモリ型並列計
算機で並列実行する方法において、参照されている配列要素が自プロセッサにあるか他プロ
セッサにあるかを、該間接参照ループ内で判定するステ
ップと、自プロセッサにある場合に該配列要素への代入をするス
テップと、他プロセッサにある場合に該配列要素についての位置情
報を該間接参照ループ内で位置リストに登録するステッ
プと、該間接参照ループ終了後に該位置リストをプロセッサ間
で交換するステップと、該交換された位置リストを用いて、他プロセッサから参
照されている配列要素の値を含む値リストを作成するス
テップと、該値リストをプロセッサ間で交換するステップと、該交換された値リストを用いて他プロセッサの配列要素
の値を自プロセッサの配列要素に代入するステップとを
含むことを特徴とする、間接参照ループの並列実行方
法。
【請求項１０】請求項９記載の間接参照ループの並列
実行方法において、位置リストに登録する位置情報は、参照されている配列
要素を所有するプロセッサのプロセッサ番号、該配列要
素のインデックス、該配列要素を参照しているループイ
タレーションのインデックスを含むことを特徴とする間
接参照ループの並列実行方法。
【請求項１１】逐次処理プログラムまたは共有メモリ
型並列計算機用プログラムを分散メモリ型並列計算機プ
ログラムに変換するプログラム並列化方法において、配列の添字が配列になっている間接参照が代入文の左辺
に現われるループに対して、間接参照されている配列の
要素を最後に書き換えたイタレーションのインデックス
を記録する最終イタレーション配列の宣言文をプログラ
ム内に挿入するステップと、該最終イタレーション配列の初期化文を該間接参照ルー
プの前に挿入するステップと、参照されている配列要素
が自プロセッサにあるか他プロセッサにあるかを判定す
る文を、該間接参照ループ内に挿入するステップと、最終イタレーション配列にイタレーションインデックス
を記録する文を、該間接参照ループ内に挿入するステッ
プと、他プロセッサにある場合に該配列要素についての代入情
報を代入リストに登録する文を、該間接参照ループ内に
挿入するステップと、該代入リストをプロセッサ間で交換する代入リスト交換
文を、該間接参照ループの後に挿入するステップと、該交換された代入リストを用いて他プロセッサの配列要
素の値を自プロセッサの配列要素に代入する文を、該代
入リスト交換文の後に挿入するステップとを含むことを
特徴とするプログラム並列化方法。
【請求項１２】請求項１１記載のプログラム並列化方
法において、代入リストに登録する代入情報は、参照されている配列
要素を所有するプロセッサのプロセッサ番号、該配列要
素のインデックス、該配列要素を参照しているループイ
タレーションのインデックス、および該配列要素に代入
すべき値を含むことを特徴とするプログラム並列化方
法。
【請求項１３】配列の添字が配列になっている間接参
照が代入文の左辺に現われるループを分散メモリ型並列
計算機で並列実行する方法において、配列要素を最後に書き換えたイタレーションのインデッ
クスを記録する最終イタレーション配列を初期化するス
テップと、参照されている配列要素が自プロセッサにあるか他プロ
セッサにあるかを、該間接参照ループ内で判定するステ
ップと、自プロセッサにある場合に該配列要素への代入を実行
し、該最終イタレーション配列にイタレーションインデ
ックスを記録するステップと、他プロセッサにある場合に該配列要素についての代入情
報を、該間接参照ループ内で代入リストに登録するステ
ップと、該間接参照ループ終了後に該代入リストをプロセッサ間
で交換するステップと、該交換された代入リストを用いて他プロセッサの配列要
素の値を自プロセッサの配列要素に代入するステップと
を含むことを特徴とする間接参照ループの並列実行方
法。
【請求項１４】請求項１３記載の間接参照ループの並
列実行方法において、代入リストに登録する代入情報は、参照されている配列
要素を所有するプロセッサのプロセッサ番号、該配列要
素のインデックス、該配列要素を参照しているループイ
タレーションのインデックス、および該配列要素に代入
すべき値を含むことを特徴とする、間接参照ループの並
列実行方法。
【請求項１５】請求項１３記載の間接参照ループの並
列実行方法において、交換された代入リストを用いて他プロセッサの配列要素
の値を自プロセッサの配列要素に代入するステップは、
最終イタレーション配列に格納されているインデックス
と代入リスト内のループイタレーションインデックスを
比較するステップと、前者が後者よりも小さいときに、
代入を実行し、かつ、後者を最終イタレーション配列に
格納するステップを含むことを特徴とする間接参照ルー
プの並列実行方法。
【請求項１６】配列の添字が配列になっている間接参
照が代入文の左辺に現われるループを分散メモリ型並列
計算機で並列実行する方法において、間接参照されてい
る配列の要素を最後に書き換えたイタレーションのイン
デックスを記録する配列を設けたことを特徴とする間接
参照ループの並列実行方法。
【請求項１７】逐次処理プログラムまたは共有メモリ
型並列計算機用プログラムを分散メモリ型並列計算機プ
ログラムに変換するプログラム並列化方法において、配列の添字が配列になっている間接参照が加算代入文の
左辺に現われるループに対して、参照されている配列要
素が自プロセッサにあるか他プロセッサにあるかを判定
する文を、該間接参照ループ内に挿入するステップと、他プロセッサにある場合に該配列要素についての代入情
報を代入リストに登録する文を、該間接参照ループ内に
挿入するステップと、該代入リストをプロセッサ間で交換する代入リスト交換
文を、該間接参照ループの後に挿入するステップと、該交換された代入リストを用いて他プロセッサの配列要
素の値を自プロセッサの配列要素に加算代入する文を、
該代入リスト交換文の後に挿入するステップとを含むこ
とを特徴とするプログラム並列化方法。
【請求項１８】請求項１７記載のプログラム並列化方
法において、代入リストに登録する代入情報は、参照されている配列
要素を所有するプロセッサのプロセッサ番号、該配列要
素のインデックス、および該配列要素に代入すべき値を
含むことを特徴とするプログラム並列化方法。
【請求項１９】配列の添字が配列になっている間接参
照が加算代入文の左辺に現われるループを分散メモリ型
並列計算機で並列実行する方法において、参照されている配列要素が自プロセッサにあるか他プロ
セッサにあるかを、該間接参照ループ内で判定するステ
ップと、自プロセッサにある場合に該配列要素への加算代入をす
るステップと、他プロセッサにある場合に該配列要素についての代入情
報を該間接参照ループ内で代入リストに登録するステッ
プと、該間接参照ループ終了後に該代入リストをプロセッサ間
で交換するステップと、該交換された代入リストを用いて他プロセッサの配列要
素の値を自プロセッサの配列要素に加算代入するステッ
プとを含むことを特徴とする間接参照ループの並列実行
方法。
【請求項２０】請求項１９記載の間接参照ループの並
列実行方法において、代入リストに登録する代入情報は、参照されている配列
要素を所有するプロセッサのプロセッサ番号、該配列要
素のインデックス、および該配列要素に代入すべき値を
含むことを特徴とする間接参照ループの並列実行方法。