# HG changeset patch # User Masataka Kohagura # Date 1455778762 -32400 # Node ID ca50770a7fdebeee793dc3ade92d983020c4208f # Parent 497c01bb005dc7081d3b673fb5eda40ebafe6879 add result diff -r 497c01bb005d -r ca50770a7fde paper/c5.tex --- a/paper/c5.tex Thu Feb 18 12:48:38 2016 +0900 +++ b/paper/c5.tex Thu Feb 18 15:59:22 2016 +0900 @@ -32,13 +32,13 @@ \hline CPU Num / 実行方式 & Mac(wc) & mmap & Blocked Read\\ \hline - 1 & 10.590 & 9.96 & 9.33 \\ + 1 & 10.59 & 9.96 & 9.33 \\ \hline - 4 & --- & 8.63 & 8.52 \\ + 4 & --- & 8.63 & 8.52 \\ \hline - 8 & --- & 10.35 & 8.04 \\ + 8 & --- & 10.35 & 8.04 \\ \hline - 12 & --- & 9.26 & 7.82 \\ + 12 & --- & 9.26 & 7.82 \\ \hline \end{tabular} \caption{ファイル読み込みを含む Word Count} @@ -117,12 +117,12 @@ \end{tiny} \section{正規表現} -当実験では、Mac の egrep 、C で実装した逐次に DFA の状態遷移と照らし合わせマッチングをする、Cerium で並列処理をする CeriumGrep を比較している。 +当実験では、Mac の egrep 、C で実装した逐次に DFA の状態遷移と照らし合わせマッチングをする single thread grep、Cerium で並列処理をする CeriumGrep を比較している。 表\ref{table:metachar}は500MB(単語数約8500万) のファイルに対して正規表現 `[A-Z][A-Za-z0-9]*s' をマッチングした結果である。 これはファイル読み込みを含めた結果と読み込みを含めていない結果の比較である。 -C実装Grep や CeriumGrep は繰返し実行をすると実行速度が短くなる。 +single thread grep や CeriumGrep は繰返し実行をすると実行速度が短くなる。 これは、読み込んだファイルがキャッシュに残っており、ファイル読み込みが省略されるためである。 同じファイルに対して違う正規表現でマッチングさせたとしてもファイル読み込みが省略されるため、高速に結果が返ってくる。 @@ -138,7 +138,7 @@ \hline 実行方式 & ファイル読み込み有 & ファイル読み込み無\\ \hline - C実装Grep & 21.17 & 16.15\\ + single thread grep & 21.17 & 16.15\\ \hline CeriumGrep(CPU 12) mmap & 18.00 & 5.12\\ \hline @@ -169,7 +169,7 @@ \hline 実行方式/File Size(Match Num) & 50MB(54万) & 100MB(107万) & 500MB(536万) & 1GB(1072万) \\ \hline - C実装 Grep & 4.51 & 9.42 & 20.62 & 40.10\\ + single thread grep & 4.51 & 9.42 & 20.62 & 40.10\\ \hline CeriumGrep(CPU 12) mmap & 8.97 & 10.79 & 18.00 & 29.16\\ \hline @@ -190,6 +190,7 @@ は aとb が多く含まれている約500MB(単語数約2400万)のファイルに対して、正規表現の状態数を変化させてみた。 これは読み込みを含んでいる結果で、CeriumGrep のファイル読み込みは Blocked Read、CPU 数 12 にて実行した。 + この例題で使用した正規表現は `(a \textbar b)' を `*a' の直後に付け加えていくと、それだけ状態数が指数関数的に増えていく。 CeriumGrep は状態数が指数関数的に増加しても 1 秒ほど増加するが、egrep では 5,6 秒ほど増加していく。 \newpage @@ -198,18 +199,19 @@ \begin{table}[ht] \begin{center} ファイルサイズ : 500MB(単語数約2400万)\\ + 状態数の内訳 : 状態割当時の状態数/subset 後の状態数\\ ファイル読み込みを含む\\ \begin{tabular}[t]{|l|r|r|r|r|} \hline 正規表現 & 状態数 & マッチ数 & CeriumGrep (CPU 12) bread & egrep \\ \hline - '(a \textbar b)*a(a \textbar b)(a \textbar b)z' & 12 & 約10万 & 26.58 & 70.11 \\ + '(a \textbar b)*a(a \textbar b)(a \textbar b)z' & 5/12 & 約10万 & 26.58 & 70.11 \\ \hline - '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)z' & 21 & 約8万 & 27.89 & 76.78 \\ + '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)z' & 6/21 & 約8万 & 27.89 & 76.78 \\ \hline - '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)z' & 38 & 約4万 & 28.86 & 81.88 \\ + '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)z' & 7/38 & 約4万 & 28.86 & 81.88 \\ \hline - '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)z' & 71 & 約2万 & 29.15 & 86.93 \\ + '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)z' & 8/71 & 約2万 & 29.15 & 86.93 \\ \hline \end{tabular} \caption{正規表現の状態数を増やした Grep の結果} @@ -232,9 +234,9 @@ ファイル読み込みを含む\\ \begin{tabular}[t]{|c|r|} \hline - 実行方式/File Size(Match Num) & time (s)\\ + 実行方式 & time (s)\\ \hline - C実装 Grep & 27.13\\ + single thread grep & 27.13\\ \hline CeriumGrep(CPU 12) mmap & 21.58\\ \hline diff -r 497c01bb005d -r ca50770a7fde paper/master_paper.pdf Binary file paper/master_paper.pdf has changed diff -r 497c01bb005d -r ca50770a7fde slide/s6/index.html --- a/slide/s6/index.html Thu Feb 18 12:48:38 2016 +0900 +++ b/slide/s6/index.html Thu Feb 18 15:59:22 2016 +0900 @@ -323,112 +323,327 @@

