changeset 4:de567168b555

fix.
author koba <koba@cr.ie.u-ryukyu.ac.jp>
date Sun, 13 Feb 2011 21:57:04 +0900
parents 1ca5e8bd0ab8
children be3e93355890
files paper/sigss-paper.pdf paper/sigss-paper.tex
diffstat 2 files changed, 1 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
Binary file paper/sigss-paper.pdf has changed
--- a/paper/sigss-paper.tex	Sun Feb 13 21:09:42 2011 +0900
+++ b/paper/sigss-paper.tex	Sun Feb 13 21:57:04 2011 +0900
@@ -1,1 +1,1 @@
-%% 1. 「論文」
%% v1.6 [2009/11/03]
\documentclass{ieicej}
%\documentclass[invited]{ieicej} % 招待論文
%\documentclass[comment]{ieicej} % 解説論文
\usepackage{graphicx}
%\usepackage{latexsym}
%\usepackage[fleqn]{amsmath}
%\usepackage[psamsfonts]{amssymb}

\setcounter{page}{1}

\field{}
\jtitle{GameFrameWork Cerium における Sequential な Game Program の分割と
  動作の検証}
\etitle{Division and verification of Sequential Game Program
  on GameFrameWork Cerium }
\authorlist{%
 \authorentry{小林 佑亮}{Yusuke KOBAYASHI}{ryukyu}% <= 記述しないとエラーになります
 \authorentry{河野 真治}{Shinji KONO}{ryukyu}
 \authorentry{多賀野 海人}{Kaito TAGANO}{ryukyu}
 \authorentry{金城 裕}{Yutaka KINJO}{ryukyu}
}
\affiliate[ryukyu]{琉球大学 理工学研究科 情報工学専攻 並列信頼研究室}
          {Concurrency Reliance Laboratory, Information Engineering Course,
            Faculty of Engineering Graduate School of Engineering and Science,
            University of the Ryukyus.}
%\affiliate[所属ラベル]{和文所属}{英文所属}
%\paffiliate[]{}
%\paffiliate[現在の所属ラベル]{和文所属}

\begin{document}
\begin{abstract}
本稿では Task に分割されたゲームプログラムのテストを行う。ゲームにおける
ランダム要素であるプレイヤー入力と乱数の固定化を行い、分割プログラムと
シーケンシャルプログラムの動作が同一であることを確認する。
さらに高速なテスト処理環境を構築する。
\end{abstract}
\begin{keyword}
ゲーム テスト Cell Cerium
\end{keyword}
\begin{eabstract}
We test divided game program. 
We immobilize random element that player input and random numbers, 
and check behavior of divided program and sequential program. 
At that we constract fast testing environment.
\end{eabstract}
\begin{ekeyword}
game test Cell Cerium
\end{ekeyword}
\maketitle

\section{はじめに}
我々は、これまで家庭用ゲーム機上におけるゲームプログラミングをサポートする
オープンな開発フレームワークの研究を行ってきた。現在は PlayStation3 上での開発を行っている。

PlayStation3 のアーキテクチャは Cell Broadband Engine と呼ばれ、
1  つの PPE(PowerPC Processor Element) と 8 つの SPE(Synergistic Processor
Element) で構成される。我々は、このような Many Core Architecture を用いた
並列プログラムの開発フレームワークとして Cerium Game Engine を開発した。
Cerium では、 プログラムを Task という単位で管理しており、この Task と計算に
必要なパラメータを PPE や各 SPE に並列に処理させる事により、プログラムの
動作を実現している。

Cerium はゲームプログラムをサポートしたフレームワークである。
ゲームプログラムの特徴としては、プレイヤーのゲームパッドからの入力やコード内
に埋め込まれた乱数などの非決定的な要素が多く、バグの再現性が低いことが
挙げられる。また遷移する状態数が膨大である為、一般的なテスト駆動のテストでは
ゲーム内のバグを見つけ出すのは難しい。

また、Cerium におけるゲーム開発ではプログラムを Task に分割するが、
Task 間でのパラメータの同期や Task 処理の実行順序によって
生成される乱数が異なるなどの問題があり、単純にシーケンシャルに
書かれたゲームプログラムを Task に分割して処理させても、元のプログラムを
逐次実行させた時と同じ動作をすることは保証されない。

そこで本研究ではシーケンシャルなゲームプログラムと Task に分割した
ゲームプログラムの動作が同一であることを確認するためのテスト手法を提案する。
シーケンシャルに書かれたゲームプログラムとそれを Task に分割したゲーム
プログラムをテストモデルとし、プレイヤー入力や乱数などの非決定的な要素の
固定化や、動作の同一性を確かめるのに必要なパラメータの書き出し、そして
より高速な動作でテストを行うことができる環境を構築する。

\section{Cell BE と Cerium}

\subsection{Cell Broadband Engine}
Cell Broadband Engine は SCEI と IBM によって開発された CPU である。
2 thread の PPE(PowerPC Processor Element)と、8個の SPE
(Synergistic Processor Element)からなる非対称なマルチコアプロセッサであり、
高速リングパスであるEIB(Element Interface Bus)で構成されている。
Cerium の動作環境である PS3 Linux では PPE と 6個の SPE が使用できる。
(図\ref{fig:cell})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{images/cell.eps}
\end{center}
\caption{Cell Broadband Engine}
\label{fig:cell}
\end{figure}

