--- 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 を高くする必要があるという知見を得られた。

Binary file paper/figures/.DS_Store has changed

--- a/paper/master_paper.aux	Mon Feb 09 11:32:28 2015 +0900
+++ b/paper/master_paper.aux	Tue Feb 10 14:06:53 2015 +0900
@@ -77,29 +77,51 @@
 \@writefile{toc}{\contentsline {chapter}{\numberline {第7章}並列処理向けI/O}{24}}
 \@writefile{lof}{\addvspace {10\p@ }}
 \@writefile{lot}{\addvspace {10\p@ }}
-\@writefile{toc}{\contentsline {section}{\numberline {7.1}新たに実装したI/Oの機構}{24}}
-\@writefile{toc}{\contentsline {chapter}{\numberline {第8章}Memory Allocator}{25}}
-\@writefile{lof}{\addvspace {10\p@ }}
-\@writefile{lot}{\addvspace {10\p@ }}
-\@writefile{toc}{\contentsline {section}{\numberline {8.1}現状のMemory Allocator}{25}}
-\@writefile{toc}{\contentsline {section}{\numberline {8.2}新しいMemory Allocator}{25}}
-\@writefile{toc}{\contentsline {chapter}{\numberline {第9章}ベンチマーク}{26}}
+\@writefile{toc}{\contentsline {section}{\numberline {7.1}mmap}{24}}
+\@writefile{lof}{\contentsline {figure}{\numberline {7.1}{\ignorespaces mmap の Model}}{24}}
+\newlabel{fig:mmap}{{7.1}{24}}
+\@writefile{toc}{\contentsline {section}{\numberline {7.2}Blocked Read による I/O の並列化}{25}}
+\@writefile{lof}{\contentsline {figure}{\numberline {7.2}{\ignorespaces BlockedRead による WordCount}}{25}}
+\newlabel{fig:blockedread}{{7.2}{25}}
+\newlabel{src:blockedread_create}{{7.1}{26}}
+\@writefile{lol}{\contentsline {lstlisting}{\numberline {7.1}BlockedRead を行う Task の生成}{26}}
+\newlabel{src:blockedread_task}{{7.2}{26}}
+\@writefile{lol}{\contentsline {lstlisting}{\numberline {7.2}BlockedRead Task}{26}}
+\@writefile{toc}{\contentsline {section}{\numberline {7.3}I/O 専用 Thread の実装}{27}}
+\@writefile{lof}{\contentsline {figure}{\numberline {7.3}{\ignorespaces BlockedRead と Task を同じ thread で動かした場合}}{27}}
+\newlabel{fig:spe_any_blockedread}{{7.3}{27}}
+\@writefile{lof}{\contentsline {figure}{\numberline {7.4}{\ignorespaces IO Thread による BlockedRead}}{27}}
+\newlabel{fig:iothread__blockedread}{{7.4}{27}}
+\@writefile{toc}{\contentsline {chapter}{\numberline {第8章}Memory Allocator}{28}}
 \@writefile{lof}{\addvspace {10\p@ }}
 \@writefile{lot}{\addvspace {10\p@ }}
-\@writefile{lot}{\contentsline {table}{\numberline {9.1}{\ignorespaces Ceriumを実行する実験環境1}}{26}}
-\newlabel{tab:firefly_spec}{{9.1}{26}}
-\@writefile{lot}{\contentsline {table}{\numberline {9.2}{\ignorespaces Ceriumを実行する実験環境2}}{26}}
-\newlabel{tab:dragonfly_spec}{{9.2}{26}}
-\@writefile{toc}{\contentsline {chapter}{\numberline {第10章}結論}{27}}
+\@writefile{toc}{\contentsline {section}{\numberline {8.1}現状のMemory Allocator}{28}}
+\@writefile{toc}{\contentsline {section}{\numberline {8.2}新しいMemory Allocator}{28}}
+\@writefile{toc}{\contentsline {chapter}{\numberline {第9章}ベンチマーク}{29}}
 \@writefile{lof}{\addvspace {10\p@ }}
 \@writefile{lot}{\addvspace {10\p@ }}
