Mercurial > hg > Papers > 2014 > masakoha-thesis > final

changeset 68:9c5f2ffbeb4e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix preliminary
author Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
date Mon, 24 Feb 2014 19:41:40 +0900
parents 2817add546be
children 3988365f6f03
files paper/chapter3.tex paper/chapter4.tex paper/fig/blockread.graffle paper/thesis-paper.pdf preliminary/final-thesis.pdf preliminary/final-thesis.tex
diffstat 6 files changed, 76 insertions(+), 67 deletions(-) [+]
line wrap: on
line diff
--- a/paper/chapter3.tex	Mon Feb 24 14:18:43 2014 +0900
+++ b/paper/chapter3.tex	Mon Feb 24 19:41:40 2014 +0900
@@ -27,7 +27,8 @@
   \end{table}
 \end{tiny}
 
-1GB のテキストファイルを分割して読み込み終わるまでの時間を表\ref{table:preaddata}に示す。
+ハードディスクに保存されている 10GB のテキストファイルを分割して読み込み終わるまでの時間を表\ref{table:preaddata}に示す。
+分割サイズとは、1回の読み込み量である。
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
@@ -37,11 +38,9 @@
         \hline
         分割サイズ & 読み込み速度(s)\\
         \hline
-        16KB & XX.XXX \\
+        16KB & 391.7 \\
         \hline
-        16MB & XX.XXX \\
-        \hline
-        256MB & XX.XXX \\
+        16MB & 123.6 \\
         \hline
       \end{tabular}
       \caption{file read の実行結果}
@@ -50,7 +49,6 @@
 \end{tiny}
 
 分割サイズを大きくすると、pread の呼ばれる回数が少なくなるので読み込むことが速くなる。
-しかし、ある一定以上の大きさになると I/O ネックが勝ってしまい、読み込み速度が変わらない。
 
 \newpage
 
@@ -69,7 +67,7 @@
 
 \begin{figure}[htbp]
 \begin{center}
-\includegraphics[width=0.5\textwidth]{fig/bruteforth.pdf}
+\includegraphics[width=0.7\textwidth]{fig/bruteforth.pdf}
 \end{center}
 \caption{力まかせ法}
 \label{fig:bruteforth}
@@ -84,8 +82,6 @@
 pattern の末尾から比較していくことである。そして不一致が起こった場合は、
 その不一致が起こった text の文字で再度比較する場所が決まる。
 
-
-\newpage
 まず始めに、比較する場所を着目点とおく。図\ref{fig:bmsearchthink}の場合、
 最初に比較する patternの末尾 と、それに対応する text を着目点とする。
 (a)ではその着目点で不一致が起こっているので、それ以上比較しなくてもよいことがわかる。
@@ -95,12 +91,14 @@
 
 \begin{figure}[htbp]
 \begin{center}
-\includegraphics[width=0.5\textwidth]{fig/bmsearchthink.pdf}
+\includegraphics[width=0.7\textwidth]{fig/bmsearchthink.pdf}
 \end{center}
 \caption{pattern に含まれていない文字で不一致になった場合}
 \label{fig:bmsearchthink}
 \end{figure}
 
+\newpage
+
 次に、pattern に含まれている文字で不一致になった場合を紹介する。
 図\ref{fig:bmsearchthink}と同様に、文字を比較していく。
 図\ref{fig:bmsearchinclude}(a)のときに不一致が起こる。
@@ -114,7 +112,7 @@
 
 \begin{figure}[htbp]
 \begin{center}
-\includegraphics[width=0.5\textwidth]{fig/bmsearchinlucde.pdf}
+\includegraphics[width=0.7\textwidth]{fig/bmsearchinlucde.pdf}
 \end{center}
 \caption{pattern に含まれている文字で不一致になった場合}
 \label{fig:bmsearchinclude}
@@ -131,7 +129,7 @@
 
 \begin{figure}[htbp]
 \begin{center}
-\includegraphics[width=0.5\textwidth]{fig/bmsearchsame.pdf}
+\includegraphics[width=0.7\textwidth]{fig/bmsearchsame.pdf}
 \end{center}
 \caption{pattern に同じ文字が複数入り、その文字で不一致になった場合}
 \label{fig:bmsearchsame}
