JPH08106440A - 分散共有メモリ計算機システム - Google Patents

Abstract

(57)【要約】 （修正有） 【目的】 分散共有メモリへのアクセス性能を向上させ
る。 【構成】 メインメモリ106は、共有データ一貫性保証
制御指定命令列メモリ201、作業用メモリ202、共有デー
タメモリ203、共有データ一貫性保証制御命令列メモリ2
04、共有データ管理テーブル205、及び共有データ待ち
カウンタ付き優先度キュー206を備える。プロセッサ104
が共有データ一貫性保証制御指定命令列メモリ201の命
令列を実行すること、又はネットワークインタフェース
107から他計算機のネットワークパケットを受信するこ
とにより、共有データ一貫性保証制御命令列メモリ204
の命令列が実行される。共有データ一貫性保証制御命令
列メモリ204の命令列が共有データ管理テーブル205、及
び共有データ待ちカウンタ付き優先度キュー206を参
照、又は変更することにより、共有データメモリ203に
格納された共有データの一貫性、及び並列に動作するプ
ログラムの同期が制御される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ネットワークで結合さ
れた複数の計算機で構成される疎結合計算機システムに
おいて、物理的に分散配置されたメモリ上のデータを別
計算機上で実行中の複数のプログラムで共有するための
分散共有メモリ方式に係わり、特にネットワーク資源を
有効利用し、その結果、分散共有メモリへのアクセス性
能を向上させる分散共有メモリ方式に関する。

【０００２】

【従来の技術】疎結合計算機システムにおいて、各計算
機上に物理的に分散したメモリを、プログラマに対して
は論理的に共有しているように見せる技術を分散共有メ
モリと呼ぶ。

【０００３】分散共有メモリの従来技術の例として、共
有データにアクセスする際に共有データの一貫性を保証
する区間を指定するMuninシステムがある。Muninシステ
ムはJ.B.Carter他の論文「Implementation and Perform
ance of Munin」、第13回オペレーティングシステム原
理シンポジウム会議録(the 13th ACM Symposium on Ope
rating Systems Principles)、1991年10月、152ー164頁
で開示されている。Muninでは、共有データメモリへの
書き込みまたは読み込み操作をする際、その操作をする
前に一貫性保証を要求する命令と、その操作をした後に
一貫性保証を解除する命令をプログラム中に記述する。
一貫性保証を要求する命令をacquire命令,一貫性保証を
解除する命令をrelease命令と呼ぶ。acquire命令とrele
ase命令で挟まれた区間で書き込み操作があった場合に
は、その変更は各計算機上に存在する共有データに直ち
に反映されるのではなく、release命令が発行された後
でその変更が反映される。

【０００４】このようにすると、一貫性保証区間で共有
データに対する書き込み操作を複数回行っても、他の計
算機へのデータの転送は一貫性保証区間の終了後の一回
だけしか発生しない。このため、無駄なデータ転送を防
ぐことが可能であり、ネットワーク資源を有効利用する
ことができる。

【０００５】Muninの方式では、同じ共有データに対す
るacquire命令が複数計算機で発行される場合があるの
で、一貫性保証区間内の処理を実行する順序を制御する
ために、同期手段を別に提供している。

【０００６】一方、ネットワークで結合され、各計算機
が独立にアドレス空間を持つような疎結合計算機におい
て、広く用いられている同期手段としてはバリア同期が
ある。バリア同期を実現するためには、ネットワークと
は別に専用の信号線を設ける方式、ネットワークパケッ
トによって実現する方式がある。前者の専用の信号線を
設ける方式は、特別なハードウェアが必要となり高価で
ある。一方、後者は、ネットワークパケットを各計算機
ごとに送信する必要がある。バリア同期については、
「並列処理マシン、富田真治・末吉敏則著、オーム社、1
989」の133ページから134ページに示されている。

【０００７】

【発明が解決しようとする課題】従来の技術における問
題点は次のとおりである。

【０００８】Muninシステムでは、同期手段が一貫性保
証手段とは別に提供されているため、パケットのやりと
りによって同期を実現する疎結合計算機システムにおい
ては、パケットを送受信する回数が増加する。このた
め、パケット量が増加し、ネットワークに負担をかける
という第１の課題がある。

【０００９】各計算機が個々のOSによって独立に制御さ
れ、マルチプロセス・マルチユーザ環境で動作する疎結
合計算機システムにおいては、各計算機に均質に演算を
割り振っても、各計算機の負荷やスケジューリングの都
合によって、動作がばらばらになる可能性がある。ま
た、アプリケーションによっては、計算機間の仕事内
容、量の違いで各計算機の処理時間が異なる場合があ
る。したがって、従来一般に用いられていたバリア同期
では、無駄な待ち時間が生じるという第２の課題があ
る。

【００１０】本発明の目的は、ネットワーク資源を有効
利用するために一貫性保証制御と同期制御を少ないネッ
トワークパケット数で実現し、その結果、分散共有メモ
リへのアクセス性能を向上させる分散共有メモリ計算機
システムを提供することにある。

【００１１】本発明の他の目的は、同期の際に生じる無
駄な待ち時間を削減し、プログラムを効率的に実行する
分散共有メモリ計算機システムを提供することである。

【００１２】

【課題を解決するための手段】本発明では、共有データ
の一貫性保証区間をプログラム中で指定するために、一
貫性保証指定手段と、その一貫性保証の指定を解除する
一貫性保証解除手段を設ける。また、一貫性保証区間内
で他計算機から同じ共有データに対して一貫性保証要求
を受けた時にその要求を蓄える手段を設ける。一貫性保
証要求を蓄える手段は、上記一貫性保証要求の数に関わ
るカウンタ手段と、共有データに対するアクセス順序を
制御する値を蓄える手段を備えている。これらの手段を
持たせることにより、疎結合計算機システム上の分散共
有メモリにおいて、パケットの量を増やすことなく、同
期処理を含む共有データの一貫性を保証することが可能
となるため、第１の課題を解決できる。また、共有デー
タへのアクセスに関係する計算機間だけで同期をとるこ
とにより、無駄な待ち時間を削減することができるた
め、第２の課題も解決できる。

【００１３】さらに、上述の一貫性保証指定手段を2つ
に分離し、一貫性保証制御を予約する手段と、その予約
が受理されるのを待つ手段を設ける。こうすることによ
り、一貫性保証制御を指定する間にプログラムを中断さ
せないで、別の計算を多重に実行することも可能とな
る。

【００１４】

【作用】本発明によれば、共有データの一貫性保証のた
めの同期と並列プログラムを制御するための同期のため
に必要なネットワークパケットを少なくすることができ
るので、ネットワーク資源を有効に活用することができ
る。

【００１５】また、共有データへのアクセスに関係する
計算機間だけで同期をとることにより、全計算機で一斉
に同期をとる方法に比べて無駄な待ち時間を削減するこ
とができるため、プログラム実行時の効率が向上する。

【００１６】

【実施例】図1は、本発明における疎結合計算機システ
ム100の一実施例である。

【００１７】本図において、疎結合計算機100は、複数
の計算機101をネットワーク102で接続して構成される。
計算機101において、103は計算機を構成する各ブロック
間のデータ転送路であるシステム・バス、104はプログラ
ムを実行するプロセッサ、103はプログラムやデータを
格納する磁気ディスク等の補助記憶装置、106はプログ
ラム実行中に該プログラムやデータを格納するためのメ
インメモリ、107はネットワーク102との入出力を制御す
るためのネットワークインタフェースである。本発明に
よる分散メモリ方式は、例えば計算機101(1)上のプログ
ラムと計算機101(2)上のプログラムが並列実行する時
に、データを共有する際に適用される。

【００１８】図2は、本発明におけるメインメモリ106の
一実施例を示すブロック図である。

【００１９】メインメモリ106は、共有データ一貫性保
証制御指定命令列メモリ201、作業用メモリ202、共有デ
ータメモリ203、共有データ一貫性保証制御命令列メモ
リ204、共有データ待ちカウンタ付き優先度キュー205、
共有データ管理テーブル205から構成される。

【００２０】共有データ一貫性保証制御指定命令列メモ
リ201、及び共有データ一貫性保証制御命令列メモリ204
に格納されたデータはシステムバス103を介してプロセ
ッサ104に対する命令として読み込まれ、作業用メモリ2
02、共有データメモリ203、共有データ待ちカウンタ付
き優先度キュー205、共有データ管理テーブル205のデー
タに対する読み込み、書き込み動作、あるいはネットワ
ークインタフェース107に対する制御コマンド、及びデ
ータ転送を行う。共有データ一貫性保証制御指定命令列
メモリ201にの中に格納される命令として共有データメ
モリ203に対する一貫性保証を指定する命令と一貫性保
証を解除する命令がある。プロセッサ104はこれらの一
貫性保証指定命令および一貫性保証解除命令をシステム
バス103を介して読み込み、システムバス103を介してネ
ットワークインタフェース107に対する制御コマンド、
及びデータを転送する。

【００２１】共有データ一貫性保証制御命令列メモリ20
4の命令は共有データ管理テーブル205及び共有データ待
ちカウンタ付き優先度キュー206を用い、共有データメ
モリ203のデータ内容を他の計算機101にある共有データ
メモリ203の内容と一致するように動作する。共有デー
タ一貫性保証制御指定命令列メモリ201に格納された一
貫性保証制御命令をプロセッサ104が読み込むと、プロ
セッサ104は共有データ一貫性保証制命令列メモリ204中
の命令を呼び出す。