\subsection{Game Framework Cerium}
Cerium は我々が提案したゲーム開発フレームワークで、独自の Rendering Engine 
を持つ。Cerium は C++ で実装されており、画像の読み込みや入力デバイスは SDL 
を用いて行っている。以下に Cerium を構成する 3 つの機能を列挙する。

\begin{description}
\item[{\bf SceneGraph:}] オブジェクトのパラメータやポリゴン情報を tree 構造
のノードで管理する
\item[{\bf RenderingEngine:}] 3 種類の Task によって並列に描画処理を行う
\item[{\bf TaskManager:}] Task を動的に各 CPU (PPE,SPE) に割り振る
\end{description}

\subsection{Cerium の Task}
Cerium で使用される Task への分割単位はサブルーチンまたは関数としている。
Task には様々な API が用意されており、実行する CPU の選択や入出力される
データの設定、Task の依存関係などがセット出来るようになっている。

\begin{table}
\caption{Task Manager の API}
\begin{tabular}{c|l} 
\hline
\hline
create\_task & Task を生成する \\ \hline
run & 実行 Task Queue の実行\\ \hline
set\_inData & Task への入力データのアドレスを追加 \\ \hline
set\_outData & Task からのデータ出力先アドレスを追加 \\ \hline
set\_param & Task に 32 bit の情報を追加 \\ \hline
wait\_for & Task 同士の依存関係をセット \\ \hline
set\_cpu & Task を実行する CPU(PPE,SPE0〜5) の設定 \\ \hline
set\_post & Task が終了した後 PPE 側で実行される関数の登録 \\ \hline
\end{tabular}
\label{tb:tm_api}
\end{table}

\section{ゲームプログラムにおけるテスト}
多くのゲームでは多数のオブジェクトが存在し、プレイヤーのコントローラー入力や
ゲームの進行状況によって新たなオブジェクトが生成される。生成された
オブジェクトは他のオブジェクトの座標などのパラメータに影響され、衝突判定を
行ったり、挙動が変化する。

\if0
(図\ref{fig:game})
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{images/game.eps}
\end{center}
\caption{ゲームオブジェクトの相互作用}
\label{fig:game}
\end{figure}
\fi

このようにゲームプログラムでは常にプレイヤーの入力がゲームに影響され、
オブジェクト同士のパラメーターが相互に干渉し合うため、遷移する状態が
膨大であり、一般的なテスト駆動のように遷移する状態が仕様の範囲内に収まる
のかチェックするようなテストは向かない。ゲームプログラムは実際にプレイヤーが
ゲームをプレイすることが重要なテストとなる。

\subsection{プレイヤーの入力の不定性}
プレイヤーの入力は常に非決定的であり、例え同じ人間が同じゲームの同じ場面を
プレイしたとしても毎回全く同じ入力をする可能性は極めて低い。
こうした事からプレイヤーは制御不能なランダム要素であると考えられ、
ゲームプログラムテストにおけるバグの再現性を低下させている。

\subsection{ゲームにおける乱数}
ゲームにおける乱数は、オブジェクトの振る舞いに多様性を持たせたり、ランダムな
配置を実現する為に使われ、ゲームのボリュームや面白さを広げる役割を担ってきた。
予測不能な乱数はゲームプレイにおいては面白さを牽引する要因となるが、

テスト環境では、こうした乱数のランダム性はデバッグをする上でバグの再現を
困難にする。乱数生成器を無効にするか、定数でシードすることによってバグの
再現性を下げることなく、テストすることが出来る

\subsection{SPE における乱数生成の非決定性}\label{sec:spe_random}
通常のシーケンシャルなプログラムでは、乱数を必要とする処理系が 1 つの乱数列
から順番に乱数を取得し、使用する。しかし並列プログラムではこの処理系は Task 
として SPE に送られる。乱数列は SPE 毎に独自に生成されるため、各 Task が
受け取る乱数は逐次実行した時とは異なる値となってしまう。また、SPE 内でも 
Task 同士に依存関係を持たせない限り、Task の実行順序が保証されないので
こちらも受け取る乱数が不定となる原因となる。(図\ref{fig:spe_random})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.35]{images/spe_random.eps}
\end{center}
\caption{SPE 内での乱数の生成}
\label{fig:spe_random}
\end{figure}

\section{テストモデルとなるシューティングゲーム}

\subsection{Super Dandy}
Super Dandy は我々が PlayStation でのゲーム開発を行っていた 1998 年に
開発されたシューティングゲームである。SuperDandy は開発する環境が変わる度に
移植されており、過去には PlayStation2 Linux、OpenGL バージョンも作られた。
(図\ref{fig:dandy})

\begin{figure}[hb]
\begin{center}
\includegraphics[scale=0.15]{images/dandy.eps}
\end{center}
\caption{Super Dandy}
\label{fig:dandy}
\end{figure}

Super Dandy が伝統的に移植されてきた背景には、全 5 ステージのある程度の
ボリュームのあるゲームであること、衝突判定やオブジェクト管理、ステージクリア
によるシーン切り替えなど、基本的なゲームとしての要素が入っていること、
そして動作結果を過去の環境と比較することで新たな環境のチューニングが行える
ことが挙げられる。

