\chapter{Cerium}
Cerium は、Cell 向けに開発された並列プログラミングフレームワークである。
Cell は Sony Computer Entertainment 社が販売した PlayStation3 に搭載されているヘテロジニアスマルチコア・プロセッサである。
本章では Cerium の実装について説明する。

\section{Cerium の概要}
Cerium は当初 Cell 向けに開発され、C/C++ で実装されている。
現在では Linux、 MacOS X 上で動作する並列プログラミングフレームワークである。

Cerium は TaskManager、SceneGraph、Rendering Engine の3要素から構成されている。
本研究では汎用計算フレームワークである TaskManager を利用して文字列の並列計算を行なった。

図\ref{fig:TaskManager}は Cerium が Task の生成/実行する場合のクラス構成図である。
TaskManager で依存関係が解消され、実行可能になった Task は ActiveTaskList に格納される。
ActiveTaskList に格納された Task は、依存関係が解消されているのでどのような順番で実行されても問題はない。
Task は転送を行いやすい TaskList に変換され、CpuType に対応した Scheduler に転送される。
なお、転送はSynchronozed Queue である mail を通して行われる。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{images/cerium/createTask.pdf}
  \end{center}
  \caption{Task Manager}
  \label{fig:TaskManager}
\end{figure}

\newpage

\section{Cerium TaskManager}
Cerium TaskManager では、処理の単位を Task として記述していく。
関数やサブルーチンを Task として取り扱い、その Task にて Input Data/Output Data 及び Task の依存関係を設定する。
そして Task は設定された依存関係を考慮しながら実行される。

Input Data で格納した 2 つの数を乗算し、Output Data に演算結果を格納する multiply という例題のソースコード\ref{src:createTask}を以下に示す。

また、Task の生成時に用いる API 一覧を表\ref{table:TaskCreateAPI}に示す。
\begin{lstlisting}[frame=lrbt,label=src:createTask,caption=Task の生成,numbers=left]
multi_init(TaskManager *manager)
{
    float *A, *B, *C;

    // create Task
    HTaskPtr multiply = manager->create_task(MULTIPLY_TASK);

    // set device
    multiply->set_cpu(SPE_ANY);

    // set inData
    multiply->set_inData(0, (memaddr)A, sizeof(float)*length);
    multiply->set_inData(1, (memaddr)B, sizeof(float)*length);

    // set outData
    multiply->set_outData(0, (memaddr)C, sizeof(float)*length);

    // set parameter
    multiply->set_param(0,(long)length);

    // spawn task
    multiply->spawn();
}
\end{lstlisting}

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \label{table:TaskCreateAPI}
      \small
      \begin{tabular}[t]{c|l}
        \hline
        create\_task& Task を生成する \\
        \hline
        set\_inData & Task への入力データのアドレスを追加 \\
        \hline
        set\_outData & Task への出力データのアドレスを追加 \\
        \hline
        set\_param & Task へ値を一つ渡す。ここでは length \\
        \hline
        set\_cpu & Task を実行するデバイスの設定  \\
        \hline
        spawn & 生成した Task を TaskList に set \\
        \hline
      \end{tabular}
      \caption{Task 生成における API}
    \end{center}
  \end{table}
\end{tiny}

次に、デバイス側で実行される Task のソースコードを\ref{src:task}に示す。
\begin{lstlisting}[frame=lrbt,label=src:task,caption=Task,numbers=left]
static int
run(SchedTask *s) {
    // get input
    float *i_data1 = (float*)s->get_input(0);
    float *i_data2 = (float*)s->get_input(1);

    // get output
    float *o_data  = (float*)s->get_output(0);

    // get parameter
    long length = (long)s->get_param(0);

    // calculate
    for (int i=0; i<length; i++) {
        o_data[i] = i_data1[i] * i_data2[i];
    }
    return 0;
}
\end{lstlisting}
また表\ref{table:taskAPI}は Task 側で利用する API である。
Task 生成時に設定した Input Data や parameter を取得することができる。

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \caption{Task 側で使用する API}
      \label{table:taskAPI}
      \small
      \begin{tabular}[t]{c|l}
        \hline
        get\_input & Scheduler から input data を取得 \\
        \hline
        get\_output & Scheduler から output data を取得 \\
        \hline
        get\_param & set\_param した値を取得 \\
        \hline
      \end{tabular}
    \end{center}
  \end{table}
\end{tiny}

\newpage

Task 生成時に設定できる要素を以下に列挙する。

\begin{itemize}
\item Input Data
\item Output Data
\item Parameter
\item CpuType
\item Dependency
\end{itemize}

