JPH04152465A - データ処理システム及びデータ処理方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 Ｃ概　要〕 プログラムを複数の計算機で並列実行するデータ処理シ
ステム及びデータ処理方法に関し同期処理のオーハヘン
ドを少なくし実行時間を短くすることを目的とし。

所定の処理を複数に分割してなる複数の並列実行単位と
、前記並列実行単位を並列実行する複数の計算機と、前
記並列実行の際に前記複数の計算機の間の同期を一般命
令のみを用いてとるｗｕ手続部とを備えるように構成す
る。

Ｃ産業上の利用分野〕 本発明はデータ処理システム及びデータ処理方法に関し
、更に詳しくは、プログラムを複数の計算機で並列実行
するデータ処理システム及びデータ処理方法に関する。

複数の計算機（プロセッサ）でプログラムを並列実行す
ることにより、その実行時間を短くすることが行われる
。

〔従来の技術〕

１つのプログラム等を複数の計算機で並列実行する場合
に、各計算機の間で同期を取って演算を行わないと正し
い実行結果が得られない場合がある。

今１例えば、第７図（ａ）図示の如きＦＯＲＴＲＡＮで
記述された（Ｄ○）ループを並列実行する場合を考える
。ループは、汎用プログラムを並列実行する場合に、最
も容易に並列化できる。

第７図（ａ）の逐次実行用オリジナルプログラムの並列
実行イメージは、第７図（ｂ）図示の如くになる。この
イメージは１次のようなものである。即ち、ループの各
回転を並列実行単位とする。

２つの計算機で並列実行する。このために、ループのパ
ラメータの奇偶を利用して２巡回分配方式により第７図
（ｂ）図示の手続きに分割する。

第７図（ｂ）の手続きを並列実行した場合、計算機−１
においてＩ＝ＩをＡ（ｒ＋１）へ代入する代入文が実行
されないうちに、計算機−２において１＝２でのＡ　（
Ｉ）の参照が行われることがある。この場合、実行結果
は、第７図（ａ）の逐次実行プロ°グラムの結果と異な
るものとなってしまう。

そこで、第７図（ｃ）図示の如く、同期処理を行う手続
きｐｏｓ　を及び−ａｉｔを設けて、実行結果を保証し
ている。ｓｙｎ＃１及びｓｙｎ＃２は、同期処理用に使
用される変数（同期用変数）でありｐｏｓ　ｔｅｄ″１
ｗａｉｔｉｎｇ”及び”ｃｌｅａｒｅｄ″の３種類の値
をとる。ｐｏｓｔ、　ｗａｉｔ及びｒｅｓｅｔは、同期
用変数を使用して同期処理を行う手続きである。即ち。

Ｗａ口は、引数として与えられた同期用変数の値がｐｏ
ｓ　ｔｅｄ”でなければ、その値を“−ａｉｔｉｎｇ”
に変更し１次に値が“ｐｏｓ　ｔｅｄ”に変更されるま
で処理の続行を休止する手続きである。ｐｏｓ　ｔは、
引数の同期用変数の値を“ｐｏｓ　ｔｅｄ“にする手続
きで、休止している手続きの実行が再開される。　ｒｅ
ｓｅｔは、同期用変数の値が“ｐｏｓ　ｔｅｄ”のとき
これを“ｃｌｅａｒｅｄ”に変更する手続きである。

第７図（ｃ）の手続きを並列実行した場合、ループの各
回転においてｐｏｓｔ、　ｗａｉｔ及びｒｅｓｅ　を手
続きが実行され、同期のポイント（ｗａｉｔ手続き）に
おいて同期がとられる。

〔発明が解決しようとする課題〕

前述の従来技術においては、同期用変数ｓｙｎ　＃１及
びｓｙｎ＃２が、２つの計算機に共有されている必要が
ある。しかし、このため、逆に、２つの計算機が略同時
に１つの同期用変数について参照変更を行う可能性があ
る。この場合、当該同期用変数は破壊され、結果として
、正しい処理が行われなくなる。

そこで、同期用変数の参照１手続きの休止及び手続きの
再開という処理を、不可分に行う必要がある。このため
に、同期処理用の特殊なハードウェア命令（例えば、Ｔ
／Ｓ命令）が使用される。

