\chapter{並列プログラミング\\フレームワーク Cerium}
Cerium は、当初 Cell 用の Fine-Grain TaskManager として当研究室で開発された。
本章では Cerium の実装について説明する。

\section{Cerium の概要}
Cerium は当初 Cell 用であったが、現在では Linux、 MacOS X上で動作する。
GPGPU の Data Parallel を含めて同じ形式で記述できる。

CeriumはTaskManager、 SceneGraph、Rendering Engine の3つの要素から構成される。
本研究では Cerium の TaskManager を汎用計算フレームワークとして改良を行った。

\section{Cerium TaskManager}
Cerium TaskManager では、処理の単位を Task としてプログラムを記述していく。
関数やサブルーチンを Task として扱い、 Task 間の依存関係を考慮しながら実行される。

ソースコード:\ref{src:createTask}に Host 側で Task を生成する例題を示す。
input data を2つ用意し、 input data の各要素同士を乗算し、
output に格納する multiply という例題である。

\begin{lstlisting}[frame=lrbt,label=src:createTask,caption=Task の生成,numbers=left]
void
multiply_init(TaskManager *manager, float *i_data1, float *i_data2, float *o_data) {
  
    // create task
    HTask* multiply = manager->create_task(MULTIPLY_TASK);
    multiply->set_cpu(spe_cpu);

    // set indata
    multiply->set_inData(0, i_data1, sizeof(float) * length);
    multiply->set_inData(1, i_data2, sizeof(float) * length);

    // set outdata
    multiply->set_outData(0, o_data, sizeof(float) * length);

    // set parameter
    multiply−>set_param(0,(long)length);
    
    // set device
    multiply->set_cpu(SPE_ANY);
    
    // spawn task
    multiply−>spawn();
}
\end{lstlisting}

表:\ref{table:task_create_api}は Task 生成時に用いる API の一覧である。
create された Task は Input Data や 依存関係を設定し、
spawn することで TaskManager に登録される。

\begin{tiny}
  \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 へ値を一つ渡す。ここではlengthを渡している \\
        \hline
        set\_cpu & Task を実行する Device の設定 \\
        \hline
        spawn & 生成した Task を ActiveTaskList に登録する \\
        \hline
      \end{tabular}
      \caption{Task 生成おける API}
      \label{table:task_create_api}
    \end{center}
  \end{table}
\end{tiny}

次に、ソースコード:\ref{src:task} に Device 側で実行される Task (OpenCL、CUDA でいう kernel) の記述を示す。

\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:task_api}は Task 側で使用する API である。
Host 側で設定した Input Data やパラメタを取得することができる。

\begin{tiny}
  \begin{table}[htpb]
    \begin{center}
      \small
      \begin{tabular}[htpb]{c|l}
        \hline
        get\_input & 入力データのアドレスを取得 \\
        \hline
        set\_output & 出力先データのアドレスを取得 \\
        \hline
        set\_param & パラメータを取得 \\
        \hline
      \end{tabular}
      \caption{Task 側で使用する API}
      \label{table:task_api}
    \end{center}
  \end{table}
\end{tiny}

Task を生成する際に設定できる要素は以下の通りとなる。

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

Input/Output Data, Parameter は関数で言うところの引数に相当する。
CpuType は Task が動作する Device を示し、 Dependency は他の Task との依存関係を表す。

\section{Cerium における Task}
図:\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/createTask.pdf}
  \end{center}
  \caption{Task Manager}
  \label{fig:taskmanager}
\end{figure}

\section{Task の Scheduling}
GPU や Cell のような Shared Memory でない環境でのプログラミングを行う場合、
Task の入出力となるデータを転送し、転送が終わってから Task を起動しなければならない。
転送処理がボトルネックとなり、並列度が低下してしまう。
そのため、Cerium はパイプライン実行をサポートしている。

Scheduler に転送された Task はパイプラインで処理される(図:\ref{fig:scheduler})。
Task が全て終了すると Scheduler から TaskManager に mail を通して通知される。
通知に従い依存関係を解決した Task が再び TaskManager から Scheduler に転送される。

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

Cerium の Task は SchedTask と呼ばれるデータ構造で表現されている。
SchedTask は input/output data の length や合計 size を持っており、
これらのパラメタから自分の data が格納されているアドレスを算出し、read/write を実行する。
SchedTask を利用することで容易にパイプラインを構築できる。
Task をパイプライニングにより Scheduling している部分をソースコード:\ref{src:pipeline_multicore}に示す。

\begin{lstlisting}[frame=lrbt,label=src:pipeline_multicore,caption=Task,numbers=left]
void
Scheduler::run(SchedTaskBase* task1)
{
    // Pipeline Stage
    SchedTaskBase* task2 = new SchedNop();
    SchedTaskBase* task3 = new SchedNop();

    // main loop
    do {

        task1->read();
        task2->exec();
        task3->write();

        delete task3;

        task3 = task2;
        task2 = task1;
        task1 = task1->next(this, 0);

    } while (task1);

    delete task3;
    delete task2;
}
\end{lstlisting}

引数として受け取っている task1 は Task のリストである。このリストがなくなるまでパイプライン実行のループを回す。
task1 が read、task2 が exec、task3 が write を担当している。
つまり task3 には read と exec が終わった Task が来るため、write が終わったら delete して良い。
各 Task はそれぞれの処理を行い、task2 は task3 に、task1 は task2 に自分の Task を渡していく。

このメインループを回すことで Cerium の Scheduler はパイプラインによる実行を可能にしている。