--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/cerium.tex	Tue May 05 15:36:41 2015 +0900
@@ -0,0 +1,116 @@
+\section{Cerium}
+Cerium は、当初 Cell 用の Fine-Grain Task Manager\cite{gongo:2008a} として当研究室で開発された。
+TaskManager, SceneGraph, Rendering Engine の3つの要素から構成されており、今では、PS3 および Linux, MacOS X 上で動作する。
+GPGPU の Data Parallel を含めて、同じ形式で並列プログラムを記述することができる。
+
+\subsection{Cerium TaskManager}
+TaskManager は、Task と呼ばれる分割されたプログラムを管理する。
+関数やサブルーチンを Task として扱い、Task 同士の依存関係を考慮しながら実行される。
+Task は TaskManager を使って生成する。
+Task を生成する際に、以下のような要素を設定することができる。
+
+\begin{itemize}
+  \item input data
+  \item output data
+  \item parameter
+  \item cpu type
+  \item dependency
+\end{itemize}
+
+input, output, parameter は関数でいうところの引数に相当する。
+cpy type は Task がどのようなの Device の組み合わせで実行されるかを示す。
+dependency は他の Task との依存関係を示している。
+
+\begin{figure}[!h]
+  \begin{center}
+    \includegraphics[scale=0.4]{./images/createTask.pdf}
+  \end{center}
+  \caption{Task Manager}
+  \label{fig:createTask}
+\end{figure}
+
+図:\ref{fig:createTask}は Cerium が Task を生成/実行する場合のクラスの構成である。
+TaskManager で依存関係が解消され、実行可能になった Task は ActiveTaskList に移される。
+ActiveTaskList に移された Task は依存関係が存在しないのでどのような順序で実行されても問題ない。
+Task は Scheduler に転送しやすい TaskList に変換してから cpy type に対応する Scheduler に Synchronized Queue である mail を通して転送される。
+Scheduler ではパイプラインで task が処理される(図:\ref{fig:task_scheduler})。
+Task が終了すると Scheduler から TaskManager に mail を通して通知される。
+その通知に従って依存関係が処理され、再び TaskManager から Scheduler に Task が転送される。
+
+\begin{figure}[!h]
+  \begin{center}
+    \includegraphics[scale=0.4]{./images/scheduler.pdf}
+  \end{center}
+  \caption{Task Scheduler}
+  \label{fig:task_scheduler}
+\end{figure}
+
+以下に Task を生成する例題を示す。
+表:\ref{table:TaskManager_api}は Task を生成に用いる API を示している。
+input データを2つ用意し、input データの各要素同士を乗算し、output に格納する multiply という例題である。
+
+\lstinputlisting[caption=multiply,label=test]{./source/multiply.cc}
+
+\begin{table}[htpb]
+  \begin{center}
+    \small
+    \begin{tabular}[htpb]{|c|l|} \hline
+      create\_task & Task を生成する \\ \hline
+      set\_inData  & Task への入力データのアドレスを追加 \\ \hline
+      set\_outData & Task からのデータ出力先アドレスを追加 \\ \hline
+      set\_param   & Task のパラメータ \\ \hline
+      wait\_for    & Task の依存関係 \\ \hline
+      set\_cpu     & Task を実行する Device の設定 \\ \hline
+      spawn        & Task を登録する \\ \hline
+      iterate      & データ並列で実行する Task として登録する \\ \hline
+    \end{tabular}
+    \caption{Task 生成に用いる API}
+    \label{table:TaskManager_api}
+  \end{center}
+\end{table}
+
+CPU で実行される Task(OpenCL, CUDA でいう kernel) の記述は以下のようになる。
+表:\ref{table:taskAPI}は Task 側で使用する API である。
+
+\lstinputlisting[caption=task,label=test]{./source/multiply_task.cc}
+
+\begin{table}[ht]
+  \begin{center}
+    \small
+    \begin{tabular}[t]{|c|l|} \hline
+      get\_input  & 入力データのアドレスを取得 \\ \hline
+      get\_output & データ出力先のアドレスを取得 \\ \hline
+      get\_param  & パラメータを取得 \\ \hline
+    \end{tabular}
+    \caption{ Task 側で使用する API }
+    \label{table:taskAPI}
+  \end{center}
+\end{table}
+
+\subsection{Cerium におけるデータ並列}
+Cerium でデータ並列による実行をサポートするために、OpenCL の API に合わせた iterate という API を用意した。
+iterate は length を引数として受け取り、Scheduler で length の値と受け取った引数の個数を次元数として Task 数を計算し、データ並列で実行する Task として生成する。
+
+例として、CPU 数4、一次元で10個のデータに対してデータ並列実行を行なった場合、各 CPU が担当する index は表:\ref{table:dpi}のようになる。
+
+\begin{table}[h]
+  \begin{center}
+    \small
+    \begin{tabular}[t]{c||c|c|c|c} \hline
+      &CPU0& CPU1&CPU2&CPU3 \\ \hline
+      1&0&1&2&3 \\ \hline
+      2&4&5&6&7 \\ \hline
+      3&8&9& & \\ \hline
+    \end{tabular}
+    \caption{Data 並列実行時の index の割り当て}
+    \label{table:dpi}
+  \end{center}
+\end{table}
+
+各 CPU が担当する index は SchedTask に格納してある。
+データ並列で実行する Task の記述は以下のようになる。
+
+\lstinputlisting[caption=example,label=test]{./source/multiply_task_dp.cc}
+
+並列プログラムでは、並列化する Task が全部同一であるということは少なくない。
+iterate を実装したことで、Task を生成する部分をループで回す必要はなくなり、OpenCL と同様に1つの記述で異なる index を持つ Task を Multi Core CPU 上で実行することが可能になった。