\chapter{Cell BE と Cerium} \label{chapter:early}
ここでは Cerium がターゲットとしている Cell Broadband Engine の説明と 
Game Framework Cerium の実装、および同じ並列プログラミングのフレームワーク
である OpenCL について説明する。

\section{Cell Broadband Engine}\label{sec:cell}
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})

\subsection{PPE (PowerPC Processor Element)}\label{sec:ppe}
PPE は Cell Broadband Engine のメインプロセッサで、複数の SPE を
コアプロセッサとして使用することができる汎用プロセッサである。
メインメモリや外部デバイスへの入出力、SPE を制御する役割を担っている。

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

\newpage

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

\section{Game Framework Cerium}\label{sec:cerium}
Cerium は我々が提案したゲーム開発フレームワークで、独自の Rendering Engine 
を持つ。ゲーム中のオブジェクトの振る舞いやルールは SceneGraph で管理し、
それらの動きやレンダリングの処理を動的に SPE に割り振るカーネルとして 
Task Manager が用いられる。Cerium は C++ で実装されており、画像の読み込みや
入力デバイスは SDL を用いて行っている。

\subsection{SceneGraph}\label{sec:scenegraph}
ゲームを構成するオブジェクトやその振る舞いを格納したノードの集合を 
SceneGraph とする。SceneGraph のノードは親子関係を持つ tree で構成される。
親子関係とは、親オブジェクトの回転や平行移動などの行列計算による
頂点座標の変更が、子オブジェクトにも反映する関係のことである。これは子に
対してスタックに積まれた親の変換行列を掛けることで実現できる。

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.6]{images/sgtree.pdf}
\end{center}
\caption{SceneGraph Tree}
\label{fig:sgtree}
\end{figure}

\newpage

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

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

Rendering Engine における描画処理は、SceneGraph から、実際に表示する
ポリゴンを抽出、ポリゴンから Span の生成、Span に RGB をマッピングし
描画する、といった 3 つの行程に分けることができる。そして各行程が Task として
定義され、Cerium に組み込まれている。
ここでいう Span とは、ポリゴンに対するある特定の Y 座標に関する
データを抜き出したものである。

\section{Task Manager}\label{sec:taskmanager}
Task Manager は、Cerium における並列処理を可能とするフレームワークであり、
Task と呼ばれる分割された各プログラムを管理する。Task の単位はサブルーチン
または関数とし、Task 同士の依存関係を考慮しながら実行していく。
現在実装されている基本的な TaskManager の API の実装を表 \ref{tb:tm_api} に
示す。また、本研究で使用した API の詳細については \ref{sec:tm_api} 節にて
述べる。

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

\section{メインスレッドの実装}\label{sec:main_thread}
メインスレッドでは、主に Task の起動と、Task に渡すオプションの設定を行う。
ここでは、Task の定義と、Task のオプション設定について説明する。

\subsection{Task の定義}\ref{task_struct}
実行される Task のデータ構造は以下のようになる。このデータは PPE、SPE の
各スレッドで使用される

\begin{verbatim}
class Task {
public: // variables
    int task_size;
    int command;
    int param_count;
    int inData_count;
    int outData_count;
    int inData_offset;
    int outData_offset;
    void *data[] __attribute__ ((aligned (DEFAULT_ALIGNMENT))); 
...
}

class ListElement {

int size;
memaddr addr;
\end{verbatim}

Task クラスは、各 CPU が実行する Task の単位オブジェクトである。
Task のサイズを示す task\_size や Task ID を格納する command といった
パラメータの他、後述する set\_param や set\_inData、set\_outData でセットした
値を格納する data というバッファを持つ。
以下は SPE が Task に格納された各種パラメータを用いて 処理を実行する
ステップである。(図\ref{fig:task_struct})

\begin{enumerate}
\item inDataElement にあるアドレス(メインメモリ空間)を参照し、DMA で
  メインメモリからデータを取得する
\item command を見て、どの Task を実行するか決定する
\item DMA read した値を Task に渡し、実行する
\item 演算結果の DMA 転送先を、outDataElement を参照して決定する
\item DMA write する
\end{enumerate}

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.7]{images/task_struct.pdf}
\end{center}
\caption{Task の構造と SPE からのデータの参照}
\label{fig:task_struct}
\end{figure}

\newpage

また、PPE では Task クラスの他に HTask クラスが存在する。

\begin{verbatim}
class HTask : public SimpleTask {

