Mercurial > hg > Papers > 2016 > masa-master

changeset 91:ca50770a7fde

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add result
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Thu, 18 Feb 2016 15:59:22 +0900
parents 497c01bb005d
children 8857808cd8e8
files paper/c5.tex paper/master_paper.pdf slide/s6/index.html
diffstat 3 files changed, 300 insertions(+), 83 deletions(-) [+]
line wrap: on
line diff
--- 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
Binary file paper/master_paper.pdf has changed
--- 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 @@
 
       <div class='slide'>
   <h2>実験1:Word Count</h2>
-  <p>全ての実験のfile size</p>
+<ul>
+    <li>FileSize : 500MB</li>
+    <li>単語数 : 約8500万</li>
+    <li>ファイル読み込みを含む時間</li>
+</ul>
 <table  border="2" cellpadding="0" cellspacing="0">
     <tbody>
         <tr>
-            <td align=center>read mode \ CPU num</td>
+            <td align=center>CPU Num\実行方式</td>
             <td></td>
-            <td align=center>CPU 1</td>
-            <td align=center>CPU 4</td>
-            <td align=center>CPU 8</td>
-            <td align=center>CPU 12</td>
-            <td align=center>GPU(CUDA)</td>
+            <td align=center>Mac(wc)</td>
+            <td align=center>mmap</td>
+            <td align=center>Blocked Read</td>
         </tr>
         <tr>
-            <td align=center>mmap</td>
-            <td></td>
-            <td>15.353</td>
-            <td>11.287</td>
-            <td>11.707</td>
-            <td>11.137</td>
-            <td><div align=right>103.410</div></td>
+            <td align=right> 1</td>
+            <td align=right></td>
+            <td align=right>10.59</td>
+            <td align=right>9.96</td>
+            <td align=right>9.33</td>
         </tr>
         <tr>
-            <td align=center>read</td>
-            <td></td>
-            <td>16.846</td>
-            <td>11.730</td>
-            <td>11.487</td>
-            <td>11.437</td>
-            <td><div align=right>106.050</div></td>
+            <td align=right>4</td>
+            <td align=right></td>
+            <td align=right>---</td>
+            <td align=right>8.63</td>
+            <td align=right>8.52</td>
         </tr>
         <tr>
-            <td align=center>Blocked Read(SPE_ANY)</td>
-            <td></td>
-            <td>13.297</td>
-            <td>11.984</td>
-            <td>10.887</td>
-            <td>11.146</td>
-            <td><div align=right>94.626</div></td>
+            <td align=right>8</td>
+            <td align=right></td>
+            <td align=right>---</td>
+            <td align=right>10.35</td>
+            <td align=right>8.04</td>
         </tr>
         <tr>
-            <td align=center>Blocked Read(IO_0)</td>
-            <td></td>
-            <td>11.503</td>
-            <td>11.437</td>
-            <td>11.365</td>
-            <td>11.412</td>
-            <td><div align=right>94.496</div></td>
-            <!--
-            <td bgcolor="#ffffcc">Blocked Read(IO_0)</td>
-            <td bgcolor="#ffffcc">99.2</td>
-            -->
+            <td align=right>12</td>
+            <td align=right></td>
+            <td align=right>---</td>
+            <td align=right>9.26</td>
+            <td align=right>7.82</td>
         </tr>
     </tbody>
 </table>
 
 <ul>
-<li> hoge </li>
-<li> <font color=red>hoge</font></li>
+    <li>FileSize : 500MB</li>
+    <li>単語数 : 約8500万</li>
+    <li>ファイル読み込みを含まない時間</li>
+</ul>
+<table  border="2" cellpadding="0" cellspacing="0">
+    <tbody>
+        <tr>
+            <td align=center>実行方式</td>
+            <td></td>
+            <td align=center>実行速度(s)</td>
+        </tr>
+        <tr>
+            <td align=right>Mac(wc)</td>
+            <td align=right></td>
+            <td align=right>4.08</td>
+        </tr>
+        <tr>
+            <td align=right>Cerium Word Count(CPU 1)</td>
+            <td align=right></td>
+            <td align=right>3.70</td>
+        </tr>
+        <tr>
+            <td align=right>Cerium Word Count(CPU 4)</td>
+            <td align=right></td>
+            <td align=right>1.00</td>
+        </tr>
+        <tr>
+            <td align=right>Cerium Word Count(CPU 8)</td>
+            <td align=right></td>
+            <td align=right>0.52</td>
+        </tr>
+        <tr>
+            <td align=right>Cerium Word Count(CPU 12)</td>
+            <td align=right></td>
+            <td align=right>0.40</td>
+        </tr>
+    </tbody>
+</table>
+
+</div>
+
+      <div class='slide'>
+    <h2>実験2 : Boyer-Moore String Search</h2>
+<ul>
+    <li>FileSize : 500MB</li>
+    <li>単語数 : 約8500万</li>
+    <li>検索文字列 : Pakistan</li>
+    <li>マッチ数 : 約400万</li>
+    <li>ファイル読み込みを含まない</li>
 </ul>
