\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}

\end{eabstract}

% 表題
\maketitle

% 本文
\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{CellBroadbandEngine}
\label{fig:cell}
\end{figure}

\newpage

\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 で構成される。親子関係とは、親オブジェクトの回転や
並列移動等の行列計算による頂点座標の変更が、子オブジェクトにも反映する関係のことである。
これは子に対してスタックに積まれた親の変換行列を掛けることで実現できる。

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

\subsubsection{Task の Dependency}\label{sssec:dependency}
Task には依存関係(Dependency)を持たせることができる。以下に記述例を示す。

\begin{verbatim}
//task2 は task1 が終了してから開始する
task2->wait_for(task1);
\end{verbatim} 

上記の場合には 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.6]{figure/dependency.eps}
\end{center}
\caption{CellBroadbandEngine}
\label{fig:dependency}
\end{figure}

\subsubsection{}

\subsection{Rendering Engine}\label{ssec:rendering}
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 は画面の描画毎にパイプライン的に実行される

\newpage

\section{Task の Dependency}
Cerium の Task には依存関係を持たせる機能がある。

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

\end{document}