% Sample file for the use of compsoft style file.
%
\documentclass[T]{compsoft}

% Preamble
%
% 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
% 巻数，号数，開始ページ，終了ページを指定する．
\volNoPp{16}{5}{78}{83}

% ワークショップによる推薦論文の場合，ワークショップ名を指定する．
% \suisen{ワークショップ名}

% 特集の場合，特集のタイトルを与える．
% \tokushu{特集のタイトル}

% 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
% 大会の回数は計算される．
\taikai{2010}

% ここに，使用するパッケージを列挙する．
\usepackage[dvips]{graphics}

% ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
% 再定義は原則として避けること．

\begin{document}

% 論文のタイトル
\title{Cell Task Manager Cerium を用いたゲーム作成}

% 著者
% 和文論文の場合，姓と名の間には半角スペースを入れ，
% 複数の著者の間は全角スペースで区切る
%
\author{小林 佑亮　　河野 真治
%
% ここにタイトル英訳 (英文の場合は和訳) を書く．
%
\ejtitle{development of games on Cell Task Manager Cerium}
%
% ここに著者英文表記 (英文の場合は和文表記) および
% 所属 (和文および英文) を書く．
% 複数著者の所属はまとめてよい．
%
\shozoku{Yusuke KOBAYASHI, Shinji KONO}{琉球大学大学院 理工学研究科 情報工学専攻 並列信頼研}%
{Dept\. Concurrency Reliance Laboratory, Information Engineering Course, Faculty of Engineering Graduate School of Engi-
neering and Science, University of the Ryukyus.}
%
% 出典情報は \shutten とすれば出力される．
%\shutten
%
% 受付年月日，記事カテゴリなどは自動的に生成される．
%\uketsuke{1999}{8}{3}
%
% その他，脚注に入れるものがあれば，\note に記述する．
%\note{脚注に入れる内容}
}

%
% 和文アブストラクト
\Jabstract{%
我々は PlayStation3 上でのゲームプログラミングをサポートする Cerium Engine を開発した。
Ceriumにおけるゲーム開発ではオブジェクトの描画や動作を Task という単位で管理しており、
この Task を動的に SPE に割り振ることによってプログラムの並列化を図っている。
現在、Cerium を用いたゲーム開発を進めており、その過程で様々なバグが発生することがわかった。
本稿では Cerium によるゲーム開発の例と Test の手法について提案する。
}
%
% 英文アブストラクト（大会論文には必要なし)
% \Eabstract{}
%
\maketitle

\section{概要}
当研究室ではこれまで家庭用ゲーム機上でのゲームプログラミングの開発を行ってきた。
過去には PlayStation や PlayStation2、 Game Boy Advance を用いており、現在は PlayStation3(以下PS3) で動作するゲーム開発を行っている。

PS3 では Fedora や Yellow Dog Linux といった Linux OS を動作させることができるので(現在の公式のサポートは終了している)
C や C++ といったプログラム言語を用いて Linux 上でプログラミングすることが可能となっている。
しかしPS3 の Architecture である Cell Broadband Engine は複数の SPE を使用する並列プログラミングが求められている。
そこで我々は Cell のような Many Core Architecture を用いた、並列プログラムの開発をサポートするフレームワークとして
Fine Grain Task Manager を開発した。このTask Manager を用いたゲーム開発フレームワークが Cerium である。

Cerium におけるゲーム開発ではオブジェクトの動作(Move)と、相互作用(collision)を Task として記述し、
その計算に必要なパラメータを SPE に転送して処理させる。しかし、Task の依存関係(dependency)や転送するパラメータの
整合性が取れないと期待した動作が行われない。本研究では Cerium を使ったゲーム開発を通して生じたバグを考察し、
効果的なテスト手法を提案することで、ゲームプログラムの動作を保証することを目的とする。

\section{Cell Broadband Engine}\label{section:CellBE}
Cell Broadband Engine は SCEI と IBM、東芝によって開発された CPU である。2 thread の PPE(PowerPC Processor Element)と、
8個のSPE(Synergistic Processor Element)からなる非対称なマルチコアプロセッサであり、高速リングバスであるEIB(Element Interface Bus)
で構成されている。PS3 Linux では6個の SPE を使うことが出来る。(図\ref{figure:CellBE})

\begin{figure}[tb]
\begin{center}
\scalebox{0.50}{\includegraphics{image/cbe.eps}}
\end{center}
\caption{Cell Broadband Engine Architecture}
\label{figure:CellBE}
\end{figure}