+<table  border="2" cellpadding="0" cellspacing="0">
+    <tbody>
+        <tr>
+            <td align=center>CPU Num\実行方式</td>
+            <td></td>
+            <td align=center>力任せ法</td>
+            <td align=center>Boyer-Moore String Search</td>
+        </tr>
+        <tr>
+            <td align=right> 1</td>
+            <td align=right></td>
+            <td align=right>3.17</td>
+            <td align=right>1.70</td>
+        </tr>
+        <tr>
+            <td align=right>4</td>
+            <td align=right></td>
+            <td align=right>0.87</td>
+            <td align=right>0.49</td>
+        </tr>
+        <tr>
+            <td align=right>8</td>
+            <td align=right></td>
+            <td align=right>0.47</td>
+            <td align=right>0.27</td>
+        </tr>
+        <tr>
+            <td align=right>12</td>
+            <td align=right></td>
+            <td align=right>0.33</td>
+            <td align=right>0.21</td>
+        </tr>
+    </tbody>
+</table>
+      </div>
 
+      <div class='slide'>
+    <h2>実験3:正規表現</h2>
+<ul>
+    <li>FileSize : 500MB</li>
+    <li>単語数 : 約8500万</li>
+    <li>正規表現 : ‘[A-Z][A-Za-z0-9]*s’</li>
+    <li>マッチ数 : 約536万</li>
+    <li>ファイル読み込みの有無</li>
+</ul>
+<table  border="2" cellpadding="0" cellspacing="0">
+    <tbody>
+        <tr>
+            <td align=center>実行方式</td>
+            <td></td>
+            <td align=center>ファイル読み込み有</td>
+            <td align=center>ファイル読み込み無</td>
+        </tr>
+        <tr>
+            <td align=right>single thread grep</td>
+            <td align=right></td>
+            <td align=right>21.17</td>
+            <td align=right>16.15</td>
+        </tr>
+        <tr>
+            <td align=right>CeriumGrep(CPU 12) mmap</td>
+            <td align=right></td>
+            <td align=right>18.00</td>
+            <td align=right>5.12</td>
+        </tr>
+        <tr>
+            <td align=right>CeriumGrep(CPU 12) bread</td>
+            <td align=right></td>
+            <td align=right>15.76</td>
+            <td align=right>5.18</td>
+        </tr>
+        <tr>
+            <td align=right>egrep</td>
+            <td align=right></td>
+            <td align=right>59.51</td>
+            <td align=right>59.51</td>
+        </tr>
+    </tbody>
+</table>
+
+<ul>
+    <li>ファイルサイズ : 500MB(約8500万単語)</li>
+    <li>正規表現 : ‘[A-Z][A-Za-z0-9]*s’</li>
+    <li>ファイルサイズを変更してみる</li>
+</ul>
 <table  border="2" cellpadding="0" cellspacing="0">
     <tbody>
         <tr>
-            <td align=center>read mode \ CPU num</td>
+            <td align=center>実行方式\ FileSize(Match Num)</td>
             <td></td>
-            <td align=center>CPU 12</td>
-            <td align=center>GPU</td>
+            <td align=center>50MB(54万)</td>
+            <td align=center>100MB(107万)</td>
+            <td align=center>500MB(536万)</td>
+            <td align=center>1GB(1072万)</td>
         </tr>
         <tr>
-            <td align=center>mmap</td>
-            <td></td>
-            <td><div align=right>0.854</div></td>
-            <td><div align=right>94.479</div></td>
+            <td align=right>single thread grep</td>
+            <td align=right></td>
+            <td align=right>4.51</td>
+            <td align=right>9.42</td>
+            <td align=right>20.62</td>
+            <td align=right>40.10</td>
         </tr>
         <tr>
-            <td align=center>read</td>
-            <td></td>
-            <td><div align=right>1.487</div></td>
-            <td><div align=right>94.614</div></td>
+            <td align=right>CeriumGrep(CPU 12) mmap</td>
+            <td align=right></td>
+            <td align=right>8.97</td>
+            <td align=right>10.79</td>
+            <td align=right>18.00</td>
+            <td align=right>29.16</td>
         </tr>
         <tr>
