--- a/cerium.tex	Mon Jan 11 11:39:37 2016 +0900
+++ b/cerium.tex	Mon Jan 11 21:27:55 2016 +0900
@@ -146,4 +146,72 @@
 計算処理の並列化を図ったとしても I/O がボトルネックになってしまい処理全体が高速にならない。
 本項では Cerium に実装した並列処理用 I/O を行ない、I/O 部分の高速化を図った。
 
-Cerium の例題ではファイル読み込みを mmap にて実装していた。しかし、mmap だとファイルを読み込んでから Task を実行するので、読み込んでいる間は他の CPU が動作せず並列度が落ちる。そこで、I/O 部分も Task と並列に動作するように実装した。
+Cerium の例題ではファイル読み込みを mmap にて実装していた。
+しかし、mmap だとファイルを読み込んでから Task を実行するので、読み込んでいる間は他の CPU が動作せず並列度が落ちる。
+
+mmap は function call 後にすぐにファイルを読みに行くのではなく、仮想メモリ領域にファイルの中身を対応させる。
+その後メモリ空間にアクセスされたときに、OS が対応したファイルを読み込む。
+また、読み込む方法が OS 依存となってしまうため環境に左右されやすく、プログラムの書き手が読み込みの制御をすることが難しい。
+
+図\ref{fig:mmap}は mmap で読み込んだファイルに対して Task1 、 Task2 がアクセスしてそれぞれの処理を行うときのモデルである。
+
+Task1 が実行されると仮想メモリ上に対応したファイルが読み込まれ、読み込み後 Task1 の処理が行われる。
+その後 Task2 も Task1 と同様の処理が行われるが、これら 2 つの Task の間に待ちが入る。
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.7]{images/mmap.pdf}
+  \end{center}
+  \caption{mmap Model}
+  \label{fig:mmap}
+\end{figure}
+
+mmap を使わず、読み込みを独立した Thread で行ない、ファイルを一度に全て読み込むのではなくある程度の大きさ(Block)分読み込み、読み込まれた部分に対して並列に Task を起動する。
+これを Blocked Read と呼び、高速化を図った。
+
+Blocked Read を実装するにあたり、WordCount を例題に挙げる。
+ファイルを読み込む Task (以下、ReadTask) と、読み込んだファイルに対して計算を行う Task (以下、WordCount) を別々に生成する。ReadTask は一度にファイル全体を読み込むのではなく、ある程度の大きさで分割してから読み込みを行う。分割して読み込んだ範囲に対して WordCount を行う。
+
+WordCount を Blocked Read で読み込み処理をしたとき以下の図\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 ごとに生成して WordCount を行なっている。
+Task Block で計算される領域が Blocked Read で読み込む領域を追い越して実行してしまうと、まだ読み込まれていない領域に対して計算されてしまう。
+その問題を解決するために依存関係を適切に設定する必要がある。
+Blocked Read による読み込みが終わってから TaskBlock が起動されるようにするため、Cerium の API である wait\_for にて依存関係を設定する。
+
+また、ReadTask は連続で処理される必要がある。
+なぜならば、ReadTask でファイルを読み込む前提で WordCount がその領域に対して計算を行うので、ReadTask の処理が遅くなってしまうだけでオーバーヘッドとなってしまう。\ref{fig:BlockedReadModel}
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.5]{./images/blockedreadimage.pdf}
+  \end{center}
+  \caption{BlockedRead Model}
+  \label{fig:BlockedReadModel}
+\end{figure}
+
+Blocked Read を実装することにより、読み込み部分と処理部分の並列化を行なった。Blocked Read は連続で読み込まれる必要があるため、さらに I/O 専用 thread を実装した。
+
+\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}
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.7]{./images/iothread.pdf}
+  \end{center}
+  \caption{IO Thread による BlockedRead}
+  \label{fig:iothread_blockedread}
+\end{figure}

Binary file images/blockedread.pdf has changed

Binary file images/blockedreadimage.pdf has changed

Binary file images/iothread.pdf has changed

Binary file images/mmap.pdf has changed

Binary file images/speblockedread.pdf has changed

Binary file master_paper.pdf has changed