JPH0713805A - 並列計算機及びプログラム実行再現方法 - Google Patents

Abstract

(57)【要約】 【目的】本発明は、プログラム再現に必要な情報の記録
量を減少させ、また任意のチェックポイントからのプロ
グラム再現を容易に行なうことを可能にする。 【構成】複数のプロセッシングエレメントから共有メモ
リに対してアクセスする並列計算機において、共有メモ
リ２は、データ保持部２０と、データの更新回数及び読
出し回数を記録するバージョン管理部２１と、アクセス
操作が行なわれたか否かを識別するためのアクセス識別
部２２とが設けられ、プログラム実行の際にスナップシ
ョットを実行し、チェックポイント間でアクセス操作が
行なわれたデータ、共有メモリ２に対するアクセス履
歴、及びチェックポイント時のプロセッサ状態情報を記
録し、プログラムを再現実行する際に、アクセス履歴に
基づいてプログラム再現の同期を取った後に、記録され
た情報をもとに再現された共有メモリ２及びプロセッサ
状態情報によりプログラムを再実行することを特徴とす
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、共有メモリを有する並
列計算機及び並列計算機におけるプログラムの実行再現
方法に関する。

【０００２】

【従来の技術】一般に、単一プロセッシングエレメント
の装置において、プログラムは繰り返し実行しても同じ
振舞をする。この性質を利用して、多くデバッギングツ
ールが開発されている。

【０００３】ところで、より処理能力の高い計算機を実
現するために、複数のプロセッシングエレメントを設
け、これらによって並列に処理を行なう並列計算機の開
発が行なわれている。

【０００４】並列計算機では、各プロセッシングエレメ
ントのタイミングのずれなどにより、プログラム実行
が、必ずしも同じ振舞をするとは限らない。また、任意
の経過時間からプログラム実行を再現するには、多くの
スナップショットと、メモリのアクセス履歴を保持する
必要がある。従って、単一プロセッシングエレメントの
装置に用いられるデバッギングツールを、単純に並列計
算機に対して適用することはできない。

【０００５】並列計算機でプログラムを再現する方式と
して、共有メモリを有するものでは、「Real-Time, Coc
urrent Checkpoint for Parallel Programs 」（Kai L
i,Jeffrey F. Naughton and James S. Plank, ACM SIGP
LAN Notices, Vol.25, No.3,pp. 79-88, 1990 ）に説明
されているような、チェックポイント毎に、メモリの内
容を全て記録しておく方式がある。この方式は、変化部
分だけ記録するように改良するのは容易であるが、プロ
グラム実行を再現するという点においては、プロセス間
の相互干渉情報を持たないため、特定の状態から始めた
としても必ずしも前回のプログラム実行と同じ結果にな
るとは限らない。

【０００６】また、分散環境における方式として、「IG
OR:A System for Program Debugging via Reversible E
xecution」（ S. Feldman and C. Brown, ACM SIGPLAN
Notices, Vol.24, No.1, pp.112-123, 1989 ）に説明さ
れているような、変化する部分だけをインクリメンタル
に記録する方式がある。この方式は、プロセス間の相互
干渉情報がメッセージの送受を記録したものであり、メ
ッセージ通信が共有メモリアクセスよりも遅いという特
性により、単位時間当たりに記録されるログ量は分散環
境のほうが相対的に少ない。ただし、メッセージに追い
越しが起こる場合には、単にどこから到着しただけでな
く、メッセージ送信元で付加する独特なメッセージ番号
や内容などの情報を記録する必要が生じる。

【０００７】さらに、従来では、共有メモリアクセスの
順序を再現するための履歴を記録するためには、各プロ
セッシングエレメント共通のグローバルクロックによっ
てタイムスタンプを取るか、共通の格納領域にプロセッ
シングエレメント番号とアクセス操作種別、データなど
を順序関係を保ちながら記録する必要があった。

【０００８】

【発明が解決しようとする課題】このように従来の並列
計算機では、同じ振舞いをするようにプログラムを再現
させるためには多くの情報を記録しておく必要があっ
た。また、任意のチェックポイントからのプログラムを
再現しようとする場合には、グローバルクロックや、メ
ッセージ送信元で付加する独特なメッセージ番号や内容
などの前述した各種情報を格納するための格納領域を設
ける等の必要があった。

【０００９】本発明は前記のような事情を考慮してなさ
れたもので、プログラム再現に必要な情報の記録量を減
少させると共に、任意のチェックポイントからのプログ
ラム再現を容易に行なうことが可能な並列計算機及びプ
ログラム実行再現方法を提供することを目的とする。