-            <td align=center>Blocked Read(SPE_ANY)</td>
-            <td></td>
-            <td><div align=right>0.847</div></td>
-            <td><div align=right>93.920</div></td>
+            <td align=right>CeriumGrep(CPU 12) bread</td>
+            <td align=right></td>
+            <td align=right>7.75</td>
+            <td align=right>10.49</td>
+            <td align=right>15.76</td>
+            <td align=right>26.83</td>
         </tr>
         <tr>
-            <td align=center>Blocked Read(IO_0)</td>
-            <td></td>
-            <td><div align=right>0.866</div></td>
-            <td><div align=right>93.912</div></td>
+            <td align=right>egrep</td>
+            <td align=right></td>
+            <td align=right>6.42</td>
+            <td align=right>12.80</td>
+            <td align=right>59.51</td>
+            <td align=right>119.23</td>
         </tr>
     </tbody>
 </table>
-</div>
 
-      <div class='slide'>
-    <h2>Boyer-Moore String Search</h2>
+<ul>
+    <li>ファイルサイズ : 500MB(約2400万単語)</li>
+    <li>ファイル読み込みを含む</li>
+    <li>正規表現の状態数を増やしてみる</li>
+</ul>
+<table  border="2" cellpadding="0" cellspacing="0">
+    <tbody>
+        <tr>
+            <td align=center>正規表現</td>
+            <td></td>
+            <td align=center>状態数</td>
+            <td align=center>subset後の状態数</td>
+            <td align=center>マッチ数</td>
+            <td align=center>CeriumGrep(CPU12) bread</td>
+            <td align=center>egrep</td>
+        </tr>
+        <tr>
+            <td align=left>’(a|b)*a(a|b)(a|b)z’</td>
+            <td align=right></td>
+            <td align=right>5</td>
+            <td align=right>12</td>
+            <td align=right>約10万</td>
+            <td align=right>26.58</td>
+            <td align=right>70.11</td>
+        </tr>
+        <tr>
+            <td align=left>’(a|b)*a(a|b)(a|b)(a|b)z’</td>
+            <td align=right></td>
+            <td align=right>6</td>
+            <td align=right>21</td>
+            <td align=right>約8万</td>
+            <td align=right>27.89</td>
+            <td align=right>76.78</td>
+        </tr>
+        <tr>
+            <td align=left>’(a|b)*a(a|b)(a|b)(a|b)(a|b)z’</td>
+            <td align=right></td>
+            <td align=right>7</td>
+            <td align=right>38</td>
+            <td align=right>約4万</td>
+            <td align=right>28.86</td>
+            <td align=right>81.88</td>
+        </tr>
+        <tr>
+            <td align=left>’(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)z’</td>
+            <td align=right></td>
+            <td align=right>8</td>
+            <td align=right>71</td>
+            <td align=right>約2万</td>
+            <td align=right>29.15</td>
+            <td align=right>86.93</td>
+        </tr>
+    </tbody>
+</table>
+
+
+<ul>
+    <li>ファイルサイズ : 500MB(約2400万単語)</li>
+    <li>正規表現 : (W|w)ork</li>
+    <li>ab が並んでいるファイルに対して全くマッチングしない正規表現を与える</li>
+    <li>ファイル読み込みを含む</li>
+</ul>
+<table  border="2" cellpadding="0" cellspacing="0">
+    <tbody>
+        <tr>
+            <td align=center>実行方式</td>
+            <td></td>
+            <td align=center>time(s)</td>
+        </tr>
+        <tr>
+            <td align=left>single thread grep</td>
+            <td align=right></td>
+            <td align=right>27.13</td>
+        </tr>
+        <tr>
+            <td align=left>CeriumGrep(CPU12) mmap</td>
+            <td align=right></td>
+            <td align=right>21.58</td>
+        </tr>
+        <tr>
+            <td align=left>CeriumGrep(CPU12) bread</td>
+            <td align=right></td>
+            <td align=right>19.99</td>
+        </tr>
+        <tr>
+            <td align=left>egrep</td>
+            <td align=right></td>
+            <td align=right>28.33</td>
+        </tr>
+    </tbody>
+</table>
       </div>
 
       <div class='slide'>
-    <h2>正規表現</h2>
-      </div>
-
-      <div class='slide'>
-    <h2>まとめ</h2>
+    <h2>結論</h2>
     <ul>
         <li> I/O と Task を分離し、同時に動くように改良し、どの環境でも安定した速度が出た。 </li>
         <li> I/O 専用の Thread の追加 </li>
@@ -436,7 +651,7 @@
         mmap でも一度に読み込む大きさを小さくすれば、Blocked Read とほぼ同じ速度が出る。
         </li>
     </ul>
-    <h2 class="yellow">今後の課題</h2>
+    <h2>今後の課題</h2>
     <ul>
         <li> Cerium の API として実装 </li>
         <li>