@@ -151,12 +149,13 @@
 
 \begin{figure}[htbp]
 \begin{center}
-\includegraphics[width=0.5\textwidth]{fig/bmsearchbasic.pdf}
+\includegraphics[width=0.7\textwidth]{fig/bmsearchbasic.pdf}
 \end{center}
 \caption{Boyer-Moore Search String}
 \label{fig:bmsearchbasic}
 \end{figure}
 
+\newpage
 このように、Boyer-Moore Search String は、不一致が起こった時の text の文字によって着目点をずらすということが起こるので、
 文字列検索を行う前に、着目点をずらす量を参照するための BMsearch skip table を作成する。
 "doing" という pattern であれば、そのテーブルは図\ref{fig:bmskiptable1}となる。
--- a/paper/chapter4.tex	Mon Feb 24 14:18:43 2014 +0900
+++ b/paper/chapter4.tex	Mon Feb 24 19:41:40 2014 +0900
@@ -1,11 +1,11 @@
 \chapter{並列処理向け I/O の設計と実装}
 \label{chap:poordirection}
 
-\section{map reduce}
+\section{map reduce の設計}
 
 \begin{figure}[htbp]
 \begin{center}
-\includegraphics[width=1.0\textwidth]{fig/mapreduce.pdf}
+\includegraphics[width=0.8\textwidth]{fig/mapreduce.pdf}
 \end{center}
 \caption{map reduce image}
 \label{fig:mmap} \end{figure} 
@@ -142,8 +142,19 @@
 \label{fig:speany}
 \end{figure}
 
-この問題を解決するために、Task Manager に IO\_0という新しいデバイス設定を追加した。
-この設定は他のデバイス設定よりも priority を高く設定している。
+この問題を解決するために、Task Manager に新しく I/O 専用の thread を用意した。
+%この問題を解決するために、Task Manager に IO\_0という新しいデバイス設定を追加した。
+
+この設定は他のデバイス設定よりも priority を高く設定している。(\ref{fig:addio0})
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=0.7\textwidth]{fig/addio_0.pdf}
+\end{center}
+\caption{IO\_0 の追加}
+\label{fig:addio0}
+\end{figure}
+
 SPE\_ANY よりも高く設定しているので、IO\_0 で設定を行う Read Task に SPE\_ANY で設定した 文字列検索 Task に割り込まれることがなくなる。
 (図\ref{fig:io0})
 
--- a/paper/fig/blockread.graffle	Mon Feb 24 14:18:43 2014 +0900
+++ b/paper/fig/blockread.graffle	Mon Feb 24 19:41:40 2014 +0900
@@ -26,7 +26,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2014-02-24 05:15:37 +0000</string>
+	<string>2014-02-24 09:48:59 +0000</string>
 	<key>Modifier</key>
 	<string>masataka kohagura</string>
 	<key>NotesVisible</key>
@@ -28304,7 +28304,7 @@
 					<key>Points</key>
 					<array>
 						<string>{132.36103293874675, 232.07150599490603}</string>
-						<string>{132.36106559200596, 248.50654822205897}</string>
+						<string>{132.36106559200599, 248.50654822205897}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -28340,8 +28340,8 @@
 					<integer>552</integer>
 					<key>Points</key>
 					<array>
-						<string>{157.72335141816612, 232.07150597754608}</string>
-						<string>{157.72338344326772, 248.5065476340697}</string>
+						<string>{157.72335141816603, 232.07150597754608}</string>
+						<string>{157.72338344326749, 248.5065476340697}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -28378,7 +28378,7 @@
 					<key>Points</key>
 					<array>
 						<string>{183.08567164429857, 232.0715095184045}</string>
-						<string>{183.08570428262638, 248.50654826977546}</string>
+						<string>{183.08570428262635, 248.50654826977546}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -36865,8 +36865,8 @@
 					<integer>51</integer>
 					<key>Points</key>
 					<array>
-						<string>{121.35434215276572, 177.31362670908658}</string>
-						<string>{123.14575009932759, 203.20489374014423}</string>
+						<string>{121.35421405866239, 177.31362701255151}</string>
+						<string>{123.14540006458277, 203.20489457295614}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -36963,8 +36963,8 @@
 					<integer>48</integer>
 					<key>Points</key>
 					<array>
