Mercurial > hg > Papers > 2016 > masa-master
annotate paper/c5.tex @ 67:9c16f6b18100
add result
| author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 16 Feb 2016 17:54:07 +0900 |
| parents | 5defec0399f9 |
| children | c01a514d33f7 |
| rev | line source |
|---|---|
| 53 | 1 \chapter{ベンチマーク} |
| 2 本項で行なった実験の環境は以下の通りである。 | |
| 3 \begin{itemize} | |
| 4 \item Mac OS X 10.10.5 | |
| 5 \item 2*2.66 GHz 6-Core Intel Xeon | |
| 6 \item Memory 16GB 1333MHz DDR3 | |
| 7 \item 1TB HDD | |
| 8 \end{itemize} | |
| 45 | 9 |
| 66 | 10 Cerium で実装した Word Count と Mac の wc の比較と、実装した正規表現と Mac の egrep の比較を行なった。 |
| 56 | 11 また、それぞれの結果に実装した並列処理向け I/O の結果も含む。 |
| 54 | 12 |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
13 \section{Word Count} |
| 56 | 14 ファイルの大きさは 約500MByte で、このファイルには 約650万行、約8300万単語が含まれている。 |
| 66 | 15 |
| 16 表\ref{table:IOwordcount} は、ファイル読み込みを含めた Word Count の結果である。 | |
| 17 Mac の wc ではこのファイルを処理するのに 10.59 秒かかる。それに対して、Cerium Word Count は mmap Blocked Read 全ての状況で Mac の wc よりも速いことを示している。 | |
| 18 Cerium Word Count 12 CPU のとき、7.83 秒で処理をしており、Mac の wc の 1.4 倍ほど速くなっている。 | |
| 19 | |
| 20 mmap は読み込みを OS が制御しており、書き手が制御できない。 | |
| 21 また Word Count が走る際ファイルアクセスはランダムアクセスとなる。 | |
| 22 mmap はランダムアクセスを想定していなくてグラフにばらつきが起こっていると考えられる。 | |
| 23 Blocked Read では読み込みをプログラムの書き手が制御しており、ファイルの読み込みもファイルの先頭から順次読み込みを行なっている。 | |
| 24 そのため、読み込みを含めた結果にばらつきが起こりにくくなっていると予想される。 | |
| 25 | |
| 26 \begin{tiny} | |
| 27 \begin{table}[ht] | |
| 28 \begin{center} | |
| 29 \begin{tabular}[t]{|r|r|r|r|} | |
| 30 \hline | |
| 31 CPU Num / 実行方式 & Mac(wc) & mmap & Blocked Read\\ | |
| 32 \hline | |
| 33 1 & 10.590 & 9.96 & 9.33 \\ | |
| 34 \hline | |
| 35 4 & --- & 8.63 & 8.52 \\ | |
| 36 \hline | |
| 37 8 & --- & 10.35 & 8.04 \\ | |
| 38 \hline | |
| 39 12 & --- & 9.26 & 7.82 \\ | |
| 40 \hline | |
| 41 \end{tabular} | |
| 42 \caption{ファイル読み込みを含む Word Count} | |
| 43 \label{table:IOwordcount} | |
| 44 \end{center} | |
| 45 \end{table} | |
| 46 \end{tiny} | |
| 47 | |
| 48 \newpage | |
| 49 表\ref{fig:wordcount} はファイル読み込みを含まない Word Count の結果である。 | |
| 50 | 50 |
| 56 | 51 Mac の wc ではこのファイルを処理するのに 4.08 秒かかる。それに対して、Cerium Word Count は 1 CPU で 3.70 秒、12 CPU だと 0.40 秒で処理できる。 |
| 53 | 52 |
| 56 | 53 1 CPU で動作させると Mac の wc よりも 1.1 倍ほど速くなり、12 CPU で動作させると wc よりも 10.2 倍ほど速くなった。 |
| 66 | 54 1 CPU と 12 CPU で比較すると、9.25 倍ほど速くなった。 |
| 56 | 55 |
| 66 | 56 ファイルを読み込んだ結果と比較すると、ファイルを読み込まないで実行したほうが 6,7 秒ほど速くなる。 |
| 57 これよりファイルを読み込んだ文字列処理の場合、処理時間の60\%から90\% はファイルの読み込みであることがわかる。 | |
| 53 | 58 |
| 56 | 59 \begin{tiny} |
| 60 \begin{table}[ht] | |
| 61 \begin{center} | |
| 66 | 62 \begin{tabular}[t]{|r|r|} |
| 56 | 63 \hline |
| 64 実行方式 & 実行速度(秒)\\ | |
| 65 \hline | |
| 66 Mac(wc) & 4.08 \\ | |
| 67 \hline | |
| 68 Cerium Word Count(CPU 1) & 3.70\\ | |
| 69 \hline | |
| 70 Cerium Word Count(CPU 4) & 1.00\\ | |
| 71 \hline | |
| 72 Cerium Word Count(CPU 8) & 0.52\\ | |
| 73 \hline | |
| 74 Cerium Word Count(CPU 12) & 0.40\\ | |
| 75 \hline | |
| 76 \end{tabular} | |
| 77 \caption{ファイル読み込み無しの Word Count} | |
| 78 \label{fig:wordcount} | |
| 79 \end{center} | |
| 80 \end{table} | |
| 81 \end{tiny} | |
| 54 | 82 |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
83 \section{正規表現} |
| 66 | 84 当実験では、Mac の egrep 、C で実装した逐次に DFA の状態遷移と照らし合わせる CGrep、Cerium で並列処理をする CeriumGrep を比較している。 |
| 47 | 85 |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
86 表\ref{table:AZaz} は正規表現 '[A-Z][A-Za-z0-9]*s' を 500MB(単語数約8500万)、1GB(単語数約1.7億語)のファイルに対してマッチングを行なった。 |
| 53 | 87 |
| 56 | 88 \begin{tiny} |
| 89 \begin{table}[ht] | |
| 90 \begin{center} | |
| 66 | 91 \begin{tabular}[t]{|c|r|r|r|} |
| 56 | 92 \hline |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
93 実行方式/File Size(Match Num) & 500MB(536万) & 1GB(1072万) \\ |
| 56 | 94 \hline |
| 66 | 95 CGrep & 20.62 & 40.10\\ |
| 56 | 96 \hline |
| 65 | 97 CeriumGrep(CPU 12) mmap & 18.00 & 26.96\\ |
| 56 | 98 \hline |
| 65 | 99 CeriumGrep(CPU 12) bread & 12.48 & 21.14\\ |
| 56 | 100 \hline |
| 65 | 101 egrep & 59.51 & 119.23\\ |
| 56 | 102 \hline |
| 103 \end{tabular} | |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
104 \caption{ファイルサイズを変化させた各 grep の結果} |
| 56 | 105 \label{table:AZaz} |
| 106 \end{center} | |
| 107 \end{table} | |
| 108 \end{tiny} | |
| 109 | |
| 65 | 110 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 66 | 111 |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
112 表\ref{table:metachar} 500MB(単語数約8500万) のファイルに対して正規表現 '[A-Z][A-Za-z0-9]*s' をマッチングした結果である。 |
|
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
113 これはファイル読み込みを含めた結果と読み込みを含めていない結果の比較である。 |
|
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
114 egrep は実行するたびにファイル読み込みを行うため、ファイル読み込み無しの測定はなし。 |
| 66 | 115 \begin{tiny} |
| 116 \begin{table}[ht] | |
| 117 \begin{center} | |
| 118 \begin{tabular}[t]{|c|r|r|} | |
| 119 \hline | |
| 120 実行方式 & ファイル読み込み有 & ファイル読み込み無\\ | |
| 121 \hline | |
| 122 CGrep & 21.171 & 16.150\\ | |
| 123 \hline | |
| 124 CeriumGrep(CPU 2) & 27.061 & 15.401\\ | |
| 125 \hline | |
| 126 CeriumGrep(CPU 12) & 12.48 & 7.386\\ | |
| 127 \hline | |
| 128 egrep & 59.51 & --- \\ | |
| 129 \hline | |
| 130 \end{tabular} | |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
131 \caption{ファイル読み込み有りと無しを変化させた各 grep の結果} |
| 66 | 132 \label{table:metachar} |
| 133 \end{center} | |
| 134 \end{table} | |
| 135 \end{tiny} | |
| 136 | |
| 137 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 65 | 138 表\ref{table:abab} |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
139 aとb が多く含まれている約500MB(単語数約2300万)のファイルに対して、正規表現の状態数を変化させてみた。 |
|
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
140 これは読み込みを含んでいる結果で、CeriumGrep のファイル読み込みは Blocked Read、CPU 数 12 にて実行した。 |
| 65 | 141 |
| 142 \begin{tiny} | |
| 143 \begin{table}[ht] | |
| 144 \begin{center} | |
| 66 | 145 \begin{tabular}[t]{|l|r|r|r|} |
| 65 | 146 \hline |
| 147 正規表現 & マッチ数 & CeriumGrep time (s) & egrep time(s)\\ | |
| 148 \hline | |
| 66 | 149 '(a \textbar b)*a(a \textbar b)(a \textbar b)' & 約1950万 & 38.67 & 86.66 \\ |
| 65 | 150 \hline |
| 66 | 151 '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)' & 約1640万 & 38.72 & 94.25 \\ |
| 65 | 152 \hline |
| 66 | 153 '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)' & 約1640万 & 39.59 & 100.98 \\ |
| 65 | 154 \hline |
| 66 | 155 '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)' & 約1550万 & 38.68 & 104.82 \\ |
| 65 | 156 \hline |
| 157 \end{tabular} | |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
158 \caption{正規表現の状態数を増やした Grep の結果} |
| 65 | 159 \label{table:abab} |
| 160 \end{center} | |
| 161 \end{table} | |
| 162 \end{tiny} | |
| 163 | |
| 164 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 53 | 165 |
| 66 | 166 表\ref{table:nomatch} ab の文字列がならんでいるところに (W \textbar w)ord の正規表現 |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
167 aとb が多く含まれている約500MB(単語数約2300万)のファイルに対して、全くマッチしない正規表現を与えてパターンマッチングさせてみた。 |
| 61 | 168 |
| 169 \begin{tiny} | |
| 170 \begin{table}[ht] | |
| 171 \begin{center} | |
| 66 | 172 \begin{tabular}[t]{|c|r|} |
| 61 | 173 \hline |
| 66 | 174 実行方式/File Size(Match Num) & time (s)\\ |
| 61 | 175 \hline |
| 66 | 176 CGrep & 27.130\\ |
| 61 | 177 \hline |
| 66 | 178 CeriumGrep(CPU 12) mmap & 21.576\\ |
| 61 | 179 \hline |
| 66 | 180 CeriumGrep(CPU 12) bread & 19.986\\ |
| 61 | 181 \hline |
| 66 | 182 egrep & 28.332\\ |
| 61 | 183 \hline |
| 184 \end{tabular} | |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
185 \caption{全くマッチングしないパターンを grep した結果} |
|
62
0d13c52a54fd
remove bm_search explain
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
186 \label{table:nomatch} |
| 61 | 187 \end{center} |
| 188 \end{table} | |
| 189 \end{tiny} | |
| 190 | |
| 66 | 191 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 192 % | |
| 193 % 表\ref{table:abab} | |
| 194 % | |
| 195 % \begin{tiny} | |
| 196 % \begin{table}[ht] | |
| 197 % \begin{center} | |
| 198 % \begin{tabular}[t]{|r|r|r|r|} | |
| 199 % \hline | |
| 200 % CPU Num / 実行方式 & egrep & mmap & Blocked Read\\ | |
| 201 % \hline | |
| 202 % 1 & 83.09 & 57.65 & 40.49 \\ | |
| 203 % \hline | |
| 204 % 2 & --- & 43.96 & 33.72 \\ | |
| 205 % \hline | |
| 206 % 4 & --- & 33.37 & 34.26 \\ | |
| 207 % \hline | |
| 208 % 8 & --- & 35.48 & 32.46 \\ | |
| 209 % \hline | |
| 210 % \end{tabular} | |
| 211 % \caption{abab} | |
| 212 % \label{table:abab} | |
| 213 % \end{center} | |
| 214 % \end{table} | |
| 215 % \end{tiny} | |
| 216 % |