\subsection{Task Dandy(Super Dandy Task version)}\label{sec:taskdandy}
本研究を進めるにあたり、Super Dandy を Cerium の Task で書き換えた 
Task Dandy を作成した。Task Dandy はできるだけ元の Super Dandy のコード
やデータ構造を流用し、比較、テストが容易に行えるように設計した。
(図\ref{fig:taskdandy})

その為、Super Dandy で Move や Collision の処理を行う state\_update() や
collision\_detect() においてオブジェクトの動きや衝突判定を行う Move Task や 
Collision Task を生成している。また、obj\_draw() はオブジェクトの描画を行う
関数であったが、Task Dandy ではSceneGraph の tree を生成している。
ゲームの処理を抜けると、さきほど生成した SceneGraph の tree から描画処理を
行う 3 つの Task を生成する。

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{images/taskdandy.eps}
\end{center}
\caption{Super Dandy と Task Dandy の処理}
\label{fig:taskdandy}
\end{figure}

\section{テスト環境の構築}

\subsection{テストログに記述する情報とそのタイミング}
シーケンシャルなプログラムを Task に分割した際に、新たに発生するバグとして、
本研究では以下の項目に焦点を当てた。

\begin{itemize}
\item Task 間のデータの同期
\item Task の実行順序
\item Task の定義
\end{itemize}

このうち、Task の定義については、Task の中身が非常に小さい為(Super Dandy 
なら 20〜100 行程度)、Task の inData や outData を調べるといった従来のテスト
手法でも十分にテストが可能である。その他の 2 つについては、いずれも衝突判定
の際に生じるバグである。
(図\ref{fig:test_log})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.3]{images/test_log.eps}
\end{center}
\caption{Task Dandy で起こりうるバグ}
\label{fig:test_log}
\end{figure}

そこで、オブジェクトが被弾した時、そしてオブジェクトが生成された時にテスト
ログを取ることで効率的にバグを発見することができると考えた。以下に実際に
収集したテストログの例を示す。

\begin{verbatim}
F64: CREATE  [NAME]enemy_greenclab_0
[COORD]x= 120.000000  y= -128.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
\end{verbatim}

それぞれのパラメータの詳細は次のとおりである。

\begin{itemize}
\item {\bf F64,F85: }生成、もしくは被弾した時の経過フレーム。
\item {\bf CREATE,DELETE:} CREATE ならオブジェクトが生成された、DELETE なら
  オブジェクトが被弾した事を表す。
\item {\bf NAME: }オブジェクトの種類と ID。ID はオブジェクトの種類毎に 0 
  から順番に付けられるのでどのオブジェクトの情報なのかを特定できる。
\item {\bf COORD: }オブジェクトのxy座標とxy方向の速度。
\item {\bf BULLET: }その瞬間に画面内に存在した弾の数。差異があれば同期が
  取れていないことを示す。
\end{itemize}

これにより、フレーム単位でどのオブジェクトが生成、または被弾したのか知ること
ができる。trace モードでプレイヤーの入力を固定し、各バージョンでテストログを
取り、その差異を調べることでバグが発生している時間や場所を特定することが
できる。

\subsection{プレイヤー入力の固定化}\label{sec:fix_input}
ゲームにおいてプレイヤーからの入力は制御不能なランダム要素であり、
バグを再現することを困難にする。そこでプレイヤーからの入力を1フレーム毎に
記録し、バイナリデータとして書き出す Capture モードと書き出されたバイナリ
データを読み込み、プレイヤーの入力を再現する Trace モードを実装した。

\section{SPE における乱数の固定化}\label{sec:ppe_random}
SPE 内で乱数を生成すると、毎回異なる値を生成してしまう。
そこであらかじめ PPE 内で乱数列を生成し、inData として Task に渡しておく。
Task Dandy では Task の生成、定義がされるタイミングは Super Dandy における
Move 関数や Collision 関数が実行されるタイミングと同じである為、渡される乱数
は Super Dandy と同じ乱数となる。
(図\ref{fig:ppe_random})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{images/ppe_random.eps}
\end{center}
\caption{PPE 内での乱数の生成と乱数の受け渡し}
\label{fig:ppe_random}
\end{figure}

\subsection{描画処理を行わないビデオモード}\label{sec:video_none}
Task Dandy ではゲームの処理や Task 生成を行った後、Rendering Engine を用いて 
3 つの Task を用いて画面の描画処理を行っている。

しかし、プレイヤーの入力をバイナリデータから読み出す場合、処理の詳細が
知りたい場合を除いて画面の描画処理は不要となる。そこでテスト用に画面の
描画処理を行わないモードを Cerium に実装した。これは、Cerium 内で描画用の 
Task を生成する処理を行わないことで多くの処理時間を要する描画処理を行わずに
テストを行うことができるビデオモードである。
(図\ref{fig:video_none})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{images/video_none.eps}
\end{center}
\caption{描画処理を行わないビデオモード}
\label{fig:video_none}
\end{figure}

\section{バグ検出実験}

\subsection{開発した環境における検出方法}
まずはじめに OpenGL バージョンの Super Dandy を Capture モードでプレイする。
プレイはエンディングまで行い、プレイヤーの入力データを保存する。
Task Dandy を Trace モードで実行し、入力データを読み込ませる。
そして各バージョンそれぞれから得られたテストログを比較、考察し、
バグの発生していると思われる箇所を特定する。

この方法で実際にテストを行い、以下のようなテストログが取れた。