ところが、この種の命令は一般の命令よりも実行時間が
長くなるということが特徴的事項であるので、多数（各
回転毎）のｐｏｓｔ＋　ｗａｉｔ、　ｒｅｓｅｔの処理
のために、多くのオーバへ、ドが生してしまうという問
題がある。また、結果として、並列実行した割には、実
行時間が短くならないという問題もある。

本発明は、同期処理のオーバヘッドを少なくし実行時間
を短くすることが可能な並列実行用のデータ処理システ
ム及びデータ処理方法を提供することを目的とする。

〔課題を解決するための手段〕

第１図は本発明の原理構成図であり１本発明によるデー
タ処理システムを示す。

第１図において、１は計算機、２は同期用変数。

３はｗｕ手続部、４は並列実行単位である。

複数の計算機ｋｌ及びＩ−２は、各々、並列実行単位４
−１及び４−２を実行する。即ち、ある所定の処理は、
複数の並列実行単位４−１．４２に分割され、複数の計
算機１−１及び１−２で並列実行される。

並列実行単位４−１及び４−２は、Ｄ○ループの如きル
ープの回転の各々である。なお１図においては、第１の
計算機１−１で実行される並列実行単位の集まりを並列
実行単位４−１で示す。並列実行単位４−２についても
同様である。

複数の同期用変数２−１及び２−２　（ｓｙｎ＃　１及
びｓｙｎ＃２）は、前述の３種類の値ではなく、各々、
計算機１１及び１−２において実行されるループの回転
の状態即ち並列実行単位４−１及び４−２の回転の状態
（回転順序番号）を示す。計Ｘ＠Ｉ−１に対応する同期
用変数２−１は２計算機１−１のみが更新でき、計算機
１−２は参照が許されるのみである。同期用変数２−２
についても同様である。

ｗｕ手続部３−１及び３−２は、　ｗｕ　（ｗａｉｔｕ
ｎｔｉｌ）処理を行うことにより、各々、自社Ｘ機１１
及び１−２と他社電機１−２及び１−１との同期をとる
。即ち、ｗｕ手続部３−１は、自計算機１−１における
回転の状態（即ちｓｙｎ＃１に等しい）と、他社算１１
＠ｌ−２における回転の状態を示す同期用変数２−２　
＜ｓｙｎ＃　２　）とを比較し２両者の関係が所定のも
のとなるまで（ｕｎｔｉｌ）、その並列実行単位４−１
の実行を待つ（ｗａｉｔ）。ｗｕ手続部３−２について
も同様である。

〔作　用〕

計算機１−１は２並列実行単位４−１の実行において、
その回転の状態を示すように同期用変数２−１を更新す
る。同様に、同期用変数２−２も計算機１−２によって
更新される。

実行中の並列実行単位４−１がら呼び出されたＷＩ４手
続部３−１は、内針算１！１−１の回転の状態（ｓｙｒ
＋＃　ｌ　）と、他計算機１−２の同期用変数２２　（
ｓｙｎ＃　２　）とを比較し１両者の関係が所定のもの
となるまで待つ。Ｗｕ−＋峰部３−２についても同様で
ある。

ここで５例えば、ｗｕ手続部３−１が、　　ｓｙｎ＃２
−１≧ｓｙｎ＃１まで処理を待ち、この関係が成立した
時に次処理を実行するとする。一方、ｗｕ手続部３−２
が、　　ｓｙｒ＋＃１≧ｓｙｎ＃２まで処理を待ち、こ
の関係が成立した時に次処理を実行するとする。これに
より、計算機１−１におけるループの１回転の実行の終
了を待って、計算機１−２において次の１回転の実行が
開始される。また計算機１−２におけるループの１回転
の実行の終了を待って、計算機１−１において次の回転
の実行が開始される。

以上により、　ｐｏｓｔ、　ｗａｉｔ、　ｒｅｓｅｔ等
の特殊なハードウェア命令を用いることなく１通常の一
般命令のみで、高速に計算機間の同期をとることができ
る。

〔実施例］ （ａ）第１の実施例 第２図は、実施例構成図である。