【００１０】

【課題を解決するための手段】本発明は、複数のプロセ
ッシングエレメントから共有メモリに対してアクセスす
る並列計算機において、データを格納するためのデータ
保持手段と、前記データ保持手段に保持されたデータに
対応して、同データに対する更新回数及び読出し回数を
示す情報を記録するバージョン管理手段と、前記データ
保持手段に保持されたデータを含むメモリブロック単位
で、アクセス操作が行なわれたか否かを識別するための
情報を記録するアクセス識別手段とが設けられた共有メ
モリと、プログラム実行時に前記プロセッシングエレメ
ントに対してスナップショットの実行を指示すると共
に、前記アクセス識別手段によって記録された情報に応
じて、チェックポイント間でアクセス操作が行なわれた
前記共有メモリ中の前記保持手段によって保持されたデ
ータ、及び前記バージョン管理手段によって記録された
情報を格納するスナップショット管理手段と、プログラ
ム再現時に前記プロセッシングエレメントに対して任意
のチェックポイントからプログラムの再現実行を指示す
ると共に、スナップショット管理手段によって格納され
た内容に基づいて前記共有メモリを復元する再現実行管
理手段とが設けられたチェックポイント管理手段と、前
記スナップショット管理手段によるスナップショットの
実行指示に応じて、前記共有メモリに対するアクセス履
歴を格納するアクセス履歴格納手段と、チェックポイン
ト時のプロセッサ状態情報を格納するプロセッサ状態格
納手段と、前記再現実行管理手段によるプログラム再現
実行の指示に応じて、前記プロセッサ状態格納手段によ
って格納されたプロセッサ状態情報を復元するプロセッ
サ状態復元手段と、前記アクセス履歴格納手段によって
格納されたアクセス履歴に基づいて、プログラム再現の
同期が取られた後に、前記再現実行管理手段によって再
現された前記共有メモリ及び前記プロセッサ状態復元手
段によって復元されたプロセッサ状態情報によりプログ
ラムを再実行するプロセッサとが設けられたプロセッシ
ングエレメントと、を具備したことを特徴する。

【００１１】

【作用】このような構成によれば、プログラム実行時に
おいて、各プロセッシングエレメントは、書き込み時に
はバージョン番号（更新回数）と読み出し回数を、読出
し時にはバージョン番号だけを記録する。また、定期的
に共有メモリのスナップショットとして、前回との変化
部分についてだけ記録しておく。

【００１２】任意のチェックポイントからプログラムの
実行を再現する場合、共有メモリは、当該チェックポイ
ント及びそれ以前の中から最新の共有メモリの情報を検
索し、共有メモリ内容を復元する。各プロセッシングエ
レメントは、当該チェックポイントのプロセッサ状態情
報からプロセッサ状態を復元する。

【００１３】プログラム実行再現時に、各プロセッシン
グエレメントは、共有メモリアクセス履歴に従い、書き
込み時にはバージョン番号と読み出し回数が一致するま
で、書き込み操作を待機させ、一致した時に、書き込み
操作を行なう。読出し時にはバージョン番号が一致する
まで、その操作を待機させ、一致した時に、読み込み操
作を行なう。これによりプログラム実行の再現を行な
う。

【００１４】

【実施例】以下、図面を参照して本発明の一実施例を説
明する。図１は本実施例に係わる並列計算機の主要な構
成を示すブロック図である。図１に示すように、並列計
算機は、複数のプロセッシングエレメント１−１，１−
２，…，１−ｎ、共有メモリ２、チェックポイント管理
部３、二次記憶装置４、及びバス５によって構成されて
いる。プロセッシングエレメント１−１，１−２，…，
１−ｎ、共有メモリ２、及びチェックポイント管理部３
は、バス５を介して接続されており、各プロセッシング
エレメント１−１，１−２，…，１−ｎから共有メモリ
２に対する書き込み／読出し操作がバス５を経由して行
なわれる。

【００１５】各プロセッシングエレメント１−１，１−
２，…，１−ｎには、プロセッサ１０、ローカルメモリ
１１、プロセッサ状態管理部１２、アクセス履歴管理部
１３が設けられている。プロセッサ状態管理部１２は、
プロセッサ状態情報を管理するもので、プロセッサ１０
のＰＳＷ（program status word ）、レジスタ、ローカ
ルメモリの内容を含むプロセッサ状態情報を格納するた
めのプロセッサ状態格納部１２ａ、プロセッサ状態情報
を任意の時点に復元するプロセッサ状態復元部１２ｂが
設けられている。アクセス履歴管理部１３は、各プロセ
ッサの共有メモリ２に対するアクセス履歴を格納するた
めのアクセス履歴格納部１３ａと、共有メモリ２に対す
るアクセスの順序を復元するアクセス履歴復元部１３ｂ
が設けられている。なお、ローカルメモリ１１は、必ず
しも必要ではなく、以下の説明を行なうために構成要素
としている。