実験1:Word Count

-

全ての実験のfile size

+ - + - - - - - + + + - - - - - - - + + + + + - - - - - - - + + + + + - - - - - - - + + + + + - - - - - - - - + + + + +
read mode \ CPU numCPU Num\実行方式 CPU 1CPU 4CPU 8CPU 12GPU(CUDA)Mac(wc)mmapBlocked Read
mmap15.35311.28711.70711.137
103.410
 110.599.969.33
read16.84611.73011.48711.437
106.050
4---8.638.52
Blocked Read(SPE_ANY)13.29711.98410.88711.146
94.626
8---10.358.04
Blocked Read(IO_0)11.50311.43711.36511.412
94.496
12---9.267.82
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
実行方式実行速度(s)
Mac(wc)4.08
Cerium Word Count(CPU 1)3.70
Cerium Word Count(CPU 4)1.00
Cerium Word Count(CPU 8)0.52
Cerium Word Count(CPU 12)0.40
+ +
+ +
+

実験2 : Boyer-Moore String Search

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
CPU Num\実行方式力任せ法Boyer-Moore String Search
13.171.70
40.870.49
80.470.27
120.330.21
+
+
+

実験3:正規表現

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
実行方式ファイル読み込み有ファイル読み込み無
single thread grep21.1716.15
CeriumGrep(CPU 12) mmap18.005.12
CeriumGrep(CPU 12) bread15.765.18
egrep59.5159.51
+ + - + - - + + + + - - - - + + + + + + - - - - + + + + + + - - - - + + + + + + - - - - + + + + + +
read mode \ CPU num実行方式\ FileSize(Match Num) CPU 12GPU50MB(54万)100MB(107万)500MB(536万)1GB(1072万)
mmap
0.854
94.479
single thread grep4.519.4220.6240.10
read
1.487
94.614
CeriumGrep(CPU 12) mmap8.9710.7918.0029.16
Blocked Read(SPE_ANY)
0.847
93.920
CeriumGrep(CPU 12) bread7.7510.4915.7626.83
Blocked Read(IO_0)
0.866
93.912
egrep6.4212.8059.51119.23
-
-
-

Boyer-Moore String Search

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
正規表現状態数subset後の状態数マッチ数CeriumGrep(CPU12) breadegrep
’(a|b)*a(a|b)(a|b)z’512約10万26.5870.11
’(a|b)*a(a|b)(a|b)(a|b)z’621約8万27.8976.78
’(a|b)*a(a|b)(a|b)(a|b)(a|b)z’738約4万28.8681.88
’(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)z’871約2万29.1586.93
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
実行方式time(s)
single thread grep27.13
CeriumGrep(CPU12) mmap21.58
CeriumGrep(CPU12) bread19.99
egrep28.33
-

正規表現

-
- -
-

まとめ

+

結論

-

今後の課題

+

今後の課題