\chapter{Cerium} \label{chapter:cerium}

\section{Cell 用の Fine-Grain Task Manager}

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{Task Manager} \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
    add\_inData   & Task への入力データのアドレスを追加 \\ \hline
    add\_outData  & Task からのデータ出力先アドレスを追加 \\ \hline
    add\_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 に沿って Task を実行していき、 Task 毎に実行完了の Mail を送る。
TaskList の Task をすべて実行すると、次の TaskList を要求する Mail を PPE 側に送る。

\section{改良した Task Manager API} \label{sec:taskarray}

以下に新しく追加した API 、仕様の変更があった API を \tabref{new_taskmanager_api} に示す。

\begin{table}[htb]
  \caption{New Task Manager API} \label{tab:new_taskmanager_api}
  \hbox to\hsize{\hfil
  \begin{tabular}{|c|l|} \hline
    create\_task\_array  & Task Array を生成する \\ \hline
    \hline
    set\_inData   & add\_inData から変更 \\ \hline
    set\_outData  & add\_outData から変更 \\ \hline
    set\_param    & add\_param から変更 \\ \hline
    next\_task\_array    & Task Array 内の Task の実行順を設定する\\ \hline
    spawn\_task\_array  & Task Array を実行 Task Queue に登録する \\ \hline
  \end{tabular}\hfil}
\end{table}

以下に Task Array を用いた記述例を示す。このプログラムは Task Array に複数の同一 Task を
登録して、まとめて実行するというプログラムである。各 API の詳細は後述する。

\begin{verbatim}
void
hello_init(TaskManager *manager)
{
    /**
     * Create Task
     *   create_task(Task ID);
     */

    /*うしろ3つ param/inData/outData の数を指定する*/
    HTask *twice_main = manager->create_task_array(Hello,task_num,data_count,
                                                   data_count,data_count);
    Task *t = 0;

    for(int i = 0;i<task_num;i++) {
        t = twice_main->next_task_array(Hello, t);
    }
    twice_main->spawn_task_array(t->next());
    twice_main->set_cpu(SPE_ANY);
    twice_main->spawn();
}

static int
run(SchedTask *s,void *rbuf, void *wbuf)
{
    s->printf("Hello World\n");
    return 0;
}

// 実行結果
% ./hello -task 6
Hello World
Hello World
Hello World
Hello World
Hello World
Hello World

\end{verbatim}

プログラムに用いられてる新しい API について説明する。\\
\begin{description}
\item[create\_task\_array: ] 同一の Task を複数持つことのできる Task Array を生成する。
Task Arrayについては\ref{sec:taskarray}節で詳しく説明する。
\item[next\_task\_array: ] Task Array に Task を実行順序を定める。実行順序は next\_task\_array 
を行った順になる。
\item[spawn\_task\_array: ] Task Array の中のすべての Task が書きこまれたかどうかをチェックする。
\end{description}

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

これまで Task のデータは add\_inData, add\_outData, add\_param された順に read\/write buffer に書きこまれていた。
しかし、これではデータ数が多くなった場合に管理するのが難しくなる恐れが出てきた。例えば、100個のデータをadd\_inData
した場合、特定のデータを取り出す際にそのデータが何番目にadd\_inDataされたのかを知らなければならない。この問題を解決するために、
in\/outのData と param を index を用いて buffer の任意の場所に書き込めるように仕様を変更した。
これは規模の大きな例題を作成するようになって分かった問題の一つである。

\section{新しく追加した Task 「Task Array」}

新しく追加された Task 「 Task Array 」について説明する。
Word Count の場合、対象となるファイルによって大量の Task が生成される。PPE 側で実行される Task もあるなかで、
大量の Task を一つ一つの Task 毎に依存関係を処理していては、SPE からの TaskList 要求への反応が遅れ、 SPE の
待ち時間が生じてしまうと考えられる。この問題を解決するために、我々は Task Array を提案、実装した。 
Task Array は、複数の Task をまとめて扱うことが出来る。Task Array に登録した順番で
依存関係を設定しているので、PPE で解決する Task の数が減り、 SPE からの TaskList 要求に応答しやすくなる。
また、一度に多くの Task を TaskList に登録できるため、 SPE 側からの TaskList 要求の回数が減り、待ち時間が
生じる可能性が減る。さらに Task Array の処理時間が長くなれば、DMA の転送時間を隠すことにも繋がる。Word Count 
と Rendering Engine において、Task Array の効果を検証した\cite{yutaka}。