【００２２】次に共有データ一貫性保証制御命令列メモ
リ204中の命令は、プロセッサ104に読み込まれ、共有デ
ータ管理テーブル205と共有データ待ちカウンタ付き優
先度キュー206を参照して、必要な情報をネットワーク
インタフェース107、ネットワーク102を介して他の計算
機101に転送する。

【００２３】他の計算機101からネットワーク103を介し
てネットワークインタフェース107にパケットが転送さ
れると、プロセッサ104が割り込みを発生して、他の計
算機からパケットが到達したことを検出する。なお、ネ
ットワークパケットが他の計算機101から送られてきた
のを検出する方法としては、定期的にプロセッサ104が
ネットワークインタフェース107を監視することでも実
現可能である。

【００２４】他の計算機101からネットワークパケット
が転送されたことをプロセッサ104が検出すると、共有
データ一貫性保証制御命令列メモリ204中の命令を実行
する。共有データ一貫性保証制御命令列メモリ204中の
命令は共有データ管理テーブル205、共有データ待ちカ
ウンタ付き優先度キュー206を参照し、必要であれば、
システムバス103を介して共有データメモリ203に格納さ
れた共有データの更新を行う。共有データ管理テーブル
205は自計算機101の共有データメモリ203に格納してあ
るデータの一貫性を保持するために用いる。共有データ
待ちカウンタ付き優先度キュー206は、他の計算機101か
らの共有データに対する要求を保持しておくバッファで
ある。

【００２５】図3は本発明におけるメインメモリ106に格
納する共有データ一貫性保証制御指定命令列メモリ20
1、作業用メモリ202、共有データメモリ203の一実施例
をより詳細に説明する図である。

【００２６】命令列301は、共有データ一貫性保証制御
指定命令列メモリ201に格納されている一貫性保証制御
命令を含む命令列を、計算機のアプリケーションから起
動するように、言語Cで記述した一実施例である。命令
列301は、共有データの生成を行なう命令302、一貫性保
証を指定する命令303、共有データに対して更新を行う
命令304、一貫性保証を解除する命令305から構成されて
いる。プログラマは、並列プログラムを記述する際に、
各計算機のアプリケーションの優先度等を考慮して、共
有データの生成および更新、一貫性保証およびその解除
などを指定する。

【００２７】命令302は任意の共有データを示す番号
「2」と共有データのサイズを指定する部分から構成さ
れており、この例では整数型intの要素サイズで大きさ1
00の配列データを生成し、tableにその配列データの領
域へのポインタが格納される。この命令を実行すると各
計算機の共有データメモリ203の中にtableで差し示され
る共有データ320が生成される。共有データメモリ203内
の共有データは複数個存在する。命令303は、共有デー
タ生成命令302で生成した共有データ320の一貫性保証を
指定する一貫性保証指定命令である。この命令303で
は、一貫性保証をする共有データを指定するための共有
データ番号、共有データに対する要求の待ち数、共有デ
ータに対する要求の優先度を指定する。命令304は、命
令303で一貫性保証指定を行った共有データを更新する
命令である。命令305は、共有データ320を示す番号
「２」の一貫性保証を解除する一貫性保証解除命令であ
る。命令304では共有データ320に対して複数回の更新操
作があることに注意されたい。命令304での共有データ3
20に対する複数の更新操作は、一貫性保証解除命令305
まで各計算機101の上の共有データ320に対する変更が延
期され、ネットワーク108を介して転送されるデータ量
を削減することができる。

【００２８】命令302、303、305は、共有データ一貫性
保証制御命令列内の命令を起動させる制御コマンドを発
行する。これらの制御コマンドの発行が検出され、共有
データ一貫性保証制御命令列メモリが起動されると、共
有データ管理テーブルへの登録、変更を行い、必要に応
じてネットワークインタフェース107を介して他計算機
内の共有データ320の一貫性を制御する。作業用メモリ2
02は、自計算機内で一時的に用いる変数、たとえば、命
令列301で用いられている変数「ｉ」310が格納される。

【００２９】図4は、共有データ管理テーブル205、共有
データ待ちカウンタ付き優先度キュー206の一実施例で
ある。

【００３０】共有データ管理テーブル205は共有データ3
20ごとに共有データ番号401、共有データ開始アドレス4
02、共有データのサイズ403、オーナ計算機番号404、予
約済みフラグ405、使用中フラグ406、共有データ待ちキ
ュー番号408を持つ。共有データ待ちキュー番号408は、
複数個存在する共有データ待ちカウンタ付き優先度キュ
ー206の一つを差し示す。各共有データ待ちカウンタ付
き優先度キュー206は要求待ちカウンタ407と、要求待ち
計算機リスト410から構成される。要求待ち計算機リス
ト410は要求待ち計算機411、及び要求待ち優先度412の
組をエントリとして持つ優先度キューで構成される。共
有データ番号401は共有データメモリ203に複数存在する
共有データを識別するための番号で疎結合計算機システ
ム100の各計算機101で共通の番号である。共有データ開
始アドレス402と共有データサイズ403によって、共有デ
ータ320の領域の位置と大きさを指定する。

【００３１】オーナ計算機番号404は、共有データ番号4
01で示された共有データの最新状態を持つ計算機を示
す。オーナ計算機番号404と自計算機番号404が等しい時
には、その共有データのオーナは自計算機である。予約
済みフラグ405は一貫性保証指定命令303がすでに実行さ
れていることを示している。この予約済みフラグをチェ
ックすることによって、同じ共有データに対して複数の
一貫性保証要求が出された場合にはエラーとする。使用
中フラグ406は、一貫性保証指定命令303でオーナ計算機
となってから、一貫性保証解除命令305が発行されるま
での間、「１」となるフラグである。共有データ待ちキ
ュー番号408は、共有データ待ちカウンタ付き優先度キ
ュー206のエントリを示し、オーナ計算機404が自計算機
である時だけ有効である。

【００３２】共有データ待ちカウンタ付き優先度キュー
206は要求待ちカウンタ407と要求待ちリスト410から構
成される。要求待ちカウンタ407は、一貫性保証指定手
段303によって指定される要求待ち数との加算処理によ
って変更され、このカウンタを用いて、要求待ちリスト
410の制御を行う。要求待ちリスト410は、要求待ち計算
機411と要求待ち優先度412の各エントリを保持してお
り、自計算機がオーナとなっている共有データに対し
て、他計算機からの一貫性保証指定命令320による要求
を格納する優先度キューである。本実施例における要求
待ちリスト410の優先度は値が大きいほうが優先度が高
くなっている。なお共有データ待ちカウンタ付き優先度
キュー206を使用した実施例の詳細な説明は第11図、第1
2図を用いて後述する。

【００３３】図5は、本発明におけるネットワーク102を
介してネットワークインタフェース107で送受信される
ネットワークパケット501の一実施例である。

【００３４】ネットワークパケット501はパケットヘッ
ダ502とデータ503から構成される。一貫性保証パケット
ヘッダ501は、送付先計算機504、送付元計算機505、共
有データ番号506、共有データ管理コマンド507、共有デ
ータ管理情報508から構成される。送付元計算機505か
ら、共有データ番号506に対応する共有データ320の一貫
性を制御するために、送付先計算機504に対する共有デ
ータ管理コマンド507、及び共有データ管理情報508を送
信する。

【００３５】図6は、図5のパケットヘッダ502中の共有
データ管理コマンド507と共有データ管理情報508をより
詳細に説明する図である。

【００３６】本実施例の共有データ管理コマンド507に
は、一貫性保証予約コマンド「ACQUIRE」601、一貫性保
証許可コマンド「ACQUIRE_ACK」602の2つがある。各共
有データ管理コマンド507に対応して、共有データ管理
情報508がその後ろに続く。

【００３７】一貫性保証予約コマンド「ACQUIRE」601に
は待ちカウンタ設定数611と要求待ち優先度612、一貫性
保証許可コマンド「ACQUIRE_ACK」602には変更オーナ計
算機621と要求待ち計算機リスト622がそれぞれ対応す
る。共有データ管理コマンド507が一貫性保証予約コマ
ンド「ACQUIRE」601の時にはデータ503は空である。

【００３８】一貫性保証許可コマンド「ACQUIRE_ACK」6
02では、オーナ計算機が保持している最新データがデー
タ503に詰め込まれる。

【００３９】以上の共有データ管理コマンドはすべて全
部の計算機に対してブロードキャストする。このブロー
ドキャストは、各計算機から送信したブロードキャスト
の到着順序がすべての計算機で同じになるものが前提で
ある。ブロードキャストをするためには、たとえば、パ
ケットヘッダの送付先計算機504の値を「−１」とし、
ネットワークインタフェース107では、送付先計算機
「−１」にパケットを送信する時にブロードキャストす
ることを予め決めておけば良い。

【００４０】図7は、本発明の一実施例において、複数
の計算機101で一貫性保証制御命令が発行された時の動
作を示すタイミングチャートである。

