--- a/paper/chapter3.tex	Mon Feb 16 20:07:21 2015 +0900
+++ b/paper/chapter3.tex	Tue Feb 17 03:31:37 2015 +0900
@@ -1,4 +1,4 @@
-\chapter{Ceriumを用いた例題}
+\chapter{Cerium を用いた例題}
 Cerium は様々な例題を含んでいる。本論文では Bitonic Sort、 Word Count、 FFT の3つの例題を扱う。
 
 Bitonic Sort は、ベンチマークをとる際の一般的な例題として選択した。
@@ -13,6 +13,7 @@
 以上3つの例題を用いてベンチマークを行っていく。本論文で使用する各種例題について紹介する。
 
 \section{Bitonic Sort}
+\label{sec:about_sort}
 Cerium Task Manager を使った Sort である。
 Bitonic Sort は配列の分割を行い、分割した部分に対して sort を行う。
 分割後の Sort には QuickSort を使用している。Task の構成は以下のようになる。
@@ -103,4 +104,83 @@
 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:sort}
+\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_rependency,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 により依存関係を記述できる事が望ましい。