JP3239963B2 - マルチ・プロセッサ計算機システム - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は複数のプロセッサから構
成される計算機システムにおいて、データを分割して割
り当て、複数のプロセッサにより並列実行するためマル
チ・プロセッサ計算機システムに関し、特に、本発明は
各プロセッサがそれぞれ固有のメモリを持つ分散メモリ
方式のマルチ・プロセッサ計算機システムに関するもの
である。

【０００２】

【従来の技術】複数のプロセッサからなる計算機システ
ムとして、従来から図６（ａ），（ｂ）に示すシステム
が知られている。同図（ａ），（ｂ）において、１１
ａ，１１ｂ…はプロセッサ、１２，１２ａ，１２ｂ…は
メモリ、１３はネットワークを示す。同図（ａ）は、共
有メモリ方式のマルチ・プロセッサ・システムを示し、
各プロセッサ１１ａ，１１ｂはメモリ１２を共有してお
り、メモリ１２は各プロセッサ１１ａ，１１ｂの命令か
ら直接アクセス可能である。

【０００３】同図（ｂ）は分散メモリ方式のマルチ・プ
ロセッサ・システムを示し、各プロセッサ１１ａ，１１
ｂ…が固有のメモリ１２ａ，１２ｂ…を有し、各プロセ
ッサ間の通信はネットワーク１３を介して行われる。と
ころで、上記したマルチ・プロセッサ・システムにおい
て、複数のプロセッサによりプログラムを並列実行する
場合、従来、次の２つの方法が用いられていた。 並
列実行可能部分にその旨の指示を行った１つのソース・
プログラムを変換して並列実行する方法。

【０００４】図７（ａ）は同図（ｃ）に示すソース・プ
ログラムＰ１をプロセッサ１１ａ，１１ｂ、メモリ１２
より構成されるメモリ共有方式のマルチ・プロセッサ・
システムにおいて実行する場合を示した図である。同図
におけるソース・プログラムＰ１は、ファイルより配列
Ａにデータを読込み２台のプロセッサによりＤＯループ
を並列実行する例を示したものであり、「READ A」によ
りファイルよりデータを配列Ａに読み込み、「PARALLEL
DO I=1,1000…」「=A(I) 」により並列実行を行う。

【０００５】上記ソース・プログラムＰ１は共有メモリ
方式のマルチ・プロセッサ・システムにおいて、同図
（ａ）に示すように実行される。プロセッサ１１ａによ
り、メモリ１２に配列の領域を確保したのち、「READ
A」を実行して、メモリ１２に確保された領域にファイ
ルよりデータを読み込む。ついで、プロセッサ１１ａ，
１１ｂにより並列実行が開始される。すなわち、ＤＯル
ープの１〜１０００のループを２つに分割し、プロセッ
サ１１ａにより１〜５００のＤＯループを、また、プロ
セッサ１１ｂにより５０１〜１０００のＤＯループを並
列に実行し、参照データは、それぞれのプロセッサ１１
ａ，１１ｂによりメモリ１２から読み込まれる。

【０００６】同図（ｂ）は上記ソース・プログラムＰ１
を、メモリ１２ａを持つプロセッサ１１ａ，メモリ１２
ｂを持つプロセッサ１１ｂより構成される分散メモリ方
式のマルチ・プロセッサ・システムにより実行する場合
を示す図である。同図（ｂ）において、プロセッサ１１
ａにより、メモリ１２ａに配列の領域を確保したのち、
「READ A」を実行して、メモリ１２ａに確保された領域
にファイルよりデータを読み込む。

【０００７】ついで、ＤＯループの１〜１０００のルー
プを２つに分割し、同図（ａ）に示したように、プロセ
ッサ１１ａ，プロセッサ１１ｂにより１〜５００のＤＯ
ループ、５０１〜１０００のＤＯループを並列に実行す
る。また、この場合には、配列データがメモリ１２ａに
格納されているため、プロセッサ１１ｂがＤＯループの
命令を実行するごとに、データがプロセッサ１１ａ，１
１ｂ間で転送される。このため転送のオーバ・ヘッドが
生じて、実行時間が増大する。 プロセッサごとにソ
ース・プログラムを記述し、それぞれを実行形式プログ
ラムに変換して並列実行する方法。

【０００８】図８（ａ）はメモリ１２ａを持つプロセッ
サ１１ａ、メモリ１２ｂを持つプロセッサ１１ｂから構
成される分散メモリ方式のマルチ・プロセッサ・システ
ムにより、それぞれのプロセッサ用に記述された図８
（ｂ）に示すソース・プログラムＰ２ａ、ソース・プロ
グラムＰ２ｂを実行する場合を示す図である。ソース・
プログラムＰ２ａ，ｐ２ｂは、ファイルよりそれぞれ配
列ＡおよびＢにデータを読込み、ソース・プログラムＰ
１と同様に、２台のプロセッサによりＤＯループを並列
実行する例を示したものである。

