近年の計算機、ネットワークシステムの大規模化、高速化に伴い、これらのシステムの設計、評価に用いられるシミュレーションにも多大な時間を要するようになってきている。この種のシミュレーションは、気象シミュレーションのように流体(大気)の運動を連続的に追跡するのではなく、通信システムにおけるパケットの交換機への到着といった特定の"瞬間"のみに着目して、その事象によるシステムの内部状態の変遷を追跡するものである。このような離散事象シミュレーション(Discrete Event Simulation;DES)の並列化による高速化の研究は数多くなされている。それらの多くは、対象とする系のモデルを並列に動作するサブモデルに分割し、それ等を模擬する論理プロセス(Logical Process;LP)を物理プロセッサ(Physical Processor;PP)に分割して同期を取りながら実行を進めるものである。 こうした並列DES(Parallel DES;PDES)の研究の歴史は十数年にもなり、LP間同期プロトコルの最適化、同期機構を実現するライブラリや言語処理系、逐次シミュレーションプログラムの自動並列化等、様々な手法が提案されてきた。にもかかわらず、DESの並列化には、未だハードウェアやプロトコル同期機構等の低レベルの知識とプログラミングの習熟が必要なのが現状である。PDES研究グループと一般のDESを行っている人々との間の認識の隔たりに関する懸念は、今に始まったことではない。PDESはDESを高速化するための唯一の手段ではないが、それでもなお、筆者は他のアプローチ(importance samplingや分散(variance)の削減等)よりも第一原理に忠実にプログラミング出来る点で、最も直感的な方法であると考える。 本論文では、はじめにPDESの基本概念について述べ、続いて当該研究分野の最近の技術進歩について概観する。次に、5年前に主要な研究者から提起されたPDESの生き残りに関する問題に対する取り組みについて述べる。 残りの章では、これらの議論を踏まえ問題点に対するいくつかの側面からの解決手法を提案する。 1 楽観的同期方式における状態管理 LP間の楽観的同期方式のひとつであるタイムワープは、LP間の同期を緩め、因果関係の不整合が生じた時点でその回復処理を行うもので、楽観性をうまく制御することによりモデルに内在する並列性を十分に引き出す可能性を持つと考えられている。 回復処理を実現するためには、LP毎に内部状態の履歴を保存しておく必要がある。状態管理方式としては、コピーに基づくもの(Copy State Saving;CSS)と、チェックポイント間の状態の差分に基づくもの(Incremental State Saving;ISS)が提案されている。いずれの方式も多くの汎用PDESプラットフォームに組み込まれ、自動化されている。 CSS方式では、ユーザは保存したい状態を状態変数として申告しておくと、プラットフォームは最適なタイミングでそれ等のコピーを保存し、ロールバック時にはロールバック時点の直前の履歴を状態ベクタに書き戻すことにより状態の回復を行う。 ISS方式では、ユーザは状態の変化を取り消す操作を手続きとして申告する。更に実行時には状態の変更を行う際取り消し操作の識別子を申告する。プラットフォーム側では、ロールバックの際その識別子を基に取り消し操作を逐次的に呼び出し、状態を回復する。 通信、計算機システムで多用される待ち行列シミュレーションでは、状態として待ち行列データ構造(キュー)を管理する必要がある。キューは一般にはリンクリストを用いた動的なものであり、CSS方式では直接管理出来ない。一方ISS方式を用いると管理が可能になるが、取り消し操作の記述も容易ではなく、記述法もプラットフォームにより異なるのが現状である。また、ロールバック距離に比例した回復コストを要するという問題もある。 待ち行列シミュレーションで特に良く用いられる先入れ先出しキュー(FIFOキュー)は一旦挿入された要素間の順序変更は起らないため、その性質を利用した最適化が可能である。CSS方式はユーザに対する負担も軽く、FIFOキューが通常の埋め込みデータ構造と同様に扱うことが出来るならば、ISS方式を用いずにFIFOキューを管理することが可能になる。 本論文では、FIFOキューをCSSに基づくプラットフォームで状態変数として実現する、平易なインタフェースを持つC++のクラスライブラリの提案と性能評価を行う。更に多段接続交換網シミュレーションに対する組み込みを行うことにより、実アプリケーションへの適用の容易性と有効性を示す。 タイムワープ方式のプラットフォームは、同期の管理について、回復処理を行うタイミングの決定等の機能を共通して実現している。本論文では更に、こうした機構によるCSS方式のプラットフォームの状態管理機構をそのまま用いてISSを支援する一般的な枠組みについて提案する。 2 統計出力解析 DESでは、対象とする系を設計や評価に適した形で模擬し、効率よく実行するのみならず、実行途中の動作や設計/評価に必要な指標(統計量)を、必要な精度と分析者が処理しやすい形式で出力する機能を備えていなければならない。特にPDESでは、LPから個々に出力されるデータの効率よい収集/平均等所望の形式への変換が望まれる。 ところでDESは出力解析の観点からは、ある時点での系の状態を対象とするTerminating Simulationと、系の定常状態を対象とする定常状態シミュレーションに大別することが出来る。前者は終了時刻或はイベントが予め与えられるものであり、多くのPDESプラットフォームも予め終了時刻を与えるものである。一方、後者では系の定常状態での統計量が所望の精度で得られる時刻を予め決定することが出来ず、バッチ平均法等の精度判定機構としばしばそれによる停止処理が必要である。しかし、PDESではこうした研究は稀であり、そのような機構を備えた汎用PDESプラットフォームも筆者の知る限り存在しない。 本論文では上記を踏まえ、定常状態シミュレーションの統計出力解析手法のひとつであるバッチ平均法をPDESに組み込む枠組みを提案する。本枠組みは、ひとつのバッチを構成する出力データの収集方法の違い(仮想時刻に基づく手法とサンプル数に基づく手法)による精度の違いに関する検討、プロトコル毎の組み込み手法の相違、実装のレベルの相違(OSのプロセスレベル、プラットフォームレベル、イベントレベル)に関する検討より成る。 3 LPのスケジューリング機構 PDESにおいて、一般に、LPの数とPP数は異なるため、通常単一のプロセッサが複数のサブモデルをシミュレートする。この場合、複数のLP間での実行順序の解決(スケジューリング)が必要となる。 スケジューリング手法の一つとして、LPが持つ事象リストの先頭要素のタイムスタンプの小さい順に制御を移す最小時刻印法(Least Time Stamp First;LTSF)がある。また、保守的プロトコルの場合、LP内での送信元毎の外部イベント間のスケジューリングも必要である。 これ等のスケジューリングのために用いるプライオリティキューの実装方式として、最高優先度の要素の取り出し、要素の挿入が高速に行えるよう様々な方式が提案されている。 上記のスケジューリングの場合、LP数が変化しない限り要素の数が一定で、各要素が優先度を上下させるという特徴があり、こうした特徴を生かした効率よい実装としてトーナメント形式のデータ構造が提案されている。このデータ構造を用いると、要素の優先度の変更が平均で定数コストで済むが、LTSFスケジューリングのような最高優先度の要素の変更は木構造の根から葉まで全て再評価する必要があるため、常にO(logN)のコストが必要である。このような問題は、二進木構造を持つヒープを用いて解決することが出来る。 本論文では、提案するヒープ型と従来のトーナメント型の両データ構造のC++クラスライブラリによる実装について述べ、両者の性能比較を行うとともに他の関連研究との比較を行い、最後に楽観的プロトコルへの適用についての方向性を述べる。 4 LP移送による通信の最適化 PDESプログラムは外部イベントの交換のため極めて通信集約的であり、LP間通信が全体の性能に与える影響は大きい。LP間の通信パターンと、PP間の結合トポロジとの間で何らかの整合を取ることによって、PP間の結合ネットワークに対する負荷を軽減させ、性能向上を図ることが出来る。PDESは行列計算のような比較的規則性の強い科学技術計算と異なり、静的な通信パターンも実行時の動特性もより複雑であり、最適なLPからPPへのマッピングを求めることは非常に困難である。例えば、実際のIPルータでは、入力されるパケット数のポート間の偏りは時間とともに変化するだろう。 更に、今日のマルチユーザに対応した並列計算機においては、PP網の中の有限集合を実行時に割り付けられることになる。このような場合は、たとえLP間通信パターンが静的であっても最適なマッピングはコンパイル時には決定出来ないため、マッピングの決定は実行時に適応的に行われることが望ましい。 LPの動的マッピングを実現するためには、LPの実行時のPP間の移送機構が必要である。また、移送に関して何らかの基準を設け、プログラムが最適な動作点の近くで安定することを保証することが必要である。 本論文では、LP間の通信のPP間網に対する負荷をモデル化し、それを最小化するようにLPを移送しながら漸近的に最適な割り当てに近づけて行く枠組みを提案する。SR2201の採用しているようなハイパクロスバーネットワークでは、軸の乗り換え回数が主なコストとなるが、本枠組みにより2×2単位スイッチの4段構成のBanyan-Switch網を単純にマップした場合の乗り換え回数を1/3に削減することが出来た。 |