--- a/paper/chapter6.tex	Mon Feb 09 11:32:28 2015 +0900
+++ b/paper/chapter6.tex	Tue Feb 10 14:06:53 2015 +0900
@@ -1,2 +1,140 @@
 \chapter{並列処理向けI/O}
-\section{新たに実装したI/Oの機構}
+ファイル読み込みなどの I/O を含むプログラムは、読み込み時間が Task の処理時間と比較してオーバーヘッドになることが多い。
+プログラムの並列化を行ったとしても、 I/O がボトルネックになってしまうと処理は高速にならない。
+本項では Cerium に並列処理用の I/O の実装を行う。これにより I/O 部分の高速化を図る。
+
+\section{mmap}
+Cerium ではファイルの読み込みを mmap により実装していた。
+しかし、mmap や read によりファイルを読み込んでから処理を実行させると、
+読み込んでいる間は他の CPU が動作せず、並列度が落ちてしまう。
+そこで、 I/O 部分も並列に動作するよう実装した。
+
+Read を並列に行うには、File Open ではなく mmap を使う方法がある。
+mmap はすぐにファイルを読みに行くのではなく、まず仮想メモリ空間にファイルの中身を対応させる。
+メモリ空間にアクセスが行われると、OS が対応したファイルを読み込む。
+
+mmap で読み込んだファイルに Task1、Task2 がアクセスし、それぞれの処理を行う際の例を図:\ref{fig:mmap}に示す。
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.7]{./images/mmap.pdf}
+  \end{center}
+  \caption{mmap の Model}
+  \label{fig:mmap}
+\end{figure}
+
+Task1 が実行される時、仮想メモリ上 Open されたファイルの読み込みを行い、Task1 の処理を行う。
+その後、同様に Task2 も読み込みを行ってから処理を行う。この Task1 と Task2 の間に待ちが入る。
+
+ファイルの読み込みが起こると、アクセスした Thread/Process には wait がかかってしまう。
+しかし mmap による Read は Task と並列に実行されるべきである
+ mmap は逐次アクセスを仮定しているので、OS 内部で自動的にファイルの先読みを行う事も期待できる。
+しかしそれは OS の実装に依存してしまう。
+読み込みが並列に実行されない場合、 Task が読み込み待ちを起こしてしまう。
+読み込みが OS 依存となるため、環境によって左右されやすく、汎用性を損なってしまう。
+
+そこで、mmap を使わず、read を独立したスレッドで行い、読み込まれた部分に倒して並列に Task を起動する。
+これを Blocked Read と呼ぶ。Blocked Read によるプログラミングは複雑になるが、高速化が期待できる。
+
+\section{Blocked Read による I/O の並列化}
+Blocked Read を実装するに辺り、WordCount を例に考える。
+Blocked Read はファイル読み込み用の Task(以下、ReadTask) と
+読み込んだファイルに対して処理を行う Task(今回はWordCount) を別々に生成する。
+ReadTask はファイル全体を一度に全て読み込むのではなく、ある程度の大きさで分割してから読み込みを行う。
+分割後の読み込みが終わると、読み込んだ範囲に対して WordCount を行う。
+
+BlockedRead による WordCount を行う場合、図:\ref{fig:blockedread}のようになる。
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.5]{./images/blockedread.pdf}
+  \end{center}
+  \caption{BlockedRead による WordCount}
+  \label{fig:blockedread}
+\end{figure}
+
+Task を一定数まとめた単位で生成し、起動を行っている。この単位を Task Block と定義する。
+TaskBlock が BlockedRead を追い越して実行してしまうと、まだ読み込まれてない領域に対して処理を行ってしまう。
+その問題を解決するため、依存関係を設定する。
+BlockedReadによる読み込みが終わってから TaskBlock が起動されるよう、
+Cerium の API である wait\_for により依存関係を設定する。
+
+以上を踏まえ、BlockedRead の実装を行った。
+BlockedRead Task の生成はソースコード:\ref{src:blockedread_create}のように行う。
+
+\begin{lstlisting}[frame=lrbt,label=src:blockedread_create,caption=BlockedRead を行う Task の生成,numbers=left]
+HTaskPtr readTask = manager->create_task(READ_TASK)
+readTask->set_cpu(DEVICE_TYPE);
+readTask->set_outData(0, file_map + task_num * division_size, task_blocks * division_size);
+readTask->set_param(0, fd);
+readTask->set_param(1, task_num * division_size);
+runTask();
+readTask->set_param(2, task_num * division_size)
+readTask->spawn();
+\end{lstlisting}
+
+\begin{itemize}
+\item 3行目、set\_outData(0): ファイルを読み込んだ際の格納場所を設定
+\item 4行目、set\_param(0): 読み込むファイルディスクリプタを設定
+\item 5行目、set\_param(1): BlockedRead Task で読み込むファイルの範囲の先頭のポジションを設定
+\item 7行目、set\_param(2): BlockedRead Task で読み込むファイルの範囲の末尾のポジションを設定
+\end{itemize}
+
+Cerium において、 WordCount で必要な Task を全て生成してしまうと、
+その Task のデータ構造自体がメモリを消費してしまう。
+そこである程度の量の Task を起動し、それが終了してから(正確には終了する前に)次の Task を生成するようになっている。
+それらの機能を持った関数が6行目にあたる run\_tasks である。
+run\_tasks に wait\_for による ReadTask との待ち合わせの処理を入れれば良い。
+
+BlockedRead の Task をいかに示す。
+
+\begin{lstlisting}[frame=lrbt,label=src:blockedread_task,caption=BlockedRead Task,numbers=left]
+static int
+read_task(SchedTask *s, void *rbuf, void *wbuf) {
+    long fd = (long)s->get_param(0);
+    long start = (long)s->get_param(1);
+    long end   = (long)s->get_param(2);
+    char txt   = (char*)s->get_output(wbuf, 0);
+    long size  = end - start;
+    
+    pread(fd, txt, size, start);
+    return 0;
+}
+\end{lstlisting}
+
+Cerium の API により、生成部分で設定したパラメタをそれぞれ受け取る。
+ファイル読み込みの先頭・末尾のポジションが渡されているので、ファイルから読み込むサイズは求められる。
+受け取ったパラメタをそれぞれ pread 関数に渡すことで Blocked Read を実現している。
+\newpage
+\section{I/O 専用 Thread の実装}
+Cerium Task Manager では、各種 Task にデバイスを設定することができる。
+ SPE\_ANY 設定を使用すると、 Task Manager で CPU の割り振りを自動的に行う。
+BlockedRead は連続で読み込まれなければならないが、
+SPE\_ANY 設定で実行すると BlockedRead 間に別の Task を割り込んでしまう場合がある。
+(図:\ref{fig:spe_any_blockedread})
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.7]{./images/speblockedread.pdf}
+  \end{center}
+  \caption{BlockedRead と Task を同じ thread で動かした場合}
+  \label{fig:spe_any_blockedread}
+\end{figure}
+
+そこで I/O 専用の Thread である IO\_0 の追加を行った。
+
+IO\_0 は SPE\_ANY とは別 Thread の Scheduler で動くので、SPE\_ANY で動いている Task に割り込まれることはない。
+しかし、読み込みの終了を通知し、次の read を行う時に他の Task がスレッドレベルで割り込んでしまう事がある。
+pthread\_getschedparam() で IO\_0 の priority の設定を行う必要がある(図:\ref{fig:iothread_blockedread})。
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.7]{./images/iothread.pdf}
+  \end{center}
+  \caption{IO Thread による BlockedRead}
+  \label{fig:iothread__blockedread}
+\end{figure}
+IO\_0 で実行される Task は BlockedRead のみなので、
+IO\_0 のpriority を高く設定することで Blocked Read は連続で実行される。
+
+また、以上の事から I/O を含む処理では、 I/O を行う Thread の priority を高くする必要があるという知見を得られた。