(57)【特許請求の範囲】
【請求項１】
Ｏｐｔｉｍｉｓｔｉｃ法を用いて、将来時刻における観測対象の位置を仮説として推定する模擬処理を実行するとともに、定期的に入力される前記観測対象の観測情報に基づいて、前記仮説を評価し、矛盾する前記仮説を取り消す分散シミュレーションシステムであって、
シミュレーション時間軸上のシミュレーション周期の時刻毎に、前記仮説として推定される観測対象の位置が複数存在する仮説模擬処理を並列に実行する複数のフェデレートを備え、
前記複数のフェデレートは、それぞれ前記シミュレーション周期の時刻毎の前記仮説模擬処理をタスクとし、シミュレーション時間軸上の、前記シミュレーション周期よりも長いチャンク周期に応じて、複数の前記タスクをチャンクとして前記仮説模擬処理を並列に実行するとともに、実時間軸上の前記観測情報の入力周期を前記チャンク周期と一致させる
ことを特徴とする分散シミュレーションシステム。
【請求項２】
前記複数のフェデレートは、前記観測情報が入力された時点で、観測時刻までの前記仮説模擬処理のすべてが完了していない場合には、前記観測時刻までの前記仮説模擬処理がすべて完了するまで前記チャンクを実行し、前記観測情報による前記仮説の評価を待たせる
ことを特徴とする請求項１に記載の分散シミュレーションシステム。
【請求項３】
前記複数のフェデレートは、前記観測情報が入力された時点で、観測時刻までの前記仮説模擬処理のすべてが完了していない場合には、それまでに実行した前記仮説模擬処理をすべて取り消して、入力された前記観測情報に基づいて、新たに前記仮説模擬処理を実行する
ことを特徴とする請求項１に記載の分散シミュレーションシステム。
【請求項４】
前記複数のフェデレートは、
すでに実行した前記チャンクの処理時間を記録して統計処理を行うことで、前記チャンクの処理時間の推定値を求め、
前記観測情報が入力された時点で、観測時刻までの前記仮説模擬処理のすべてが完了していない場合には、前記観測時刻までの前記仮説模擬処理がすべて完了するまでに実行しなければならない前記チャンクの数と、前記チャンクの処理時間の推定値とに基づいて、前記観測時刻までの前記仮説模擬処理がすべて完了するまで前記チャンクを実行するのに必要な総チャンク実行時間を推定し、
前記総チャンク実行時間が、次の前記観測情報が入力されるまでの時間よりも短ければ、前記観測時刻までの前記仮説模擬処理がすべて完了するまで前記チャンクを実行し、前記観測情報による前記仮説の評価を待たせ、
前記総チャンク実行時間が、次の前記観測情報が入力されるまでの時間よりも長ければ、それまでに実行した前記仮説模擬処理をすべて取り消して、入力された前記観測情報に基づいて、新たに前記仮説模擬処理を実行する
ことを特徴とする請求項１に記載の分散シミュレーションシステム。
【請求項５】
Ｏｐｔｉｍｉｓｔｉｃ法を用いて、将来時刻における観測対象の位置を仮説として推定する模擬処理を実行するとともに、定期的に入力される前記観測対象の観測情報に基づいて、前記仮説を評価し、矛盾する前記仮説を取り消す、コンピュータによって実行される分散シミュレーション方法であって、
シミュレーション時間軸上のシミュレーション周期の時刻毎に、前記仮説として推定される観測対象の位置が複数存在する仮説模擬処理を並列に実行する仮説模擬処理ステップを備え、
前記仮説模擬処理ステップは、
前記シミュレーション周期の時刻毎の前記仮説模擬処理をタスクとし、シミュレーション時間軸上の、前記シミュレーション周期よりも長いチャンク周期に応じて、複数の前記タスクをチャンクとして前記仮説模擬処理を並列に実行するステップと、
実時間軸上の前記観測情報の入力周期を前記チャンク周期と一致させるステップと、
を有することを特徴とする分散シミュレーション方法。
【請求項６】
前記仮説模擬処理ステップは、前記観測情報が入力された時点で、観測時刻までの前記仮説模擬処理のすべてが完了していない場合に、前記観測時刻までの前記仮説模擬処理がすべて完了するまでチャンクを実行し、前記観測情報による前記仮説の評価を待たせるステップをさらに有する
ことを特徴とする請求項５に記載の分散シミュレーション方法。
【請求項７】
前記仮説模擬処理ステップは、前記観測情報が入力された時点で、観測時刻までの前記仮説模擬処理のすべてが完了していない場合に、それまでに実行した前記仮説模擬処理をすべて取り消して、入力された前記観測情報に基づいて、新たに前記仮説模擬処理を実行するステップをさらに有する
ことを特徴とする請求項５に記載の分散シミュレーション方法。
【請求項８】
前記仮説模擬処理ステップは、
すでに実行した前記チャンクの処理時間を記録して統計処理を行うことで、前記チャンクの処理時間の推定値を求めるステップと、
前記観測情報が入力された時点で、観測時刻までの前記仮説模擬処理のすべてが完了していない場合に、前記観測時刻までの前記仮説模擬処理がすべて完了するまでに実行しなければならない前記チャンクの数と、前記チャンクの処理時間の推定値とに基づいて、前記観測時刻までの前記仮説模擬処理がすべて完了するまで前記チャンクを実行するのに必要な総チャンク実行時間を推定するステップと、
前記総チャンク実行時間が、次の前記観測情報が入力されるまでの時間よりも短ければ、前記観測時刻までの前記仮説模擬処理がすべて完了するまで前記チャンクを実行し、前記観測情報による前記仮説の評価を待たせるステップと、
前記総チャンク実行時間が、次の前記観測情報が入力されるまでの時間よりも長ければ、それまでに実行した前記仮説模擬処理をすべて取り消して、入力された前記観測情報に基づいて、新たに前記仮説模擬処理を実行するステップと、をさらに有する
ことを特徴とする請求項５に記載の分散シミュレーション方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、Ｏｐｔｉｍｉｓｔｉｃ法を用いて将来時刻の観測対象の位置をシミュレーションする分散シミュレーションシステムおよび分散シミュレーション方法に関する。
【背景技術】
【０００２】
従来から、Ｏｐｔｉｍｉｓｔｉｃ法を用いた分散シミュレーションシステムとして、米軍を中心に標準化された分散シミュレーションシステムのアーキテクチャであるＨＬＡ（Ｈｉｇｈ  Ｌｅｖｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ）が知られている（例えば、非特許文献１参照）。以下、図面を参照しながら、非特許文献１に示された分散シミュレーションシステムについて説明する。
【０００３】
図２は、非特許文献１に示されたＨＬＡによる分散シミュレーションシステムを示すブロック構成図である。図２において、この分散シミュレーションシステムは、フェデレーション１０１と、フェデレーション１０１に含まれる複数のフェデレート（第１、第２、・・・、第ｎフェデレート）１０２と、分散シミュレーション基盤であるＲＴＩ（Ｒｕｎ−Ｔｉｍｅ  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ）１０３とを備えている。
【０００４】
フェデレーション１０１は、シミュレーションシステム全体を示す。複数のフェデレート１０２は、分散して並列に実行される模擬処理等のプログラムである。ＲＴＩ１０３は、シミュレーションの実行中に行われるフェデレーション１０１全体の実行制御や、フェデレート１０２間のデータ交換等の共通機能を提供する。
【０００５】
図３は、図２に示した分散シミュレーションシステムにおける、Ｏｐｔｉｍｉｓｔｉｃ法によるフェデレート１０２のシミュレーション時刻進行の例を示す説明図である。ここでは、第１フェデレートおよび第２フェデレートのみを示している。図３において、第１、第２フェデレートは、それぞれシミュレーション時刻における模擬処理を実行するが、その際に、将来のシミュレーション時刻における模擬処理を行うこともできる。なお、将来のシミュレーション時刻の模擬処理を、未だ確定しておらず、取り消される可能性があることから、仮説と呼ぶこととする。
【０００６】
具体的には、図３の例において、第１フェデレートは、時刻ｔ０において、時刻ｔ０よりも将来の時刻における仮説を実行し、その結果として、時刻ｔｘにおけるイベントｅｖ（ｔｘ）を第２フェデレートに送信する。Ｏｐｔｉｍｉｓｔｉｃ法では、フェデレート１０２は、それぞれ自身のシミュレーション時刻よりも将来の時刻におけるイベントを、任意のタイミングで受信することができる。
【０００７】
そのため、第２フェデレートは、時刻ｔ０において、将来イベントであるイベントｅｖ（ｔｘ）を受信し、イベントｅｖ（ｔｘ）に基づく時刻ｔｘの仮説を実行することができる。また、第２フェデレートは、時刻ｔｘにおける仮説の結果として、時刻ｔｙにおけるイベントｅｖ（ｔｙ）を、第１フェデレートに送信する。また、第１フェデレートは、時刻ｔ０において、イベントｅｖ（ｔｙ）に基づく時刻ｔｙの仮説を実行することができる。
【０００８】
図４は、図３に示したフェデレート１０２のシミュレーション時刻進行において、時刻ｔｘに進んだ際の模擬処理を示す説明図である。図４において、第２フェデレートは、図３に示したように、時刻ｔ０において、時刻ｔｘの仮説を実行していたので、時刻ｔｘに進んだ際には、時刻ｔｘの仮説の評価を行い、仮説が誤りであった場合には、その仮説を取り消した後に、時刻ｔｘの模擬処理を実行する。
【０００９】
具体的には、図４に示した処理フローに基づいて、まず、イベントｅｖ（ｔｘ）に基づく仮説の評価を行う。ここで、仮説が誤りであった場合には、その仮説を取り消した後に、時刻ｔｘの模擬処理を実行する。一方、仮説が誤りでなかった場合には、そのまま時刻ｔｘの模擬処理を実行する。
【００１０】
図５は、図４の処理フローにおいて、仮説が誤りであったために、仮説が取り消された場合のイベント取り消しの例を示す説明図である。図５において、第２フェデレートの時刻ｔｘにおいて、以前の時刻ｔ０で実行した時刻ｔｘの仮説が誤りであったことが判明したため、仮説が取り消された結果、その仮説に基づいて、第１フェデレートに送信されていたイベントｅｖ（ｔｙ）についても、取り消し処理が行われる。
【００１１】
このとき、イベントｅｖ（ｔｙ）の取り消しは、イベント送信先の第１フェデレートに対して通知され、第１フェデレートでは、時刻ｔ０における、イベントｅｖ（ｔｙ）に基づく時刻ｔｙの仮説の取り消し処理が行われる。なお、図３〜５におけるフェデレート１０２のシミュレーション時刻の進行制御およびイベントの通信処理は、ＲＴＩ１０３によって管理される。
【００１２】
以上のように、Ｏｐｔｉｍｉｓｔｉｃ法では、フェデレート１０２は、シミュレーションにおける現在時刻よりも将来の時刻の模擬処理を仮説として実行し、さらに仮説によって発生した将来イベントの送受信によって、仮説の実行を進めていくことができる。また、シミュレーション時刻が進行した際に仮説の評価が行われ、仮説が誤りであった場合には、仮説の取り消しおよびイベントの取り消しの連鎖が発生する。
【００１３】
また、Ｏｐｔｉｍｉｓｔｉｃ法を用いた分散シミュレーションシステムとして、シミュレーション時刻進行によって多数の仮説を投機的にシミュレーション実行する複数の仮説模擬処理を、複数の演算装置に分散して並列に実行し、全体を分散シミュレーション基盤が実行制御するものが知られている（例えば、非特許文献２参照）。
【００１４】
非特許文献２に示された分散シミュレーションシステムでは、ＨＬＡと同様のシステム構成において、実時間における現在時刻よりも将来の状況について、Ｏｐｔｉｍｉｓｔｉｃ法により、予測的に仮説として模擬処理を実行する。また、この分散シミュレーションシステムでは、実世界の観測情報を取り入れることによって仮説を評価し、実世界の状況に対して誤った仮説を取り消すことにより、リアルタイムに予測状況を修正することを特徴とする。
【００１５】
図６は、非特許文献２に示された分散シミュレーションシステムにおける処理の概念を示す説明図である。図６において、この分散シミュレーションシステムにおける処理は、予測フェーズと評価フェーズとの繰り返しによって実行される。ここで、Ｘｐ（ｔｉ）は、時刻ｔｉにおける仮説の実行結果を示し、Ｘｍ（ｔｉ）は、時刻ｔｉにおける実世界の観測情報を示している。また、評価フェーズは、仮説を評価するフェーズであり、ここでは、Ｘｐ（ｔｉ）がＸｍ（ｔｉ）を基準として評価され、評価結果としてＸｅ（ｔｉ）が出力される。
【００１６】
予測フェーズは、Ｏｐｔｉｍｉｓｔｉｃ法による将来時刻の仮説を実行するフェーズであり、ここでは、Ｘｅ（ｔｉ）を入力として、時刻ｔｉ＋１までの将来時刻の仮説が実行され、仮説の実行結果としてＸｐ（ｔｉ＋１）が出力される。なお、Ｘｐ（ｔｉ＋１）は、次に実世界の観測情報が入力された時刻に始まる評価フェーズにおいて評価される。
【００１７】
図７は、図６に示した予測フェーズと評価フェーズとの繰り返しを具体例で示す説明図である。図７において、仮説模擬処理部１および仮説模擬処理部２は、Ｏｐｔｉｍｉｓｔｉｃ法によって、将来時刻における仮説の実行と仮説の評価とを行う処理部であり、図２に示したフェデレートの一種である。また、観測情報処理部は、実世界の観測情報を仮説模擬処理部に反映するための処理部であり、これも図２に示したフェデレートの一種である。なお、図７では、図６の予測フェーズから説明を始めるために、時刻ｔｉ−１から図示している。
【００１８】
図７の予測フェーズでは、実時間における将来時刻の仮説を、複数の仮説模擬処理部が、Ｏｐｔｉｍｉｓｔｉｃ法によって並列に実行する。ここで、将来時刻とは、時刻ｔｉ−１よりも未来の時刻のことである。なお、予測フェーズは、観測情報処理部が実世界の観測情報を送信し、シミュレーション時刻を進めるまで実行される。
【００１９】
予測フェーズに続いて、評価フェーズが実行される。評価フェーズは、観測情報処理部が時刻ｔｉの観測情報を仮説模擬処理部に送信し、シミュレーション時刻を時刻ｔｉに進めたタイミングで開始される。シミュレーション時刻が時刻ｔｉに進んだことにより、仮説模擬処理部において、仮説の評価が実行される。
【００２０】
仮説の評価は、時刻ｔｉにおける仮説の実行結果と、観測情報処理部から送信された時刻ｔｉの観測情報との比較によって行われる。これにより、時刻ｔｉの観測情報と矛盾する仮説は、評価フェーズにおいて取り消される。
【００２１】
すべての仮説の評価が完了すると、評価フェーズは終了し、続いて予測フェーズが実行され、取り消されなかった仮説と、必要に応じて時刻ｔｉの観測情報から新たに生成される仮説とに基づいて、時刻ｔｉよりも将来の時刻における仮説模擬処理が実行される。
【先行技術文献】
【非特許文献】
【００２２】
【非特許文献１】“ＩＥＥＥ  Ｓｔａｎｄａｒｄ  ｆｏｒ  Ｍｏｄｅｌｉｎｇ  ａｎｄ  Ｓｉｍｕｌａｔｉｏｎ（Ｍ＆Ｓ）  Ｈｉｇｈ  Ｌｅｖｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ（ＨＬＡ）−Ｆｅｄｅｒａｔｅ  Ｉｎｔｅｒｆａｃｅ  Ｓｐｅｃｉｆｉｃａｔｉｏｎ”，ＩＥＥＥ  Ｓｔｄ  １５１６．１−２０００
【非特許文献２】Ｊｅｆｆｒｅｙ  Ｓ．Ｓｔｅｉｎｍａｎ，ｅｔ  ａｌ．，“Ｓｉｍｕｌａｔｉｎｇ  Ｐａｒａｌｌｅｌ  Ｏｖｅｒｌａｐｐｉｎｇ  Ｕｎｉｖｅｒｓｅｓ  ｉｎ  ｔｈｅ  Ｆｉｆｔｈ  Ｄｉｍｅｎｓｉｏｎ  ｗｉｔｈ  ＨｙｐｅｒＷａｒｐＳｐｅｅｄ  Ｉｍｐｌｅｍｅｎｔｅｄ  ｉｎ  ｔｈｅ  ＷａｒｐＩＶ  Ｋｅｒｎｅｌ”，Ｓｉｍｕｌａｔｉｏｎ  Ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ  Ｗｏｒｋｓｈｏｐ，Ｐａｐｅｒ  ０８Ｓ−ＳＩＷ−０２５，Ｓｐｒｉｎｇ  ２００８
【非特許文献３】Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｐａｒａｌｌｅｌ  Ｃｏｍｐｕｔｉｎｇ，ｈｔｔｐｓ：／／ｃｏｍｐｕｔｉｎｇ．ｌｌｎｌ．ｇｏｖ／ｔｕｔｏｒｉａｌｓ／ｐａｒａｌｌｅｌ＿ｃｏｍｐ／
【非特許文献４】Ｍｅｎｌｏ  Ｐａｒｋ，“Ｇｅｔｔｉｎｇ  ＯｐｅｎＭＰ  Ｕｐ  Ｔｏ  Ｓｐｅｅｄ”，ＩＷＯＭＰ  ２０１０，ｈｔｔｐ：／／ｗｗｗ．ｃｏｍｐｕｎｉｔｙ．ｏｒｇ／ｔｒａｉｎｉｎｇ／ｔｕｔｏｒｉａｌｓ／４％２０ＯｐｅｎＭＰ＿ａｎｄ＿Ｐｅｒｆｏｒｍａｎｃｅ．ｐｄｆ
【発明の概要】
【発明が解決しようとする課題】
【００２３】
しかしながら、従来技術には、以下のような課題がある。
非特許文献２に示したような、予測フェーズと評価フェーズとを繰り返して実行するシステムにおいて、観測対象の将来時刻における位置を予測する場合、予測結果は、実時間において予測時刻に達する前に得られなければならない。
【００２４】
すなわち、仮説模擬処理を開始した時刻を時刻ｔ０とし、予測時刻を時刻ｔｚとすると、仮説模擬処理は、少なくとも（ｔｘ−ｔ０）時間以内に実行されなければならない。そのため、このようなシステムでは、仮説模擬処理における予測フェーズおよび評価フェーズの高速化が必要であり、特に多数の仮説模擬処理部を用いた並列処理の効率化が課題となる。
【００２５】
このような課題を具体的に説明するために、まず、仮説模擬処理において、多数の仮説が並列に処理される例を示し、次に、一般的な並列処理の効率化手法の適用方式の説明と、その方式における問題点とを示す。
【００２６】
図８は、ある観測対象の将来時刻における位置を、観測情報に基づいて、離散的に仮説として模擬処理を実行する例を示す説明図である。図８では、時刻毎に仮説の位置が変化し、また別の仮説が派生する様子をグラフ化して示している。図８において、横軸は時間の進行を示し、縦軸は仮説の位置の差異を１次元で例示し、白丸（○）はその時刻における仮説の１つの位置を示している。
【００２７】
また、白丸（○）から次の時刻の白丸（○）に引かれた矢印線（→）は、ある時刻の仮説の位置に基づいて、シミュレーション周期であるδｔ時間後（次の時刻）における仮説の位置が、仮説模擬処理によって導き出されていることを示している。
【００２８】
図８に示した例では、仮説模擬処理を開始した時刻ｔ０の位置を親として、仮説模擬処理が実行される時刻毎に仮説が２つに分岐しており、時刻ｔ０の時点では仮説数が１であったのに対して、時刻ｔ３の時点では、仮説数が８に増加している。なお、図８は、仮説の位置の遷移を概念的に示したものであり、具体的な仮説の実行は、複数の仮説模擬処理部において並列に実行される。
【００２９】
図９は、図８に示した例において、時刻ｔ２の観測情報が入力された例を示す説明図である。図９において、黒丸（●）は、時刻ｔ２における観測対象の位置を示している。時刻ｔ２の観測情報が入力されると、Ｏｐｔｉｍｉｓｔｉｃ法によるシミュレーション時刻進行が行われ、シミュレーション時刻が時刻ｔ２に進むとともに、評価フェーズが実行される。
【００３０】
図９に示した例では、時刻ｔ２における仮説の位置に対して誤差範囲を設定し、時刻ｔ２の誤差範囲内に観測対象の位置が収まっている仮説以外の仮説を、観測情報と矛盾すると判断する。
【００３１】
図１０は、図９の評価フェーズにおいて、観測情報と矛盾すると判断された仮説と、その仮説の子孫となる仮説とが、取り消される例を示す説明図である。図１０において、時刻ｔ２の観測情報と矛盾していると判断された仮説と、シミュレーション時刻進行によって、その仮説に基づいて派生した仮説とが取り消される（図中の×）。ここで、図８〜１０のように実行される観測対象の将来予測を高速化するためには、仮説模擬処理の並列処理を効率化する必要がある。
【００３２】
図１１は、一般的な並列処理の効率化手法を示す説明図である。図１１では、ある時刻における仮説の位置から、シミュレーション周期δｔ後の位置を予測する処理１つを１つのタスクとし、そのまま１つの仮説模擬処理部に処理を割り当てる例を示している。図１１において、一点鎖線の三角形で囲まれた部分が１つのタスクを示しており、時刻が進む毎に、指数的に増加するタスクが、順次仮説模擬処理部に割り当てられる。
【００３３】
仮説模擬処理部では、割り当てられたタスクをスレッドとしてＣＰＵで処理するが、図１１の例では、１つのタスクが１つのスレッドとして実行されるので、ＣＰＵの数に応じて決まるスレッド数に対して、タスクの数が非常に多くなる。
【００３４】
このような場合には、タスク全体の処理時間に対して、スレッドの切り替え等に要する逐次処理時間コストの割合が高くなるので、並列処理におけるアムダールの法則により、スレッド数を増やしても、大きな並列効果を得ることができないという問題がある。
【００３５】
次に、この問題点を解決するための一般的な手法と、その手法を用いた際に新たに発生する問題点とについて説明する。
【００３６】
スレッド数に対してタスク数が多すぎる場合において、処理性能を向上させるための手法として、ＯｐｅｎＭＰなどの一般的に用いられる並列計算ライブラリでは、複数のタスクをまとめることによって処理の粒度を大きくし、タスク全体の処理時間に対する逐次処理時間コストの割合を抑制する「チャンク」が用いられている（例えば、非特許文献３、４参照）。
【００３７】
図１２は、図８に示した例に対して、チャンクによってタスク粒度を大きくした例を示す説明図である。図１２において、図８に示した観測対象の将来予測は、前時刻における仮説の位置に基づいて、次時刻における仮説の位置を模擬するものなので、図８の複数のタスクをまとめるためには、シミュレーション周期δｔ以上となるチャンク周期であるΔｔ時間後までのタスクをまとめることになる。
【００３８】
図１２に示した例では、チャンク周期Δｔの値が、シミュレーション周期δｔの三倍であり、図中の一点鎖線の三角形で囲まれた７つのタスクが１つにまとめられてスレッドに割り当てられる（チャンクサイズが７）。そのため、図１１に示した例と比べて、スレッドの切り替え等に要する逐次処理時間コストが、理想的には１／７となり、タスク全体の処理時間に対する逐次処理時間の割合を減らすことができる。
【００３９】
ここで、予測フェーズでは、時刻が進む毎に、タスク数が指数的に増加するので、時刻を進めている間、無限にタスクが存在すると考えると、上述したチャンクを用いる手法によれば、逐次処理時間の割合を減らすために、チャンクサイズをいくら大きくしても問題がないように思われる。しかしながら、このシステムは、観測情報に基づいて、リアルタイムで観測対象の将来時刻における位置を予測するものであり、チャンクサイズが大きすぎると、評価フェーズの処理において、以下の問題が発生する。
【００４０】
図１３は、図１２に示した例において、チャンクサイズが大きすぎる場合の問題を説明するための説明図である。図１３では、チャンクサイズが大きく、１つのチャンクの処理に時間がかかったために、評価フェーズにおいて観測情報が入力された際に、観測時刻における仮説模擬処理が完了していない状況を例示している。
【００４１】
図１３において、時刻ｔ４が観測情報の観測時刻であり、黒丸（●）は観測情報の位置を示している。図１３の状況では、本来図９、１０で示したように、仮説の評価と、観測情報と矛盾する仮説の取り消しとが行われるが、この段階では、未だ時刻ｔ４のすべての仮説模擬処理が完了していないので、このままでは、評価フェーズが実行された後に、時刻ｔ４における仮説模擬処理が実行されることとなる。
【００４２】
図１４は、図１２に示した例において、時刻ｔ４の観測情報によって仮説の評価が行われた後に、時刻ｔ４における仮説模擬処理が実行された場合の例を示す説明図である。図１３において、１１１、１１２、１１３が、仮説の評価後に実行される仮説模擬処理を示しており、時刻ｔ４の観測情報と矛盾する仮説が実行されていることが分かる。
【００４３】
このように、チャンクサイズが大きすぎる場合には、１つのチャンクの処理に時間がかかり、評価フェーズにおいて観測情報が入力された際に、観測時刻における仮説模擬処理が完了していない状況が発生する。
【００４４】
そのため、本来であれば、観測情報と矛盾するとして取り消されるはずの仮説について模擬処理が後から実行され、評価フェーズ後にも不要な仮説について模擬処理が実行されるという問題がある。すなわち、チャンクサイズが大きすぎる場合には、無駄な仮説模擬処理が実行される恐れがある。
【００４５】
この発明は、上記のような課題を解決するためになされたものであり、チャンクを用いる並列処理において、無駄な仮説模擬処理が実行されることを抑制することができる分散シミュレーションシステムおよび分散シミュレーション方法を得ることを目的とする。
【課題を解決するための手段】
【００４６】
この発明に係る分散シミュレーションシステムは、Ｏｐｔｉｍｉｓｔｉｃ法を用いて、将来時刻における観測対象の位置を仮説として推定する模擬処理を実行するとともに、定期的に入力される観測対象の観測情報に基づいて、仮説を評価し、矛盾する仮説を取り消す分散シミュレーションシステムであって、シミュレーション時間軸上のシミュレーション周期の時刻毎に、仮説として推定される観測対象の位置が複数存在する仮説模擬処理を並列に実行する複数のフェデレートを備え、複数のフェデレートは、それぞれシミュレーション周期の時刻毎の仮説模擬処理をタスクとし、シミュレーション時間軸上の、シミュレーション周期よりも長いチャンク周期に応じて、複数のタスクをチャンクとして仮説模擬処理を並列に実行するとともに、実時間軸上の観測情報の入力周期をチャンク周期と一致させるものである。
【００４７】
この発明に係る分散シミュレーション方法は、Ｏｐｔｉｍｉｓｔｉｃ法を用いて、将来時刻における観測対象の位置を仮説として推定する模擬処理を実行するとともに、定期的に入力される観測対象の観測情報に基づいて、仮説を評価し、矛盾する仮説を取り消す、コンピュータによって実行される分散シミュレーション方法であって、シミュレーション時間軸上のシミュレーション周期の時刻毎に、仮説として推定される観測対象の位置が複数存在する仮説模擬処理を並列に実行する仮説模擬処理ステップを備え、仮説模擬処理ステップは、シミュレーション周期の時刻毎の仮説模擬処理をタスクとし、シミュレーション時間軸上の、シミュレーション周期よりも長いチャンク周期に応じて、複数のタスクをチャンクとして仮説模擬処理を並列に実行するステップと、実時間軸上の観測情報の入力周期をチャンク周期と一致させるステップと、を有するものである。
【発明の効果】
【００４８】
この発明に係る分散シミュレーションシステムおよび分散シミュレーション方法によれば、シミュレーション周期の時刻毎に、観測対象の仮説が分岐する仮説模擬処理を並列に実行する複数のフェデレートは、それぞれシミュレーション周期の時刻毎の仮説模擬処理をタスクとし、シミュレーション周期よりも長いチャンク周期に応じて、複数のタスクをチャンクとしてまとめて仮説模擬処理を並列に実行するとともに、チャンク周期を、観測情報の入力周期と一致させる。
そのため、チャンクを用いる並列処理において、無駄な仮説模擬処理が実行されることを抑制することができる。
【図面の簡単な説明】
【００４９】
【図１】この発明の実施の形態１に係る分散シミュレーションシステムを示すブロック構成図である。
【図２】非特許文献１に示されたＨＬＡによる分散シミュレーションシステムを示すブロック構成図である。
【図３】図２に示した分散シミュレーションシステムにおける、Ｏｐｔｉｍｉｓｔｉｃ法によるフェデレートのシミュレーション時刻進行の例を示す説明図である。
【図４】図３に示したフェデレートのシミュレーション時刻進行において、時刻ｔｘに進んだ際の処理を示す説明図である。
【図５】図４の処理フローにおいて、仮説が誤りであったために、仮説が取り消された場合のイベント取り消しの例を示す説明図である。
【図６】非特許文献２に示された分散シミュレーションシステムにおける処理の概念を示す説明図である。
【図７】図６に示した予測フェーズと評価フェーズとの繰り返しを具体例で示す説明図である。
【図８】ある観測対象の将来時刻における位置を、観測情報に基づいて、離散的に仮説として模擬処理を実行する例を示す説明図である。
【図９】図８に示した例において、時刻ｔ２の観測情報が入力された例を示す説明図である。
【図１０】図９の評価フェーズにおいて、観測情報と矛盾すると判断された仮説と、その仮説の子孫となる仮説とが、取り消される例を示す説明図である。
【図１１】一般的な並列処理の効率化手法を示す説明図である。
【図１２】図８に示した例に対して、チャンクによってタスク粒度を大きくした例を示す説明図である。
【図１３】図１２に示した例において、チャンクサイズが大きすぎる場合の問題を説明するための説明図である。
【図１４】図１２に示した例において、時刻ｔ４の観測情報によって仮説の評価が行われた後に、時刻ｔ４における仮説模擬処理が実行された場合の例を示す説明図である。
【発明を実施するための形態】
【００５０】
以下、この発明に係る分散シミュレーションシステムおよび分散シミュレーション方法の好適な実施の形態につき図面を用いて説明するが、各図において同一、または相当する部分については、同一符号を付して説明する。
【００５１】
実施の形態１．
図１は、この発明の実施の形態１に係る分散シミュレーションシステムを示すブロック構成図である。この分散シミュレーションシステムは、非特許文献２に示したものと同様に、Ｏｐｔｉｍｉｓｔｉｃ法を用いて、将来時刻の観測対象の位置を仮説として模擬処理を実行するとともに、定期的に入力される観測対象の観測情報に基づいて、仮説を評価し、矛盾する仮説を取り消すものである。
【００５２】
図１において、この分散シミュレーションシステムは、フェデレーション１と、フェデレーション１に含まれる複数のフェデレート（第１、第２、・・・、第ｎフェデレート）２と、分散シミュレーション基盤であるＲＴＩ３とを備えている。
【００５３】
フェデレーション１は、シミュレーションシステム全体を示す。複数のフェデレート２は、分散して並列に実行される仮説模擬処理等のプログラムである。ＲＴＩ３は、シミュレーションの実行中に行われるフェデレーション１全体の実行制御や、フェデレート２間のデータ交換等の共通機能を提供する。
【００５４】
ここで、複数のフェデレート２は、シミュレーション周期の時刻毎に、観測対象の仮説が分岐する仮説模擬処理を並列に実行する。また、複数のフェデレート２は、それぞれシミュレーション周期の時刻毎の仮説模擬処理をタスクとし、シミュレーション周期よりも長いチャンク周期に応じて、複数のタスクをチャンクとしてまとめて仮説模擬処理を並列に実行するとともに、チャンク周期を、観測情報の入力周期と一致させる。
【００５５】
具体的には、チャンクされたタスクのチャンクサイズＴは、時刻毎の仮説の分岐数ｓ、シミュレーション周期δｔの値、およびチャンク周期Δｔの値に基づいて、次式で表される。
【００５６】
Ｔ＝ｓ＾０＋ｓ＾１＋ｓ＾２＋…＋ｓ＾ＲＯＵＮＤＤＯＷＮ（Δｔ／δｔ）
【００５７】
なお、時刻毎の仮説の分岐数ｓおよびシミュレーション周期δｔの値は、観測対象のシミュレーションモデルによって決定される値であり、変更するとシミュレーション実行結果に影響を与えるので、並列処理の効率化のために変更するには適さない。そのため、並列処理の効率化のために、シミュレーション実行結果に影響を与えないチャンク周期Δｔの値を動的に変更することにより、チャンクサイズＴを調整する。
【００５８】
そこで、複数のフェデレート２は、次のルールに従い、チャンクされたタスクのチャンクサイズＴを決定するチャンク周期Δｔの値を、シミュレーション実行中に動的に制御する。
【００５９】
ＩＦ（スレッド数≧タスク数）
Δｔ＝δｔ
ＥＬＳＥ
Δｔ＝観測情報の入力周期
【００６０】
すなわち、タスク数は、観測対象のシミュレーションを開始した時点である時刻ｔ０においては１であり、時刻が進むに従い指数的に増加する。そのため、シミュレーションを開始した後で、タスク数がスレッド数を超えないうちは、複数のフェデレート２は、チャンク周期Δｔの値をシミュレーション周期δｔと一致させてチャンクを抑制し、時刻が進んでタスク数がスレッド数を超えた時点からチャンクを開始する。
【００６１】
続いて、チャンクを開始したならば、複数のフェデレート２は、チャンク周期Δｔの値を、観測情報の入力周期と一致させることにより、チャンクの開始点となる時刻が、観測情報の時刻と一致するように調整する。この制御により、チャンクされるタスクの最大時刻が、次に観測情報が入力される時刻を越すことがなくなるので、チャンクサイズＴが大きくなりすぎることを防ぐことができる。
【００６２】
なお、観測情報の入力周期は、本システムに直接あるいは間接的に接続されるセンサシステムの諸元（例えば、回転式レーダシステムの場合、単位時間あたりの回転数が観測情報の入力周期に相当する）から得る方法や、あるいは過去の観測情報の入力時刻を記録し、その結果を統計的に解析して算出する方法等がある。
【００６３】
以上のように、実施の形態１によれば、シミュレーション周期の時刻毎に、観測対象の仮説が分岐する仮説模擬処理を並列に実行する複数のフェデレートは、それぞれシミュレーション周期の時刻毎の仮説模擬処理をタスクとし、シミュレーション周期よりも長いチャンク周期に応じて、複数のタスクをチャンクとしてまとめて仮説模擬処理を並列に実行するとともに、チャンク周期を、観測情報の入力周期と一致させる。
そのため、チャンクを用いる並列処理において、無駄な仮説模擬処理が実行されることを抑制することができる。
【００６４】
実施の形態２．
上記実施の形態１では、チャンクサイズＴを決定するチャンク周期Δｔの値を、観測情報の入力周期と一致させることにより、チャンクサイズＴが大きくなりすぎることを防ぐことができる。しかしながら、評価フェーズにおいて観測情報が入力された際に、観測時刻の仮説模擬処理が完了することを保証することはできない。
【００６５】
そこで、複数のフェデレート２は、観測情報が入力された際に、未だ実行されていないチャンクの開始時刻を調べ、観測時刻よりも前の開始時刻のチャンクが未だ実行されていなければ、それらのチャンクの実行が完了するまで、評価フェーズの処理開始を待たせる。これにより、観測時刻の仮説模擬処理が、評価フェーズの処理開始までに完了することを保証することができる。
【００６６】
以上のように、実施の形態２によれば、上記実施の形態１に加え、観測情報が入力された時点で、観測時刻までの仮説模擬処理のすべてが完了していない場合には、観測時刻までの仮説模擬処理がすべて完了してから仮説の評価を開始することにより、取り消されていたはずの仮説模擬処理が後から実行されることを防ぐことができる。
【００６７】
実施の形態３．
上記実施の形態２では、観測情報の観測時刻よりも前の開始時刻におけるチャンクの実行が完了するまで、評価フェーズの処理開始を待たせることにより、観測時刻の仮説模擬処理が、評価フェーズの処理開始までに完了することを保証する。
【００６８】
しかしながら、これから実行されるチャンクにおいて処理しなければならないタスク数が非常に多い場合等に、チャンクの実行に時間がかかってしまうと、評価フェーズを開始する前に、次の観測情報が入力されることにより、処理が追いつかなくなるという問題が発生する。
【００６９】
そこで、複数のフェデレート２は、観測情報が入力された際に、未だ実行されていないチャンクの開始時刻を調べ、観測時刻よりも前の開始時刻のチャンクが未だ実行されていなければ、それまでに実行した仮設模擬処理をすべて取り消して、入力された観測情報に基づいて、新たに仮説模擬処理を実行する。これにより、少ないタスクから将来予測をやり直すことで、観測対象の将来時刻の予測が追いつかなくなることを防止することができる。
【００７０】
以上のように、実施の形態３によれば、上記実施の形態１に加え、観測情報が入力された時点で、観測時刻までの仮説模擬処理のすべてが完了していない場合には、それまでに実行した仮説模擬処理をすべて取り消して、入力された観測情報に基づいて、新たに仮説模擬処理を実行することにより、少ない仮説数からシミュレーションを実行しなおすことができ、観測対象の将来時刻の予測が追いつかなくなることを防止することができる。
【００７１】
実施の形態４．
上記実施の形態１で示したチャンクサイズＴの決定方式では、各チャンクのチャンクサイズＴが同じ値となるので、実際にチャンクをスレッドで実行した際の処理時間は、どのチャンクでもほぼ同じ処理時間になると考えられる。
【００７２】
そこで、複数のフェデレート２は、シミュレーション実行中に、実行したチャンクの処理時間を記録して統計処理を行うことで、１つのチャンクの実行にかかる処理時間の推定値を求める。
【００７３】
また、複数のフェデレート２は、観測情報が入力された際に、観測時刻までの仮説模擬処理のすべてが完了していない場合には、観測時刻の仮説模擬処理がすべて完了するまでに実行しなければならないチャンクの数と、チャンクの処理時間の推定値とに基づいて、観測時刻の仮説模擬処理がすべて完了するまでチャンクを実行するのに必要な時間を見積る。
【００７４】
ここで、複数のフェデレート２は、見積もった時間が、次の観測情報が入力されるまでの時間よりも短ければ、実施の形態２に示した方式を実行し、見積もった時間が、次の観測情報が入力されるまでの時間よりも長ければ、実施の形態３に示した方式を実行する。これにより、全体的な処理時間を短縮することができる。
【００７５】
以上のように、実施の形態４によれば、上記実施の形態１に加え、すでに実行したチャンクの処理時間を記録して統計処理を行うことで、チャンクの処理時間の推定値を求め、観測情報が入力された時点で、観測時刻までの仮説模擬処理のすべてが完了していない場合には、観測時刻までの仮説模擬処理がすべて完了するまでに実行しなければならないチャンクの数と、チャンクの処理時間の推定値とに基づいて、観測時刻までの仮説模擬処理がすべて完了するまでチャンクを実行するのに必要な総チャンク実行時間を推定し、総チャンク実行時間が、次の観測情報が入力されるまでの時間よりも短ければ、観測時刻までの仮説模擬処理がすべて完了するまでチャンクを実行し、観測情報による仮説の評価を待たせ、総チャンク実行時間が、次の観測情報が入力されるまでの時間よりも長ければ、それまでに実行した仮説模擬処理をすべて取り消して、入力された観測情報に基づいて、新たに仮説模擬処理を実行する。そのため、全体的な処理時間を短縮することができる。
【符号の説明】
【００７６】
１  フェデレーション、２  複数のフェデレート、３  ＲＴＩ。
【図１】
0005818725.tif 000002
【図２】
0005818725.tif 000003
【図３】
0005818725.tif 000004
【図４】
0005818725.tif 000005
【図５】
0005818725.tif 000006
【図６】
0005818725.tif 000007
【図７】
0005818725.tif 000008
【図８】
0005818725.tif 000009
【図９】
0005818725.tif 000010
【図１０】
0005818725.tif 000011
【図１１】
0005818725.tif 000012
【図１２】
0005818725.tif 000013
【図１３】
0005818725.tif 000014
【図１４】
0005818725.tif 000015