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

changeset 65:1ff5dde6decf

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
date Mon, 24 Feb 2014 05:31:01 +0900
parents 663ef31f734f
children dd1755633a9f
files paper/chapter5.tex paper/fig/blockread.graffle paper/thesis-paper.pdf
diffstat 3 files changed, 280 insertions(+), 55 deletions(-) [+]
line wrap: on
line diff
--- a/paper/chapter5.tex	Mon Feb 24 03:07:57 2014 +0900
+++ b/paper/chapter5.tex	Mon Feb 24 05:31:01 2014 +0900
@@ -3,30 +3,50 @@
 
 
 \section{実験環境}
-Mac OS X 10.9.1
 
-2*2.66 GHz 6-Core Intel Xeon
-
-Memory 16GB 1333MHz DDR3
-
-HHD 1TB
-
-file size 約10 GB
-
-BM search で文字列を検索
+\begin{itemize}
+\item Mac OS X 10.9.1
+\item 2*2.66 GHz 6-Core Intel Xeon
+\item Memory 16GB 1333MHz DDR3
+\item HHD 1TB
+\item file size 10 GB
+\item CPU num 12
+\item Boyer-Moore String Search で pattern がいくつ含まれているか検索
+\item ファイルを読み込みから結果が返ってくるまでを測定
+\end{itemize}
 
 \section{結果}
 
-・ mmap での計測
-
-・ Blocked Read が SPE\_ANYのとき
-
-・ Blocked Read が IO\_0 のとき
+以下の表に実行結果を示す。
 
-・初回実行時には Broked Read のほうが速くなったが、キャッシュに残らない
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \label{table:result}
+      \small
+      \begin{tabular}[t]{c|r}
+        \hline
+        読み込み方法 & 平均実行速度(s)\\
+        \hline
+        mmap & 154.6 \\
+        \hline
+        Blocked Read \& SPE\_ANY & 106.0 \\
+        \hline
+        Blocked Read \& IO\_0 & 99.2 \\
+        \hline
+      \end{tabular}
+      \caption{実行結果}
+    \end{center}
+  \end{table}
+\end{tiny}
 
-・サイズによってはキャッシュに入らないので、同じファイル 2回検索するとそうとうなコストに
-
-・ 2回目以降での測定(ファイルがキャッシュにのこったときのもの)
+実験結果より、mmap より Blocked Read \& IO\_0 の実行速度が 36 \% 改善された。
+また、Blocked Read の CPU Type も SPE\_ANY から IO\_0 に変更することによって更に 4 \% の改善が見られた。
 
 \section{考察}
+mmap より Blocked Read で実装したほうが速くなったが、これは mmap の読み込み方法が問題であると考える。
+
+I/O を含む例題の場合、シングルコアでの逐次実行であれば、mmap や pread で実装しても、Task は 読み込みを行って文字列検索を行うというシンプルな動作になる。
+しかし、マルチコアの並列実行であれば、mmap で実装してしまうと、Task それぞれで読み込みを行ってしまうので競合が発生してしまう。
+
+読み込みの競合が起こらないように Blocked Read にて読み込み部分と文字列検索部分を分けた結果、こちらのほうが速度が向上した。
--- a/paper/fig/blockread.graffle	Mon Feb 24 03:07:57 2014 +0900
+++ b/paper/fig/blockread.graffle	Mon Feb 24 05:31:01 2014 +0900
@@ -26,7 +26,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2014-02-23 17:32:25 +0000</string>
+	<string>2014-02-23 20:26:58 +0000</string>
 	<key>Modifier</key>
 	<string>masataka kohagura</string>
 	<key>NotesVisible</key>
@@ -36824,6 +36824,246 @@
 					<key>Head</key>
 					<dict>
 						<key>ID</key>
