--- a/paper/cerium.tex	Sun Apr 20 16:25:41 2014 +0900
+++ b/paper/cerium.tex	Sun Apr 20 22:21:07 2014 +0900
@@ -1,6 +1,5 @@
 \section{Cerium TaskManager}\label{section:cerium}
 
-\subsection{Cerium Task Manager の概要}
 Cerium Task Manager は並列プログラミングフレームワークであり、内部では C や C++ で実装されている。
 Cerium Task Manager は、User が並列処理を Task 単位で記述し、関数やサブルーチンを Task として扱い、その Task に対して Input Data、Output Data 及び依存関係を設定する。
 そして、それに基づいた設定の元で Task Manager にて管理し実行される。
@@ -17,32 +16,29 @@
 \label{fig:cerium}
 \end{figure}
 
-\subsection{Cerium Task Manager の利用方法}
+\newpage
+
+\subsection{Cerium Task Manager を使った例題}
+今回計測に使用した例題 WordCount を例にとり、以下に Task の生成部分を以下に示す。
+このプログラムは、WordCount Task と Print Task の2種類の Task から構成される。
 
-input Data で格納して 2 つの数を乗算し、output data に格納する multiply という例題がある。
-その例題の Task 生成部分を以下に示す。
+input data とは、mmap や read で読み込んだファイルであり、このファイルを $ n $ KByte の大きさに分割して、WordCount Task にそれぞれ割り当てる。
 
-\newpage
+WordCount Task は、input された data の単語数と行数をカウントし、それらを output に指定された data 領域に書きこむ。
+
+以下に WordCount の Task 生成部分を示す。
 
 \begin{verbatim}
-multi_init(TaskManager *manager)
-{
-    float *A, *B, *C;
-    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_param(0,(long)length);
-    multiply->spawn();
-}
+exec = manager->create_task(TASK_EXEC);
+exec->set_inData(0,
+                file_mmap + i*division_size,
+                size);
+exec->set_outData(0,o_data + i*out_size,
+                division_out_size);
+
+exec->set_cpu(spe_cpu);
+exec->spawn();
+i++;
 \end{verbatim}
 
 \begin{tiny}
@@ -54,11 +50,9 @@
         \hline
         create\_task& Task を生成する \\
         \hline
-        set\_inData & Task への入力データのアドレスを追加 \\
+        set\_inData & Task に入力データのアドレスを追加 \\
         \hline
-        set\_outData & Task への出力データのアドレスを追加 \\
-        \hline
-        set\_param & Task へ値を一つ渡す。ここでは length \\
+        set\_outData & Task に出力データのアドレスを追加 \\
         \hline
         set\_cpu & Task を実行するデバイスの設定  \\
         \hline
@@ -70,21 +64,47 @@
   \end{table}
 \end{tiny}
 
+しかし、input data は分割されたデータが送られてくるため、分割された前後のテキストがどうなっているかはわからない。
+そのため担当範囲であるデータの先頭と末尾のパラメータを単語数と行数の他に付け加える。後にそのデータを他の WordCount の結果と照らし合わせ、分割されたテキストを正しく整合する。
 Task の記述は以下のようになる。
 \\
 
 \begin{verbatim}
