--- a/paper/benchmark.tex	Mon Apr 14 21:00:32 2014 +0900
+++ b/paper/benchmark.tex	Tue Apr 15 18:01:08 2014 +0900
@@ -1,3 +1,55 @@
 \section{benchmark}
 \label{section:benchmark}
 
+\subsection{実験環境}
+
+\begin{itemize}
+\item Mac OS X 10.9.1
+\item 2*2.66 GHz 6-Core Intel Xeon
+\item Memory 16GB 1333MHz DDR3
+\item HHD 1TB
+\item file size 10 GB
+\item CPU num 12
+\item Boyer-Moore String Search で pattern がいくつ含まれているか検索
+\item ファイルを読み込みから結果が返ってくるまでを測定
+\end{itemize}
+
+\subsection{結果}
+
+以下の表に実行結果を示す。
+
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \label{table:result}
+      \small
+      \begin{tabular}[t]{c|r}
+        \hline
+        読み込み方法 & 平均実行速度(s)\\
+        \hline
+        mmap & 154.6 \\
+        \hline
+        一括 Read & 114.9 \\
+        \hline
+        Blocked Read \& SPE\_ANY & 106.0 \\
+        \hline
+        Blocked Read \& IO\_0 & 99.2 \\
+        \hline
+        mmap (CPU num:2) & 106.2 \\
+        \hline
+      \end{tabular}
+      \caption{実行結果}
+    \end{center}
+  \end{table}
+\end{tiny}
+
+実験結果より、mmap より Blocked Read \& IO\_0 の実行速度が 36 \% 改善された。
+また、Blocked Read の CPU Type も SPE\_ANY から IO\_0 に変更することによって更に 4 \% の改善が見られた。
+
+\section{考察}
+mmap より Blocked Read で実装したほうが速くなったが、これは mmap の読み込み方法が問題であると考える。
+
+I/O を含む例題の場合、シングルコアでの逐次実行であれば、mmap や pread で実装しても、Task は 読み込みを行って文字列検索を行うというシンプルな動作になる。
+しかし、マルチコアの並列実行であれば、mmap で実装してしまうと、Task それぞれで読み込みを行ってしまうので競合が発生してしまう。
+
+読み込みの競合が起こらないように Blocked Read にて読み込み部分と文字列検索部分を分けた結果、こちらのほうが速度が向上した。

--- a/paper/cerium.tex	Mon Apr 14 21:00:32 2014 +0900
+++ b/paper/cerium.tex	Tue Apr 15 18:01:08 2014 +0900
@@ -28,11 +28,15 @@
 multi_init(TaskManager *manager)
 {
     float *A, *B, *C;
-    HTaskPtr multiply = manager->create_task(MULTIPLY_TASK);
+    HTaskPtr multiply = manager->create_task
+                                (MULTIPLY_TASK);
     multiply->set_cpu(SPE_ANY);
-    multiply->set_inData(0, (memaddr)A, sizeof(float)*length);
-    multiply->set_inData(1, (memaddr)B, sizeof(float)*length);
-    multiply->set_outData(0, (memaddr)C, sizeof(float)*length);
+    multiply->set_inData
+            (0, (memaddr)A, sizeof(float)*length);
+    multiply->set_inData
+            (1, (memaddr)B, sizeof(float)*length);
+    multiply->set_outData
+            (0, (memaddr)C, sizeof(float)*length);
     multiply->set_param(0,(long)length);
     multiply->spawn();
 }