【００４１】区間701、703、705では、それぞれ共有デ
ータ番号「２」の共有データを所有しているオーナ計算
機であることを示しており、区間702、704は一貫性保証
指定命令304(1)を発行したプログラムが中断している区
間を示す。計算機101(i)の共有データ一貫性保証制御命
令列メモリ204中の命令は、プロセッサ一貫性保証指定
命令304(1)が指定されると、一貫性保証予約コマンド
「ACQUIRE」601(1)を全計算機にブロードキャストす
る。その時点でオーナとなっている計算機101(j)はすで
に一貫性保証解除命令305を発行しているものとする。
計算機101(j)は一貫性保証予約コマンド「ACQUIRE」601
(1)を受け取ると、一貫性保証許可コマンド「ACQUIRE_A
CK」602(1)を全計算機にブロードキャストする。一貫性
保証許可コマンド「ACQUIRE_ACK」602(1)を受け取るま
で、計算機101(i)のプログラムは中断する。計算機101
(i)が一貫性保証許可コマンド「ACQUIRE_ACK」602(1)を
受けると、オーナ計算機が計算機101(j)から計算機101
(i)に変わる。計算機101(k)などの他の計算機が、一貫
性保証許可コマンド「ACQUIRE_ACK」602(1)を受け取る
と、オーナ計算機が計算機101(j)から計算機101(i)に変
更したことを共有データ管理テーブルに反映させる。計
算機101(i)で一貫性保証解除命令305(1)が実行されない
うちに、計算機101(k)から一貫性保証指定命令304(2)で
発行される一貫性保証予約コマンド「ACQIRE」601(2)が
オーナ計算機である計算機101(i)に到達しても、一貫性
保証解除命令305(1)が実行されるまで、一貫性保証許可
コマンド「ACQUIRE_ACK」602(2)は送信されない。計算
機101(k)が一貫性保証許可コマンド「ACQUIRE_ACK」602
(2)を待つことにより、一貫性保証のための同期を実現
することができる。

【００４２】図8はネットワークインタフェース107から
ネットワークパケット501を受けとった時の共有データ
一貫性保証制御命令列メモリ204に格納されている命令
列を示すPAD図である。

【００４３】まず、ステップ801のパケットヘッダ解析
処理によって、ネットワークパケット501を各送付先計
算機504、送付元計算機505、共有データ番号506、共有
データ管理コマンド507、共有データ管理情報508、及び
データ503に分解する。次にステップ802では、共有デー
タ管理コマンド507の内容を調べ、一貫性保証許可コマ
ンド「ACQUIRE_ACK」か一貫性保証予約コマンド「ACQUI
RE」のどちらかであるかを検査する。もし、一貫性保証
許可コマンド「ACQUIRE_ACK」コマンドであれば、ステ
ップ803に進む。ステップ803では受信パケット中の変更
オーナ計算機621が自計算機かどうか検査し、もしそう
であれば、ステップ804に示すように使用中フラグ406を
「１」とし、オーナ計算機404を自計算機とする。も
し、受信パケット中の変更オーナ計算機621が自計算機
でなけれは゛、共有管理テーブル205中のオーナ計算機40
4を変更オーナ計算機621とする。

【００４４】ステップ802で共有データ管理コマンド507
が一貫性保証予約コマンド「ACQUIRE」601であれば、ス
テップ3に示すように、共有管理テーブル205のオーナ計
算機404と自計算機を調べ、オーナ計算機であれば、ス
テップ807の「ACQUIRE」受信処理を行う。

【００４５】図9は、「ACQUIRE」受信処理807を詳細に
説明するPAD図である。

【００４６】まず、ステップ901では、受信パケット中
で指定された共有データ番号506で指定された共有デー
タ待ちカウンタ付き優先度キュー206中の要求待ちカウ
ンタ407の値と受信パケット中の待ちカウンタ設定数902
に加えた値を新しい要求待ちカウンタ407の値とする。

【００４７】次に、ステップ902では、共有データ管理
テーブル205中の使用中フラグ406が「１」でかつ要求待
ちカウンタ407が「０」であるかどうか検査する。も
し、使用中フラグ406が「１」か要求待ちカウンタが
「０」でなければ、ステップ903にあるように受信パケ
ット中の要求待ち優先度612に従い、共有データ管理テ
ーブル205の要求待ち優先度キュー206に加える。使用中
フラグ406が「１」かつ要求待ちカウンタ407が「０」で
あれば、ステップ904にあるように、共有データ待ちキ
ュー番号408から共有データ待ちカウンタ付き優先度キ
ューを参照し、もし、待ちがあればステップ905で受信
パケット中の要求待ち優先度612に従い、共有データ管
理テーブル205の要求待ち優先度キュー206に加え、ステ
ップ906で共有データ待ちキュー番号の先頭を取り出
し、次のオーナ計算機とする。ステップ904において待
ちがなければ、受信パケットの送付元計算機505を次の
オーナ計算機とする。ステップ905とステップ906の処理
によって、先に到着した一貫性保証予約コマンド「ACQU
IRE」を優先的に受け付けることが可能となる。

【００４８】ステップ903において複数計算機からの要
求を優先度によって順序づけることが可能となる。も
し、順序づけせずに要求を出した順番に処理を行いたけ
れば、複数計算機からの優先度をすべて等しくしておけ
ば良い。

【００４９】図10は、ステップ908における「ACQUIRE_A
CK」送信処理の詳細を示したPAD図である。

【００５０】「ACQUIRE_ACK」送信処理においては、ま
ず、ステップ1001で共有データ管理テーブル205のオー
ナ計算機の欄404を次のオーナ計算機として設定する。
次にステップ1002で、共有データ管理テーブル205のオ
ーナ計算機404をパケットヘッダの送付先計算機504、自
計算機をパケットヘッダの送付元計算機505、共有デー
タ番号401をパケットヘッダの共有データ番号506、「AC
QUIRE_ACK」コマンド602を共有データ管理コマンド50
7、共有データ番号506に対応する共有データ待ちカウン
タ付きキュー206の要求待ち計算機リスト206をパケット
ヘッダの要求待ち計算機リスト622にそれぞれコピーす
る。次にステップ1003でパケットのデータ部に共有デー
タ管理テーブル205の開始アドレス402からデータサイズ
分のデータをコピーする。最後にステップ1004ではネッ
トワークパケットをネットワークインタフェース107に
転送して、送付先計算機504に送ることを指示する。

【００５１】図11は、本発明の一実施例において、一貫
性保証指定命令302における要求待ち設定数を指定した
場合の動作を示すタイミングチャートである。

【００５２】区間1101、1102、1105、1106では、それぞ
れ共有データ番号「２」の共有データを所有しているオ
ーナ計算機であることを示しており、区間1103、1105は
一貫性保証指定命令304を発行したプログラムが中断し
ている区間を示す。なお区間1101では、すでに一貫性保
証解除命令が発行された後であるとする。計算機101(i)
における一貫性保証指定命令304(1)では共有データ番号
「２」に対して、要求待ち数「１」を加え、この要求が
優先度「０」となるように指定する。計算機101(i)では
一貫性保証予約コマンド「ACQUIRE」601(1)をブロード
キャストし、オーナ計算機である計算機101(j)に要求を
伝える。

【００５３】計算機101(j)の共有データ番号「２」に対
応する共有データ待ちカウンタ付きキュー206の要求待
ちカウンタ407は、この時0となっており、一貫性保証指
定命令304(1)で指定した要求待ち設定数「１」が加えら
れ、要求待ちカウンタ407の値は「１」となる。要求待
ちカウンタ407が「０」以外の時は、一貫性許可コマン
ド「ACQUIRE_ACK」が返されない。ここで、計算機101
(k)から次の一貫性保証指定命令304(2)により、一貫性
保証予約コマンド「ACQUIRE」601(2)がブロードキャス
トされる。この時、要求待ち設定数は「−１」で、優先
度は「１」と指定される。ここで、計算機(j)の共有デ
ータ番号「２」に対応する共有データ待ちカウンタ付き
キュー206の要求待ちカウンタ407の値に「−１」が加え
られ、要求待ちカウンタ407は「０」となる。また、先
の一貫性保証予約コマンド601(1)で要求待ち優先度キュ
ー206には計算機(i)からの優先度「０」の要求が格納さ
れており、優先度「１」の計算機101(k)からの要求と比
較して、優先度の高い計算機101(k)をオーナ計算機とし
て一貫性保証許可コマンド「ACQUIRE_ACK」603(1)がブ
ロードキャストされ、共有データ番号「２」のオーナ計
算機は計算機101(k)となる。計算機101(i)からの要求
は、オーナ計算機(k)に一貫性保証許可コマンド「ACQUI
RE_ACK」603(1)の共有データ管理情報として一緒に送信
される。計算機101(i)の要求は一貫性保証解除命令305
(1)が計算機101(k)で実行されるまで遅延される。

【００５４】このように、一貫性保証指定命令304にお
いて、要求待ち設定数と優先度を併せて指定することに
よって、一貫性保証のために必要な同期のみならず、並
列プログラムの全体を制御する同期も実現することが可
能となる。

【００５５】図12は、図11で示した一貫性保証指定命令
302で要求待ち設定数を指定した場合の計算機101(i)に
おける共有データ番号「２」に対応する共有データ待ち
カウンタ付きキュー206のの様子を示した図である。