【０００９】ソース・プログラムＰ２ａはプロセッサ１
１ａ用に記述されたプログラムであり、ソース・プログ
ラムＰ２ｂはプロセッサ１１ｂ用に記述されたプログラ
ムである。上記ソース・プログラムＰ２ａ，Ｐ２ｂは分
散メモリ方式のマルチ・プロセッサ・システムにおい
て、同図（ａ）に示すように実行される。

【００１０】プロセッサ１１ａ，１１ｂにより、それぞ
れのメモリ１２ａ，１２ｂに配列の領域を確保したの
ち、プロセッサ１１ａにおいては「READ A」を実行し
て、配列データを５００要素分を読み込んで配列Ａに格
納し、その後、”前半完了”という事象を通知する。プ
ロセッサ１１ｂにおいては、”前半完了”という事象が
起きることを待ち続け、それが満足したのちに「READ
B」を実行して配列データを５００要素分読み込み配列
Ｂへ格納する。

【００１１】以上のようにして、メモリ１２ａに１〜５
００までのデータが格納されるとプロセッサ１１ａによ
り、また、メモリ１２ｂに５０１〜１０００のデータが
格納されるとプロセッサ１１ｂにより並列にＤＯループ
を実行し、参照データは、それぞれのプロセッサ１１
ａ，１１ｂによりメモリ１２ａ，１２ｂから読み込まれ
る。

【００１２】

【発明が解決しようとする課題】ところで、上記した
の方法は、図６（ａ）に示したような、均一の共有メモ
リ方式（各プロセッサからのメモリに対するアクセス速
度にあまり差がない共有メモリ方式）のマルチ・プロセ
ッサ・システムに適用するには適しているが、図６
（ｂ）に示した分散メモリにおいては、データの参照時
に他のプロセッサとのデータ転送が生じるため、実行時
間が増大するという欠点があった。

【００１３】また、上記したの方法は、各プロセッサ
ごとにソース・プログラムを記述しなければならないた
め、例えば、ＲＥＡＤ文のような並列実行できない部分
のために、ＰＯＳＴ，ＷＡＩＴ文による同期制御等の考
慮をプログラム中でするなど、並列実行できない部分の
ための考慮をプログラム中でしなければならず、プログ
ラムの記述がむずかしいという欠点があった。

【００１４】本発明は上記した従来技術の欠点に鑑みな
されたものであって、複数のプロセッサからなる分散方
式のマルチ・プロセッサ・システムにおいて、プロセッ
サを複数台利用するための命令の分割と、データを各プ
ロセッサの固有のメモリに割り当てるためのデータ分割
を、１つの分割指示により共通に行えるようにすること
により、並列実行用プログラムを容易に記述できるよう
にするとともに、データ参照時及び格納時のデータ転送
時間を削減し、並列実行における実行時間を短縮するこ
とができるマルチ・プロセッサ計算機システムを提供す
ることを目的とする。

【００１５】

【課題を解決するための手段】図１は本発明の原理図で
ある。上記課題を解決するため、本発明は、図１に示す
ように、分散メモリ方式、もしくは、プロセッサとメモ
リ間の距離によってプロセッサからメモリへのアクセス
速度に差がある共有メモリ方式のマルチ・プロセッサ計
算機システムにおいて、マルチ・プロセッサ計算機シス
テム２の複数のプロセッサ２ａ，２ｂ，２ｃにより一つ
のソース・プログラム１を分担して並列実行する際、ソ
ース・プログラム中に記述されたプロセッサ数と、命令
及びデータの分割基準となるインデックス区間と、イン
デックスの分割方法を示す情報とに基づき、ソース・プ
ログラム中の一つの一次元配列データおよび命令を、上
記ソース・プログラム中の命令部の各プロセッサへの分
割と、一次元配列データの各プロセッサのメモリへの分
割とが一致するように複数個に分割したオブジェクト・
プログラムを各プロセッサ毎に生成する。 そして、マル
チ・プロセッサ計算機システム２の各プロセッサ２ａ，
２ｂ，２ｃに当該オブジェクト・プログラムを割り当
て、上記各プロセッサ２ａ，２ｂ，２ｃにより、上記分
割された上記割り当てられたオブジェクト・プログラム
を並列実行するようにしたものである。

【００１６】

