(57)【要約】      （修正有）【課題】バリア同期によるシミュレーション時間進行が行われている場合でも、前回までの実行結果を利用した模擬の削除を効率よく適用する分散シミュレーションシステムの提供。【解決手段】複数演算装置で分散して模擬処理する分散シミュレーションシステムで、現試行中のモンテカルロシミュレーションの次に実行するシミュレーション時刻の任意の模擬処理結果が、前回までに試行した同じシミュレーション時刻に試行し、その模擬処理結果と同じ結果になることが予め判明しており、前回の結果を再利用することで、次に実行する任意の模擬処理実行が省略可能な場合、省略可能な当該模擬処理を除いた模擬処理の演算装置への割り当てを行うことにより、実行が必要な模擬処理のみを動的に演算装置にスケジューリングし実行する。【選択図】図５
2012008946.tif 000002
【特許請求の範囲】
【請求項１】
複数の対象物に対する模擬処理を複数の演算装置に分散して実行する分散シミュレーションシステムによりモンテカルロシミュレーションを実行する方法において、
現在試行中のモンテカルロシミュレーションの次に実行するシミュレーション時刻の任意の模擬処理結果が、前回までの同じシミュレーション時刻に試行し、その模擬処理結果と同じ結果となることが予め判明しており、その結果を再利用することで、次に実行する任意の模擬処理の実行を省略できる場合に、
結果の再利用によって実行を省略できる当該模擬処理を除いた模擬処理の演算装置への割り当てを行うことにより、
シミュレーション実行中に実行が必要な模擬処理のみを動的に演算装置にスケジューリングして、実行することを特徴とする分散シミュレーション方法。
【請求項２】
分散シミュレーション方法は、複数の演算装置間で行うデータ通信により矛盾が生じないよう、シミュレーション時間進行に従ってバリア同期が行われる方法であり、分散して実行する模擬処理間のバリア同期を行うシミュレーション時刻を、模擬処理の演算装置への割り当て処理によってシミュレーション実行中に動的に求めることを特徴とする請求項１記載の分散シミュレーション方法。
【請求項３】
分散して実行する模擬処理間のバリア同期を行うシミュレーション時刻が求められた際に、演算装置数を超えた数の模擬処理を割り当てる必要が生じた場合には、シミュレーションの実行中に模擬処理の実行を終了した演算装置から演算装置数の超過分の模擬処理を割り当てることで、演算装置数の超過分の模擬処理を動的に負荷の軽い演算装置へスケジューリングし、シミュレーションを実行することを特徴とする請求項２記載の分散シミュレーション方法。
【請求項４】
分散して実行する模擬処理間のバリア同期を行うシミュレーション時刻が求められた際に、そのシミュレーション時刻までの模擬処理の実行を投機的なシミュレーション時間進行によって行うことを特徴とする請求項２記載の分散シミュレーション方法。
【請求項５】
分散して実行する模擬処理間のバリア同期を行うシミュレーション時刻が求められた際に、そのシミュレーション時刻までの模擬処理の実行を投機的なシミュレーション時間進行によって行い、
さらに、分散して実行する模擬処理間のバリア同期を行うシミュレーション時刻が求められた際に、演算装置数を超えた数の模擬処理を割り当てる必要が生じた場合には、シミュレーションの実行中に模擬処理の実行を終了した演算装置から演算装置数の超過分の模擬処理を割り当て、演算装置数の超過分の模擬処理を動的に負荷の軽い演算装置へスケジューリングすることを特徴とする請求項２記載の分散シミュレーション方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の演算装置で異なる対象物を模擬し、模擬結果を複数の演算装置間でデータ通信する分散シミュレーションシステムでの分散シミュレーション方法に関するものである。
【背景技術】
【０００２】
一般的にモンテカルロ法を用いたシミュレーションは、ある事象の発生確率が不明な場合に、乱数を用いてｎ回のシミュレーションを実行し、その事象の発生回数ｍを得て、発生確率の近似解ｍ／ｎを求めるために利用される。この近似解の精度は確率論において試行回数が多い方が高くなるため、よりよい近似解を得るためには、より多くのシミュレーション実行回数が必要である。しかし時間的な制約があるような場合、従来のシミュレーション実行環境では満足なシミュレーション実行回数を得ることは困難であり、より高速にモンテカルロシミュレーションを実行できる方式が必要とされている。
【０００３】
モンテカルロシミュレーションを高速に実行するための従来技術として、特許文献１と非特許文献１が挙げられる。特許文献１は、モンテカルロシミュレーションの高速化手法として、微小なタイムステップに基づいて実行する移動体シミュレーションにおいて、初回に実行した結果を利用して、２回目以降は結果的に不要となる模擬を削除し、総実行時間を短縮するものである。また、非特許文献１記載のモンテカルロシミュレーション高速実行技術は、米軍を中心として標準化された分散シミュレーションシステムのアーキテクチャであるHigh Level Architecture（ＨＬＡ）である。ＨＬＡは、シミュレーションを複数のフェデレートと呼ばれるプログラムで分散処理させるためのアーキテクチャを定めたもので、シミュレーションの対象となる１つの大きな問題（フェデレーション）を複数のフェデレートで模擬処理するように分割し、各フェデレートを演算装置に割り当てて並列分散処理させ、全体をRun-Time Infrastructure（ＲＴＩ）という基盤プログラムが制御することにより、システム全体としての処理の高速化などを目的としたものである。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開2007-78288号公報「シミュレーション実行方法」
【非特許文献】
【０００５】
【非特許文献１】IEEE 1516.1-2000 - Standard for Modeling and Simulation High Level Architecture(HLA) - Federate Interface Specification
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１に挙げたＨＬＡは分散シミュレーションシステムの標準アーキテクチャであり、ＨＬＡに基づく、あるいはＨＬＡと良く似た分散処理を用いた、分散シミュレーション実行環境は一般的に広く利用されている。図１は、ＨＬＡによる一般的な分散シミュレーションシステムの例である。ＨＬＡでは、ＲＴＩ１０１が、分散実行される模擬処理１０２に対するシミュレーション時間の進行に基づき実行制御と、模擬処理１０２間のデータ通信制御を行なう。また図２は、ＨＬＡに基づき構築された一般的な分散シミュレーションシステムのシミュレーション時間進行の例である。このようなシステムでは、シミュレーションに登場する移動物体やセンサなどの模擬対象物を模擬処理するフェデレートを演算装置に割り付け、各フェデレートがシミュレーション時間の時間刻みに従って模擬対象物の模擬処理を並列実行する。その際、フェデレート間のデータ通信によって矛盾が生じないよう、シミュレーション時間進行に従ってバリア同期が行われる。フェデレート間のデータ通信とバリア同期は、ＲＴＩによって制御される。
【０００７】
図３は、図２のような分散シミュレーションの実行において、シミュレーション時間の進行に基づき模擬処理の実行を制御するために利用されるイベントリストを示したものである。イベントリストは、模擬処理についてその実行時刻と実行入力値が設定されており、シミュレーション実行により実行中に実行時刻が更新されると、どの他の模擬処理が同じ実行時刻に設定されているかの情報が取り出され、その他の模擬処理が割り当てられた演算装置に対し、実行時刻と実行入力値が渡されて模擬処理が実行される。その時刻の演算装置における模擬処理の実行が終了すると、イベントリストには、模擬処理の次回の実行時刻と実行入力値が設定される。
【０００８】
イベントリストに設定される次回の実行時刻は、模擬処理の種別に応じて次の２種類の何れかとなる。一つは、例えば航空レーダ模擬処理のように周期的に実行されるような模擬処理の場合であり、このような模擬処理では模擬処理自身が次回の実行時刻を設定する。もう一つは、例えば航空管制模擬処理（航空レーダ模擬処理の実行結果である探知情報が生成された場合のみ実行される）のように他の模擬処理の実行結果イベントに依存して実行するような模擬処理の場合であり、このような模擬処理では依存する実行結果イベントの発生時刻が次回の実行時刻として設定される。
イベントリストに設定される実行入力値は、その模擬処理が模擬を行うのに必要とする入力値であり、自身の模擬実行結果である状態情報や、あるいは他の模擬処理の実行結果が設定される。
【０００９】
上記のようなシミュレーション時間の進行に基づき模擬処理の実行を制御する分散シミュレーション実行環境において、さらにモンテカルロシミュレーションを高速に実行するために、特許文献１に挙げたような、前回までの実行結果を利用して２回目以降は結果的に不要となる模擬を削除する方式を採用した場合、図４に示す例のようになる。図４は、演算装置１にて処理している航空機フェデレートの模擬処理がTn、Tn+1時刻において省略可能であった場合の例であるが、各時刻において演算装置１にて模擬処理が省略可能であっても、フェデレート間で毎時刻のバリア同期が行われているため、模擬処理を省略した演算装置は、その時刻は他の演算装置の模擬処理の実行が終了するまで待たされている。すなわち、分散シミュレーションシステムでは、一部の模擬処理において前回までの実行結果を利用することができ、模擬を省略できたとしても、他の模擬処理がそのシミュレーション時間において処理を行っている間はシミュレーション時間進行を待たされてしまうため、全体として高速にシミュレーションを実行することが困難であるという課題がある。
【００１０】
本発明は、上記のような、分散シミュレーションシステムにおいてバリア同期によるシミュレーション時間進行が行われている場合でも、前回までの実行結果を利用した模擬の削除を効率よく適用する分散シミュレーション方式に関するものである。
【課題を解決するための手段】
【００１１】
本発明に係る分散シミュレーション方法は、
模擬処理を複数の演算装置に分散して実行する分散シミュレーションシステムによるモンテカルロシミュレーションを実行する方法において、
現在試行中のモンテカルロシミュレーションの次に実行するシミュレーション時刻の任意の模擬処理結果が、前回までに試行した同じシミュレーション時刻に試行し、その模擬処理結果と同じ結果となることが予め判明しており、その結果を再利用することで、実行を省略できる場合に、
結果の再利用によって実行を省略できる当該模擬処理を除いた模擬処理の演算装置への割り当てを行うことにより、
シミュレーション実行中に実行が必要な模擬処理のみを動的に演算装置にスケジューリングして、実行する。
【発明の効果】
【００１２】
本発明に係る分散シミュレーション方法によれば、
モンテカルロシミュレーションにおける２回目以降のシミュレーション実行において、スケジューリング処理による実行中の動的なフレームの決定と模擬処理の演算装置への割り当てを行うことにより、バリア同期回数を削減することができる。また、他の演算装置での処理結果を待たずに投機的に模擬処理の実行を開始することにより、演算装置における処理の待ち時間を減らし、効率的に演算装置を利用できる。これらの効果により、シミュレーション実行の高速化を行うことができる。
【図面の簡単な説明】
【００１３】
【図１】ＨＬＡによる分散シミュレーションシステムの構成例を示す図である。
【図２】ＨＬＡによる分散シミュレーションシステムのシミュレーション時間進行の例を示す図である。
【図３】分散シミュレーション実行時に模擬処理制御用のイベントリストを示す図である。
【図４】処理中の航空機フェデレートの模擬処理がT省略可能な場合のシミュレーション時間進行の例を示す図である。
【図５】本発明による分散シミュレーションシステムの構成例を示す図である。
【図６】本発明によるシミュレーション実行中、動的に模擬処理の演算装置への割り当てを行ったシミュレーション時間進行の例を示す図である。
【図７】本発明によるスケジューリング処理の処理フロー図である。
【図８】スケジューリング処理結果のスケジューリングリスト例を示す図である。
【発明を実施するための形態】
【００１４】
実施の形態１．
分散シミュレーションシステムを用いてモンテカルロシミュレーションを実行する際に、結果の再利用によって実行を省略できる当該模擬処理を除いた模擬処理の演算装置への割り当てを行う実施の形態について述べる。
図５は、本発明による分散シミュレーションシステムの構成例である。図５において５０１は、分散実行される模擬処理１０２に対するシミュレーション時間の進行に基づき実行制御と、模擬処理１０２間のデータ通信制御を行なう分散シミュレーション基盤である。分散シミュレーション基盤５０１は、図１に示したＨＬＡに準拠した分散シミュレーションシステムにおけるＲＴＩ１０１に類似した基盤プログラムであるが、さらに本発明によるモンテカルロシミュレーションを高速化するための機能を付与した基盤プログラムである。５０２は、シミュレーション時間の進行に基づき模擬処理の実行を制御するために利用されるイベントリストである。５０３は、イベントリスト５０２およびスケジューリングリスト５０４に基づき、模擬処理１０２を演算装置へ割り当てて処理実行させるスケジューリング処理である。５０４は、モンテカルロシミュレーションの２回目以降の試行において、前回までの試行で既に同じ結果が出ている模擬処理の実行を省き、また同時に演算装置に実行をスケジューリングできる模擬処理と実行する時刻、入力情報を管理するスケジューリングリストで、スケジューリング処理５０３が、イベントリスト５０２の設定値を基に同時に演算装置へ割り当て可能な模擬処理１０２の組合せを設定し、さらにスケジューリング処理５０３が模擬処理１０２を演算装置へ割り当てる際に参照するものである。
図６は、本発明によってシミュレーション実行中に動的に模擬処理の演算装置への割り当てを行った例である。図４に示すバリア同期後に各演算装置で実行されるスケジューリング処理において、演算装置間のバリア同期を行うシミュレーション時間の刻み幅であるフレームと、演算装置に実行を割り当てる模擬処理を決定する。
【００１５】
図７は、スケジューリング処理の処理フローを示す。スケジューリング処理では、スケジューリングリストに対して、その時刻から演算装置で並列実行しようとする模擬処理を登録し、スケジューリングリストに設定された模擬処理の時刻の最大値までを、次のバリア同期を行うまでのフレームサイズとして設定する。
図８は、スケジューリングリストの例である。スケジューリングリストは、図７の処理フローに基づき登録されるが、登録される情報のうち、実行入力値および実行出力値は、イベントリストと、モンテカルロ試行の前回までのシミュレーションにおける結果データから、以下のように登録される。
【００１６】
○実行登録の場合：実行入力値を設定し、実行出力値は設定しない
(A)   実行入力値として設定可能な、同じシミュレーションにおける前の時刻の試行
結果情報がある場合：実行入力値に、同じシミュレーションにおける前の時刻の試
行結果情報を設定
(B)   実行入力値として設定可能な、同じシミュレーションにおける前の時刻の試行
結果情報がない場合：実行入力値に、前回までのシミュレーションにおける前の時
刻の試行結果情報を設定（複数ある場合は、任意の試行結果情報を設定）
○省略登録の場合：実行出力値を設定し、実行入力値は設定しない。実行出力値に、図
７の処理フローの(1)の処理で探索した結果情報を設定
【００１７】
図７の処理フローの(2)の処理において、演算装置に割り当てられた模擬処理は、フレーム内の時刻の模擬を実行するが、同じフレームに割り当てられた同じ模擬処理または他の模擬処理の前の時刻の結果情報に基づいて模擬を実行する場合には、模擬結果による依存関係のある模擬処理が並列実行されることになる。このため、これらの模擬処理は、モンテカルロ試行による前回までのシミュレーション実行における結果データを用いて投機的な実行を行うものとする。すなわち、依存している情報を、前回までのシミュレーション実行における結果データと仮定して模擬の実行を投機的に開始し、後から依存している情報が生成された際にその情報と仮定した情報を比較して、異なっていれば模擬の実行をやり直し、異なっていなければ投機的に実行した結果をそのまま採用する。例えば、図６のフレーム m において、演算装置２に割り当てられた航空機管制模擬処理(Tn+1)と、演算装置３に割り当てられた航空レーダ模擬処理（Tn+1）は、演算装置１に割り当てられた航空レーダ模擬処理(Tn)の結果である探知情報に依存するが、モンテカルロ試行による前回までのシミュレーション実行における航空レーダ模擬処理(Tn)の結果である探知情報を用いて投機的に実行を開始し、その後で演算装置１の航空レーダ模擬処理(Tn)の実行結果である探知情報を受信した際に、それぞれ実行のやり直しが必要か否かを判定する。
【００１８】
以上のように、モンテカルロシミュレーションにおける２回目以降のシミュレーション実行において、スケジューリング処理による実行中の動的なフレームの決定と模擬処理の演算装置への割り当てを行うことにより、バリア同期回数を削減することができる。また、他の演算装置での処理結果を待たずに投機的に模擬処理の実行を開始することにより、演算装置における処理の待ち時間を減らし、効率的に演算装置を利用できる。これらの効果により、シミュレーション実行の高速化を行うことができる。
【００１９】
実施の形態２．
次に、演算装置数の超過分の模擬処理を動的に負荷の軽い演算装置へスケジューリングする方法について述べる。
図７の処理フローの(3)の条件判定では、演算装置数を超える数の模擬処理がスケジューリングリストに登録されないように判定を行うが、続く(4)の条件判定において、イベントリストに未だバリア同期までに実行しなければならない模擬処理が存在すると判定された場合、演算装置数の超過分の模擬処理がスケジューリングリストに実行登録される場合がある。このような場合は、以下の手順で実行登録された模擬処理を演算装置に割り当てる。
【００２０】
(1)   実行時刻の早い模擬処理から順に演算装置に割り当てる。
(2)   ある演算装置Ａにおいて模擬処理Ｂの実行が終了した場合、以下を実行する。
(イ)  模擬処理Ｂの結果情報Ｃが、スケジューリングリストに残った未割り当ての模
擬処理の実行入力値となる場合、スケジューリングリストの該当模擬処理の実行入
力値を、結果情報Ｃに書き換える
(ロ)  スケジューリングリストに残った未割り当ての模擬処理の中から最も実行時刻
の早い模擬処理を１つ選択し、演算装置Ａに割り当てる
(3)   スケジューリングリストに残った未割り当ての模擬処理が無くなるまで(2)の処
理を繰り返す
【００２１】
この手順により、動的に処理が終了した演算装置へのスケジューリングが行われ、また実行が終了した模擬処理の結果情報によりスケジューリングリストの実行入力値が変更されることにより入力値を仮定した投機的な実行が行われなくなるため再実行のリスクが回避されることから、演算装置数を超える数の模擬処理がスケジューリングリストに登録された場合にも効率的にシミュレーションを実行することが可能となる。
【００２２】
なお、演算装置に割り当てられた模擬処理を実行するとき、同じフレームに割り当てられた同じ模擬処理または他の模擬処理の前の時刻の結果情報に基づいて模擬を実行する場合には、依存している情報を、モンテカルロ試行による前回までのシミュレーション実行における結果データと仮定して模擬の実行を投機的に開始し、後から依存している情報が生成された際にその情報と仮定した情報を比較して、異なっていれば模擬の実行をやり直し、異なっていなければ投機的に実行した結果をそのまま採用し、
さらに、分散して実行する模擬処理間のバリア同期を行うシミュレーション時刻が求められた際に、演算装置数を超えた数の模擬処理を割り当てる必要が生じた場合には、シミュレーションの実行中に模擬処理の実行を終了した演算装置から演算装置数の超過分の模擬処理を割り当てることにより、演算装置数の超過分の模擬処理を動的に負荷の軽い演算装置へスケジューリングし、全体として高速に試行中のシミュレーションを実行するようにしてもよい。このようにすることで、さらにシミュレーション実行の高速化を行うことができる。
【産業上の利用可能性】
【００２３】
この発明に係る分散シミュレーションシステムによるモンテカルロシミュレーション実行方式は、例えば航空機の模擬と航空レーダの模擬および航空管制レーダの模擬を行う分散シミュレーションシステムに利用可能である。
【符号の説明】
【００２４】
１０１；ＲＴＩ、１０２；模擬処理、５０１；分散シミュレーション基盤、５０２；イベントリスト、５０３；スケジューリング処理、５０４；スケジューリングリスト。
【図１】
2012008946.tif 000003
【図２】
2012008946.tif 000004
【図３】
2012008946.tif 000005
【図４】
2012008946.tif 000006
【図５】
2012008946.tif 000007
【図６】
2012008946.tif 000008
【図７】
2012008946.tif 000009
【図８】
2012008946.tif 000010