【００５６】1201、1202、1203は計算機101(j)における
ある時刻での共有データ待ちカウンタ付き優先度キュー
206の様子を示している。1201は図11における区間110
1、1202は図11における区間1102、1203は図11において
区間1202の直後に一貫性保証許可コマンド「ACQUIRE_AC
K」602(1)を送信する直前の様子を示している。ネット
ワークパケットの送信元計算機のフィールド504(1),504
(2)には、それぞれ計算機101(i),101(k) から発行され
たコマンドであることを意味する「i]、「k」を示して
いる。1201,1202,1203での要求待ちカウンタ407(1),407
(2),407(3)は一貫性保証予約コマンド601(1),601(2)の
待ちカウンタ設定数611(1),611(2)によって加算され
る。1203に見るように、後に到着した計算機101(k)から
の要求の優先度612(2)が先に到着していた計算機101(i)
の要求の優先度612(1)よりも高いため、要求待ちリスト
410(3)の先頭は入れ替わる。次に、要求待ちカウンタ40
7(3)を検査すると「０」となっているため、要求待ちリ
スト410(3)の先頭である計算機101(k)からの要求が先に
実行される。

【００５７】図13は、一貫性保証指定命令304を一貫性
保証予約命令1301と一貫性保証許可待ち命令1302に分離
する実施例の動作を示す図である。

【００５８】計算機101(i)がオブジェクト番号「２」の
共有データを所有するオーナ計算機である時、計算機10
1(k)において、一貫性保証予約命令1301を実行すると、
一貫性保証予約コマンド「ACQUIRE」602が計算機(i)に
送信される。一貫性保証指定命令304を実行した時に
は、計算機(i)から一貫性保証許可コマンド602を受け取
るまで計算機(k)の上のプログラムは待たされる。しか
し、一貫性保証指定命令304を一貫性保証予約命令1301
と一貫性保証許可待ち命令1302に分割することによっ
て、一貫性保証予約命令と1301と一貫性保証許可待ち命
令1302の間に共有データをアクセスしない計算を別に行
うことができる。これらの命令1301、1302は共有データ
管理テーブル205、共有データ待ちカウンタ付き優先度
キュー206の構成、及び共有データ一貫性保証制御命令
メモリ204を変更することなく実現することができる。

【００５９】以上に述べた実施例では、一貫性保証指定
命令において、要求待ちカウンタ407と要求待ち優先度4
12を指定することによって、並列プログラムの処理の流
れを制御する同期を実現している。本発明は、一貫性保
証指定命令における指定を別の方法にしても実現でき
る。図14から図29によって他の実施例について説明を行
う。

【００６０】図14は、本実施例のメインメモリ106を示
すブロック図である。

【００６１】メインメモリ106は、共有データ一貫性保
証制御指定命令列メモリ201、作業用メモリ202、共有デ
ータメモリ203、共有データ一貫性保証制御命令列メモ
リ204、共有データ管理テーブル205、カウンタ付き共有
データ待ち要求キュー1401、グループ管理テーブル1402
から構成される。図２と比較すると、共有データ待ちカ
ウンタ付き優先度キュー206がカウンタ付き共有データ
待ち要求キュー1401に置き変わり、グループ管理テーブ
ル1402が新たに付け加えられた。

【００６２】カウンタ付き共有データ待ち要求キュー14
01は、共有データ待ち優先度キュー205と同様に、他の
計算機101からの共有データに対する一貫性保証の要求
を保持しておくバッファである。しかし、保持する内容
が異なるため、詳細は図16にて後述する。

【００６３】共有データ一貫性保証制御指定命令列メモ
リ201中の命令列がプロセッサ104に読み込まれて実行さ
れている時、処理を行っている実体を概念的にプロセス
とよぶ。本実施例では、一つの計算機内に複数のプロセ
スが存在することも可能である。また、データを共有し
て保持し、一つのまとまった処理を協調して動作する複
数のプロセスをグループとよぶ。グループ管理テーブル
1402によってグループに属するプロセスの管理を行う。

【００６４】図15は本実施例において、メインメモリ10
6に格納する共有データ一貫性保証制御指定命令列メモ
リ201をより詳細に説明する図である。

【００６５】命令列1500は、共有データ一貫性保証制御
指定命令列メモリ201に格納されている一貫性保証制御
命令を含む命令列を言語Cで記述した例である。命令列3
01は、グループに参加することを宣言するグループ参加
命令1501、共有データの生成を行なう命令302、一貫性
保証を指定する命令1502、共有データに対して更新を行
う命令304、一貫性保証を解除する命令305、機能を拡張
したバリア同期であるアクセス番号カウンタリセットバ
リア同期命令1503から構成されている。

【００６６】グループに参加することを宣言する命令15
01、一貫性保証を指定する命令1502、アクセス番号カウ
ンタリセットバリア同期命令1503以外の命令の説明は、
図３に述べた通りである。

【００６７】命令1501は、グループ番号「１」で示され
るグループに参加することを宣言する命令である。本実
施例では、共有データの生成を行なう命令302の前に実
行することを前提とし、一つのプロセスが参加できるグ
ループは一つだけであるとする。

【００６８】命令1502は、共有データ生成命令302で生
成した共有データ320の一貫性保証を指定する一貫性保
証指定命令である。この命令1502では、一貫性保証の対
象とする共有データを指定するための共有データ番号、
共有データに対してアクセスする順序を指定するアクセ
ス番号を指定する。共有データに対してアクセスする順
序は、一貫性保証指定命令1502の引き数として通し番号
を指定することによって制御できる。

【００６９】しかし、アクセス番号をプログラム全体で
通して指定すると、プログラマの負担が大きくなる。こ
の問題を解決するために、プログラムのまとまった処理
毎に独立して通し番号を指定できるようにするための命
令1503を設けている。

【００７０】命令1503によって、グループ番号「１」で
示されるグループに属するプロセス全体でバリア同期を
とることを指定している。本実施例のシステムでは、命
令1502で指定したアクセス番号通りに順序制御するため
に、命令1502を発行して、アクセスが許可された数をカ
ウントするアクセス番号カウンタを持っている。アクセ
ス番号カウンタリセットバリア同期命令1503は、このア
クセス番号カウンタを０にする機能があるため、命令15
03を発行した後から、再びアクセス番号を１から指定し
始めることが可能である。

【００７１】図16は、共有データ管理テーブル205、カ
ウンタ付き共有データ待ち要求キュー1401の一実施例で
ある。

【００７２】共有データ管理テーブル205が図４と異な
るのは、各共有データ毎にグループ番号1601が加えられ
た点と、共有データ待ちキュー番号408が、カウンタ付
き共有データ待ち要求キュー番号1602となった点であ
る。共有データ毎に設けられたグループ番号欄1601に
は、各共有データを使用するプロセスが属するグループ
のグループ番号が記入されている。カウンタ付き共有デ
ータ待ち要求キュー番号1602は、複数個存在するカウン
タ付き共有データ待ち要求キュー1401の一つを指し示
す。

【００７３】各カウンタ付き共有データ待ち要求キュー
1401はアクセス番号カウンタ1603と、共有データ待ち要
求リスト1604から構成される。共有データ待ち要求リス
ト1604は待ち計算機1605、及びアクセス番号1606の組を
エントリとして一貫性保証の要求を保持するキューであ
る。自計算機がオーナとなっている共有データに対し
て、他計算機から発行される一貫性保証指定命令1502に
よる要求を格納する。アクセス番号カウンタ1603は、ア
クセスを許可した要求の数をカウントし、一貫性保証指
定命令1502で指定されるアクセス番号通りに実行順序を
制御するために用いられる。なおカウンタ付き共有デー
タ待ち要求キュー206を使用した実施例の詳細な説明は
後述する。

【００７４】図17は、グループ管理テーブル1402の一実
施例である。グループ管理テーブル1402はグループ毎
に、グループ番号1701、グループ参加予約プロセス数17
02、グループ参加プロセス数1703、グループ参加プロセ
ス番号1704、バリアカウンタ1705を持つ。

【００７５】プロセスは共有データの初期化を行う前
に、グループに参加する。グループ参加命令1501によっ
て参加するグループを指定すると、共有データ一貫性制
御命令列メモリ201内の命令列が起動され、グループ管
理テーブル1402に必要項目が記入される。グループ参加
予約プロセス数1702には、グループ参加命令1501で指定
されるグループ参加プロセス数が設定される。グループ
参加プロセス番号1704には、グループ参加命令1501を発
行したプロセスをシステム内で一意に特定できるよう
に、そのプロセスの存在する計算機の識別子と、計算機
内のプロセスの識別子の組合せ「（計算機番号、計算機
内プロセス番号）」で登録される。計算機番号にはIPア
ドレス、計算機内プロセス番号にはUNIXのプロセスIDを
用いる方法などが考えられる。グループ参加プロセス番
号1704に登録されたプロセスの数がグループ参加プロセ
ス数1703に記入される。グループ参加命令1501を発行し
たプロセスの数がグループ参加予約プロセス数1702の値
に達した時点で、共有データを用いる並列処理が開始さ
れる。バリアカウンタ1705は、グループに属しているプ
ロセスがアクセス番号カウンタリセットバリア同期命令
1503を発行した数をカウントするために用いる。

【００７６】グループ参加命令1501の内容は、全計算機
にブロードキャストされ、各計算機で同じように項目が
記入されるため、グループ管理テーブル1402の内容は全
ての計算機で同一になる。グループ参加命令1501を発行
した時の処理の詳細は図28、29において説明する。

【００７７】図18は、図5のパケットヘッダ502中の共有
データ管理コマンド507と共有データ管理情報508をより
詳細に説明する図である。