Input/Output Data、Parameter は関数の引数に相当する。
Cpu Type は Task を動作させるデバイスを設定することができ、Dependency は他の Task との依存関係を設定することができる。
\newpage
\section{並列処理向け I/O}
ファイル読み込みなどの I/O を含むプログラムは、読み込み時間が Task の処理時間と比較してオーバーヘッドになることが多い。
計算処理の並列化を図ったとしても I/O がボトルネックになってしまい処理全体が高速にならない。
本項では Cerium に実装した並列処理用 I/O を行ない、I/O 部分の高速化を図った。

Cerium の例題ではファイル読み込みを mmap にて実装していた。
しかし、mmap だとファイルを読み込んでから Task を実行するので、読み込んでいる間は他の CPU が動作せず並列度が落ちる。

mmap は function call 後にすぐにファイルを読みに行くのではなく、仮想メモリ領域にファイルの中身を対応させる。
その後メモリ空間にアクセスされたときに、OS が対応したファイルを読み込む。
また、読み込む方法が OS 依存となってしまうため環境に左右されやすく、プログラムの書き手が読み込みの制御をすることが難しい。

図\ref{fig:mmap}は mmap で読み込んだファイルに対して Task1 、 Task2 がアクセスしてそれぞれの処理を行うときのモデルである。

Task1 が実行されると仮想メモリ上に対応したファイルが読み込まれ、読み込み後 Task1 の処理が行われる。
その後 Task2 も Task1 と同様の処理が行われるが、これら 2 つの Task の間に待ちが入る。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{images/cerium/mmap.pdf}
  \end{center}
  \caption{mmap Model}
  \label{fig:mmap}
\end{figure}

mmap を使わず、読み込みを独立した Thread で行ない、ファイルを一度に全て読み込むのではなくある程度の大きさ(Block)分読み込み、読み込まれた部分に対して並列に Task を起動する。
これを Blocked Read と呼び、高速化を図った。

Blocked Read を実装するにあたり、WordCount を例題に挙げる。
ファイルを読み込む Task (以下、ReadTask) と、読み込んだファイルに対して計算を行う Task (以下、WordCount) を別々に生成する。ReadTask は一度にファイル全体を読み込むのではなく、ある程度の大きさで分割してから読み込みを行う。分割して読み込んだ範囲に対して WordCount を行う。

WordCount を Blocked Read で読み込み処理をしたとき以下の図\ref{fig:BlockedRead}の様になる。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.5]{./images/cerium/blockedread.pdf}
  \end{center}
  \caption{BlockedRead による WordCount}
  \label{fig:BlockedRead}
\end{figure}

Task を一定の単位でまとめた Task Block ごとに生成して WordCount を行なっている。
Task Block で計算される領域が Blocked Read で読み込む領域を追い越して実行してしまうと、まだ読み込まれていない領域に対して計算されてしまう。
その問題を解決するために依存関係を適切に設定する必要がある。
Blocked Read による読み込みが終わってから TaskBlock が起動されるようにするため、Cerium の API である wait\_for にて依存関係を設定する。

また、ReadTask は連続で処理される必要がある。
なぜならば、ReadTask でファイルを読み込む前提で WordCount がその領域に対して計算を行うので、ReadTask の処理が遅くなってしまうだけでオーバーヘッドとなってしまう。\ref{fig:BlockedReadModel}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.5]{./images/cerium/blockedreadimage.pdf}
  \end{center}
  \caption{BlockedRead Model}
  \label{fig:BlockedReadModel}
\end{figure}

\newpage
Blocked Read を実装することにより、読み込み部分と処理部分の並列化を行なった。Blocked Read は連続で読み込まれる必要があるため、さらに I/O 専用 thread を実装した。

Cerium Task Manager では、それぞれの Task に対してデバイスを設定することができる。
SPE\_ANY 設定をすると、Task Manager が CPU の割り振りを自動的に行う。
Blocked Read は連続で読み込まれなければならないが、SPE\_ANY で設定すると Blocked Read 間に別の Task が割り込まれる恐れがある。(図\ref{fig:spe_any_blockedread})

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/cerium/speblockedread.pdf}
  \end{center}
  \caption{BlockedRead と Task を同じ thread で動かした場合}
  \label{fig:spe_any_blockedread}
\end{figure}

Task が Blocked Read 間に割り込まれないようにするため、I/O 専用 thread である iO\_0 の設定を追加した。

IO\_0 は SPE\_ANY とは別 thread の scheduler で動作するので、SPE\_ANY で動作している Task に割り込むことはない。
しかし、読み込みの終了を通知し、次の read を行う時に他の Task がスレッドレベルで割り込んでしまう事がある。
pthread\_getschedparam() で IO\_0 の priority の設定を行う必要がある(図:\ref{fig:iothread_blockedread})。
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/cerium/iothread.pdf}
  \end{center}
  \caption{IO Thread による BlockedRead}
  \label{fig:iothread_blockedread}
\end{figure}

IO\_0 で実行される Task は Blocked Read のみで、さらに IO\_0 の priority を高く設定することにより Blocked Read が他の Task に割り込まれることなく連続に実行される。