（様式 20）成果報告書

TSUBAME 共同利用 平成 27 年度 学術利用 成果報告書

GPU 上での離散イベントシミュレーション実行に向けた基礎的検討
A Fundamental Study on Parallel Discrete Event Simulations on GPUs
大原 衛
Mamoru Ohara
地方独立行政法人東京都立産業技術研究センター
Tokyo Metropolitan Industrial Technology Research Institutehttp://www.iri-tokyo.jp/
本研究は、GPU を用いた並列離散イベントシミュレーション（PDES）の高性能化、高信頼化を目的とする。
本課題では、PDES の高信頼化のための基礎的検討として、ソフトウェア若化の PDES への適用を試みた。ソフトウェア若化は、ソフトウェアの除去困難なバグに対する高信頼化手法である。本研究では、楽観的な PDES手法であるタイムワープ手法にソフトウェア若化を適用する手法を提案する。著者らは以前に提案手法の信頼性解析モデルを構築した。本課題では、実際に MPI（Message Passing Interface）を用いたタイムワープシミ
ュレータを実装し、解析モデルで用いる諸パラメータの計測を行った。
In this study, we introduced software rejuvenation into parallel discrete event simulations (PDES)
as the basis for the preparation of using GPUs in PDES. Software rejuvenation is a promisingtechnique that avoids failures caused by hard-to-fix bugs in software. We previously proposed anumber of software rejuvenation schemes for time warp technique, which is one of optimistic
synchronization techniques used in PDES, and developed an analytical model for evaluating system
reliability. Moreover, we implemented an experimental simulator using MPI (Message PassingInterface) on TSUBAME and measured parameters of the analytical model. In this article we report
the measurement results.

Keywords: parallel discrete event simulation (PDES), time warp simulation, software rejuvenation,
analytical model, message passing interface (MPI)

背景と目的が 行 わ れ て い る ． 実 用 的 に も ， い く つ か の MPI

近年，GPGPU（General Purpose processing on（Message Passing Interface）実装では，ハードウェ

GPUs）を用いた連続系シミュレーションの高速化は広アの故障を検出し，他のノードで代替するなどの方策く取り組まれているが，離散イベントシミュレーションが採られている．一方，ソフトウェアの問題，いわゆる（Discrete Event Simulation: DES）の並列化を試みバグの発現に対しては，既存の MPI 実装では対応でた事例は報告が少ない．DES の応用は待ち行列やネきない．近年，除去が困難なバグへの対応法として，予ットワーク，論理回路シミュレーションなど幅広く，これら防的にソフトウェアを再起動するソフトウェア若化法の分野でも並列化による性能の向上が強く求められて（software rejuvenation）が用いられ始めている．これいる．本研究は，GPGPU を用いた DES の性能向上をは従来，主にエンタープライズ用途で用いられてきたが，目的とする．

HPC（High Performance Computing）に対しても適多数の計算ノードを用いた大規模シミュレーションで用する試みが為されている．申請者らも，楽観的手法は，これらのノード間で同期を行いながら処理を進める．

に対してソフトウェア若化を適用するための基礎的な検このため，一部のノードの故障や通信遅延によって，シ討を行っている．本利用課題では，著者らが先行研究ミュレーションの進行が停滞する可能性を考慮しなけれで構築した解析モデルの検証を主な目的として，ばならない．本課題では，このような耐故障技術を確立

TSUBAME 上で DES の実稼働データを取得する．

するための基礎的な検討を行う．

TSUBAME を利用することで現実的な規模の数値例

ハードウェアの故障に対してはこれまでに多くの研究を得ることが本年度における利用の目的である．

（様式 20）成果報告書
ロセスの処理の進行が大きく異ならないようにすることが重要である．

概要
申 請 者 ら は 以 前 に ， 並 列 DES （ Parallel DES:

ソフトウェア若化を行う際にも，一部のプロセスの進PDES）の楽観的同期手法であるタイムワープ手法に行が妨げられることは避けなければならない．この目的