【００７８】本実施例の共有データ管理コマンド507に
は、一貫性保証予約コマンド「ACQUIRE」1801、一貫性
保証許可コマンド「ACQUIRE_ACK」1802、アクセス番号
カウンタリセットバリア同期コマンド「BARRIER」180
3、グループ参加コマンド「JOIN_GROUP」1804の4つがあ
る。一貫性保証予約コマンド「ACQUIRE」1801にはアク
セス番号1811、一貫性保証許可コマンド「ACQUIRE_AC
K」1802には次オーナ計算機1821とカウンタ付き共有デ
ータ待ち要求キュー1822、アクセス番号カウンタリセッ
トバリア同期コマンド「BARRIER」1803にはグループ番
号1831、グループ参加コマンド「JOIN_GROUP」1804には
グループ番号1841、グループ参加プロセス数1842、グル
ープ参加プロセス番号1843がそれぞれ共有データ管理情
報508として格納される。

【００７９】共有データ管理コマンド507が一貫性保証
許可コマンド「ACQUIRE_ACK」1802の場合だけ、データ
欄503にはオーナ計算機が保持している最新データが格
納される。

【００８０】一貫性保証許可コマンド「ACQUIRE_ACK」1
802と、アクセス番号カウンタリセットバリア同期コマ
ンド「BARRIER」1803は、グループに属するプロセスが
存在する計算機にマルチキャストされる。ただし、自計
算機は除く。この場合、パケットヘッダ502の送付先計
算機504には、マルチキャストする宛先の計算機番号を
全て記入する。マルチキャストする宛先計算機を特定す
るために次の処理を行う。まず、共有データ管理テーブ
ル205を参照して、対象とする共有データを使用するグ
ループのグループ番号1601を得る。次に、グループ管理
テーブル1402を参照して、グループ番号に対応するグル
ープ参加プロセス番号1707を得る。グループ参加プロセ
ス番号は、「（計算機番号、計算機内プロセス番号）」
の組で表されているため、この計算機番号で示される計
算機を宛先とする。

【００８１】グループ参加コマンド「JOIN_GROUP」1804
は、全計算機に対してブロードキャストする。

【００８２】これらのマルチキャスト、ブロードキャス
トは、各計算機から送信したパケットの到着順序がすべ
ての計算機で同じになることを前提とする。

【００８３】図19は、複数の計算機101上のプロセスが
一貫性保証指定命令1502を発行した場合の動作を示すタ
イミングチャートである。

【００８４】区間1901、1904、1905は、共有データ番号
「２」の共有データを所有しているオーナ計算機である
期間を示している。区間1902、1903は、それぞれ一貫性
保証指定命令1502(1)、1502(2)を発行したプロセスが中
断している区間を示す。

【００８５】区間1901において、共有データ番号「２」
に対応するアクセス番号カウンタ1603(1)は、「２」と
なっているとする。

【００８６】共有データ番号「２」、アクセス番号
「４」を指定して計算機101(i)上のプロセスが一貫性保
証指定命令1502(1)を発行した時、一貫性保証制御命令
列メモリ204中の命令列が起動され、以下の処理が行わ
れる。

【００８７】共有データ管理テーブル205を参照して、
オーナ計算機404が計算機101(j)であるという情報を得
る。次に、パケットヘッダ502に必要な情報を記入す
る。具体的には、計算機101(j)の識別子を送付先計算機
欄504に、自計算機の識別子を送付元計算機欄505に、共
有データ番号「２」を共有データ番号欄506に、一貫性
保証予約コマンド「ACQUIRE」1801(1)を共有データ管理
コマンド欄507に、アクセス番号「４」をアクセス番号
欄1811にそれぞれ記入する。そして、ネットワークイン
タフェース107にパケットを転送することによって、オ
ーナ計算機である計算機101(j)に一貫性保証予約コマン
ド「ACQUIRE」1801(1)を送信する。

【００８８】先に計算機101(i)から計算機101(j)に送信
した一貫性保証予約コマンド「ACQUIRE」1801(1)の内容
は、共有データ待ち要求リスト1604に入れられ、一貫性
保証許可コマンド「ACQUIRE_ACK」1802(1)の共有データ
待ち要求リスト欄1822に格納されてオーナ計算機101(k)
に送信される。また、「ACQUIRE_ACK」1802(1)を送信す
る前にアクセス番号カウンタ1603(1)に１が加算され、
区間1904ではアクセス番号カウンタ1603(2)の値は
「３」となる。計算機101(i)の要求は一貫性保証解除命
令305(1)が計算機101(k)で実行されるまで遅延される。

【００８９】このように、一貫性保証指定命令1502で、
アクセス番号を指定することによって、一貫性保証のた
めに必要な相互排除のみならず、並列プログラムの全体
の流れを制御する同期も実現することが可能となる。

【００９０】図20は、一貫性保証指定命令1502におい
て、例外的にアクセス順序を変える指定を行った場合の
タイムチャートを示している。

【００９１】本実施例では、アクセス番号にあらかじめ
決められた特定の数値を設定した場合には、例外的に順
序を変えることを可能とした。ここでは、アクセス番号
に「−１」を設定した場合に、優先的にアクセス可能と
した。

【００９２】以下、共有データ番号「２」の共有データ
を対象とする。区間2001においてアクセス番号カウンタ
1603(1)が１であるとする。計算機101(k)上のプロセス
から発行された一貫性保証指定命令1502(1)では、共有
データ番号「２」の共有データに対して、アクセス番号
「２」で示すように２番目にアクセスすることを指定し
ている。通常であれば、計算機101(j)上のプロセスが一
貫性保証解除命令305(1)を発行した時に、計算機101(k)
に対して一貫性保証許可コマンド「ACQUIRE_ACK」1802
が送信される。しかし、計算機101(i)から発行した一貫
性保証指定命令1502(2)で、共有データ番号「２」、ア
クセス番号「−１」と指定した場合、計算機101(i)に対
して一貫性保証許可コマンド「ACQUIRE_ACK」1802(1)が
送信される。この時、区間2003のアクセス番号カウンタ
1603(2)の値は区間2001の時から変化しない。その後、
一貫性保証解除命令305(2)が発行されてから計算機101
(k)に一貫性保証許可コマンド「ACQUIRE_ACK」1802(2)
が送信され、アクセス番号カウンタ1603(3)の値は
「２」となる。

【００９３】アクセス番号を「−１」と設定した一貫性
保証指定命令1502が重なった場合には、一貫性保証予約
コマンド「ACQUIRE」1801が先にオーナ計算機に到達し
た方を優先する。

【００９４】この機能は、必ずしも順序通りにアクセス
しなくてもよい場合や、優先的にアクセスしたい場合に
用いることができる。

【００９５】図21は、アクセス番号カウンタリセットバ
リア同期命令1503が実行された時の動作を示すタイミン
グチャートである。

【００９６】計算機101(k)上のプロセスが共有データ番
号「２」、アクセス番号「８」として一貫性保証指定命
令1502(1)を発行した後の状態である区間2103で、アク
セス番号カウンタ1603(2)は「８」となっている。アク
セス番号カウンタリセットバリア同期命令1503は、バリ
ア同期をとると同時に、アクセス番号カウンタを「０」
にリセットすることによってアクセス番号を再び１から
指定できるようにするための命令である。

【００９７】計算機101(j)上のプロセスがアクセス番号
カウンタリセットバリア同期命令1503を発行すると、共
有データ一貫性保証制御命令列メモリ204中の命令列が
起動され、グループ管理テーブル1402を参照して、対応
するグループのバリアカウンタ1705に１加算する。ま
た、アクセス番号カウンタリセットバリア同期コマンド
「BARRIER」1803を、グループ参加プロセスの存在する
計算機にマルチキャストする。アクセス番号カウンタリ
セットバリア同期コマンド「BARRIER」1803が到着した
計算機101(i),(k)では、グループ管理テーブル1402を参
照して、対応するグループのバリアカウンタ1705に１加
算する。

【００９８】また、計算機101(i),(k)上のプロセスがそ
れぞれアクセス番号カウンタリセットバリア同期命令15
03(2)、1503(3)を発行した場合も、同様の処理が行われ
る。アクセス番号カウンタリセットバリア同期命令1503
を出したプロセスは、グループ内の全プロセスからバリ
アが出るまで、区間2105、2106に示すように処理が中断
される。

【００９９】各計算機101上のプロセスがアクセス番号
カウンタリセットバリア同期命令1503を実行し、バリア
カウンタ1705の値がグループ参加プロセス数1703に等し
くなった時点で、アクセス番号カウンタ1603(3)の値を
０にし、プロセスの処理を続行する。処理の続行後、一
貫性保証指定命令1502(2)では、アクセス番号を１から
指定できる。

【０１００】このようにすることによって、モジュール
毎に分割して通し番号を付けるプログラムを記述できる
ため、プログラマの負担を軽減する効果がある。

【０１０１】図22はネットワークインタフェース107か
らネットワークパケット501を受けとった時に起動され
る共有データ一貫性保証制御命令列メモリ204に格納さ
れている命令列の処理を示すPAD図である。

【０１０２】まず、ステップ2201のパケットヘッダ解析
処理によって、ネットワークパケット501を各送付先計
算機504、送付元計算機505、共有データ番号506、共有
データ管理コマンド507、共有データ管理情報508、及び
データ503に分解する。次にステップ2202では、共有デ
ータ管理コマンド507の内容を調べ、一貫性保証予約コ
マンド「ACQUIRE」1801か、一貫性保証許可コマンド「A
CQUIRE_ACK」1802か、アクセス番号カウンタリセットバ
リア同期コマンド「BARRIER」1803か、グループ参加コ
マンド「JOIN_GROUP」1804のどれであるかを検査する。