【００１６】共有メモリ２には、データ保持部２０、バ
ージョン管理部２１、アクセス識別部２２が設けられて
いる。データ保持部２０は、各プロセッシングエレメン
ト１−１，１−２，…，１−ｎによって操作されるデー
タを格納するためのものである。バージョン管理部２１
は、データ保持部２０に格納された各データに対応し
て、データに対する更新回数を示すバージョン番号とそ
のバージョン番号の値に対応する読出し回数を管理する
もので、読出し回数カウンタ２１ａ、更新回数カウンタ
２１ｂが設けられている。アクセス識別部２２は、メモ
リブロック単位で、その領域にアクセスされたか否かを
識別するためのフラグ（アクセス情報）を記録するため
のものである。また、アクセスされたか否かを識別する
だけでなく、読出し／書き込みアクセスを区別して記録
するようにしても良い。アクセス識別部２２によって読
出し／書き込みアクセスを区別して記録しない場合とす
る場合の各状況毎に、動作の説明を後述している。

【００１７】チェックポイント管理部３には、スナップ
ショット管理部３０、及び再現実行管理部３１が設けら
れている。スナップショット管理部３０は、プログラム
実行時に定期的に各プロセッシングエレメント１−１，
１−２，…，１−ｎに対してスナップショットの実行を
指示するものである。スナップショット管理部３０は、
各プロセッシングエレメント１−１，１−２，…，１−
ｎのプロセッサ状態管理部１２に対して、プロセッサ状
態、及びローカルメモリ１１の内容を保存させ、アクセ
ス履歴管理部１３に対して、共有メモリ２の情報を保存
させる。再現実行管理部３１は、プログラム再現時に任
意のチェックポイント状態からプログラムを再現実行す
ることを所定の各部に指示するものであり、任意のチェ
ックポイントでの状態からプログラムを再現実行させる
ため、プロセッサ状態管理部１２に対して当該チェック
ポイントのプロセッサ状態、及びローカルメモリ１１を
復元させ、アクセス履歴管理部１３に対して共有メモリ
２の情報を復元させる。

【００１８】二次記憶装置４は、チェックポイント管理
部３による制御のもとに、プログラム実行を再現するた
めの各種データ、例えばデータ保持部２０中のデータ
や、バージョン管理部２１の読出し回数カウンタ２１ａ
及び更新回数カウンタ２１ｂの値を記憶するためのもの
である。

【００１９】次に、本実施例の動作について、各状況毎
に説明する。ここでは、プロセッシングエレメント１−
１，１−２，…，１−ｎ中の任意のプロセッシングエレ
メントＰの動作を例にして説明する。

【００２０】（１）アクセス識別部２２で読出し／書き
込みを区別しない方法。 （１−Ａ）プログラムの実行時。 ここでは、プロセッシングエレメントＰが共有メモリ２
のアドレスＡＤＤＲ１からデータを読出してレジスタＸ
に格納する読出し命令を発行する例を用いて、共有メモ
リ２に対する読出し操作を説明する。なお、この命令の
処理が実行される前の、共有メモリ２の状態が図２
（ａ）に示すようになっているものとする。すなわち、
データ保持部２０のアドレスＡＤＤＲ１にはデータ５が
格納され、このデータに対応してバージョン管理部２１
の読出し回数カウンタ２１ａの値が３、更新回数カウン
タ２１ｂの値が２であり、アクセス識別部２２のアドレ
スＡＤＤＲ１に対応するメモリブロックのフラグが「ｏ
ｆｆ」となっている。

【００２１】まず、読出し命令に応じて、アクセス識別
部２２の当該アドレスに対応するメモリブロックのアク
セスフラグを「ｏｎ」にする。また、データ保持部２０
から当該アドレスのデータ５を取り出し、プロセッシン
グエレメントＰのプロセッサに渡す。

【００２２】バージョン管理部２１は、当該アドレスの
読出し回数カウンタ２１ａをインクリメントし（値は
４）、更新回数カウンタ２１ｂから当該アドレスの更新
回数の値２を取り出して、プロセッシングエレメントＰ
のアクセス履歴管理部１３に渡す。プロセッシングエレ
メントＰのアクセス履歴管理部１３は、その値をアクセ
ス履歴格納部１３ａにログとして記録する。

