# HG changeset patch # User Yuhi TOMARI # Date 1423544813 -32400 # Node ID d7cf4a51597f0f5aac27579dc5c5651f9a190471 # Parent 71257663515404038341840f303acdbd9bbc0805 parallel IO diff -r 712576635154 -r d7cf4a51597f paper/chapter6.tex --- 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 を高くする必要があるという知見を得られた。 diff -r 712576635154 -r d7cf4a51597f paper/figures/.DS_Store Binary file paper/figures/.DS_Store has changed diff -r 712576635154 -r d7cf4a51597f paper/master_paper.aux --- 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}} diff -r 712576635154 -r d7cf4a51597f paper/master_paper.dvi Binary file paper/master_paper.dvi has changed diff -r 712576635154 -r d7cf4a51597f paper/master_paper.lof --- 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@ } diff -r 712576635154 -r d7cf4a51597f paper/master_paper.log --- 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) [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) + +[25] +File: images/emblem-bitmap.eps Graphic file (type 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) + [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) + [30] +File: images/emblem-bitmap.eps Graphic file (type 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). diff -r 712576635154 -r d7cf4a51597f paper/master_paper.lot --- 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@ } diff -r 712576635154 -r d7cf4a51597f paper/master_paper.pdf Binary file paper/master_paper.pdf has changed diff -r 712576635154 -r d7cf4a51597f paper/master_paper.toc --- 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}