# HG changeset patch
# User Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
# Date 1393054611 -32400
# Node ID a56ad81ccdf9f73d2e6528cbf3961b4a4a4f73b1
# Parent  5d25f13493c3387fdef766d4d6fb062426ba1085
fic

diff -r 5d25f13493c3 -r a56ad81ccdf9 preliminary/final-thesis.pdf
Binary file preliminary/final-thesis.pdf has changed
diff -r 5d25f13493c3 -r a56ad81ccdf9 preliminary/final-thesis.tex
--- a/preliminary/final-thesis.tex	Sat Feb 22 02:49:04 2014 +0900
+++ b/preliminary/final-thesis.tex	Sat Feb 22 16:36:51 2014 +0900
@@ -45,6 +45,8 @@
 Cerium Task ManagerはPlayStation 3/Cell、Mac OS X及びLinux上で利用することが可能で、近年ではGPUへの利用も可能となった。\cite{tomari}
 
 \section{I/O を含む Task の概要}
+ファイルを読み込んで一定の大きさでファイルを分割し (File Read)、それらに対してそれぞれ文字列検索等の処理 (Run Tasks)を行う。
+そしてそれぞれの処理から返されたの結果 (Output Data)を最後に集計をして結果を返す(Run resultTask)。(図\ref{fig:includeio})
 
 図\ref{fig:includeio}
 
@@ -52,24 +54,30 @@
 \begin{center}
 \includegraphics[width=0.4\textwidth]{pic/includeio.pdf}
 \end{center}
-\caption{includeio}
+\caption{I/O を含む Task}
 \label{fig:includeio}
 \end{figure}
 
+先行研究では、File Readの部分は mmap 関数を使用して実装していた。mmap 関数での実装の場合はコードの記述が容易である。
 
 \section{並列処理向け I/O の設計と実装}
 
-図\ref{fig:blockedreadimage}
+\subsection{mmap での実装の問題点}
+
+mmap でファイルを読み込むタイミングは、mmap 関数が呼ばれたときではなく、mmap した領域に対して何らかのアクセスをしたときに初めてファイルが読み込まれる。
+つまり、分割された Task は文字列検索をすぐに行うのではなく、文字列検索を行おうとした時に初めてファイルが格納される。
+Task は複数一斉に実行されることが望ましいが、mmap だとそれぞれの Task で読み込みが起こってしまうので、I/O ネックによる Task の待ちが発生する恐れがある。
 
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=0.4\textwidth]{pic/blockedreadimage.pdf}
-\end{center}
-\caption{Blocked Read image}
-\label{fig:blockedreadimage}
-\end{figure}
+\subsection{Blocked Read の設計と実装}
+Blocked Read とは、あるサイズずつで読み込む処理と、それらに文字列検索行う処理を分離させるための実装方法である。
+この方法では、読み込み専用の Blocked Read と、文字列検索を行う Task Blocks をを別々に生成し処理を行う。
+Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行い、読み込みされ次第それぞれの文字列検索が行われる。
 
-図\ref{fig:blockedreadwait}
+Task は 1つずつ起動すると、起動した Task でメモリを圧迫してしまうため、Task を複数まとめたブロック単位で起動を行う。
+この1つのブロックで処理されるテキストファイルを、Blocked Read で読み込んでいき、読み込みが終わったら読み込まれた範囲の Task Blocks を起動する。
+もし、Blocked Read で読み込まれる前にその範囲を担当する Task が起動してしまうと、正しい結果が返ってこない。
+それを防止するために、Task Blocks は必ず Blocked Read が行われてから起動するように wait をかけている。
+(図\ref{fig:blockedreadwait})
 
 \begin{figure}[htbp]
 \begin{center}
@@ -79,29 +87,63 @@
 \label{fig:blockedreadwait}
 \end{figure}
 
+\subsection{I/O 専用 thread の実装}
+Cerium Task Manager では Task 単位で CPU Type の設定を変更することができる。
+SPE\_ANY という CPU Type を設定すると、Cerium Task Manager 側が自動的に CPU を割り振ってくれる。
+しかし、今回の実装でこのCPU Type を使用してしまうと、Blocked Read Task の隙間時間に Task が割り振られてしまう問題がある。
+(図\ref{fig:speany})
 
-図\ref{fig:io0}
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=0.4\textwidth]{pic/speany.pdf}
+\end{center}
+\caption{SPE\_ANYでの設定時}
+\label{fig:speany}
+\end{figure}
+
+その問題を解決するために、IO\_0 という CPU Type を新しく実装した。
+IO\_0 は他の CPU Type よりも priority を高く設定しているので、他の Task に割り込まれることがないようにした。
+(図\ref{fig:io0})
 
 \begin{figure}[htbp]
 \begin{center}
 \includegraphics[width=0.4\textwidth]{pic/io0.pdf}
 \end{center}
-\caption{io0}
+\caption{IO\_0 での実装時}
 \label{fig:io0}
 \end{figure}
 
+\section{ベンチマーク}
 
-図\ref{fig:speany}
+\subsection{実験環境}
+\begin{itemize}
+ \item Mac OS X Mavericks (10.9.1)
+ \item HDD 1TB、Memory 16GB、CPU 2*2.66 GHz 6-Core Intel Xeon
+ \item ファイルサイズ 10GBに対して検索文字列がいくつ含まれるのかカウント
+\end{itemize}
+\subsection{実験結果}
 
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=0.4\textwidth]{pic/speany.pdf}
-\end{center}
-\caption{speany}
-\label{fig:speany}
-\end{figure}
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \label{table:preaddata}
+      \small
+      \begin{tabular}[t]{c|l}
+        \hline
+        読み込み方法 & 実行速度(s)\\
+        \hline
+        mmap & XX.XXX \\
+        \hline
+        Blocked Read \& SPE\_ANY & XX.XXX \\
+        \hline
+        Blocked Read \& IO\_0 & XX.XXX \\
+        \hline
+      \end{tabular}
+      \caption{file read の実行結果}
+    \end{center}
+  \end{table}
+\end{tiny}
 
-\section{ベンチマーク}
 
 \section{まとめと今後の課題}
 
@@ -116,9 +158,5 @@
 Cerium Task Manager の GPGPU への対応\\
 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)、May 2013
 
-\bibitem{BM}J.S.Moore, R.S. Boyer.\\
-A Fast String Searching Algorithm\\
-Communications of the Association for Computing Machinery, 1977,pp.762-772.
-
 \end{thebibliography}
 \end{document}