--- a/paper/chapter2.tex	Sat Jan 14 00:16:39 2012 +0900
+++ b/paper/chapter2.tex	Tue Feb 07 17:38:59 2012 +0900
@@ -1,4 +1,587 @@
-\chapter{議論}
+\chapter{Cerium} \label{chapter:cerium}
+Cerium \cite{gongo} は Cell 用の Fine-Grain Task Manager として同研究室の宮國が実装した。
+本章ではその実装について説明する
+
+\section{Cerium の概要}
+
+Cerium は、我々が提案したフレームワークで、TaskManager (\ref{sec:cerium_taskmanager}), 
+SceneGraph (\ref{sec:cerium_scenegraph}) と Rendering Engine (\ref{sec:cerium_renderingengine}) の
+３つの要素から構成されており、PS3, Mac OS X, Linux 上でゲームフレームワークとして動作する。ゲーム中の
+オブジェクトの振る舞いやルールは SceneGraph で管理し、それらの動きや Rendering の処理を動的に SPE に
+割り振るカーネルとして、TaskManager が用いられる。PS3 の Graphics Engine の仕様は公開されておらず、
+Cerium は独自の Rendering Engine を有している。
+
+\section{Cerium TaskManager} \label{sec:cerium_taskmanager}
+
+Task Manager は、 Task と呼ばれる、分割された各プログラムを管理する。 Task の単位は
+サブルーチンまたは関数として、 Task 同士の依存関係を考慮しながら実行していく。
+先行研究において実装されていた TaskManager の API を \tabref{old_taskmanager_api} に示す。
+\begin{table}[htb]
+  \caption{旧Task Manager API} \label{tab:old_taskmanager_api}
+  \hbox to\hsize{\hfil
+  \begin{tabular}{|c|l|} \hline
+    create\_task  & Task を生成する \\ \hline
+    run           & 実行 Task Queue の実行 \\ \hline
+    allocate      & 環境のアライメントを考慮した allocator \\ \hline
+    set\_inData   & Task への入力データのアドレスを追加 \\ \hline
+    set\_outData  & Task からのデータ出力先アドレスを追加 \\ \hline
+    set\_param    & Task のパラメータ (32 bits) \\ \hline
+    wait\_for     & Task の依存関係の考慮 \\\hline
+    set\_cpu      & Task を実行する CPU の設定 \\ \hline
+    set\_post     & Task が終了したら PPE 側で実行される関数の登録 \\ \hline
+    spawn         & Task を実行 Task Queue に登録する \\ \hline
+  \end{tabular}\hfil}
+\end{table}
+
+\section{Cerium における Task} \label{sec:task_depandency}
+
+Task は TaskManager を使って生成する。 Task を生成する際に、以下のような要素が設定可能
+である。
+
+\begin{enumerate}
+\item input data
+\item output data
+\item parameter
+\item cpu type
+\item dependency
+\end{enumerate}
+
+input, output, data, parameter は関数でいうところの引数に価する。cpu type は Task が 
+PPE または SPE のどちらで実行されるかを示している。 dependency は他の Task との
+依存関係を示している。依存関係の情報は PPE 側が持っており、 SPE, PPE の Task が終了
+すると、Task の終了が通知され、その通知に従って PPE が依存関係を処理していく（例: 
+Task A の終了通知を受け、 PPE は Task B を実行可能状態にする)。Task の依存関係の
+処理を図を用いて説明する。\\
+
+Task B は Task A の終了を待っている。他の Task の終了を待っている Task は、Wait Queue に、
+Task を待っていない Task は Active Queue に入れる。この時点で Task A が先頭にあるので 
+Task A が SPE に送られる(\figref{task-dependency1})。
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.70]{./images/task-dependency1.pdf}
+  \end{center}
+  \caption{Task dependency 1}
+  \label{fig:task-dependency1}
+\end{figure}
+
+\newpage
+
+そして、SPE に送られた Task A は SPE で処理が行われる(\figref{task-dependency2})。
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.68]{./images/task-dependency2.pdf}
+  \end{center}
+  \caption{Task dependency 2}
+  \label{fig:task-dependency2}
+\end{figure}
+
+Task A の処理が終了すると mail で Task B へ通知される。Task B はその通知を受け取ると
+待ち状態が解除される(\figref{task-dependency3})。
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.68]{./images/task-dependency3.pdf}
+  \end{center}
+  \caption{Task dependency 3}
+  \label{fig:task-dependency3}
+\end{figure}
+
+待ち状態が解除された Task B は、Active Queue に追加され、
+この図(\figref{task-dependency4})では、Task C 終了後に
+SPE に送られ処理が行われる。
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.68]{./images/task-dependency4.pdf}
+  \end{center}
+  \caption{Task dependency 4}
+  \label{fig:task-dependency4}
+\end{figure}
+
+\newpage
+
+\section{Task のスケジューリング}
+
+SPE は、Task を一つずつ受け取るのではなく、ある程度まとめて受け取る。それを TaskList 
+と呼んでいる。 TaskList は各 SPE 用に PPE側で生成される。(\figref{task_scheduler})
+SPE は 受け取ったTaskList に沿って Task を実行していき、 Task 毎に実行完了の Mail を送る。
+TaskList の Task をすべて実行すると、次の TaskList を要求する Mail を PPE 側に送る。
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.61]{./images/scheduler.pdf}
+  \end{center}
+  \caption{Task scheduler}
+  \label{fig:task_scheduler}
+\end{figure}
+
+
+\section{Task の入出力} \label{sec:input_output}
+
+Task の入出力の API として、set\_inData, set\_param , set\_oudData がある。
+\begin{description}
+
+\item[set\_inData(index, addr, size)] は、 データを受け取る buffer の配列番号とデータのアドレス、そのデータのサイズを
+引数として入力する。このデータは DMA 転送されるため、addr は 16 byte alignment が取れており、size は 16 byte の
+倍数である必要がある。
+
+\item[set\_param(index, param)] は、データを受け取る buffer の配列番号と 32bit のデータを渡す。set\_inData で渡すには
+小さいデータを送るのに適している。 param はアドレスとしてではなく、値を Task オブジェクトが直接持っているので、 DMA 
+転送は行わない。
+
+\item[set\_outData(index, addr, size)] は、Task のデータの出力先を指定する。使用方法は set\_inData と同じで、alignment, 
+byte 数に気をつける必要がある。
+
+\end{description}
+\section{SceneGraph} \label{sec:cerium_scenegraph}
+
+本研究では、ゲーム中の一つの場面 (Scene) を構成するオブジェクトやその振る舞い、ゲームのルールの集合を SceneGraph とする \cite{chiaki}。SceneGraph のノードは親子関係を持つ tree で構成される(\figref{scenegraph})。親子関係とは、親オブジェクトの
+回転や平行移動などの行列計算による頂点座標の変更が、子オブジェクトにも反映する関係のことである。これは子に対して
+スタックに積まれた親の変換行列を掛けることで実現できる。SceneGraph ノードは以下のようなデータと動作を持つ。
+
+\begin{description}
+\item[Vertex:] ポリゴンオブジェクトの頂点座標
+\item[Texture:] ポリゴンオブジェクトのテクスチャ座標
+\item[TextureImage:] テクスチャイメージ
+\item[TransMatrix:] ポリゴンオブジェクトの変換行列
+\item[Coordinates:] オブジェクトの座標
+\item[Angle:] オブジェクトの角度
+\item[Move:] 自律的なオブジェクトの動き
+\item[Collision:] 他のノードと衝突したときの動き
+\end{description}
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.61]{./images/scenegraph.pdf}
+  \end{center}
+  \caption{SceneGraph}
+  \label{fig:scenegraph}
+\end{figure}
+
+\subsection{Scene ポリゴンの生成}
+
+ゲーム中に登場するオブジェクトは、オープンソースの 3D モデリングツール
+である Blender \cite{blender} を用いる。
+Blender で記述したポリゴンオブジェクトを、座標やテクスチャイメージを
+埋め込んだ xml ファイルとして出力する。
+Blender にはPython インタプリタがあり、xml ファイルを生成する Python スクリプトを作成している。
+xml には、オブジェクトの名前、ポリゴン情報、ポリゴンに対応するテクスチャ座標、
+テクスチャイメージがある。
+
+xml ファイル形式を採用している理由は、Cerium が MacOSX や PS3 Linux などの
+複数の環境で動作することを目的としており、環境に依存しないテキスト形式での
+データ構造を構築できるからである。また、Cerium は将来的にネットワークを
+使用することを考えており、その際に有効なフォーマットであると考えたからである。\\
+
+ネットワークを使用した例題として、Federated Linda \cite{akamine}
+を用いた「水族館ゲーム」を赤嶺が作成した。
+
+このゲームは、複数のクライアントのディスプレイを並べて使用する。各プレイヤーは１匹
+ずつ魚のオブジェクトが与えられ、それを自由に操作することができる。また、魚は画面の
+端まで移動すると、自分の画面上からは消え、接続している他のプレイヤーの画面の端
+から出てくる。(\figref{aquarium}) このゲームは、初めに xml ファイルをすべての
+プレイヤーが共有した状態で開始される。
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.61]{./images/aquarium.pdf}
+  \end{center}
+  \caption{水族館ゲーム}
+  \label{fig:aquarium}
+\end{figure}
+
+\subsection{SceneGraph オブジェクトの生成} \label{sec:cerium_renderingengine}
+
+Cerium は生成された xml ファイルから、そのパラメータを持つ SceneGraph オブジェクト
+を生成する (Original SceneGraph)。ここで作られたオブジェクトはユーザには見せず、
+ユーザが該当する SceneGraph を生成したい場合は Original を参照し、そのコピー
+(Copy SceneGraph) を渡す。
+
+Original SceneGraph の情報は Cerium が配列として持っており、xml ファイルを
+読み込んで生成された SceneGraph を SceneGraph ID の位置に格納する。
+SceneGraph ID は SceneGraph に割り当てられるグローバル ID である。配列に
+格納する時点で登録された順に ID が割り当てられる。改良後では、同時に、 Scenegraph の
+名前を key, ID を value として hash に登録しているので、ユーザは ID と
+名前の両方から Scenegraph を生成することができる。
+
+
+\section{RenderingEngine}
+RenderingEngineは TaskManager から提供される Task から構成され、主に以下の3つの Task から成る。(\figref{rendering_flow})
+
+\begin{description}
+\item[CreatePolygonTask: ] SceneGraph での処理結果を元に、モデリングデータの座標変換を行う
+\item[CreateSpanTask: ] 座標変換されたポリゴンを、水平な線(Span)に分割する
+\item[DrawSpanTask: ] 分割された Span を実際に画面へと描画する。
+\end{description}
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.5]{./images/rendering3.pdf}
+  \end{center}
+  \caption{Rendering flow}
+  \label{fig:rendering_flow}
+\end{figure}
+
+これら Task の入出力のデータとして、PolygonPack, SpanPack がある。それぞれポリゴンの情報を格納する構造体、Spanの情報を格納する構造体である。Task と合わせてその構造体について説明していく。
+
+\subsubsection{PolygonPack}
+
+PolygonPack は、SceneGraph から抽出されたポリゴンの集合である。CreatePolygonTask で扱う構造体である。
+以下に構造を示す。
+
+\begin{verbatim}
+// ポリゴンを構成する情報
+typedef struct TrianglePack {
+    // テクスチャ情報
+    TriTexInfo tex_info; 
+
+    // ポリゴンを構成する頂点の情報
+    VertexPack ver1, ver2, ver3;
+    
+    // 法線ベクトルの情報
+    NormalPack normal1, normal2, normal3;
+
+} TrianglePack, *TrianglePackPtr;
+
+typedef struct PolygonPack {
+
+    TrianglePack tri[MAX_SIZE_TRIANGLE];
+
+    struct POLYGON_info {
+        int size;
+        int light_pos[3]; // 光源の位置
+        int light_rgb[3]; // 光源の色
+    }info;
+    PolygonPack* next;
+} PolygonPack, *PolygonPackPtr;
+\end{verbatim}
+
+\begin{description}
+\item[TriTexInfo] は、テクスチャイメージのアドレス、幅、高さ、
+縮小率が格納されている
+
+\item[VertexPack] は、ポリゴンの頂点座標と対応するテクスチャの座標が
+格納されている
+
+\item[NormalPack] は、ポリゴンの法線ベクトルの情報が格納されている
+
+\newpage
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.70]{./images/polygonpack.pdf}
+  \end{center}
+  \caption{PolygonPack(TrianglePack)}
+  \label{fig:polyonpack}
+\end{figure}
+
+\end{description}
+
+PolygonPack は光源やテクスチャ、頂点の情報から構成される。
+テクスチャの縮小率に関しては \ref{sec:cerium_scale} で詳しく説明する。
+
+\subsubsection{SpanPack}
+
+SpanPack は、ポリゴンから抽出された Span の集合である。CreateSpan で PolygonPack を元に SpanPack が生成される。以下に構造を示す。
 