第２図において、５はロードされた並列実行単位、６は
ｗｕ呼出部、７は回転順序番号領域、８はＤＡＳＤ等の
外部メモリ、９は共有メモリである。

この実施例は、２台の計算機１−１及び１−２が、各々
、（Ｄｏ）ループの奇数回転及び偶数回転を同期をとり
つつ並列実行する例である。

計算機１−１及び１−２は、中央処理装置（ＣＰＵ）及
び主メモリからなる。この主メモリには、外部メモリ８
から並列実行単位（ロードモジュール）４−１及び４−
２が各々ロードされ実行状態の並列実行単位５−１及び
５−２とされる。また、ｗｕ手続部３−１及び３−２も
、主メモリ上に存在する。更に、主メモリの所定の領域
が回転順序番号領域７−１及び７−２として、並列実行
単位５−１及び５−２の回転順序番号（Ｊ。

ｊ）を格納するために用いられる。

計算機１−１及び１−２は、共有メモリ９を備える。共
有メモリ９の所定の領域が、同期用変数１−１及び２−
２の格納のための領域として用いられる。

ロードされた並列実行単位５−１は、ｗｕ手続部３−１
の呼出しに先立って、自己の回転１＠序番号Ｊを回転順
序番号領域７−１にセットし、また当該番号ｊを用いて
共有メモリ９中の自計算機１１の同期用変数２−１を更
新する。また、ｗｕ手続部３−１の呼び出し後、即ち、
ｗｕ手続部３１からの復帰後に１次の回転の実行のため
に当該番号Ｊを＋１だけカウントアツプする。

並列実行単位５−１のｗｕ呼出部６−１はｗｕ手続部３
−１を呼び出し、これに所定の関係式を渡して、ｗｕ処
理を依願する。

ｗｕ手続部３−１は、自計算機１−１の回転順序番号領
域７−１を参照して２回転順序番号Ｊを知る。従って１
回転順序番号領域７−１は、並列実行単位５−１からｗ
ｕ手続部３−１へ当該番号Ｊを渡すための手段である。

また、ｗｕ手続部３１は、共有メモリ９中の他計算機１
−２の同期用変数２−２　（ｓｙｎ　＃２）を参照して
、これを知る。この時、ｗｕ手続部３−１は同期用変数
２２の参照ができるのみであるので、当該変数ｓｙｎ＃
２を破壊することはなく、また、その更新とは無関係に
参照することができる。

ｗｕ手続部３−１は、参照した当該番号Ｊ及び変数ｓｙ
ｎ＃２を、並列実行単位５−１から渡された関係式を用
いて比較し、当該関係式が満たされるまで待つ。そして
、当該関係式が成立した場合に、並列実行単位５−１に
復帰する（制御を戻す）。従って、この復帰の時点で、
他計算機１２の同期用変数２−２が所定の値となってい
るので１　同期がとられている。

Ｗｕ呼出部６−２及びｗｕ手続部３−２についても同様
である。

第３図は並列実行処理フローである。

■　並列実行単位４−１及び４−２を実行する上位プロ
グラムが、並列実行を開始するために同期用変数２−１
及び２−２をリセントする（「０」とする）。この後、
並列実行単位４−１及び４−２が、各々、計算機１−１
及び１−２にロードされ、並列実行される。

■　並列実行単位５−１が、自己の回転順序番号Ｊの初
期値として「１」を１回転順序番号領域７−１にセット
する。

並列実行単位５−２も、同様の処理を行う（記号はｊを
用いる）。

なお、処理■乃至■において並列実行単位５１の実行す
る処理は、並列実行単位５−１の実行する処理と同一で
あるので、以下、その説明は省略する。

■　並列実行単位５−１が、第３回転の処理の実行を開
始する。

■　並列実行単位５−１が、他計算機１−２即ち並列実
行単位５−２から参照される値の処理を行う。

■　並列実行単位５−１が、自己の同期用変数２１に９
回転順序番号領域７−１に格納された値ｒＪ」をセント
する。

■　この後、所定の処理を行った後、ｗｕ呼出部６−１
が、ｗｕ手続部３−１を呼び出す。

ｗｕ＋碕部３−１は、ｗｕ処理を行って、他社算４１！
Ｌ−２即ち並列実行単位５−２との同期をとる。