-\newlabel{chapter:conclusion}{{10}{27}}
-\@writefile{toc}{\contentsline {section}{\numberline {10.1}まとめ}{27}}
-\@writefile{toc}{\contentsline {section}{\numberline {10.2}今後の課題}{27}}
+\@writefile{toc}{\contentsline {section}{\numberline {9.1}実験環境}{29}}
+\@writefile{lot}{\contentsline {table}{\numberline {9.1}{\ignorespaces Ceriumを実行する実験環境1}}{29}}
+\newlabel{tab:firefly_spec}{{9.1}{29}}
+\@writefile{lot}{\contentsline {table}{\numberline {9.2}{\ignorespaces Ceriumを実行する実験環境2}}{29}}
+\newlabel{tab:dragonfly_spec}{{9.2}{29}}
+\@writefile{toc}{\contentsline {section}{\numberline {9.2}マルチコア}{30}}
+\@writefile{lof}{\contentsline {figure}{\numberline {9.1}{\ignorespaces マルチコア CPU における Sort}}{30}}
+\newlabel{fig:sort_on_multicore}{{9.1}{30}}
+\@writefile{toc}{\contentsline {section}{\numberline {9.3}GPGPU}{30}}
+\@writefile{toc}{\contentsline {section}{\numberline {9.4}並列 I/O}{30}}
+\@writefile{lof}{\contentsline {figure}{\numberline {9.2}{\ignorespaces マルチコア CPU における WordCount}}{31}}
+\newlabel{fig:wordcount_on_multicore}{{9.2}{31}}
+\@writefile{toc}{\contentsline {chapter}{\numberline {第10章}結論}{32}}
+\@writefile{lof}{\addvspace {10\p@ }}
+\@writefile{lot}{\addvspace {10\p@ }}
+\newlabel{chapter:conclusion}{{10}{32}}
+\@writefile{toc}{\contentsline {section}{\numberline {10.1}まとめ}{32}}
+\@writefile{toc}{\contentsline {section}{\numberline {10.2}今後の課題}{32}}
 \citation{*}
 \bibstyle{junsrt}
 \bibdata{master_paper}
-\@writefile{toc}{\contentsline {chapter}{謝辞}{28}}
+\@writefile{toc}{\contentsline {chapter}{謝辞}{33}}
 \bibcite{msgpack:2013}{1}
 \bibcite{nobuyasu:2013a}{2}
 \bibcite{shoshi:2011a}{3}
@@ -110,5 +132,5 @@
 \bibcite{dynamo}{8}
 \bibcite{deos2013}{9}
 \bibcite{d_add2013}{10}
-\@writefile{toc}{\contentsline {chapter}{参考文献}{29}}
-\@writefile{toc}{\contentsline {chapter}{発表文献}{30}}
+\@writefile{toc}{\contentsline {chapter}{参考文献}{34}}
+\@writefile{toc}{\contentsline {chapter}{発表文献}{35}}

Binary file paper/master_paper.dvi has changed

--- a/paper/master_paper.lof	Mon Feb 09 11:32:28 2015 +0900
+++ b/paper/master_paper.lof	Tue Feb 10 14:06:53 2015 +0900
@@ -14,6 +14,12 @@
 \addvspace {10\p@ }
 \addvspace {10\p@ }
 \addvspace {10\p@ }
+\contentsline {figure}{\numberline {7.1}{\ignorespaces mmap の Model}}{24}
+\contentsline {figure}{\numberline {7.2}{\ignorespaces BlockedRead による WordCount}}{25}
+\contentsline {figure}{\numberline {7.3}{\ignorespaces BlockedRead と Task を同じ thread で動かした場合}}{27}
+\contentsline {figure}{\numberline {7.4}{\ignorespaces IO Thread による BlockedRead}}{27}
 \addvspace {10\p@ }
 \addvspace {10\p@ }
+\contentsline {figure}{\numberline {9.1}{\ignorespaces マルチコア CPU における Sort}}{30}
+\contentsline {figure}{\numberline {9.2}{\ignorespaces マルチコア CPU における WordCount}}{31}
 \addvspace {10\p@ }