\begin{verbatim}
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
\end{verbatim}

ここで Super Dandy と Task Dandy の 2 つのログを比較したときの特徴を
洗いだすと以下のようになる。

\begin{itemize}
\item Super Dandy では別フレームで被弾した敵オブジェクトが Task Dandy では
  同フレーム内で被弾している
\item 同フレーム内で被弾したときの弾丸の数が一致している
\item それ以外のログは Super Dandy と Task Dandy 共に一緒である
\end{itemize}

こうした結果から 2 つのオブジェクト間で弾丸データの同期が取れていない、と
いう仮説を立てた。Collision Task 間でデータを同期させるには、Collision Task 
を同じ CPU に送り、予め衝突判定に必要なパラメータの領域を LS に確保し、
その領域のパラメータで衝突判定を行う方法が考えられる。

\if0
(図\ref{fig:collision_reflect})
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.3]{images/collision_reflect.eps}
\end{center}
\caption{共用領域による Collision Task の同期}
\label{fig:collision_reflect}
\end{figure}
\fi

以上のことをふまえて Collision Task を書き換え、再び同じプレイヤー入力で
テストログを出力させた。以下にその結果を示す。

\begin{verbatim}
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
\end{verbatim}

この結果よりオブジェクトの処理の結果がフレーム単位で同じであることがわかる。
衝突判定時のテストログ出力から得られた同期バグ検出は有効であった。

\section{Task への乱数受け渡しによるバグの再現性の検証}
Task への乱数受け渡しの手法が期待通りの動きをするかどうか、多数の隕石
オブジェクトが生成されるステージで全ての隕石オブジェクトが生成されるのを
観察し、検証した。この隕石オブジェクトは以下のような実装になっている

\begin{verbatim}
    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;
    } else if(sf == 2) {
        ....
    } else if(sf == 3) {
        ....
    }
\end{verbatim}

このオブジェクトは乱数によって 3 種類の処理に分かれる。処理の中では xy 座標
、xy 方向の速度が決定し、次の状態へ遷移する、という動作になっている。
そこで、この処理が行われた直後のオブジェクトの座標を記録し、Super Dandy、
Task Dandy 双方のデータに違いがあるかどうか調べた。

以下はその結果である。

\begin{verbatim}
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]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
[ID]1  [COORD]x= -35.000000  y= 20.000000
              vx= 3.000000  vy= 1.000000
...
\end{verbatim}

ID はそのオブジェクト固有の値である。SPE で並列実行させた場合、実行順序は
バラバラになっているが、xy 座標、速度の値は逐次実行した場合と一致している
ことがわかる。Task への乱数受け渡しは有効に働いていることがわかる。

\subsection{ビデオモードによる実行時間の比較}
描画を行わないビデオモードと通常のビデオモードで実行時間を計測し、
その差がどの程度あるのかを比較した。実行時間の計測には Unix 環境で使用できる
 time コマンドを使用し、計測モデルとして OpenGL で動作している Super Dandy 
と Task Dandy を使用した。それぞれ描画を行わないバージョンと 1200x800 で
画面描画を行うバージョンを動かし、テストした。以下が計測結果である。

\begin{table}[h]
\caption{ビデオモードによる実行時間の比較}
\begin{tabular}{c||c|c|c} 
\hline
\hline
  & OpenGL & Task(no video) & Task \\ \hline \hline
実行時間 & 336.09 sec & 385.17 sec & 6643.16 sec \\ \hline
\end{tabular}
\label{tb:test_time}
\end{table}

OpenGL バージョンと Task Dandy で実行時間が 50 sec 程増加している。
これはゲーム中の Move と Collision を Task 化したことにより、Cerium での 
Task の処理が発生したためと思われる。

次に描画処理を行った時の実行時間だが、Task Dandy では膨大な処理時間が
発生している。これは ゲーム内の Task に加え、Cerium の描画処理の為の Task が
多くの処理時間を要し、オーバーヘッドが膨大になっているからだと思われる。

\section{まとめ}
Capture と Trace によるプレイヤー入力の固定化、生成される乱数の固定化、
および画面描画を行わないビデオモードの実装によってバグの再現性の向上、
そしてテスト時間の短縮を実現することができた。

さらに異なるバグを発見する為には、多種多様なゲームのプレイヤー入力を Capture
、Trace する必要がある。

%% 謝辞 \ack

%\bibliographystyle{sieicej}
%\bibliography{myrefs}
\begin{thebibliography}{99}% 文献数が10未満の時 {9}
\bibitem{kono}
河野 真治,
PS3 上でのゲームプログラミング,
第51回プログラミング・シンポジウム, 2010.

\bibitem{gongo}
宮國 渡,
Cell 用の Fine-Grain Task Manager の実装,
琉球大学理工学研究科情報工学専攻 平成20年度学位論文, 2009.

\bibitem{akira}
神里 晃,
Cell を用いたゲームフレームワークの提案,
琉球大学理工学研究科情報工学専攻 平成19年度学位論文, 2008.

\bibitem{yutaka}
金城 裕,
Fine grain Task Manager Cerium のチューニング,
日本ソフトウェア科学会第27回大会論文集, 2010.

\end{thebibliography}

%% 付録 \appendix
%%      \section{}
\if0
\begin{biography}
\profile{}{}{}
%\profile{会員種別}{名前}{紹介文}% 顔写真あり
%\profile*{会員種別}{名前}{紹介文}% 顔写真なし
\end{biography}
\fi

