--- a/paper/OS-116-6.tex	Sun Dec 19 23:01:46 2010 +0900
+++ b/paper/OS-116-6.tex	Sun Dec 19 23:08:03 2010 +0900
@@ -1,1 +1,439 @@
-\documentclass[techrep]{ipsjpapers}
\usepackage{graphicx}

% 巻数，号数などの設定
\setcounter{年数}{2011}

% ユーザが定義したマクロなど．
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)\nobreak}
\def\>{\nobreak\(\rangle\)}
\def\|{\verb|}
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\LATEX{\iLATEX\Large}
\def\LATEx{\iLATEX\normalsize}
\def\LATex{\iLATEX\small}
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
\def\Quote{\list{}{}\item[]}
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
	$\backslash$#1\fi}

%\checklines	% 行送りを確認する時に使用
\begin{document}%{
% 和文表題
\title[学生用 PS3 GameFrameWork Cerium での Pipeline ストールの検出]%
	{学生用 PS3 GameFrameWork Cerium での\\Pipeline ストールの検出}
% 英文表題
\etitle{Detecting pipeline stall on PS3 GameFrameWork Cerium}
% 所属ラベル
\affilabel{UNI}{琉球大学 理工学研究科 情報工学専攻 並列信頼研究室\\
                Concurrency Reliance Laboratory, Information Engineering Course,
                Faculty of Engineering Graduate School of Engineering and Science,
                University of the Ryukyus.}

% 和文著者名
\author{小林 佑亮\affiref{UNI}\and
	河野 真治\affiref{UNI}\and
        多賀野 海人\affiref{UNI}\and
        金城　裕\affiref{UNI}}
	
% 英文著者名
\eauthor{Yusuke Kobayashi\affiref{UNI}\and
	 Shinji Kono\affiref{UNI}\and
         Kaito Tagano\affiref{UNI}\and
         Yutaka Kinjo\affiref{UNI}}

% 和文概要
\begin{abstract}
我々は PlayStation3 上でのゲームプログラミングをサポートする Cerium Engine を開発した。
Cerium におけるゲーム開発ではオブジェクトの描画や動作を Task という単位で管理しており、
この Task を SPE に送り、Pipeline で実行することによってプログラムの並列化を図っている。
この Pipeline におけるストールによって実行速度の低下が発生することが分かっている。
本研究ではこのストールを検出することを考える。
\end{abstract}
% 英文概要
\begin{eabstract}
We developed Cerium Engine which support Game Programming on PlayStation3.
Cerium managed drawing objects and movement in unit called Task.
By sending SPE a Task and executing on pipeline,we attempt parallelize program.
Stalling of this pipeline reduce execution speed.
Ins this paper, we detect this stall.
\end{eabstract}

% 表題
\maketitle

\newpage

% 本文
\section{はじめに}
当研究室ではこれまで家庭用ゲーム機上でのゲームプログラミングの開発を行ってきた。
過去には PlayStation や PlayStation2、GameBoyAdvance を用いており、
現在は PlayStation3(以下 PS3) で 動作するゲーム開発を行っている。
PS3 では Fedora や Yellow Dog Linux といった Linux O を動作させることができるので
(現在の公式のサポートは終了している)C や C++ といったプログラム言語を用いて
Linux 上でプログラミングすることが可能となっている。しかし、PS3 の Architecture である
CellBroadbandEngine は複数の SPE を使用する並列プログラミングが求められている。
そこで我々は Cell のような ManyCoreArchitecture を用いた、並列プログラムの開発を
サポートするフレームワークとして FineGrainTaskManager を開発した。
この TaskManager を用いたゲーム開発フレームワークが Cerium である。

Cerium を用いたゲーム開発ではプログラムの動作を Task という単位で管理し、
この Task と必要なデータを複数の SPE に転送して処理させる。
転送された各 TASK は並列に処理され、Pipeline で実行される。
本研究では Cerium に対して様々なテストを行い、
Cerium の チューニングやゲームプログラミングを補助するテスト手法を提案する。
%}{

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

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

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

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

\section{Cerium Engine}
Cerium は 独自の Rendering Engine と Scene Graph、Task Manager の3つによって構成される。
ゲーム中のオブジェクトの振る舞いやルール、Polygon Data は SceneGraph によって管理され、
それらの動きや Rendering の処理を動的に SPE に割り振るカーネルとして TaskManager が用いられる。
Cerium は C++ で実装されており、画像の読み込みや入力デバイスはSDL\footnote[1]{
Simple DirectMedia Layer。グラフィックやサウンドなどの API を提供するフリーのライブラリ。
} を用いて行っている。

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

\subsection{Task Manager}
Task Manager は Task と呼ばれる、分割された各プログラムを管理する。
Task の単位はサブルーチンまたは関数とする。
Task は主に PPE 内で生成され、処理する内容と必要なデータを設定する。
実行可能になった Task から各 SPE 割り当てられ、Task を受け取った SPE はその情報を元に
処理を実行する。

\subsection{Rendering Engine}\label{ssec:rendering}
現在、PlayStation3 の GPU にアクセスする API が公開されていないため、
Cerium の Rendering Engine では、オブジェクトの描画を Cell で並列処理している。
描画処理を段階別に以下の3種類の Task に分けている。

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

この3つの Task に依存関係を持たせ、CPU に送ることにより画面の描画を実現している。

\begin{figure}[tb]
\begin{center}
\includegraphics[width=5cm]{figure/scenegraph.eps}
\end{center}
\caption{Scene Graph Tree}
\label{fig:sg}
\end{figure}

\newpage

\section{Cerium の Task}

\subsection{Task ID}
Task ID とは、各 Task に割り振られたグローバル ID である。通常の逐次型プログラムでは
Task を選択して実行する場合、その関数ポインタを指定して実行すればいい。
しかし Cell の場合、PPE と SPE 上ではアドレス空間が異なるため、SPE 上で実行される 
Task を PPE から直接アドレス指定することはできない。そこで、Task 毎に ID を割り振り、
その ID から、SPE 上にある Task が格納された配列を参照して実行する。

\subsection{Task を実行させる CPU の選択}
Task Manager の {\bf set\_cpu()}により、Task をどの CPU で実行するか選択することが出来る。(図\ref{set_cpu})

\begin{figure}[tb]
\setbox0\vbox{
\hbox{//SPE 1 で実行する}
\hbox{task1\|->set_cpu(SPE_1);|}
\hbox{}
\hbox{//SPE のどれかで実行する}
\hbox{task2\|->set_cpu(SPE_ANY);|}
\hbox{}
\hbox{//PPE で実行する}
\hbox{task3\|->set_cpu(PPE);|}
}\fbox{\box0}
\caption{set\_cpu による実行 CPU の選択}
\label{fig:set_cpu}
\end{figure}

これにより、PPE 内でも Task を実行することが可能になるため、環境依存によるプログラム変換は 
Task の部分だけとなる。

\subsection{Task で入出力されるデータ}\label{ssec:inout}
Task に渡すデータとして、{\bf add\_inData}と{\bf add\_param}がある。
{\bf add\_inDara(addr, size)}は、Task に渡すデータのアドレスと、そのデータの
サイズを引数として入力する。このデータは DMA 命令により転送される。
{\bf add\_param(param)}は、Task に32 bit のデータを渡す。param はアドレスとして
ではなく、値を Task オブジェクトが直接持っているので DMA 命令による転送は行わない。

\subsection{Task 間の共用領域}
各 Task は独立して動作するため、使用するメモリ領域も他の Task と干渉することは無い。
しかし、処理によっては Task 間で同じデータを使用する場合がある。
その場合、Task 毎に同じデータを持つよりも、LS 上に一つロードしてそのデータを
各 Task が参照することが望ましい。
共用領域を allocate するには、{\bf global\_alloc(int id, int size)}を使う。id は
allocate した領域に割り振る番号で、size が allocate するバイト数を表す。
allocate した領域のアドレスは{\bf glbal\_get(int id)}で、global\_alloc() 時に
指定した id を渡すことで取得できる。 global\_alloc() した領域は、TaskManager 側で
解放することな無いのでユーザが{\bf global\_free(int id)}を実行する必要がある。
共用領域は各 SPE 上に置かれるので、違う SPE の領域を参照することはできない。

\subsection{Task の Dependency}\label{ssec:dependency}
Task に依存関係(Dependency)を持たせるには{\bf wait\_for}を使用する。

\setbox0\vbox{
\hbox{//task2 は task1 が終了してから開始する}
\hbox{task2\|->|wait\_for(task1);}
}\fbox{\box0}
\label{fig:single}

上記の場合には task1 は Active Queue へ、task2 は Wait Queue へ格納される。
Active Queue に格納された Task は各 SPE に送られ処理される。
終了した Task から PPE の Task Manager へタスク終了のコマンドを発行する。
コマンドを受け取った Task Manager は Wait Queue を調べ、依存関係を満たした Task から
Active Queue に移し、SPE へ送る。(図\ref{fig:dependency})

\begin{figure}[tb]
\begin{center}
\includegraphics[scale=0.45]{figure/dependency.eps}
\end{center}
\caption{Task の Dependency}
\label{fig:dependency}
\end{figure}

\subsection{Task 終了時に実行される関数}\label{ssec:set_post}
{\bf set\_post}を使うことでTask が終了した際に PPE で実行される関数と、
その引数を指定できる。(図\ref{fig:set_post})

{\bf set\_post}により、ユーザ側でも Task が終了したということを検知できる。
また、大量の Task に依存関係を設定する場合、一度に {bf create\_task}で生成し、
{\bf wait\_for}で繋げるというのは難しい。その場合、ある一定数の Task だけ
生成しておき、{\bf set\_post}を使って終了したことを確認して、その中で新たに 
Task を生成していくという方法により依存関係を設定することができる。

\begin{figure}[tb]
\setbox0\vbox{
\hbox{int data = 3;}
\hbox{task\|->|set\_post(func1, (void*)data);}
\hbox{}
\hbox{void}
\hbox{func1(void *data)}
\hbox{\|{|}
\hbox{\ \ printf\|("func1: data = %d\n", (int)data)|;}
\hbox{\|}|}
\hbox{//実行結果}
\hbox{func1: data = 3}
}\fbox{\box0}
\caption{set\_post による関数の設定}
\label{fig:set_post}
\end{figure}

\section{Super Dandy}
{\bf SuperDandy}は当研究室が PlayStation でのゲーム開発を行っていた時期に
開発されたシューティングゲームである。{\bf SuperDandy}は開発する環境が変わる度に
移植されており、過去には PlayStation2、MacOSX 用も作られた。今回、新たに 
MacOSX バージョンをベースとして Cerium で動作するバージョンを作成した。
SuperDandyが伝統的に移植されてきた背景には、ある程度のボリュームのあるゲームであること、
動作結果を過去の環境と比較することで新たな環境のチューニングが行えることが挙げられる。

\subsection{Super Dandy の Cerium への移植}
Cerium ではオブジェクトの管理は SceneGraph を用いて行っているが、
Super Dandy は独自にオブジェクトの管理を行なっている。また PutSprite という
描画用の関数が存在する。この関数は 
OpenGL\footnote[2]{
2D, 3D オブジェクトの描画の為のプログラムインターフェース
}
を使用しており、XY座標、テクスチャの指定を行うことによってオブジェクトの描画を
行うことができる。また、PutSprite の他にオブジェクトの拡大縮小が可能な PutSpriteEx
が存在する。Super Dandy を Cerium へ移植する場合には、この PutSprite, PutSpriteEx 
と同名の関数を用意し、その中で SceneGraph tree への登録を行うことで Cerium 上への
移植に成功した。また、この方法で移植することによってSuper Dandy 内で設定された
細かなパラメータを再利用でき、旧バージョンとの比較によって Cerium の機能の洗い出しを
することができる。具体的にはテクスチャの表示のズレ、光源処理のチューニングなどである。
また、元の PutSprite,PutSpriteEX を使うことにより旧バージョンを動かすことができる。
これにより異なる環境での動作の確認が容易に行える。

\subsection{Super Dandy on PlayStation3}
現在、この Super Dandy を Task ベースで動かすための移植作業を行っている。
Super Dandy を Task 化して PlayStation3 上で動かす場合、Cell Broadband Architecture
を意識する必要がある。Super Dandy は move(動作)やcollision(衝突判定)を関数ポインタ
で持っているが、それを Task 化して並列で動かす場合、PPE と SPE のメモリ領域は
異なるので関数ポインタのアドレスは使用できない。Cerium では Task を ID で管理しているので
それを使用して move や collision を行うのが望ましい。
Super Dandy を始め、ゲームには相互に干渉するパラメータが多数存在する。
共通のパラメータを必要とする Task 群を global\_alloc を使用して同じ Task 内で
処理させたり、Task 同士に依存関係を持たせる事が必要となる。
しかし、Task に複雑な依存関係を持たせると、Pipeline 処理がストールしてしまう原因となる。

\section{Pipeline のストール}
Task は SPE で並列処理させることで全体的な処理速度が増す。
しかし、PPE による処理が挟まれたり、Task の依存関係を解決するために時間がかかると
パフォーマンスが低下する。
例えばある Task の処理を複数の Task が待つような dependency が設定されていたとき、
依存している Task の処理に時間がかかると、動作していない SPE が発生してしまう。(図\ref{fig:stall})
これにより Task 処理の並列度が低下し、全体的なパフォーマンスの低下に繋がる。
Cerium で実行される各 Task は Pipeline 状に処理することによって全ての SPE を
常に busy 状態することにより、並列度を維持することが望ましい。(図\ref{fig:pipeline})
そこで Pipeline 上のストールを検出し、並列度の低い箇所を発見するテスト機構を実装した。

\begin{figure}[tb]
\begin{center}
\includegraphics[scale=0.6]{figure/stall.eps}
\end{center}
\caption{dependency によるストール}
\label{fig:stall}
\end{figure}

\begin{figure}[tb]
\begin{center}
\includegraphics[scale=0.5]{figure/pipeline.eps}
\end{center}
\caption{各 SPE による Task の Pipeline 実行}
\label{fig:pipeline}
\end{figure}

\subsection{Pipeline ストールの検出}
SPE の稼働率が低い場合、Task の依存関係の問題や
PPE 処理が挟まれている可能性がある。
そこで SPE の稼働率が低下している時の Task Queue を調べる。
この Task Queue には PPE で実行される Task を格納するキューと
SPE で実行される Task を格納するキューがあり、
それぞれ activeTaskQueue と waitTaskQueue を持つ。
ここで大きなパフォーマンスの低下を引き落としていると思われる 
PPE 側の TaskQueue を検証した。
また、キューの長さと格納されている Task ID を表示し、
どの Task がどれくらい積まれているかを調べた。

\subsection{ball\_bound}
ball\_bound は 3D のボールが画面内で跳ねる初歩的なプログラムである。
このボールの描画には Cerium の機能の一つである Rendering Engine が使われている。

\begin{figure}[tb]
\setbox0\vbox{
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = StartTask ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = CreatePolygonFromSceneGraph ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 6 }
\hbox{task\_name = CreateSpan ,task\_name = CreateSpan ,task\_name = CreateSpan ,}
\hbox{task\_name = CreateSpan ,task\_name = CreateSpan ,task\_name = CreateSpan ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = StartTask ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = CreatePolygonFromSceneGraph ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 6}
\hbox{...}
\hbox{4.073489 FPS}
}\fbox{\box0}
\caption{実行結果1}
\label{fig:result}
\end{figure}

図\ref{fig:result}を見ると3種類の Task が表示されているのが分かる。
{\bf StartTask }は全ての Task の一番初めに PPE で実行される Task である。
{\bf CreatePolygonFromSceneGraph}と{\bf CreateSpan}は\ref{ssec:rendering}節で述べたように
Rendering Engine の Task であるが、PPE 側の TaskQueue に格納されてしまっている。
これが実行速度の低下を招いていると考えられる。

上記の実行結果を検証したところ、SPE に送られる予定の Task が
PPE で実行される Task を待っている時、PPE 側の TaskQueue に
格納されてしまうバグがあることがわかった。
このバグを修正した結果が(図\ref{fig:result2})である。

\begin{figure}[tb]
\setbox0\vbox{
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = StartTask ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = CreatePolygonFromSceneGraph ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = StartTask ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = CreatePolygonFromSceneGraph ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = StartTask ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = CreatePolygonFromSceneGraph ,}
\hbox{...}
\hbox{3.059250 FPS}
}\fbox{\box0}
\caption{実行結果2}
\label{fig:result2}
\end{figure}

CreateSpan が正しく SPE に送られ、処理されている。
しかし、実行速度は低下してしまっている。これは SPE に送られた Task が
必要なデータを DMA 転送により取得しているため、その待ち時間と送信時間が
結果的に PPE 上での実行処理より遅延を引き起こしていると考えられる。

\section{まとめ}
TaskQueue に格納された Task と SPE の稼働率により、並列度の低い箇所を
知ることができた。しかし、処理速度は改善されていない。
同じ Task でも PPE 上での処理と SPE 上での処理にかかる時間が異なる。
そこで Task の 両環境での平均的な処理時間を取得することで、
CPU に適切な Task 処理の振り分けをすることができる。
また、今回の方法だけでは局所的な情報だけであり
Task がどのように展開されているのか、どの程度並列度が落ちているのかまではわからない。
登録された Task には set\_post や wait\_for で設定された依存関係が保存されており、
この情報のログを取り、依存関係の樹形図を可視化することができれば
Cerim における並列プログラミングを強力にバックアップすることができる。

\begin{thebibliography}{3}

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

\bibitem{article2}
FIXSTARS:http://cell.fixstars.com/ps3linux/index.php/メインページ

\bibitem{article3}
Mark Deloura:Game Programming Gems
株式会社ボーンデジタル 2001

\end{thebibliography}

\end{document}
\ No newline at end of file
+\documentclass[techrep]{ipsjpapers}
+\usepackage{graphicx}
+
+% 巻数，号数などの設定
+\setcounter{年数}{2011}
+
+% ユーザが定義したマクロなど．
+\makeatletter
+\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
+\def\<{\(\langle\)\nobreak}
+\def\>{\nobreak\(\rangle\)}
+\def\|{\verb|}
+\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
+\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
+\def\LATEX{\iLATEX\Large}
+\def\LATEx{\iLATEX\normalsize}
+\def\LATex{\iLATEX\small}
+\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
+    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
+\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
+\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
+\def\Quote{\list{}{}\item[]}
+\let\endQuote\endlist
+\def\TT{\if@LaTeX@e\tt\fi}
+\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
+	$\backslash$#1\fi}
+
+%\checklines	% 行送りを確認する時に使用
+\begin{document}%{
+% 和文表題
+\title[学生用 PS3 GameFrameWork Cerium での Pipeline ストールの検出]%
+	{学生用 PS3 GameFrameWork Cerium での\\Pipeline ストールの検出}
+% 英文表題
+\etitle{Detecting pipeline stall on PS3 GameFrameWork Cerium}
+% 所属ラベル
+\affilabel{UNI}{琉球大学 理工学研究科 情報工学専攻 並列信頼研究室\\
+                Concurrency Reliance Laboratory, Information Engineering Course,
+                Faculty of Engineering Graduate School of Engineering and Science,
+                University of the Ryukyus.}
+
+% 和文著者名
+\author{小林 佑亮\affiref{UNI}\and
+	河野 真治\affiref{UNI}\and
+        多賀野 海人\affiref{UNI}\and
+        金城　裕\affiref{UNI}}
+	
+% 英文著者名
+\eauthor{Yusuke Kobayashi\affiref{UNI}\and
+	 Shinji Kono\affiref{UNI}\and
+         Kaito Tagano\affiref{UNI}\and
+         Yutaka Kinjo\affiref{UNI}}
+
+% 和文概要
+\begin{abstract}
+我々は PlayStation3 上でのゲームプログラミングをサポートする Cerium Engine を開発した。
+Cerium におけるゲーム開発ではオブジェクトの描画や動作を Task という単位で管理しており、
+この Task を SPE に送り、Pipeline で実行することによってプログラムの並列化を図っている。
+この Pipeline におけるストールによって実行速度の低下が発生することが分かっている。
+本研究ではこのストールを検出することを考える。
+\end{abstract}
+% 英文概要
+\begin{eabstract}
+We developed Cerium Engine which support Game Programming on PlayStation3.
+Cerium managed drawing objects and movement in unit called Task.
+By sending SPE a Task and executing on pipeline,we attempt parallelize program.
+Stalling of this pipeline reduce execution speed.
+Ins this paper, we detect this stall.
+\end{eabstract}
+
+% 表題
+\maketitle
+
+\newpage
+
+% 本文
+\section{はじめに}
+当研究室ではこれまで家庭用ゲーム機上でのゲームプログラミングの開発を行ってきた。
+過去には PlayStation や PlayStation2、GameBoyAdvance を用いており、
+現在は PlayStation3(以下 PS3) で 動作するゲーム開発を行っている。
+PS3 では Fedora や Yellow Dog Linux といった Linux O を動作させることができるので
+(現在の公式のサポートは終了している)C や C++ といったプログラム言語を用いて
+Linux 上でプログラミングすることが可能となっている。しかし、PS3 の Architecture である
+CellBroadbandEngine は複数の SPE を使用する並列プログラミングが求められている。
+そこで我々は Cell のような ManyCoreArchitecture を用いた、並列プログラムの開発を
+サポートするフレームワークとして FineGrainTaskManager を開発した。
+この TaskManager を用いたゲーム開発フレームワークが Cerium である。
+
+Cerium を用いたゲーム開発ではプログラムの動作を Task という単位で管理し、
+この Task と必要なデータを複数の SPE に転送して処理させる。
+転送された各 TASK は並列に処理され、Pipeline で実行される。
+本研究では Cerium に対して様々なテストを行い、
+Cerium の チューニングやゲームプログラミングを補助するテスト手法を提案する。
+%}{
+
+\section{Cell Broadband Engine}\label{sec:Cell}
+CellBroadbandEngine は SCEI と IBM、東芝によって開発された CPU である。
+2 thread の PPE(PowerPC Processor Element)と
+8個の SPE(Synergistic Processor Element)からなる非対称なマルチコアプロセッサであり、
+高速リングバスであるEIB(Element Interface Bus)で構成されている。
+PS3 Linux では6個の SPE を使うことが出来る。(図\ref{fig:cell})
+
+\subsection{PPE(PowerPC Processor Element)}\label{ssec:PPE}
+PPE は Cell Broadband Engine のメインプロセッサで、
+複数の SPE をコアプロセッサとして使用することができる汎用プロセッサである。
+メインメモリや外部デバイスへの入出力、SPE を制御する役割を担っている。
+PPU(PowerPC Processor Unit)は、PPEの演算処理を行うユニットで、
+PowerPC アーキテクチャをベースとした命令セットを持つ。
+PPSS(PowerPC Processor Storage Subsystem)は PPU からメインメモリへのデータアクセスを
+制御するユニットである。
+
+\subsection{SPE(Synergistic Processor Element)}\label{ssec:SPE}
+SPE には 256KB の Local Store(LS)と呼ばれる直接参照できるメモリ領域があり、
+バスに負担をかける事なく並列に計算を進めることが出来る。
+SPE からメインメモリへは、直接アクセスすることは出来ず、SPE を構成する一つである
+MFC (Memory Flow Controller)へ、チャネルを介してDMA(Direct Memory Access)命令を送ることで行われる。
+
+\begin{figure}[tb]
+\begin{center}
+\includegraphics[scale=0.7]{figure/cell.eps}
+\end{center}
+\caption{Cell Broadband Engine}
+\label{fig:cell}
+\end{figure}
+
+\section{Cerium Engine}
+Cerium は 独自の Rendering Engine と Scene Graph、Task Manager の3つによって構成される。
+ゲーム中のオブジェクトの振る舞いやルール、Polygon Data は SceneGraph によって管理され、
+それらの動きや Rendering の処理を動的に SPE に割り振るカーネルとして TaskManager が用いられる。
+Cerium は C++ で実装されており、画像の読み込みや入力デバイスはSDL\footnote[1]{
+Simple DirectMedia Layer。グラフィックやサウンドなどの API を提供するフリーのライブラリ。
+} を用いて行っている。
+
+\subsection{Scene Graph}
+Cerium ではゲーム中の一つの場面(Scene)を構成するオブジェクトの頂点座標やテクスチャー、
+そしてその振る舞いの集合を SceneGraph としている。
+SceneGraph のノードは親子関係を持つ tree で構成される。親子関係とは、親オブジェクトの回転や
+並列移動等の行列計算による頂点座標の変更が、子オブジェクトにも反映する関係のことである。
+これは子に対してスタックに積まれた親の変換行列を掛けることで実現できる。(図\ref{sg})
+
+\subsection{Task Manager}
+Task Manager は Task と呼ばれる、分割された各プログラムを管理する。
+Task の単位はサブルーチンまたは関数とする。
+Task は主に PPE 内で生成され、処理する内容と必要なデータを設定する。
+実行可能になった Task から各 SPE 割り当てられ、Task を受け取った SPE はその情報を元に
+処理を実行する。
+
+\subsection{Rendering Engine}\label{ssec:rendering}
+現在、PlayStation3 の GPU にアクセスする API が公開されていないため、
+Cerium の Rendering Engine では、オブジェクトの描画を Cell で並列処理している。
+描画処理を段階別に以下の3種類の Task に分けている。
+
+\begin{itemize*}
+\item 
+SceneGraph が持つ Polygon の座標から、実際に画面に表示する座標の計算を行い、
+それを格納した PolyPack を生成する SceneGraph2PolygonPack Task
+\item 
+PolygonPack から同じ Y 座標を持つ線分の集合である SpanPack を生成する 
+PolygonPack2SpanPack Task
+\item 
+SpanPack を Texture を読み込みながら Z Buffer を用いて描画する DrawSpan Task
+\end{itemize*} 
+
+この3つの Task に依存関係を持たせ、CPU に送ることにより画面の描画を実現している。
+
+\begin{figure}[tb]
+\begin{center}
+\includegraphics[width=5cm]{figure/scenegraph.eps}
+\end{center}
+\caption{Scene Graph Tree}
+\label{fig:sg}
+\end{figure}
+
+\newpage
+
+\section{Cerium の Task}
+
+\subsection{Task ID}
+Task ID とは、各 Task に割り振られたグローバル ID である。通常の逐次型プログラムでは
+Task を選択して実行する場合、その関数ポインタを指定して実行すればいい。
+しかし Cell の場合、PPE と SPE 上ではアドレス空間が異なるため、SPE 上で実行される 
+Task を PPE から直接アドレス指定することはできない。そこで、Task 毎に ID を割り振り、
+その ID から、SPE 上にある Task が格納された配列を参照して実行する。
+
+\subsection{Task を実行させる CPU の選択}
+Task Manager の {\bf set\_cpu()}により、Task をどの CPU で実行するか選択することが出来る。(図\ref{set_cpu})
+
+\begin{figure}[tb]
+\setbox0\vbox{
+\hbox{//SPE 1 で実行する}
+\hbox{task1\|->set_cpu(SPE_1);|}
+\hbox{}
+\hbox{//SPE のどれかで実行する}
+\hbox{task2\|->set_cpu(SPE_ANY);|}
+\hbox{}
+\hbox{//PPE で実行する}
+\hbox{task3\|->set_cpu(PPE);|}
+}\fbox{\box0}
+\caption{set\_cpu による実行 CPU の選択}
+\label{fig:set_cpu}
+\end{figure}
+
+これにより、PPE 内でも Task を実行することが可能になるため、環境依存によるプログラム変換は 
+Task の部分だけとなる。
+
+\subsection{Task で入出力されるデータ}\label{ssec:inout}
+Task に渡すデータとして、{\bf add\_inData}と{\bf add\_param}がある。
+{\bf add\_inDara(addr, size)}は、Task に渡すデータのアドレスと、そのデータの
+サイズを引数として入力する。このデータは DMA 命令により転送される。
+{\bf add\_param(param)}は、Task に32 bit のデータを渡す。param はアドレスとして
+ではなく、値を Task オブジェクトが直接持っているので DMA 命令による転送は行わない。
+
+\subsection{Task 間の共用領域}
+各 Task は独立して動作するため、使用するメモリ領域も他の Task と干渉することは無い。
+しかし、処理によっては Task 間で同じデータを使用する場合がある。
+その場合、Task 毎に同じデータを持つよりも、LS 上に一つロードしてそのデータを
+各 Task が参照することが望ましい。
+共用領域を allocate するには、{\bf global\_alloc(int id, int size)}を使う。id は
+allocate した領域に割り振る番号で、size が allocate するバイト数を表す。
+allocate した領域のアドレスは{\bf glbal\_get(int id)}で、global\_alloc() 時に
+指定した id を渡すことで取得できる。 global\_alloc() した領域は、TaskManager 側で
+解放することな無いのでユーザが{\bf global\_free(int id)}を実行する必要がある。
+共用領域は各 SPE 上に置かれるので、違う SPE の領域を参照することはできない。
+
+\subsection{Task の Dependency}\label{ssec:dependency}
+Task に依存関係(Dependency)を持たせるには{\bf wait\_for}を使用する。
+
+\setbox0\vbox{
+\hbox{//task2 は task1 が終了してから開始する}
+\hbox{task2\|->|wait\_for(task1);}
+}\fbox{\box0}
+\label{fig:single}
+
+上記の場合には task1 は Active Queue へ、task2 は Wait Queue へ格納される。
+Active Queue に格納された Task は各 SPE に送られ処理される。
+終了した Task から PPE の Task Manager へタスク終了のコマンドを発行する。
+コマンドを受け取った Task Manager は Wait Queue を調べ、依存関係を満たした Task から
+Active Queue に移し、SPE へ送る。(図\ref{fig:dependency})
+
+\begin{figure}[tb]
+\begin{center}
+\includegraphics[scale=0.45]{figure/dependency.eps}
+\end{center}
+\caption{Task の Dependency}
+\label{fig:dependency}
+\end{figure}
+
+\subsection{Task 終了時に実行される関数}\label{ssec:set_post}
+{\bf set\_post}を使うことでTask が終了した際に PPE で実行される関数と、
+その引数を指定できる。(図\ref{fig:set_post})
+
+{\bf set\_post}により、ユーザ側でも Task が終了したということを検知できる。
+また、大量の Task に依存関係を設定する場合、一度に {bf create\_task}で生成し、
+{\bf wait\_for}で繋げるというのは難しい。その場合、ある一定数の Task だけ
+生成しておき、{\bf set\_post}を使って終了したことを確認して、その中で新たに 
+Task を生成していくという方法により依存関係を設定することができる。
+
+\begin{figure}[tb]
+\setbox0\vbox{
+\hbox{int data = 3;}
+\hbox{task\|->|set\_post(func1, (void*)data);}
+\hbox{}
+\hbox{void}
+\hbox{func1(void *data)}
+\hbox{\|{|}
+\hbox{\ \ printf\|("func1: data = %d\n", (int)data)|;}
+\hbox{\|}|}
+\hbox{//実行結果}
+\hbox{func1: data = 3}
+}\fbox{\box0}
+\caption{set\_post による関数の設定}
+\label{fig:set_post}
+\end{figure}
+
+\section{Super Dandy}
+{\bf SuperDandy}は当研究室が PlayStation でのゲーム開発を行っていた時期に
+開発されたシューティングゲームである。{\bf SuperDandy}は開発する環境が変わる度に
+移植されており、過去には PlayStation2、MacOSX 用も作られた。今回、新たに 
+MacOSX バージョンをベースとして Cerium で動作するバージョンを作成した。
+SuperDandyが伝統的に移植されてきた背景には、ある程度のボリュームのあるゲームであること、
+動作結果を過去の環境と比較することで新たな環境のチューニングが行えることが挙げられる。
+
+\subsection{Super Dandy の Cerium への移植}
+Cerium ではオブジェクトの管理は SceneGraph を用いて行っているが、
+Super Dandy は独自にオブジェクトの管理を行なっている。また PutSprite という
+描画用の関数が存在する。この関数は 
+OpenGL\footnote[2]{
+2D, 3D オブジェクトの描画の為のプログラムインターフェース
+}
+を使用しており、XY座標、テクスチャの指定を行うことによってオブジェクトの描画を
+行うことができる。また、PutSprite の他にオブジェクトの拡大縮小が可能な PutSpriteEx
+が存在する。Super Dandy を Cerium へ移植する場合には、この PutSprite, PutSpriteEx 
+と同名の関数を用意し、その中で SceneGraph tree への登録を行うことで Cerium 上への
+移植に成功した。また、この方法で移植することによってSuper Dandy 内で設定された
+細かなパラメータを再利用でき、旧バージョンとの比較によって Cerium の機能の洗い出しを
+することができる。具体的にはテクスチャの表示のズレ、光源処理のチューニングなどである。
+また、元の PutSprite,PutSpriteEX を使うことにより旧バージョンを動かすことができる。
+これにより異なる環境での動作の確認が容易に行える。
+
+\subsection{Super Dandy on PlayStation3}
+現在、この Super Dandy を Task ベースで動かすための移植作業を行っている。
+Super Dandy を Task 化して PlayStation3 上で動かす場合、Cell Broadband Architecture
+を意識する必要がある。Super Dandy は move(動作)やcollision(衝突判定)を関数ポインタ
+で持っているが、それを Task 化して並列で動かす場合、PPE と SPE のメモリ領域は
+異なるので関数ポインタのアドレスは使用できない。Cerium では Task を ID で管理しているので
+それを使用して move や collision を行うのが望ましい。
+Super Dandy を始め、ゲームには相互に干渉するパラメータが多数存在する。
+共通のパラメータを必要とする Task 群を global\_alloc を使用して同じ Task 内で
+処理させたり、Task 同士に依存関係を持たせる事が必要となる。
+しかし、Task に複雑な依存関係を持たせると、Pipeline 処理がストールしてしまう原因となる。
+
+\section{Pipeline のストール}
+Task は SPE で並列処理させることで全体的な処理速度が増す。
+しかし、PPE による処理が挟まれたり、Task の依存関係を解決するために時間がかかると
+パフォーマンスが低下する。
+例えばある Task の処理を複数の Task が待つような dependency が設定されていたとき、
+依存している Task の処理に時間がかかると、動作していない SPE が発生してしまう。(図\ref{fig:stall})
+これにより Task 処理の並列度が低下し、全体的なパフォーマンスの低下に繋がる。
+Cerium で実行される各 Task は Pipeline 状に処理することによって全ての SPE を
+常に busy 状態することにより、並列度を維持することが望ましい。(図\ref{fig:pipeline})
+そこで Pipeline 上のストールを検出し、並列度の低い箇所を発見するテスト機構を実装した。
+
+\begin{figure}[tb]
+\begin{center}
+\includegraphics[scale=0.6]{figure/stall.eps}
+\end{center}
+\caption{dependency によるストール}
+\label{fig:stall}
+\end{figure}
+
+\begin{figure}[tb]
+\begin{center}
+\includegraphics[scale=0.5]{figure/pipeline.eps}
+\end{center}
+\caption{各 SPE による Task の Pipeline 実行}
+\label{fig:pipeline}
+\end{figure}
+
+\subsection{Pipeline ストールの検出}
+SPE の稼働率が低い場合、Task の依存関係の問題や
+PPE 処理が挟まれている可能性がある。
+そこで SPE の稼働率が低下している時の Task Queue を調べる。
+この Task Queue には PPE で実行される Task を格納するキューと
+SPE で実行される Task を格納するキューがあり、
+それぞれ activeTaskQueue と waitTaskQueue を持つ。
+ここで大きなパフォーマンスの低下を引き落としていると思われる 
+PPE 側の TaskQueue を検証した。
+また、キューの長さと格納されている Task ID を表示し、
+どの Task がどれくらい積まれているかを調べた。
+
+\subsection{ball\_bound}
+ball\_bound は 3D のボールが画面内で跳ねる初歩的なプログラムである。
+このボールの描画には Cerium の機能の一つである Rendering Engine が使われている。
+
+\begin{figure}[tb]
+\setbox0\vbox{
+\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
+\hbox{task\_name = StartTask ,}
+\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
+\hbox{task\_name = CreatePolygonFromSceneGraph ,}
+\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 6 }
+\hbox{task\_name = CreateSpan ,task\_name = CreateSpan ,task\_name = CreateSpan ,}
+\hbox{task\_name = CreateSpan ,task\_name = CreateSpan ,task\_name = CreateSpan ,}
+\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
+\hbox{task\_name = StartTask ,}
+\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
+\hbox{task\_name = CreatePolygonFromSceneGraph ,}
+\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 6}
+\hbox{...}
+\hbox{4.073489 FPS}
+}\fbox{\box0}
+\caption{実行結果1}
+\label{fig:result}
+\end{figure}
+
+図\ref{fig:result}を見ると3種類の Task が表示されているのが分かる。
+{\bf StartTask }は全ての Task の一番初めに PPE で実行される Task である。
+{\bf CreatePolygonFromSceneGraph}と{\bf CreateSpan}は\ref{ssec:rendering}節で述べたように
+Rendering Engine の Task であるが、PPE 側の TaskQueue に格納されてしまっている。
+これが実行速度の低下を招いていると考えられる。
+
+上記の実行結果を検証したところ、SPE に送られる予定の Task が
+PPE で実行される Task を待っている時、PPE 側の TaskQueue に
+格納されてしまうバグがあることがわかった。
+このバグを修正した結果が(図\ref{fig:result2})である。
+
+\begin{figure}[tb]
+\setbox0\vbox{
+\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
+\hbox{task\_name = StartTask ,}
+\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
+\hbox{task\_name = CreatePolygonFromSceneGraph ,}
+\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
+\hbox{task\_name = StartTask ,}
+\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
+\hbox{task\_name = CreatePolygonFromSceneGraph ,}
+\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
+\hbox{task\_name = StartTask ,}
+\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
+\hbox{task\_name = CreatePolygonFromSceneGraph ,}
+\hbox{...}
+\hbox{3.059250 FPS}
+}\fbox{\box0}
+\caption{実行結果2}
+\label{fig:result2}
+\end{figure}
+
+CreateSpan が正しく SPE に送られ、処理されている。
+しかし、実行速度は低下してしまっている。これは SPE に送られた Task が
+必要なデータを DMA 転送により取得しているため、その待ち時間と送信時間が
+結果的に PPE 上での実行処理より遅延を引き起こしていると考えられる。
+
+\section{まとめ}
+TaskQueue に格納された Task と SPE の稼働率により、並列度の低い箇所を
+知ることができた。しかし、処理速度は改善されていない。
+同じ Task でも PPE 上での処理と SPE 上での処理にかかる時間が異なる。
+そこで Task の 両環境での平均的な処理時間を取得することで、
+CPU に適切な Task 処理の振り分けをすることができる。
+また、今回の方法だけでは局所的な情報だけであり
+Task がどのように展開されているのか、どの程度並列度が落ちているのかまではわからない。
+登録された Task には set\_post や wait\_for で設定された依存関係が保存されており、
+この情報のログを取り、依存関係の樹形図を可視化することができれば
+Cerim における並列プログラミングを強力にバックアップすることができる。
+
+\begin{thebibliography}{3}
+
+\bibitem{article1}
+宮國 渡: Cell 用の Fine-Grain Task Manager の実装.
+ 琉球大学大学院 理工学研究科 情報工学専攻 平成20年度 学位論文 2008.
+
+\bibitem{article2}
+FIXSTARS:http://cell.fixstars.com/ps3linux/index.php/メインページ
+
+\bibitem{article3}
+Mark Deloura:Game Programming Gems
+株式会社ボーンデジタル 2001
+
+\end{thebibliography}
+
+\end{document}