--- a/paper/master_paper.log	Mon Feb 09 11:32:28 2015 +0900
+++ b/paper/master_paper.log	Tue Feb 10 14:06:53 2015 +0900
@@ -1,4 +1,4 @@
-This is e-pTeX, Version 3.1415926-p3.4-110825-2.6 (utf8.euc) (TeX Live 2013) (format=platex 2013.5.30)  9 FEB 2015 11:32
+This is e-pTeX, Version 3.1415926-p3.4-110825-2.6 (utf8.euc) (TeX Live 2013) (format=platex 2013.5.30)  10 FEB 2015 12:21
 entering extended mode
  \write18 enabled.
  %&-line parsing enabled.
@@ -377,21 +377,57 @@
 File: images/emblem-bitmap.eps Graphic file (type eps)
  <images/emblem-bitmap.eps> [23]
 第 7 章(24ページ)
-) (./chapter7.tex [24
-
-]
-第 8 章(25ページ)
-) (./chapter8.tex [25
+File: ./images/mmap.pdf Graphic file (type pdf)
+<./images/mmap.pdf> [24
 
 ]
-第 9 章(26ページ)
-) (./conclusion.tex [26
+File: ./images/blockedread.pdf Graphic file (type pdf)
+ <./images/blockedread.pdf>
+File: images/emblem-bitmap.eps Graphic file (type eps)
+ <images/emblem-bitmap.eps>
+[25]
+File: images/emblem-bitmap.eps Graphic file (type eps)
+ <images/emblem-bitmap.eps> [26]
+File: ./images/speblockedread.pdf Graphic file (type pdf)
+ <./images/speblockedread.pdf>
+Overfull \hbox (2.16278pt too wide) in paragraph at lines 118--119
+ [] 
+ []
+
+
+LaTeX Warning: Reference `fig:iothread_blockedread' on page 27 undefined on inp
+ut line 128.
+
+File: ./images/iothread.pdf Graphic file (type pdf)
+<./images/iothread.pdf>
+Overfull \hbox (47.1306pt too wide) in paragraph at lines 132--133
+ [] 
+ []
+
+) (./chapter7.tex
+File: images/emblem-bitmap.eps Graphic file (type eps)
+ <images/emblem-bitmap.eps> [27]
+第 8 章(28ページ)
+) (./chapter8.tex [28
 
 ]
-第 10 章(27ページ)
-) (./thanx.tex [27
+第 9 章(29ページ)
+File: ./figures/multicore/sort_.pdf Graphic file (type pdf)
+<./figures/multicore/sort_.pdf> [29
 
-]) (./master_paper.bbl [28
+]
+File: ./figures/multicore/word_count_.pdf Graphic file (type pdf)
+ <./figures/multicore/word_count_.pdf>)
+(./conclusion.tex
+File: images/emblem-bitmap.eps Graphic file (type eps)
+ <images/emblem-bitmap.eps> [30]
+File: images/emblem-bitmap.eps Graphic file (type eps)
+ <images/emblem-bitmap.eps>
+[31]
+第 10 章(32ページ)
+) (./thanx.tex [32
+
+]) (./master_paper.bbl [33
 
 ]
 
@@ -402,24 +438,27 @@
 LaTeX Font Warning: Font shape `JY1/gt/m/it' undefined
 (Font)              using `JY1/gt/m/n' instead on input line 25.
 
-) (./appendix.tex [29
+) (./appendix.tex [34
 
 ])
 No file master_paper.ind.
-[30
+[35
 
 ] (./master_paper.aux)
 
 LaTeX Font Warning: Some font shapes were not available, defaults substituted.
 
+
+LaTeX Warning: There were undefined references.
+
  ) 
 Here is how much of TeX's memory you used:
- 2492 strings out of 494008
- 35051 string characters out of 6154472
- 179731 words of memory out of 5000000
- 5871 multiletter control sequences out of 15000+600000
+ 2530 strings out of 494008
+ 35697 string characters out of 6154472
+ 189731 words of memory out of 5000000
+ 5902 multiletter control sequences out of 15000+600000
  18570 words of font info for 72 fonts, out of 8000000 for 9000
  745 hyphenation exceptions out of 8191
- 33i,12n,40p,301b,1252s stack positions out of 5000i,500n,10000p,200000b,80000s
+ 30i,12n,40p,301b,1888s stack positions out of 5000i,500n,10000p,200000b,80000s
 
-Output written on master_paper.dvi (37 pages, 91888 bytes).
+Output written on master_paper.dvi (42 pages, 113092 bytes).

--- a/paper/master_paper.lot	Mon Feb 09 11:32:28 2015 +0900
+++ b/paper/master_paper.lot	Tue Feb 10 14:06:53 2015 +0900
@@ -11,6 +11,6 @@
 \addvspace {10\p@ }
 \addvspace {10\p@ }
 \addvspace {10\p@ }
-\contentsline {table}{\numberline {9.1}{\ignorespaces Ceriumを実行する実験環境1}}{26}
-\contentsline {table}{\numberline {9.2}{\ignorespaces Ceriumを実行する実験環境2}}{26}
+\contentsline {table}{\numberline {9.1}{\ignorespaces Ceriumを実行する実験環境1}}{29}
+\contentsline {table}{\numberline {9.2}{\ignorespaces Ceriumを実行する実験環境2}}{29}
 \addvspace {10\p@ }

Binary file paper/master_paper.pdf has changed

--- a/paper/master_paper.toc	Mon Feb 09 11:32:28 2015 +0900
+++ b/paper/master_paper.toc	Tue Feb 10 14:06:53 2015 +0900
@@ -23,14 +23,20 @@
 \contentsline {section}{\numberline {6.1}OpenCL および CUDA による実装}{20}
 \contentsline {section}{\numberline {6.2}データ並列}{21}
 \contentsline {chapter}{\numberline {第7章}並列処理向けI/O}{24}
-\contentsline {section}{\numberline {7.1}新たに実装したI/Oの機構}{24}
-\contentsline {chapter}{\numberline {第8章}Memory Allocator}{25}
-\contentsline {section}{\numberline {8.1}現状のMemory Allocator}{25}
-\contentsline {section}{\numberline {8.2}新しいMemory Allocator}{25}
-\contentsline {chapter}{\numberline {第9章}ベンチマーク}{26}
-\contentsline {chapter}{\numberline {第10章}結論}{27}
-\contentsline {section}{\numberline {10.1}まとめ}{27}
-\contentsline {section}{\numberline {10.2}今後の課題}{27}
-\contentsline {chapter}{謝辞}{28}
-\contentsline {chapter}{参考文献}{29}
-\contentsline {chapter}{発表文献}{30}
+\contentsline {section}{\numberline {7.1}mmap}{24}
+\contentsline {section}{\numberline {7.2}Blocked Read による I/O の並列化}{25}
+\contentsline {section}{\numberline {7.3}I/O 専用 Thread の実装}{27}
+\contentsline {chapter}{\numberline {第8章}Memory Allocator}{28}
+\contentsline {section}{\numberline {8.1}現状のMemory Allocator}{28}
+\contentsline {section}{\numberline {8.2}新しいMemory Allocator}{28}
+\contentsline {chapter}{\numberline {第9章}ベンチマーク}{29}
+\contentsline {section}{\numberline {9.1}実験環境}{29}
+\contentsline {section}{\numberline {9.2}マルチコア}{30}
+\contentsline {section}{\numberline {9.3}GPGPU}{30}
+\contentsline {section}{\numberline {9.4}並列 I/O}{30}
+\contentsline {chapter}{\numberline {第10章}結論}{32}
+\contentsline {section}{\numberline {10.1}まとめ}{32}
+\contentsline {section}{\numberline {10.2}今後の課題}{32}
+\contentsline {chapter}{謝辞}{33}
+\contentsline {chapter}{参考文献}{34}
+\contentsline {chapter}{発表文献}{35}