-\section{はじめに}
-はじめに
+\begin{verbatim}
+class Span {
+public:
+    // テクスチャ情報
+    uint32 *tex_addr;
+    int tex_width, tex_height;
+
+    // span の開始 x 座標、y 座標、長さ
+    int x, y, length_x;
+
+    // span の z 座標(開始、終了)
+    float start_z, end_z;
+
+    // span に対応するテクスチャの座標
+    float tex_x1, tex_x2, tex_y1, tex_y2;
+
+    // span の法線ベクトル
+    float normal_x, normal_y, normal_z;
+};
+
+class SpanPack {
+public: /* fields */
+    struct SpanInfo {
+        int start;
+        int size;
+        int y_top;
+        int light_pos[3];
+        int light_rgb[3];
+    } info;
+    Span span[MAX_SIZE_SPAN];
+    SpanPack *next;
+};
+\end{verbatim}
+
+Span は、その座標と対応するテクスチャの座標を持つ(\figref{cerium_span})
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.80]{./images/spanpack.pdf}
+  \end{center}
+  \caption{Span の構造}
+  \label{fig:cerium_span}
+\end{figure}
+
+Rendering には SpanPack を用いる。
+ここからは、SceneGraph から Rendering までの流れを それぞれの Task を用いて説明する。
+
+\subsection{CreatePolygonTask} \label{createpolygonfromscenegraph}
+
+SceneGraph の move や collision を行い、各オブジェクトの変換行列
+を生成する。その後、SceneGraph が持つポリゴンの座標と法線ベクトルに
+変換行列をかけ、得られた座標を PolygonPack に格納していく。
+これまでは関数で書かれていたが、SPE に処理を割り振ることも視野に入れ、
+Task で書いている。新しい Rendering のデータ構造で述べた法線ベクトルの
+計算も追加している。以下がそのコードである。
+
+\newpage
+
+\begin{verbatim}
+
+SceneGraphPtr sg_top = sg_draw_tree;
+
+// ポリゴンの１辺
+xyz1[0] = sg->coord_xyz[(i+0)*3];
+xyz1[1] = sg->coord_xyz[(i+0)*3+1];
+xyz1[2] = sg->coord_xyz[(i+0)*3+2]*-1.0f;
+xyz1[3] = 1.0f;
+
+/* xyz2, xyz3 は省略 */
+
+// ポリゴンの１辺の法線ベクトル
+normal1[0] = sg->normal[(i+0)*3];
+normal1[1] = sg->normal[(i+0)*3+1];
+normal1[2] = sg->normal[(i+0)*3+2]*-1.0f;
+
+/* normal2, normal3 は省略 */
+
+// sg->matrix = 回転行列*透視変換行列
+ApplyMatrix(xyz1, sg->matrix);
+ApplyMatrix(normal1, sg->real_matrix);
+
+// PolygonPack の TrianglePack　に計算した値とテクスチャの座標を格納する
+PolygonPackPtr pp = new PolygonPack;
+TrianglePack *triangle = &pp->tri[pp->info.size++];
+
+triangle->ver1.x = xyz1[0];
+triangle->ver1.y = xyz1[1];
+triangle->ver1.z = xyz1[2];
+triangle->ver1.tex_x = sg->coord_tex[(i+0)*3];
+triangle->ver1.tex_y = sg->coord_tex[(i+0)*3+1];
+triangle->normal1.x = normal1[0];
+triangle->normal1.y = normal1[1];
+triangle->normal1.z = normal1[2];
+
+/* ver2, ver3, normal2. normal3 は省略 */
+
+// テクスチャのアドレス、幅、高さ、縮小率を格納する
+triangle->tex_info.addr   = sg->texture_info.pixels;
+triangle->tex_info.width  = sg->texture_info.t_w;
+triangle->tex_info.height = sg->texture_info.t_h;
+triangle->tex_info.scale_max = sg->texture_info.scale_max;
+\end{verbatim}
+
+これらの処理を全ての Scenegraph に行い、PolygonPack を生成していく。
+
+\subsection{CreateSpanTask} \label{createspan}
+
+生成された PolygonPack に格納されているポリゴンから、Span を抽出していく。
+Span は x 軸に平行な線分を表しているため、初めにポリゴンを水平に分割して
+二つの三角形 (Triangle1, Triangle2) を作り、それぞれに対してSpan を求める 
+\cite{akira} (\figref{sep-polygon})。
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.90]{./images/sep-polygon.pdf}
+  \end{center}
+  \caption{ポリゴンの分割と Span 生成}
+  \label{fig:sep-polygon}
+\end{figure}
+
+得られた Span を SpanPack に格納する場合、その SpanPack が持つ全ての Span の y 座標
+が一定範囲内に入るようにする。
+
+Rendering する場合、画面を複数の領域に分割し、それぞれを一つの Task で担当する。Cerium 
+では Rendering 時に Z Buffer を用いているため、同じ Task に違う領域の Span があると
+正常に描画できない。そこで、一つの SpanPack には決まった y 座標を持った Span だけを
+入れることにより、Rendering 時には独立して行うことができる。
+y の範囲は 8 としている(\figref{spanpack-rendering})。
+
+\newpage
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.80]{./images/spanpack-rendering.pdf}
+  \end{center}
+  \caption{SpanPack の割り当て(height = 1080)}
+  \label{fig:spanpack-rendering}
+\end{figure}
+
+\subsection{Rendering するための準備}
+
+画面に Rendering するためには、SpanPack の中の Span を辿り、対応する RGB 値をテクスチャイメージから取り出して
+ frame buffer に書きこむ必要がある。しかし、SPE のメモリ領域は 256KB しかないため、Span が参照している
+テクスチャイメージ全てを SPE に送ることはできない。
+
+そこで我々は、テクスチャイメージに対して分割、Tile管理、縮小という操作を行うことでこの問題
+を解決した。
+
+\subsection{Texture の分割} \label{separate_texture}
+
+SPE のメモリ領域は 256KB しかないため、テクスチャイメージを全て転送すると動かなくなる可能性がある。
+そこで、そこで、テクスチャをブロックに分割し、ブロックごとに転送することにした。そのブロックを Tile 
+と呼び、分割単位は 8 x 8 とする(\figref{cerium_tile})。Tile は \figref{cerium_tile} 
+の順番で配列に変換する。
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.80]{./images/cerium_tile.pdf}
+  \end{center}
+  \caption{Texture の分割と Tile}
+  \label{fig:cerium_tile}
+\end{figure}
+
+Span が持つテクスチャのアドレスはこの配列を指しており、描画する Span 中の 1 pixel の座標から、
+目的の Tile を計算する。その Tile をメインメモリから DMA で持ってきて RGB 値を取り出す。
+
+\subsection{SPE 上での Tile 管理}
+
+描画 Task が変わるたびに、新しい Tile を転送していては、DMA 転送のコストがかかりすぎる。そこで、
+すでに SPE 上に転送してある Tile を保存しておく。そして、次に描画する Span が保存してある Tile 
+を参照する場合、新たに DMA 転送を行わずに保存してある Tile を使用する。新たに Tile を参照し且つ領域に
+空きが無い場合、 FIFO で Tile の入れ替えを行う。Tile の検索は、テクスチャのアドレスを key とし、
+Tile を value としてハッシュを用いる。 
+\begin{comment}
+SPE 上で保存する Tile の数を変化させることによって、Rendering の実行速度がどのように変化するか
+実験した(\figref{cerium_hash_test})。
+
+\begin{table}[htb]
+  \begin{center}
+    \caption{SPE 上での Tile 管理数による実行速度比較} \label{tab:cerium_hash_test}
+    \hbox to\hsize{\hfil
+      \begin{tabular}{c|l} \hline \hline
+        Tile 保存数 & 実行速度 (FPS) & \\ \hline
+        \hline
+        1 &  &\\ \hline
+        128 &  &\\ \hline
+      \end{tabular}\hfil}
+  \end{center}
+\end{table}
+
+\figref{cerium_hash_test} より、SPE 上で保存する Tile の数を増やすことによりテクスチャ
+のヒット率が上昇し、DMA 転送回数が減ることで実行速度が向上するがわかる。
+
+\end{comment}
+
+\subsection{Texture の縮小} \label{sec:cerium_scale}
+
+遠くにあるオブジェクトは小さく描画される。この場合、使用されるテクスチャは原寸大である
+必要がない。そこで、オリジナルのテクスチャの他に縮小したテクスチャを用意し、描画される
+オブジェクトの大きさによって、使用するテクスチャを変更する。
+
+テクスチャは Tile に分割しなければならないため、縦横ともに 8 の倍数を保つようにする。
+これまでは、テクスチャの縦横どちらかのサイズが最小 (8ドット) になったとき、縮小画像生成を終了
+していたが、テクスチャのサイズが縦横で違う場合、長い方に合わせて空のデータを埋め込み 8 の倍数
+の正方形にするように改良した。この改良によってテクスチャの最大縮小率を正確に求めることが出来るよう
+になったこの制約を守りながら 2 分の 1 ずつ縮小させたときの最大縮小率を求める。縮小したテクスチャ
+毎に Tile で分割し、すべての縮小率で求めた Tile を繋げて Tile Array とする(\figref{tapestry})。
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.80]{./images/tapestry.pdf}
+  \end{center}
+  \caption{Tapestry の生成}
+  \label{fig:tapestry}
+\end{figure}
+
+縮小したテクスチャを Tapestry と呼ぶ。 SceneGraph や PolygonPack の時点では
+テクスチャイメージとして Tile Array の先頭アドレスを持っている。CreateSpan の中で
+使用する Span の長さに適した scale を求め、その scale にあった Tapestry を span 生成
+ためのテクスチャとする。
+
+\ref{separate_texture} でも話したとおり、テクスチャを全て SPE 内に送ることはできない。
+Tile 単位で分割し、更にハッシュを用いて SPE 内にキャッシュすることによって無駄な転送
+コストを減少させた。さらに Scale によって 描画に用いる Tapestry を変更することで、
+１テクスチャの Tile の数を減少させることができる。必要 Tile のヒット率が上昇し、結果
+転送コストの削減に繋がる。
+
+この Texture hash の効果を示す。(\tabref{ball_bound})例題として、ball bound を使用した。
+
+\begin{table}[!htb]
+  \begin{center}
+    \caption{キャッシュの効果(ball bound)} \label{tab:ball_bound}
+    \hbox to\hsize{\hfil
+      \begin{tabular}{|c|c|c|c|c|} \hline
+        キャッシュ & FPS & DMA転送待ち時間 & mail待ちの割合 & SPE稼働率\\ \hline
+        なし & 24.6FPS & 5.5\% & 72.4\% & 22.1\% \\ \hline
+        あり & 27.2FPS & 1.8\% & 76.2\% & 22.0\% \\ \hline
+      \end{tabular}\hfil}
+  \end{center}
+\end{table}
+
+
+\subsection{DrawSpanTask} \label{drawspan}
+
+現在、PlayStation 3 の GPU にアクセスする API は公開されていないため、Cerium では 
+Frame Buffer に直接描画する。Frame Buffer のアドレスは mmap() で取得できるため、 Task 
+出力として Frame Buffer を指定するか、Task 内で DMA 転送を行えば描画することができる。
+Mac OSX 上で動かす場合は SDL を用いて描画を行う。
+
+Rendering は DrawSpan という Task で行う。受け取った SpanPack から Span を取り出す。
+Span の端から 1 pixel ずつ見ていき、その pixel の z 座標と Z Buffer を見比べ、描画
+するものと判断されると、対応する RGB 値を書きこむ。
+
+また、DrawSpan は分割された画面領域の一部を担当するので、Span がその領域を
+越えている場合は描画しない。現在、一つの DrawSpan が描画する領域は 256x8 としてい
+る(\figref{drawspan})。
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.80]{./images/drawspan.pdf}
+  \end{center}
+  \caption{DrawSpan の担当領域}
+  \label{fig:drawspan}
+\end{figure}
+
+\subsection{RenderingTask のパイプライン化} \label{drawspan}
+主に 3つの Task から構成されいる RenderingEngine だが、それぞれの Task はバリア同期を行なっている。Cerium においてバリア同期を行う場合に、２つの待ち時間がある。
+\begin{itemize}
+\item SPEが他のSPEの処理完了を待つ時間
+\item バリア同期が完了し、PPE 側で次の Task が作られる時間
+\end{itemize}
+
+この二つの時間の間SPEの処理が止まり、処理性能の低下につながる。この待ち時間を回避するためには、Taskの粒度を下げる、他の SPE の処理完了を待っている SPE に、別の Task を割り当てる、等の方法がある。別の Task を割り当てるには Task の実行をパイプライン化する方法がある。そこで、特に3つの Task の中でも処理の重い DrawSpanTask と、CreatePolygonTask, CreateSpanTask の Task でパイプライン化を行っている。(\figref{rend-dep}) 速度比較の対象として、SuperDnady と呼ばれる、学生実験で制作されたシューティングゲームを用いた。FPSは一秒あたりの RednderingEngine 全体の処理回数(Frame per Scecond)であり、busy ration はSPEの稼働率である。(\tabref{pipeline_superdandy})
+
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.90]{./images/rend-dep.pdf}
+  \end{center}
+  \caption{DrawSpan の担当領域}
+  \label{fig:rend-dep}
+\end{figure}
+
+\begin{table}[!htb]
+  \begin{center}
+    \caption{パイプライン化の効果(ball bound)} \label{tab:pipeline_ballbound}
+    \hbox to\hsize{\hfil
+      \begin{tabular}{|c|c|c|c|c|} \hline
+        PipeLine & FPS & DMA転送待ち時間 & mail待ちの割合 & SPE稼働率\\ \hline
+        なし & 27.2FPS & 1.8\% & 76.2\% & 22.0\% \\ \hline
+        あり & 30.2FPS & 1.8\% & 74.3\% & 23.7\% \\ \hline
+      \end{tabular}\hfil}
+  \end{center}
+\end{table}
+
+パイプライン化した結果（\tabref{pipeline_ballbound}）、SPEの稼働率が向上し、FPSも向上した。
+処理性能を維持するには、SPEはなるべく稼働させ続けなければならない。
+その為には処理をTaskに分割し、並列実行するだけでなく、バリア同期などで、
+SPEの待ち時間が発生することへ対処しないといけない。
+その対処の一つとしてそれにパイプライン化は有効である。