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

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

Cerium \cite{gongo} は Cell 用の Fine-Gerain 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 を有している。

\subsection{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 \hline
    create\_task  & Task を生成する \\ \hline
    run           & 実行 Task Queue の実行 \\ \hline
    allocate      & 環境のアライメントを考慮した allocator \\ \hline
    \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}

\subsection{Cerium における Task}

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.68]{./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


\subsection{Task のスケジューリング}

SPE は、Task を一つずつ受け取るのではなく、ある程度まとめて受け取る。それを TaskList 
と呼んでいる。 TaskList に沿って Task を実行していき、 Task 毎に実行完了の Mail を送る。
TaskList の Task をすべて実行すると、次の TaskList を要求する Mail を PPE 側に送る。

\subsection{新しい API} \label{sec:taskarray}

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

\begin{table}[htb]
  \caption{Task Manager API} \label{tab:new_taskmanager_api}
  \hbox to\hsize{\hfil
  \begin{tabular}{c|l} \hline \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[spwan\_task\_array: ] Task Array の中のすべての Task が書きこまれたかどうかをチェックする。
\end{description}

また、仕様変更になった Task に引き渡すデータを管理する API (set\_inData, set\_outData, set\_param) について
説明する。\\

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

\subsection{Task Array}

新しく追加された Task 「 Task Array 」について説明する。
WordCount の場合、対象となるファイルによって大量の 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{jssst-yutaka}。

\subsection{Task Array 化による検証}

\subsubsection{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 である必要がある。

\subsubsection{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 \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 転送の待ち時間も削減できる。

\subsubsection{Rendering Engine の Task}

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

\subsubsection{Rndering Engine の Task Array 化}

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

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

\begin{table}[htb]
  \begin{center}
    \caption{Word Count の Task Array 化による比較}
    \label{tab:rendering-taskarray-compare}
    \begin{tabular}{|c|c|c|c|}
      \hline 
      & Task & Task Array & 向上率\\
      \hline \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}

結果から 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 処理の時間短縮になったと考えられる。

\subsection{Task Array 化による検証の結果}

Task Array の効果が表れるのは、PPE 側に実行すべき Task があり、PPE が常に稼動している場合ということが
分かった。 Word Count では、PPE 側の Task がなく、mail 待ちがほとんど起きていなかったので Task Array の
効果が無かった。大量のファイルをマッピングし、メモリを多く消費するのでメモリアクセスに時間がかかり、DMA 
転送に待ち時間が発生したと考えられる。それによって、Task Array を用いても DMA 転送時間を覆い隠すことが
できなかった。また、複数の SPE が同時にメインメモリにアクセスする際に、それぞれ離れた

\begin{comment}
\\ ###########################途中############################\\
\end{comment}


・Task を1種類に戻したい

・spu側からmailを送ったときにキューに溜まるようにした

・getsegmentを入れた理由

・bussy rate

・queue info

・tasklistのdependencyが変わってる

・waitlistが残ってるのはdead lock deteption


\subsection{SceneGraph} \label{sec:scenegraph}
 
・sgidの追加

\subsection{Rendering Engine} \label{sec:renderingengine}

・DrawSpan は常に動いているようにしたいー＞pipelineの見直しが絶対に必要

・pipelineに関連して double buffering の見直しも。

・CreatePolygonFromSceneGraph

・検証よりもpipelineでちゃんと動くところを見せたほうがいい