--- a/paper/conclusion.tex	Mon Apr 14 21:00:32 2014 +0900
+++ b/paper/conclusion.tex	Tue Apr 15 18:01:08 2014 +0900
@@ -1,1 +1,28 @@
-\section{まとめ}
+\subsection{まとめ}
+
+本研究では、I/Oを含む Task の並列処理の動作の改善を行った。
+ファイルを mmap でメモリを確保すると、文字列検索を行う Task が読み込みを行い、それが終了後に検索が行われる。
+読み込みが各 Task それぞれに割り当てられてしまうので、すべての Task が読み込み待ちとなってしまう。
+それを解決する方法として、読み込みを行う Task と文字列検索を行う Task を分けるように Blocked Read の設計と実装を行った。
+
+Blocked Read である程度の大きさを読み込んだら Task が順次起動するように実装したが、それだけだと順次読み込んでいる Blocked Read に Task が割り込まれてしまう。
+そのようなことが起こらないように、Cerium Task Manager に新しいデバイスの設定 IO\_0 というタイプを追加した。このデバイスは、他のデバイス設定よりも priority を高く設定しているので、このタイプ以外で起動する Task に割り込まれることが起こらなくなる。
+
+これらを実装した結果、本研究では mmap で実装したときよりも 36 \% の動作改善が見られた。
+本研究を通して、I/O を含む Task の並列化の問題において、I/O の動作を改善する余地があると考える。
+
+\subsection{今後の課題}
+本来読み込みを行ったファイルは、一度プログラムを実行したあとでもキャッシュとしてメモリ上にテキストがそのまま残っている。
+キャッシュとは、使用頻度の高いデータを高速なデバイスに蓄えておくことによって読み込みのオーバーヘッドを少なくするための機能である。
+
+ハードディスクはメモリと比較すると読み込みが遅いので、ハードディスクからファイル読み込みを行うと、読み込みが速いメモリのほうに格納される。
+読み込んだファイルが再利用されるとき、ハードディスクからメモリに格納するという時間が無くなるので、2回目以降の実行結果は速くなる。
+
+mmap で実装を行うと、同じファイルに対して複数回検索を行うときに 2回目以降のプログラムの処理は速くなる。
+本研究では mmap で 10GB のファイルに対して文字列検索を行うと約150秒かかるが、2回目以降の実行速度に関しては、約7秒でプログラムが終了する。
+
+Blocked Read も 2回目以降の実行速度は mmap と同様に速くなるのだが、ある一定のファイルサイズを越えてしまうとキャッシュが無効となってしまう。
+10GB のファイルではそのようなことが発生することは確認しているが、どれくらいの大きさからキャッシュが無効になるのか不明である。
+
+キャッシュが無効になってしまうと、Blocked Read で実装した文字列検索は複数回実行するときに不利となる。
+なぜこのようなことが起こるのか調査して、それが起こらないように実装していきたい。

--- a/paper/example.tex	Mon Apr 14 21:00:32 2014 +0900
+++ b/paper/example.tex	Tue Apr 15 18:01:08 2014 +0900
@@ -1,5 +1,102 @@
 \section{Cerium Task Manager を使った例題}
 
-\subsection{File Read}
+\subsection{ファイルの読み込みに関する例題}
+テキストファイルをある一定のサイズに分割して読み込むプログラムである。このプログラムでは、pread という関数で実装した。
+pread 関数は UNIX 標準に関するヘッダファイル、unistd.h に含まれている関数である。(表\ref{table:pread})
+読み込んだテキストファイルはバッファに格納されるが、その格納先は TaskManager の API でメモリを確保する。
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \label{table:pread}
+      \small
+        ssize\_t pread(int fd, void *buf, size\_t nbyte, off\_t offset);
+      \begin{tabular}[t]{c|l}
+        \hline
+        int fd & 読み込むファイルディスクリプタ \\
+        \hline
+        void *buf & 予め用意したバッファへの書き込み \\
+        \hline
+        size\_t nbyte & 読み込むサイズ \\
+        \hline
+        off\_t offset& ファイルの先頭からのオフセット \\
+        \hline
+      \end{tabular}
+      \caption{pread 関数の概要}
+    \end{center}
+  \end{table}
+\end{tiny}
+
+この例題の Task 生成部分を以下に示す。
+\\
+\begin{verbatim}
+HTaskPtr read = manager->create_task(Read_task);
+read->set_cpu(SPE_ANY);
+
+read->set_param(0,(long)task_number);
+read->set_param(1,(long)division_size);
+if(read_left_size <= division_size){
+    read->set_param(2,(long)left_size);
+}else{
+    read->set_param(2,(long)division_size);
+}
+read->set_param(3,(long)fd);
+
+read->set_outData(0,read_text + task_number*division_size,
+                                            division_size);
+read->spawn();
+
+read_left_size -= division_size;
+task_number++;
+\end{verbatim}
 
