離散事象シミュレーション - yuuk1's Digital Garden

# 離散事象シミュレーション ## 定義離散事象シミュレーション(discrete-event simulation, DES)は、システムの離散状態モデル(discrete-state model)を用いるシミュレーションである。状態変数(state variable、システムの状態を定義する変数)が離散値のみを取り、その値の変化(事象, event)によって時刻が進む。計算機システムでは各デバイスのジョブ数のように状態が離散量で記述されるため DES が主流になる。「離散」は状態変数を指す語であり、時間軸自体は離散でも連続でもよい点に注意が要る(連続状態モデルは連続事象モデルとも呼ばれ、化学系の濃度モデリング等で使われる)(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 24 Introduction to Simulation]] §24.3, §24.5.3)。計算機科学者にとって意味を持つシミュレーションの類型は、静的で時間軸を持たないモンテカルロシミュレーション、実システムの時系列記録(トレース)を入力とするトレース駆動シミュレーション、そして DES の3つに整理される。DES はこれらのうち唯一「事象によって時間が進む動的なシステム挙動」そのものをモデル化する類型であり、モンテカルロシミュレーションが静的な確率現象の評価に、トレース駆動シミュレーションが実ワークロードに基づく資源管理アルゴリズムの比較に向くのに対し、DES は待ち行列・スケジューリングなど事象駆動のシステム挙動全般を扱える汎用性を持つ(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 24 Introduction to Simulation]] §24.5)。 ## 共通構造と事象集合アルゴリズム対象システムによらず、DES は事象スケジューラ・シミュレーションクロックと時間進行機構(単位時間方式対事象駆動方式)・システム状態変数・事象ルーチン・入力ルーチン・レポート生成器・初期化ルーチン・トレースルーチン・動的メモリ管理・メインプログラムという共通構成要素の一部を持つ。汎用言語で実装する場合はすべてを分析者が書く必要があり、SIMULA・SIMSCRIPT・GPSS・GASP のようなシミュレーション専用言語はその一部を提供する(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 24 Introduction to Simulation]] §24.5.3)。これらの構成要素のうち事象スケジューラは最も頻繁に実行される部分であり、未来事象の集合(event set)をどのデータ構造で管理するかが実行時間を支配する。事象集合には「新規事象の挿入」と「最早事象の検索・除去」という2つの頻出操作があり、両者のトレードオフに応じて順序連結リスト(小規模な事象集合に強い)・添字付き線形リスト(カレンダーキューを含む、中規模に強い)・木構造/ヒープ(大規模に強い)が使い分けられる。効率的な事象集合アルゴリズムの実装だけで総プロセッサ時間が最大30%節約された事例が報告されている(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 24 Introduction to Simulation]] §24.6)。 ## 結果の解析(検証・妥当性確認・過渡状態の除去・停止条件) モデルを組み立てて動かせるだけでは DES は完成しない。得られた結果をどう扱うかという後段の手続きが、モデル構築そのものと並ぶもう一つの柱をなす。第一に、モデルの良さは**検証(verification、実装が前提どおりに動くか)**と**妥当性確認(validation、前提が現実を代表しているか)**という独立した2軸で測られ、両軸の詳細な技法群は [[シミュレーションモデルの検証と妥当性確認]] に切り出した。第二に、多くの DES は定常状態の性能だけに関心があるため、初期の過渡状態(transient state)をどこまで捨てるかという**過渡状態の除去(transient removal)**が必要になる。長時間実行・適切な初期化・切り捨て・初期データ削除・独立反復の移動平均・バッチ平均という6手法があり、いずれも「定常状態の変動は過渡状態の変動より小さい」という前提に立つヒューリスティックにとどまる。第三に、シミュレーションをいつ止めるかという**停止条件**は、目標とする信頼区間の幅から逆算して決める。DES の観測は多くの場合、待ち時間のように連続する観測どうしが相関するため、独立観測を前提とした分散の公式がそのまま使えない。独立反復・バッチ平均・再生成(regeneration、システムが初期状態へ戻り以後の履歴に依存しなくなる再生成点で区切る手法)という3手法で、相関のある観測から平均の分散を正しく推定する。定常状態に至らないシステム(終了型シミュレーション、terminating simulation)ではこれらの過渡状態除去は不要になる(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 25 Analysis of Simulation Results]] §25.1-§25.5)。 ## 横断的知見 - **モデル構築の「共通構造」とモデル運用の「結果解析」は、どちらも定型化された手続きへ還元されるが、後者はより多くの手法の使い分けを要求する**: 第24章が示す事象スケジューラ・状態変数・事象ルーチンという共通構造は、事象集合のデータ構造という単一の技術的選択肢(連結リスト/添字付き線形リスト/ヒープ)に整理される。これに対し第25章の結果解析は、検証だけで11、過渡状態の除去だけで6、分散推定だけで3という多数の技法が並立し、どれか一つを選べば済むわけではなく複数を組み合わせて使うことが前提になっている。同じ「定型手続きへの還元」でも、モデルを動かす部分は最適なデータ構造を1つ選ぶ問題に収束するのに対し、結果を解析する部分はヒューリスティックの多層防御(検証の11技法、妥当性確認の3拠り所×3対象、過渡除去の6手法)として設計されている点が対照的である(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 24 Introduction to Simulation]] §24.6, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 25 Analysis of Simulation Results]] §25.1, §25.3, §25.5)。 - **「事象集合の管理コストが実行時間を支配する」という問題設定は35年後もスケールを変えて再出現する**: Jain (1991) は単一計算機上の DES を対象に、事象数20未満なら単純な連結リスト、20〜120なら添字付き線形リスト、それ以上ならヒープが最適という経験則(Reeves 1984、McCormack and Sargent 1979)を示し、事象集合のデータ構造選択という「局所的な最適化」で問題を解決する。一方 [[ネットワークシミュレーション]] が扱う LLM 訓練のパケット単位 DES(PLDES)では、1イテレーションで O(10¹²) の事象が発生し、いかに優れた事象集合データ構造(ヒープ等)を選んでも実行時間がスケールしない規模に達している。Wormhole (NSDI 2026) はこの壁を、事象集合アルゴリズムの改良ではなく、繰り返しパターンの検出によるメモ化・早送りという「事象そのものを生成しない」アプローチで突破する。同じ「事象集合コストがボトルネック」という問題の構造は35年を経ても連続しているが、解法の位相が「良いデータ構造を選ぶ」から「シミュレーションすべき事象数自体を減らす」へと非連続に転換している点が対比として際立つ(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 24 Introduction to Simulation]] §24.6, [[ネットワークシミュレーション]])。 - **「共通構造」に含まれる乱数生成器は、第24章では要素の1つとして触れられるにとどまり、その設計論は第26章に切り出されている**: 第24章はシミュレーションが失敗する8つのよくある誤りの1つに「貧弱な乱数生成器」、もう1つに「シードの不適切な選択」を挙げ、いずれも「自作より広く分析済みの既知の生成器を使うほうが安全(第26章で詳述)」「シード選択の指針は§26.7」と明示的に第26章へ先送りする。第26章はこの約束を、線形合同法(LCG)の周期・質を決める乗数・法の選び方(§26.2)と、マルチストリームシミュレーションのための6項目のシード選択指針(§26.7)として回収する。DESの「共通構造」を構成する要素(事象スケジューラ・状態変数・乱数生成器等)のうち、事象スケジューラの効率化技法は第24章内で完結するのに対し、乱数生成器という要素だけは設計論全体が独立した章に切り出されている点が対照的である。詳細は[[乱数生成器]]に集約した(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 24 Introduction to Simulation]] §24.1, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 26 Random-Number Generation]] §26.2, §26.7)。 ## 未解決の問い - Reeves (1984)・McCormack and Sargent (1979) の事象集合データ構造の実証比較は数十〜数百規模の事象数を前提としている。並列 PLDES(Unison 等)のような並列化された事象集合管理は、本章が示す単一プロセッサ前提の比較(連結リスト/添字付き線形リスト/ヒープ)とどう接続するか、あるいは根本的に別の設計原理を要するか。 - 本章はシミュレーション言語(SIMULA・SIMSCRIPT・GPSS・GASP)を1991年時点の選択肢として比較するが、現代の DES フレームワーク(ns-3・OMNeT++ 等、[[ネットワークシミュレーション]] 参照)がこの4分類(シミュレーション言語/汎用言語/拡張言語/シミュレーションパッケージ)のどこに位置づくかは未検討。 - モンテカルロシミュレーション・トレース駆動シミュレーション・DES という3類型の区分は、ハイブリッド(例: DES の一部にモンテカルロ的乱数評価を組み込む)をどう扱うか。本章は3類型を並列に提示するのみで、組み合わせ方には触れていない。 - 第25章が示す検証・妥当性確認・過渡状態除去・停止条件の技法群は、事象集合アルゴリズムの選択(第24章)と異なりすべてヒューリスティックであり定量的な最適性の基準を持たない。ネットワークシミュレーション(PLDES)のような大規模 DES で、これらのヒューリスティックがどこまでスケールするか(例えば過渡状態の除去の6手法が O(10¹²) 事象規模のシミュレーションでも同様に機能するか)は、現時点でどのソースからも確認できていない。 ## 関連 - source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 24 Introduction to Simulation]] / [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 25 Analysis of Simulation Results]] / [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 26 Random-Number Generation]] - 概念: [[モンテカルロシミュレーション]] —— 静的シミュレーションとの対比。 / [[ネットワークシミュレーション]] —— DES の大規模応用(PLDES)。 / [[状態機械]] —— 状態変数・事象という DES の語彙は状態機械の状態・遷移に対応する具体化。 / [[シミュレーションモデルの検証と妥当性確認]] —— 結果解析の検証・妥当性確認の詳細技法。 / [[乱数生成器]] —— DES の共通構造から切り出された生成器の設計論。 / [[信頼区間]] —— 停止条件が依拠する信頼区間の理論的基盤。 - 実体: [[Raj Jain]] / [[The Art of Computer Systems Performance Analysis]] ## 出典 - Raj Jain, *The Art of Computer Systems Performance Analysis*, John Wiley & Sons, 1991, Chapter 24, §24.3, §24.5, §24.6. - Raj Jain, *The Art of Computer Systems Performance Analysis*, John Wiley & Sons, 1991, Chapter 25, §25.1-§25.5. - Raj Jain, *The Art of Computer Systems Performance Analysis*, John Wiley & Sons, 1991, Chapter 26, §26.2, §26.7.