\chapter{Cerium を用いた例題}
Cerium は様々な例題を含んでいる。本論文では Bitonic Sort、 Word Count、 FFT の3つの例題を扱う。

Bitonic Sort は、ベンチマークをとる際の一般的な例題として選択した。

Word Count は、計算自体は条件に合う word をカウントアップしていくシンプルな内容である。
シンプルな計算でも並列化する事で大きな性能向上を狙える事を示す。

FFT:Fast Fourier Transform(高速フーリエ変換) は、
信号処理や画像処理から大規模シミュレーションに至るまで幅広い分野で活用されている計算である。
バタフライ演算などの計算の性質上、データ並列と相性がよく、 GPGPU で高い並列度を維持できる事が知られている\cite{fft}。

以上3つの例題を用いてベンチマークを行っていく。本論文で使用する各種例題について紹介する。

\section{Bitonic Sort}
\label{sec:about_sort}
Cerium Task Manager を使った Sort である。
Bitonic Sort は配列の分割を行い、分割した部分に対して sort を行う。
分割後の Sort には QuickSort を使用している。Task の構成は以下のようになる。

\begin{itemize}
\item SortSimpleTask
\item QuickSortTask
\end{itemize}
指定された数の乱数を生成し、sort する例題である。
SortSimpleTask は Task の割り当てを行う Task である。
QuickSortTask は割り当てられた範囲を QuickSort により Sort する Task である。
図:\ref{fig:sort_example}に Bitonic Sort の例を示す。
SimpleSortTask は乱数列を分割し、 QuickSortTask に割り当てる。QuickSortTask は割り当てられた部分を Sortする。
分割した部分をQuickSortTaskに割り当て、繰り返し起動していく事でSort を行う。

\begin{enumerate}
  \item SimpleSortTask が乱数列を分割し、 QuickSortTask に割り当てる
  \item QuickSortTask が割り当てられた部分を Sort する
  \item SimpleSortTask が最初に割り当てた範囲の中間から次の範囲の中間までを QuickSortTask に割り当てる
  \item QuickSortTask が割り当てられた部分を Sort する
\end{enumerate}
このようなTaskの分割 →Sort を分割数分繰り返し実行することで全体をSortする。

本論文では Bitonic Sort による測定を行う場合、10万入力を Input とするベンチマークを行う。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/sort_benchmark.pdf}
  \end{center}
  \caption{Bitonic Sort の例}
  \label{fig:sort_example}
\end{figure}
\newpage

\section{Word Count}
WordCount は Input としてファイルを受け取り、ファイルの単語数と行数を集計し、表示する。
空白で区切られたものを単語として扱う。

Word Count の Task の構成は以下の通りである。

\begin{itemize}
\item WordCountTask
\item PrintTask
\end{itemize}

WordCountTask は Input された data を Word Count し、
単語数と行数を Output として指定された Data 領域に書き込む Task である。

Task には分割されたテキストが送られてくるため、送られてきたテキストの前後の状態によっては振る舞いを変える必要がある。
分割により Word の途中で切れてしまう場合があり、その場合だとword数-1する処理が必要になる。
そのため、 WordCountTask は自分が割り当てられた範囲である data の先頭と末尾のパラメータを返す。

PrintTask は WordCountTask によって書き出された単語数と行数を集計し、出力する Task である。
集計時は全 WordCount の結果を照らし合わせ、分割されたテキストを正しく整合する。
PrintTask は WordCountTask を wait する設定で、全ての WordCountTask が終了したあとに動作する。

WordCount の対象として入力されたファイルは、 mmap を用いてメモリに展開する。
その後データを 16KByte の大きさに分割しながら WordCountTask に割り当てていく。

各 Task 間の data の流れを図:\ref{fig:wordcount}に示す。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/wordcount.pdf}
  \end{center}
  \caption{WordCountのフロー}
  \label{fig:wordcount}
\end{figure}

\clearpage

\section{FFT}
FFT:Fast Fourier Transform(高速フーリエ変換) は、フーリエ変換と周波数フィルタによる画像処理を行う例題である。
今回は入力として受け取った画像に対してハイパスフィルターを行う例題である。

FFT の Task の構成は以下のとおりである。