+						<integer>8</integer>
+					</dict>
+					<key>ID</key>
+					<integer>52</integer>
+					<key>Points</key>
+					<array>
+						<string>{174.78414800719656, 218.14816136090596}</string>
+						<string>{221.20739729763693, 218.14816136090596}</string>
+					</array>
+					<key>Style</key>
+					<dict>
+						<key>stroke</key>
+						<dict>
+							<key>HeadArrow</key>
+							<string>FilledArrow</string>
+							<key>Legacy</key>
+							<true/>
+							<key>LineType</key>
+							<integer>1</integer>
+							<key>TailArrow</key>
+							<string>0</string>
+						</dict>
+					</dict>
+					<key>Tail</key>
+					<dict>
+						<key>ID</key>
+						<integer>46</integer>
+					</dict>
+				</dict>
+				<dict>
+					<key>Class</key>
+					<string>LineGraphic</string>
+					<key>Head</key>
+					<dict>
+						<key>ID</key>
+						<integer>46</integer>
+					</dict>
+					<key>ID</key>
+					<integer>51</integer>
+					<key>Points</key>
+					<array>
+						<string>{121.35529867678233, 177.31362450979645}</string>
+						<string>{123.14836393558373, 203.20488774565121}</string>
+					</array>
+					<key>Style</key>
+					<dict>
+						<key>stroke</key>
+						<dict>
+							<key>HeadArrow</key>
+							<string>FilledArrow</string>
+							<key>Legacy</key>
+							<true/>
+							<key>LineType</key>
+							<integer>1</integer>
+							<key>TailArrow</key>
+							<string>0</string>
+						</dict>
+					</dict>
+					<key>Tail</key>
+					<dict>
+						<key>ID</key>
+						<integer>9</integer>
+					</dict>
+				</dict>
+				<dict>
+					<key>Class</key>
+					<string>LineGraphic</string>
+					<key>Head</key>
+					<dict>
+						<key>ID</key>
+						<integer>49</integer>
+					</dict>
+					<key>ID</key>
+					<integer>50</integer>
+					<key>Points</key>
+					<array>
+						<string>{124.686891540929, 292.72221175516592}</string>
+						<string>{124.686891540929, 316.90738395819511}</string>
+					</array>
+					<key>Style</key>
+					<dict>
+						<key>stroke</key>
+						<dict>
+							<key>HeadArrow</key>
+							<string>FilledArrow</string>
+							<key>Legacy</key>
+							<true/>
+							<key>LineType</key>
+							<integer>1</integer>
+							<key>TailArrow</key>
+							<string>0</string>
+						</dict>
+					</dict>
+					<key>Tail</key>
+					<dict>
+						<key>ID</key>
+						<integer>47</integer>
+					</dict>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{74.5818518537872, 317.40738394100197}, {100.21006286627792, 28.888889312744141}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>ID</key>
+					<integer>49</integer>
+					<key>Shape</key>
+					<string>Rectangle</string>
+					<key>Text</key>
+					<dict>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1265
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 Spawn Task}</string>
+					</dict>
+				</dict>
+				<dict>
+					<key>Class</key>
+					<string>LineGraphic</string>
+					<key>Head</key>
+					<dict>
+						<key>ID</key>
+						<integer>47</integer>
+					</dict>
+					<key>ID</key>
+					<integer>48</integer>
+					<key>Points</key>
+					<array>
+						<string>{124.30640165693954, 233.09257366778326}</string>
+						<string>{124.55971056087196, 262.83334056894927}</string>
+					</array>
+					<key>Style</key>
+					<dict>
+						<key>stroke</key>
+						<dict>
+							<key>HeadArrow</key>
+							<string>FilledArrow</string>
+							<key>Legacy</key>
+							<true/>
+							<key>LineType</key>
+							<integer>1</integer>
+							<key>TailArrow</key>
+							<string>0</string>
+						</dict>
+					</dict>
+					<key>Tail</key>
+					<dict>
+						<key>ID</key>
+						<integer>46</integer>
+					</dict>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{74.5818518537872, 263.33332245961492}, {100.21006286627792, 28.888889312744141}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>ID</key>
+					<integer>47</integer>
+					<key>Shape</key>
+					<string>Rectangle</string>
+					<key>Text</key>
+					<dict>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1265
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 Scheduler}</string>
+					</dict>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{74.074085130154359, 203.70370249754822}, {100.21006286627792, 28.888889312744141}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>ID</key>
+					<integer>46</integer>
+					<key>Shape</key>
+					<string>Rectangle</string>
+					<key>Text</key>
+					<dict>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1265
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 IO Threads}</string>
+					</dict>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{78.511440980122941, 322.22218400984059}, {100.21006286627792, 28.888889312744141}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>ID</key>
+					<integer>43</integer>
+					<key>Shape</key>
+					<string>Rectangle</string>
+					<key>Text</key>
+					<dict>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1265
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 Spawn Task}</string>
+					</dict>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{82.2151446184169, 326.66662837579349}, {100.21006286627792, 28.888889312744141}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>ID</key>
+					<integer>42</integer>
+					<key>Shape</key>
+					<string>Rectangle</string>
+					<key>Text</key>
+					<dict>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1265
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 Spawn Task}</string>
+					</dict>
+				</dict>
+				<dict>
+					<key>Class</key>
+					<string>LineGraphic</string>
+					<key>Head</key>
+					<dict>
+						<key>ID</key>
 						<integer>38</integer>
 					</dict>
 					<key>ID</key>
@@ -37179,41 +37419,6 @@
 					<key>Head</key>
 					<dict>
 						<key>ID</key>
-						<integer>8</integer>
-					</dict>
-					<key>ID</key>
-					<integer>16</integer>
-					<key>Points</key>
-					<array>
-						<string>{160.09771747376584, 176.9872782553353}</string>
-						<string>{232.32927137559574, 203.53010114097233}</string>
-					</array>
-					<key>Style</key>
-					<dict>
-						<key>stroke</key>
-						<dict>
-							<key>HeadArrow</key>
-							<string>FilledArrow</string>
-							<key>Legacy</key>
-							<true/>
-							<key>LineType</key>
-							<integer>1</integer>
-							<key>TailArrow</key>
-							<string>0</string>
-						</dict>
-					</dict>
-					<key>Tail</key>
-					<dict>
-						<key>ID</key>
-						<integer>9</integer>
-					</dict>
-				</dict>
-				<dict>
-					<key>Class</key>
-					<string>LineGraphic</string>
-					<key>Head</key>
-					<dict>
-						<key>ID</key>
 						<integer>9</integer>
 					</dict>
 					<key>ID</key>
Binary file paper/thesis-paper.pdf has changed