\end{document}
\ No newline at end of file
+%% 1. 「論文」
%% v1.6 [2009/11/03]
\documentclass{ieicej}
%\documentclass[invited]{ieicej} % 招待論文
%\documentclass[comment]{ieicej} % 解説論文
\usepackage{graphicx}
%\usepackage{latexsym}
%\usepackage[fleqn]{amsmath}
%\usepackage[psamsfonts]{amssymb}

\setcounter{page}{1}

\field{}
\jtitle{GameFrameWork Cerium における Sequential な Game Program の分割と
  動作の検証}
\etitle{Division and verification of Sequential Game Program
  on GameFrameWork Cerium }
\authorlist{%
 \authorentry{小林 佑亮}{Yusuke KOBAYASHI}{ryukyu}% <= 記述しないとエラーになります
 \authorentry{河野 真治}{Shinji KONO}{ryukyu}
 \authorentry{多賀野 海人}{Kaito TAGANO}{ryukyu}
 \authorentry{金城 裕}{Yutaka KINJO}{ryukyu}
}
\affiliate[ryukyu]{琉球大学 理工学研究科 情報工学専攻 並列信頼研究室}
          {Concurrency Reliance Laboratory, Information Engineering Course,
            Faculty of Engineering Graduate School of Engineering and Science,
            University of the Ryukyus.}
%\affiliate[所属ラベル]{和文所属}{英文所属}
%\paffiliate[]{}
%\paffiliate[現在の所属ラベル]{和文所属}

\begin{document}
\begin{abstract}
本稿では Task に分割されたゲームプログラムのテストを行う。ゲームにおける
ランダム要素であるプレイヤー入力と乱数の固定化を行い、分割プログラムと
シーケンシャルプログラムの動作が同一であることを確認する。
さらに高速なテスト処理環境を構築する。
\end{abstract}
\begin{keyword}
ゲーム テスト Cell Cerium
\end{keyword}
\begin{eabstract}
We test divided game program. 
We immobilize random element that player input and random numbers, 
and check behavior of divided program and sequential program. 
At that we constract fast testing environment.
\end{eabstract}
\begin{ekeyword}
game test Cell Cerium
\end{ekeyword}
\maketitle

\section{はじめに}
我々は、これまで家庭用ゲーム機上におけるゲームプログラミングをサポートする
オープンな開発フレームワークの研究を行ってきた。現在は PlayStation3 上での開発を行っている。

PlayStation3 のアーキテクチャは Cell Broadband Engine と呼ばれ、
1  つの PPE(PowerPC Processor Element) と 8 つの SPE(Synergistic Processor
Element) で構成される。我々は、このような Many Core Architecture を用いた
並列プログラムの開発フレームワークとして Cerium Game Engine を開発した。
Cerium では、 プログラムを Task という単位で管理しており、この Task と計算に
必要なパラメータを PPE や各 SPE に並列に処理させる事により、プログラムの
動作を実現している。

Cerium はゲームプログラムをサポートしたフレームワークである。
ゲームプログラムの特徴としては、プレイヤーのゲームパッドからの入力やコード内
に埋め込まれた乱数などの非決定的な要素が多く、バグの再現性が低いことが
挙げられる。また遷移する状態数が膨大である為、一般的なテスト駆動のテストでは
ゲーム内のバグを見つけ出すのは難しい。

また、Cerium におけるゲーム開発ではプログラムを Task に分割するが、
Task 間でのパラメータの同期や Task 処理の実行順序によって
生成される乱数が異なるなどの問題があり、単純にシーケンシャルに
書かれたゲームプログラムを Task に分割して処理させても、元のプログラムを
逐次実行させた時と同じ動作をすることは保証されない。

そこで本研究ではシーケンシャルなゲームプログラムと Task に分割した
ゲームプログラムの動作が同一であることを確認するためのテスト手法を提案する。
シーケンシャルに書かれたゲームプログラムとそれを Task に分割したゲーム
プログラムをテストモデルとし、プレイヤー入力や乱数などの非決定的な要素の
固定化や、動作の同一性を確かめるのに必要なパラメータの書き出し、そして
より高速な動作でテストを行うことができる環境を構築する。

\section{Cell BE と Cerium}

\subsection{Cell Broadband Engine}
Cell Broadband Engine は SCEI と IBM によって開発された CPU である。
2 thread の PPE(PowerPC Processor Element)と、8個の SPE
(Synergistic Processor Element)からなる非対称なマルチコアプロセッサであり、
高速リングパスであるEIB(Element Interface Bus)で構成されている。
Cerium の動作環境である PS3 Linux では PPE と 6個の SPE が使用できる。
(図\ref{fig:cell})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{images/cell.eps}
\end{center}
\caption{Cell Broadband Engine}
\label{fig:cell}
\end{figure}

\subsection{Game Framework Cerium}
Cerium は我々が提案したゲーム開発フレームワークで、独自の Rendering Engine 
を持つ。Cerium は C++ で実装されており、画像の読み込みや入力デバイスは SDL 
を用いて行っている。以下に Cerium を構成する 3 つの機能を列挙する。

