Mercurial > hg > Papers > 2014 > masakoha-thesis > final
changeset 69:3988365f6f03
add eclbkbox.sty
author | Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 25 Feb 2014 05:08:39 +0900 |
parents | 9c5f2ffbeb4e |
children | 286a8f57becf |
files | paper/chapter2.tex paper/chapter3.tex paper/chapter4.tex paper/chapter6.tex paper/eclbkbox.sty paper/thesis-paper.pdf paper/thesis-paper.tex preliminary/final-thesis.tex |
diffstat | 8 files changed, 131 insertions(+), 9 deletions(-) [+] |
line wrap: on
line diff
--- a/paper/chapter2.tex Mon Feb 24 19:41:40 2014 +0900 +++ b/paper/chapter2.tex Tue Feb 25 05:08:39 2014 +0900 @@ -24,7 +24,8 @@ input Data で格納して 2 つの数を乗算し、output data に格納する multiply という例題がある。 その例題の Task 生成部分を以下に示す。 - +\\ +\begin{breakbox} \begin{verbatim} multi_init(TaskManager *manager) { @@ -38,11 +39,11 @@ multiply->spawn(); } \end{verbatim} +\end{breakbox} \begin{tiny} \begin{table}[ht] \begin{center} - \caption{Task 生成における API} \label{table:create_taskAPI} \small \begin{tabular}[t]{c|l} @@ -60,11 +61,17 @@ spawn & 生成した Task を TaskList に set \\ \hline \end{tabular} + \caption{Task 生成における API} \end{center} \end{table} \end{tiny} +\newpage + Task の記述は以下のようになる。 +\\ + +\begin{breakbox} \begin{verbatim} static int run(SchedTask *s,void *rbuf, void *wbuf) @@ -80,6 +87,7 @@ return 0; } \end{verbatim} +\end{breakbox} \begin{tiny} \begin{table}[ht]
--- a/paper/chapter3.tex Mon Feb 24 19:41:40 2014 +0900 +++ b/paper/chapter3.tex Tue Feb 25 05:08:39 2014 +0900 @@ -207,8 +207,6 @@ \fi -\newpage - この例題ではファイルを読み込んで一定の大きさでファイルを分割する。分割したものにそれぞれ Boyer-Moore String Search を行う。 それぞれの結果は pattern が含まれている個数が返ってくるので、最後に集計をして個数を表示する。このような一つ一つの処理を Task と呼ぶ。 @@ -223,6 +221,8 @@ \label{fig:includeiotask} \end{figure} +\newpage + ファイルを分割したときに、分割される部分で pattern が含まれる場合が存在する。 その場合は、本来の読み込み部分の text の長さ $L$ に加えて、pattern の長さ $s$ だけ多く読みこむように設計することでこの問題は解決できる。 しかし、1 つの Search Task の text の長さが $L+s$ の場合だと、pattern が Search Task 1 に含まれ、Search Task 2 にも含まれてしまう。 @@ -246,6 +246,7 @@ \label{fig:includeiotask} \end{figure} +\newpage 力任せ法と Boyer-Moore String Search を比較してみた。以下に実験環境と結果を示す。(表\ref{table:search}) \begin{itemize} \item Mac OS X 10.9.1
--- a/paper/chapter4.tex Mon Feb 24 19:41:40 2014 +0900 +++ b/paper/chapter4.tex Tue Feb 25 05:08:39 2014 +0900 @@ -10,6 +10,8 @@ \caption{map reduce image} \label{fig:mmap} \end{figure} +\newpage + \section{mmap での実装の問題点} mmap とは、sys/mman.h に含まれている関数で、ファイルの読み込み等に使用される関数である。 ファイルディスクリプタで指定したファイルを offset から len バイトの範囲を読み込む。 @@ -60,11 +62,12 @@ \caption{mmap image} \label{fig:mmap} \end{figure} - +\newpage \section{Bloked Read の設計と実装} Blocked Read とは、読み込みの Task と、それに対する何らかの処理の Task を切り離すための実装方法で、pread 関数にて実装した。 pread 関数は、unistd.h に含まれているので、UNIX 専用の関数である。ファイルディスクリプタで指定したファイルの先頭 から -offset 分ずれた場所を基準として、その基準から count バイトを読み込み、それを buf に格納する。\ref{table:pread} +offset 分ずれた場所を基準として、その基準から count バイトを読み込み、それを buf に格納する。 +\ref{table:pread} \begin{tiny} \begin{table}[ht] @@ -124,7 +127,7 @@ \label{fig:block} \end{figure} - +\newpage \section{I/O 専用 thread の実装} Cerium Task Manager では、各種 Task にデバイスを設定することができる。デバイスとは、GPU や CPU であり、GPUを利用するときは GPU\_ANY、CPU を利用するときは SPE\_ANYと設定することによってデバイスを利用できる。
--- a/paper/chapter6.tex Mon Feb 24 19:41:40 2014 +0900 +++ b/paper/chapter6.tex Tue Feb 25 05:08:39 2014 +0900 @@ -13,8 +13,34 @@ そのようなことが起こらないように、Cerium Task Manager に新しいデバイスの設定 IO\_0 というタイプを追加した。このデバイスは、他のデバイス設定よりも priority を高く設定しているので、このタイプ以外で起動する Task に割り込まれることが起こらなくなる。 これらを実装した結果、本研究では mmap で実装したときよりも 36 \% の動作改善が見られた。 +本研究を通して、I/O を含む Task の並列化の問題において、I/O の動作を改善する余地があると考える。 \section{今後の課題} \subsection{実メモリ以上のファイルの取り扱い} +本研究での実験では、実メモリ以上のファイルを取り扱ってはいない。 +Blocked Read のメリットとして、実メモリ以上のファイルサイズを取り扱うことができることである。 +実メモリ以上のファイルを読み込む際には一旦分割して読み込み、その読み込み領域を担当する Task が終了したら、そのメモリ領域を解放する。 +そして、その解放した部分に読み込みを行うことで、メモリの節約にも利用できる。 + +現段階での実装は、Task Manager 側で予めテキストファイルの大きさをメモリに確保して、その部分に読み込んだファイルを格納していくようになっている。 +この実装方法ではメモリ以上のファイルを読み込めないので、この問題を解決する必要がある。 + \subsection{Blocked Read で読み込んだファイルがキャッシュに残らない} +本来読み込みを行ったファイルは、一度プログラムを実行したあとでもキャッシュとしてメモリ上にテキストがそのまま残っている。 +キャッシュとは、使用頻度の高いデータを高速なデバイスに蓄えておくことによって読み込みのオーバーヘッドを少なくするための機能である。 + +ハードディスクはメモリと比較すると読み込みが遅いので、ハードディスクからファイル読み込みを行うと、読み込みが速いメモリのほうに格納される。 +読み込んだファイルが再利用されるとき、ハードディスクからメモリに格納するという時間が無くなるので、2回目以降の実行結果は速くなる。 + +mmap で実装を行うと、同じファイルに対して複数回検索を行うときに 2回目以降のプログラムの処理は速くなる。 +本研究では mmap で 10GB のファイルに対して文字列検索を行うと約150秒かかるが、2回目以降の実行速度に関しては、約7秒でプログラムが終了する。 + +Blocked Read も 2回目以降の実行速度は mmap と同様に速くなるのだが、ある一定のファイルサイズを越えてしまうとキャッシュが無効となってしまう。 +10GB のファイルではそのようなことが発生することは確認しているが、どれくらいの大きさからキャッシュが無効になるのか不明である。 + +キャッシュが無効になってしまうと、Blocked Read で実装した文字列検索は複数回実行するときに不利となる。 +なぜこのようなことが起こるのか調査して、それが起こらないように実装していきたい。 + \subsection{Blocked Read を Cerium API化} +現段階での Blocked Read の実装は、複雑な書き方で実装しなければならない。 +この実装を Cerium の API に落としこむことによって、簡単に実装できるようにしたい。
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/eclbkbox.sty Tue Feb 25 05:08:39 2014 +0900 @@ -0,0 +1,82 @@ +% eclbkbox.sty by Hideki Isozaki, 1992 +% Date: May 28, 1993 + +\newbox\bk@bxb +\newbox\bk@bxa +\newif\if@bkcont +\newif\ifbkcount +\newcount\bk@lcnt + +\def\breakboxskip{2pt} +\def\breakboxparindent{1.8em} + +\def\breakbox{\vskip\breakboxskip\relax +\setbox\bk@bxb\vbox\bgroup +\advance\linewidth -2\fboxrule +\advance\linewidth -2\fboxsep +\hsize\linewidth\@parboxrestore +\parindent\breakboxparindent\relax} + +% \@tempdimb: amount of vertical skip +% between the first line (\bk@bxa) and the rest (\bk@bxb) +\def\bk@split{% +\@tempdimb\ht\bk@bxb % height of original box +\advance\@tempdimb\dp\bk@bxb +\setbox\bk@bxa\vsplit\bk@bxb to\z@ % split it +\setbox\bk@bxa\vbox{\unvbox\bk@bxa}% recover height & depth of \bk@bxa +\setbox\@tempboxa\vbox{\copy\bk@bxa\copy\bk@bxb}% naive concatenation +\advance\@tempdimb-\ht\@tempboxa +\advance\@tempdimb-\dp\@tempboxa}% gap between two boxes + + +% \@tempdima: height of the first line (\bk@bxa) + fboxsep +\def\bk@addfsepht{% + \setbox\bk@bxa\vbox{\vskip\fboxsep\box\bk@bxa}} + +\def\bk@addskipht{% + \setbox\bk@bxa\vbox{\vskip\@tempdimb\box\bk@bxa}} + +% \@tempdima: depth of the first line (\bk@bxa) + fboxsep +\def\bk@addfsepdp{% + \@tempdima\dp\bk@bxa + \advance\@tempdima\fboxsep + \dp\bk@bxa\@tempdima} + +% \@tempdima: depth of the first line (\bk@bxa) + vertical skip +\def\bk@addskipdp{% + \@tempdima\dp\bk@bxa + \advance\@tempdima\@tempdimb + \dp\bk@bxa\@tempdima} + +\def\bk@line{% + \hbox to \linewidth{\ifbkcount\smash{\llap{\the\bk@lcnt\ }}\fi + \vrule \@width\fboxrule\hskip\fboxsep + \box\bk@bxa\hfil + \hskip\fboxsep\vrule \@width\fboxrule}} + +\def\endbreakbox{\egroup +\ifhmode\par\fi{\noindent\bk@lcnt\@ne +\@bkconttrue\baselineskip\z@\lineskiplimit\z@ +\lineskip\z@\vfuzz\maxdimen +\bk@split\bk@addfsepht\bk@addskipdp +\ifvoid\bk@bxb % Only one line +\def\bk@fstln{\bk@addfsepdp +\vbox{\hrule\@height\fboxrule\bk@line\hrule\@height\fboxrule}}% +\else % More than one line +\def\bk@fstln{\vbox{\hrule\@height\fboxrule\bk@line}\hfil +\advance\bk@lcnt\@ne +\loop + \bk@split\bk@addskipdp\leavevmode +\ifvoid\bk@bxb % The last line + \@bkcontfalse\bk@addfsepdp + \vtop{\bk@line\hrule\@height\fboxrule}% +\else % 2,...,(n-1) + \bk@line +\fi + \hfil\advance\bk@lcnt\@ne +\if@bkcont\repeat}% +\fi +\leavevmode\bk@fstln\par}\vskip\breakboxskip\relax} + +\bkcountfalse +
--- a/paper/thesis-paper.tex Mon Feb 24 19:41:40 2014 +0900 +++ b/paper/thesis-paper.tex Tue Feb 25 05:08:39 2014 +0900 @@ -1,5 +1,6 @@ \documentclass[a4j,12pt]{jreport} \usepackage[dvipdfm]{graphicx} +\usepackage{eclbkbox} \usepackage{mythesis} \usepackage{multirow} \usepackage{here}
--- a/preliminary/final-thesis.tex Mon Feb 24 19:41:40 2014 +0900 +++ b/preliminary/final-thesis.tex Tue Feb 25 05:08:39 2014 +0900 @@ -151,8 +151,9 @@ \section{まとめ} mmap で I/O を含む Task を実装するとき、mmap した領域に対して何らかの処理が加わった時にしか読み込みが行わないので、それぞれの Task に読み込みを任せてしまうことになる。 -それを解決する方法として、Blocked Read と Task を並列に行う実装を行った。また、Blocked Read は、他の Task に割り込まれないように改善した。 -その結果、35 \% の実行速度の改善が見られた。 +それを解決する方法として、Blocked Read と Task を並列に行う実装を行った。 +また、Blocked Read が、他の Task に割り込まれないように改善した結果、35 \% の実行速度の改善が見られた。 +本研究より、I/O を含む Task は、チューニング次第で更に改善する余地があると考える。 \thispagestyle{fancy}