Mercurial > hg > Papers > 2011 > koba-sigss
view presen/sigss-presen.html @ 9:b7b8c6307895 default tip
finish.
author | koba <koba@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 08 Mar 2011 19:17:46 +0900 |
parents | 7e707cabd73a |
children |
line wrap: on
line source
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <title>sig-ss_presentation</title> <!-- metadata --> <meta name="generator" content="S5" /> <meta name="version" content="S5 1.1" /> <meta name="presdate" content="20050728" /> <meta name="author" content="Eric A. Meyer" /> <meta name="company" content="Complex Spiral Consulting" /> <!-- configuration parameters --> <meta name="defaultView" content="slideshow" /> <meta name="controlVis" content="hidden" /> <!-- style sheet links --> <link rel="stylesheet" href="ui/default/slides.css" type="text/css" media="projection" id="slideProj" /> <link rel="stylesheet" href="ui/default/outline.css" type="text/css" media="screen" id="outlineStyle" /> <link rel="stylesheet" href="ui/default/print.css" type="text/css" media="print" id="slidePrint" /> <link rel="stylesheet" href="ui/default/opera.css" type="text/css" media="projection" id="operaFix" /> <!-- S5 JS --> <script src="ui/default/slides.js" type="text/javascript"></script> </head> <body> <div class="layout"> <div id="controls"><!-- DO NOT EDIT --></div> <div id="currentSlide"><!-- DO NOT EDIT --></div> <div id="header"></div> <div id="footer"> <h1>[date:11/03/08]</h1> <h2>GameFrameWork Cerium におけるSequential な Game Program の分割と動作の検証</h2> </div> </div> <div class="presentation"> <div class="slide"> <h1>GameFrameWork Cerium における<br> Sequential な Game Program の分割と<br> 動作の検証</h1> <h3>小林 佑亮</h3> <h4>多賀野 海人 金城 裕 河野 真治</h4> <h4>琉球大学 理工学研究科 並列信頼研究室</h4> </div> <!-- <div class="slide"> <h1>発表内容</h1> <ol> <li>序論</li> <li>Cell BE と Cerium</li> <li>ゲームプログラミングにおけるテスト</li> <li>テスト対象のシューティングゲーム Super Dandy</li> <li>構築したテスト環境</li> <li>テスト環境によるデバッグと検証</li> <li>まとめ</li> </ol> </div> --> <div class="slide"> <h1>研究要旨</h1> <font size="3"><ul> <li>当研究室のPlayStation3用マルチコア並列ゲームフレームワーク Cerium ではプログラムをTaskという単位に分割して並列処理を行う。 <li>Ceriumに既存の逐次型のゲームを移植すると、Taskの並列実行による非決定的な実行により、同じ動作にならない場合がある。 <li>ゲームプログラムにはプレイヤーの入力や乱数などの非決定的要素が元々入っており、単純な動作比較ではうまくいかない。 <br> <li>本研究ではプログラムの実行ログを取得し移植時の動作の比較を行う。 <li>そのために入力と乱数による非決定的な要素の固定化を行った。 <li>並列実行はCeriumのFifo実行機能を用いて決定的な動作を実現した。 <br> <li>Super Dandyというシューティングゲームに本方法を適用し実用的な時間内での動作比較を行うことができた。 </ul></font> </div> <!-- <div class="slide"> <h1>Cell Broadband Engine</h1> <center> <img src="images/cell.png" width=350 height=150/> </center> <ul class="simple"> <li>SCE と 東芝、IBM によって開発されたCPU</li> <li>2 thread の PPE(PowerPC Processor Element) と 8 個の SPE(Synergistic Processor Element)を持つ</li> <li>各 CPU 間は高速リングバスであるEIB(Element Interface Bus)で 繋がっている</li> </ul> </div> <div class="slide"> <h1>Game Framework Cerium</h1> <h2>プログラムを Task と呼ばれる分割された単位で管理する</h2> <ul> <li>Task の単位はサブルーチンまたは関数とする</li> <li>Task には依存関係や処理させる CPU などを設定することができる</li> <li>生成された Task を依存関係を考慮しながら Cell B.E に送る</li> </ul> <br> <h2>独自の RenderingEngine により、Task を用いた描画処理を行うことが出来る</h2> </div> <div class="slide"> <h1>Game Framework Cerium</h1> <dl> <b><dt>SceneGraph</dt></b> <dd>オブジェクトのパラメータやポリゴン情報を tree 構造のノードで管理</dd> <b><dt>Rendering Engine</dt></b> <dd>3 種類の Task によって並列に描画処理を行う</dd> <b><dt>TaskManager</dt></b> <dd>Task を動的に SPE へ割り振るカーネルとして振舞う</dd> </dl> </div> <div class="slide"> <h1>Task に設定できる項目</h1> <ul class="simple"> <li>Task 内で処理するデータ</li> <li>処理したデータの出力先</li> <li>Task を実行する CPU</li> <li>Task 同士の依存関係</li> <li>Task 終了時に実行する関数</li> </ul> </div> <div class="slide"> <h1>CppUnit</h1> <ul class="simple"> <li>xUnit と呼ばれる単体テストのためのフレームワークの内の 1 つ</li> <li>単体テストとは関数やメソッドなどの比較的小さな単位で行うテストで、 モジュールへの入力と出力を調べることでそのモジュールが要求された仕様を 満たしているかをテストする手法</li> <li>CppUnit は 1 つの事象に対して様々なテストケースを同時にテストできる</li> <li>羅列したテストケースは一括で実行と結果表示が出来る</li> <li>しかしこうした単体テストではゲームプログラムのバグを見つけるのは難しい</li> </ul> </div> <div class="slide"> <h1>ゲームに対する単体テストの欠点</h1> <ul> <li>単体テストは瞬間的な値の正しさは調べられる</li> <li>しかし常にオブジェクトのパラメータが変化するゲームには有効的ではない</li> <li>ゲームのバグは他のオブジェクトのパラメータとの関係により発生するものが 多い</li> <li>一般的な単体テストではゲームのバグの発見は難しい</li> </ul> </div> <div class="slide"> <h1>ゲームプログラムの特徴</h1> <ul class="simple"> </ul> </div> <div class="slide"> <h1>プレイヤーの入力の不定性</h1> <ul class="simple"> <li>プレイヤーの入力は常に非決定的(毎回結果が異なる)</li> <li>同じ人間が同じゲームの同じ場面をプレイしても全く同じ入力をする可能性 は極めて低い</li> <li>プレイヤーは制御不能なランダム要素</li> <li>テストにおけるバグの再現性を低下させている</li> </ul> </div> <div class="slide"> <h1>ゲームにおける乱数の役割</h1> <ul class="simple"> <li>オブジェクトの振る舞いに多様性を持たせる</li> <li>ランダムな位置配置に使われる</li> <li>乱数のランダム性はデバッグをする上でバグの再現を困難にする</li> <li>対処法としては、乱数生成器を無効にするか、定数でシードする</li> </ul> </div> --> <div class="slide"> <h1>シューティングゲーム Super Dandy</h1> <table> <tr> <td> <font size="4"><ul class="simple"> <li>PS2上の全5 ステージのボリュームのあるシューティングゲーム <li>PS3上に移植する際にTask分割して並列実行を行うようにする <li>ゲームオブジェクトはSceneGraph上に以下のState Patternを用いて構築されている <li>State Pattern一つ一つをTaskとして実装する <ul> <li>オブジェクトの移動(Move) <li>衝突判定(Collision) <li>ステージ毎のオブジェクト生成(Schedule) </ul> </ul></font> <td> <img src="images/dandy.png" width=300 height=250/> </table> </div> <div class="slide"> <h1>ゲームプログラムの特徴</h1> <table> <tr> <td> <ul class="simple"> <li>自機や敵機、弾丸などの様々な種類のオブジェクトがある</li> <li>プレイヤーの入力により、自機が移動したり弾丸オブジェクトが生成されるなど、ゲームに影響を与える</li> <li>オブジェクト同士が衝突したり、生成されることでゲームの状態が変化する</li> <li>プレイヤー入力、乱数などの非決定的な要素により、テストの再現性が低下する</li> </ul> </td> <td> <img src="images/game.png" width=300 height=300/> </td> </tr> </table> </div> <!-- <div class="slide"> <h1>Super Dandy 移植の利点</h1> <ul class="simple"> <li>全 5 ステージという、ある程度のボリュームのあるゲーム</li> <li>衝突判定やオブジェクト判定、ステージクリアによるシーン切り替えと、基本的なゲームの要素が入っている</li> <li>動作結果を過去の環境と比較することによる新たな環境のチューニングができる</li> </ul> </div> --> <!-- <div class="slide"> <h1>Super Dandy のデータ構造</h1> <dl> <b><dt>player</dt></b> <dd>プレイヤーの操作する機体。xy 座標、残機数、無敵時間、 コンテニュー回数などを持つ。</dd> <b><dt>CHARACTER</dt></b> <dd>敵機や敵の弾。xy 座標とその方向の速さ、体力、倒したときのスコア、 オブジェクトの種類を表すキャラナンバーを持つ。</dd> <b><dt>BULLET</dt></b> <dd>プレイヤーが撃った弾。xy 座標をもつ。プレイヤーが射撃ボタンを押すと 弾が配列に格納され、敵に当たるか画面外にいくと消滅する。</dd> </dl> </div> <div class="slide"> <h1>Task Dandy(Super Dandy Task version)</h1> <table> <tr> <td><ul class="simple"> <li>オブジェクトの Move や Collision を Task 化</li> <li>オブジェクトの描画は Cerium による Task を用いた描画処理</li> <li>SuperDandy のコードやデータ構造を流用</li> </ul></td> <td> <img src="images/taskdandy.png" width=250 height=250/> </td> </tr> </table> </div> --> <div class="slide"> <h1>目標とするテスト環境</h1> <ul class="simple"> <li>オブジェクトの生成時と衝突判定して状態変化した時にログを取る <li>Move時にはログを生成しないのでログの量を抑えることが出来る <li>プレイヤーの入力や乱数などの非決定的な要素を固定する <li>移植前後の動作の違いを確認する <li>移植後の逐次実行時と並列実行時による動作の違いを確認する <li>Graphicsを表示しない高速なテストを可能にする </ul> </div> <!-- <div class="slide"> <h1>出力されるテストログ</h1> <center> <font size="4"> <div style="border :2px solid #000000"><pre> F64: CREATE [NAME]enemy_greenclab_0 [COORD]x= 120.000000 y= -128.000000 vx= 0.000000 vy= 4.000000 F85: DELETE [NAME]enemy_greenclab_0 [COORD]x= 120.000000 y= -44.000000 vx= 0.000000 vy= 4.000000 [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 </pre></div></font> </center> <font size="3"><dl class="simple"> <b><dt>F64, F85</dt></b> <dd>生成、被弾した時の経過フレーム</dd> <b><dt>CREATE, DELETE</dt></b> <dd>CREATE はオブジェクトの生成、DELETE はオブジェクトの被弾</dd> <b><dt>NAME</dt></b> <dd>オブジェクトの種類と ID</dd> <b><dt>COORD</dt></b> <dd>オブジェクトの xy 座標と速度</dd> <b><dt>BULLET</dt></b> <dd>その瞬間に画面内に存在した弾丸の数。</dd> </dl></font> </div> --> <!-- <font size="3"><ul class="simple"> <li>逐次処理では弾の動く処理の後、敵オブジェクトが動く</li> <li>敵オブジェクトが動く前に被弾したため、敵オブジェクトは削除される</li> <li>逐次処理と異なり、並列処理では、敵オブジェクトの処理が弾の動く処理より先に行われる場合がある</li> <li>逐次実行では削除されるはずの敵オブジェクトがそのまま生存する</li> </ul></font> </div> <div class="slide"> <h1>並列処理によるバグ その2</h1> <center> <img src="images/parallel_bug2.png" width=300 height=150> </center> <font size="3"><ul class="simple"> <li>敵オブジェクトと発射した弾の衝突判定が行われる</li> <li>逐次実行では敵と弾が衝突したとき、逐次的に両方のオブジェクトの消滅処理が行われる</li> <li>並列処理では敵と弾が衝突したとき、同時に別の敵オブジェクトの衝突判定も行われる</li> <li>このオブジェクトは弾との衝突判定を行い、削除される</li> </ul></font> </div> --> <div class="slide"> <h1>プレイヤー入力の固定化の実装</h1> <center> <img src="images/cap_trace.png" width=300 height=150> </center> <font size="3"><ul class="simple"> <li>プレイヤーからの入力を 1 フレーム毎に記録する</li> <li>書き出したファイルを読み込むことで過去のプレイヤー入力を再現できる</li> <li>旧バージョンの入力を記録し、新バージョンで読み出すことができる</li> <li>入力が同じでも動作が違えばそこにバグが潜んでいると考えられる</li> </ul></font> </div> <!-- <div class="slide"> <h1>テスト環境における描画処理</h1> <table> <tr> <td><ul class="simple"> <li>Cerium を用いたゲームでは画面バッファの確保、描画用の Task の生成により画面を描画する</li> <li>プレイヤーの入力の固定化とテストログ出力により画面描画を行わずにテストができる</li> <li>描画用 Task や画面バッファの生成処理を行わない事により、テストの高速化ができる</li> </ul></td> <td> <img src="images/video2.png" width=300 height=300/> </td> </tr> </table> </div> --> <!-- <div class="slide"> <h1>バグの検出方法</h1> <ul class="simple"> <li>SuperDandy でプレイヤー入力を記録</li> <li>記録された入力を用いて TaskDandy を実行</li> <li>各バージョンで得られたテストログを比較</li> <li>テストログの違いにより、バグの発生している箇所を特定</li> </ul> </div> --> <div class="slide"> <h1>並列処理によるバグ</h1> <font size="3"><table> <tr> <td><ul class="simple"> <li>逐次処理と異なり、並列処理では、敵オブジェクトの処理が弾の動く処理より先に行われる場合がある</li> <li>逐次実行では削除されるはずの敵オブジェクトがそのまま生存する</li> </ul></td> <td> <center> <img src="images/parallel_bug1.png" width=300 height=150> </center> </td> </tr> <tr> <td><ul class="simple"> <li>並列処理では敵と弾が衝突したとき、同時に別の敵オブジェクトの衝突判定も行われる</li> <li>逐次実行では生存するはずの敵オブジェクトが削除される</li> </ul></td> <td> <center> <img src="images/parallel_bug2.png" width=300 height=150> </center> </td> </tr> </table></font> </div> <div class="slide"> <h1>並列処理のバグを検出するタイミング</h1> <font size="4"><ul class="simple"> <li>ゲームの並列処理によるバグは主に衝突判定時に検出できる</li> <li>ゲームプログラムの状態が遷移する時、バグが検出される</li> <li>ゲームの状態が遷移する時(オブジェクトの削除・生成)、テストログを書き出すことにより、 並列処理のバグを洗い出す</li> </ul></font> <br> <center> <font size="3"> <div style="border :2px solid #000000"><pre> F64: CREATE [NAME]enemy_greenclab_0 [COORD]x= 120.000000 y= -128.000000 vx= 0.000000 vy= 4.000000 F85: DELETE [NAME]enemy_greenclab_0 [COORD]x= 120.000000 y= -44.000000 vx= 0.000000 vy= 4.000000 [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 </pre></div></font> </center> </div> <div class="slide"> <h1>SuperDandyの逐次実行と並列実行の比較</h1> <font size="3"><div style="border :2px solid #000000"><pre> super dandy >> F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000 ... [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 F117: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= 40.000000 ... [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 << task dandy F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000 ... [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 F109: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= -24.000000 ... [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 </pre></div></font> <ul class="simple"> <li>逐次実行時に別フレームで死んだ2つの敵オブジェクトが並列処理では同フレームで死亡</li> <li>片方が死んだ後、弾丸のオブジェクトの除去がされてない</li> <li>各オブジェクトのCollision Taskの間で弾丸データの同期が取れていない</li> </ul> </div> <div class="slide"> <h1>Collision Task間でのデータの同期</h1> <table> <tr> <td><ul class="simple"> <li>予め衝突判定に必要なデータをCPUに送っておく</li> <li>Collision Taskを同じCPUに送る</li> <li>Taskで送られたデータを用いて衝突判定を行う</li> <li>同じCPU上なのでCollision Task間でパラメータの共有ができる</li> </ul></td> <td> <img src="images/collision_uml.png" width=300 height=300/> </td> </tr> </table> </div> <div class="slide"> <h1>Collision Task の改良後の比較</h1> <font size="3"><div style="border :2px solid #000000"><pre> super dandy >> F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000 ... [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 F117: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= 40.000000 ... [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 << task dandy F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000 ... [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 F117: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= 40.000000 ... [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 </pre></div></font> <ul class="simple"> <li>2 つのバージョンにおけるオブジェクトの衝突判定が一致している</li> <li>また、弾丸オブジェクトの個数も一致している</li> <li>Collision Task のデータ同期が正しく行われていることがわかる</li> </ul> </div> <div class="slide"> <h1>ゲーム内の乱数のテストへの影響</h1> <div style="border :2px solid #000000"><font size="2"><pre> int sf = random() % 4; if((sf == 0) || (sf == 1)) { p->x = -35; p->y = random() % (120 - 35); p->vx = (random() % 4 + 1); p->vy = random() % 3 + 1; p->state = chara_state23; } if((sf == 2)) { ..... } if(sf == 3) { ..... </pre></font></div> <ul class="simple"> <li>乱数によって決定される条件式を持つ <li>乱数を固定化すると、テストのカバレッジが不十分になる可能性がある <li>Taskが逐次実行と並列実行で異なる乱数を使用する場合があり、テストの再現性がなくなる </ul> </div> <div class="slide"> <h1>PS3での予測可能な乱数の使用</h1> <table> <tr> <td><font size="4"><ul class="simple"> <li>シーケンシャルなゲームプログラムでは 1 つの乱数列から順番に乱数を取得</li> <li>PS3におけるTaskによる並列実行では各CPU内で独自の乱数列を生成</li> <li>逐次実行と並列実行で異なる乱数を使用するので、実行した結果が異なる</li> </ul></font></td> <td> <img src="images/spe_random.png" width=350 height=250/> </td> </tr> </table> </div> <div class="slide"> <h1>PS3での予測可能な乱数の使用</h1> <table> <tr> <td><ul class="simple"> <li>あらかじめメインのCPU内で乱数列を生成しておく</li> <li>Taskを生成した際に列から乱数を取得し、渡しておく</li> <li>Taskの生成タイミングはSuper DandyのMoveやCollisionと同じ</li> <li>Super Dandyと同じ乱数が使用できる</li> </ul></td> <td> <img src="images/spe_random.png" width=350 height=250/> </td> </tr> </table> </div> <div class="slide"> <h1>実行結果</h1> <div style="border :2px solid #000000"><font size="3"><pre> super dandy >> [ID]1 [COORD]x= -35.000000 y= 20.000000 vx= 3.000000 vy= 1.000000 ... [ID]6 [COORD]x= 220.000000 y= -30.000000 vx= 1.000000 vy= 4.000000 ... [ID]11 [COORD]x= -35.000000 y= 57.000000 vx= 3.000000 vy= 3.000000 ... << task dandy [ID]1 [COORD]x= -35.000000 y= 20.000000 vx= 3.000000 vy= 1.000000 [ID]6 [COORD]x= 220.000000 y= -30.000000 vx= 1.000000 vy= 4.000000 [ID]11 [COORD]x= -35.000000 y= 57.000000 vx= 3.000000 vy= 3.000000 ... </pre></font></div> <ul class="simple"> <li>同一のIDを持つオブジェクト同士では、座標や速さの値が一致している</li> <li>Taskへの乱数受け渡しによる固定化が行われている</li> <li>乱数による条件分岐におけるカバレッジのカバーができている</li> </ul> </div> <!-- <div class="slide"> <h1>乱数受け渡しによる実行結果の検証</h1> <ul class="simple"> <li>生成された隕石オブジェクトのパラメータが両バージョンで一致している</li> <li>Task への乱数受け渡しによるバグの再現性の低下防止は有効である</li> </ul> </div> --> <div class="slide"> <h1>描画の有無による実行時間の比較</h1> <font size="4"> <h2>プレイヤー入力の固定化により描画処理を省略し、テストを高速に行うことができる</h2> </font> <center> <table border="1" cellspacing="0"> <tr><td></td><!--<th>SuperDandy</th>--><th>描画有り</th><th>描画無し</th></tr> <tr><th>実行時間</th><!--<td>336.09 sec</td>--><td>6643.16 sec</td><td>385.17 sec</td></tr> </table> </center> <ul class="simple"> <li>描画を行わないことにより、処理時間が大幅に減少した</li> <li>描画処理 Task の処理時間が非常に大きい</li> <li>Cerium のチューニングにより実行時間は減少する</li> </ul> </div> </ul> </div> <div class="slide"> <h1>まとめ</h1> <h2>本研究では並列環境におけるゲームプログラムのテスト手法を提案した</h2> <ul class="simple"> <li>ゲームにおける非決定的な要素であるプレイヤー入力、乱数生成を固定化し、 Single Trace の再現性を保証した</li> <li>ゲームの状態遷移時においてテストログを出力することにより、 シーケンシャルなプログラムを Task に分割し、並列実行した時に 発生するバグを検出、修正した</li> </ul> </div> <div class="slide"> <h1>今後の課題</h1> <ul class="simple"> <li>プログラムのカバレッジのカバー、およびカバー率の測定を行う <li>ゲームの状態遷移を数え上げることにより、ゲームの動作全体の比較を可能にする</li> </ul> </div>