分散型離散系シミュレーションのためのスケジューリング、マッピング手法の検討

概要

論文の詳細を見る
事象駆動方式の離散系シミュレーションを並列に実行する手法の1つに、生起する事象の管理を各プロセスで分散して行う分散型離散系シミュレーションがある。分散型離散系シミュレーションでは、シミュレーションの対象となる系の構成要素に対応する各プロセスが独立の時刻を持ち、プロセス間の相互作用はメッセージの交換により行われる。メッセージには送受される仮想時刻を示す時刻印が押される。各プロセスにおいては、受け取ったメッセージは仮想時刻の順に処理しなくてはならないのだが、複数のプロセスからメッセージを受け取る場合などはメッセージの到着が仮想時刻の順であるとは限らないため、正当な実行を保証する処理方法が問題になる。この処理方法としては、大きく分けて2種類の方法が提案されている。1つは保守的(Conservative)な方法と呼ばれるもので、受け取ったメッセージよりも古い時刻印を持ったメッセージがもはや到着せず、受けとったメッセージを処理するのが正当であることを保証した上で処理を進める方法である。この方法では、処理の正当性の保証のためのオーバヘッドが大きく、効率の向上は難しいという問題がある。もう1つは楽観的(Optimistic)な方法と呼ばれるもので、メッセージを受け取るととりあえず処理を進め、後でより古い時刻印を持ったメッセージが到着すれば、履歴を用いて状態を復帰するという方法である。この方法では、履歴の管理、状態の回復のオーバヘッドが問題である。本稿では、楽観的な方法について、[Jefferson 85]に示されたVirtual Timeと呼ばれる手法を対象に、マッピング、スケジューリングを工夫することにより、オーバヘッドを低減し、処理の効率を向上させる手法について述べる。
一般社団法人情報処理学会の論文
1990-03-14

分散型離散系シミュレーションのためのスケジューリング、マッピング手法の検討

スポンサーリンク

概要

著者

関連論文

スポンサーリンク