\subsection{Word Count の Task}

まずは例題の Word Count の Task について説明する。 Word Count の Task は以下の二つである。

\begin{enumerate}
\item WordCountTask
\item PrintTask
\end{enumerate}

WordCountTask は、 input で与えられた data を word count し、 output data に書きだす Task である。PrintTask は
すべての WordCountTask の実行完了を待ち、 output へ書き出された値を集計し出力する Task である。一度に SPE に
送信できるデータ容量は DMA の仕様上 16Kbyte が限界である。また、転送するデータは 16 の倍数 byte である必要がある。

\subsection{WordCountTask の Task Array 化}

Task Array 一つに、64 個 の Task を入れ、 Word Count 対象は 166MB のテキストファイルとした。 Task Array を
適用した場合と、そうでない場合で比較する。 6 個の SPE を使用し、実行にかかった時間を time, SPE 稼働時間における
DMA 転送待ち時間の割合を dma wait, SPE 稼働時間における次の TaskList の mail 待ち時間の割合を mail wait とする。
以下に表で示す( \tabref{wc-taskarray-compare} )。割合に SPE 6 個の平均で示している。この時の Task 数は約 1 万である。

\begin{table}[htb]
  \begin{center}
    \caption{Word Count の Task Array 化による比較}
    \label{tab:wc-taskarray-compare}
    \begin{tabular}{|c|c|c|c|}
      \hline 
      & Task & Task Array & 向上率\\
      \hline
      time & 2.184s & 2.109s & 3.5\% \\
      \hline
      dma wait & 18\% & 12\% & 6\% \\
      \hline
      mail wait & 5\% & 8\% & -3\%\\
      \hline
    \end{tabular}
  \end{center}
\end{table}

表に示した結果より、著しい Task Array の効果は見られなかった。この結果は Word Count においては誤差の範囲内である。
効果が見られなかった原因はおそらく Word Count の場合は PPE 側の Task が無いので、依存関係の処理にほとんど待ち時間が
発生しなかったからだと考えられる。また、Word Count ではファイルをメモリにマッピングするので、ファイルの容量が
大きい場合に大量にメモリを消費してしまう。その結果スワップが起きやすくなり、DMA 転送待ち時間が長くなっている
可能性がある。この解決策として、一度にファイルをすべてマッピングするのではなく、切り分けてマッピングするのが
良い。Word Count が終わった領域に、次の Word Count に必要な領域を入れ替えて使うことでメモリを節約でき、
スワップを減らすことができる。その結果メモリアクセスが高速になり、DMA 転送の待ち時間も削減できる。

\subsection{Rendering Engine の Task}

Rendering Engine は主に CreatePolygon, CreateSpan, DrawSpan という三つの Task から構成されている。
Rendering Engine の詳しい説明は後述する( \ref{sec:cerium_renderingengine} )。

\subsection{Rendering Engine の Task Array 化}

Rendering Engine の中で、最も数が多く生成される DrawSpanTask を Task Array 化した。
地球と月を表示する例題を対象に効果を検証した(\tabref{rendering-taskarray-compare})。 FPS(Frame Per Second) は、一秒間に
表示できる Frame 数のことである。

\begin{table}[htb]
  \begin{center}
    \caption{Rendering Engine の Task Array 化による比較}
    \label{tab:rendering-taskarray-compare}
    \begin{tabular}{|c|c|c|c|}
      \hline 
      & Task & Task Array & 向上率\\
      \hline 
      FPS & 3.94 & 4.32 \% & 9.6\%\\
      \hline
      dma wait & 0.06\% & 0.07\% & 0.01\%\\
      \hline
      mail wait & 55\% & 42\% & -13\% \\
      \hline
    \end{tabular}
  \end{center}
\end{table}

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.8]{./images/universe.pdf}
  \end{center}
  \caption{地球と月を表示する例題}
  \label{fig:universe}
\end{figure}

