Mercurial > hg > Papers > 2016 > masa-master

changeset 66:5defec0399f9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Tue, 16 Feb 2016 17:29:28 +0900
parents 6af8c277a662
children 9c16f6b18100
files paper/c5.tex paper/master_paper.pdf paper/memo/data.txt
diffstat 3 files changed, 125 insertions(+), 113 deletions(-) [+]
line wrap: on
line diff
--- a/paper/c5.tex	Tue Feb 16 16:23:26 2016 +0900
+++ b/paper/c5.tex	Tue Feb 16 17:29:28 2016 +0900
@@ -7,26 +7,59 @@
 \item 1TB HDD
 \end{itemize}
 
-Cerium で実装した Word Count と Mac の wc の比較と、今回実装した正規表現と Mac の egrep の比較を行なった。
+Cerium で実装した Word Count と Mac の wc の比較と、実装した正規表現と Mac の egrep の比較を行なった。
 また、それぞれの結果に実装した並列処理向け I/O の結果も含む。
 
 \section{Word Count}
 ファイルの大きさは 約500MByte で、このファイルには 約650万行、約8300万単語が含まれている。
-図\ref{fig:wordcount} はファイル読み込みを含まない Word Count の結果である。
+
+表\ref{table:IOwordcount} は、ファイル読み込みを含めた Word Count の結果である。
+Mac の wc ではこのファイルを処理するのに 10.59 秒かかる。それに対して、Cerium Word Count は mmap Blocked Read 全ての状況で Mac の wc よりも速いことを示している。
+Cerium Word Count 12 CPU のとき、7.83 秒で処理をしており、Mac の wc の 1.4 倍ほど速くなっている。
+
+mmap は読み込みを OS が制御しており、書き手が制御できない。
+また Word Count が走る際ファイルアクセスはランダムアクセスとなる。
+mmap はランダムアクセスを想定していなくてグラフにばらつきが起こっていると考えられる。
+Blocked Read では読み込みをプログラムの書き手が制御しており、ファイルの読み込みもファイルの先頭から順次読み込みを行なっている。
+そのため、読み込みを含めた結果にばらつきが起こりにくくなっていると予想される。
+
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \begin{tabular}[t]{|r|r|r|r|}
+        \hline
+        CPU Num / 実行方式 & Mac(wc) & mmap & Blocked Read\\
+        \hline
+         1 & 10.590  & 9.96  & 9.33 \\
+        \hline
+         4 & ---     & 8.63  & 8.52 \\
+        \hline
+         8 & ---     & 10.35 & 8.04 \\
+        \hline
+        12 & ---     & 9.26  & 7.82 \\
+        \hline
+      \end{tabular}
+  \caption{ファイル読み込みを含む Word Count}
+  \label{table:IOwordcount}
+    \end{center}
+  \end{table}
+\end{tiny}
+
+\newpage
+表\ref{fig:wordcount} はファイル読み込みを含まない Word Count の結果である。
 
 Mac の wc ではこのファイルを処理するのに 4.08 秒かかる。それに対して、Cerium Word Count は 1 CPU で 3.70 秒、12 CPU だと 0.40 秒で処理できる。
 
 1 CPU で動作させると Mac の wc よりも 1.1 倍ほど速くなり、12 CPU で動作させると wc よりも 10.2 倍ほど速くなった。
+1 CPU と 12 CPU で比較すると、9.25 倍ほど速くなった。
 
-1 CPU と 12 CPU で比較すると、9.25 倍ほど速くなった。
-12 倍速くなるはずだが、Word Count の処理以外にも Word Count のタスクを作る、タスクを CPU に送るなどの通信部分も含まれるため理論値は出ない。
-
-表\ref{table:metachar}
+ファイルを読み込んだ結果と比較すると、ファイルを読み込まないで実行したほうが 6,7 秒ほど速くなる。
+これよりファイルを読み込んだ文字列処理の場合、処理時間の60\%から90\% はファイルの読み込みであることがわかる。
 
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
-      \begin{tabular}[t]{r|r}
+      \begin{tabular}[t]{|r|r|}
         \hline
         実行方式 & 実行速度(秒)\\
         \hline
@@ -47,44 +80,8 @@
   \end{table}
 \end{tiny}
 