    QueueInfo<TaskQueue> *wait_me;  // List of task waiting for me
    QueueInfo<TaskQueue> *wait_i;   // List of task for which I am waiting
    PostFunction post_func;
    void *post_arg1;
    void *post_arg2;
    CPU_TYPE cpu_type;
...
\end{verbatim}

HTask は wait\_me、wait\_i というキューを持ち、Task の依存関係を記録する。
また、cpu\_type は Task が実行される CPU の切り替えに、post\_func と 
post\_arg は、Task 終了時に PPE で実行される関数と引数になる。
以上のことからわかるように、Task そのものにはコードの記述はなく、SPE にロード
してある Task の配列から、command に格納してある Task ID に従ってコードを
取得し、実行するだけである。よって、予めコード部分を SPE にロードしておく
必要がある。

\subsection{Task Manager の API}\label{sec:tm_api}
Task で並列処理をさせる時、ユーザはまず PPE 側で Task の生成、初期化を行う
必要がある。ここではその際に使用する Task Manager の API を紹介する。

\subsubsection*{create\_task}\label{sec:task_make}
Task を生成するには、TaskManager の API である {\bf create\_task }
を実行する。

\begin{verbatim}
HTaskPtr task = manager->create_task(ID);
\end{verbatim}

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

\subsubsection*{set\_cpu}\label{sec:set_cpu}
TaskManager の{\bf set\_cpu }により、Task をどの CPU で実行させるかを
選択する事ができる。

\begin{verbatim}
//SPE 1 で実行
    task1->set_cpu(SPE_1);
//SPE のどれかで実行
    task1->set_cpu(SPE_ANY);
//PPE で実行
    task1->set_cpu(PPE);
\end{verbatim}


\subsubsection*{set\_inData set\_outData set\_param}\label{sec:task_io}
Task に入力と出力先を渡す API として、{\bf set\_inData }と
{\bf set\_outData }、そして{\bf set\_param }がある。

\begin{verbatim}
    int a;
    Data *addr;

    task->set_param(0, (memaddr)a);
    task->set_inData(0, addr, sizeof(Data));
    task->set_outData(0, addr, sizeof(Data));
\end{verbatim}

set\_inData は格納する場所の番号と Task に渡すデータのアドレス、
そのデータのサイズを引数として入力する。このアドレスに格納されているデータは 
DMA 転送によって SPE に送られる為、16 バイトアライメントが取れており、
データサイズは 16 バイト倍数である必要がある。
set\_param は、Task に 32 bit のデータを DMA 転送ではなく、直接渡す。
このため set\_inData で渡すには小さいデータを送るのに適している。
Task の出力先は set\_outData で指定する。使用方法は set\_inData と
同じである。

\subsubsection*{wait\_for}\label{sec:dependency}
TaskManager は Task 依存を解決する機能を持っている。

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

この例では task1 が task2、task3 の終了を待つ。task2、task3 が終了すると
task1 が SPE に割り振られる。

\if0
この時、task1 は TaskManager の持つ waitTaskQueue へ、task2、3 は 
activeTaskQueue へ格納される。activeTaskQueue から各 CPU へ Task が
割り振られ、Task が終了したらメインスレッドへ Task 終了のメールを発行する。
メインスレッドはそれを受け取り、waitTaskQueue の Task を調べ、Task 依存を
満たした Task を activeTaskQueue に移し替える。
(図\ref{fig:dependency})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{images/dependency.pdf}
\end{center}
\caption{Task の依存関係の解決}
\label{fig:dependency}
\end{figure}
\fi

\subsubsection*{set\_post}\label{sec:set_post}
Task が終了した時、{\bf set\_post }を使うことでメインスレッドで実行される
関数と、その引数を指定できる。また、set\_post が実行されるタイミングで
ユーザが Task が終了したことを検知することができる。

\section{CPU スレッドの実装}\label{sec:cpu_thread}
各 CPU(PPE、SPE) では、メインスレッドで生成された Task を受け取り、その情報を
元に、Task を実行する。ここでは Task 処理の詳細と Task の本体部分の記述、
そして 本研究で使用した API について説明する。

\subsection{Task の処理}\label{sec:task_exec}
Task 本体の記述例は以下のようになっている。

\begin{verbatim}
static int
state(SchedTask *smanager, void *rbuf, void *wbuf)
{
    CHARACTER *p = (CHARACTER*)smanager->get_input(rbuf, 0);
    CHARACTER *q = (CHARACTER*)smanager->get_output(wbuf, 0);    
    player *jiki = (player*)smanager->get_input(rbuf, 1);
    
    p->y += p->vy;
    p->x += p->vx;
    if ((p->y < jiki->y) && (p->y + 16 > jiki->y)) {
        p->vy = -2;
        p->vx = ((jiki->x > p->x) ? 4 : -4);
    }
    *q = *p;
    return 0;
}
\end{verbatim}

これは図\ref{fig:task_struct} の (3) にあたる処理である。
\ref{sec:task_io} 節でセットしたデータを get\_input で受け取り、
get\_output で書き出し用のバッファのアドレスを受け取っている。
上記の例では、セットしたデータを用いて処理した後で書き出し用のバッファに
書き込んでいる。

\newpage

\subsection{SchedTask}\label{sec:schedtask}
SchedTask とは、Task の処理中に Task に関する処理を行うことができる
オブジェクトで、Task の引数として与えられている。SchedTask の API を
表 \ref{tb:st_api} に示す。

\begin{table}[h]
\caption{SchedTask の API}
\begin{tabular}{c|l} 
\hline
\hline
create\_task & Task を生成する \\ \hline
allocate & 環境のアライメントを考慮したメモリアロケータ\\ \hline \hline
get\_input & set\_inData で指定したデータを取得する \\ \hline
get\_output & set\_outData で指定した領域に書きこむバッファを取得する \\ \hline
get\_param & set\_param で指定した 32 ビットデータを取得する \\ \hline \hline
global\_alloc & Task 間で共用するデータの allocate \\ \hline
global\_get & global\_alloc した領域のアドレスを取得 \\ \hline
global\_free & global\_alloc した領域の free \\ \hline \hline
mainMem\_alloc & メインメモリ上の allocate \\ \hline
mainMem\_get & mainMem\_alloc した領域のアドレス(メインメモリ空間)を取得 \\ \hline
mainMem\_wait & mainMem\_alloc が完了するまで待つ \\ \hline
\end{tabular}
\label{tb:st_api}
\end{table}

\subsubsection*{Input Data の取得}\label{sec:indata}
\ref{sec:task_exec} 節のコードの rbuf にはメインスレッドで set\_inData により
指定したデータの実体が入っている。(図\ref{fig:rbuf})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{images/rbuf.pdf}
\end{center}
\caption{set\_inData による rbuf の構造}
\label{fig:rbuf}
\end{figure}

\newpage

このデータを扱う場合、直接 rbuf を見るのではなく

\begin{verbatim}
int *data = (int*)smanager->get_input(rbuf, index);
\end{verbatim}

というようにして取得する。index は set\_inData で指定した番号になる。
同様に set\_param で設定した値は、get\_param(index) で得られる。ここの index 
も get\_input と同じく、指定した番号である。

\subsubsection*{Output Data の取得}\label{sec:outdata}
Task が出力を行う場合、Task 生成時に set\_outData を行い、出力先のアドレスと
データサイズが指定されている。wbuf は rbuf 同様、指定したサイズ分の
バッファで、Task の処理を行う前に生成時に設定したデータサイズを元にバッファを
 allocate する。wbuf はこの時点ではただのバッファで、中には何も入っていない
(不定)。Task 処理の終了時、wbuf の値を set\_outData で指定したアドレスに DMA 
転送する。(図\ref{fig:wbuf})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.6]{images/wbuf.pdf}
\end{center}
\caption{set\_outData による wbuf の構造}
\label{fig:wbuf}
\end{figure}

