Mercurial > hg > Papers > 2016 > masa-master

changeset 75:c8893a5b53cf

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Wed, 17 Feb 2016 19:43:19 +0900
parents 1f1ef47ba380
children 99ddf7f900dc
files paper/c5.tex paper/c6.tex paper/master_paper.pdf paper/master_paper.tex paper/memo/data.txt
diffstat 5 files changed, 121 insertions(+), 16 deletions(-) [+]
line wrap: on
line diff
--- a/paper/c5.tex	Wed Feb 17 15:11:49 2016 +0900
+++ b/paper/c5.tex	Wed Feb 17 19:43:19 2016 +0900
@@ -26,6 +26,8 @@
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
+        ファイルサイズ : 500MB(単語数約8500万)\\
+        ファイル読み込みも含む\\
       \begin{tabular}[t]{|r|r|r|r|}
         \hline
         CPU Num / 実行方式 & Mac(wc) & mmap & Blocked Read\\
@@ -59,6 +61,8 @@
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
+        ファイルサイズ : 500MB(単語数約8500万)\\
+        ファイル読み込みは含まない\\
       \begin{tabular}[t]{|r|r|}
         \hline
         実行方式 & 実行速度(秒)\\
@@ -80,11 +84,42 @@
   \end{table}
 \end{tiny}
 
+\section{Boyer-Moore Stirng Search}
+ファイルの大きさは 約500MByte で、このファイルには、約8300万単語が含まれている。このファイルに `Paskistan' という文字列がいくつマッチするかカウントしている。(マッチ数 約400万)
+
+表\ref{table:bmsearch}
+はファイル読み込みを含まないで計測している。力任せ法と比較すると、Boyer-Moore String Search が最大 63 \% ほど速くなる。
+
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+        ファイルサイズ : 500MB(単語数約8500万)\\
+        検索文字列 : Pakistan\\
+        マッチ数約400万 \\
+        ファイル読み込みは含まない\\
+      \begin{tabular}[t]{|r|r|r|}
+        \hline
+        CPU 数 & 力任せ法 & Boyer-Moore String Search\\
+        \hline
+         1 & 3.17  & 1.70  \\
+        \hline
+         4 & 0.87  & 0.49  \\
+        \hline
+         8 & 0.47  & 0.27  \\
+        \hline
+        12 & 0.33  & 0.21  \\
+        \hline
+      \end{tabular}
+  \caption{力任せ法と Boyer-Moore String Search の比較}
+  \label{table:bmsearch}
+    \end{center}
+  \end{table}
+\end{tiny}
+
 \section{正規表現}
 当実験では、Mac の egrep 、C で実装した逐次に DFA の状態遷移と照らし合わせマッチングをするC実装の Grep、Cerium で並列処理をする CeriumGrep を比較している。
 
-
-表\ref{table:metachar} 500MB(単語数約8500万) のファイルに対して正規表現 '[A-Z][A-Za-z0-9]*s' をマッチングした結果である。
+表\ref{table:metachar}は500MB(単語数約8500万) のファイルに対して正規表現 `[A-Z][A-Za-z0-9]*s' をマッチングした結果である。
 これはファイル読み込みを含めた結果と読み込みを含めていない結果の比較である。
 
 C実装Grep や CeriumGrep は繰返し実行をすると実行速度が短くなる。