-						<string>{124.30637664506185, 233.0925736678013}</string>
-						<string>{124.55963577309348, 262.8333405700418}</string>
+						<string>{124.30637384751844, 233.09257366832264}</string>
+						<string>{124.5596274084397, 262.83334060157586}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -37110,8 +37110,8 @@
 					<integer>40</integer>
 					<key>Points</key>
 					<array>
-						<string>{403.59289020841152, 292.35182857021192}</string>
-						<string>{403.6418477655335, 316.72218932894879}</string>
+						<string>{403.59382811493339, 292.35182848951348}</string>
+						<string>{403.64431514489542, 316.72218912963075}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -37292,8 +37292,8 @@
 					<integer>30</integer>
 					<key>Points</key>
 					<array>
-						<string>{403.5643771433887, 233.46295594411487}</string>
-						<string>{403.56730498095732, 262.46294028383636}</string>
+						<string>{403.56304284685962, 233.46295594362414}</string>
+						<string>{403.5633814561657, 262.46294025488294}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -37328,7 +37328,7 @@
 					<key>Points</key>
 					<array>
 						<string>{271.81243657594177, 233.09259180137556}</string>
-						<string>{271.81245197291719, 262.46295832778645}</string>
+						<string>{271.81243657594177, 262.46295832778645}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -37418,8 +37418,8 @@
 					<integer>26</integer>
 					<key>Points</key>
 					<array>
-						<string>{322.4174582106013, 218.29040315674928}</string>
-						<string>{352.95783888363394, 218.37625534426928}</string>
+						<string>{322.4174582106013, 218.29040314444234}</string>
+						<string>{352.95783888363394, 218.37625532453504}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -37537,8 +37537,8 @@
 					<integer>15</integer>
 					<key>Points</key>
 					<array>
-						<string>{221.22318776784829, 136.39856705594281}</string>
-						<string>{167.05098451030736, 150.34218939743715}</string>
+						<string>{221.22318776784829, 136.39856705596634}</string>
+						<string>{167.05098451030736, 150.34218939748794}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -37572,8 +37572,8 @@
 					<integer>14</integer>
 					<key>Points</key>
 					<array>
-						<string>{360.67787266681347, 149.64415580712384}</string>
-						<string>{314.68246627969279, 137.1176656241316}</string>
+						<string>{360.67788647489022, 149.63888940375787}</string>
+						<string>{314.68249365772874, 137.10721546307607}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -37607,8 +37607,8 @@
 					<integer>13</integer>
 					<key>Points</key>
 					<array>
-						<string>{407.4058231760082, 87.907401162723886}</string>
-						<string>{407.40250244300876, 147.42592797779255}</string>
+						<string>{407.40662155379846, 87.907401162756742}</string>
+						<string>{407.40648048194021, 147.42592798173524}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -38144,8 +38144,8 @@
 					<integer>40</integer>
 					<key>Points</key>
 					<array>
-						<string>{403.59396363602571, 292.35182848870994}</string>
-						<string>{403.6446716642937, 316.72218908966272}</string>
+						<string>{403.59398321789575, 292.35182848870966}</string>
+						<string>{403.64472317891733, 316.72218908964658}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -38326,8 +38326,8 @@
 					<integer>30</integer>
 					<key>Points</key>
 					<array>
-						<string>{403.56288853323679, 233.46295594362397}</string>
-						<string>{403.56292769396885, 262.46294025487464}</string>
+						<string>{403.56287521561268, 233.46295594362397}</string>
+						<string>{403.56287521561268, 262.46294025487464}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -38452,8 +38452,8 @@
 					<integer>26</integer>
 					<key>Points</key>
 					<array>
-						<string>{322.4174582106013, 218.29040313965595}</string>
-						<string>{352.95783888363394, 218.37625531686001}</string>
+						<string>{322.4174582106013, 218.29040313779441}</string>
+						<string>{352.95783888363394, 218.37625531387505}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -38571,8 +38571,8 @@
 					<integer>15</integer>
 					<key>Points</key>
 					<array>