【０１０３】共有データ管理コマンド507が一貫性保証
予約コマンド「ACQUIRE」1801であれば、ステップ2203
に進む。ステップ2203では、共有データ管理テーブル20
5に記入しているオーナ計算機404が自計算機かどうか検
査し、そうであれば、ステップ2204に示すようにACQUIR
E受信処理を実行する。他の計算機が一貫性保証予約コ
マンド「ACQUIRE」1801を送信した後でオーナ計算機が
変わった場合には、オーナでない計算機に一貫性保証予
約コマンド「ACQUIRE」1801が到着することがある。こ
の場合ステップ2205に進み、到着したパケットを新たに
オーナ計算機となった計算機に転送する。具体的には、
到着したパケットのヘッダ502の送付先計算機欄505に、
共有データ管理テーブル205中のオーナ計算機404の番号
を記入して送信する。

【０１０４】共有データ管理コマンド507が一貫性保証
許可コマンド「ACQUIRE_ACK」1802であれば、ステップ2
206に進む。ステップ2206では受信パケット中の次オー
ナ計算機1821が自計算機かどうか検査する。もし自計算
機が次オーナ計算機1821である場合には一貫性保証区間
に入ることを許可されたことになる。そこで、ステップ
2207において、共有データ管理テーブル205中の該当す
る共有データ番号401の使用中フラグ406を１にする。次
にステップ2208では、共有データ管理テーブル205のオ
ーナ計算機欄404に自計算機の番号を記入する。

【０１０５】自計算機が次オーナ計算機1821でない場合
には、ステップ2209に進む。ステップ2209では、共有デ
ータ管理テーブル205のオーナ計算機欄404に次オーナ計
算機1821の番号を記入する。これによって、自計算機か
ら一貫性保証予約コマンド「ACQUIRE」1801を送信する
場合の、送付先となるオーナ計算機を知ることができ
る。

【０１０６】共有データ管理コマンド507がアクセス番
号カウンタリセットバリア同期コマンド「BARRIER」180
3であった場合、ステップ2210に進み、グループ番号183
1に対応するグループ管理テーブル1402中のバリアカウ
ンタ1705に１加算する。次にステップ2211では、バリア
カウンタ1705の値がグループ参加プロセス数1703と一致
するか否かを検査し、一致した場合は、ステップ2212の
バリア成立処理を実行する。バリア成立処理の詳細は図
26において述べる。

【０１０７】共有データ管理コマンド507がグループ参
加コマンド「JOIN_GROUP」1804であった場合、ステップ
2213のグループ参加処理を実行する。グループ参加処理
の詳細は図29において述べる。

【０１０８】図23は、「ACQUIRE」受信処理2204を詳細
に説明するPAD図である。

【０１０９】受信したパケットのヘッダ502に記入され
ている共有データ番号506に対応する共有データを対象
として以下の処理を行う。また、対象とする共有データ
に対応する共有データ待ち要求リスト1604は、共有デー
タ管理テーブル205中のカウンタ付き共有データ待ち要
求キュー番号1602から特定される。

【０１１０】まず、ステップ2301では、受信パケット中
で指定したアクセス番号1811の値が「−１」であるか否
かを検査し、「−１」であるならステップ2302に進む。

【０１１１】ステップ2302では、対象とする共有データ
に対応する共有データ待ち要求リスト1604の先頭の要求
のアクセス番号1606が「−１」である場合は、ステップ
2321に進む。

【０１１２】ステップ2321では、アクセス番号1606「−
１」の要求が共有データ待ち要求リスト1604の先頭から
複数続いている場合、アクセス番号1606「−１」の要求
の最後尾に、受信したパケットの要求を追加する。要求
の追加は、受信したパケットのヘッダ502の送付元計算
機505を待ち計算機欄1605に、アクセス番号1811をアク
セス番号欄1606に記入することによって行う。

【０１１３】対象とする共有データに対応する共有デー
タ待ち要求リスト1604の先頭の要求のアクセス番号1606
が「−１」でない場合は、ステップ2322に進み、共有デ
ータ待ち要求リスト1604の先頭に、受信したパケットの
要求を追加する。

【０１１４】アクセス番号1811に「−１」を指定した一
貫性保証指定コマンド「ACQUIRE」1801が発行された場
合は、ステップ2302、2321、2322によって、オーナ計算
機に早く届いた順にアクセスが許可されるように処理さ
れる。

【０１１５】受信パケット中で指定されたアクセス番号
1811の値が「−１」でない場合はステップ2303に進む。
処理対象の共有データに対応するアクセス番号カウンタ
1603の値が、受信パケット中で指定されたアクセス番号
1811の値よりも大きい場合、ステップ2304に進み、エラ
ーとしてプロセスを中止する。そうでない場合、ステッ
プ2305に進み、共有データ待ち要求リストの中でアクセ
ス番号1606が昇順になるように要求を追加する。

【０１１６】次にステップ2306では、共有データ管理テ
ーブル205において、処理対象の共有データに対応する
使用中フラグ406が「０」であるか否か検査する。も
し、使用中フラグ406が「０」ならば、ステップ2307に
進む。ステップ2307では、処理対象の共有データに対応
する共有データ待ち要求リスト1604の先頭の要求のアク
セス番号1606が「−１」であるか否かを検査する。もし
「−１」である場合、ただちにステップ2309の一貫性保
証許可コマンド「ACQUIRE_ACK」1802送信処理を行う。
この処理の詳細は図24を用いて後述する。

【０１１７】先頭の要求のアクセス番号1606が「−１」
でない場合、ステップ2310に進み、先頭の要求のアクセ
ス番号1606がアクセス番号カウンタ1603の値＋１と等し
いか否かを検査する。

【０１１８】両者の値が等しい場合、ステップ2311で、
アクセス番号カウンタ1603に１加算する。ステップ2312
では、ステップ2309と同様に一貫性保証許可コマンド
「ACQUIRE_ACK」1802送信処理を行う。

【０１１９】ステップ2310、2311、2312の処理によっ
て、アクセス番号1606が「−１」以外の場合はアクセス
番号順に共有データへのアクセスを順序付けることがで
きる。

【０１２０】図24は、図23のステップ2309、2312におけ
る「ACQUIRE_ACK」送信処理の詳細を示したPAD図であ
る。

【０１２１】一貫性保証許可コマンド「ACQUIRE_ACK」1
802送信処理においては、まず、ステップ2401で処理対
象とする共有データに対応する共有データ待ち要求リス
ト1604の先頭の要求を取り出す。取り出した要求の待ち
計算機1605を次オーナ計算機とし、共有データ管理テー
ブル205のオーナ計算機欄404にその識別子を記入する。

【０１２２】次にステップ2402で、パケットヘッダの送
付先計算機欄504に、一貫性保証許可コマンド「ACQUIRE
_ACK」1802をマルチキャストする宛先計算機を全て記入
する。

【０１２３】また、共有データ番号401をパケットヘッ
ダの共有データ番号欄506、「ACQUIRE_ACK」コマンド18
02をパケットヘッダの共有データ管理コマンド欄507、
前述の次オーナ計算機の識別子をパケットヘッダの次オ
ーナ計算機欄1821、共有データ番号506に対応するカウ
ンタ付き共有データ待ち要求キュー1401をパケットヘッ
ダ502のカウンタ付き共有データ待ち要求キュー欄1822
にそれぞれ記す。

【０１２４】次にステップ2403で、共有データ管理テー
ブル205に記録された開始アドレス402からサイズ403分
のデータをパケットのデータ部503にコピーする。

【０１２５】最後にステップ2404ではネットワークパケ
ットをネットワークインタフェース107に転送して、マ
ルチキャストすることを指示する。

【０１２６】図25は、アクセス番号カウンタリセットバ
リア同期命令1503が発行された場合に起動される共有デ
ータ一貫性保証制御命令列メモリ204中の命令列の処理
を示すPAD図である。

【０１２７】ステップ2501では、グループ管理テーブル
1402のグループ参加プロセス番号1704を参照して、アク
セス番号カウンタリセットバリア同期命令1503を発行し
たプロセスが属するグループのグループ番号1701を特定
する。

【０１２８】以下、このグループを対象として処理を行
う。

【０１２９】ステップ2502で、グループ番号1701に対応
するバリアカウンタ1705に１加算する。

【０１３０】ステップ2503では、アクセス番号カウンタ
リセットバリア同期コマンド「BARRIER」1803をグルー
プ参加プロセスの存在する計算機にマルチキャストす
る。この際、パケットヘッダ502には、共有データ管理
コマンド欄507にアクセス番号カウンタリセットバリア
同期コマンド「BARRIER」1803を、グループ番号欄1831
に対象としているグループのグループ番号を記入する。

【０１３１】ステップ2504では、バリアカウンタ1705が
グループ参加プロセス数1703に等しいか否かを検査し、
等しいならば、ステップ2505に進み、バリア成立処理を
行う。バリアカウンタ1705がグループ参加プロセス数17
03に等しくないならば、ステップ2506に進み、アクセス
番号カウンタリセットバリア同期命令1503を発行したプ
ロセスの処理を中断する。プロセスの処理を中断する方
法としては、アクセス番号カウンタリセットバリア同期
命令1503を発行したプロセスが、共有データ一貫性保証
制御命令列メモリ204から処理の続行を許可されるまで
サスペンドするようにしていればよい。