@@ -97,8 +132,8 @@
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
-        正規表現 '[A-Z][A-Za-z0-9]*s'\\
-        ファイルサイズ : 500MB(単語数約8500万)
+        正規表現 `[A-Z][A-Za-z0-9]*s'\\
+        ファイルサイズ : 500MB(単語数約8500万)\\
       \begin{tabular}[t]{|c|r|r|}
         \hline
         実行方式 & ファイル読み込み有 & ファイル読み込み無\\
@@ -120,15 +155,16 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-表\ref{table:AZaz} は正規表現 '[A-Z][A-Za-z0-9]*s' を 500MB(単語数約8500万)、1GB(単語数約1.7億語)のファイルに対してマッチングを行なった。
+表\ref{table:AZaz} は正規表現 `[A-Z][A-Za-z0-9]*s' を 500MB(単語数約8500万)、1GB(単語数約1.7億語)のファイルに対してマッチングを行なった。
 
 ファイルサイズに比例して処理時間も長くなっていく。
 
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
-        正規表現 '[A-Z][A-Za-z0-9]*s'\\
+        正規表現 `[A-Z][A-Za-z0-9]*s'\\
         ファイルサイズ : 500MB(単語数約8500万)\\
+        ファイル読み込みを含む\\
       \begin{tabular}[t]{|c|r|r|r|r|}
         \hline
         実行方式/File Size(Match Num)    & 50MB(54万) & 100MB(107万) & 500MB(536万) & 1GB(1072万) \\
@@ -156,11 +192,13 @@
 
 この例題で使用した正規表現は `(a \textbar b)' を `*a' の直後に付け加えていくと、それだけ状態数が指数関数的に増えていく。
 CeriumGrep は状態数が指数関数的に増加しても 1 秒ほど増加するが、egrep では 5,6 秒ほど増加していく。
+\newpage
 
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
         ファイルサイズ : 500MB(単語数約2400万)\\
+        ファイル読み込みを含む\\
       \begin{tabular}[t]{|l|r|r|r|r|}
         \hline
         正規表現 & 状態数 & マッチ数 & CeriumGrep (CPU 12) bread & egrep \\
@@ -183,20 +221,20 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 表\ref{table:nomatch} ab の文字列がならんでいるところに (W \textbar w)ord の正規表現
-aとb が多く含まれている約500MB(単語数約2300万)のファイルに対して、全くマッチしない正規表現を与えてパターンマッチングさせてみた。
+aとb が多く含まれている約500MB(単語数約2300万)のファイルに対して、全くマッチしない正規表現を与えてマッチングさせてみた。
 
-
-
+マッチングしない場合でも egrep と比較して CeriumGrep bread のほうが 30 \% ほど速くなる。
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
         ファイルサイズ : 500MB(単語数約2400万)\\
         正規表現 : (W \textbar w)ord\\
+        ファイル読み込みを含む\\
       \begin{tabular}[t]{|c|r|}
         \hline
         実行方式/File Size(Match Num) & time (s)\\
         \hline
-        CGrep & 27.13\\
+        C実装 Grep & 27.13\\
         \hline
         CeriumGrep(CPU 12) mmap  & 21.58\\
         \hline
--- a/paper/c6.tex	Wed Feb 17 15:11:49 2016 +0900
+++ b/paper/c6.tex	Wed Feb 17 19:43:19 2016 +0900
@@ -1,5 +1,15 @@
 \chapter{結論}
-\section{---}
+本研究室で開発している Cerium を利用して文字列処理の並列処理に関する研究を行なった。
+並列処理時のファイルの読み込みについて改良を行なった結果、最大13\%速くなる
+
+本研究では文字列処理の並列処理の例題として、WordCount、Boyer-Moore String Search 、正規表現を実装した。
+それぞれの例題によって結果の整合性を取る必要があるが、どのように整合性を取るかは問題によって考慮する必要がある。
+
+本研究で実装した正規表現は、正規表現から正規表現木を生成し、その正規表現木に状態を割り振りながらNFA や DFA を生成する。
+もし NFA が存在した場合は Subset Construction で DFA に変換する。
+DFA に変換後、その DFA を元に与えられたファイルに対してマッチングさせる。
+その結果、ファイル読み込みを含め egrep と比較して最大 66 \% 速度がでる。
+
 \section{今後の課題}
 これまでの正規表現は一文字ずつ参照して状態を割り振っていった。この状態割り振りの問題として文字列の長さの分だけ状態ができてしまう。
 状態が長くなればなるほど、ファイルと正規表現のマッチング時の状態遷移数もそれだけ多くなってしまう。
@@ -19,4 +29,4 @@
   \label{fig:wordstate}
 \end{figure}
 