-図\ref{fig:IOwordcount} は、ファイル読み込みを含めた Word Count の結果である。
-Mac の wc ではこのファイルを処理するのに 10.59 秒かかる。それに対して、Cerium Word Count は mmap Blocked Read 全ての状況で Mac の wc よりも速いことを示している。
-Cerium Word Count 12 CPU のとき、7.83 秒で処理をしており、Mac の wc の 1.4 倍ほど速くなっている。
-
-mmap は読み込みを OS が制御しており、書き手が制御できない。
-また Word Count が走る際ファイルアクセスはランダムアクセスとなる。
-mmap はランダムアクセスを想定していなくてグラフにばらつきが起こっていると考えられる。
-Blocked Read では読み込みをプログラムの書き手が制御しており、ファイルの読み込みもファイルの先頭から順次読み込みを行なっている。
-そのため、読み込みを含めた結果にばらつきが起こりにくくなっていると予想される。
-
-\begin{tiny}
-  \begin{table}[ht]
-    \begin{center}
-      \begin{tabular}[t]{r|r|r|r}
-        \hline
-        CPU Num / 実行方式 & Mac(wc) & mmap & Blocked Read\\
-        \hline
-        1 & 10.590  & 9.96  & 9.33 \\
-        \hline
-        2 & ---     & 8.63  & 8.52 \\
-        \hline
-        4 & ---     & 10.35 & 8.04 \\
-        \hline
-        8 & ---     & 9.26  & 7.82 \\
-        \hline
-      \end{tabular}
-  \caption{ファイル読み込みを含む Word Count}
-  \label{table:IOwordcount}
-    \end{center}
-  \end{table}
-\end{tiny}
-
 \section{正規表現}
-
-\begin{itemize}
-\item DFA を生成後(NFA であれば、Subset Construction後)、逐次にDFAと照らし合わせる。
-\item 並列処理時に NFA・DFA を分割した Task に配りそれぞれの Taskで 照らし合わせる。照らし合わせた際に NFA だとわかった場合にはその場で Subset Construction し DFA を生成する。
-\end{itemize}
+当実験では、Mac の egrep 、C で実装した逐次に DFA の状態遷移と照らし合わせる CGrep、Cerium で並列処理をする CeriumGrep を比較している。
 
 表\ref{table:AZaz} '[A-Z][A-Za-z0-9]*s'
 ファイルサイズの側のかっこ書き内は与えられた正規表現にマッチした数
@@ -93,11 +90,11 @@
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
-      \begin{tabular}[t]{c|r|r|r}
+      \begin{tabular}[t]{|c|r|r|r|}
         \hline
         実行方式/File Size(Match Num) & 500MB(500万) & 1GB(1000万) \\
         \hline
-        DFAの状態遷移での逐次実行 & 20.62 & 40.10\\
+        CGrep & 20.62 & 40.10\\
         \hline
         CeriumGrep(CPU 12) mmap  & 18.00 & 26.96\\
         \hline
@@ -106,33 +103,59 @@
         egrep & 59.51 & 119.23\\
         \hline
       \end{tabular}
-  \caption{[A-Z][A-Za-z0-9]*s のマッチング}
+  \caption{[A-Z][A-Za-z0-9]*s のマッチングの結果}
   \label{table:AZaz}
     \end{center}
   \end{table}
 \end{tiny}
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+表\ref{table:metachar}
+
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \begin{tabular}[t]{|c|r|r|}
+        \hline
+        実行方式 & ファイル読み込み有 & ファイル読み込み無\\
+        \hline
+        CGrep & 21.171 & 16.150\\
+        \hline
+        CeriumGrep(CPU 2) & 27.061 & 15.401\\
+        \hline
+        CeriumGrep(CPU 12) & 12.48 & 7.386\\
+        \hline
+        egrep & 59.51 & --- \\
+        \hline
+      \end{tabular}
+      \caption{実装したそれぞれのプログラムと egrep との比較}
+      \label{table:metachar}
+    \end{center}
+  \end{table}
+\end{tiny}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 表\ref{table:abab}
 約500 MB 、単語数約2300万 abab がめちゃくちゃ含まれているファイル
 
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
-      \begin{tabular}[t]{l|r|r|r}
+      \begin{tabular}[t]{|l|r|r|r|}
         \hline
         正規表現 & マッチ数 & CeriumGrep time (s) & egrep time(s)\\
         \hline
-        '(a|b)*a(a|b)(a|b)'                  & 約1950万  & 38.67 &  86.66 \\
+        '(a \textbar b)*a(a \textbar b)(a \textbar b)'                  & 約1950万  & 38.67 &  86.66 \\
         \hline
-        '(a|b)*a(a|b)(a|b)(a|b)'             & 約1640万  & 38.72 &  94.25 \\
+        '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)'             & 約1640万  & 38.72 &  94.25 \\
         \hline
-        '(a|b)*a(a|b)(a|b)(a|b)(a|b)'        & 約1640万  & 39.59 & 100.98 \\
+        '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)'        & 約1640万  & 39.59 & 100.98 \\
         \hline
-        '(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)'   & 約1550万 & 38.68 & 104.82 \\
+        '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)'   & 約1550万 & 38.68 & 104.82 \\
         \hline
       \end{tabular}
-  \caption{abab}
+  \caption{状態を増やした結果}
   \label{table:abab}
     \end{center}
   \end{table}
@@ -140,7 +163,7 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-表\ref{table:nomatch} ab の文字列がならんでいるところに (W|w)ord の正規表現
+表\ref{table:nomatch} ab の文字列がならんでいるところに (W \textbar w)ord の正規表現
 
 全くマッチしないパターン
 Filesize:500MB