■　同期がとられた後、並列実行単位５−１が。

他社電機１−２即ち並列実行単位５−２で処理された値
を参照した処理を行う。

■　並列実行単位５−１が１次の回転の実行のために１
回転順序番号Ｊを＋１だけカウントアツプして５回転順
序番号領域７−１にセットする。

この後、処理■以下を所定の回数だけくり返して、並列
実行を終了する。

以上の処理において、処理■が同期処理■の後に実行さ
れるので、正しい値を用いた処理が可能となる。逆に、
同期後の処理に必要な処理■が同期処理■前に実行され
るので、同期を取った後。

直ちに処理■を実行できる。そして、処理■を処理■の
直後に実行しているので、他方が処理■の状態にあれば
直ちに同期をとることができ、また。

同期用変数を常に最新の状態として同期処理に備えるこ
とができる。

第４図はｗｕ処理フロー（同期処理フロー）である。

以下の処理は、ｗｕ手続部ｉｆ又は３−２が行う。

■　自計算機１−１又は１−２の同期用変数２−１又は
２−２の更新に用いられた回転順序番号Ｊ又はｊを５そ
の回転順序番号領域７−１又は７−２を参照して知る。

■　ｗｕ呼出部６−１又は６−２から引数としで渡され
た関係式に基づいて、まず、当該番号Ｊ又はｊを用いた
演算を行う。

■　他社電機１−２又はｌ−１の同期用変数２−２又は
２−１　（ｓｙｎ＃　２又はｓｙｎ；＃１）を、共有メ
モリ９を参照して知る。

■　同期用変数ｓｙｎ＃２又はｓｙｎ＃１と、処理■の
演算結果とを、前記関係式に基づいて比較する。

■　他計算機の同期用変数が前記演算結果より小さい場
合、ウェイト状態となり、処理■以下をくり返す。

他社ＸＩ！の同期用変数が前記演算結果以上である場合
、処理を終了し、制御を並列実行単位５−１又は５−２
へ戻す。

第５図はプログラムの一例を示す図であり、第７図図示
と同様の例を本実施例によって実現したものである。

’ｓｙｎ　＃　１−０　」及びｒｓｙｎ’＃２＝Ｑｊは
、第３図の処理■に対応し、上位プログラムにより実行
される。

並列実行単位５−１　（４−１）において　ｒＪ＝ｌＪ
により、同期順序番号Ｊの初期値が「１」にセットされ
る。この値は０回転順序番号領域７−１にセーブされる
。

ｒＤｏ　　１０１＝１．１００．２Ｊにより、当３５　
Ｄ　Ｏループの奇数回転が、並列実行単位５−１とされ
る。一方、　　「Ｄｏ　　１０　　ｉ＝２，１００２」
により、偶数回転が、並列実行単位５−２とされる。こ
れらは、第３図の処理■に当たる。

ｒＡ　（１＋１）＝Ｗ　（Ｉ）Ｊは、その代入結果が、
他の並列実行単位５−２におけるｒＸ　（ｉ）＝Ａ（ｉ
）」で参照される。即ち、第３図の処理■に当たる。

’ｓｙｎ＃１＝ＪＪにより、共有メモリ９中の同期用変
数２−１に２回転順序番号領域７−１に格納された値Ｊ
が、セントされる。これは、第３図の処理■に当たる。

ｒｗａｉｔ−ｕｎｔｉｌ　Ｊは、ｗｕ呼出部６−１であ
り。

’　（ｓｙｎ　＃２＞＝Ｊ−１）　Ｊを満足すべき関係
式として渡す。呼出されたｗｕ手続部３−１はｗｕ処理
により他計算機１−２と同期をとった後ｗｕ呼出部６−
１の直後のｒＸ　（１）　＝Ａ　（Ｎ　Ｊに復帰する。

これは、第３図の処理■に当たる。

ｒＸ　（１）＝Ａ　（１）Ｊは、他の並列実行単位５−
２におけるｒＡ　（ｉ＋１）＝Ｗ　（ｊ）Ｊの結果を参
照する。即ち、第３図の処理■に当たる。

この時数に同期がとられているので、正しい値のＡ（ｉ
＋１）を参照できる。