\subsubsection*{Task 間の共用空間}\label{sec:global}
各 Task は独立して動作するため、使用するメモリ領域も他の Task と干渉すること
はない。しかし、処理によっては Task 間で同じデータを使用する場合がある。
共用領域を allocate するには global\_alloc を使う。
allocate した領域のアドレスは global\_get で取得できる。
global\_alloc した領域はユーザが global\_free で解放する必要がある。

共用領域は各 SPE に置かれるので、違う SPE の領域を参照する事はできない。
従って、同じデータを使う可能性の Task を同じ SPE 上で実行させることにより、
メモリ領域も軽減できる。(図\ref{fig:global})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.6]{images/global.pdf}
\end{center}
\caption{Task 間の共用領域}
\label{fig:global}
\end{figure}

\section{OpenCL}\label{sec:opencl}
OpenCL(Open Computing Language) とは、マルチコア CPU や GPU、その他の
プロセッサによる、ヘテロジニアスコンピューティングのフレームワークである。
OpenCL のプラットフォームモデルは Host と複数の OpenCL Device で
構成されている。OpenCL devices の中では Compute Units(CUs) として分割され、
その中でさらに Processing Elements(PEs) として分割される。

\if0
(図\ref{fig:opencl})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{images/opencl.pdf}
\end{center}
\caption{OpenCL Platform}
\label{fig:opencl}
\end{figure}
\fi

また、OpenCL Device は 4 つの違うメモリ領域 (Global Memory, Constant Memory, 
Local Memory, Private Memory) を持ち、それぞれ Host や CUs、PEs からの
アクセス権限が異なる(アドレス空間が異なる)。プログラミングモデルとしては、
データ並列、タスク並列をサポートしている。OpenCL は Host や各 device に 
kernel があることや、device 毎にメモリアドレス空間が違う、
プログラミングモデル等、TaskManager とよく似ている。