結果から DrawSpanTask を Task Array 化すると、FPS が上昇し、mail の wait 時間が減ったことが分かる。
Rendering Engine では、 PPE 側でも処理をするべき Task があり、常に PPE が稼動している状態になって
いる。そのため mail を処理する時間が遅れ、SPE のmail 待ちが発生していると考えられる。 Task Array 化
で Task をまとめることで SPE が一つの TaskList で多くの Task を実行できるようになったため、 TaskList 
を要求する回数が減って、待ち時間が発生する回数も減少した。また、それは SPE からの mail の数が減った
ということなので、PPE 側の mail 処理の時間短縮になったと考えられる。

\section{Task Array 化したことによる効果の考察}

Task Array の効果が表れるのは、PPE 側に実行すべき Task があり、PPE が常に稼動している場合ということが
分かった。 Word Count では、PPE 側の Task がなく、mail 待ちがほとんど起きていなかったので Task Array の
効果が無かった。大量のファイルをマッピングし、メモリを多く消費するのでメモリアクセスに時間がかかり、DMA 
転送に待ち時間が発生したと考えられる。それによって、Task Array を用いても DMA 転送時間を覆い隠すことが
できなかった。dma 転送をスケジューリングによってうまく隠す、またはメモリ領域を節約することができれば、
今回の Word Count のような大量のデータを用いる場合の速度向上が期待できる。\\

Task を実行している Scheduler に関する詳しい説明は \ref{sec:scheduler}で行う。

\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 インタプリタがあり、杉山 \cite{chiaki} が独自形式の
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 オブジェクトの生成}

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 を生成することができる。

\subsection{改良後の SceneGraph の操作}

Cerium では、SceneGraph を管理するクラスとして SceneGraphRoot クラスを実装している。
SceneGraphRoot では、ユーザが生成した SceneGraph を持ち、カメラ、ジョイスティック、
光源などの管理を行う。ユーザが SceneGraph のメソッドを扱うためには Viewer クラスを用いる。
Viewer クラスはシステムの API とユーザの API を切り離す目的で作成された。
createFromXMLmemory, getSgid を新しく追加した。

SceneGraphRoot と SceneGraph の API をそれぞれ 
\tabref{cerium_sg_rootapi}、\tabref{cerium_sg_api}に示す。

\begin{table}[htb]
  \begin{center}
    \caption{SceneGraphRoot API} \label{tab:cerium_sg_rootapi}
    \hbox to\hsize{\hfil
      \begin{tabular}{|l|l|} \hline
        createFromXMLfile & xml ファイルから \\
        & Original SceneGraph を生成する \\ \hline
        createFromXMLmemory & メモリ内の xml から \\
        & Original Scenegraph を生成する \\ \hline
        createSceneGraph & ID や 文字列 に対応する SceneGraph を生成する \\
        & 空の SceneGraph を生成することもできる\\ \hline
        setSceneData & セットした SceneGraph を辿って \\
        & Cerium が処理を行う \\ \hline
        getSgid & 文字列に対応する SceneGraph ID 得ることができる \\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}

\begin{table}[htb]
  \begin{center}
    \caption{SceneGraph API} \label{tab:cerium_sg_api}
    \hbox to\hsize{\hfil
      \begin{tabular}{|l|l|} \hline
        addChild(SceneGraph*) & 自身に子を追加する \\ \hline
        addBrother(SceneGraph*) & 自身に兄弟を追加する \\ \hline
        remove(void) & 自身を削除する \\ \hline
        set\_move(move\_func move) & 自身の move を設定する\\ \hline
        set\_collision(coll\_func collision) & 自身の collision を設定する\\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}

これまで、SceneGraph の名前から Copy SceneGraph を生成する際、Original SceneGraph 配列を
上から順に辿って、文字列比較を行っていた。しかしこの方法だと、SceneGraph の数に比例して
コストが増加してしまう。そのため、SceneGraph ID を登録したときに SceneGraph の名前を
key, SceneGraph ID を value として、hash に登録することにより、この問題を解決した。
getSgid は hash にアクセスして SceneGraph ID を取得している。

\subsection{例題}

以下のコードは、地球と月のオブジェクトがそれぞれ回転しながら移動するという 
SceneGraph を記述したものである。