【作用】本発明においては、マルチ・プロセッサ計算機
システム２の複数のプロセッサ２ａ，２ｂ，２ｃにより
一つのソース・プログラム１を分担して並列実行する
際、ソース・プログラム１中に記述されたプロセッサ数
と、命令及びデータの分割基準となるインデックス区間
と、インデックスの分割方法を示す情報とに基づき、ソ
ース・プログラム中の一つの一次元配列データおよび命
令を、上記ソース・プログラム中の命令部の各プロセッ
サへの分割と、一次元配列データの各プロセッサのメモ
リへの分割とが一致するように複数個に分割したオブジ
ェクト・プログラムを各プロセッサ２ａ，２ｂ，２ｃ毎
に生成し、マルチ・プロセッサ計算機システムの各プロ
セッサ２ａ，２ｂ，２ｃに当該オブジェクト・プログラ
ムを割り当て、上記割り当てられたオブジェクト・プロ
グラムを並列実行するようにしたので、並列実行用プロ
グラムを容易に記述することが可能となるとともに、デ
ータ参照時のデータ転送時間を削減し、並列実行におけ
る実行時間を短縮することが可能となる。また、プログ
ラム１中の命令部の各プロセッサ２ａ，２ｂ，２ｃへの
分割と配列データの各プロセッサ２ａ，２ｂ，２ｃのメ
モリへの分割とを一致させるようにしたので、配列デー
タの数と命令における繰り返し回数が異なっていても、
各プロセッサにおいて、問題なく並列実行を行うことが
でき、データ参照時のデータ転送時間を削減し、並列実
行における実行時間を短縮することが可能となる。

【００１７】

【実施例】図２は本発明におけるソース・プログラムの
一例と、そのプログラムを図６（ｂ）に示した分散メモ
リ方式のマルチ・プロセッサ・システムにより実行する
場合の動作を示す図である。同図において、１１ａ，１
１ｂはプロセッサ、１２ａ，１２ｂは、それぞれプロセ
ッサ１１ａ，１１ｂに固有のメモリである。また、Ｐ３
は同図のシステムにより実行されるソース・プログラム
の一例であり、前記したソース・プログラムＰ１と同様
に、ファイルより配列Ａにデータを読込み２台のプロセ
ッサによりＤＯループを並列実行する例を示したもので
ある。なお、ソース・プログラムＰ３は後述するコンパ
イラによりコンパイルされプロセッサ１１ａ，１１ｂに
より実行される実行形式のプログラムに変換される。

【００１８】また、実行形式に変換されたプログラムの
プロセッサ１１ａ，１１ｂにおける実行は、前記した図
８の場合と同様であり、プロセッサ１１ａにおいて「RE
AD A」によりファイルより配列Ａにデータを読み込み、
プロセッサ１１ｂにデータを転送して、並列実行を行
う。ソース・プログラムＰ３において、「PARTITION P=
(2,1:1000,BAND) 」は、命令部とデータ部を分割し複数
のプロセッサに割り当てるための分割情報であり、上記
記述において、括弧内の「2 」は命令又はデータを何台
のプロセッサへ割り当てるかを示すプロセッサ数、「1:
1000」は命令又はデータの分割基準となるインデックス
区間、「BAND」はインデックスの分割方法を示す。

【００１９】また、「PARALLEL DO …」は図７のソース
・プログラムＰ１で示したものと同様、並列実行開始を
記述したものである。ここで、上記インデックス区間、
インデックスの分割方法について、説明する。 インデックス区間 インデックス区間は上記したように命令又はデータの分
割基準となるものであり、図２に示したソース・プログ
ラムＰ３においては、配列宣言が「REAL A(1000)」、ま
た、ＤＯループにおける繰り返し回数が「I=1,1000」で
あり、これらはインデックス区間「1:1000」と一致して
いる。このため、配列宣言の上下限値、あるいは、ＤＯ
ループにおける繰り返し回数により命令、データを分割
しても、問題は生じない。

【００２０】しかしながら、上記配列宣言やＤＯループ
における繰り返し回数が一致しない場合、配列宣言の上
下限値、あるいは、ＤＯループにおける繰り返し回数い
ずれか一方により命令、データを分割すると、他方によ
る分割値と一致しないという問題が生ずる。例えば、下
記の例において、 配列宣言においては、Ａ（４００）であるが、ＤＯルー
プにおける繰り返し回数はＩ＝３，３９８であり、配列
宣言の両端が「２」ずつ計算対象外となっている。上記
例において、配列Ａを４分割すると、配列ＡはＡ（１：
１００） Ａ（１０１：２００） Ａ（２０１：３０
０） Ａ（３０１：４００）に分割される。また、ＤＯ
ループのＩ＝３，３９８により、繰り返し回数を４分割
すると、Ｉ＝３，１０１ Ｉ＝１０２，２００ Ｉ＝２
０１，２９９ Ｉ＝３００，３９８に分割され、１０１
と３００の所で両者は一致しない。

