(57)【特許請求の範囲】
【請求項１】
各々がＣＰＵ（計算主体）、チェックシステムおよびメモリを含むノードとして独立してコンピュータ計算を進めることが可能であって、あるノード（自己ノード）及び少なくとも１つの他のノード（非自己ノード）を含み、これら複数のノードが互いに通信できるようにリンクされており、これらの複数のノードにわたって、何らかの離散時間に属する計算用データグループ（データ配列など）をある離散時間から次の離散時間へと発展させながら、コンピュータ計算を並列に進めていく方法であって、
あるノードにおいて、ある離散時間に属する計算用データグループであって、離散時間の発展において収束先が初期値に依存しない問題が適用されている計算用データグループに基づいたコンピュータ計算を開始して、その計算結果が所定の範囲に収束するまで反復法の計算を実行するステップと、
あるノードにおいて、開始したコンピュータ計算を停止（中断）することなく、反復法の計算の実行に並行して、反復法の計算を実行している途中の所定のタイミング（時点）において、チェックポイントとしての中間計算データグループを取得するステップと、
あるノードにおいて、取得したチェックポイントとしての中間計算データグループを、外部メモリに記憶するステップと、
あるノードにおいて、次の離散時間へと離散時間を発展させる前に、他のノードにおいて並列に進められているところの前述した全てのステップが完了していることが確認されるのを待つステップと、
完了が確認されたことに応じて、あるノードにおいて、収束した計算結果を参照して、次の離散時間に属する計算用データグループに基づいたコンピュータ計算を開始するステップとを有する、
方法。
【請求項２】
さらに、チェックポイントからの回復として、
あるノードにおいて、外部メモリに記憶されているところの、取得したチェックポイントとしての中間計算データグループを参照するステップと、
あるノードにおいて、これらデータグループおよびデータに基づいたコンピュータ計算を開始して、その計算結果が所定の範囲に収束するまで反復法の計算を実行するステップとを有する、
請求項１に記載の方法。
【請求項３】
各々がＣＰＵ（計算主体）、チェックシステムおよびメモリを含むノードとして独立してコンピュータ計算を進めることが可能であって、あるノード（自己ノード）及び少なくとも１つの他のノード（非自己ノード）を含み、これら複数のノードが互いに通信できるようにリンクされており、これらの複数のノードにわたって、何らかの離散時間に属する計算用データグループ（データ配列など）をある離散時間から次の離散時間へと発展させながら、コンピュータ計算を並列に進めていく、システムであって、
あるノードにおいて、ある離散時間に属する計算用データグループであって、離散時間の発展において収束先が初期値に依存しない問題が適用されている計算用データグループに基づいたコンピュータ計算を開始して、その計算結果が所定の範囲に収束するまで反復法の計算を実行し、
あるノードにおいて、開始したコンピュータ計算を停止（中断）することなく、反復法の計算の実行に並行して、反復法の計算を実行している途中の所定のタイミング（時点）において、チェックポイントとしての中間計算データグループを取得し、
あるノードにおいて、取得したチェックポイントとしての中間計算データグループを外部メモリに記憶し、
あるノードにおいて、次の離散時間へと離散時間を発展させる前に、他のノードにおいて並列に進められているところの前述した全ての処理が完了していることが確認されるのを待ち、
完了が確認されたことに応じて、あるノードにおいて、収束した計算結果を参照して、次の離散時間に属する計算用データグループに基づいたコンピュータ計算を開始する、
システム。
【請求項４】
さらに、チェックポイントからの回復として、
あるノードにおいて、外部メモリに記憶されているところの、取得したチェックポイントとしての中間計算データグループを参照し、
あるノードにおいて、これらデータグループおよびデータに基づいたコンピュータ計算を開始して、その計算結果が所定の範囲に収束するまで反復法の計算を実行する、
請求項３に記載のシステム。
【請求項５】
ＣＰＵ（計算主体）、チェックシステムおよびメモリを含むノードとして独立してコンピュータ計算を進めることが可能であって、少なくとも１つの他のノード（非自己ノード）との間で互いに通信できるようにリンクされており、これらの複数のノードにわたって、何らかの離散時間に属する計算用データグループ（データ配列など）をある離散時間から次の離散時間へと発展させながら、コンピュータ計算を並列に進めていく、ノード（自己ノード）において実行する方法であって、
ある離散時間に属する計算用データグループであって、離散時間の発展において収束先が初期値に依存しない問題が適用されている計算用データグループに基づいたコンピュータ計算を開始して、その計算結果が所定の範囲に収束するまで反復法の計算を実行するステップと、
開始したコンピュータ計算を停止（中断）することなく、反復法の計算の実行に並行して、反復法の計算を実行している途中の所定のタイミング（時点）において、チェックポイントとしての中間計算データグループを取得するステップと、
取得したチェックポイントしての中間計算データグループを、外部メモリに記憶するステップと、
次の離散時間へと離散時間を発展させる前に、他のノードにおいて並列に進められているところの前述した全ての処理が完了していることが確認されるのを待つステップと、
完了が確認されたことに応じて、収束した計算結果を参照して、次の離散時間に属する計算用データグループに基づいたコンピュータ計算を開始するステップとを有する、
ノード（自己ノード）において実行する方法。
【請求項６】
さらに、チェックポイントからの回復として、
外部メモリに記憶されているところの、取得したチェックポイントとしての中間計算データグループを参照するステップと、
これらデータグループおよびデータに基づいたコンピュータ計算を開始して、その計算結果が所定の範囲に収束するまで反復法の計算を実行するステップとを有する、
請求項５に記載のノード（自己ノード）において実行する方法。
【請求項７】
ＣＰＵ（計算主体）、チェックシステムおよびメモリを含むノードとして独立してコンピュータ計算を進めることが可能であって、少なくとも１つの他のノード（非自己ノード）との間で互いに通信できるようにリンクされており、これらの複数のノードにわたって、何らかの離散時間に属する計算用データグループ（データ配列など）をある離散時間から次の離散時間へと発展させながら、コンピュータ計算を並列に進めていく、ノード（自己ノード）であって、
ある離散時間に属する計算用データグループであって、離散時間の発展において収束先が初期値に依存しない問題が適用されている計算用データグループに基づいたコンピュータ計算を開始して、その計算結果が所定の範囲に収束するまで反復法の計算を実行し、
開始したコンピュータ計算を停止（中断）することなく、反復法の計算の実行に並行して、反復法の計算を実行している途中の所定のタイミング（時点）において、チェックポイントとしての中間計算データグループを取得し、
取得したチェックポイントとしての中間計算データグループを、外部メモリに記憶し、
次の離散時間へと離散時間を発展させる前に、他のノードにおいて並列に進められているところの前述した全ての処理が完了していることが確認されるのを待ち、
完了が確認されたことに応じて、収束した計算結果を参照して、次の離散時間に属する計算用データグループに基づいたコンピュータ計算を開始する、
ノード（自己ノード）。
【請求項８】
さらに、チェックポイントからの回復として、
外部メモリに記憶されているところの、取得したチェックポイントとしての中間計算データグループを参照し、
これらデータグループおよびデータに基づいたコンピュータ計算を開始して、その計算結果が所定の範囲に収束するまで反復法の計算を実行する、
請求項７に記載のノード（自己ノード）。
【請求項９】
請求項１、２、５または６の何れかに記載の方法の各ステップを、あるノード（自己ノード）に含まれるところの、ＣＰＵ（計算主体）若しくはチェックシステムまたはこれらを一体にしたものに実行させる、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、反復法(iterationmethod)のコンピュータ計算を並列に進めていくにあたって、チェックポイント(Checkpoint)取得を行い、回復にあたってその取得されたデータを効率的に生かす技術に関する。
【背景技術】
【０００２】
スーパーコンピュータ(Supercomputer)の規模の拡大に伴い、チェックポイント(Checkpoint)に要する時間の増大が大きな問題となりつつある。 チェックポイントの取得には長時間かかるが、書換えの起きるメモリの特定時点でのチェックポイントを取得するため、チェックポイント取得中の計算の一時停止等、整合性を確保するためのオーバヘッドが必要となる。
【０００３】
（従来技術の例１）Copy-on-writeand incremental Checkpointing：
この方式の概要：  メモリをコピーオンライト(copy-on-write)でwriteプロテクトした上で、計算を停止（中断）せずにCheckpointを事前取得する。Checkpointの事前取得後に計算を停止し、copy-on-writeメカニズムによりコピーされた事前取得中の更新部分を事前取得したCheckpointに反映させる。
この方式の不利な点：  メモリの更新される範囲が小さい場合のみに有効な手法と言える。LU分解計算、Poisson 方程式の解法等に適用した場合、Checkpointの取得中にメモリの広範囲が変更されるため、Checkpoint事前取得中の変更をCheckpointへ反映させるための停止時間がかかり、停止時間が削減できない。
【０００４】
（従来技術の例２）Flashmemory/MRAM等disk以外への不揮発性媒体の使用：
この方式の概要:  HDD等低速なメディアに書き込む前に一旦高速な不揮発性媒体にコピーすることにより、停止時間を削減する。
この方式の不利な点:  不揮発性メモリのための余分なコストがかかる。現在のスーパーコンピュータではメモリコストが全体の半分以上を占めており、不揮発性メモリのためにもメモリと同等のコストが必要となる。
【０００５】
この他、チェックポイントの取得に関する要素技術については、特許文献１や特許文献２のような技術があるが、何れも反復法(iteration method)の計算に関するものではない。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平７−２７１６２４号公報
【特許文献２】特開平９−２０４３１８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、反復法(iterationmethod)のコンピュータ計算を並列に進めていくにあたって、チェックポイント(Checkpoint)取得を行うこと、および、回復にあたってその取得されたデータを効率的に生かすことにある。
【課題を解決するための手段】
【０００８】
時間発展計算等反復法を繰り返す並列計算中のCheckpoint取得時、各ノードで独立に計算を停止せず、計算と並行してCheckpointを取得する。これによりCheckpoint取得時間中の計算停止が不要となり、計算とCheckpoint取得を同時に行うことが可能になる。計算がI/Oボトルネックで無い場合、Checkpoint取得時間が隠蔽され実行時間が削減される。
【０００９】
その際、Checkpoint取得処理が全ノード（並列計算が進められている非自己ノード）で同一の反復法計算内(時間発展計算のシミュレーション時間における同一時間の計算内)で終了するよう、反復計算の終了時に全ノードでCheckpoint処理の終了を待ち合わせる。
【発明の効果】
【００１０】
この方法では、取得処理中の異なる時点の値を含むCheckpointデータが取得されるが、反復法の収束計算に用途を限定することにより、収束先が初期値に依存しない問題においてCheckpointデータ中の異なる時点の値の混在が許容されることによる。
【図面の簡単な説明】
【００１１】
【図１】図１は、本発明が適用されるところの、基本単位となるノードの構成と、その複数のノードが通信リンクを形成している構成を示す図である。
【図２】図２は、反復法の計算における時間発展と、チェックポイント取得を説明する模式図である。
【図３】図３は、従来の手法と本発明の手法とを比較する図である。
【図４】図４は、チェックポイントの取得手順を示す図である。
【図５】図５は、チェックポイントからの回復手順を示す図である。
【図６】図６は、本発明の手法を実施した場合に予想される、信頼性のためのコストを理論的に算出したグラフである。
【図７】図７は、本発明の手法をPoisson方程式に適用した実施例を示すグラフである。
【発明を実施するための形態】
【００１２】
図１は、本発明が適用されるところの、基本単位となるノードの構成と、その複数のノードが通信リンクを形成している構成を示す図である。本発明では、外部メモリの接続方式、媒体の種類は問わないが、外部メモリには通常NAS/SAN等で結合されたハードディスク等の不揮発性メモリが用いられる。
【００１３】
各ノードは、ＣＰＵ（計算主体）、チェックポイント(Checkpoint)システムおよびメモリを含み、独立してコンピュータ計算を進めることが可能である。図１中では、並列に計算を進めていくところの全ノードのうち、ノード（自己ノード）及び少なくとも１つの他のノード（非自己ノード）が示されており、これら複数のノードが互いに通信できるようにリンクされている。
【００１４】
図２は、反復法の計算における時間発展と、チェックポイント取得を説明する模式図である。何らかの離散時間に属する計算用データグループ（データ配列など）を、ある離散時間（ｔ＝ｋ−１）から、次の離散時間（ｔ＝ｋ）へと時間発展させながら、コンピュータ計算を並列に進めていくというのが、コンピュータ計算（物理現象のシミュレーション等）の基本となる。
【００１５】
計算用データグループは、例えば、Poisson方程式で表現される微分方程式などが、図示のようにｘまたはｙで表現される２次元空間にメッシュのような形式で離散化されており、メッシュの交点（ｘ１，ｙ１）（ｘ２，ｙ１）（ｘ３，ｙ１）・・・の各々において、物理変数が与えられている。コンピュータ計算においては、メッシュの交点の値として計算される新たな値を、時間発展の過程で更新していくことで、メモリ容量を削減している。一般的なプログラミングでは、（メッシュの交点の数×物理変数の種類の数）分を次の離散時間まで記憶しておくための枠として、コンピュータプログラム中の配列などが用いられる。
【００１６】
ある離散時間（ｔ＝ｋ−１）から（収束）計算が開始され、計算結果が所定の範囲に収束するまでは、次の離散時間（ｔ＝ｋ）へは計算を進めない。収束するまで計算が反復的に繰り返されることが、「反復法」という名称の由来になっている。計算結果が収束しているかどうかを判定するための「所定の範囲」については、当業者であれば、様々な閾値判定を導入したり、収束の具合などの状況に応じて適宜、変更したりすることができる。収束の具合などの状況は、時間ｔの離散化の度合い［ここでは（ｋ−１）とｋとの間隔］にも影響してくることが知られている。
【００１７】
本発明においては、反復法の計算を実行している途中の所定のタイミング（時点）において、チェックポイントとしての中間計算データグループを取得する。この取得は、開始したコンピュータ計算を停止（中断）することなく、非同期なＩ／Ｏ（入出力）操作によって行われる。
【００１８】
図３は、従来の手法と本発明の手法とを比較する図である。従来の手法では、計算開始時点のチェックポイントを取得するという、同期Ｉ／Ｏ操作によって行われていた。一方、本発明の手法では、コンピュータ計算を停止（中断）することなく、計算途中のチェックポイントが非同期なＩ／Ｏ（入出力）操作によって取得される。本発明の手法によれば、反復法の計算を実行し続けることができる一方で、所定のタイミング（時点）の異なる時間混合を含むことがある。
【００１９】
このようなことから、自己ノードにおいて、取得したチェックポイントしての中間計算データグループを、外部メモリに記憶しておくことには重要な意義がある。チェックポイントからの回復では、そこからコンピュータ計算を開始するためである。
【００２０】
図４は、チェックポイントの取得手順を示す図である。図１に示したところの、ＣＰＵ（計算主体）と、チェックポイント(Checkpoint)システムとに分けて、それらが協働する態様としての手順を示している。もっとも、当業者であれば、ハードウエア資源としての態様、ソフトウエア資源（コンピュータプログラムなど）としての態様、または、ハードウエア資源とソフトウエア資源とが協働する態様として、この他にも様々なバリエーションをもって本発明を実施することができるであろう。
【００２１】
計算主体は、１０において、収束計算を開始する。２０において、自己ノードのチェックポイントシステムにチェックポイント取得指示を送信する（チェックポイントシステムとの連係）。３０において、収束計算を再開して、同一の収束計算終了まで実行する。４０において、チェックポイントシステムからの終了通知を受信する（チェックポイントシステムとの連係）。５０において、次の離散時間の収束計算のために１０に戻る。
【００２２】
チェックポイントシステムは、６０において、計算主体からチェックポイント取得開始指示を受信する。７０において、メモリの内容を外部メモリに記憶して保存する。８０において、少なくとも１つの他のノード（非自己ノード）との間でのバリア同期等により、次の離散時間へと離散時間を時間発展させる前に、該当する全てのノードにおいて並列に進められているところの前述した全てのステップが完了していることが確認されるのを待つ。
【００２３】
チェックポイントシステムは、９０において、完了が確認されたことに応じて、自己ノードの計算主体にチェックポイント取得終了通知を送信し、それが計算主体の４０において受信される（計算主体との連係）。このことによって、５０において、自己ノードの計算主体は、収束した計算結果を参照して、次の離散時間に属する計算用データグループに基づいたコンピュータ計算を開始する。１００において、次の離散時間の収束計算のために６０に戻る。次の離散時間に時間発展する前に、引続き、異なるタイミング（時点）でのチェックポイントを取得する（ように準備する）ことができる。
【００２４】
図５は、チェックポイントからの回復手順を示す図である。図４と同様に、図１に示したところの、ＣＰＵ（計算主体）と、チェックポイント(Checkpoint)システムとに分けて、それらが協働する態様としての手順を示している。
【００２５】
計算主体は、１１０において、自己ノードのチェックポイントシステムにチェックポイント回復開始指示を送信する（チェックポイントシステムとの連係）。１２０において、チェックポイントシステムからチェックポイント回復終了指示を受信する（チェックポイントシステムとの連係）。１３０において、チェックポイント取得時に実行中であった収束計算の開始時から実行を再開する。
【００２６】
チェックポイントシステムは、１４０において、自己ノードの計算主体からチェックポイント回復開始指示を受信する（計算主体との連係）。１５０において、外部メモリからメモリ内容を回復する。１６０において、少なくとも１つの他のノード（非自己ノード）との間でのバリア同期等により、該当する全てのノードにおいて並列に進められているところの前述した全てのステップが完了していることが確認されるのを待つ。１７０において、自己ノードの計算主体にチェックポイント回復終了通知を送信し、それが計算主体の１２０において受信される。このことによって、１３０において、自己ノードの計算主体は、チェックポイント取得時に実行中であった収束計算の開始時から実行を再開する。
【００２７】
本発明ではチェックポイントの取得時に計算を停止させないため、異なるタイミング（時点）で取得したメモリ内容が混在するデータをチェックポイントからの回復処理時に用いることになる。このようなデータの使用が許される理由は、反復法の収束計算に用途を限定することによる。一般に反復法では解の初期値として、他の方法で計算した近似値、固定値（例えば全て０）もしくは乱数等を用いる。計算においては与えられた初期値を元に、反復ごとに正しい解との差分（残差）がより小さくなるように近似計算を行い、残差が事前に指定された値以下になるまで反復を繰り返す。
【００２８】
本手法ではCheckpointデータ中の異なる時点の値の混在したデータが取得されるが、本発明では収束先が初期値に依存しない問題を想定しているため、初期値によらず同一の値への収束が保障される。つまり、Checkpointデータ中の異なる時点の値の混在したデータを用いても、回復した場合の計算の停止性、計算結果の正当性が保障される。
【００２９】
次に、Checkpointデータ中の異なる時点の値の混在したデータから回復した場合の収束回数について述べる。反復法においては現在の解を反復ごとに正しい解に近づけていくため、一般により正しい解に近い初期値を使用することで少ない反復回数で正しい解に収束させることが可能になる。そのため、本発明のCheckpoint取得方法のようにたとえ取得時点が混在したとしてもより反復が進んだ値を利用することで、より正しい解に近い初期値を得ることができ、それにより回復時における収束までの反復回数が短くなる。
【００３０】
本発明の手法は、ノード、ノードにおいて実行する方法、または、複数のノードにわたってコンピュータ計算を並列に進めていく方法若しくはシステムとして実施することができる。方法の各ステップを、あるノード（自己ノード）に含まれるところの、ＣＰＵ（計算主体）若しくはチェックシステムまたはこれらを一体にしたものに実行させる、コンピュータプログラム、としても実施することができる。
【００３１】
図６は、本発明の手法を実施した場合に予想される、信頼性のためのコストを理論的に算出したグラフである。MTBF0.3日、チェックポイント所要時間10分の場合において、オーバヘッド = Checkpoint取得コスト + 故障による計算時間の喪失コストとして計算した理論値を示す。
【００３２】
ただし、条件として、バックグランドのCheckpoint取得のオーバヘッドにより計算時間が延びることはないものとして計算している。（計算中ＣＰＵ以外の資源の利用がほぼない場合を想定しており。I/O資源使用の場合、その割合に応じて発明の効果は減少する場合もあり得る。）
【００３３】
グラフ中の”Proposed(estimation)”のデータは、本発明を適用した場合のオーバヘッドの理論値を示す。また、それ以外の各データは、Checkpointの取得間隔をそれぞれ、１時間、２時間、６時間、１日とした場合のオーバヘッドを示す。チェックポイント間隔一日、MTBF１０日間の場合、１１．１％であったオーバヘッドを本発明の適用により約０．４％に削減していることに成功している。
【実施例】
【００３４】
図７は、本発明の手法をPoisson方程式に適用した実施例を示すグラフである。
【００３５】
計算の条件を列挙すると、
方程式：    Poisson方程式
計算アルゴリズム：    Gauss-Seidel
入力データ数（=２次元データ配列）：  16384 (=128x128)
Checkpoint取得速度：  32 point / iteration (= Checkpoint取得間隔 512 iteration)
Checkpoint取得終了時点のiteration回数：  500, 1000, 1500
【００３６】
本実施例でも、上記構成及び手順で示したものと同一の方式を用いる。ただし、上記構成中、Checkpointシステムと計算主体を一体として、同一のプログラムとして実現している。以下は、計算開始後、500、1000、1500回目のiterationでCheckpointを取得し、取得したCheckpointから回復した場合の残差を示している。取得までのiteration回数が取得後のiteration回数にどう影響するかを示すために、グラフではCheckpoint取得までのiteration回数から回復後の残差を表示している。
【００３７】
さらに、本発明を応用できる実施例としては、以下の（１）〜（４）を挙げることができる。
（１）BiCG法等反復法による収束計算をベースとし、初期解によらず収束値が確定する計算に適用できる。
（２）CFD、electrostatics、mechanical engineering、theoretical physics、第一原理計算等幅広い分野で用いられるPoisson方程式は初期値によらず収束値が確定することが保証されている計算に適用できる。
（３）初期解によって収束値が異なる計算にも本発明は適用可能である。ただし、本発明を適用しCheckpointから復帰後、元の収束値以外の値に収束すること、もしくは、収束しなくなることも考えられる。初期解によって収束値が異なる計算を含む問題では、本発明の適用により実行結果が変化する可能性がある。この条件を利用者が受容する場合には、本発明を初期解によって収束値が異なる計算に適用できる。
（４）Checkpointの取得の際、非同期Ｉ／Ｏの代わりにRDMA(Remote Direct MemoryAccess)等を用いる非同期通信を用いることも可能である。この場合Checkpointシステムは、自己ノード以外のノード上で動作することとなるが、手順そのものは変わらない。RDMAを用いることで対象ノードのＣＰＵ資源を用いることなくCheckpoint取得が行えるため、Checkpoint取得による収束計算時間（図４の３０）の延びを削減でき、本発明の効果をより高めることができる。
【図１】
0005759203.tif 000002
【図２】
0005759203.tif 000003
【図３】
0005759203.tif 000004
【図４】
0005759203.tif 000005
【図５】
0005759203.tif 000006
【図６】
0005759203.tif 000007
【図７】
0005759203.tif 000008