ｒＪ＝Ｊ＋ｌＪは、第３図の処理■に当たる。

並列実行単位５−２　（４−２）についても同様である
。

ここで、ｗｕ手続きにおいて満足すべき関係式について
説明する。ｗｕ手続部３−１及び３−２において満足す
べき関係式は、自計算機１−１又ハ１−２　ト他社Ｘｌ
１１−２又ハ１−１　トノ間の距Ｍ（計電機間距ｔｌ）
ｘによって決定される。距離Ｘは、以下の如く定義され
る。即ち、ループの第１回転２第２回転、・・・・・・
、第ｎ回転の実行が割り当てられる計算機を、各々、第
１計算機、第２計算機、・・・・・・、第ｎ計算機と呼
ぶこととする。そして、第ｊ計算機についての第１計算
機と第ｊ計算機間の距離Ｘを’ｊ−ｉＪであると定義す
る。

本実施例では、計算機１−１については、Ｘ＝１（第１
回転）−２（第２回転）−一１であり。

計算１！１−２については、ｘ＝２（第２回転）１　（
第１回転）−】である。距＃Ｘが負である場合、即ち、
ｗｕ手続部３−１は１回転順序番号Ｊ１を求めるように
される。正である場合、即ちｗｕ手続部３〜２は、当該
処理は行わないようにされる。即ち１回転順序番号ｊを
そのまま用いる。

Ｗｕ手続部３−１からみると、同期用変数ｓｙｎ＃２が
Ｊ−１（以上）であれば、ループの１つ前の回転のｒＡ
　（ｉ＋１）　−ｗ　（ｉ）Ｊが終了しているので、同
期がとられたことになる。ＷＵ手続部３−２からみると
、同期用変数ｓｙｎ＃１が、ｊ（以上）であれば、同様
にループの１つ前の回転の当該処理が終了しているので
、同期がとれたことになる。

（ｂ）第２の実施例 第６図は、他の実施例構成図である。

この実施例は、ｎ個の仮想プロセッサ１０（１０−１乃
至１Ｏ−ｎ）に対して、ループの各回転を割り当てて並
列実行する例である。仮想プロセッサ１０は、第１の実
施例における計算機１に相当するものである。共有メモ
リ９には、各仮想プロセッサ１０−１乃至１０−ｎに対
応する同期用変数ｓｙｎ＃１乃至ｓｙｎ＃ｎが、所定の
領域に格納される。同期用変数ｓｙｎ＃１乃至ｓｙｎ＃
ｎは。

対応する仮想プロセッサ１０−１乃至１０−ｎの回転の
状態を示す。

この実施例では、各仮想プロセッサ１０のｗｕ手続部３
（図示せず）において満足すべき関係式は、以下の如く
に定められる。

まず、ループの第１回転、第２回転、・・・・・・、第
ｎ回転の実行が割り当てられた仮想プロセッサ１０を、
各々、第１プロセツサ、第２プロセツサ。

・・・・・・、第ｎプロセッサと呼ぶこととする。プロ
セッサ間距離Ｘは、前述の計算機間圧Ｍｘと同様に定義
される。また、第１プロセツサに着目すると第１回転２
第ｉ＋ｎ回転、第ｉ＋２ｎ回転、・・・・・・が割り当
てられる。そこで、第ｉ及び第１プロセツサについて、
第ｉ＋ＫＸｎ回転と第ｊ　＋　Ｌ　Ｘ　ｎ回転（Ｌ≧に
、　　ｉ≦ｎ、Ｊ≦ｎ）との間の時間距離を、ｒＬ−Ｋ
Ｊであると定義する。

ループの全ての回転の間のデータ依存関係（Ｉ　Ｉ　Ｄ
　：　Ｉｎｔｅｒ　Ｉｔｅｒａｔｉｏｎａｌ　Ｄｅｐｅ
ｎｄｅｎｃｙ）に対して同期処理が必要となる。各ＩＩ
Ｄ毎に、同期用変数５ｙｎ４１等を用いた関係式による
ｗｕ処理を行う。