+read という Task を宣言し、Task に CPU Type、パラメータとして生成した Task 番号の task\_number
+1つの Task の読み込み量 division\_size、読み込むファイルのファイルディスクリプタ fd を設定する。
+読み込んだデータの格納先を set\_outData にて設定を行い、そして spawn にて Task を生成する。
+
+Task が生成されると、division\_size分の読み込みを行ったということで、残りの読み込み量 read\_left\_size から division\_size を引き、そして task\_numberを増加させる。
+この Task 生成部分は ファイルサイズ を division\_size で割った数だけ生成され、もし余りがあれば更に1加えた数になる。
+その数が Read Task の数となり、その数だけループ処理を行う。
+中盤にある if 文は、最後の Read Task かどうかで実際に読み込む量が決定される。
+
+read Task の記述を以下に示す。
+\\
+\begin{verbatim}
+static int
+read_task(SchedTask *s, void *rbuf, void *wbuf)
+{
+    long task_number = (long)s->get_param(0);
+    long division_size = (long)s->get_param(1);
+    long read_size = (long)s->get_param(2);
+    long fd = (long)s->get_param(3);
+
+    char *read_text = (char*)s->get_output(wbuf,0);
+
+    pread(fd, read_text, (long)read_size , division_size*task_number);
+    return 0;
+}
+\end{verbatim}
+
+生成時に設定したデータ群を受け取り、それらのデータを pread の引数に渡す。読み込まれたファイルは read\_text に格納される。
+
+ハードディスクに保存されている 10GB のテキストファイルを分割して読み込み終わるまでの時間を下記に示す。
+分割サイズとは、1回の読み込み量である。
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \label{table:preaddata}
+      \small
+      \begin{tabular}[t]{c|l}
+        \hline
+        分割サイズ & 読み込み速度(s)\\
+        \hline
+        16KB & 391.7 \\
+        \hline
+        16MB & 123.6 \\
+        \hline
+      \end{tabular}
+    \end{center}
+  \end{table}
+\end{tiny}
+
+分割サイズを大きくすると、pread の呼ばれる回数が少なくなるので読み込むことが速くなる。
 \subsection{Word Count}

--- a/paper/io.tex	Mon Apr 14 21:00:32 2014 +0900
+++ b/paper/io.tex	Tue Apr 15 18:01:08 2014 +0900
@@ -1,8 +1,159 @@
 \section{並列処理向け I/O の設計と実装}
 
-\subsection{mmap での実装}
+\subsection{mmap での実装と問題点}
+mmap とは、sys/mman.h に含まれている関数で、ファイルの読み込み等に使用される関数である。
+ファイルディスクリプタで指定したファイルを offset から len バイトの範囲を読み込む。
+この時にアドレス addr からメモリを確保するようにする。
+prot には、PROT\_READによるページの読み込み、PROT\_WRITEによるページへの書き込みなどを指定でき、
+flags にはメモリ確保する際のオプションを指定することができる。(表\ref{table:mmap})
+
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \label{table:mmap}
+      \small
+      void * mmap(void *addr, size\_t len, int prot, int flags, int fd, off\_t offset);
+
+      \begin{tabular}[t]{c|l}
+        \hline
+        void *addr &  メモリに確保するときの先頭のアドレス\\
+        \hline
+        size\_t len &  メモリを確保するサイズ\\
+        \hline
+        int prot &  ファイルモード選択\\
+        \hline
+        int flags &  確保するときのオプション指定\\
+        \hline
+        int fd &  読み込むファイルのファイルディスクリプタ\\
+        \hline
+        off\_t offset & ファイル先頭からの読み込み開始位置 \\
+        \hline
+      \end{tabular}
+      \caption{mmap 関数の概要}
+    \end{center}
+  \end{table}
+\end{tiny}
+
+mmap でファイルを読み込むタイミングは、mmap 関数が呼ばれたときではなく、mmap した領域に対して何らかのアクセスをしたときに初めてファイルが読み込まれる。
+
+図\ref{fig:mmap}では、読み込んだファイルを分割して、それらの領域に何らかの処理を加えるときの図である。これらの処理を Task と呼ぶ。
+Task 1 という1個目の Task が実行される。実行されたときに初めてそれらの領域にファイルが読み込まれ、その後何らかの処理が行われ、そして Task 2 も同様に読み込みを行ってから処理が行われる。
+これら Task は並列に実行されるべきであるが、ファイル読み込みの I/O 部分がネックとなり、本来並列実行される Task が読み込み待ちを起こしてしまう恐れがある。
+その上、読み込み方法が OS 依存となるために環境によって左右されやすく、プログラムの書き手が読み込みに関して制御しにくい。
+
+それらを解決するためには、ファイル読み込みと Task を分離し、ファイルの読み込みも制御しやすくでき、なおかつ高速で動くのではないかと考えた。
+
+
+% \begin{figure}[htbp]
+% \begin{center}
+% \includegraphics[width=0.7\textwidth]{fig/mmap.pdf}
+% \end{center}
+% \caption{mmap image}
+% \label{fig:mmap} \end{figure} 
+
 
 \subsection{Blocked Read の設計と実装}
 