\begin{itemize}
\item BitReverse
\item Butteerfly
\item HighPassFilter
\item SpinFact
\item Transpose
\end{itemize}

FFT は画像 Data に対して様々な Task を割り当てる。
入力は比較的大きなサイズを想定している。
Input と Output を繰り返し行うと、特に GPU だとボトルネックになってしまう。
このベンチマークで並列度を維持するにはデータ並列実行に対応し、データ依存で並列化を可能にする必要がある。

\section{Task の生成}
Cerium において並列処理を行う場合、 Task を大量に生成する場合がある。
WordCount や BitonicSort がそれにあたり、データの分割数分 Task の生成を行う必要がある。
しかし、そういった場合において一気に Task を生成して実行を行うと著しく性能が低下する。
起動していなくても Task そのものがメモリを圧迫してしまい、処理速度が低下する。
Task の生成と実行を並行して行う必要があり、Task は徐々に一定数ごとに生成されるべきである。

Sort の例題を元に Task の生成について考える。
Sort の手順は\ref{sec:about_sort}節でも述べたが、
「乱数列を分割して Sort 」と
「割り当てた範囲の中間から次の範囲の中間までを Sort 」、以上の2つの Sort により構成される。
「乱数列を分割して Sort」を fsort 、
「割り当てた範囲の中間から次の範囲の中間までを Sort 」を bsort とする。
2つの Sort の構成を図:\ref{fig:fsort_bsort}に示す。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/fsort_bsort.pdf}
  \end{center}
  \caption{fsort と bsort}
  \label{fig:fsort_bsort}
\end{figure}

bsort は fsort の結果に対して Sort を行う。つまりこの2つの Sort 間には依存関係が存在する。
更にステージが次へ進むと fsort は前のステージの bsort の結果に対して Sort を行うため、
更に依存関係が存在する。
例題に関する依存関係を記述しながら、Task を徐々に生成する依存関係も記述するため、
Task 生成部分は複雑になるという問題がある。
Sort の例題における依存関係の記述を行う Task を SortSimple とし、ソースコード:\ref{src:sort_dependency}に示す。

\begin{lstlisting}[frame=lrbt,label=src:sort_dependency,caption=Sort の例題における依存関係の記述,numbers=left]
static int
sort_start(SchedTask *manager, void *d, void *e)
{
    Sort *s =  (Sort*)manager->get_param(0);
    long half_num = s->split_num-1;

    for (int i = 0; i < s->split_num-1; i++) {
        s->fsort[i] = manager->create_task(QUICK_SORT,
                                           (memaddr)&s->data[i*block_num], sizeof(Data)*block_num,
                                           (memaddr)&s->data[i*block_num], sizeof(Data)*block_num);

        if (i>0 && s->bsort[i-1]) {
            s->fsort[i]->wait_for(s->bsort[i-1]);
        }
        if (i<s->split_num-2 && s->bsort[i]) {
            s->fsort[i]->wait_for(s->bsort[i]);
        }
    }

    HTaskPtr restart = manager->create_task(SortSimple,0,0,0,0);
    restart->set_param(0,(memaddr)s);
    if (!all) restart->wait_for(s->fsort[0]);
    for (int i = 0; i < s->split_num; i++) {
        s->fsort[i]->spawn();
    }
    if (sort_count == 1) {
        // last loop wait for all task
         for (int i = 0; i < half_num; i++) {
            restart->wait_for(s->bsort[i]);
            s->bsort[i]->auto_free();
        }
    }
    restart->spawn();

    return 0;
}
\end{lstlisting}

\begin{itemize}
\item 13行目 : fsort が前のステージの fsort の結果を wait する
\item 16行目 : bsort が fsort の結果に対して wait する
\item 20行目 : SortSimple 内で SortSimple Task を生成する事で再起を行う
\item 23行目 : このループで分割ブロックの分だけ Task を生成している
\item 28行目 : ループの最後は全ての Task が終了するのを待つ
\end{itemize}

このように例題ごとの依存関係と、Task をブロックで区切って徐々に生成していくための依存関係
の両方を記述しなければならない。
Task 間で wait\_for することで依存関係を設定するのではなく、 Data Dependency により依存関係を記述できる事が望ましい。