\begin{verbatim}
/*
 * @param sgroot SceneGraphRoot のメソッドを使うための Viewer クラス
 * @param screen_w ゲーム画面の width
 * @param screen_h ゲーム画面の height
 */
universe(Viewer *sgroot, int screen_w, int screen_h)
{
    SceneGraphPtr earth;
    SceneGraphPtr moon;

    // xml ファイルを読み込み、Original SceneGraph を生成
    sgroot->createFromXMLfile( "xml_file/universe.xml");
    sgroot->createFromXMLfile( "xml_file/cube.xml");

    // SceneGraph name から SceneGraph を生成する(Original からのコピー)
    earth = sgroot->createSceneGraph("Earth"); // 地球
    moon = sgroot->createSceneGraph("Moon"); // 月

    // SceneGraph の move と collision を設定                                                    
    earth->set_move_collision(earth_move, earth_collision);
    moon->set_move_collision(moon_move, moon_collision);

    earth->xyz[0] = screen_w / 2; // 初期位置(x)
    earth->xyz[1] = screen_h / 2; // 初期位置(y)
    earth->stack_xyz[0] = 3.0f;
    earth->stack_xyz[1] = 3.0f; 

    // SceneGraph 同士の親子関係を設定 (今回は 親 earth、子 moon)
    earth->addChild(moon);

    // SceneGraphRoot に、使用する SceneGraph を設定する
    // このとき、ユーザーが記述した SceneGraph の root を渡す
    sgroot->setSceneData(earth);
}

/*
 * @param node 自身（この場合は moon）
 */
void
moon_move(SceneGraphPtr node, void *sgroot_, int screen_w, int screen_h)
{
  node->angle[0] += 3.0f; // x 軸方向に回転させる
}

/*
 * @param node 自身（この場合は earth）
 */
void
earth_move(SceneGraphPtr node, void *sgroot_, int screen_w, int screen_h)
{
    node->angle[1] += 1.0f; // y 軸方向に回転させる
    if (node->angle[1] > 360.0f) {
        node->angle[1] = 0.0f;
    }

    node->xyz[0] += node->stack_xyz[0]; // x 軸方向に平行移動させる
    if ((int)node->xyz[0] > screen_w || (int)node->xyz[0] < 0) {
        // 画面外に出そうになったときに方向を変える
        node->stack_xyz[0] = -node->stack_xyz[0];
    }

    node->xyz[1] += node->stack_xyz[1]; // y 軸方向に平行移動させる
    if ((int)node->xyz[1] > screen_h || (int)node->xyz[1] < 0) {
        // 画面外に出そうになったときに方向を変える
        node->stack_xyz[1] = -node->stack_xyz[1];
    }
}

\end{verbatim}

実行結果を \figref{example_universe} に示す。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.40]{./images/universe3.pdf}
  \end{center}
  \caption{SceneGraph の例題}
  \label{fig:example_universe}
\end{figure}

\section{Rendering Engine} \label{sec:cerium_renderingengine}

Rendering Engine は SceneGraph の処理の他に CreatePolygonFromSceneGraph
(\ref{createpolygonfromscenegraph}), CreateSpan(\ref{createspan}), 
DrawSpan(\ref{drawspan}) という 3 つの Task から構成されている。
Span とは、ポリゴンに対するある特定の Y 座標に関するデータを
抜き出したものである \\ ( \figref{inst_span} )。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.60]{./images/inst-span.pdf}
  \end{center}
  \caption{Span}
  \label{fig:inst_span}
\end{figure}


\subsection{Rendering で用いる新しいデータ構造}

Rendering 処理は SPE で行うことを前提とし、それに合わせたデータ構造を
採用している。光源処理を追加したことにより、法線ベクトルの情報をデータ構造内
に追加している。

\subsubsection{PolygonPack}

PolygonPack は、SceneGraph から抽出されたポリゴンの集合である。
以下に構造を示す。

\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 の集合である。以下に構造を示す。

\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 までの流れを説明する。

\subsection{SceneGraph から PolygonPack を生成する新しい Task} \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{CreateSpan} \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 のヒット率が上昇し、結果
転送コストの削減に繋がる。

\subsection{DrawSpan} \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}