+Blocked Read とは、読み込みの Task と、それに対する何らかの処理の Task を切り離すための実装方法で、pread 関数にて実装した。
+pread 関数は、unistd.h に含まれているので、UNIX 専用の関数である。ファイルディスクリプタで指定したファイルの先頭 から 
+offset 分ずれた場所を基準として、その基準から count バイトを読み込み、それを buf に格納する。
+\ref{table:pread}
+
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \label{table:pread}
+      \small
+      ssize\_t pread(int d, void *buf, size\_t nbyte, off\_t offset);
+
+      \begin{tabular}[t]{c|l}
+        \hline
+        int d & 読み込むファイルのファイルディスクリプタ\\
+        \hline
+        void *buf & 読み込んだファイルの格納場所 \\
+        \hline
+        size\_t nbyte & 読み込むファイル量\\
+        \hline
+        off\_t offset & ファイル先頭からの読み込み開始位置\\
+        \hline
+      \end{tabular}
+      \caption{pread 関数の概要}
+    \end{center}
+  \end{table}
+\end{tiny}
+
+mmap での実装との違いは、ファイルの読み込みがどのタイミングで起こるかである。
+mmap で実装したときは、Task 1つ 1つが読み込みを行ってから処理を行う。
+それに対して、Blocked Readは、読み込み専用の Read Task と、処理専用の Task を別々に生成する。
+Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行う。
+分割して読み込み終わったら、それぞれの Task が実行される。
+(図\ref{fig:block})
+Read Task が生成されて、その後 Task の生成となるので、Read Task は常に走っている必要がある。
+
+%\begin{figure}[htbp]
+%\begin{center}
+%\includegraphics[width=0.8\textwidth]{fig/blockedreadimage.pdf}
+%\end{center}
+%\caption{Blocked Read image}
+%\label{fig:block}
+%\end{figure}
+
+図\ref{fig:block} では、Read Task 1つに対して Task 1つ起動しているが、このように1つ1つ生成、起動をすると Task 生成でメモリを圧迫してしまい、全体的な動作に影響を与えてしまう。
+実際には Task をある一定数まとめた単位で生成し、起動を行っている。この単位を Task Block と定義する。
+
+Task Block 1つ当たりの Task 量を $n$ とおく。Task 1つ当たりの読み込む量を $L$ とすると、Task Block 1つ当たりの読み込む量は $L \times n$ となる。
+Blocked Read が読み込み終わってから、Task Blockが起動するようにするので、Blocked Read 1つ当たりの読み込み量も $L \times n$となる。
+
+もし、Task Block が Blocked Read よりも先走ってしまうとどうなるであろうか。
+まだ読み込まれていない領域に対して何らかの処理を行ってしまうので、正しい結果が返ってこなくなってしまう。
+それを防止するために、Blocked Read が読み込み終わってから Task Block が起動されるように wait をかけている。
+
+%(図\ref{fig:block})
+%\begin{figure}[htbp]
+%\begin{center}
+%\includegraphics[width=1.0\textwidth]{fig/blockreadtask.pdf}
+%\end{center}
+%\caption{Blocked Read image}
+%\label{fig:block}
+%\end{figure}
+
+
 \subsection{I/O 専用 thread の実装}
 
+Cerium Task Manager では、各種 Task にデバイスを設定することができる。
+SPE\_ANY を使用すると、Task Manager で CPU の割り振りを自動的に行う。しかし、この機能を使用すると、Blocked Read に影響を与えてしまう。
+Blocked Read 、Task それぞれに SPE\_ANY にてデバイスの設定を行うと、Task Manager 側で自動的に CPU を割り当てられ、本来 Blocked Read は連続で読み込むはずが、他の Task を割り当てられてしまう。
+(図\ref{fig:speany})
+
+%\begin{figure}[htbp]
+%\begin{center}
+%\includegraphics[width=1.0\textwidth]{fig/speany.pdf}
+%\end{center}
+%\caption{SPE\_ANY での実装時}
+%\label{fig:speany}
+%\end{figure}
+
+この問題を解決するために、Task Manager に新しく I/O 専用の thread 、 IO\_0 の追加を行った。
+
+%(図\ref{fig:addio0})
+%%この問題を解決するために、Task Manager に IO\_0という新しいデバイス設定を追加した。
+%
+%
+%\begin{figure}[htbp]
+%\begin{center}
+%\includegraphics[width=0.7\textwidth]{fig/addio_0.pdf}
+%\end{center}
+%\caption{IO\_0 の追加}
+%\label{fig:addio0}
+%\end{figure}
+
+SPE\_ANY で使用する CPU の設定よりも高く設定しているので、IO\_0 で設定を行う Read Task に SPE\_ANY で設定した 文字列検索 Task に割り込まれることがなくなる。
+(図\ref{fig:io0})
+
+%\begin{figure}[htbp]
+%\begin{center}
+%\includegraphics[width=1.0\textwidth]{fig/io0.pdf}
+%\end{center}
+%\caption{Blocked Read Task を IO\_0 での実装時}
+%\label{fig:io0}
+%\end{figure}