\section{Cerium TaskManager}\label{section:cerium}

Cerium Task Manager は並列プログラミングフレームワークであり、内部では C や C++ で実装されている。
Cerium Task Manager は、User が並列処理を Task 単位で記述し、関数やサブルーチンを Task として扱い、その Task に対して Input Data、Output Data を設定する。
Input Data、Output Data とは関数でいう引数に相当する。そして Task が複数存在する場合、それらに依存関係を設定することができる。
そして、それに基づいた設定の元で Task Manager にて管理し実行される。
Cerium Task Manager は PlayStation 3/Cell、Mac OS X 及び Linux 上で利用することが可能である。

図\ref{fig:cerium} は Cerium が Task を作成・実行する場合のクラスの構成となる。User が createtask を行い、input data や Task の依存関係の設定を行うと、TaskManager で Task が生成される。
Task 毎に依存関係を表す wait\_i と wait\_me というリストがあり、依存関係が解消されて実行可能になった Task は ActiveTaskList に移される。さらに、Scheduler に転送する際には TaskList に変換を行ってから各 Scheduler に転送される。

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.3]{images/ceriumtaskmanager.pdf}
\end{center}
\caption{Cerium Task Manager}
\label{fig:cerium}
\end{figure}

\newpage

\subsection{Cerium Task Manager を使った例題}
今回計測に使用した例題 WordCount を例にとり、以下に Task の生成部分を以下に示す。
このプログラムは、WordCount Task と Print Task の2種類の Task から構成される。

input data とは、mmap や read で読み込んだファイルであり、このファイルを $ n $ KByte の大きさに分割して、WordCount Task にそれぞれ割り当てる。

%WordCount Task の input data には読み込んだファイル、 output data には単語数と行数をカウントしたデータを書きこむ。

WordCount Task の input data には、WordCount Task が担当するテキストの範囲を設定し、output data には単語数や行数、そしてその範囲の先頭と末尾の状態を表すフラグを配列として格納する。
% WordCount Task の set\_inData には、WordCount Task が担当するテキストの範囲を設定し、set\_outData には単語数や行数、そしてその範囲の先頭と末尾の状態を表すフラグを配列として格納する。

以下に WordCount Task の生成部分を示す。

\begin{verbatim}
wc = manager->create_task(WORD_COUNT);
wc->set_inData(0,
                file_mmap + i*division_size,
                size);
wc->set_outData(0,o_data + i*out_size,
                division_out_size);

wc->set_cpu(spe_cpu);
wc->spawn();
i++;
\end{verbatim}

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \label{table:create_taskAPI}
      \small
      \begin{tabular}[t]{c|l}
        \hline
        create\_task& Task を生成する \\
        \hline
        set\_inData & Task に入力データのアドレスを追加 \\
        \hline
        set\_outData & Task に出力データのアドレスを追加 \\
        \hline
        set\_cpu & Task を実行するデバイスの設定  \\
        \hline
        spawn & 生成した Task を TaskList に set する\\
        \hline
      \end{tabular}
      \caption{Task 生成における API}
    \end{center}
  \end{table}
\end{tiny}
状態を表すフラグを格納している理由は、
input data は分割されたデータが送られてくるため、分割された前後のテキストがどうなっているかはわからない。
空白か改行が読み込まれたときに単語として認識するので、単語の終わりで分割されたときにその単語がカウントされない。

単語数 3 の例文「I'm so happy.」の o 直後に分割される場合を図\ref{fig:dividepoint}に示す。

wc Task 1 は "I'm" "so" の 単語に見えるが、"so" は単語の途中で分割された可能性がある。1 つの単語かどうかわからないので、wc Task 1 の単語数は 1 となる。

wc Task 2 は "happy." だけなので、単語数は 1 となり、 合計単語数が 2 となってしまう。

wc Task 1 の "so" を単語として認識させるには、wc Task 2 の先頭が空白か改行である必要がある。
しかし、wc Task 内では隣接した Task の情報がわからないので、各 Task の先頭と末尾の状態を持たせて、最後の集計のときに整合させる必要がある。

このように単語の終わりでファイル分割されたとき、その分割ファイルの末尾が空白か改行以外の文字列であり、そして、隣接した分割ファイルの先頭が空白か改行であれば、単語として認識される。

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.4]{images/dividepoint.pdf}
\end{center}
\caption{単語の終わりで分割されたテキスト}
\label{fig:dividepoint}
\end{figure}

そのため、出力結果に分割ファイルの先頭と末尾の状態のフラグを \verb+head_tail_flag+として単語数と行数に付け加える。後にそのデータを他の WordCount の結果と照らし合わせ、分割されたテキストを正しく整合する。

WordCount Task の記述は以下のようになる。
\\