【００２３】前述した読出し操作の後、共有メモリ２の
状態は図２（ｂ）、アクセス履歴管理部１３のアクセス
履歴格納部１３ａに格納されたログの内容は図２
（ｃ）、プロセッシングエレメントＰのプロセッサ１０
のレジスタＸの内容は図２（ｄ）に示すようにそれぞれ
変化する。

【００２４】次に、プロセッシングエレメントＰが共有
メモリ２のアドレスＡＤＤＲ２にレジスタＸの内容を書
き込む命令を発行する例を用いて、共有メモリ２に対す
る書き込み操作を説明する。なお、この命令の処理が実
行される前の、共有メモリ２の状態が図３（ａ）、プロ
セッシングエレメントＰのプロセッサ１０のレジスタＸ
の内容が図３（ｂ）に示すようになっているものとす
る。すなわち、データ保持部２０のアドレスＡＤＤＲ２
にはデータ５が格納され、このデータに対応してバージ
ョン管理部２１の読出し回数カウンタ２１ａの値が４、
更新回数カウンタ２１ｂの値が２であり、アクセス識別
部２２のアドレスＡＤＤＲ２に対応するメモリブロック
のフラグが「ｏｎ」となっている。また、レジスタＸの
内容はデータ１０となっている。

【００２５】まず、書き込み命令に応じて、アクセス識
別部２２の当該アドレスに対応するメモリブロックのア
クセスフラグを「ｏｎ」にする。また、データ保持部２
０は、プロセッシングエレメントＰのプロセッサ１０か
らのレジスタＸのデータ１０を当該アドレスに設定す
る。

【００２６】バージョン管理部２１は、当該アドレスの
読出し回数カウンタ２１ａの値４と更新回数カウンタ２
１ｂの値２をプロセッシングエレメントＰのアクセス履
歴管理部１３に渡すと共に、読出し回数カウンタ２１ａ
をクリアし、更新回数カウンタ２１ｂをインクリメント
する。プロセッシングエレメントＰのアクセス履歴管理
部１３は、その読出し回数カウンタ２１ａの値と更新回
数カウンタ２１ｂの値（バージョン番号）をログとして
記録する。

【００２７】前述した書き込み操作の後、共有メモリ２
の状態は図３（ｃ）、アクセス履歴管理部１３のアクセ
ス履歴格納部１３ａに格納されたログの内容は図３
（ｄ）に示すようにそれぞれ変化する。

【００２８】スナップショット管理部３０は、定期的に
チェックポイントを作るために、各プロセッシングエレ
メント１−１，１−２，…，１−ｎに、スナップショッ
トを取ることを指示する。この際、スナップショット管
理部３０は、各プロセッシングエレメント１−１，１−
２，…，１−ｎへの割り込みで行なってもよく、またス
ナップショット管理部３０が共有メモリ２の特定領域に
スナップショット命令を書き込み、各プロセッサがその
特定領域を定期的にポーリングすることによって行なっ
ても良い。

【００２９】チェックポイントを生成するために、各プ
ロセッシングエレメント１−１，１−２，…，１−ｎの
プロセッサ１０は通常の処理を中断する。プロセッサ状
態管理部１２は、プロセッサ１０の状態、及びローカル
メモリ１１の内容をプロセッサ状態格納部１２ａに保存
する。なお、ローカルメモリ内容は、プロセッサ１０に
よってアクセスされるだけなので、値が変更された部分
だけを格納していけば良い。プロセッサ状態は、その時
点よりプログラムを復元するために必要な各種レジスタ
の内容、及びＰＳＷである。

【００３０】スナップショット管理部３０は、アクセス
識別部２２のアクセス情報を参照して前回のスナップシ
ョット以降にアクセスされた部分を探す。例えば、スナ
ップショットを取る直前の共有メモリ２の一部が図４
（ａ）に示すようになっているものとする。

【００３１】この場合、アクセス識別部２２にはメモリ
ブロックｉ，ｋのフラグが「ｏｎ」となっているため、
スナップショット管理部３０は、共有メモリ２に格納さ
れた、データ保持部２０のメモリブロックｉ，ｋのデー
タ、バージョン管理部２１の読出し回数カウンタ２１ａ
及び更新回数カウンタ２１ｂの値を二次記憶装置４に格
納する。図４（ｂ）はスナップショットによって記録さ
れる情報を示している。