【００２１】一方、分割情報のインデックス区間を基準
として分割すると、ＤＯループにおける繰り返し回数
は、Ｉ＝３，１００ Ｉ＝１０１，２００ Ｉ＝２０
１，３００ Ｉ＝３０１，３９８に分割され、データの
分割と一致する。以上のように、命令や配列を、その繰
り返しの始値、終値あるいは配列宣言の添字の上下限値
ではなく、分割情報のインデックス区間を基準として分
割することにより、上記した例のように、境界値が計算
対象外であるとき等、縮小区間においても、命令と配列
の分割を一致させることができる。 インデックスの
分割方法図３はインデックスの分割方法を示す図であ
り、同図において、縦軸はプロセッサ番号を示し、横軸
はインデックス値を示している。同図に示すように、イ
ンデックスは「均等分割」、「循環分割」、「三角分
割」等の種々の方法で分割することができる。

【００２２】上記分割方法において、例えば、三角分割
は、ＤＯループが下記のような２重ループになっている
場合など、後ろの方ほど処理量が多い場合に採用するこ
とにより、処理量を均一化することができる。 図４は、並列実行を行うためのソース・プログラムをコ
ンパイルするためのコンパイラの構成の一例を示す図で
あり、同図において、２１は並列実行するためのソース
・プログラム、２２はソース・プログラムをコンパイル
するためのコンパイラ、２３はソース・プログラムを解
析するソース・プログラム解析部、２４はソース・プロ
グラムより自動的に並列化可能部分を見つけ出す最適化
部、２５は解析されたソース・プログラムより実行形式
の並列オブジェクト・プログラムを生成するコード生成
部、２６はソース・プログラム解析部において構文解析
を行うための構文、２７は作成された並列オブジェクト
・プログラムである。

【００２３】なお、図４における最適化部２４は必要に
応じて設けられるものであって、図２の例に示したよう
に、ソース・プログラム中に並列化部分が記述されてい
る場合には必要ない。同図において、ソース・プログラ
ム２１がコンパイラ２２に与えられると、ソース・プロ
グラム２１は、まず、ソース・プログラム解析部２３に
おいてソース・プログラムの解析が行われる。

【００２４】ソース・プログラム解析部２３において構
文解析を行う際には、通常のソース・プログラムを解析
する場合に用いられる構文２６の文法に加え、並列実行
用ソース・プログラムを解釈するための並列用構文２６
ａの文法を参照して、構文解析が行われる。図５はＦｏ
ｒｔｒａｎのソース・プログラムに並列実行用の分割記
述を採用した構文の一例を示す図であり、同図に示した
構文は、図２のソース・プログラムＰ３をＢＮＦ（Ｂａ
ｃｋｕｓ−Ｎａｕｒ Ｆｏｒｍ）により記述した一例を
示している（ＢＮＦについては、例えば、A.V.ホセ外２
名著「コンパイラＩ−原理・技法・ツール」株式会社サ
イエンス社1990/10/10初版発行などコンパイラ関係の文
献を参照されたい）。

【００２５】ソース・プログラム解析部２３の出力は、
必要に応じて最適化部２４に与えられる。なお、最適化
部２４は、前記したように、ソース・プログラム中に並
列化部分が記述されている場合には必要ない。最適化部
２４においては、与えられたソース・プログラム中で並
列化可能な部分を選択する。ソース・プログラム中で並
列化可能な部分としては、ＤＯループのように繰り返し
演算が行われる部分が選択されるが、その選択にあたっ
ては、例えば、多重ＤＯループの場合にはＤＯループの
交換を行い出来るだけ外側のループを分割することによ
り並列処理制御の回数を少なくしてオーバ・ヘッドを削
減するなど、その実行性能を考慮する。

【００２６】以上のようにして、ソース・プログラム解
析部において、解析が行われたプログラム、あるいは、
最適化部２４において、並列化対象ループが選択された
プログラムはコード生成部２５に与えられる。コード生
成部２５においては、上記プログラムより最終的なオブ
ジェクト・プログラムが生成される。

【００２７】コード生成部２５においてオブジェクト・
プログラムを生成するに際して、命令については、繰り
返し演算の始値、終値と分割情報のインデックス値とが
比較され、実行するプロセッサが決定されるとともに、
データについては、配列宣言の添字の下限、上限と分割
情報のインデックス値とが比較され、データを割りつけ
るプロセッサが決定される。

