分散シミュレーションシステム
【課題】モンテカルロ試行の中で確率の高いシミュレーションについての結果を得ることができる分散シミュレーションシステムを得る。
【解決手段】将来予測模擬部１は、オプティミスティック法によって複数のシミュレーションを実行する。分散シミュレーション基盤２は、シミュレーション時刻毎の中間的な各シミュレーション結果を集計して最も確率が高いと予測されるシミュレーションの優先順位に基づいて将来予測模擬部１における次のシミュレーション時刻のシミュレーション実行を割り当てるスケジューリングを行う。また、分散シミュレーション基盤２は、予め定めた制約時間内に全てのシミュレーションの実行が完了しない場合は確率が低いと予測されるシミュレーションの実行を打ち切る。
【解決手段】将来予測模擬部１は、オプティミスティック法によって複数のシミュレーションを実行する。分散シミュレーション基盤２は、シミュレーション時刻毎の中間的な各シミュレーション結果を集計して最も確率が高いと予測されるシミュレーションの優先順位に基づいて将来予測模擬部１における次のシミュレーション時刻のシミュレーション実行を割り当てるスケジューリングを行う。また、分散シミュレーション基盤２は、予め定めた制約時間内に全てのシミュレーションの実行が完了しない場合は確率が低いと予測されるシミュレーションの実行を打ち切る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オプティミスティック（Ｏｐｔｉｍｉｓｔｉｃ）法を用いて分散シミュレーションを行う分散シミュレーションシステムに関するものである。
【背景技術】
【０００２】
Ｏｐｔｉｍｉｓｔｉｃ法を用いる従来の分散シミュレーションシステムとして、例えば非特許文献１に記載されたものがあった。非特許文献１は、米軍を中心として標準化された分散シミュレーションシステムのアーキテクチャであるＨｉｇｈ Ｌｅｖｅｌ Ａｒｃｈｉｔｅｃｔｕｒｅ（ＨＬＡ）を示している。
図１は、ＨＬＡのアーキテクチャを示したものである。ＨＬＡでは、シミュレーションシステム全体をフェデレーション１０１と呼び、分散実行される模擬処理などのプログラムをフェデレート１０２と呼ぶ。そして、シミュレーションの実行中に行われる、フェデレーション全体の実行制御や、フェデレート間のデータ交換などの共通機能を、Ｒｕｎ−Ｔｉｍｅ Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ（ＲＴＩ）１０３という分散シミュレーション基盤が提供する。
【０００３】
図２は、ＨＬＡにおけるＯｐｔｉｍｉｓｔｉｃ法によるフェデレート１０２のシミュレーション時刻進行の例を示した図である。
フェデレート１及びフェデレート２は、それぞれシミュレーション時刻における模擬処理を実行するが、その際に将来のシミュレーション時刻の模擬を行うことも可能である。ここで、将来のシミュレーション時刻の模擬を、未だ確定しておらず取り消される可能性のある模擬であることから、仮説と呼ぶこととする。例えば図２の例において、フェデレート１は時刻ｔ０においてｔ０より将来の時刻の仮説を実行し、その結果としてｔｘ時刻のイベントｅｖ（ｔｘ）をフェデレート２に送信している。Ｏｐｔｉｍｉｓｔｉｃ法では、フェデレートは自分のシミュレーション時刻よりも将来の時刻のイベントを任意のタイミングで受信できることが特徴であり、そのためフェデレート２はｔ０時刻において将来イベントであるｅｖ（ｔｘ）を受信し、ｅｖ（ｔｘ）に基づくｔｘ時刻の仮説を実行することができる。フェデレート２は、ｔｘ時刻の仮説の結果としてｔｙ時刻のイベントｅｖ（ｔｙ）をフェデレート１に送信し、フェデレート１はｔ０時刻においてｅｖ（ｔｙ）に基づくｔｙ時刻の仮説を実行することができる。
【０００４】
次に、図３は、図２のフェデレート１、フェデレート２が時刻進行し、ｔｘ時刻に進んだ際の処理を示した図である。フェデレート２は、図１に示した通り、ｔ０時刻においてｔｘ時刻の仮説を実行していたため、ｔｘ時刻に進んだ際には、図に示したような処理フローに基づき、ｔｘ時刻の仮説の評価を行い、誤っていた場合にはその仮説の取消を実行した後にｔｘ時刻の模擬を実行する。図４は、図３の処理フローにおいて、仮説が誤っていたため仮設が取り消された場合のイベント取消の例を示す。フェデレート２のｔｘ時刻において、以前のｔ０時刻に実行したｔｘ時刻の仮説が誤っていたことが判明したため仮説の取消が行われた結果、その仮説に基づきフェデレート１に送信されていたイベントｅｖ（ｔｙ）についても取消が行われる。イベントｅｖ（ｔｙ）の取消は、イベント送信先のフェデレート１に対して通知され、フェデレート１ではｅｖ（ｔｙ）に基づきｔ０時刻に実行していた仮説の取消処理が行われる。
なお、図２および図３におけるフェデレートのシミュレーション時刻の進行制御と、イベントの通信処理は、ＲＴＩ１０３が管理する。
【０００５】
以上のように、Ｏｐｔｉｍｉｓｔｉｃ法では、シミュレーションにおける現在時刻より将来の時刻の模擬を仮説として実行し、さらに仮説によって発生した将来イベントの送信と受信によって仮説の実行を進めていくことが可能である。なお、将来イベントについては誤っていた場合に取消を行うことが可能なため、相反するような複数のイベントを同時に送信することにより、相反するようなシミュレーションを同時に実行することも可能である。この特徴を利用すると、例えば確率的なイベントを複数派生させることによって、モンテカルロシミュレーションにおける複数のモンテカルロ試行を同時に実行させることが可能である。
【０００６】
また、従来、Ｏｐｔｉｍｉｓｔｉｃ法によるシミュレーション時刻進行によって多数の仮説を投機的にシミュレーション実行する複数の仮説模擬処理を複数の演算装置に分散し、全体を分散シミュレーション基盤が実行制御する分散シミュレーションシステムの例としては、例えば非特許文献２に示されたものがあった。非特許文献２は、ＨＬＡと同様のシステム構成において、実時間における現在時刻より未来の状況をＯｐｔｉｍｉｓｔｉｃ法によって予測的にシミュレーション実行するためのシミュレーション実行基盤に関するものである。非特許文献２の５．１節によれば、将来予測された複数のシミュレーションは、多数のデシジョンポイント（Ｄｅｃｉｓｉｏｎ Ｐｏｉｎｔ）によってグラフ構造化されたフューチャーグラフ（Ｆｕｔｕｒｅｓ Ｇｒａｐｈ）として表され、Ｄｅｃｉｓｉｏｎ Ｐｏｉｎｔによって枝分かれした一つのパスが、一回のモンテカルロ試行において実行されるシミュレーションに対応する。図５に、非特許文献２のＦｕｔｕｒｅｓ Ｇｒａｐｈの例を示す。
【０００７】
図５において、各時刻（縦線）において黒丸で示されているのがその時刻におけるイベントを示しており、その時刻においてイベントを処理した結果が次以降の時刻のイベントとして出力されることを矢印線で示している。一つのイベント処理から複数の矢印線が出力されているものは、そのイベント処理において排他的な複数のＤｅｃｉｓｉｏｎが出力されていることを示しており、このイベント処理が枝分かれする分岐点がＤｅｃｉｓｉｏｎ Ｐｏｉｎｔである。なお、時刻線上におけるイベントの置かれた位置は、そのイベントを正規化した際の相対的なイベント間の違いを示したものである。
図５では、ｔ０からｔｘまでの論理時間進行において、各時刻において一つ以上のＤｅｃｉｓｉｏｎ Ｐｏｉｎｔが存在し、時刻が進むにつれシミュレーションが枝分かれしている様子が示されている。最終的に、ｔｘ時刻における各シミュレーションの結果であるイベントを正規化し、正規化された結果の分布から将来についての確率的な見積りを行う。
【０００８】
続いて図６に、図５のＦｕｔｕｒｅｓ Ｇｒａｐｈを非特許文献２のシミュレーション実行基盤がＯｐｔｉｍｉｓｔｉｃ法によってモンテカルロシミュレーションを実行する例を示す。尚、図６中、白丸（○）は保留イベント、大きな黒丸（●）は実行イベント、小さな黒丸（・）は実行済みイベント、×は便宜的取消を示している。Ｏｐｔｉｍｉｓｔｉｃ法では、非特許文献１で説明した通り、将来時刻のイベントを受け取ることで仮説として将来時刻のシミュレーションを実行することができ、またイベントの取消によって仮説のシミュレーションを実行し直すことが可能である。非特許文献２のシミュレーション実行基盤は、Ｏｐｔｉｍｉｔｓｉｃ法の仕組みを利用し、一つのモンテカルロ試行に対応するシミュレーションを一つの仮説として実行し、予測したい将来時刻までのシミュレーションを実行し終えると、便宜的にイベントの取消を実施して別のモンテカルロ試行に対応するシミュレーションを実行できる時刻まで時間を巻き戻し、別のモンテカルロ試行に対応するシミュレーションを実行する。
【０００９】
図６の例では、先ずモンテカルロ試行１回目においてｔ０からシミュレーション１を実行し、時刻を進めるに従いＤｅｃｉｓｉｏｎ Ｐｏｉｎｔによって別のイベントが枝分かれするが、その枝分かれしたイベントの処理は保留して、ｔｘまでシミュレーション１を実行する。次に、モンテカルロ試行２回目においては、シミュレーション１において別のシミュレーションが最初に分岐した時点においてシミュレーション１を実行するために使用したイベントを便宜的に取り消す。なお、このイベントの取消は便宜的なものであり、イベントから派生して実行されたシミュレーション全てが取り消されるわけではなく、シミュレーション結果は全て保存されている。イベントの便宜的な取消に基づき、非特許文献２の分散シミュレーション基盤がシミュレーション１において保留したシミュレーションを実行可能な時刻であるｔ１まで時刻を巻き戻し、実行可能なイベントに基づいてｔ１からシミュレーション２をｔｘまで実行する。モンテカルロ試行３回目では、モンテカルロ試行２回目と同様に、シミュレーション１およびシミュレーション２において保留されたシミュレーションを実行可能な時刻であるｔ２まで時刻を巻き戻し、ｔ２からシミュレーション３を実行する。なお、シミュレーション実行中に、他のモンテカルロ試行のシミュレーションの結果とイベントが同じになる場合は、シミュレーションをマージすることにより、余分なシミュレーションの分岐を抑制する。
【００１０】
以上のように、非特許文献２の方式では、Ｏｐｔｉｍｉｓｔｉｃ法を利用してモンテカルロ試行を実行することにより、各モンテカルロ試行において、巻き戻される時刻までのシミュレーションと、等しいイベントのシミュレーションについて、それぞれ実行回数が１回のみとなり、同じ結果になることが分かっているイベント処理を省略することができるため、モンテカルロ試行を高速に実行することが可能となる。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】IEEE 1516.1-2000 - Standard for Modeling and Simulation High Level Architecture(HLA) - Federate Interface Specification
【非特許文献２】Jeffrey S. Steinman, et al., “Simulating Parallel Overlapping Universes in the Fifth Dimension with HyperWarpSpeed Implemented in the WarpIV Kernel”, 2008 Spring Simulation Interoperability Workshop, 08S-SIW-025
【発明の概要】
【発明が解決しようとする課題】
【００１２】
非特許文献２の方式は、モンテカルロ試行を高速に実行することが可能であるが、非特許文献２の方式が適用されるシステムは、現在時刻より未来の状況を予測的にシミュレーション実行することを目的にしており、そのためにはシミュレーションが予測したい将来時刻までに終了しなければならないというリアルタイム制約の課題がある。
しかしながら、上記従来の分散シミュレーションシステムでは、このようなリアルタイム制約に対し、十分な解決手段を提供していないという課題があった。例えば、非特許文献２の方式でも、Ｄｅｃｉｓｉｏｎ Ｐｏｉｎｔにおけるシミュレーション分岐数が非常に多くなった場合などでリアルタイム制約における制約時間内にモンテカルロ試行が実行終了できないケースが考えられ、そのような場合はシミュレーションを途中で打ち切ることになるが、このような場合は、非特許文献２の方式では次に挙げる二つの問題があった。
【００１３】
即ち、第一の問題としては、モンテカルロ試行の実行中に動的にＦｕｔｕｒｅｓ Ｇｒａｐｈが更新されるため、途中の段階で最終的なモンテカルロ試行回数を求めることができないという問題である。次に、第二の問題は、打ち切られるまでに実行したモンテカルロ試行については、Ｏｐｔｉｍｉｓｔｉｃ法によって巻き戻せる時刻順に実行されており、モンテカルロ試行全体が完了していない途中段階で結果を集計しても、どの様な偏りがあるか分からないという問題である。このような問題のため、非特許文献２の方式では、リアルタイム制約における制約時間内にモンテカルロ試行が実行終了できずシミュレーションを途中で打ち切った場合に、それまで実行されたシミュレーションの結果について確率的な高低を判断することができないといった課題があった。
【００１４】
この発明は上記のような課題を解決するためになされたもので、モンテカルロ試行の中で確率の高いシミュレーションについての結果を得ることができる分散シミュレーションシステムを得ることを目的とする。
【課題を解決するための手段】
【００１５】
この発明に係る分散シミュレーションシステムは、現在の状況をシミュレーション初期条件として多数回のモンテカルロ試行によるシミュレーションを実行し、各シミュレーション結果を統計処理して確率的な将来予測を行う場合に、並列に複数のシミュレーションを実行する分散シミュレーションシステムであって、オプティミスティック法によって複数のシミュレーションを実行する将来予測模擬部と、シミュレーション時刻毎の中間的な各シミュレーション結果を集計して最も確率が高いと予測されるシミュレーションの優先順位に基づいて将来予測模擬部における次のシミュレーション時刻のシミュレーション実行を割り当てるスケジューリングを行う分散シミュレーション基盤とを備え、分散シミュレーション基盤は、予め定めた制約時間内に全てのシミュレーションの実行が完了しない場合は確率が低いと予測されるシミュレーションの実行を打ち切るようにしたものである。
【発明の効果】
【００１６】
この発明の分散シミュレーションシステムは、シミュレーションの優先順位に基づいて次のシミュレーション時刻のシミュレーション実行を割り当て、予め定めた制約時間内に全てのシミュレーションの実行が完了しない場合は確率が低いと予測されるシミュレーションの実行を打ち切るようにしたので、より確率が高くなると予測されるシミュレーションを制約時間内に実行することができる。
【図面の簡単な説明】
【００１７】
【図１】ＨＬＡのアーキテクチャを示す説明図である。
【図２】ＨＬＡにおけるオプティミスティック法によるフェデレートのシミュレーション時刻進行の例を示す説明図である。
【図３】図２におけるフェデレート１，２がｔｘ時刻に進んだ際の処理を示した説明図である。
【図４】イベント取消の例を示す説明図である。
【図５】非特許文献２のＦｕｔｕｒｅｓ Ｇｒａｐｈの例を示す説明図である。
【図６】オプティミスティック法によってモンテカルロシミュレーションを実行する例を示す説明図である。
【図７】この発明の実施の形態１による分散シミュレーションシステムを示す構成図である。
【図８】この発明の実施の形態１による分散シミュレーションシステムのシミュレーション実行を示す説明図である。
【図９】この発明の実施の形態１による分散シミュレーションシステムのスケジュールリストを示す説明図である。
【図１０】この発明の実施の形態１による分散シミュレーションシステムのイベントの実行が制約時間で打ち切られた場合の動作を示す説明図である。
【図１１】この発明の実施の形態１による分散シミュレーションシステムのイベントの実行が制約時間で打ち切られた場合のスケジュールリストを示す説明図である。
【発明を実施するための形態】
【００１８】
実施の形態１．
図７は、この発明の実施の形態１による分散シミュレーションシステムを示す構成図である。
図７に示す分散シミュレーションシステムは、将来予測模擬部１と分散シミュレーション基盤２を備えている。将来予測模擬部１は、実時間における現在時刻より未来の状況を予測的にシミュレーション実行する機能部であり、Ｏｐｔｉｍｉｓｔｉｃ法による分散並列処理によって仮説を実行する複数の仮説模擬処理部１−１〜１−ｎを備えている。即ち、将来予測模擬部１は、Ｏｐｔｉｍｉｓｔｉｃ法によって複数のシミュレーションを並列に実行する機能部である。分散シミュレーション基盤２は、将来予測模擬部１の仮説模擬処理部１−１〜１−ｎに対して、シミュレーション時刻による時刻進行制御とイベントの送受信制御を行う機能部である。
【００１９】
尚、図７に示す分散シミュレーションシステムは、コンピュータを用いて実現され、将来予測模擬部１及び分散シミュレーション基盤２は、それぞれの機能に対応したソフトウェアと、これらソフトウェアを実行するためのＣＰＵやメモリといったハードウェアから構成されている。また、それぞれの仮説模擬処理部１−１〜１−ｎは、並列に処理を行う複数のＣＰＵを用いて構成されている。さらに、将来予測模擬部１や分散シミュレーション基盤２の少なくとも一部を専用のハードウェアで構成してもよい。
【００２０】
次に、実施の形態１の分散シミュレーションシステムの動作について説明する。
図８は、図７の何れかの仮説模擬処理部１−１〜１−ｎにおいて、実時間における現在時刻ｔ０より未来の状況を、Ｄｅｃｉｓｉｏｎ Ｐｏｉｎｔによってグラフ構造化されたＦｕｔｕｒｅｓ Ｇｒａｐｈとしてシミュレーション実行する様子を示している。尚、図中の白丸（○）は保留イベント、大きな黒丸（●）は実行イベント、小さな黒丸（・）は実行済みイベントを示している。本発明のＦｕｔｕｒｅｓ Ｇｒａｐｈによるモンテカルロ試行の実行は、非特許文献２のシステムとは異なり、ｔ０からｔｘまでの各時刻において異なるモンテカルロ試行をできる限り同時に実行する。図８の状況で説明すると、論理時刻ｔ０において異なるモンテカルロ試行１、２に対応するイベントｅｖ１＿１、ｅｖ２＿１が論理時刻ｔ１に出力された場合、論理時刻ｔ１におけるシミュレーション実行は、ｅｖ１＿１とｅｖ２＿１のイベント処理を同時に実行することにより、モンテカルロ試行１、２を同時に実行する。
【００２１】
図９は、図８の状況における分散シミュレーション基盤２の、仮説模擬処理部１−１〜１−ｎでのイベント処理をスケジューリングするために使用するスケジューリングリストを示したものである。スケジューリングリストは、１行に一つのイベントについての情報を格納したもので、左列に仮説模擬処理部１−１〜１−ｎで実行する際の実行優先度が格納され、中列にイベントの論理時刻が格納され、右列にイベントが格納されている。スケジューリングリストの各行は、先ず左列の実行優先度の降順でソートされ、同じ実行優先度の複数のイベントについては論理時刻の昇順にソートされている。同じ実行優先度で同じ論理時刻の複数のイベントの順序は任意である。なお、実行優先度は合計が１になるような数値が設定される。スケジューリングリストに登録されたイベントは、リストの上から順に仮説模擬処理部１−１〜１−ｎに実行が割当られるが、この分散シミュレーションシステムがリアルタイム以上の処理速度でｔｘ時刻までの将来予測シミュレーションを実行するために設定された制約時間まで仮説模擬処理部１−１〜１−ｎで処理が行われ、制約時間までにスケジューリングリストに登録された全てのイベントが実行できなかった場合にはその時点でイベントの処理が打ち切られる。スケジューリングリストは、スケジューリングリストに登録された全てのイベントが実行されるか、または制約時間で打ち切られるとクリアされ、別のスケジューリングリストが作成される。
【００２２】
次に、図８、図９の状況における動作について説明する。図８、図９の状況は本発明による分散シミュレーションシステムにおいて将来予測が開始され始めた段階であり、スケジューリングリストに登録された全てのイベントが制約時間内に処理し終える状況である。
先ず、何れかの仮説模擬処理部１−１〜１−ｎが、論理時刻ｔ０において現在時刻の状態を基に次時刻であるｔ１の状況をシミュレーション実行し、その結果として将来時刻ｔ１に対してシミュレーションがモンテカルロ試行１、２に枝分かれするイベントｅｖ１＿１およびｅｖ２＿２が論理時刻ｔ１に対して出力される。仮説模擬処理部１−１〜１−ｎにおける論理時刻ｔ０のシミュレーション実行が終わると、分散シミュレーション基盤２は、論理時刻ｔ１に生成されたｅｖ１＿１とｅｖ２＿２を正規化して比較し、マージ可能か否かを判断し、その結果によってイベント実行優先度を計算し、スケジューリングリストへの登録を行う。図８におけるｔ０実行の状況では、マージすることができないため、ｅｖ１＿１の実行優先度Ｐｅｖ１＿１と、ｅｖ２＿１の実行優先度Ｐｅｖ２＿１の夫々に公平になるよう計算｛１／（モンテカルロ試行数）｝に基づき実行優先度０．５を設定し、スケジューリングリストに登録する。
【００２３】
次に、論理時刻ｔ１におけるシミュレーション実行について説明する。論理時刻ｔ１のシミュレーション実行は、先ず、分散シミュレーション基盤２がスケジューリングリストの上から順に実行するイベントを取り出し、仮説模擬処理部１−１〜１−ｎにおいて仮説模擬処理を実行させる。図の状況では、ｅｖ１＿１およびｅｖ２＿１が同じ実行優先度であったため、ｅｖ１＿１とｅｖ２＿１のどちらが先に実行されるかは状況依存である。ｅｖ１＿１とｅｖ２＿１の実行が終了すると、論理時刻ｔ２に対してシミュレーションが枝分かれするイベントが出力される。図８の状況では、ｅｖ１＿１の実行の結果、モンテカルロ試行１におけるｅｖ１＿２と、枝分かれしたモンテカルロ試行３におけるｅｖ３＿１が出力され、またｅｖ２＿１の実行の結果、モンテカルロ試行２におけるｅｖ２＿２と、枝分かれしたモンテカルロ試行４におけるｅｖ４＿１が出力されている。
【００２４】
論理時刻ｔ１のシミュレーション実行が終わると、分散シミュレーション基盤２は、論理時刻ｔ１の際と同様に、論理時刻ｔ２に生成された各イベントを正規化して比較し、マージ可能か否かを判断し、その結果によってイベント実行優先度を計算し、スケジューリングリストへの登録を行う。各イベントに対する実行優先度の計算は、各モンテカルロ試行に対する実行優先度は｛１／（モンテカルロ試行数）｝に基づき０．２５になるが、図８の状況ではｅｖ３＿１がｅｖ２＿２にマージされているため、ｅｖ２＿２の実行優先度Ｐｅｖ２＿２はマージ回数分実行優先度が加算されて０．５となり、スケジューリングリストに登録されるとｅｖ２＿２がリストの最上位に格納される。
【００２５】
次に、論理時刻ｔ２におけるシミュレーション実行について説明する。論理時刻ｔ２のシミュレーション実行は、先ず、分散シミュレーション基盤２がスケジューリングリストの上から順に実行するイベントを取り出し、仮説模擬処理部１−１〜１−ｎにおいて仮説模擬処理を実行させる。図の状況では、ｅｖ２＿２が最も実行優先度が高いため、分散シミュレーション基盤２は、ｅｖ２＿２から仮説模擬処理部１−１〜１−ｎにおいて仮説模擬処理を実行させる。ｅｖ２＿２、ｅｖ１＿２、ｅｖ４＿１の実行が終了すると、論理時刻ｔ３に対してシミュレーションが枝分かれするイベントが出力される。図８の状況では、ｅｖ１＿２の実行の結果、モンテカルロ試行１におけるｅｖ１＿３と、枝分かれしたモンテカルロ試行５、６におけるｅｖ５＿１、ｅｖ６＿１が出力され、ｅｖ２＿２の実行の結果、モンテカルロ試行２におけるｅｖ２＿３と、枝分かれしたモンテカルロ試行７におけるｅｖ７＿１が出力され、またｅｖ３＿１の実行の結果、モンテカルロ試行３におけるｅｖ４＿２と、枝分かれしたモンテカルロ試行８におけるｅｖ８＿１が出力される。
【００２６】
論理時刻ｔ２のシミュレーション実行が終わると、論理時刻ｔ０、ｔ１の際と同様に、分散シミュレーション基盤２は論理時刻ｔ３に生成された各イベントを正規化して比較し、マージ可能か否かを判断し、その結果によってイベント実行優先度を計算して、スケジューリングリストへの登録を行う。各イベントに対する実行優先度の計算は、各モンテカルロ試行に対する実行優先度は｛１／（モンテカルロ試行数）｝に基づき０．１２５になるが、図８の状況では、先ずモンテカルロ試行２のｅｖ２＿３は論理時刻ｔ２においてモンテカルロ試行３がマージされているためマージ回数分実行優先度が加算されて０．２５となり、またｅｖ４＿２は論理時刻ｔ３においてｅｖ８＿１がｅｖ４＿２にマージされるためマージ回数分実行優先度が加算されて０．２５となりスケジューリングリストに登録される。
【００２７】
このように、各時刻のモンテカルロ試行が同時に実行されると、出力される次時刻のイベントの正規化によってモンテカルロ試行間のマージ可能性が判断され、マージされたモンテカルロ試行は実行優先度が高く設定される。以降、同様の処理がｔｘまで続けられるが、次に図１０、図１１を用いてスケジューリングリストに登録されたイベントの実行が制約時間で打ち切られた場合の動作について説明する。尚、図１０における白丸（○）は保留イベント、大きな黒丸（●）は実行イベント、小さな黒丸（・）は実行済みイベントを示している。
【００２８】
図１０のｔ３実行の状況は、図８のｔ２実行後の状態から論理時刻ｔ３のイベントをスケジューリングリストを用いて仮説模擬処理部１−１〜１−ｎで実行した際に、スケジューリングリストの上から順に実行されたｅｖ２＿３、ｅｖ４＿２、ｅｖ１＿３のイベント実行が制約時間内に終了し、ｅｖ５＿１、ｅｖ６＿１、ｅｖ８＿１の実行ができなかった場合を示している。本発明による分散シミュレーションシステムでは、このまま次の論理時刻ｔ４のイベント実行に進むが、その際にｔ４より前に実行できなかったイベントのモンテカルロ試行を含めて実行優先度を計算する。ｔ４時刻までに派生した各モンテカルロ試行に対する実行優先度は｛１／（モンテカルロ試行数）｝に基づき０．１になるが、ここでマージ回数分についての加算が行われ、その結果ｅｖ２＿４はｔ２においてマージが行われているため０．２、ｅｖ４＿３はｔ３およびｔ４においてマージが行われているため０．３、他のモンテカルロ試行が０．１となる。実行優先度とイベントをスケジューリングリストに登録すると、図１１のｔ４のように登録される。先ず、実行優先度によって降順にソートされるため、ｅｖ４＿３に続いてｅｖ２＿４の順に並び、そのほかのイベントについては実行優先度は同じであるが、これらのイベントは時刻の昇順にソートされるため、ｅｖ５＿１、ｅｖ６＿１、ｅｖ８＿１が上に登録される。論理時刻ｔ４においては、このスケジューリングリストに基づき、リストの上から順に仮説模擬処理部１−１〜１−ｎに対してイベント実行が割り当てられる。
【００２９】
このような動作を行うことにより実施の形態１では次のような効果がある。即ち、現在時刻ｔ０の状況をもとにモンテカルロ試行によって将来時刻ｔｘの状況を見積るようなシミュレーションシステムにおいては、ｔｘに実時間が進んでしまう前にシミュレーションを実行させる必要があるため、制約時間内でシミュレーションが実行できない場合は途中でシミュレーションを打ち切らなければならない。しかしながら、本実施の形態による分散シミュレーションシステムでは、時刻毎にＤｅｃｉｓｉｏｎ Ｐｏｉｎｔで派生したモンテカルロ試行のイベントについて同時に実行するためのスケジューリングを行い、その際、マージされたイベントの数によってモンテカルロ試行の優先順位をつけることにより、制約時間内で全てのイベントが実行できなくてもマージ数の多いモンテカルロ試行が優先的にｔｘまでに実行されるため、モンテカルロ試行の中で確率の高いシミュレーションについてｔｘ時刻の結果を得ることができる。
【００３０】
また、マージ数が少なく優先度が低いシミュレーションが多くなった場合には、前時刻のイベントから優先的にスケジューリングが行われるため、優先されるイベントが局所的に偏ることを防ぐことができる。
【００３１】
以上説明したように、実施の形態１の分散シミュレーションシステムによれば、現在の状況をシミュレーション初期条件として多数回のモンテカルロ試行によるシミュレーションを実行し、各シミュレーション結果を統計処理して確率的な将来予測を行う場合に、並列に複数のシミュレーションを実行する分散シミュレーションシステムであって、オプティミスティック法によって複数のシミュレーションを実行する将来予測模擬部と、シミュレーション時刻毎の中間的な各シミュレーション結果を集計して最も確率が高いと予測されるシミュレーションの優先順位に基づいて将来予測模擬部における次のシミュレーション時刻のシミュレーション実行を割り当てるスケジューリングを行う分散シミュレーション基盤とを備え、分散シミュレーション基盤は、予め定めた制約時間内に全てのシミュレーションの実行が完了しない場合は確率が低いと予測されるシミュレーションの実行を打ち切るようにしたので、より確率が高くなると予測されるシミュレーションを制約時間内に実行することができる。
【００３２】
また、実施の形態１の分散シミュレーションシステムによれば、分散シミュレーション基盤は、任意のシミュレーション時刻におけるシミュレーション結果が同一であった場合は、同一のシミュレーション結果をマージした数だけ確率を加算するようにしたので、制約時間内でのシミュレーションの精度を向上させることができる。
【００３３】
また、実施の形態１の分散シミュレーションシステムによれば、分散シミュレーション基盤は、同一のシミュレーション時刻における複数のシミュレーションを同時に実行するようにしたので、制約時間内でのシミュレーションをより確実に実行することができる。
【００３４】
また、実施の形態１の分散シミュレーションシステムによれば、分散シミュレーション基盤は、打ち切ったシミュレーションについて、次時刻以降のシミュレーション時刻におけるシミュレーション実行の際に優先度を再計算し、確率が同じと見積られる他のシミュレーションより優先的にスケジューリングを行うようにしたので、優先されるシミュレーションの実行が局所的に偏ることを防ぐことができる。
【００３５】
尚、本願発明はその発明の範囲内において、実施の形態の任意の構成要素の変形、もしくは実施の形態の任意の構成要素の省略が可能である。
【符号の説明】
【００３６】
１ 将来予測模擬部、１−１〜１−ｎ 仮説模擬処理部、２ 分散シミュレーション基盤。
【技術分野】
【０００１】
本発明は、オプティミスティック（Ｏｐｔｉｍｉｓｔｉｃ）法を用いて分散シミュレーションを行う分散シミュレーションシステムに関するものである。
【背景技術】
【０００２】
Ｏｐｔｉｍｉｓｔｉｃ法を用いる従来の分散シミュレーションシステムとして、例えば非特許文献１に記載されたものがあった。非特許文献１は、米軍を中心として標準化された分散シミュレーションシステムのアーキテクチャであるＨｉｇｈ Ｌｅｖｅｌ Ａｒｃｈｉｔｅｃｔｕｒｅ（ＨＬＡ）を示している。
図１は、ＨＬＡのアーキテクチャを示したものである。ＨＬＡでは、シミュレーションシステム全体をフェデレーション１０１と呼び、分散実行される模擬処理などのプログラムをフェデレート１０２と呼ぶ。そして、シミュレーションの実行中に行われる、フェデレーション全体の実行制御や、フェデレート間のデータ交換などの共通機能を、Ｒｕｎ−Ｔｉｍｅ Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ（ＲＴＩ）１０３という分散シミュレーション基盤が提供する。
【０００３】
図２は、ＨＬＡにおけるＯｐｔｉｍｉｓｔｉｃ法によるフェデレート１０２のシミュレーション時刻進行の例を示した図である。
フェデレート１及びフェデレート２は、それぞれシミュレーション時刻における模擬処理を実行するが、その際に将来のシミュレーション時刻の模擬を行うことも可能である。ここで、将来のシミュレーション時刻の模擬を、未だ確定しておらず取り消される可能性のある模擬であることから、仮説と呼ぶこととする。例えば図２の例において、フェデレート１は時刻ｔ０においてｔ０より将来の時刻の仮説を実行し、その結果としてｔｘ時刻のイベントｅｖ（ｔｘ）をフェデレート２に送信している。Ｏｐｔｉｍｉｓｔｉｃ法では、フェデレートは自分のシミュレーション時刻よりも将来の時刻のイベントを任意のタイミングで受信できることが特徴であり、そのためフェデレート２はｔ０時刻において将来イベントであるｅｖ（ｔｘ）を受信し、ｅｖ（ｔｘ）に基づくｔｘ時刻の仮説を実行することができる。フェデレート２は、ｔｘ時刻の仮説の結果としてｔｙ時刻のイベントｅｖ（ｔｙ）をフェデレート１に送信し、フェデレート１はｔ０時刻においてｅｖ（ｔｙ）に基づくｔｙ時刻の仮説を実行することができる。
【０００４】
次に、図３は、図２のフェデレート１、フェデレート２が時刻進行し、ｔｘ時刻に進んだ際の処理を示した図である。フェデレート２は、図１に示した通り、ｔ０時刻においてｔｘ時刻の仮説を実行していたため、ｔｘ時刻に進んだ際には、図に示したような処理フローに基づき、ｔｘ時刻の仮説の評価を行い、誤っていた場合にはその仮説の取消を実行した後にｔｘ時刻の模擬を実行する。図４は、図３の処理フローにおいて、仮説が誤っていたため仮設が取り消された場合のイベント取消の例を示す。フェデレート２のｔｘ時刻において、以前のｔ０時刻に実行したｔｘ時刻の仮説が誤っていたことが判明したため仮説の取消が行われた結果、その仮説に基づきフェデレート１に送信されていたイベントｅｖ（ｔｙ）についても取消が行われる。イベントｅｖ（ｔｙ）の取消は、イベント送信先のフェデレート１に対して通知され、フェデレート１ではｅｖ（ｔｙ）に基づきｔ０時刻に実行していた仮説の取消処理が行われる。
なお、図２および図３におけるフェデレートのシミュレーション時刻の進行制御と、イベントの通信処理は、ＲＴＩ１０３が管理する。
【０００５】
以上のように、Ｏｐｔｉｍｉｓｔｉｃ法では、シミュレーションにおける現在時刻より将来の時刻の模擬を仮説として実行し、さらに仮説によって発生した将来イベントの送信と受信によって仮説の実行を進めていくことが可能である。なお、将来イベントについては誤っていた場合に取消を行うことが可能なため、相反するような複数のイベントを同時に送信することにより、相反するようなシミュレーションを同時に実行することも可能である。この特徴を利用すると、例えば確率的なイベントを複数派生させることによって、モンテカルロシミュレーションにおける複数のモンテカルロ試行を同時に実行させることが可能である。
【０００６】
また、従来、Ｏｐｔｉｍｉｓｔｉｃ法によるシミュレーション時刻進行によって多数の仮説を投機的にシミュレーション実行する複数の仮説模擬処理を複数の演算装置に分散し、全体を分散シミュレーション基盤が実行制御する分散シミュレーションシステムの例としては、例えば非特許文献２に示されたものがあった。非特許文献２は、ＨＬＡと同様のシステム構成において、実時間における現在時刻より未来の状況をＯｐｔｉｍｉｓｔｉｃ法によって予測的にシミュレーション実行するためのシミュレーション実行基盤に関するものである。非特許文献２の５．１節によれば、将来予測された複数のシミュレーションは、多数のデシジョンポイント（Ｄｅｃｉｓｉｏｎ Ｐｏｉｎｔ）によってグラフ構造化されたフューチャーグラフ（Ｆｕｔｕｒｅｓ Ｇｒａｐｈ）として表され、Ｄｅｃｉｓｉｏｎ Ｐｏｉｎｔによって枝分かれした一つのパスが、一回のモンテカルロ試行において実行されるシミュレーションに対応する。図５に、非特許文献２のＦｕｔｕｒｅｓ Ｇｒａｐｈの例を示す。
【０００７】
図５において、各時刻（縦線）において黒丸で示されているのがその時刻におけるイベントを示しており、その時刻においてイベントを処理した結果が次以降の時刻のイベントとして出力されることを矢印線で示している。一つのイベント処理から複数の矢印線が出力されているものは、そのイベント処理において排他的な複数のＤｅｃｉｓｉｏｎが出力されていることを示しており、このイベント処理が枝分かれする分岐点がＤｅｃｉｓｉｏｎ Ｐｏｉｎｔである。なお、時刻線上におけるイベントの置かれた位置は、そのイベントを正規化した際の相対的なイベント間の違いを示したものである。
図５では、ｔ０からｔｘまでの論理時間進行において、各時刻において一つ以上のＤｅｃｉｓｉｏｎ Ｐｏｉｎｔが存在し、時刻が進むにつれシミュレーションが枝分かれしている様子が示されている。最終的に、ｔｘ時刻における各シミュレーションの結果であるイベントを正規化し、正規化された結果の分布から将来についての確率的な見積りを行う。
【０００８】
続いて図６に、図５のＦｕｔｕｒｅｓ Ｇｒａｐｈを非特許文献２のシミュレーション実行基盤がＯｐｔｉｍｉｓｔｉｃ法によってモンテカルロシミュレーションを実行する例を示す。尚、図６中、白丸（○）は保留イベント、大きな黒丸（●）は実行イベント、小さな黒丸（・）は実行済みイベント、×は便宜的取消を示している。Ｏｐｔｉｍｉｓｔｉｃ法では、非特許文献１で説明した通り、将来時刻のイベントを受け取ることで仮説として将来時刻のシミュレーションを実行することができ、またイベントの取消によって仮説のシミュレーションを実行し直すことが可能である。非特許文献２のシミュレーション実行基盤は、Ｏｐｔｉｍｉｔｓｉｃ法の仕組みを利用し、一つのモンテカルロ試行に対応するシミュレーションを一つの仮説として実行し、予測したい将来時刻までのシミュレーションを実行し終えると、便宜的にイベントの取消を実施して別のモンテカルロ試行に対応するシミュレーションを実行できる時刻まで時間を巻き戻し、別のモンテカルロ試行に対応するシミュレーションを実行する。
【０００９】
図６の例では、先ずモンテカルロ試行１回目においてｔ０からシミュレーション１を実行し、時刻を進めるに従いＤｅｃｉｓｉｏｎ Ｐｏｉｎｔによって別のイベントが枝分かれするが、その枝分かれしたイベントの処理は保留して、ｔｘまでシミュレーション１を実行する。次に、モンテカルロ試行２回目においては、シミュレーション１において別のシミュレーションが最初に分岐した時点においてシミュレーション１を実行するために使用したイベントを便宜的に取り消す。なお、このイベントの取消は便宜的なものであり、イベントから派生して実行されたシミュレーション全てが取り消されるわけではなく、シミュレーション結果は全て保存されている。イベントの便宜的な取消に基づき、非特許文献２の分散シミュレーション基盤がシミュレーション１において保留したシミュレーションを実行可能な時刻であるｔ１まで時刻を巻き戻し、実行可能なイベントに基づいてｔ１からシミュレーション２をｔｘまで実行する。モンテカルロ試行３回目では、モンテカルロ試行２回目と同様に、シミュレーション１およびシミュレーション２において保留されたシミュレーションを実行可能な時刻であるｔ２まで時刻を巻き戻し、ｔ２からシミュレーション３を実行する。なお、シミュレーション実行中に、他のモンテカルロ試行のシミュレーションの結果とイベントが同じになる場合は、シミュレーションをマージすることにより、余分なシミュレーションの分岐を抑制する。
【００１０】
以上のように、非特許文献２の方式では、Ｏｐｔｉｍｉｓｔｉｃ法を利用してモンテカルロ試行を実行することにより、各モンテカルロ試行において、巻き戻される時刻までのシミュレーションと、等しいイベントのシミュレーションについて、それぞれ実行回数が１回のみとなり、同じ結果になることが分かっているイベント処理を省略することができるため、モンテカルロ試行を高速に実行することが可能となる。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】IEEE 1516.1-2000 - Standard for Modeling and Simulation High Level Architecture(HLA) - Federate Interface Specification
【非特許文献２】Jeffrey S. Steinman, et al., “Simulating Parallel Overlapping Universes in the Fifth Dimension with HyperWarpSpeed Implemented in the WarpIV Kernel”, 2008 Spring Simulation Interoperability Workshop, 08S-SIW-025
【発明の概要】
【発明が解決しようとする課題】
【００１２】
非特許文献２の方式は、モンテカルロ試行を高速に実行することが可能であるが、非特許文献２の方式が適用されるシステムは、現在時刻より未来の状況を予測的にシミュレーション実行することを目的にしており、そのためにはシミュレーションが予測したい将来時刻までに終了しなければならないというリアルタイム制約の課題がある。
しかしながら、上記従来の分散シミュレーションシステムでは、このようなリアルタイム制約に対し、十分な解決手段を提供していないという課題があった。例えば、非特許文献２の方式でも、Ｄｅｃｉｓｉｏｎ Ｐｏｉｎｔにおけるシミュレーション分岐数が非常に多くなった場合などでリアルタイム制約における制約時間内にモンテカルロ試行が実行終了できないケースが考えられ、そのような場合はシミュレーションを途中で打ち切ることになるが、このような場合は、非特許文献２の方式では次に挙げる二つの問題があった。
【００１３】
即ち、第一の問題としては、モンテカルロ試行の実行中に動的にＦｕｔｕｒｅｓ Ｇｒａｐｈが更新されるため、途中の段階で最終的なモンテカルロ試行回数を求めることができないという問題である。次に、第二の問題は、打ち切られるまでに実行したモンテカルロ試行については、Ｏｐｔｉｍｉｓｔｉｃ法によって巻き戻せる時刻順に実行されており、モンテカルロ試行全体が完了していない途中段階で結果を集計しても、どの様な偏りがあるか分からないという問題である。このような問題のため、非特許文献２の方式では、リアルタイム制約における制約時間内にモンテカルロ試行が実行終了できずシミュレーションを途中で打ち切った場合に、それまで実行されたシミュレーションの結果について確率的な高低を判断することができないといった課題があった。
【００１４】
この発明は上記のような課題を解決するためになされたもので、モンテカルロ試行の中で確率の高いシミュレーションについての結果を得ることができる分散シミュレーションシステムを得ることを目的とする。
【課題を解決するための手段】
【００１５】
この発明に係る分散シミュレーションシステムは、現在の状況をシミュレーション初期条件として多数回のモンテカルロ試行によるシミュレーションを実行し、各シミュレーション結果を統計処理して確率的な将来予測を行う場合に、並列に複数のシミュレーションを実行する分散シミュレーションシステムであって、オプティミスティック法によって複数のシミュレーションを実行する将来予測模擬部と、シミュレーション時刻毎の中間的な各シミュレーション結果を集計して最も確率が高いと予測されるシミュレーションの優先順位に基づいて将来予測模擬部における次のシミュレーション時刻のシミュレーション実行を割り当てるスケジューリングを行う分散シミュレーション基盤とを備え、分散シミュレーション基盤は、予め定めた制約時間内に全てのシミュレーションの実行が完了しない場合は確率が低いと予測されるシミュレーションの実行を打ち切るようにしたものである。
【発明の効果】
【００１６】
この発明の分散シミュレーションシステムは、シミュレーションの優先順位に基づいて次のシミュレーション時刻のシミュレーション実行を割り当て、予め定めた制約時間内に全てのシミュレーションの実行が完了しない場合は確率が低いと予測されるシミュレーションの実行を打ち切るようにしたので、より確率が高くなると予測されるシミュレーションを制約時間内に実行することができる。
【図面の簡単な説明】
【００１７】
【図１】ＨＬＡのアーキテクチャを示す説明図である。
【図２】ＨＬＡにおけるオプティミスティック法によるフェデレートのシミュレーション時刻進行の例を示す説明図である。
【図３】図２におけるフェデレート１，２がｔｘ時刻に進んだ際の処理を示した説明図である。
【図４】イベント取消の例を示す説明図である。
【図５】非特許文献２のＦｕｔｕｒｅｓ Ｇｒａｐｈの例を示す説明図である。
【図６】オプティミスティック法によってモンテカルロシミュレーションを実行する例を示す説明図である。
【図７】この発明の実施の形態１による分散シミュレーションシステムを示す構成図である。
【図８】この発明の実施の形態１による分散シミュレーションシステムのシミュレーション実行を示す説明図である。
【図９】この発明の実施の形態１による分散シミュレーションシステムのスケジュールリストを示す説明図である。
【図１０】この発明の実施の形態１による分散シミュレーションシステムのイベントの実行が制約時間で打ち切られた場合の動作を示す説明図である。
【図１１】この発明の実施の形態１による分散シミュレーションシステムのイベントの実行が制約時間で打ち切られた場合のスケジュールリストを示す説明図である。
【発明を実施するための形態】
【００１８】
実施の形態１．
図７は、この発明の実施の形態１による分散シミュレーションシステムを示す構成図である。
図７に示す分散シミュレーションシステムは、将来予測模擬部１と分散シミュレーション基盤２を備えている。将来予測模擬部１は、実時間における現在時刻より未来の状況を予測的にシミュレーション実行する機能部であり、Ｏｐｔｉｍｉｓｔｉｃ法による分散並列処理によって仮説を実行する複数の仮説模擬処理部１−１〜１−ｎを備えている。即ち、将来予測模擬部１は、Ｏｐｔｉｍｉｓｔｉｃ法によって複数のシミュレーションを並列に実行する機能部である。分散シミュレーション基盤２は、将来予測模擬部１の仮説模擬処理部１−１〜１−ｎに対して、シミュレーション時刻による時刻進行制御とイベントの送受信制御を行う機能部である。
【００１９】
尚、図７に示す分散シミュレーションシステムは、コンピュータを用いて実現され、将来予測模擬部１及び分散シミュレーション基盤２は、それぞれの機能に対応したソフトウェアと、これらソフトウェアを実行するためのＣＰＵやメモリといったハードウェアから構成されている。また、それぞれの仮説模擬処理部１−１〜１−ｎは、並列に処理を行う複数のＣＰＵを用いて構成されている。さらに、将来予測模擬部１や分散シミュレーション基盤２の少なくとも一部を専用のハードウェアで構成してもよい。
【００２０】
次に、実施の形態１の分散シミュレーションシステムの動作について説明する。
図８は、図７の何れかの仮説模擬処理部１−１〜１−ｎにおいて、実時間における現在時刻ｔ０より未来の状況を、Ｄｅｃｉｓｉｏｎ Ｐｏｉｎｔによってグラフ構造化されたＦｕｔｕｒｅｓ Ｇｒａｐｈとしてシミュレーション実行する様子を示している。尚、図中の白丸（○）は保留イベント、大きな黒丸（●）は実行イベント、小さな黒丸（・）は実行済みイベントを示している。本発明のＦｕｔｕｒｅｓ Ｇｒａｐｈによるモンテカルロ試行の実行は、非特許文献２のシステムとは異なり、ｔ０からｔｘまでの各時刻において異なるモンテカルロ試行をできる限り同時に実行する。図８の状況で説明すると、論理時刻ｔ０において異なるモンテカルロ試行１、２に対応するイベントｅｖ１＿１、ｅｖ２＿１が論理時刻ｔ１に出力された場合、論理時刻ｔ１におけるシミュレーション実行は、ｅｖ１＿１とｅｖ２＿１のイベント処理を同時に実行することにより、モンテカルロ試行１、２を同時に実行する。
【００２１】
図９は、図８の状況における分散シミュレーション基盤２の、仮説模擬処理部１−１〜１−ｎでのイベント処理をスケジューリングするために使用するスケジューリングリストを示したものである。スケジューリングリストは、１行に一つのイベントについての情報を格納したもので、左列に仮説模擬処理部１−１〜１−ｎで実行する際の実行優先度が格納され、中列にイベントの論理時刻が格納され、右列にイベントが格納されている。スケジューリングリストの各行は、先ず左列の実行優先度の降順でソートされ、同じ実行優先度の複数のイベントについては論理時刻の昇順にソートされている。同じ実行優先度で同じ論理時刻の複数のイベントの順序は任意である。なお、実行優先度は合計が１になるような数値が設定される。スケジューリングリストに登録されたイベントは、リストの上から順に仮説模擬処理部１−１〜１−ｎに実行が割当られるが、この分散シミュレーションシステムがリアルタイム以上の処理速度でｔｘ時刻までの将来予測シミュレーションを実行するために設定された制約時間まで仮説模擬処理部１−１〜１−ｎで処理が行われ、制約時間までにスケジューリングリストに登録された全てのイベントが実行できなかった場合にはその時点でイベントの処理が打ち切られる。スケジューリングリストは、スケジューリングリストに登録された全てのイベントが実行されるか、または制約時間で打ち切られるとクリアされ、別のスケジューリングリストが作成される。
【００２２】
次に、図８、図９の状況における動作について説明する。図８、図９の状況は本発明による分散シミュレーションシステムにおいて将来予測が開始され始めた段階であり、スケジューリングリストに登録された全てのイベントが制約時間内に処理し終える状況である。
先ず、何れかの仮説模擬処理部１−１〜１−ｎが、論理時刻ｔ０において現在時刻の状態を基に次時刻であるｔ１の状況をシミュレーション実行し、その結果として将来時刻ｔ１に対してシミュレーションがモンテカルロ試行１、２に枝分かれするイベントｅｖ１＿１およびｅｖ２＿２が論理時刻ｔ１に対して出力される。仮説模擬処理部１−１〜１−ｎにおける論理時刻ｔ０のシミュレーション実行が終わると、分散シミュレーション基盤２は、論理時刻ｔ１に生成されたｅｖ１＿１とｅｖ２＿２を正規化して比較し、マージ可能か否かを判断し、その結果によってイベント実行優先度を計算し、スケジューリングリストへの登録を行う。図８におけるｔ０実行の状況では、マージすることができないため、ｅｖ１＿１の実行優先度Ｐｅｖ１＿１と、ｅｖ２＿１の実行優先度Ｐｅｖ２＿１の夫々に公平になるよう計算｛１／（モンテカルロ試行数）｝に基づき実行優先度０．５を設定し、スケジューリングリストに登録する。
【００２３】
次に、論理時刻ｔ１におけるシミュレーション実行について説明する。論理時刻ｔ１のシミュレーション実行は、先ず、分散シミュレーション基盤２がスケジューリングリストの上から順に実行するイベントを取り出し、仮説模擬処理部１−１〜１−ｎにおいて仮説模擬処理を実行させる。図の状況では、ｅｖ１＿１およびｅｖ２＿１が同じ実行優先度であったため、ｅｖ１＿１とｅｖ２＿１のどちらが先に実行されるかは状況依存である。ｅｖ１＿１とｅｖ２＿１の実行が終了すると、論理時刻ｔ２に対してシミュレーションが枝分かれするイベントが出力される。図８の状況では、ｅｖ１＿１の実行の結果、モンテカルロ試行１におけるｅｖ１＿２と、枝分かれしたモンテカルロ試行３におけるｅｖ３＿１が出力され、またｅｖ２＿１の実行の結果、モンテカルロ試行２におけるｅｖ２＿２と、枝分かれしたモンテカルロ試行４におけるｅｖ４＿１が出力されている。
【００２４】
論理時刻ｔ１のシミュレーション実行が終わると、分散シミュレーション基盤２は、論理時刻ｔ１の際と同様に、論理時刻ｔ２に生成された各イベントを正規化して比較し、マージ可能か否かを判断し、その結果によってイベント実行優先度を計算し、スケジューリングリストへの登録を行う。各イベントに対する実行優先度の計算は、各モンテカルロ試行に対する実行優先度は｛１／（モンテカルロ試行数）｝に基づき０．２５になるが、図８の状況ではｅｖ３＿１がｅｖ２＿２にマージされているため、ｅｖ２＿２の実行優先度Ｐｅｖ２＿２はマージ回数分実行優先度が加算されて０．５となり、スケジューリングリストに登録されるとｅｖ２＿２がリストの最上位に格納される。
【００２５】
次に、論理時刻ｔ２におけるシミュレーション実行について説明する。論理時刻ｔ２のシミュレーション実行は、先ず、分散シミュレーション基盤２がスケジューリングリストの上から順に実行するイベントを取り出し、仮説模擬処理部１−１〜１−ｎにおいて仮説模擬処理を実行させる。図の状況では、ｅｖ２＿２が最も実行優先度が高いため、分散シミュレーション基盤２は、ｅｖ２＿２から仮説模擬処理部１−１〜１−ｎにおいて仮説模擬処理を実行させる。ｅｖ２＿２、ｅｖ１＿２、ｅｖ４＿１の実行が終了すると、論理時刻ｔ３に対してシミュレーションが枝分かれするイベントが出力される。図８の状況では、ｅｖ１＿２の実行の結果、モンテカルロ試行１におけるｅｖ１＿３と、枝分かれしたモンテカルロ試行５、６におけるｅｖ５＿１、ｅｖ６＿１が出力され、ｅｖ２＿２の実行の結果、モンテカルロ試行２におけるｅｖ２＿３と、枝分かれしたモンテカルロ試行７におけるｅｖ７＿１が出力され、またｅｖ３＿１の実行の結果、モンテカルロ試行３におけるｅｖ４＿２と、枝分かれしたモンテカルロ試行８におけるｅｖ８＿１が出力される。
【００２６】
論理時刻ｔ２のシミュレーション実行が終わると、論理時刻ｔ０、ｔ１の際と同様に、分散シミュレーション基盤２は論理時刻ｔ３に生成された各イベントを正規化して比較し、マージ可能か否かを判断し、その結果によってイベント実行優先度を計算して、スケジューリングリストへの登録を行う。各イベントに対する実行優先度の計算は、各モンテカルロ試行に対する実行優先度は｛１／（モンテカルロ試行数）｝に基づき０．１２５になるが、図８の状況では、先ずモンテカルロ試行２のｅｖ２＿３は論理時刻ｔ２においてモンテカルロ試行３がマージされているためマージ回数分実行優先度が加算されて０．２５となり、またｅｖ４＿２は論理時刻ｔ３においてｅｖ８＿１がｅｖ４＿２にマージされるためマージ回数分実行優先度が加算されて０．２５となりスケジューリングリストに登録される。
【００２７】
このように、各時刻のモンテカルロ試行が同時に実行されると、出力される次時刻のイベントの正規化によってモンテカルロ試行間のマージ可能性が判断され、マージされたモンテカルロ試行は実行優先度が高く設定される。以降、同様の処理がｔｘまで続けられるが、次に図１０、図１１を用いてスケジューリングリストに登録されたイベントの実行が制約時間で打ち切られた場合の動作について説明する。尚、図１０における白丸（○）は保留イベント、大きな黒丸（●）は実行イベント、小さな黒丸（・）は実行済みイベントを示している。
【００２８】
図１０のｔ３実行の状況は、図８のｔ２実行後の状態から論理時刻ｔ３のイベントをスケジューリングリストを用いて仮説模擬処理部１−１〜１−ｎで実行した際に、スケジューリングリストの上から順に実行されたｅｖ２＿３、ｅｖ４＿２、ｅｖ１＿３のイベント実行が制約時間内に終了し、ｅｖ５＿１、ｅｖ６＿１、ｅｖ８＿１の実行ができなかった場合を示している。本発明による分散シミュレーションシステムでは、このまま次の論理時刻ｔ４のイベント実行に進むが、その際にｔ４より前に実行できなかったイベントのモンテカルロ試行を含めて実行優先度を計算する。ｔ４時刻までに派生した各モンテカルロ試行に対する実行優先度は｛１／（モンテカルロ試行数）｝に基づき０．１になるが、ここでマージ回数分についての加算が行われ、その結果ｅｖ２＿４はｔ２においてマージが行われているため０．２、ｅｖ４＿３はｔ３およびｔ４においてマージが行われているため０．３、他のモンテカルロ試行が０．１となる。実行優先度とイベントをスケジューリングリストに登録すると、図１１のｔ４のように登録される。先ず、実行優先度によって降順にソートされるため、ｅｖ４＿３に続いてｅｖ２＿４の順に並び、そのほかのイベントについては実行優先度は同じであるが、これらのイベントは時刻の昇順にソートされるため、ｅｖ５＿１、ｅｖ６＿１、ｅｖ８＿１が上に登録される。論理時刻ｔ４においては、このスケジューリングリストに基づき、リストの上から順に仮説模擬処理部１−１〜１−ｎに対してイベント実行が割り当てられる。
【００２９】
このような動作を行うことにより実施の形態１では次のような効果がある。即ち、現在時刻ｔ０の状況をもとにモンテカルロ試行によって将来時刻ｔｘの状況を見積るようなシミュレーションシステムにおいては、ｔｘに実時間が進んでしまう前にシミュレーションを実行させる必要があるため、制約時間内でシミュレーションが実行できない場合は途中でシミュレーションを打ち切らなければならない。しかしながら、本実施の形態による分散シミュレーションシステムでは、時刻毎にＤｅｃｉｓｉｏｎ Ｐｏｉｎｔで派生したモンテカルロ試行のイベントについて同時に実行するためのスケジューリングを行い、その際、マージされたイベントの数によってモンテカルロ試行の優先順位をつけることにより、制約時間内で全てのイベントが実行できなくてもマージ数の多いモンテカルロ試行が優先的にｔｘまでに実行されるため、モンテカルロ試行の中で確率の高いシミュレーションについてｔｘ時刻の結果を得ることができる。
【００３０】
また、マージ数が少なく優先度が低いシミュレーションが多くなった場合には、前時刻のイベントから優先的にスケジューリングが行われるため、優先されるイベントが局所的に偏ることを防ぐことができる。
【００３１】
以上説明したように、実施の形態１の分散シミュレーションシステムによれば、現在の状況をシミュレーション初期条件として多数回のモンテカルロ試行によるシミュレーションを実行し、各シミュレーション結果を統計処理して確率的な将来予測を行う場合に、並列に複数のシミュレーションを実行する分散シミュレーションシステムであって、オプティミスティック法によって複数のシミュレーションを実行する将来予測模擬部と、シミュレーション時刻毎の中間的な各シミュレーション結果を集計して最も確率が高いと予測されるシミュレーションの優先順位に基づいて将来予測模擬部における次のシミュレーション時刻のシミュレーション実行を割り当てるスケジューリングを行う分散シミュレーション基盤とを備え、分散シミュレーション基盤は、予め定めた制約時間内に全てのシミュレーションの実行が完了しない場合は確率が低いと予測されるシミュレーションの実行を打ち切るようにしたので、より確率が高くなると予測されるシミュレーションを制約時間内に実行することができる。
【００３２】
また、実施の形態１の分散シミュレーションシステムによれば、分散シミュレーション基盤は、任意のシミュレーション時刻におけるシミュレーション結果が同一であった場合は、同一のシミュレーション結果をマージした数だけ確率を加算するようにしたので、制約時間内でのシミュレーションの精度を向上させることができる。
【００３３】
また、実施の形態１の分散シミュレーションシステムによれば、分散シミュレーション基盤は、同一のシミュレーション時刻における複数のシミュレーションを同時に実行するようにしたので、制約時間内でのシミュレーションをより確実に実行することができる。
【００３４】
また、実施の形態１の分散シミュレーションシステムによれば、分散シミュレーション基盤は、打ち切ったシミュレーションについて、次時刻以降のシミュレーション時刻におけるシミュレーション実行の際に優先度を再計算し、確率が同じと見積られる他のシミュレーションより優先的にスケジューリングを行うようにしたので、優先されるシミュレーションの実行が局所的に偏ることを防ぐことができる。
【００３５】
尚、本願発明はその発明の範囲内において、実施の形態の任意の構成要素の変形、もしくは実施の形態の任意の構成要素の省略が可能である。
【符号の説明】
【００３６】
１ 将来予測模擬部、１−１〜１−ｎ 仮説模擬処理部、２ 分散シミュレーション基盤。
【特許請求の範囲】
【請求項１】
現在の状況をシミュレーション初期条件として多数回のモンテカルロ試行によるシミュレーションを実行し、各シミュレーション結果を統計処理して確率的な将来予測を行う場合に、並列に複数のシミュレーションを実行する分散シミュレーションシステムであって、
オプティミスティック法によって前記複数のシミュレーションを実行する将来予測模擬部と、
シミュレーション時刻毎の中間的な各シミュレーション結果を集計して最も確率が高いと予測されるシミュレーションの優先順位に基づいて前記将来予測模擬部における次のシミュレーション時刻のシミュレーション実行を割り当てるスケジューリングを行う分散シミュレーション基盤とを備え、
前記分散シミュレーション基盤は、予め定めた制約時間内に全てのシミュレーションの実行が完了しない場合は確率が低いと予測されるシミュレーションの実行を打ち切ることを特徴とする分散シミュレーションシステム。
【請求項２】
分散シミュレーション基盤は、任意のシミュレーション時刻におけるシミュレーション結果が同一であった場合は、当該同一のシミュレーション結果をマージした数だけ確率を加算することを特徴とする請求項１記載の分散シミュレーションシステム。
【請求項３】
分散シミュレーション基盤は、同一のシミュレーション時刻における複数のシミュレーションを同時に実行することを特徴とする請求項１または請求項２記載の分散シミュレーションシステム。
【請求項４】
分散シミュレーション基盤は、打ち切ったシミュレーションについて、次時刻以降のシミュレーション時刻におけるシミュレーション実行の際に優先度を再計算し、確率が同じと見積られる他のシミュレーションより優先的にスケジューリングを行うことを特徴とする請求項１から請求項３のうちのいずれか１項記載の分散シミュレーションシステム。
【請求項１】
現在の状況をシミュレーション初期条件として多数回のモンテカルロ試行によるシミュレーションを実行し、各シミュレーション結果を統計処理して確率的な将来予測を行う場合に、並列に複数のシミュレーションを実行する分散シミュレーションシステムであって、
オプティミスティック法によって前記複数のシミュレーションを実行する将来予測模擬部と、
シミュレーション時刻毎の中間的な各シミュレーション結果を集計して最も確率が高いと予測されるシミュレーションの優先順位に基づいて前記将来予測模擬部における次のシミュレーション時刻のシミュレーション実行を割り当てるスケジューリングを行う分散シミュレーション基盤とを備え、
前記分散シミュレーション基盤は、予め定めた制約時間内に全てのシミュレーションの実行が完了しない場合は確率が低いと予測されるシミュレーションの実行を打ち切ることを特徴とする分散シミュレーションシステム。
【請求項２】
分散シミュレーション基盤は、任意のシミュレーション時刻におけるシミュレーション結果が同一であった場合は、当該同一のシミュレーション結果をマージした数だけ確率を加算することを特徴とする請求項１記載の分散シミュレーションシステム。
【請求項３】
分散シミュレーション基盤は、同一のシミュレーション時刻における複数のシミュレーションを同時に実行することを特徴とする請求項１または請求項２記載の分散シミュレーションシステム。
【請求項４】
分散シミュレーション基盤は、打ち切ったシミュレーションについて、次時刻以降のシミュレーション時刻におけるシミュレーション実行の際に優先度を再計算し、確率が同じと見積られる他のシミュレーションより優先的にスケジューリングを行うことを特徴とする請求項１から請求項３のうちのいずれか１項記載の分散シミュレーションシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１２−２４３２１２（Ｐ２０１２−２４３２１２Ａ）
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願番号】特願２０１１−１１４９４７（Ｐ２０１１−１１４９４７）
【出願日】平成２３年５月２３日（２０１１．５．２３）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願日】平成２３年５月２３日（２０１１．５．２３）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
[ Back to top ]