【００３２】これらの処理が終了すると、スナップショ
ット管理部３０は、アクセス識別部２２にアクセス情報
をクリアさせ、各プロセッサにスナップショットが完了
したことを伝える。各プロセッサは、通常の処理を再開
する。図４（ｃ）は図４（ａ）に対応する、スナップシ
ョット後の共有メモリ２の内容を示している。

【００３３】（１−Ｂ）プログラムの再現時。 任意のチェックポイントから処理を再現するために、再
現実行管理部３１は、各プロセッシングエレメント１−
１，１−２，…，１−ｎに再現すべきチェックポイント
位置を通知する。

【００３４】プロセッサ状態管理部１２のプロセッサ状
態復元部１２ｂは、再現実行管理部３１によって通知さ
れたチェックポイント位置のプロセッサ状態、及びロー
カルメモリ内容を、プロセッサ状態格納部１２ａから検
索し、それぞれをプロセッサ１０とローカルメモリ１１
に設定する。

【００３５】アクセス履歴管理部１３のアクセス履歴復
元部１３ｂは、通知されたチェックポイントからの履歴
をアクセスできるように、ログを当該チェックポイント
時点の先頭から読み出す準備をする。

【００３６】再現実行管理部３１は、共有メモリ２の状
態を復元するため、再現すべきチェックポイント、及び
それ以前のチェックポイントのスナップショットによっ
て記録された情報を、二次記憶装置４から、それぞれの
メモリブロックの最新情報を検索し、共有メモリ２のデ
ータ保持部２０、バージョン管理部２１（読出し回数カ
ウンタ２１ａ、更新回数カウンタ２１ｂ）に設定する。

【００３７】これらの処理が終了すると、再現実行管理
部３１は、各プロセッシングエレメント１−１，１−
２，…，１−ｎの各プロセッサ１０に実行再現準備が完
了したことを通知する。

【００３８】ここでは、プロセッシングエレメントＰが
共有メモリ２のアドレスＡＤＤＲ１からデータを読出し
てレジスタＸに格納する読出し命令を発行する例を用い
て、共有メモリ２に対する読出し操作を説明する。な
お、この命令の処理が実行される前の、共有メモリ２の
状態が図５（ａ）、プロセッシングエレメントＰのアク
セス履歴格納部１３ａに格納されたログが図５（ｂ）に
示すようになっているものとする。

【００３９】プロセッサ１０は、共有メモリ２に対する
読出し操作を行なう際、アクセス履歴管理部１３からの
ログ情報と、バージョン管理部２１の更新回数カウンタ
２１ｂの値が等しくなるまでウエイトされる。両者の値
が等しくなった時、バージョン管理部２１は、読出し回
数カウンタ２１ａの値をインクリメントし、プロセッサ
１０にデータ保持部２０のデータを渡し、処理を継続さ
せる。アクセス履歴管理部１３は、ログのポインタを進
める。この例では、ＡＤＤＲ１に対応する更新回数カウ
ンタ２１ｂの値が２になるまでプロセッサ１０をウエイ
トさせ、更新回数カウンタ２１ｂの値が２になったなら
ば、読出し回数カウンタ２１ａをインクリメントする。
この命令の処理が行なわれた後の共有メモリ２の状態は
図５（ｃ）に示すようになる。

【００４０】次に、プロセッシングエレメントＰが共有
メモリ２のアドレスＡＤＤＲ２にレジスタＸの内容を書
き込む命令を発行する例を用いて、共有メモリ２に対す
る書き込み操作を説明する。なお、この命令の処理が行
なわれる前の、共有メモリ２の状態が図６（ａ）、プロ
セッシングエレメントＰのプロセッサ１０のレジスタＸ
の内容が図６（ｂ）、アクセス履歴管理部１３のアクセ
ス履歴格納部１３ａに格納されたログが図６（ｃ）に示
すようになっているものとする。

【００４１】プロセッサ１０は、共有メモリ２に対する
書き込み操作を行なう際、アクセス履歴管理部１３から
のバージョン番号（更新回数）とバージョン管理部２１
の更新回数カウンタ２１ｂの値が等しく、かつ、アクセ
ス履歴管理部１３からの読出し回数と読出し回数カウン
タ２１ａの値が等しくなるまでウエイトされる。それぞ
れで値が等しくなった時に、共有メモリ２は、プロセッ
サ１０からのデータをデータ保持部２０に格納し、バー
ジョン管理部２１の更新回数カウンタ２１ｂをインクリ
メントし、読出し回数カウンタ２１ａをクリアする。そ
して、プロセッサ１０の処理を継続させ、アクセス履歴
管理部１３のログのポインタを進める。