【００２８】図５に示した例の場合には、「locate-sta
tement」に対しては、「array-name」の宣言における上
下限値を、分割情報のインデックス範囲と照らし合わせ
て複数の配列に分割し、それぞれのプロセッサ用の実行
形式プログラムに組み込む。また、「parallel-do-stat
ement 」に対しては、「start-value 」および「end-va
lue 」を分割情報のインデックス範囲に照らし合わせ
て、それぞれのプロセッサごとの新しい「start-value
」、「end-value 」による繰り返しを実行形式のプロ
グラムに組み込む。

【００２９】以上のような処理により、コンパイラ２２
は並列実行用の並列オブジェクト・プログラム２７を生
成して出力し、並列オブジェクト・プログラム２７ａな
いし２７ｃが各プロセッサにロードされ実行される。実
際には、各プロセッサ用の並列オブジェクト・プログラ
ム２７ａないし２７ｃは一連のプログラムとして出力さ
れて各プロセッサにロードされ、各プロセッサにおける
実行時、各プロセッサが自プロセッサに対応したプログ
ラム部分を選んで実行する。

【００３０】なお、以上の実施例においては、分散メモ
リ方式を持つマルチ・プロセッサ・システムに本発明を
適用した例を示したが、本発明は上記実施例に限定され
るものではなく、例えば、共有メモリ方式をもつマルチ
・プロセッサ・システムであっても、メモリと各プロセ
ッサとの間の距離によりメモリへのアクセス速度に差が
あり、各プロセッサの命令実行部が参照するデータを得
るためのデータ転送時間が演算時間より大きく、データ
転送時間の削減がプログラム全体の実行速度の向上に寄
与するシステムに適用することにより、分散メモリ方式
の場合と同様な効果を得ることが可能である。

【００３１】また、上記実施例においては、ソース・プ
ログラムをコンパイラによりコンパイルして実行する例
を示したが、本発明は上記実施例に限定されるものでは
なく、例えば、ソース・プログラムを計算機上でそのま
ま実行するインタプリータ方式、あるいは、一つのソー
ス・プログラムから複数個の新ソース・プログラムを生
成するプリプロセッサ方式にも適用することができる。

【００３２】

【発明の効果】以上説明したことから明らかにように、
本発明においては、ソース・プログラム中の一つの配列
データを複数個の配列に分割し複数のプロセッサのメモ
リへ割り当て、上記プログラム中の命令部と配列データ
の分割・割り当てを一致させるようにしたので、並列実
行用プログラムを容易に記述することができるととも
に、データ参照時のデータ転送時間を削減し、並列実行
における実行時間を短縮することが可能となる。

【図面の簡単な説明】

【図１】本発明の原理図である。

【図２】本発明の実施例における並列実行処理を示す図
である。

【図３】インデックスの分割方法を示す図である。

【図４】本発明の実施例におけるコンパイラの構成を示
す図である。

【図５】本発明の実施例における構文の一例を示す図で
ある。

【図６】複数のプロセッサからなる計算機システムの構
成を示す図である。

【図７】従来例（その１）を示す図である。

【図８】従来例（その２）を示す図である。

【符号の説明】

１，２１ ソース・プログラム ２ マルチ・プロセッサ・システム ２２ コンパイラ ２７ オブジェクト・プログラム １１ａ，１１ｂ プロセッサ １２ａ，１２ｂ メモリ ２３ ソース・プログラム解析部 ２４ 最適化部 ２５ コード生成部

Claims (1)

(57)【特許請求の範囲】
1. 【請求項１】 分散メモリ方式、もしくは、プロセッサ
   とメモリ間の距離によってプロセッサからメモリへのア
   クセス速度に差がある共有メモリ方式のマルチ・プロセ
   ッサ計算機システムであって、ソース・プログラム中に記述された プロセッサ数と、命
   令及びデータの分割基準となるインデックス区間と、イ
   ンデックスの分割方法を示す情報とに基づき、ソース・
   プログラム中の一つの一次元配列データおよび命令を、
   上記ソース・プログラム中の命令部の各プロセッサへの
   分割と、一次元配列データの各プロセッサのメモリへの
   分割とが一致するように複数個に分割したオブジェクト
   ・プログラムを各プロセッサ毎に生成し、マルチ・プロ
   セッサ計算機システムの各プロセッサに当該オブジェク
   ト・プログラムを割り当て、 上記各プロセッサは、上記割り当てられたオブジェクト
   ・プログラムを並列実行することを特徴とするマルチ・
   プロセッサ計算システム。