\begin{description}
\item[{\bf SceneGraph:}] オブジェクトのパラメータやポリゴン情報を tree 構造
のノードで管理する
\item[{\bf RenderingEngine:}] 3 種類の Task によって並列に描画処理を行う
\item[{\bf TaskManager:}] Task を動的に各 CPU (PPE,SPE) に割り振る
\end{description}

\subsection{Cerium の Task}
Cerium で使用される Task への分割単位はサブルーチンまたは関数としている。
Task には様々な API が用意されており、実行する CPU の選択や入出力される
データの設定、Task の依存関係などがセット出来るようになっている。

\begin{table}
\caption{Task Manager の API}
\begin{tabular}{c|l} 
\hline
\hline
create\_task & Task を生成する \\ \hline
run & 実行 Task Queue の実行\\ \hline
set\_inData & Task への入力データのアドレスを追加 \\ \hline
set\_outData & Task からのデータ出力先アドレスを追加 \\ \hline
set\_param & Task に 32 bit の情報を追加 \\ \hline
wait\_for & Task 同士の依存関係をセット \\ \hline
set\_cpu & Task を実行する CPU(PPE,SPE0〜5) の設定 \\ \hline
set\_post & Task が終了した後 PPE 側で実行される関数の登録 \\ \hline
\end{tabular}
\label{tb:tm_api}
\end{table}

\section{ゲームプログラムにおけるテスト}
多くのゲームでは多数のオブジェクトが存在し、プレイヤーのコントローラー入力や
ゲームの進行状況によって新たなオブジェクトが生成される。生成された
オブジェクトは他のオブジェクトの座標などのパラメータに影響され、衝突判定を
行ったり、挙動が変化する。

\if0
(図\ref{fig:game})
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{images/game.eps}
\end{center}
\caption{ゲームオブジェクトの相互作用}
\label{fig:game}
\end{figure}
\fi

このようにゲームプログラムでは常にプレイヤーの入力がゲームに影響され、
オブジェクト同士のパラメーターが相互に干渉し合うため、遷移する状態が
膨大であり、一般的なテスト駆動のように遷移する状態が仕様の範囲内に収まる
のかチェックするようなテストは向かない。ゲームプログラムは実際にプレイヤーが
ゲームをプレイすることが重要なテストとなる。

\subsection{プレイヤーの入力の不定性}
プレイヤーの入力は常に非決定的であり、例え同じ人間が同じゲームの同じ場面を
プレイしたとしても毎回全く同じ入力をする可能性は極めて低い。
こうした事からプレイヤーは制御不能なランダム要素であると考えられ、
ゲームプログラムテストにおけるバグの再現性を低下させている。

\subsection{ゲームにおける乱数}
ゲームにおける乱数は、オブジェクトの振る舞いに多様性を持たせたり、ランダムな
配置を実現する為に使われ、ゲームのボリュームや面白さを広げる役割を担ってきた。
予測不能な乱数はゲームプレイにおいては面白さを牽引する要因となるが、

テスト環境では、こうした乱数のランダム性はデバッグをする上でバグの再現を
困難にする。乱数生成器を無効にするか、定数でシードすることによってバグの
再現性を下げることなく、テストすることが出来る

\subsection{SPE における乱数生成の非決定性}\label{sec:spe_random}
通常のシーケンシャルなプログラムでは、乱数を必要とする処理系が 1 つの乱数列
から順番に乱数を取得し、使用する。しかし並列プログラムではこの処理系は Task 
として SPE に送られる。乱数列は SPE 毎に独自に生成されるため、各 Task が
受け取る乱数は逐次実行した時とは異なる値となってしまう。また、SPE 内でも 
Task 同士に依存関係を持たせない限り、Task の実行順序が保証されないので
こちらも受け取る乱数が不定となる原因となる。(図\ref{fig:spe_random})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.35]{images/spe_random.eps}
\end{center}
\caption{SPE 内での乱数の生成}
\label{fig:spe_random}
\end{figure}

\section{テストモデルとなるシューティングゲーム}

\subsection{Super Dandy}
Super Dandy は我々が PlayStation でのゲーム開発を行っていた 1998 年に
開発されたシューティングゲームである。SuperDandy は開発する環境が変わる度に
移植されており、過去には PlayStation2 Linux、OpenGL バージョンも作られた。
(図\ref{fig:dandy})

\begin{figure}[hb]
\begin{center}
\includegraphics[scale=0.15]{images/dandy.eps}
\end{center}
\caption{Super Dandy}
\label{fig:dandy}
\end{figure}

Super Dandy が伝統的に移植されてきた背景には、全 5 ステージのある程度の
ボリュームのあるゲームであること、衝突判定やオブジェクト管理、ステージクリア
によるシーン切り替えなど、基本的なゲームとしての要素が入っていること、
そして動作結果を過去の環境と比較することで新たな環境のチューニングが行える
ことが挙げられる。

\subsection{Task Dandy(Super Dandy Task version)}\label{sec:taskdandy}
本研究を進めるにあたり、Super Dandy を Cerium の Task で書き換えた 
Task Dandy を作成した。Task Dandy はできるだけ元の Super Dandy のコード
やデータ構造を流用し、比較、テストが容易に行えるように設計した。
(図\ref{fig:taskdandy})