【０１３２】図26は、図22におけるステップ2212、図25
におけるステップ2505のバリア成立処理を詳細に説明す
るPAD図である。

【０１３３】ステップ2601では、共有データ管理テーブ
ル205のグループ番号欄1601を参照して、対象としてい
るグループが使用している共有データを抽出する。

【０１３４】ステップ2602は、ステップ2601で抽出した
共有データについてステップ2603、2604の処理を繰り返
すことを表している。ステップ2603、2604で、各共有デ
ータのオーナ計算機404が自計算機であるならば、その
共有データに対応するアクセス番号カウンタ1603を０に
リセットする処理を行う。

【０１３５】バリア成立処理は、全計算機で一斉に実行
されるため、グループで使用している全ての共有データ
のアクセス番号カウンタ1603が０にリセットされる。

【０１３６】プロセスがアクセス番号カウンタリセット
バリア同期命令1503を実行すると、バリアが成立するま
でプロセスの実行は中断される。ステップ2605では中断
したプロセスの処理を続行する許可を出す。

【０１３７】図27は、一貫性保証解除命令305が発行さ
れ、共有データ一貫性保証制御命令列メモリ204中の命
令列が起動された場合の処理を示すPAD図である。

【０１３８】まず、一貫性保証解除命令305の引き数と
して指定された共有データ番号の共有データを処理の対
象とする。ステップ2701で、共有データ管理テーブル20
5において、処理の対象とする共有データに対応する使
用中フラグ406を０にする。

【０１３９】次にステップ2702で、処理の対象とする共
有データの共有データ待ち要求リスト1604に待ち要求が
あるか否かを検査する。もし待ち要求があるならば、ス
テップ2703において図23中のステップ2330と同じ共有デ
ータ待ち要求リストの先頭の要求の処理を行う。

【０１４０】図28は、グループ参加命令1501を発行した
時の動作を示すタイミングチャートである。

【０１４１】グループ参加命令1501は各プロセスで共有
データを使用する前に一回だけ実行する。計算機101(i)
上のプロセスがグループ参加命令1501(1)を発行する
と、共有データ一貫性保証制御命令列メモリ204内の命
令列が起動され、グループ参加コマンド「JOIN_GROUP」
1804(1)が全計算機にブロードキャストされる。この
時、グループ参加命令1501(1)の引き数として指定した
グループ番号、グループ参加プロセス数と、グループ参
加命令1501(1)を発行したプロセスの識別子をパケット
ヘッダ502の共有データ管理情報508に記入する。グルー
プ参加命令1501(1)を発行したプロセスは、共有データ
一貫性保証制御命令列メモリ204から処理の続行を許可
されるまで区間2801で処理を中断する。

【０１４２】計算機101(k), 101(j)上のプロセスからグ
ループ参加命令1501(2)、1501(3)が発行された時、同様
の処理が行われる。グループ参加命令1501を発行したプ
ロセスの数がグループ参加プロセス数に達した時、処理
を中断していたプロセスを続行させる。以後、このグル
ープに属したプロセス間で共有データをアクセスする。

【０１４３】図29は、グループ参加命令1501を発行した
時に、その計算機内の共有データ一貫性保証制御命令列
メモリ204に格納されている命令列が実行する処理のPAD
図である。

【０１４４】自計算機内のプロセスからグループ参加命
令1501が発行された場合には、ステップ2908で、グルー
プ参加コマンド「JOIN_GROUP」1804を全計算機にブロー
ドキャストする。 以後のグループ参加命令基本処理22
13は、他の計算機からグループ参加コマンド1804が到着
した場合も同じである。

【０１４５】ステップ2901では、グループ管理テーブル
1402に、グループ参加命令1501で指定されたグループ番
号の情報を登録する欄が存在するか否かを検査する。も
しグループ番号に対応する登録欄が存在しなければ、ス
テップ2902に進み、グループ管理テーブル1402に対象と
するグループの登録欄を生成する。また、ステップ2903
で、グループ参加命令1501で指定されたグループ参加プ
ロセス数を、グループ管理テーブル1402のグループ参加
予約プロセス数1702の欄に記入する。

【０１４６】ステップ2904では、グループ参加プロセス
番号欄1704に、グループ参加命令1501を発行したプロセ
スのプロセス番号を登録済みであるか否かを検査する。
既に登録済みであるなら、一つのプロセスからグループ
参加命令1501を複数発行したことになるため、ステップ
2905で、エラーとしてプロセスを中止する。まだ登録さ
れていないなら、ステップ2906に進み、グループ参加プ
ロセス番号欄1704にグループ参加命令1501を発行したプ
ロセスのプロセス番号を登録する。ステップ2907では、
グループ参加プロセス数1703に１加算する。

【０１４７】ステップ2909では、グループ参加プロセス
数1703と、グループ参加予約プロセス数1702が等しいか
否かを検査し、等しい場合にはステップ2910に進む。ス
テップ2910では、グループ参加プロセス番号1704を参照
して、自計算機上のプロセスに対して処理の続行許可を
出す。グループ参加プロセス数1703が、グループ参加予
約プロセス数1702に達していない場合、ステップ2911に
進み、グループ参加命令1501を発行したプロセスの処理
を中断する。

【０１４８】

【発明の効果】本発明によれば、複数の計算機をネット
ワークで結合し、各計算機は独立したアドレス空間を持
ち、各計算機内のメモリ上に複数計算機間でデータを共
有するための共有データメモリを持つ疎結合計算機シス
テムにおいて、共有データの一貫性保証のための同期と
並列プログラムを制御するための同期のために必要なネ
ットワークパケットを少なくすることができるので、ネ
ットワーク資源を有効に活用することができる。また、
並列プログラムを制御するための同期をするとともに共
有データの一貫性保証も行うことができるので、並列プ
ログラムを記述するプログラマの負担を軽減することが
できる。その結果、特に、通信時間に比して計算時間が
長く、自動的に負荷の分散が困難であるような並列処理
の問題を効率良く処理することが可能となる。

【図面の簡単な説明】

【図１】本発明の一実施例を示す疎結合計算機システム
のブロック図である。

【図２】本発明の一実施例を示すメインメモリとネット
ワークインタフェースのブロック図である。

【図３】本発明におけるメインメモリの構造の一実施例
を示す図である。

【図４】本発明における共有データ管理テーブルの構造
の一実施例を示す図である。

【図５】本発明における通信パケット構造の一実施例を
示す図である。

【図６】本発明における通信パケット構造の一実施例を
示す図である。

【図７】本発明における共有データ一貫性保証制御命令
列メモリの処理の一実施例を示すタイミングチャートで
ある。

【図８】本発明における共有データ一貫性保証制御命令
列メモリの処理の一実施例を示すPAD図である。

【図９】本発明における共有データ一貫性保証制御命令
列メモリの処理の一実施例を示すPAD図である。

【図１０】本発明における共有データ一貫性保証制御命
令列メモリの処理の一実施例を示すPAD図である。

【図１１】本発明における共有データ一貫性保証制御命
令列メモリの処理の一実施例を示すタイミングチャート
である。

【図１２】本発明における共有データ管理テーブルと要
求待ちカウンタの一実施例を示す図である。

【図１３】本発明における共有データ一貫性保証制御命
令列メモリの処理の一実施例を示すタイミングチャート
である。

【図１４】本発明の他の実施例におけるメインメモリと
ネットワークインタフェースのブロック図である。

【図１５】本発明の他の実施例における共有データ一貫
性保証制御命令列メモリの構造を示す図である。

【図１６】本発明の他の実施例における共有データ管理
テーブルとカウンタ付き共有データ待ち要求キューの構
造を示す図である。

【図１７】本発明の他の実施例におけるグループ管理テ
ーブルの構造を示す図である。

【図１８】本発明の他の実施例における通信パケットの
構造を示す図である。

【図１９】本発明の他の実施例において、一貫性保証指
定命令を発行した時の基本動作を示すタイミングチャー
トである。

【図２０】本発明の他の実施例において、一貫性保証指
定命令で指定するアクセス番号に特定の値を設定した場
合の動作を示すタイミングチャートである。

【図２１】本発明の他の実施例において、アクセス番号
カウンタリセットバリア同期命令を発行した時の基本動
作を示すタイミングチャートである。

【図２２】本発明の他の実施例において、通信パケット
を受信した時の共有データ一貫性保証制御命令列メモリ
の処理を示すPAD図である。

【図２３】本発明の他の実施例において、一貫性保証予
約コマンドを受信した時の共有データ一貫性保証制御命
令列メモリの処理を示すPAD図である。

【図２４】本発明の他の実施例において、一貫性保証許
可コマンドを送信する時の共有データ一貫性保証制御命
令列メモリの処理を示すPAD図である。

【図２５】本発明の他の実施例において、アクセス番号
カウンタリセットバリア同期命令を発行した時の共有デ
ータ一貫性保証制御命令列メモリの処理を示すPAD図で
ある。

【図２６】本発明の他の実施例において、バリア同期が
成立した時の共有データ一貫性保証制御命令列メモリの
処理を示すPAD図である。

【図２７】本発明の他の実施例において、一貫性保証解
除命令を発行した時の共有データ一貫性保証制御命令列
メモリの処理を示すPAD図である。