@@ -148,73 +171,48 @@
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
-      \begin{tabular}[t]{c|r|r|r}
+      \begin{tabular}[t]{|c|r|}
         \hline
-        実行方式/File Size(Match Num) & I/O含む & I/O 含まない & \\
+        実行方式/File Size(Match Num) & time (s)\\
         \hline
-        DFAの状態遷移での逐次実行& 27.130 & 14.763 & \\
+        CGrep & 27.130\\
         \hline
-        CeriumGrep(CPU 12) mmap  & 21.576 & 1.873 & \\
+        CeriumGrep(CPU 12) mmap  & 21.576\\
         \hline
-        CeriumGrep(CPU 12) bread & 19.986 & & \\
+        CeriumGrep(CPU 12) bread & 19.986\\
         \hline
-        egrep & 28.332 & & \\
+        egrep & 28.332\\
         \hline
       \end{tabular}
-  \caption{(W|w)ork のマッチング}
+  \caption{(W \textbar w)ork のマッチング}
   \label{table:nomatch}
     \end{center}
   \end{table}
 \end{tiny}
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-表\ref{table:abab}
-
-\begin{tiny}
-  \begin{table}[ht]
-    \begin{center}
-      \begin{tabular}[t]{r|r|r|r}
-        \hline
-        CPU Num / 実行方式 & egrep & mmap & Blocked Read\\
-        \hline
-        1 & 83.09   & 57.65 & 40.49 \\
-        \hline
-        2 & ---     & 43.96 & 33.72 \\
-        \hline
-        4 & ---     & 33.37 & 34.26 \\
-        \hline
-        8 & ---     & 35.48 & 32.46 \\
-        \hline
-      \end{tabular}
-  \caption{abab}
-  \label{table:abab}
-    \end{center}
-  \end{table}
-\end{tiny}
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-表\ref{table:metachar}
-
-\begin{tiny}
-  \begin{table}[ht]
-    \begin{center}
-      \begin{tabular}[t]{c|r|r}
-        \hline
-        実行方式 & ファイル読み込み有 & ファイル読み込み無\\
-        \hline
-        DFAの状態遷移での逐次実行 & 21.171 & 16.150\\
-        \hline
-        並列処理(CPU 2) & 27.061 & 15.401\\
-        \hline
-        並列処理(CPU 12) & 10.419 & 7.386\\
-        \hline
-        egrep & 57.753 & --- \\
-        \hline
-      \end{tabular}
-      \caption{実装したそれぞれのプログラムと egrep との比較}
-      \label{table:metachar}
-    \end{center}
-  \end{table}
-\end{tiny}
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% 
+% 表\ref{table:abab}
+% 
+% \begin{tiny}
+%   \begin{table}[ht]
+%     \begin{center}
+%       \begin{tabular}[t]{|r|r|r|r|}
+%         \hline
+%         CPU Num / 実行方式 & egrep & mmap & Blocked Read\\
+%         \hline
+%         1 & 83.09   & 57.65 & 40.49 \\
+%         \hline
+%         2 & ---     & 43.96 & 33.72 \\
+%         \hline
+%         4 & ---     & 33.37 & 34.26 \\
+%         \hline
+%         8 & ---     & 35.48 & 32.46 \\
+%         \hline
+%       \end{tabular}
+%   \caption{abab}
+%   \label{table:abab}
+%     \end{center}
+%   \end{table}
+% \end{tiny}
+% 
Binary file paper/master_paper.pdf has changed
--- a/paper/memo/data.txt	Tue Feb 16 16:23:26 2016 +0900
+++ b/paper/memo/data.txt	Tue Feb 16 17:29:28 2016 +0900
@@ -1,4 +1,18 @@
-
++firefly+one ./time.pl './regexParser -regex '\''(W|w)ord'\'' -ts -file file/ab500MB.txt' 10
+------setting------
+    command  = ./regexParser -regex '(W|w)ord' -ts -file file/ab500MB.txt
+    loop     = 10
+------result(s)---
+       23.73 real        14.24 user         0.23 sys
+       25.75 real        14.24 user         0.26 sys
+       27.17 real        14.24 user         0.23 sys
+       26.10 real        14.24 user         0.23 sys
+       30.25 real        14.24 user         0.23 sys
+       29.39 real        14.26 user         0.24 sys
+       30.22 real        14.25 user         0.23 sys
+       29.97 real        14.25 user         0.23 sys
+       30.13 real        14.24 user         0.24 sys
+       28.86 real        14.24 user         0.24 sys
 
 
 +firefly+one ./time.pl './cerium/ceriumGrep -br -cpu 12 -subset -regex '\''(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)'\'' -file  file/+firefly+one ./time.pl './cerium/ceriumGrep -br -cpu 12 -subset -regex '\''(a|b)*a(a|b)(a|b)'\'' -file  file/ab500MB.txt' 10