今、ＩＩＤの時間距離をＤとすると１ｗａｉｔしている
仮想プロセッサ１０（のＷＵ手続部３）はｗａｉｔされ
ている仮想プロセッサ１０の同期用変数が−ａｉｔＬ、
ている仮想プロセンサ１０における（回転順序番号＋Ｄ
）に等しいか大きくなるまで。

ｗｕ手続きにより待つ、プロセンサ間距離が負の場合、
（回転順序番号＋Ｄ−１）に等しいか大きいという条件
が用いられる。

なお、第１の実施例は１時間距離Ｄ＝Ｏの場合である。

本実施例は、汎用プログラムを並列実行する場合、最も
容易に並列化できる（ＤＯ）ループの各回転を、その時
点で空いている（負荷の少ない）仮題プロセッサに割り
当てる場合に有効である。

〔発明の効果〕 以上説明したように１本発明によれば、並列実行用のデ
ータ処理システム及びデータ処理方法において、同期用
変数を用いたｗｕ処理を行う手続きを用いることにより
、一般命令の組合わせのみで同期処理を実現できるので
、同期処理のオーバヘッドを削減し、かつ、同期処理を
高速化できるので、並列実行によるデータ処理を高速化
することができる。

【図面の簡単な説明】

第１図は本発明の原理構成図 第２図は実施例構成図。 第３図は並列実行処理フロー 第４図はｗｕ処理フロー 第５図はプログラムの一例を示す図２ 第６図は他の実施例構成図。 第７図は従来技術説明図。 １は計軍機１２は同期用変数５３はｗｕ手続部。 ４及び５は並列実行単位、６はｗｕ呼出部、７は回転順
序番号領域、８は外部メモリ、９は共有メモリ、１０は
仮想プロセッサである。

Claims (7)

【特許請求の範囲】
1. （１）所定の処理を複数に分割してなる複数の並列実行
   単位（４）と、 前記並列実行単位（４）を並列実行する複数の計算機（
   １）と、 前記並列実行の際に前記複数の計算機（１）の間の同期
   を一般命令のみを用いてとるｗｕ手続部（３）とを備え
   る ことを特徴とするデータ処理システム。
2. （２）前記複数の計算機（１）の各々に対応し、当該対
   応する計算機（１）の回転の状態を示す複数の同期用変
   数（２）を備え、 前記ｗｕ手続部（３）が、自計算機（１）の前記回転の
   状態と他計算機（１）の前記同期用変数（２）との関係
   が所定の関係となるまで待つことによって前記同期をと
   る ことを特徴とする請求項（１）記載のデータ処理システ
   ム。
3. （３）前記並列実行単位（４）はｗｕ呼出部（６）を備
   え、 前記ｗｕ手続部（３）は前記ｗｕ呼出部（６）から呼び
   出されることによって前記同期をとることを特徴とする
   請求項（２）記載のデータ処理システム。
4. （４）前記同期用変数（２）は、当該同期用変数（２）
   が対応する前記計算機（１）によってのみ更新可能とさ
   れ、当該対応する計算機（１）以外の計算機（１）から
   は参照のみが可能とされる ことを特徴とする請求項（２）記載のデータ処理システ
   ム。
5. （５）所定の処理を複数に分割してなる複数の並列実行
   単位（４）を複数の計算機（１）で並列実行するデータ
   処理方法において、 前記複数の計算機（１）の各々が、 他計算機（１）から参照される値の処理を行い、 自計算機（１）の回転の状態を示す値を同期用変数（２
   ）にセットし、 一般命令のみを用いて所定の他計算機（１）との間の同
   期をとり、 他計算機（１）の値を参照した処理を行う ことを特徴とするデータ処理方法。
6. （６）前記計算機（１）で実行される前記並列実行単位
   （４）がｗｕ手続部（３）を呼び出し、前記ｗｕ手続部
   （３）が、自計算機（１）の前記回転の状態と他計算機
   （１）の前記同期用変数（２）との関係が所定の関係と
   なるまで待つことによって前記同期をとる ことを特徴とする請求項（５）記載のデータ処理方法。
7. （７）前記呼び出しの際に、前記所定の関係を表す関係
   式を、前記並列実行単位（４）が前記ｗｕ手続部（３）
   へ渡す ことを特徴とする請求項（６）記載のデータ処理方法。