【図２８】本発明の他の実施例において、グループ参加
命令を発行した時の動作を示すタイミングチャートであ
る。

【図２９】本発明の他の実施例において、グループ参加
命令を発行した時の共有データ一貫性保証制御命令列メ
モリの処理を示すPAD図である。

【符号の説明】

100：疎結合計算機システム、101：計算機、102：ネッ
トワーク、103：システムバス、104：プロセッサ、10
5：補助記憶装置、106：メインメモリ、107：ネットワ
ーク・インタフェ−ス、108：外部ネットワーク、201：
共有データ一貫性保証制御指定命令列メモリ、202：作
業用メモリ、203：共有データメモリ、204：共有データ
一貫性保証制御命令列メモリ、205：共有データ管理テ
ーブル、206：共有データ待ちカウンタ付き優先度キュ
ー、301：共有データ一貫性保証制御命令コマンドを含
む命令列、302：共有データ生成命令、303：共有データ
一貫性保証指定命令、304：共有データを更新する命令
列、305：共有データ一貫性保証解除命令、310：作業用
メモリ内ののデータ、320：共有データ両域内の共有デ
ータ、401〜406,408：共有データ管理テーブルのエント
リ、407：要求待ちカウンタ、410：要求待ち計算機リス
ト、411〜412：要求待ち計算機リストのエントリ、50
1：ネットワークパケット、502：パケットヘッダ、50
3：ネットワークパケット内のデータ、504〜508：パケ
ットヘッダのエントリ、601：一貫性保証予約コマン
ド、602：一貫性保証許可コマンド、611〜612：一貫性
保証予約コマンドのエントリ、621〜622：一貫性保証許
可コマンドのエントリ、701,703,705：共有データ番号
「２」の共有データのオーナとなっている区間、702,70
4：一貫性保証の許可を待つ区間、801〜807、901〜90
8：ネットワークパケットを受信した時の処理ステッ
プ、901〜908：一貫性保証許可コマンドを発行するため
の処理ステップ、1101,1102,1105,1106：共有データ番
号「２」の共有データのオーナ区間、1103,1104：一貫
性保証の許可を待つ区間、1201〜1203：共有データ待ち
カウンタと共有データ待ちカウンタ付き優先度キュー、
1301：一貫性保証予約命令、1302：一貫性保証許可待ち
命令、1401：カウンタ付き共有データ待ち要求キュー、
1402：グループ管理テーブル、1501：グループ参加命
令、1502：一貫性保証指定命令、1503：アクセス番号カ
ウンタリセットバリア同期命令、1601, 1602：他の実施
例で共有データ管理テーブルに新たに加わったエント
リ、1603：アクセス番号待ちカウンタ、1604：共有デー
タ待ち要求リスト、1605, 1606：共有データ待ち要求リ
ストのエントリ、1701〜1705：グループ管理テーブルの
エントリ、1801：他の実施例の一貫性保証予約コマン
ド、1802：他の実施例の一貫性保証許可コマンド、180
3：アクセス番号カウンタリセットバリア同期コマン
ド、1804：グループ参加コマンド、1811：アクセス番
号、1821, 1822：他の実施例の一貫性保証許可コマンド
の管理情報、1831：グループ番号、1841〜1843：グルー
プ参加コマンドの管理情報、1901, 1904, 1905, 2001,
2003, 2005, 2101, 2103, 2108：共有データ番号「２」
の共有データのオーナとなっている区間、1902, 1903,
2002, 2004, 2102, 2107：一貫性保証の許可を待つ区
間、2105, 2106：バリア同期の成立を待つ区間、2201〜
2213：ネットワークパケットを受信した時の処理ステッ
プ、2301〜2330：一貫性保証予約コマンドを受信した時
の処理ステップ、2401〜2404：一貫性保証許可コマンド
を送信する時の処理ステップ、2501〜2506：アクセス番
号カウンタリセットバリア同期命令を発行した時の処理
ステップ、2601〜2605：アクセス番号カウンタリセット
バリア同期が成立した時の処理ステップ、2701, 2702,
2330：一貫性保証解除命令を発行した時の処理ステッ
プ、2801, 2802：グループ参加命令が全部出るまで待つ
区間、2803〜2805：グループに参加し終えて共有データ
に対する処理を実行する区間、2901〜2922：グループ参
加命令を発行した時の処理ステップ。

フロントページの続き (72)発明者 吉沢 聡 東京都国分寺市東恋ケ窪１丁目280番地 株式会社日立製作所中央研究所内 (72)発明者 村山 秀樹 東京都国分寺市東恋ケ窪１丁目280番地 株式会社日立製作所中央研究所内 (72)発明者 山田 公稔 神奈川県横浜市戸塚区戸塚町5030番地 株 式会社日立製作所ソウトウェア開発本部内 (72)発明者 堀本 徹 神奈川県横浜市戸塚区戸塚町5030番地 株 式会社日立製作所ソウトウェア開発本部内

Claims (9)

【特許請求の範囲】
1. 【請求項１】複数の計算機をネットワークで結合し、各
   計算機は独立したアドレス空間を持ち、各計算機のメモ
   リ上に物理的に分散したデータを論理的に共有する分散
   共有メモリ計算機システムにおいて、 共有データに対して参照または更新を行う各計算機上の
   プログラムにおいて、論理的に一つの共有データに対し
   て、二つ以上のプログラムで同時には更新処理を実行で
   きない、相互排除状態に移行することを指定する一貫性
   保証指定手段と、該相互排除状態を解除することを指定
   する一貫性保証解除手段と、 上記一貫性保証指定手段と一貫性保証解除手段の間に更
   新した共有データの内容を、他の計算機上の論理的に同
   一の共有データの内容に反映させる処理を行う一貫性保
   証制御手段とを上記共有データに対して参照または更新
   を行うプログラムが動作する各計算機に備え、 上記一貫性保証指定手段が実行された時点で一貫性保証
   制御手段によって発行される一貫性保証要求メッセージ
   を蓄える要求メッセージキュー手段を上記複数の計算機
   の少なくとも一つに備え、 上記一貫性保証指定手段には 、共有データに対する参
   照または更新処理の順序を指定する手段を含み、 上記要求メッセージキュー手段には、共有データに対す
   る参照または更新処理の順序の制御に関わる現在の状態
   を保持するカウンタ手段と、参照または更新処理の順序
   の制御に関わる値を蓄える手段を含むことを特徴とする
   分散共有メモリ計算機システム。
2. 【請求項２】請求項1記載において、 上記一貫性保証指定手段で指定される、上記共有データ
   に対する参照または更新処理の順序の制御に関わる値と
   して、参照または更新処理を順序付けるプログラムの数
   を表す値と、該プログラムの間で参照または更新処理を
   順序付ける優先度を表す値を指定し、 上記要求メッセージキュー手段は、 上記カウンタ手段において、参照または更新処理に関し
   て順序付けするプログラムの数を表す値を保持し、 上記共有データに対する参照または更新処理の順序の制
   御に関わる値を蓄える手段において、該プログラム間で
   参照または更新処理を行う順序を指定するための優先度
   を表す値を蓄えることを特徴とする分散共有メモリ計算
   機システム。
3. 【請求項３】請求項1記載において、上記一貫性保証指
   定手段では、共有データに対する参照または更新処理の
   順序を示す番号を設定する手段を備え、 上記要求メッセージキュー手段は、 上記カウンタ手段において、上記共有データに対する参
   照または更新処理の順序を示す番号をカウントする手段
   を備え、 上記共有データに対する参照または更新順序の制御に関
   わる値を蓄える手段において、上記共有データに対する
   参照または更新処理の順序を示す番号を蓄えることを特
   徴とする分散共有メモリ計算機システム。
4. 【請求項４】請求項1記載において、上記共有データの
   一貫性が保証されるまで、指定した一貫性保証区間の先
   頭で同期をとることを特徴とする分散共有メモリ計算機
   システム。
5. 【請求項５】請求項1記載において、上記カウンタ手段
   の値がある特定の値以外の時は、上記共有データに対す
   る一貫性保証要求メッセージに含まれる内容を、上記要
   求メッセージキュー手段に保持することを特徴とする分
   散共有メモリ計算機システム。
6. 【請求項６】請求項1記載において、上記他の計算機か
   らの上記要求メッセージキュー手段は、共有データに対
   する参照または更新処理の順序の制御に関わる値によっ
   て、上記一貫性保証要求メッセージの内容を保持する順
   番を変えることを特徴とする分散共有メモリ計算機シス
   テム。
7. 【請求項７】請求項1記載において、上記一貫性保証指
   定手段は、一貫性保証の指定を予約する手段と、その予
   約が受理されるのを待つ手段を備えたことを特徴とする
   分散共有メモリ計算機システム。
8. 【請求項８】請求項3記載において、上記複数計算機上
   の任意のプログラムの間で一斉に待ち合わせを行う同期
   手段を備え、該同期手段には、上記カウンタ手段の内容
   を任意の値に設定する手段を有することを特徴とする分
   散共有メモリ計算機システム。
9. 【請求項９】請求項3記載において、上記共有データに
   対して参照または更新処理を行う順序を示す番号を設定
   する手段で、特定の値を設定した場合は、上記要求メッ
   セージキュー手段は、蓄えられた一貫性保証要求の内容
   の順序を、予め定められた特定の順序に並べ替えること
   を特徴とする分散共有メモリ計算機システム。