【００４２】この例では、ＡＤＤＲ２に対応する更新回
数カウンタ２１ｂの値が２になり、かつ、読出し回数カ
ウンタ２１ａの値が４になるまで、プロセッサをウエイ
トさせ、更新回数カウンタ２１ｂの値が２で、かつ、読
出し回数カウンタ２１ａ値が４になったならば、更新回
数カウンタ２１ｂをインクリメントし、読出し回数カウ
ンタ２１ａをクリアする。この命令の処理が行なわれた
後の共有メモリ２の状態は図６（ｄ）に示すようにな
る。

【００４３】（２）アクセス識別部２２において読出し
／書き出しアクセスを区別する方法。 前述したように、アクセス識別部２２において読出し／
書き出しアクセスを区別しない方法では、アクセス履歴
管理部１３は、アクセスされたか否かだけを「ｏｎ／ｏ
ｆｆ」で記録していたが、区別する方法では、書き込み
だけの時は「Ｒ（Ｒｅａｄ）」、書き込みだけの時は
「Ｗ（Ｗｒｉｔｅ）」、両方行なわれた時は「Ｒ／Ｗ
（Ｒｅａｄ／Ｗｒｉｔｅ）」、アクセスされていない時
は「ｏｆｆ」を記録するものとする。

【００４４】（２−Ａ）プログラムの実行時。 ここでは、プロセッシングエレメントＰが共有メモリ２
のアドレスＡＤＤＲ１の内容をレジスタＸに格納する命
令を発行する例を用いて共有メモリ２に対する読出し操
作を説明する。

【００４５】まず、読出し命令に応じて、アクセス識別
部２２のアドレスＡＤＤＲ１に対応するメモリブロック
のアクセスフラグがＷであれば「Ｒ／Ｗ」にし、それ以
外の時は「Ｒ」にする。また、データ保持部２０から当
該アドレスのデータを取り出し、プロセッシングエレメ
ントＰのプロセッサに渡す。

【００４６】バージョン管理部２１は、当該アドレスの
読出し回数カウンタ２１ａをインクリメントし、更新回
数カウンタ２１ｂから当該アドレスの更新回数を取り出
して、プロセッシングエレメントＰのアクセス履歴管理
部１３に渡す。プロセッシングエレメントＰのアクセス
履歴管理部１３は、その値をログとして記録する。

【００４７】次に、プロセッシングエレメントＰが共有
メモリ２のアドレスＡＤＤＲ２にレジスタＸの内容を書
き込む命令を発行する例を用いて、共有メモリ２に対す
る読出し操作を説明する。

【００４８】まず、書き込み命令に応じて、アクセス識
別部２２の当該アドレスに対応するメモリブロックのア
クセスフラグが「Ｒ」であれば「Ｒ／Ｗ」にし、それ以
外の時は「Ｗ」にする。また、データ保持部２０は、プ
ロセッシングエレメントＰのプロセッサ１０からのレジ
スタＸのデータを当該アドレスに設定する。

【００４９】バージョン管理部２１は、当該アドレスの
読出し回数カウンタ２１ａ値と更新回数カウンタ２１ｂ
の値をプロセッシングエレメントＰのアクセス履歴管理
部１３に渡すと共に、読出し回数カウンタ２１ａをクリ
アし、更新回数カウンタ２１ｂをインクリメントする。
プロセッシングエレメントＰのアクセス履歴管理部１３
は、その読出し回数カウンタ２１ａの値と更新回数カウ
ンタ２１ｂの値（更新バージョン９をログとして記録す
る。

【００５０】スナップショット管理部３０は、定期的に
チェックポイントを作るために、各プロセッシングエレ
メント１−１，１−２，…，１−ｎに、スナップショッ
トを取ることを指示する。

【００５１】チェックポイントを生成するために、各プ
ロセッシングエレメント１−１，１−２，…，１−ｎの
プロセッサ１０は通常の処理を中断する。プロセッサ状
態管理部１２は、プロセッサ１０の状態、及びローカル
メモリ１１の内容をプロセッサ状態格納部１２ａに保存
する。

【００５２】スナップショット管理部３０は、アクセス
識別部２２のアクセス情報を参照して前回のスナップシ
ョット以降にアクセスされた部分を探す。例えば、スナ
ップショットを取る直前の共有メモリ２の一部が図７
（ａ）に示すようになっているものとする。