\begin{verbatim}
wordcount(SchedTask *s, void *rbuf, void *wbuf)
{
    char *i_data = (char *)s->get_input(0);
    unsigned long long *o_data =
        (unsigned long long *)s->get_output(0);
    unsigned long long *head_tail_flag =
                                o_data + 2;
    int length = (int)s->get_inputSize(0);
    int word_flag = 0;
    int word_num = 0;
    int line_num = 0;
    int i = 0;

    head_tail_flag[0] =
        (i_data[0] != 0x20) &&
        (i_data[0] != 0x0A);

    word_num -= 1-head_tail_flag[0];

    for (; i < length; i++) {
        if (i_data[i] == 0x20) {
            word_flag = 1;
        } else if (i_data[i] == 0x0A) {
            line_num += 1;
            word_flag = 1;
        } else {
            word_num += word_flag;
            word_flag = 0;
        }
    }

    word_num += word_flag;
    head_tail_flag[1] =
        (i_data[i-1] != 0x20) &&
        (i_data[i-1] != 0x0A);

    o_data[0] = (unsigned long long)word_num;
    o_data[1] = (unsigned long long)line_num;

    return 0;
}
\end{verbatim}

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

Print Task は WordCount Task によって書き出された単語数、行数、\verb+head_tail_flag+ を集計し、結果を出力する Task である。
WordCount Task が全て走り終わったあとに、Print Task が走るように依存関係を設定している。(図\ref{fig:wordcount})

\begin{figure}[htbp] \begin{center}
\includegraphics[scale=0.4]{images/wordcount.pdf}
\end{center}
\caption{WordCount Model}
\label{fig:wordcount}
\end{figure}

\newpage
WordCount Task と Print Task の生成と依存関係の設定を以下に示す。

\begin{verbatim}
static void
run_start(TaskManager *m, char *filename)
{
    HTaskPtr print;
    WordCountPtr w;

    print = m->create_task(TASK_PRINT,
        (memaddr)&w->self,sizeof(memaddr),0,0);

    w->t_print = print;
    exec_num = 4;

    for(int i=0;i<exec_num;i++) {
        wcb = m->create_task(RUN_WORDCOUNT_BLOCKS,
        (memaddr)&w->self,sizeof(memaddr),0,0);

        print->wait_for(wcb);
        wcb->spawn();
    }
    print->spawn();
}
\end{verbatim}

\verb+WordCountPtr w+ は、ファイルサイズや読み込んだファイルの先頭アドレスなど、Task 間で共有する情報をまとめた構造体である。
WordCount を ブロック単位でここでは生成しているが、\ref{cap:block} Blocked Read の設計と実装にて後述する。

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \label{table:taskAPI}
      \small
      \begin{tabular}[t]{c|l}
        \hline
        \verb+create_task+ & Task を生成する。\verb+w->self+ は input data、\\
         & \verb+sizeof(memaddr)+ は input data のサイズ\\
        \hline
        \verb+wait_for+ & Task の依存関係を設定する。\\
         & ここでは、\verb+print+が \verb+wcb+ を待つように設定\\
        \hline
      \end{tabular}
      \caption{run\_start で使用したAPI}
    \end{center}
  \end{table}
\end{tiny}

WordCount Task がデータを集計し終わったあとに、 Print Task にて最終集計を行う。

Print Task の記述を以下に示す。

\begin{verbatim}
static int
run_print(SchedTask *s, void *rbuf, void *wbuf)
{
    WordCount *w = (WordCount*)s->get_input(0);
    unsigned long long *idata = w->o_data;
    long status_num = w->status_num;
    int out_task_num = w->out_task_num;

    unsigned long long word_data[2];

    int flag_cal_sum = 0;

    for (int i = 0; i < out_task_num ; i++) {
        word_data[0] += idata[i*w->out_size+0];
        word_data[1] += idata[i*w->out_size+1];
        unsigned long long *head_tail_flag = 
            &idata[i*w->out_size+2];
        if((i!=out_task_num-1)&&
           (head_tail_flag[1] == 1) &&
           (head_tail_flag[4] == 0)) {
            flag_cal_sum++;
        }
    }

    word_data[0] += flag_cal_sum;

    for (int i = status_num-1; i >=0; i--) {
        s->printf("%llu ",word_data[i]);
    }
    return 0;
}
\end{verbatim}

\verb+word_count[0]+ にそれぞれの単語数の合計を格納して、\verb+word_count[1]+ にそれぞれの行数の合計を格納する。
WordCount Task で集計したデータは配列として保存され、それらの配列を 1 つの大きな配列 \verb+w->o_data+ として Print Task に渡している。

また、\verb+o_data[2]+ を \verb+head_tail_flag[0]+ に置換して、末尾と先頭の処理を行う。(図\ref{fig:array})
末尾に文字列があり、先頭が空白か改行の場合は単語がカウントされないので、この状態を見て単語数を整合させる。

\begin{figure}[htbp] \begin{center}
\includegraphics[scale=0.6]{images/print.pdf}
\end{center}
\caption{集計したデータの配列図}
\label{fig:array}
\end{figure}