\subsection{PPE(PowerPC Processor Element)}
PPE は Cell Broadband Engine のメインプロセッサで、複数の SPE をコアプロセッサとして使用することができる汎用プロセッサである。
メインメモリや外部デバイスへの入出力、SPE を制御する役割を担っている。PPU(PowerPC Processor Unit)は、PPEの演算処理を行うユニットで、
PowerPC アーキテクチャをベースとした命令セットを持つ。PPSS(PowerPC Processor Storage Subsystem)は PPU からメインメモリへのデータアクセスを
制御するユニットである。(図\ref{figure:PPE})

\begin{figure}[tb]
\begin{center}
\scalebox{0.50}{\includegraphics{image/cbe-ppe.eps}}
\end{center}
\caption{PPE(PowerPC Processor Element)}
\label{figure:PPE}
\end{figure}

\subsection{SPE(Synergistic Processor Element)}\label{subsection:SPE}
SPE には 256KB の Local Store(LS)と呼ばれる、直接参照できるメモリ領域があり、バスに負担をかける事なく並列に計算を進めることが出来る。
SPE からメインメモリへは、直接アクセスすることは出来ず、SPE を構成する一つである MFC (Memory Flow Controller)へ、チャネルを介して
DMA(Direct Memory Access)命令を送ることで行われる。(図\ref{figure:SPE})

\begin{figure}[tb]
\begin{center}
\scalebox{0.50}{\includegraphics{image/cbe-spe.eps}}
\end{center}
\caption{SPE(Synergistic Processor Element)}
\label{figure:SPE}
\end{figure}

\section{Cerium Engine}
Cerium は 独自の Rendering Engine と Scene Graph、Task Manager の3つによって構成される。
ゲーム中のオブジェクトの振る舞いやルールは SceneGraph によって管理され、それらの動きや 
Rendering の処理を動的に SPE に割り振るカーネルとして Task Manager が用いられる。

CeriumはC++で実装されており、画像の読み込みや入力デバイスは SDL を用いて行っている。

\subsection{SceneGraph}
Cerium ではゲーム中の一つの場面(Scene)を構成するオブジェクトやその振る舞い、ゲームのルールの集合を SceneGraph としている。
SceneGraph のノードは親子関係を持つ tree で構成される。(図\ref{figure:SceneGraph})親子関係とは、親オブジェクトの回転や並列移動等の行列計算による
頂点座標の変更が、子オブジェクトにも反映する関係のことである。これは子に対してスタックに積まれた親の変換行列を掛けることで実現できる。

\begin{figure}[tb]
\begin{center}
\scalebox{0.50}{\includegraphics{image/scene_graph.eps}}
\end{center}
\caption{SceneGraph tree}
\label{figure:SceneGraph}
\end{figure}

\subsection{Rendering Engine}\label{subsection:rendering}
Cerium の Rendering Engine では、以下の3つの Task を持つ。

\begin{itemize}
\item SceneGraph が持つ Polygon の座標から、実際に画面に表示する座標の計算を行い、PolyPack を生成する Task
\item PolygonPack から同じ Y 座標を持つ線分の集合である SpanPack を生成する Task
\item SpanPack を Texture を読み込みながら Z Buffer を用いて描画する Task
\end{itemize} 

この3つの Task は表示画面毎にパイプライン的に実行される。そのため、Cerium では並列度を維持することが出来る。

\subsection{Task Manager}
Task Manager は Task と呼ばれる、分割された各プログラムを管理する。Task の単位はサブルーチンまたは関数とし、
Task 同士の依存関係を考慮しながら実行していく。

\subsubsection{Task の入出力}\label{subsubsection:add_inData}
Task に渡す入力として、 add\_inData がある。
add\_inData(addr, size) は、Task に渡すデータのアドレスと、そのデータのサイズを引数として入力する。
このデータは DMA 転送されるため、addr は16バイトアライメントが取れており、size は16バイト倍数である必要がある。

Task の出力先は add\_outData を使用する。使用方法は add\_inData と同じで、アライメント、バイト数にも気をつける必要がある。

\subsubsection{Task の依存関係}\label{subsubsection:dependency}
Task Manager は Task 依存を解決する機能を持っている。以下は記述例である。

\begin{verbatim}
task3->wait_for(task1);
task3->wait_for(task2);
\end{verbatim} 

wait\_for は複数の Task を指定できる。上記の場合は task3 が task1、task2 の二つの Task 終了を待つ形となる。

\subsubsection{Task 終了時に実行される関数}\label{subsubsection:set_post}
set\_post 関数を使うことによって Task が終了した際、メインスレッドで実行される関数と、その引数を指定できる。

\begin{verbatim}
int data = 3;
task->set\_post(func1, (void*)data);