ソフトウェア若化を導入する単純な手法を提案し，そので，本研究の提案手法では，システム中のすべてのプ信頼性解析モデルを構築した．本課題では，具体的なロセスが同期的に若化を行う．タイムワープ手法では，PDES プログラムを実装し，これを用いて解析モデル大域的な時刻であるグローバルバーチャルタイムのいくつかのパラメータを実測した．以下ではまず，申（Global Virtual Time: GVT）を定期的に求める．この請者らが提案するソフトウェア若化法と信頼性解析モための分散アルゴリズムとして，同期的なものと非同期デルについて概説する．

的なものが提案されている．提案手法では，同期的DES では，一連のイベントを定められた順番で処理する必要がある．タイムワープ手法では，各プロセスはGVT 計算アルゴリズムを仮定し，ソフトウェア若化はGVT 計算の直後に行う．

明示的な同期を行わず，独自にイベントの実行を進めシステムは時間 T ごとに GVT 計算を行う．また，kる．このため，システム全体の視点では，イベントが正回の GVT 計算を行うごとに連携チェックポインティングしい順序で実行されない場合がある．各プロセスは，誤を行う．チェックポインティングが完了すると，すべてのった順序でイベントが実行されたことを検知すると，そプロセスが再起動し，チェックポイントデータを読み込んのイベントを実行する以前の状態にロールバックする．

で状態を再構築する．その後，すべてのプロセスの状プロセス間の情報の共有は，メッセージ交換によって態再構築を待ち合わせて，シミュレーションを再開す行う．メッセージには，イベントを実行すべき論理時刻る．

がタイムスタンプとして付加される．また，各プロセスは，GVT 計算間隔 T やソフトウェア若化周期 k が大きく，自身が実行した最後のイベントの論理時刻をローカルソフトウェア若化が稀にしか行われない場合には，バグクロックとして保持する．プロセスは，他のプロセスからが発現しプロセスに障害が発生する可能性がある．連メッセージを受信すると，そのタイムスタンプとローカル続する 2 回のソフトウェア若化の間にいずれかのプロセクロックの値を比較する．ローカルクロック以前のメッセ

スに障害が発生したとき，障害プロセスはまず再起動ージが到着した場合には，イベントが誤った順番で処を行い，次いで直前のチェックポイントデータを読み込理された可能性があるため，ロールバックを行う．このむ．タイムワープ手法では，以前の状態に復帰した障ため，効率的なシミュレーション実行のためには，各プ害プロセスからの古いタイムスタンプを伴ったメッセー

図 1 タイムワープ手法のローカルクロック（LVT）, GVT の進行

（様式 20）成果報告書
表 1 記法ジによって，他の正常なプロセスでロールバックが発生することが想定される．これを防ぐために，障害プロセA

可用性

スはチェックポイントデータを読み込んだ後に，他のすS連続する 2 回の若化の時間間隔べてのプロセスに特別なメッセージを送信する．このメH

S のうち若化と障害によるオーバヘッドッセージを受信したプロセスは，シミュレーションの実行

U

S のうち障害が発生しない場合のオーバヘッドを中断する．

X

直前のソフトウェア若化から障害発生時点まで他のプロセスから受信したすべてのメッセージを処理の間隔し状態の回復を完了すると，障害プロセスはこれを他R(X)

障害で失われたイベントの再実行時間の全プロセスに通知する．PDES の多くの応用では，

F

X の確率分布関数

すべてのプロセスが同じソフトウェアを実行する．この

N

プロセス数

FN

N 個のプロセスに最初に発生する故障の確率ため，一つのプロセスに障害が発生した際には，他のプロセスにおいても障害が発生しやすい状態であることが予想される．本手法では，障害プロセスからの状態回復の通知を受信すると，ソフトウェア若化を行い，すべてのプロセスを再起動する．
提案法を用いたシステムの非可用性は，以下のように表される．ただし，解析モデルで用いる記法を 表 1にまとめた．
H
�= ,
AS

kT