【００５３】この場合、アクセス識別部２２にはメモリ
ブロックｋのフラグが「Ｗ」となっているため、スナッ
プショット管理部３０は、共有メモリ２に格納された、
書き込み操作が行なわれているメモリブロックｋの部分
のデータ保持部２０のデータ、バージョン管理部２１の
読出し回数カウンタ２１ａ及び更新回数カウンタ２１ｂ
の値を二次記憶装置４に格納する。さらに、スナップシ
ョット管理部３０は、アクセス識別部２２のフラグが
「Ｒ」となっている、読出し操作だけが行なわれている
メモリブロックｉの部分の、読出し回数カウンタ２１ａ
及び更新回数カウンタ２１ｂの値を二次記憶装置４に格
納する。図７（ｂ）はスナップショットによって記録さ
れる情報を示している。

【００５４】これらの処理が終了すると、スナップショ
ット管理部３０は、アクセス識別部２２にアクセス情報
をクリアさせ、各プロセッサにスナップショットが完了
したことを伝える。各プロセッサは、通常の処理を再開
する。図７（ｃ）は図７（ａ）に対応する、スナップシ
ョット後の共有メモリ２の内容を示している。

【００５５】（２−Ｂ）プログラムの再現時 任意のチェックポイントから処理を再現するために、再
現実行管理部３１は、各プロセッシングエレメント１−
１，１−２，…，１−ｎに再現すべきチェックポイント
位置を通知する。

【００５６】プロセッサ状態管理部１２は、再現実行管
理部３１によって通知されたチェックポイント位置のプ
ロセッサ状態、及びローカルメモリ内容をプロセッサ状
態格納部１２ａから検索し、それぞれをプロセッサ１０
とローカルメモリ１１に設定する。

【００５７】アクセス履歴管理部１３は、通知されたチ
ェックポイントからの履歴をアクセスできるように、ロ
グを当該チェックポイント時点の先頭から読み出す準備
をする。

【００５８】再現実行管理部３１は、共有メモリ２の状
態を復元するため、再現すべきチェックポイント、及び
それ以前のチェックポイントのスナップショットによっ
て記録された情報から、それぞれのメモリブロックの最
新情報を検索し、共有メモリ２のデータ保持部２０、バ
ージョン管理部２１（読出し回数カウンタ２１ａ、更新
回数カウンタ２１ｂ）に設定する。この際、共有メモリ
２のデータ保持部２０中のデータと、バージョン管理部
２１中の情報は別々に検索されるものとする。

【００５９】これらの処理が終了すると、再現実行管理
部３１は、各プロセッシングエレメント１−１，１−
２，…，１−ｎの各プロセッサ１０に実行再現準備が完
了したことを通知する。

【００６０】プロセッサ１０は、共有メモリ２に対する
読出し操作を行なう際、アクセス履歴管理部１３からの
ログ情報と、バージョン管理部２１の更新回数カウンタ
２１ｂの値が等しくなるまでウエイトされる。両者の値
が等しくなった時、バージョン管理部２１は、読出し回
数カウンタ２１ａの値をインクリメントし、プロセッサ
１０にデータ保持部２０のデータを渡し、処理を継続さ
せる。アクセス履歴管理部１３は、ログのポインタを進
める。

【００６１】また、プロセッサ１０は、共有メモリ２に
対する書き込み操作を行なう際、アクセス履歴管理部１
３からのバージョン番号（更新回数）とバージョン管理
部２１の更新回数カウンタ２１ｂの値が等しく、かつ、
アクセス履歴管理部１３からの読出し回数と読出し回数
カウンタ２１ａの値が等しくなるまでウエイトされる。
それぞれで値が等しくなった時に、共有メモリ２は、プ
ロセッサ１０からのデータをデータ保持部２０に格納
し、バージョン管理部２１の更新回数カウンタ２１ｂを
インクリメントし、読出し回数カウンタ２１ａをクリア
する。そして、プロセッサ１０の処理を継続させ、アク
セス履歴管理部１３のログのポインタを進める。

【００６２】

【発明の効果】以上のように本発明によれば、データ更
新回数とアクセス回数、及び共有メモリのデータ変化部
分だけからプログラム再現できるようにすることによ
り、プログラム再現に必要な情報の記録量を減らすこと
ができる。また、任意のチェックポイントからのプログ
ラム再現をバージョン番号によって同期をとるため、グ
ローバルクロックや共通の格納領域を必要とすることな
しに実現することができるという効果がある。

【図面の簡単な説明】

【図１】本発明の一実施例に係わる並列計算機の主要な
構成を示すブロック図。

【図２】アクセス識別部２２で読出し／書き込みを区別
しない方法におけるプログラム実行時の読出し操作を説
明するための図。

【図３】アクセス識別部２２で読出し／書き込みを区別
しない方法におけるプログラム実行時の書き込み操作を
説明するための図。