-						<string>{221.22318776784829, 136.3985670559714}</string>
-						<string>{167.05098451030736, 150.34218939749883}</string>
+						<string>{221.22318776784829, 136.39856705597245}</string>
+						<string>{167.05098451030736, 150.34218939750116}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -38606,8 +38606,8 @@
 					<integer>14</integer>
 					<key>Points</key>
 					<array>
-						<string>{360.6778899855093, 149.63755189528572}</string>
-						<string>{314.68250063891441, 137.10456144123449}</string>
+						<string>{360.67789088236265, 149.6372122094283}</string>
+						<string>{314.68250239440016, 137.10388739400713}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -39102,11 +39102,11 @@
 	<key>WindowInfo</key>
 	<dict>
 		<key>CurrentSheet</key>
-		<integer>1</integer>
+		<integer>18</integer>
 		<key>ExpandedCanvases</key>
 		<array/>
 		<key>Frame</key>
-		<string>{{614, 1111}, {1184, 874}}</string>
+		<string>{{1149, 943}, {1184, 874}}</string>
 		<key>ListView</key>
 		<true/>
 		<key>OutlineWidth</key>
@@ -39120,9 +39120,9 @@
 		<key>SidebarWidth</key>
 		<integer>120</integer>
 		<key>VisibleRegion</key>
-		<string>{{-20, 0}, {599.42857142857144, 420}}</string>
+		<string>{{-108.99999999999999, 20.740740374446084}, {777.03702331406942, 544.44443482920974}}</string>
 		<key>Zoom</key>
-		<real>1.75</real>
+		<real>1.3500000238418579</real>
 		<key>ZoomValues</key>
 		<array>
 			<array>
Binary file paper/thesis-paper.pdf has changed
Binary file preliminary/final-thesis.pdf has changed
--- a/preliminary/final-thesis.tex	Mon Feb 24 14:18:43 2014 +0900
+++ b/preliminary/final-thesis.tex	Mon Feb 24 19:41:40 2014 +0900
@@ -25,24 +25,21 @@
 \thispagestyle{fancy}
 
 \section{はじめに}
-\subsection{研究背景}
-近年、CPU 1 コア当たりのクロック数が頭打ちとなっているので、シングルコアでの処理能力はほとんど上がっていない。
+\subsection{研究背景と目的}
+近年、CPU 1 コア当たりのクロック数が頭打ちとなっているため、シングルコアでの処理能力はほとんど上がっていない。
 それを解決した結果、シングルコアからマルチコアへの移行によって CPU 性能が向上している。
 しかし、マルチコア CPU を最大限に活かすためには、プログラムの並列度を向上させなければならない。
-そこで当研究室では Cerium Library を提供することによって並列プログラミングを容易にしている。
+そこで当研究室では、並列プログラミング用フレームワーク、Cerium 及び Cerium Task Manager の開発を行い、提供することによって並列プログラミングを容易にしている。
 
-\subsection{研究目的}
 先行研究による Task の並列化によって、プログラム全体の処理速度は飛躍的に向上しているが\cite{kinjyo} 、
-ファイル読み込み等の I/O と Task が並列で動作するようには実装されていない。
-ファイル読み込みと Task を並列化させることにより、さらなる処理速度の向上が見込まれる。
-I/O と Task が並列に動作し、高速かつ容易に記述できるような API を Cerium Library が提供することにより、様々な人が容易に並列プログラミングが記述できるようになるであろうと考えている。
+ファイル読み込み等の I/O 処理と Task が並列で動作するようには実装されていない。
 
 本研究では、 I/O と Task の並列化の設計・実装によって既存の正規表現の処理速度、処理効率を上げることを目指す。
 
 \section{Cerium Task Manager}
-Cerium Task Managerは、並列処理をTask単位で記述する。関数やサブルーチンをTaskとして扱い、そのTaskに対してInput Data、Output Data及び依存関係を設定する。そして、それに基づいた設定の元でTaskに管理し、実行される。本稿で述べるInput Dataとは、検索対象となるテキストファイルのことである。
+Cerium Task Managerは、並列処理をTask単位で記述する。関数やサブルーチンをTaskとして扱い、そのTaskに対してInput Data、Output Data及び依存関係を設定する。そして、それに基づいた設定の元で Task Manager に管理され実行される。本稿で述べるInput Dataとは、検索対象となるテキストファイルのことである。
 