H = � {t c + t r + R(x) + t c + t r + t c }dFN + U,
0kT

S = � {x + t r + t c + R(x) + t c + t r + t c }dFN + U,
0∞

U = � {t c + t r + t c }dFN ,kT

x
R(x) =.
α + (1 − α)β

結果および考察
以下の手順でソフトウェア若化を行い，諸パラメータの計測を行った．
1.

ドライバスクリプトが MPI プログラムを起動する．

2.

システムは k 回の GVT 計算を行う．

3.

各プロセスは，チェックポイントを 2 次記憶に書き込む．

4.

MPI プログラムが終了する．

分布関数
T

GVT 計算間隔k

ソフトウェア若化周期tc

チェックポイント生成・読込時間

tr

プロセス再起動時間

α

1 イベント当たりのロールバック発生率

β

1 回のロールバックによって失われる平均イベント数
5.

ドライバスクリプトは，MPI プログラムが終了す
ると，MPI プログラムを即座に再起動する．

6.

各プロセスが 2 次記憶からチェックポイントデー
タを読み込む．

手順 3，6，および 3—6 の所要時間をそれぞれ計測
し，3—6 の所要時間から 3，6 の所要時間を減ずることで tr を求めた．
計測結果を以下に示す．シミュレーションモデルは，
WARPED2 と と も に 公 開 さ れ て い る も の か ら ，“airport”，“traffic” を用いた．airport は，飛行場における飛行機の発着を，traffic は交差点における自動車の往来を模擬する．両モデルで，オブジェクト（空港または交差点）は，X-Y 格子状に 100×100 個を配置し，10,000 論理時間のシミュレーションを実行した．

表 2 から，各シミュレーションモデルに対して，プロセス数 N の最適値があることが分かる．N が小さいときにはαが大きく，ロールバックが発生しづらい．一方，シミュレーション時間は長く，並列効果が十分に得られていないと言える．反対にプロセス数が多すぎると，ロー（様式 20）成果報告書ルバックの頻度が高くなり，シミュレーションの効率が低くなることが予想される．ソフトウェア若化周期 k が小さ下する．

いときには，この傾向が見られる．また，k が大きくなる

上述のソフトウェア若化手順は MPI プロセスの起動を含むため，プロセス数が多ければ再起動時間 tr が長

表 2 イベントコミット率とロールバックによってN

αβ

airport20.9924

trafficN

airport816

traffic

816

まとめ、今後の課題実行時間（秒）プ手法を用いたシミュレータを試験的に実装し，それを10.68

648.8

用いてソフトウェア若化に関する信頼性モデルの諸パ

0.955

13.62

364.5

ラメータの実測を行った．障害の発生しない状況下での80.90713.9923.86

ソフトウェア若化コストなどが計測された．

160.815

14.19

125.44シミュレータに意図的に故障を挿入することによって，320.929

8.82

42.78

障害が発生した状況における実際の挙動を観察し，計

64

0.359

15.26

215.95測を行うことなどが今後の課題である．

20.998

5.15

100.2

40.980

8.90

48.17

80.981

7.11

23.86

160.975

6.06

11.64

32

0.940

7.04

7.18

64

0.623

10.67

15.36

表 3 ソフトウェア若化コストモデル

明らかでない．

本課題では，楽観的な PDES 手法であるタイムワー

失われる平均イベント数
モデルと tr が長くなる傾向も見られる．この要因については，C (MB)

tc (秒)

10

8.4

1.03

1.08

20

11.2

1.39

1.11

30

14.5

1.85

1.44

40

11.8

1.48

1.63

10

6.70.911.20

20

10.5

1.39

1.22

30

9.7

1.30

1.41

40

10.6

1.40

1.60

10

10.5

1.08

1.02

20

13.0

1.35

1.16

30

12.0

1.24

1.29

40

13.8

1.44

1.37

10

8.5

0.93

1.13

20

10.9

1.17

1.27

30

11.1

1.21

1.21

40

13.5

1.45

1.25

k

tr (秒)