その為、Super Dandy で Move や Collision の処理を行う state\_update() や
collision\_detect() においてオブジェクトの動きや衝突判定を行う Move Task や 
Collision Task を生成している。また、obj\_draw() はオブジェクトの描画を行う
関数であったが、Task Dandy ではSceneGraph の tree を生成している。
ゲームの処理を抜けると、さきほど生成した SceneGraph の tree から描画処理を
行う 3 つの Task を生成する。

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{images/taskdandy.eps}
\end{center}
\caption{Super Dandy と Task Dandy の処理}
\label{fig:taskdandy}
\end{figure}

\section{テスト環境の構築}

\subsection{テストログに記述する情報とそのタイミング}
シーケンシャルなプログラムを Task に分割した際に、新たに発生するバグとして、
本研究では以下の項目に焦点を当てた。

\begin{itemize}
\item Task 間のデータの同期
\item Task の実行順序
\item Task の定義
\end{itemize}

このうち、Task の定義については、Task の中身が非常に小さい為(Super Dandy 
なら 20〜100 行程度)、Task の inData や outData を調べるといった従来のテスト
手法でも十分にテストが可能である。その他の 2 つについては、いずれも衝突判定
の際に生じるバグである。
(図\ref{fig:test_log})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.3]{images/test_log.eps}
\end{center}
\caption{Task Dandy で起こりうるバグ}
\label{fig:test_log}
\end{figure}

そこで、オブジェクトが被弾した時、そしてオブジェクトが生成された時にテスト
ログを取ることで効率的にバグを発見することができると考えた。以下に実際に
収集したテストログの例を示す。

\begin{verbatim}
F64: CREATE  [NAME]enemy_greenclab_0
[COORD]x= 120.000000  y= -128.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
\end{verbatim}

それぞれのパラメータの詳細は次のとおりである。

\begin{itemize}
\item {\bf F64,F85: }生成、もしくは被弾した時の経過フレーム。
\item {\bf CREATE,DELETE:} CREATE ならオブジェクトが生成された、DELETE なら
  オブジェクトが被弾した事を表す。
\item {\bf NAME: }オブジェクトの種類と ID。ID はオブジェクトの種類毎に 0 
  から順番に付けられるのでどのオブジェクトの情報なのかを特定できる。
\item {\bf COORD: }オブジェクトのxy座標とxy方向の速度。
\item {\bf BULLET: }その瞬間に画面内に存在した弾の数。差異があれば同期が
  取れていないことを示す。
\end{itemize}

これにより、フレーム単位でどのオブジェクトが生成、または被弾したのか知ること
ができる。trace モードでプレイヤーの入力を固定し、各バージョンでテストログを
取り、その差異を調べることでバグが発生している時間や場所を特定することが
できる。

\subsection{プレイヤー入力の固定化}\label{sec:fix_input}
ゲームにおいてプレイヤーからの入力は制御不能なランダム要素であり、
バグを再現することを困難にする。そこでプレイヤーからの入力を1フレーム毎に
記録し、バイナリデータとして書き出す Capture モードと書き出されたバイナリ
データを読み込み、プレイヤーの入力を再現する Trace モードを実装した。

\section{SPE における乱数の固定化}\label{sec:ppe_random}
SPE 内で乱数を生成すると、毎回異なる値を生成してしまう。
そこであらかじめ PPE 内で乱数列を生成し、inData として Task に渡しておく。
Task Dandy では Task の生成、定義がされるタイミングは Super Dandy における
Move 関数や Collision 関数が実行されるタイミングと同じである為、渡される乱数
は Super Dandy と同じ乱数となる。
(図\ref{fig:ppe_random})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{images/ppe_random.eps}
\end{center}
\caption{PPE 内での乱数の生成と乱数の受け渡し}
\label{fig:ppe_random}
\end{figure}

\subsection{描画処理を行わないビデオモード}\label{sec:video_none}
Task Dandy ではゲームの処理や Task 生成を行った後、Rendering Engine を用いて 
3 つの Task を用いて画面の描画処理を行っている。

しかし、プレイヤーの入力をバイナリデータから読み出す場合、処理の詳細が
知りたい場合を除いて画面の描画処理は不要となる。そこでテスト用に画面の
描画処理を行わないモードを Cerium に実装した。これは、Cerium 内で描画用の 
Task を生成する処理を行わないことで多くの処理時間を要する描画処理を行わずに
テストを行うことができるビデオモードである。
(図\ref{fig:video_none})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{images/video_none.eps}
\end{center}
\caption{描画処理を行わないビデオモード}
\label{fig:video_none}
\end{figure}

\section{バグ検出実験}

\subsection{開発した環境における検出方法}
まずはじめに OpenGL バージョンの Super Dandy を Capture モードでプレイする。
プレイはエンディングまで行い、プレイヤーの入力データを保存する。
Task Dandy を Trace モードで実行し、入力データを読み込ませる。
そして各バージョンそれぞれから得られたテストログを比較、考察し、
バグの発生していると思われる箇所を特定する。

この方法で実際にテストを行い、以下のようなテストログが取れた。

\begin{verbatim}
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
\end{verbatim}

ここで Super Dandy と Task Dandy の 2 つのログを比較したときの特徴を
洗いだすと以下のようになる。

\begin{itemize}
\item Super Dandy では別フレームで被弾した敵オブジェクトが Task Dandy では
  同フレーム内で被弾している
\item 同フレーム内で被弾したときの弾丸の数が一致している
\item それ以外のログは Super Dandy と Task Dandy 共に一緒である
\end{itemize}