-Cerium Task ManagerはPlayStation 3/Cell、Mac OS X及びLinux上で利用することが可能で、近年ではGPUへの利用も可能となった。\cite{tomari}
+Cerium Task ManagerはPlayStation 3/Cell、Mac OS X及びLinux上で利用することが可能で、近年ではGPUでの利用も可能となった。\cite{tomari}
 
 \section{I/O を含む Task の概要}
 ファイルを読み込んで一定の大きさでファイルを分割し (File Read)、それらに対してそれぞれ文字列検索等の処理 (Run Tasks)を行う。
@@ -64,10 +61,10 @@
 先行研究では mmap によるファイルの読み込みを行っていた。
 mmap でファイルを読み込むタイミングは、mmap 関数が呼ばれたときではなく、mmap した領域に対して何らかのアクセスをしたときに初めてファイルが読み込まれる。
 つまり、分割された Task は文字列検索をすぐに行うのではなく、文字列検索を行おうとした時に初めてファイルが格納される。
-Task は複数一斉に実行されることが望ましいが、mmap だとそれぞれの Task で読み込みが起こってしまうので、I/O ネックによる Task の待ちが発生する。
+Task は複数一斉に実行されることが望ましいが、mmap ではそれぞれの Task で読み込みが起こってしまうため、I/O ネックによる Task の待ちが発生する。
 
 \subsection{Blocked Read の設計と実装}
-Blocked Read とは、あるサイズずつで読み込む処理と、それらに文字列検索行う処理を分離させるための実装方法である。
+Blocked Read とは、あるサイズずつで読み込む処理と、それらに文字列検索を行う処理を分離させるための実装方法である。
 この方法では、読み込み専用の Blocked Read と、文字列検索を行う Task Blocks を別々に生成し処理を行う。
 Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行い、読み込みされ次第それぞれの文字列検索が行われる。
 
@@ -87,10 +84,10 @@
 
 \subsection{I/O 専用 thread の実装}
 Cerium Task Manager では Task 単位で CPU Type の設定を変更することができる。
-SPE\_ANY という Type を設定すると、Cerium Task Manager 側が自動的に CPU を割り振ってくれる。
+SPE\_ANY という Type を設定すると、Cerium Task Manager 側が自動的に CPU を割り振る。
 しかし、今回の実装でこの Type を使用してしまうと、Blocked Read Task の隙間時間に Task が割り振られてしまう問題がある。
 その問題を解決するために、IO\_0 という Type を新しく実装した。
-IO\_0 は他の Type よりも priority を高く設定しているので、他の Task に割り込まれることがないようにした。
+IO\_0 は他の Type よりも priority を高く設定しているため、他の Task に割り込まれることがないようチューニングを行った。
 (図\ref{fig:io0})
 %%
 %(図\ref{fig:speany})
@@ -112,6 +109,8 @@
 \label{fig:io0}
 \end{figure}
 
+\newpage
+
 \section{ベンチマーク}
 
 \begin{itemize}
@@ -148,7 +147,7 @@
 %\ref{table:result}より、mmap より Blocked Read \& IO\_0 の実行速度が 36 \% 改善された。
 表１より、mmap より Blocked Read \& SPE\_ANY の実行速度が  31\% 改善された。
 また、Blocked Read の CPU Type も SPE\_ANY から IO\_0 に変更することによって更に 4 \% の改善が見られた。
-これより、I/O を含む並列処理を行う場合は、mmap で OS に任せるのではなく、自分自身で読み込みを制御したほうが速くなることがわかる。
+これより、I/O を含む並列処理を行う場合は、mmap で実装することによって自動的に読み込ませるのではなく、自分自身で読み込みを制御したほうが速くなることがわかる。
 
 \section{まとめ}
 mmap で I/O を含む Task を実装するとき、mmap した領域に対して何らかの処理が加わった時にしか読み込みが行わないので、それぞれの Task に読み込みを任せてしまうことになる。