-static int
-run(SchedTask *s,void *rbuf, void *wbuf)
+wordcount(SchedTask *s, void *rbuf, void *wbuf)
 {
-    float *A, *B, *C;
-    A = (float*)s->get_input(rbuf,0);
-    B = (float*)s->get_input(rbuf,1);
-    C = (float*)s->get_output(wbuf,0);
-    long  length=(long)s->get_param(0);
-    for (int i=0;i<length;i++) {
-        C[i]=A[i]*B[i];
+    char *i_data = (char *)s->get_input(0);
+    unsigned long long *o_data =
+        (unsigned long long *)s->get_output(0);
+    unsigned long long *head_tail_flag =
+                                o_data + 2;
+    int length = (int)s->get_inputSize(0);
+
+    head_tail_flag[0] =
+        (i_data[0] != 0x20) &&
+        (i_data[0] != 0x0A);
+
+    word_num -= 1-head_tail_flag[0];
+
+    for (; i < length; i++) {
+        if (i_data[i] == 0x20) {
+            word_flag = 1;
+        } else if (i_data[i] == 0x0A) {
+            line_num += 1;
+            word_flag = 1;
+        } else {
+            word_num += word_flag;
+            word_flag = 0;
+        }
     }
+
+    word_num += word_flag;
+    head_tail_flag[1] =
+        (i_data[i-1] != 0x20) &&
+        (i_data[i-1] != 0x0A);
+
+    o_data[0] = (unsigned long long)word_num;
+    o_data[1] = (unsigned long long)line_num;
+
     return 0;
 }
 \end{verbatim}
@@ -107,3 +127,56 @@
     \end{center}
   \end{table}
 \end{tiny}
+
+Print Task は WordCount Task によって書き出された単語数と行数を集計し、結果を出力する Task である。
+WordCount Task が全て走り終わったあとに、Print Task が走るように wait をかけている。(図\ref{fig:wordcount})
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[scale=0.4]{images/wordcount.pdf}
+\end{center}
+\caption{WordCount Model}
+\label{fig:wordcount}
+\end{figure}
+
+単語数や行数、そして担当範囲の先頭と末尾の文字列の状態を配列としてデータを保持している。
+その配列を Print Task にて処理を行い単語数、行数を集計する。
+
+しかし、分割のされ方によっては、単語数がカウントされない場合がある。(((図が必要!!!)))
+
+
+Print Task の記述は以下のようになる。
+
+\begin{verbatim}
+static int
+run_print(SchedTask *s, void *rbuf, void *wbuf)
+{
+    WordCount *w = (WordCount*)s->get_input(0);
+    unsigned long long *idata = w->o_data;
+    long status_num = w->status_num;
+    int out_task_num = w->out_task_num;
+
+    unsigned long long word_data[2];
+
+    int flag_cal_sum = 0;
+
+    for (int i = 0; i < out_task_num ; i++) {
+        word_data[0] += idata[i*w->out_size+0];
+        word_data[1] += idata[i*w->out_size+1];
+        unsigned long long *head_tail_flag = 
+            &idata[i*w->out_size+2];
+        if((i!=out_task_num-1)&&
+           (head_tail_flag[1] == 1) &&
+           (head_tail_flag[4] == 0)) {
+            flag_cal_sum++;
+        }
+    }
+
+    word_data[0] += flag_cal_sum;
+
+    for (int i = status_num-1; i >=0; i--) {
+        s->printf("%llu ",word_data[i]);
+    }
+    return 0;
+}
+\end{verbatim}

--- a/paper/conclusion.tex	Sun Apr 20 16:25:41 2014 +0900
+++ b/paper/conclusion.tex	Sun Apr 20 22:21:07 2014 +0900
@@ -1,13 +1,7 @@
 \section{まとめと今後の課題}
-
-本研究では、I/Oを含む Task の並列処理の動作改善を行った。
-ファイルを mmap にて読み込むと、WordCount を行う Task がそれぞれ読み込みを行う。
-
-読み込みが各 Task それぞれに割り当てられてしまうので、すべての Task が読み込み待ちとなってしまう。
-それを解決する方法として、Read Task と文字列処理を行う Task を分けるように Blocked Read の設計と実装を行った。
-
-Blocked Read である程度の大きさを読み込んだら Task が順次起動するように実装したのだが、それだけだと、順次読み込んでいる Blocked Read に Task が割り込まれてしまう。
-そのようなことが起こらないように、Cerium Task Manager に新しいデバイスの設定 IO\_0 というタイプを追加した。
+本研究では、Task と 読み込みが並列に動作するように Blocked Read の実装を行った。
+またそれだけだと、Blocked Read に Task が割り込まれるので、I/O 専用 thread の追加を行った。
+Blocked Read に I/O 専用 thread を割り当てると、さらに速くなった。
 
 I/O が含まれるときの並列処理は、I/O のコントロールをプログラマが実装することで動作改善に繋がる。
 
@@ -16,7 +10,9 @@
 mmap で実装を行うと、同じファイルに対して複数回検索を行うときに 2回目以降のプログラムの処理は速くなる。
 それに対して、
 Blocked Read も 2回目以降の実行速度は mmap と同様に速くなるのだが、ある一定のファイルサイズを越えてしまうとキャッシュが無効となってしまう。
-10GB のファイルではそのようなことが発生することは確認しているが、どれくらいの大きさからキャッシュが無効になるのか不明である。
+10GB のファイルではそのようなことが発生することは確認したが、なぜこのようなことが発生するのか調査する。
 
-キャッシュが無効になってしまうと、Blocked Read で実装した文字列検索は複数回実行するときに不利となる。
-なぜこのようなことが起こるのか調査して、それが起こらないように実装する必要がある。
+さらに、pread による複数 read を実装したが、複数 mmap に関してはまだ実装・計測を行っていない。これらの計測を行って、どちらが最高速に動作するかどうか調べる必要がある。
+
+また、Blocked Read のコードを記述するのは煩雑で、これらを毎回記述することは大変である。
+これを Cerium の API として落としこむことによって、簡単に利用できるようにしたい。

--- a/paper/example.tex	Sun Apr 20 16:25:41 2014 +0900
+++ b/paper/example.tex	Sun Apr 20 22:21:07 2014 +0900
@@ -128,7 +128,7 @@
 分割サイズを大きくすると、pread の呼ばれる回数が少なくなるので読み込むことが速くなる。
 \fi
 
-Cerium Task Manager を使った例題として、WordCount を挙げる。このプログラムには、WordCount Task と Print Task の2種類の Task から構成される。
+Cerium Task Manager を使った例題として、WordCount を挙げる。このプログラムは、WordCount Task と Print Task の2種類の Task から構成される。
 
 input data とは、mmap や read で読み込んだファイルであり、このファイルを $ n $ KByte の大きさに分割して、WordCount Task にそれぞれ割り当てる。
 

--- a/paper/introduction.tex	Sun Apr 20 16:25:41 2014 +0900
+++ b/paper/introduction.tex	Sun Apr 20 22:21:07 2014 +0900
@@ -2,10 +2,13 @@
 
 当研究室では、Task 単位で記述する並列プログラミングフレームワーク、Cerium の開発を行っている。
 
-先行研究による Task の並列化によって、プログラム全体の処理速度は飛躍的に向上した。\cite{kinjyo} 
 ファイルの読み込み等の I/O を含むプログラムは、読み込み時間が Task の処理時間と比較して非常に重くなる場合が多い。
-マルチコアでの並列処理を行ったとしても、I/O の動作を軽量にしなければ、I/O を含めたプログラムの処理は軽量にならない。
+マルチコアでの並列処理を行ったとしても、I/O の動作の負担が大きければ、I/O を含めたプログラムの処理は高速にならない。
 
 従来の実装のように、ファイルを mmap や read で読み込んでから並列処理をさせると、読み込んでいる時間、他の CPU が動いていないので、並列度が下がってしまう。
 
-本研究では、並列処理時におけるファイル読み込みをどのように実装すれば軽量に動作するかを考慮し、なおかつ読み込みとそれらに対する処理をプログラム作成者が自由に書けるように設計・実装を行う。
+本研究では、並列処理時におけるファイル読み込みをどのように実装すれば最高速に動作するかを考慮し、
+なおかつ読み込みとそれらに対する処理をプログラム作成者が自由に書けるように設計・実装を行った。
+Cerium の例題にある Word Count \cite{yutaka:os} のファイル読み込み部分を様々な実装方法で測定を行い、 
+その結果、個々の Task のサイズが大きければ後述するBlocked Read のほうが mmap よりも速度が出た。
+しかし、Task のサイズが小さいと Blocked Read と mmap はほとんど同じ速度を計測した。

--- a/paper/io.tex	Sun Apr 20 16:25:41 2014 +0900
+++ b/paper/io.tex	Sun Apr 20 22:21:07 2014 +0900
@@ -1,6 +1,11 @@
 \section{並列処理向け I/O の設計と実装}
 
-\subsection{mmap での実装と問題点}
+\subsection{従来のファイル読み込みの実装と問題点}
+従来は mmap や read でファイルの読み込みの実装を行っていた。
+read で実装を行うと、ファイル読み込みを行ってから Task が並列に動く。
+しかし、ファイルの大きさが大きくなると、read の時間が大きくなってしまう。
+読み込んでいる間 Task が走らないので、CPU の待ち時間が増えてオーバーヘッドとなる。
+
 mmap とは、sys/mman.h に含まれている関数で、ファイルの読み込み等に使用される関数である。
 
 \begin{tiny}
@@ -40,13 +45,13 @@
 
 mmap でファイルを読み込むタイミングは、mmap 関数が呼ばれたときではなく、mmap した領域に対して何らかのアクセスをしたときに初めてファイルが読み込まれる。
 
-図\ref{fig:mmap}では、読み込んだファイルを分割して、それらの領域に何らかの処理を加えるときの図である。この何らかの処理のことを Task と呼ぶ。
+図\ref{fig:mmap}では、読み込んだファイルを分割して、それらの領域に何らかの処理を加えるときの図である。
 
 1個目の Task が実行されるときに初めてそれらの領域にファイルが読み込まれ、その後何らかの処理が行われ、そして Task 2 も同様に読み込みを行ってから処理が行われる。
 これら Task は並列に実行されるべきであるが、ファイル読み込みの I/O 部分がネックとなり、本来並列実行される Task が読み込み待ちを起こしてしまう恐れがある。
 さらに、読み込みが OS 依存となるために環境によって左右されやすく、プログラムの書き手が読み込みに関して制御しにくい。
 
-それらを解決するためには、ファイル読み込みと Task を分離し、ファイルの読み込みも制御しやすくでき、なおかつ高速で動くのではないかと考えた。
+それらを解決するためには、ファイル読み込みと Task を分離し、ファイルの読み込みも制御できるようになれば高速で動くのではないかと考えた。
 
 
 \begin{figure}[htbp]
@@ -63,7 +68,7 @@
 Blocked Read とは、読み込みの Task と、それらに対して何らかの処理を行う Task を切り離すための実装方法である。それを実現するため、pread 関数にて実装した。
 pread 関数は、unistd.h に含まれている UNIX 専用の関数である。
 ファイルディスクリプタで指定したファイルの先頭から offset 分ずれた場所を基準として、その基準から count バイトを読み込み、それを buf に格納する。
-(表\ref{table:pread})
+(表4)
 
 \begin{tiny}
   \begin{table}[ht]
@@ -88,11 +93,10 @@
   \end{table}
 \end{tiny}
 
-mmap での実装との違いは、ファイルの読み込みがどのタイミングで起こるかである。
-mmap で実装したときは、Task 1つ 1つが読み込みを行ってから処理を行う。
-それに対して、Blocked Readは、読み込み専用の Read Task と、処理専用の Task を別々に生成する。
-Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行う。
-分割して読み込み終わったら、それぞれの Task が実行される。
+従来の実装との違いは、ファイルの読み込みがどのタイミングで起こるかである。
+Blocked Readは、読み込み専用の Read Task と、処理専用の Task を別々に生成する。
+Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行ってから読み込む。
+分割して読み込み終わったら、読み込んだ範囲内の Task が実行される。
 %(図\ref{fig:block})
 (図4)
 Read Task が生成されて、その後 Task の生成となるので、Read Task は常に走っている必要がある。
@@ -108,10 +112,10 @@
 この図では、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$ となる。
+Task Block 1つ当たりがの Task 量を $n$ とおく。Task 1つ当たりの読み込む量を $L$ とすると、Task Block 1つ当たりの読み込む量は $L \times n$ となる。
 
 Task Block が Blocked Read よりも先走ってしまうと、
-まだ読み込まれていない領域に対して何らかの処理を行ってしまうので、正しい結果が返ってこなくなってしまう。
+まだ読み込まれていない領域に対して処理を行ってしまうので、正しい結果が返ってこなくなってしまう。
 それを防止するために、Blocked Read が読み込み終わってから Task Block が起動されるように Cerium の API である wait\_for にて依存関係を設定する。
 (図\ref{fig:block})
 
@@ -150,7 +154,7 @@
 set\_param(1) 、 set\_param(2) にて Blocked Read Task 単体で読み込むファイルの範囲の先頭と末尾のポジションを設定する。
 
 なお、run\_tasks 内部で、処理を行う task を生成している。
-その内部で、task が生成されるたびに task\_num をインクリメントを行っている。
+その内部で、task が生成されるたびに task\_num のインクリメントを行っている。
 
 Blocked Read Task の記述は以下のようになる。
 
@@ -176,29 +180,7 @@
 
 Blocked Read Task の生成部分で設定したパラメータをそれぞれ受け取る。ファイル読み込みの先頭と末尾のポジションが渡されているので、どれだけファイルを読みこめばいいか求めることができる。
 
-それらのパラメータを使用して、pread 関数に渡すことでファイル読み込みを実現している。
-
-\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}
+それらのパラメータを使用して、pread 関数に渡すことで Blocked Read によるファイル読み込みを実現している。
 
 \subsection{I/O 専用 thread の実装}
 
@@ -215,7 +197,7 @@
 \label{fig:speany}
 \end{figure}
 
-この問題を解決するため、Cerium Task Manager に新しく I/O 専用の thread 、 IO\_0 の追加を行った。
+この問題を解決するため、Task Manager に新しく I/O 専用の thread 、 IO\_0 の追加を行った。
 
 %(図\ref{fig:addio0})
 %%この問題を解決するために、Task Manager に IO\_0という新しいデバイス設定を追加した。

Binary file paper/sigos.pdf has changed

--- a/paper/sigos.tex	Sun Apr 20 16:25:41 2014 +0900
+++ b/paper/sigos.tex	Sun Apr 20 22:21:07 2014 +0900
@@ -64,7 +64,7 @@
 
 \input{introduction}   % 研究目的
 \input{cerium}         % Cerium
-\input{example}     % 開発過程
+% \input{example}     % 開発過程
 \input{io}       % many core におけるデータ並列
 \input{benchmark}       % sort
 \input{conclusion}     % まとめ