こうした結果から 2 つのオブジェクト間で弾丸データの同期が取れていない、と
いう仮説を立てた。Collision Task 間でデータを同期させるには、Collision Task 
を同じ CPU に送り、予め衝突判定に必要なパラメータの領域を LS に確保し、
その領域のパラメータで衝突判定を行う方法が考えられる。

\if0
(図\ref{fig:collision_reflect})
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.3]{images/collision_reflect.eps}
\end{center}
\caption{共用領域による Collision Task の同期}
\label{fig:collision_reflect}
\end{figure}
\fi

以上のことをふまえて Collision Task を書き換え、再び同じプレイヤー入力で
テストログを出力させた。以下にその結果を示す。

\begin{verbatim}
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
\end{verbatim}

この結果よりオブジェクトの処理の結果がフレーム単位で同じであることがわかる。
衝突判定時のテストログ出力から得られた同期バグ検出は有効であった。

\section{Task への乱数受け渡しによるバグの再現性の検証}
Task への乱数受け渡しの手法が期待通りの動きをするかどうか、多数の隕石
オブジェクトが生成されるステージで全ての隕石オブジェクトが生成されるのを
観察し、検証した。この隕石オブジェクトは以下のような実装になっている

\begin{verbatim}
    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;
    } else if(sf == 2) {
        ....
    } else if(sf == 3) {
        ....
    }
\end{verbatim}

このオブジェクトは乱数によって 3 種類の処理に分かれる。処理の中では xy 座標
、xy 方向の速度が決定し、次の状態へ遷移する、という動作になっている。
そこで、この処理が行われた直後のオブジェクトの座標を記録し、Super Dandy、
Task Dandy 双方のデータに違いがあるかどうか調べた。

以下はその結果である。

\begin{verbatim}
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]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
[ID]1  [COORD]x= -35.000000  y= 20.000000
              vx= 3.000000  vy= 1.000000
...
\end{verbatim}

ID はそのオブジェクト固有の値である。SPE で並列実行させた場合、実行順序は
バラバラになっているが、xy 座標、速度の値は逐次実行した場合と一致している
ことがわかる。Task への乱数受け渡しは有効に働いていることがわかる。

\subsection{ビデオモードによる実行時間の比較}
描画を行わないビデオモードと通常のビデオモードで実行時間を計測し、
その差がどの程度あるのかを比較した。実行時間の計測には Unix 環境で使用できる
 time コマンドを使用し、計測モデルとして OpenGL で動作している Super Dandy 
と Task Dandy を使用した。それぞれ描画を行わないバージョンと 1200x800 で
画面描画を行うバージョンを動かし、テストした。以下が計測結果である。

\begin{table}[h]
\caption{ビデオモードによる実行時間の比較}
\begin{tabular}{c||c|c|c} 
\hline
\hline
  & OpenGL & Task(no video) & Task \\ \hline \hline
実行時間 & 336.09 sec & 385.17 sec & 6643.16 sec \\ \hline
\end{tabular}
\label{tb:test_time}
\end{table}

OpenGL バージョンと Task Dandy で実行時間が 50 sec 程増加している。
これはゲーム中の Move と Collision を Task 化したことにより、Cerium での 
Task の処理が発生したためと思われる。

次に描画処理を行った時の実行時間だが、Task Dandy では膨大な処理時間が
発生している。これは ゲーム内の Task に加え、Cerium の描画処理の為の Task が
多くの処理時間を要し、オーバーヘッドが膨大になっているからだと思われる。

\section{まとめ}
Capture と Trace によるプレイヤー入力の固定化、生成される乱数の固定化、
および画面描画を行わないビデオモードの実装によってバグの再現性の向上、
そしてテスト時間の短縮を実現することができた。また、テストログの出力により、
Task 間の同期問題のバグを修正することも出来た。

しかし、今回のテストでは Task Dandy の数ある状態遷移の一部をテストしかされて
いない。さらに異なるバグを発見する為には、多種多様なゲームのプレイヤー入力を
 Capture、Trace する必要がある。しかし、これを人間によって行うには大きな労力
を伴う。このプレイヤー入力をある程度自動的に生成できる実装が必要となる。

%% 謝辞 \ack

%\bibliographystyle{sieicej}
%\bibliography{myrefs}
\begin{thebibliography}{99}% 文献数が10未満の時 {9}
\bibitem{kono}
河野 真治,
PS3 上でのゲームプログラミング,
第51回プログラミング・シンポジウム, 2010.

\bibitem{gongo}
宮國 渡,
Cell 用の Fine-Grain Task Manager の実装,
琉球大学理工学研究科情報工学専攻 平成20年度学位論文, 2009.

\bibitem{akira}
神里 晃,
Cell を用いたゲームフレームワークの提案,
琉球大学理工学研究科情報工学専攻 平成19年度学位論文, 2008.

\bibitem{yutaka}
金城 裕,
Fine grain Task Manager Cerium のチューニング,
日本ソフトウェア科学会第27回大会論文集, 2010.

\end{thebibliography}

%% 付録 \appendix
%%      \section{}
\if0
\begin{biography}
\profile{}{}{}
%\profile{会員種別}{名前}{紹介文}% 顔写真あり
%\profile*{会員種別}{名前}{紹介文}% 顔写真なし
\end{biography}
\fi

\end{document}
\ No newline at end of file