-実際にファイルに対して文字列を検索するときは、Boyer-Moore String Search と呼ばれる 1977 年に Robert S. Boyer と J Strother Moore が開発した文字列検索アルゴリズムを採用して高速化を図ろうとする。\cite{bmsearch}
+実際にファイルに対して文字列を検索するときは、Boyer-Moore String Search を採用することにより、さらに高速になると期待される。
Binary file paper/master_paper.pdf has changed
--- a/paper/master_paper.tex	Wed Feb 17 15:11:49 2016 +0900
+++ b/paper/master_paper.tex	Wed Feb 17 19:43:19 2016 +0900
@@ -73,13 +73,22 @@
 %要旨
 \begin{abstract}
 Cerium は当研究室で開発している並列プログラミングフレームワークである。
-Cerium にはファイルを読み込んで文字列処理を行う例題がある。
-mmap に代わるファイル読み込みを実装し、文字列処理とファイル読み込みが並列に実行するよう実装した。
-また、文字列処理の例題として正規表現を新しく実装して測定評価を行った。
+
+従来はファイル読み込みを mmap で実装していたが、本論文では並列処理向け I/O の Blocked Read を実装を行った。
+Blocked Read とは、ファイルを一度に読み込まずに、あるサイズに分割して読み込む手法である。
+
+Cerium にはファイルを読み込んで文字列処理を行う例題があり、Word Count 、Boyer-Moore String Search 、正規表現を実装し測定した。
+それぞれの例題によって結果の整合性を取る必要があるが、どのように整合性を取るかは問題によって考慮する必要がある。
+
+本研究で実装した正規表現は、正規表現から正規表現木を生成し、その正規表現木に状態を割り振りながらNFA や DFA を生成する。
+もし NFA が存在した場合は Subset Construction で DFA に変換する。
+そして、DFA の生成後ファイルとマッチングさせる。
+
+それぞれの例題と Mac に built-in されている wc、egrep と比較し測定を行なった。
 \end{abstract}
 
 \begin{abstract_eng}
-  We are developing parallel framework using Code/Data Segment.
+  We are developing parallel.
 \end{abstract_eng}
 
 %目次
--- a/paper/memo/data.txt	Wed Feb 17 15:11:49 2016 +0900
+++ b/paper/memo/data.txt	Wed Feb 17 19:43:19 2016 +0900
@@ -1,3 +1,51 @@
++firefly+one ./bm_search -file ../../../../Applications/Grep/regexParser/file/500MB.txt -cpu 12 -sw Pakistan
+Time: 8.842135
+Time: 9.476817
+Time: 8.412663
+Time: 9.037766
+Time: 9.744255
+
++firefly+one ./bm_search -file ../../../../Applications/Grep/regexParser/file/500MB.txt -cpu 12 -sw Pakistan
+Time: 9.475362
+Time: 10.167466
+Time: 11.650952
+Time: 9.425900
+Time: 8.842135
+
+
++firefly+one +firefly+one ./bm_search -file ../../../../Applications/Grep/regexParser/file/500MB.txt -cpu 12 -sw Pakistan
+Time: 0.337304
+Time: 0.334214
+Time: 0.332706
+Time: 0.333170
+Time: 0.333712
+
++firefly+one +firefly+one ./bm_search -file ../../../../Applications/Grep/regexParser/file/500MB.txt -cpu 12 -sw Pakistan    
+Time: 8.119197
+Time: 13.030952
+Time: 10.503337
+Time: 11.935778
+Time: 8.007437
+Time: 9.426419
+Time: 9.128091
+
++firefly+one ./bm_search -file ../../../../Applications/Grep/regexParser/file/500MB.txt -cpu 12 -sw Pakistan
+HIT:4011826
+Time: 0.210999
+Time: 0.207438
+Time: 0.207017
+Time: 0.209743
+Time: 0.207294
+
++firefly+one ./bm_search -file ../../../../Applications/Grep/regexParser/file/500MB.txt -cpu 12 -sw Pakistan -br
+Time: 0.426066
+Time: 8.939968
+Time: 7.706492
+Time: 7.715002
+Time: 9.256689
+Time: 10.722651
+Time: 9.870106
+
 +firefly+one ./time.pl './regexParser -subset -regex '\''(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)z'\'' -ts  -file file/ab500MB.txt' 10
 ------setting------
     command  = ./regexParser -subset -regex '(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)z' -ts  -file file/ab500MB.txt