void
func1(void *data)
{
  printf("func1: data = %d\n", (int)data);
}

//実行結果
func1: data = 3
\end{verbatim}

set\_postにより、ユーザ側でも Task が終了したということを検知できる

\section{Cerium を用いたゲーム開発の手法}\label{section:game_develop}
多くのゲームでは毎フレーム、オブジェクトのパラメータを計算し、その結果によって 
Rendering や collision の判定を行う必要がある。
Cerium 環境では毎フレーム、オブジェクトの動作(Move)を記述した Task を生成し
オブジェクトのパラメータと一緒に SPE に送ることで並列性を持ったゲームプログラムを実現できる。
しかし SPE の LS は 256KB しか無い為(\ref{subsection:SPE}節)、Polygon や Texture などの
余分な情報の入った SceneGraph そのものを送るのは望ましくない。
そこで計算に必要なパラメータだけを持つ Property をユーザ側で定義し、Task と共に 
SPE に送る手法を取る。SPE に計算された値は post\_func を用いて
SceneGraph に反映され、Rendering Engine によって描画される(図\ref{figure:reflect})。

以下は Task を生成するルーチンの例である。

\begin{verbatim}
HTask *task = sgroot->tmanager->create_task(id);
  task->set_cpu(SPE_ANY);
  task->add_inData(property, size);
  task->add_outData(property, size);
  task->set_post(post_func, (void*)property, 0);
  task->spawn();
\end{verbatim}

\begin{figure}[tb]
\begin{center}
\scalebox{0.50}{\includegraphics{image/reflect_value.eps}}
\end{center}
\caption{Property を用いた値の計算と SceneGraph への反映}
\label{figure:reflect}
\end{figure}

\section{Cerium を用いたゲーム開発におけるデバッグ}
Cerium を用いたゲーム開発を進める過程で発生したバグの例と
それを解決する為に用いた手法を示す。

\subsection{Task の依存関係によるバグ}
\ref{section:game_develop}章の方法を用いてゲームの作成を行ったところ、
Task による Property の計算が描画に反映されなかった。そこでプログラム上で動作している 
主要な Task の実行順序を調べてみると、以下のようになった。

\begin{enumerate}
\item GameTask(Game 本体の Task)
\item CreatePolygonFromSceneGraph(SceneGraph からPolygonPack を生成)
\item GameTask->post\_func(GameTask によって計算された値を SceneGraph に反映)
\item CreateSpan(PolygonPack から SpanPack を生成)
\item DrawSpan(SpanPack から Texture を読み込みながら描画)
\end{enumerate} 

Cerium による Rendering は 3つの Task によって実現されているが\ref{subsection:rendering}
その最初プロセスである CreatePolygonFromSceneGraph が SceneGraph への Property の値の反映より先に実行されているのがわかる。

これ対して、全ての GameTask の終了をwait\_forで待つ DummyTask(何も動作しないTask)を Rendering Task との
間に挟むことによって Task の 実行順序を調整した(図\ref{figure:debug_dependency})。

\begin{figure}[tb]
\begin{center}
\scalebox{0.50}{\includegraphics{image/dependency.eps}}
\end{center}
\caption{DummyTask による GameTask と Rendering の実行順序の調整}
\label{figure:debug_dependency}
\end{figure}

\subsection{Task に送る Input Data と Output Data の比較}
コントローラーの入力を見て、Property の値を変化させる Task を作ったところ、期待通りの動作をしなかった。
この為、この Task で処理する Input Data と Output Data の比較を行ったところ、Output Data の Property に
でたらめなパラメータが入っている事がわかった。この時点で Task 内になんらかの不当な処理がされていると予想した。

この Task では SPE に コントローラーの入力の値と Property を送っているが、Cerium の仕様により、
これらのデータは void* 型でInput され、Task 内で必要な型に cast されて使用される。
今回のバグは Task 内において、コントローラーの入力と Property の型を逆にして cast してしまったのが
原因であることがわかった。

\section{まとめと今後の課題}
今回は Task の依存関係を列挙することにより、実行順序に関するバグを発見することが出来た。
また、 Task の Input, Output を調べることにより、Task 内での不正な処理を発見した。

今後はゲームの実装を進めるとともに、コードのメトリクス(数値データ)を取りながらテストの評価をしていく予定である。

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

\bibitem{}高橋 寿一. 知識ゼロから学ぶソフトウェアテスト. 翔泳社 2005.

\bibitem{}KENT BECK. テスト駆動開発入門. PEARSON Education Japan 2003.

\end{thebibliography}
\end{adjustvboxheight}

\end{document}