【図４】アクセス識別部２２で読出し／書き込みを区別
しない方法におけるスナップショットを説明するための
図。

【図５】アクセス識別部２２で読出し／書き込みを区別
する方法におけるプログラム再現時の読出し操作を説明
するための図。

【図６】アクセス識別部２２で読出し／書き込みを区別
する方法におけるプログラム再現時の書き込み操作を説
明するための図。

【図７】アクセス識別部２２で読出し／書き込みを区別
する方法におけるスナップショットを説明するための
図。

【符号の説明】

１−１，１−２，…，１−ｎ…プロセッシングエレメン
ト、２…共有メモリ、３…チェックポイント管理部、４
…二次記憶装置、５…バス、１０…プロセッサ、１１…
ローカルメモリ、１２…プロセッサ状態管理部、１３…
アクセス履歴管理部、２０…データ保持部、２１…バー
ジョン管理部、２１ａ…読出し回数カウンタ、２１ｂ…
更新回数カウンタ、２２…アクセス識別部、３０…スナ
ップショット管理部、３１…再現実行管理部。

Claims (2)

【特許請求の範囲】
1. 【請求項１】 複数のプロセッシングエレメントから共
   有メモリに対してアクセスする並列計算機において、 データを格納するためのデータ保持手段と、 前記データ保持手段に保持されたデータに対応して、同
   データに対する更新回数及び読出し回数を示す情報を記
   録するバージョン管理手段と、 前記データ保持手段に保持されたデータを含むメモリブ
   ロック単位で、アクセス操作が行なわれたか否かを識別
   するための情報を記録するアクセス識別手段と、 が設けられた共有メモリと、 プログラム実行時に前記プロセッシングエレメントに対
   してスナップショットの実行を指示すると共に、前記ア
   クセス識別手段によって記録された情報に応じて、チェ
   ックポイント間でアクセス操作が行なわれた前記保持手
   段によって保持されたデータ、及び前記バージョン管理
   手段によって記録された情報を格納するスナップショッ
   ト管理手段と、 プログラム再現時に前記プロセッシングエレメントに対
   して任意のチェックポイントからプログラムの再現実行
   を指示すると共に、前記スナップショット管理手段によ
   って格納された内容に基づいて前記共有メモリを復元す
   る再現実行管理手段と、 が設けられたチェックポイント管理手段と、 前記スナップショット管理手段によるスナップショット
   の実行指示に応じて、前記共有メモリに対するアクセス
   履歴を格納するアクセス履歴格納手段と、 チェックポイント時のプロセッサ状態情報を格納するプ
   ロセッサ状態格納手段と、 前記再現実行管理手段によるプログラム再現実行の指示
   に応じて、前記プロセッサ状態格納手段によって格納さ
   れたプロセッサ状態情報を復元するプロセッサ状態復元
   手段と、 前記アクセス履歴格納手段によって格納されたアクセス
   履歴に基づいて、プログラム再現の同期が取られた後
   に、前記再現実行管理手段によって再現された前記共有
   メモリ及び前記プロセッサ状態復元手段によって復元さ
   れたプロセッサ状態情報によりプログラムを再実行する
   プロセッサと、 が設けられたプロセッシングエレメントと、 を具備したことを特徴とする並列計算機。
2. 【請求項２】 複数のプロセッシングエレメントから共
   有メモリに対してアクセスする並列計算機におけるプロ
   グラム実行再現方法であって、 前記共有メモリは、 データを格納するためのデータ保持手段と、 前記データ保持手段に保持されたデータに対応して、同
   データに対する更新回数及び読出し回数を示す情報を記
   録するバージョン管理手段と、 前記データ保持手段に保持されたデータを含むメモリブ
   ロック単位で、アクセス操作が行なわれたか否かを識別
   するための情報を記録するアクセス識別手段とが設けら
   れ、 プログラムを実行する際に、前記プロセッシングエレメ
   ントに対してスナップショットを実行し、 前記アクセス識別手段によって記録された情報に応じ
   た、チェックポイント間でアクセス操作が行なわれた前
   記保持手段によって保持されたデータ、及び前記バージ
   ョン管理手段によって記録された情報、並びに前記共有
   メモリに対するアクセス履歴及びチェックポイント時の
   プロセッサ状態情報を記録し、 プログラムを再現実行する際に、 前記アクセス履歴に基づいてプログラム再現の同期が取
   られた後に、前記スナップショットによって記録された
   情報をもとに再現された前記共有メモリ及びプロセッサ
   状態によりプログラムを再実行することを特徴とするプ
   ログラム実行再現方法。