Mercurial > hg > Papers > 2016 > masa-master

--- a/paper/c4.tex	Fri Feb 19 03:14:25 2016 +0900
+++ b/paper/c4.tex	Fri Feb 19 11:49:29 2016 +0900
@@ -762,7 +762,7 @@
 } CharClass, *CharClassPtr;
 \end{lstlisting}
 %ソースコードの説明 OK
-ソースコード\ref{src:cc}は文字クラスの構造体である。正規表現木の各ノードそれぞれにこの構造体を持っている。
+ソースコード\ref{src:cc}は文字クラスの構造体である。正規表現木の文字ノード、文字クラスノードはそれぞれこの構造体を持っている。
 文字クラスは二分木で構築されている。
 文字クラスの範囲は Condition 内の RangeList の begin と end に設定される。
 それぞれの二分木に文字の範囲である Condition を持っている。
--- a/paper/c6.tex	Fri Feb 19 03:14:25 2016 +0900
+++ b/paper/c6.tex	Fri Feb 19 11:49:29 2016 +0900
@@ -5,10 +5,7 @@
 本研究では文字列処理の並列処理の例題として、WordCount、Boyer-Moore String Search 、正規表現を実装した。
 それぞれの例題によって結果の整合性を取る必要があるが、どのように整合性を取るかは問題によって考慮する必要がある。

-本研究で実装した正規表現は、正規表現から正規表現木を生成し、その正規表現木に状態を割り振りながらNFA や DFA を生成する。
-もし NFA が存在した場合は Subset Construction で DFA に変換する。
-DFA に変換後、その DFA を元に与えられたファイルに対してマッチングさせる。
-その結果、ファイル読み込みを含め egrep と比較して最大 66 \% 速度がでる。
+ファイル読み込みを含め egrep と比較して最大 66 \% 速度がでる。

 \section{今後の課題}
--- a/paper/images/regex/bitvector.bb	Fri Feb 19 03:14:25 2016 +0900
+++ b/paper/images/regex/bitvector.bb	Fri Feb 19 11:49:29 2016 +0900
@@ -1,5 +1,5 @@
 %%Title: images/regex/bitvector.pdf
 %%Creator: extractbb 20150315
 %%BoundingBox: 0 0 672 552
-%%CreationDate: Thu Feb 18 19:38:59 2016
+%%CreationDate: Fri Feb 19 09:07:40 2016
--- a/slide/s6/index.html	Fri Feb 19 03:14:25 2016 +0900
+++ b/slide/s6/index.html	Fri Feb 19 11:49:29 2016 +0900
@@ -132,7 +132,7 @@
         ファイル読み込みの改良
         </li>
         <li>
-        Cerium 上での文字列処理の並列処理の実装(Word Count、Boyer-Moore String Search、正規表現)
+        Cerium 上での文字列処理の並列処理の実装(Word Count、Boyer-Moore  Search、正規表現)
         </li>
         </ul>
 を行なった。
@@ -149,10 +149,7 @@
  Cerium は、本研究室で開発している並列プログラミングフレームワークで、C/C++ で実装されている。
     </li>
     <li>
-    Cerium は当初 Sony Computer Entertainment 社の PlayStation3 に搭載されいた Cell 向けに開発されていた。現在では Linux、MacOSX 上で動作する。
-    </li>
-    <li>
-    Cerium は当初 Sony Computer Entertainment 社の PlayStation3 に搭載されいた Cell 向けに開発されていた。現在では Linux、MacOSX 上で動作する。
+    Cerium は当初 Sony Computer Entertainment 社の PlayStation3 に搭載されいた Cell 向けに開発されていた。現在では Linux、MacOSX、GPU 上で動作する。
     </li>
     <li>
     本研究では汎用計算フレームワークの TaskManager を利用して文字列処理の並列処理を実装した。
@@ -190,10 +187,20 @@
     <br>

     <ul>
-        <li> ファイルを一度に全て読み込むのではなく、ある程度の大きさに分けて読み込みを行う。</li>
-        <li> 読み込みが終わったら文字列処理の Task を起動する。</li>
+        <li>
+読み込みを独立した Thread で行ない、ファイルをある程度の大きさ(Block)ごとに読み込む。
+        </li>
+        <li>
+読み込まれた部分に対して並列に Task を起動する。
+        </li>
         <li>
-        ファイルが読み込まれていない領域に対して文字列処理が行われないように依存関係を設定する。
+Blocked Read と呼び、I/O の読み込みと Task の並列化を図った。
+        </li>
+        <li>
+Task をn 個単位でまとめた Task Block を生成する。1つのTask は ファイルの長さ L の部分を処理する。
+        </li>
+        <li>
+1つのTask Block は  L x n の部分を処理する。
         </li>
     </ul>
 </div>
@@ -220,6 +227,7 @@
       <div class='slide'>
     <h2>文字列処理の並列処理</h2>
     <object data="images/example/dividefile.svg" width="70%"  type="image/svg+xml"></object><br>
+    <ul>
     <li>
     ファイルをある程度の大きさに分割する。
     </li>
@@ -232,6 +240,48 @@
     <li>
     ファイルの分割部分で結果の整合性が取れない場合がある。その場合は例題によって様々な方法をとって整合を取る。
     </li>
+    </ul>
+    <p>
+    ファイルを読み込んで文字列処理をする流れを 1 つのクラスとして Cerium 内に組み込んだ。
+    このクラスは、ファイルをマッピングし処理をすることで小さいデータの集合を出力することから FileMapReduce と名付けた。
+    </p>
+      </div>
+
+      <div class='slide'>
+    <h2>FileMapReduce</h2>
+<pre>
+TMmain(TaskManager *manager, int argc, char *argv[])
+{
+    char *filename = 0;
+    FileMapReduce *fmp =
+        new FileMapReduce(manager,TASK_EXEC,TASK_EXEC_DATA_PARALLEL,TASK_PRINT);
+    filename = fmp->init(argc, argv);
+    if (filename < 0) {
+        return -1;
+    }
+    fmp->division_out_size = sizeof(unsigned long long)*4;
+    task_init();
+    fmp->run_start(manager, filename);
+    return 0;
+}
+</pre>
+    <ul>
+<li> TASK_EXEC : 計算を行う Task</li>
+<li> TASK_EXEC_DATA_PARALLEL : GPU にて計算を行う Task</li>
+<li> TASK_PRINT : 結果を集計する Task</li>
+    </ul>
+    <p>
+    fmp->init で cpu の数の設定や読み込み方法(mmap or Blocked Read)のオプションを解釈する。
+    </p>
+    <p>
+    fmp->division_out_size で計算を行う Task の出力されるデータ数を設定できる。
+    </p>
+    <p>
+    run_start で計算を行う Task とファイル読み込みを行う Task が生成される。さらに依存関係が設定される。
+    </p>
+    <p>
+計算を行う Task と結果の整合や表示を行う Print Task をそれぞれ決められたフォーマットに沿って記述すればよい。
+    </p>
       </div>

       <div class='slide'>
@@ -257,87 +307,255 @@
       </div>

       <div class='slide'>
-    <h2>Boyer-Moore String Search</h2>
-    <object data="images/example/bmsearchinclude.svg" width="50%"  type="image/svg+xml"></object><br>
-    <object data="images/example/bmsearchsame.svg" width="50%"  type="image/svg+xml"></object><br>
-    <object data="images/example/bmsearchthink.svg" width="50%"  type="image/svg+xml"></object><br>
+    <h2>Boyer-Moore  Search</h2>
+    <p>
+    文字列検索を高速に行うアルゴリズム
+力任せ法との大きな違いは、text と pattern を先頭から比較するのではなく、 pattern の末尾から比較していくことである。
+    </p>
     <ul>
 <li>pattern に含まれていない文字で不一致した場合は、 pattern の長さだけ後ろにずらす。</li>
 <li>pattern に含まれている文字の場合は、pattern の長さから pattern に含まれている文字の位置を引いた数だけ後ろにずらす。</li>
 <li>pattern に含まれている文字でその文字が pattern に複数含まれている場合は後ろにずらす量も複数現れる。その中の最小の値だけ後ろにずらす。</li>
     </ul>
+    <object data="images/example/bmsearchinclude.svg" width="50%"  type="image/svg+xml"></object><br>
+    <object data="images/example/bmsearchsame.svg" width="50%"  type="image/svg+xml"></object><br>
+    <object data="images/example/bmsearchthink.svg" width="50%"  type="image/svg+xml"></object><br>
       </div>

       <div class='slide'>
-    <h2>正規表現マッチャ(Cerium Grep)の実装</h2>
-    <object data="images/regex/regexbasic.svg" width="50%"  type="image/svg+xml"></object><br>
+    <h2>正規表現マッチャの実装</h2>
     <ul>
-<li>与えられた正規表現を構文解析し、正規表現木に変換する。</li>
-<li>正規表現木から非決定性オートマトン(以下、NFA)か決定性オートマトン(以下、DFA)に変換する。</li>
-<li>Subset Construction による NFA から DFA への変換をおこなう。</li>
-<li>DFA を元に文字列検索を行ない結果を返す。</li>
+<li>与えられた正規表現を構文解析し、正規表現木に変換</li>
+<li>正規表現木への状態の割当</li>
+<li>Subset Construction による状態の変換</li>
+<li>正規表現マッチャの並列処理の実装</li>
     </ul>
-
-      </div>
-
-
-      <div class='slide'>
-    <h2>parser</h2>
-    <object data="images/regex/parser.svg" width="50%"  type="image/svg+xml"></object><br>
-      </div>
-
-      <div class='slide'>
-    <h2>連接</h2>
-    <object data="images/regex/regexseq.svg" width="50%"  type="image/svg+xml"></object><br>
-    <object data="images/regex/regexseq2.svg" width="50%"  type="image/svg+xml"></object><br>
+    <p>サポートする正規表現の演算子</p>
+<table  border="2" cellpadding="0" cellspacing="0">
+    <tbody>
+        <tr>
+            <td align=center>AB</td>
+            <td align=left>連続した文字(連接)</td>
+        </tr>
+        <tr>
+            <td align=center>A*</td>
+            <td align=left>直前の文字の 0 回以上の繰返し</td>
+        </tr>
+        <tr>
+            <td align=center>A|B</td>
+            <td align=left>A または B(選択)</td>
+        </tr>
+        <tr>
+            <td align=center>[A-Z]</td>
+            <td align=left>AからZの範囲内のうち任意の一文字(文字クラス)</td>
+        </tr>
+        <tr>
+            <td align=center>( )</td>
+            <td align=left>演算の優先度の明示(グループ)</td>
+        </tr>
+    </tbody>
+</table>
       </div>


       <div class='slide'>
-    <h2>| の接続</h2>
-    <object data="images/regex/regexselect.svg" width="50%"  type="image/svg+xml"></object><br>
+    <h2>正規表現から正規表現木の生成</h2>
+    <object data="images/regex/parser.svg" width="50%"  type="image/svg+xml"></object><br>
+<pre>
+static
+NodePtr regexAtom(RegexInfoPtr ri) {
+
+    NodePtr n = NULL;
+    if (ri->tokenType == 'c') n = charClass(ri);
+    else if (ri->tokenType == 'a') n = literal(ri);
+    else if (ri->tokenType == '(') {
+        n = regex(ri);
+        if (ri->tokenType != ')') {
+            // error
+            fprintf(stderr,"unclosed ')' before %s \n", ri->ptr);
+            return createNode(ri,0,0,0,0);
+        }
+        token(ri);
+    }
+    if (ri->tokenType == '*') {
+        n = createNode(ri,'*',0,n,0);
+        token(ri);
+    }
+    return n;
+}
+
+NodePtr regex(RegexInfoPtr ri) {
+    token(ri);
+    NodePtr n = regexAtom(ri);
+    while (ri->tokenType) {
+        if (ri->tokenType == '*') {
+            n = createNode(ri,'*',0,n,0);
+            token(ri);
+            return n;
+        } else if (ri->tokenType == '|') {
+            n = createNode(ri,'|',0,n,0);
+            NodePtr n1 = regex(ri);
+            n->right = n1;
+        } else if (ri->tokenType == ')') {
+            return n;
+        } else if (ri->tokenType == ']') {
+            // error
+            return n;
+        } else {
+            n = createNode(ri,'+',0,n,0);
+            NodePtr n1 = regexAtom(ri);
+            n->right = n1;
+        }
+    }
+    return n;
+}
+</pre>
+<ul>
+<li>
+正規表現木を二分木で生成する。
+</li>
+<li>
+文字列を token で一文字ずつ読み込み、文字によってノードの結合方法が変わる。
+</li>
+<li>
+regexAtom で文字を一文字読み込む。
+</li>
+<li>
+'*' が読み込まれたら左ノードに接続する。
+</li>
+<li>
+'|' が読み込まれたら左ノードに接続し、右ノードは再帰で返されたノードを接続する。
+</li>
+<li>
+それ以外(文字か文字クラス)が読み込まれたら左ノードに接続する。そして右ノードは regexAtom で返されたノードを接続する。
+</li>
+</ul>
+
       </div>

       <div class='slide'>
-    <h2>* の組み合わせ</h2>
-    <object data="images/regex/regexasta.svg" width="50%"  type="image/svg+xml"></object><br>
+    <h2>正規表現木をオートマトンの状態遷移に沿って状態割当</h2>
+    <object data="images/regex/allostate.svg" width="50%"  type="image/svg+xml"></object><br>
+
+<pre>
+TGValue generateTransition(NodePtr n,TGValue tgv, int pass) {
+    if (n->tokenType == '+') {
+        TGValue tgvLeft = tgv;
+        tgvLeft.endState = n->right->state;
+        tgvLeft.asterisk = NULL;
+        tgvLeft = generateTransition(n->left,tgvLeft,pass);
+        TGValue tgvRight = tgv;
+        if (tgvLeft.asterisk) {
+            n->right->state = tgv.endState;
+            tgvRight.startState = tgvLeft.asterisk;
+            tgvRight = generateTransition(n->right,tgvRight,pass);
+            tgvLeft.asterisk = tgvRight.asterisk;
+            return tgvLeft;
+        }
+        tgvRight.asterisk = NULL;
+        if (pass==1) {
+            n->right->state = tgvRight.startState = createState(tgvRight,n->right);
+        } else {
+            tgvRight.startState = n->right->state;
+            tgvRight.tg->stateArray[tgvRight.startState->bitState.bitContainer] = tgvRight.startState ;
+        }
+        tgvRight = generateTransition(n->right,tgvRight,pass);
+        if (tgv.endState && tgvRight.asterisk) tgvRight.startState->accept = tgv.endState->accept;
+        tgvLeft.asterisk = tgvRight.asterisk;
+        return tgvLeft;
+    } else if (n->tokenType == '|') {
+        TGValue tgv1  = generateTransition(n->left,tgv,pass);
+        tgv1.endState = tgv.endState;
+        TGValue tgv2 = generateTransition(n->right,tgv1,pass);
+        return tgv2;
+    } else if (n->tokenType == '*') {
+        TGValue tgvAstah = tgv;
+        tgvAstah.endState = tgvAstah.startState;
+        if (pass==2) tgvAstah.endState->accept = tgv.endState->accept;
+        tgvAstah = generateTransition(n->left,tgvAstah,pass);
+        tgvAstah.asterisk = tgvAstah.startState;
+        return tgvAstah;
+    } else if (n->tokenType == 'c' || n->tokenType == 'a'){
+        TGValue tgv1 = tgv;
+        if (pass==1) {
+            n->stateNum = tgv.startState->stateNum;
+            n->state = tgv.startState;
+        } else {
+            int nextState = tgv.endState->stateNum;
+            n->nextStateNum = nextState;
+            n->nextState = tgv.endState;
+            BitVector bi = createBitVector(nextState);
+            if (n->nextState->accept) bi = bitSet(bi,1);
+            setState(n->cc,bi);
+            tgv1.startState->cc = mergeTransition(tgv1.startState,n->cc);
+        }
+        return tgv1;
+    } else {
+        return tgv;
+    }
+}
+</pre>
+
+    <ul>
+    <li>
+    tgv は
+    </li>
+    <li>
+    </li>
+    <li>
+    </li>
+    <li>
+    </li>
+    </ul>
       </div>

       <div class='slide'>
-    <h2> | * の接続</h2>
-    <object data="images/regex/regexgroup.svg" width="50%"  type="image/svg+xml"></object><br>
-      </div>
-
-      <div class='slide'>
-    <h2>正規表現の連接</h2>
-    <object data="images/regex/regexseqregex.svg" width="50%"  type="image/svg+xml"></object><br>
+    <h2>1入力で複数の状態遷移先があれば、その状態をまとめる</h2>
+    <object data="images/regex/nfa.svg" width="30%"  type="image/svg+xml"></object><br>
+    <ul>
+    <li>
+1 入力に対して遷移先が複数存在している場合は、文字によって場合分けをする必要がある。
+    </li>
+    <li>
+状態 4 は [a-z] が入力されると状態 4 に遷移し、b が入力されると状態 2 に遷移する。このとき、b が入力されると状態 2 か状態 4 のどちらかに遷移することになる。
+    </li>
+    </ul>
+    <object data="images/regex/dfa.svg" width="30%"  type="image/svg+xml"></object><br>
+    <ul>
+    <li>
+1 入力に対して遷移先が複数存在している場合は、文字によって場合分けをする必要がある。
+    </li>
+    <li>
+このとき、状態 2 と 4 を組み合わせて一つの状態を新しく作り、その状態に遷移させる。新しく作られる状態の数は状態の組み合わせなので、その状態の組み合わせの和をとっている。
+    </li>
+    <li>
+このような変換をすることによって、入力によって遷移先が一意に決定されるようになる。
+    </li>
+    </ul>
       </div>


       <div class='slide'>
-    <h2>正規表現木をオートマトンの状態遷移に沿って状態割当</h2>
-    <object data="images/regex/allostate.svg" width="50%"  type="image/svg+xml"></object><br>
-      </div>
-
-      <div class='slide'>
-    <h2>DFA</h2>
-    <object data="images/regex/dfaregex.svg" width="50%"  type="image/svg+xml"></object><br>
+    <h2>Bit Pattern での状態の表現</h2>
+    <object data="images/regex/bitvector.svg" width="50%"  type="image/svg+xml"></object><br>
+    <ul>
+    <li>
+状態の表現に BitVector を用いる。
+    </li>
+    <li>
+1つの Bit が正規表現に割り振られた Base 状態に対応する。
+    </li>
+    <li>
+組み合わされた状態は、複数の Bit が立っていることにより表される。
+    </li>
+    <li>
+状態の組み合わせは、BitVector の論理和によって簡単に計算される。
+    </li>
+    </ul>
       </div>

       <div class='slide'>
-    <h2>NFA</h2>
-    <object data="images/regex/nfaex.svg" width="50%"  type="image/svg+xml"></object><br>
-      </div>
-
-
-      <div class='slide'>
-    <h2>1入力で複数の状態遷移先があれば、その状態をまとめる</h2>
-    <object data="images/regex/nfa.svg" width="30%"  type="image/svg+xml"></object><br>
-    <object data="images/regex/dfa.svg" width="30%"  type="image/svg+xml"></object><br>
-      </div>
-
-      <div class='slide'>
-    <h2>文字クラスの構造</h2>
+    <h2>文字クラスの構造体</h2>
 <pre>
 typedef struct utf8Range {
     unsigned long begin;
@@ -346,6 +564,7 @@

 typedef struct condition {
     RangeList range;
+    Word w;
 } Condition, *ConditionList;

 typedef struct charClass {
@@ -356,33 +575,45 @@
     BitVector nextState;
 } CharClass, *CharClassPtr;
 </pre>
+    <ul>
+    <li>
+    正規表現木の文字ノードもしくは文字クラスノードこの構造体を持っている。
+    </li>
+    <li>
+    文字クラスは二分木で構築されている。
+    </li>
+    <li>
+    文字クラスの範囲は Condition 内の RangeList の begin と end に設定される。
+    </li>
+    <li>
+    その Condition の範囲内の文字の入力があれば、次の状態 nextState に遷移する。
+    </li>
+    </ul>
       </div>

       <div class='slide'>
-    <h2>cc tree merge pattern</h2>
-    <object data="images/regex/CharClassMergePattern.svg" width="50%"  type="image/svg+xml"></object><br>
-      </div>
-
-
-      <div class='slide'>
     <h2>Subset Construction</h2>
     <object data="images/regex/sc.svg" width="50%"  type="image/svg+xml"></object><br>
-      </div>
-
-
-      <div class='slide'>
-    <h2>Bit Pattern での状態の表現</h2>
+    <ul>
+    <li>
+組み合わされた状態からそれぞれの状態の場合分けをたどって、さらに別な組み合われた状態が生成される。
+    </li>
+    <li>
+新しい状態の組み合わせが出てこなくなるまでこれを繰り返す。
+    </li>
+    </ul>
       </div>

+<!--
       <div class='slide'>
-    <h2>State Array</h2>
-    <object data="images/regex/statearray.svg" width="50%"  type="image/svg+xml"></object><br>
+    <h2>cc tree merge pattern</h2>
+    <object data="images/regex/CharClassMergePattern.svg" width="50%"  type="image/svg+xml"></object><br>
       </div>
-
-      <div class='slide'>
-    <h2>正規表現の整合性</h2>
-    <object data="images/regex/regexdivide.svg" width="50%"  type="image/svg+xml"></object><br>
-      </div>
+-->
+  <div class='slide'>
+<h2>正規表現の整合性</h2>
+<object data="images/regex/regexdivide.svg" width="50%"  type="image/svg+xml"></object><br>
+  </div>

       <div class='slide'>
 <h2>実験概要</h2>
@@ -392,6 +623,9 @@
     <li>CPU：2*2.66GHz 6-Core Intel Xeon</li>
     <li>HDD :  1TB 7200 rpm SATA 3.0 Gbps </li>
 </ul>
+<p>
+mmapとbread はファイルの読み込み方式である。bread は Blocked Read を用いたときの結果である。
+</p>
       </div>

       <div class='slide'>
@@ -407,8 +641,8 @@
             <td align=center>CPU Num\実行方式</td>
             <td></td>
             <td align=center>Mac(wc)</td>
-            <td align=center>mmap</td>
-            <td align=center>Blocked Read</td>
+            <td align=center>Cerium wc (mmap)</td>
+            <td align=center>Cerium wc (bread)</td>
         </tr>
         <tr>
             <td align=right> 1</td>
@@ -440,6 +674,11 @@
         </tr>
     </tbody>
 </table>
+<p>
+wc は 10.59秒で実行され、bread を用いた Cerium Word Count は CPU 12 のとき 7.82 秒となる。
+Cerium wc が最大 1.4 倍速くなった。
+</p>
+

 <ul>
     <li>FileSize : 500MB</li>
@@ -480,11 +719,16 @@
         </tr>
     </tbody>
 </table>
+<p>
+ファイル読み込みを含まない場合、wc と比較して最大10.2倍速くなった。
+1 CPU と 12 CPU で比較すると、9.25 倍ほど速くなった。
+</p>
+

 </div>

       <div class='slide'>
-    <h2>実験2 : Boyer-Moore String Search</h2>
+    <h2>実験2 : Boyer-Moore Search</h2>
 <ul>
     <li>FileSize : 500MB</li>
     <li>単語数 : 約8500万</li>
@@ -498,7 +742,7 @@
             <td align=center>CPU Num\実行方式</td>
             <td></td>
             <td align=center>力任せ法</td>
-            <td align=center>Boyer-Moore String Search</td>
+            <td align=center>Boyer-Moore Search</td>
         </tr>
         <tr>
             <td align=right> 1</td>
@@ -526,10 +770,13 @@
         </tr>
     </tbody>
 </table>
+<p>
+ファイル読み込みを含まないで計測している。力任せ法と比較すると、Boyer-Moore Search が最大 63 % ほど速くなる。
+</p>
       </div>

       <div class='slide'>
-    <h2>実験3:正規表現</h2>
+    <h2>実験3:正規表現(1/2)</h2>
 <ul>
     <li>FileSize : 500MB</li>
     <li>単語数 : 約8500万</li>
@@ -571,6 +818,11 @@
         </tr>
     </tbody>
 </table>
+<p>
+single thread grep や CeriumGrep は繰返し実行をすると実行速度が短くなる。 これは、読み込んだファイルがキャッシュに残っており、ファイル読み込みが省略されるためである。
+しかし egrep は繰返し実行しても毎回ファイルを読み込みにいく。
+CeriumGrep(CPU 12)bread で検索すると、egrep で検索するよりも 4 倍ほど速くなる。
+</p>

 <ul>
     <li>ファイルサイズ : 500MB(約8500万単語)</li>
@@ -621,7 +873,13 @@
         </tr>
     </tbody>
 </table>
+<p>
+ファイルサイズが小さいと single thread grep や egrep のほうが速い。
+</p>
+      </div>

+      <div class='slide'>
+    <h2>実験3:正規表現(2/2)</h2>
 <ul>
     <li>ファイルサイズ : 500MB(約2400万単語)</li>
     <li>ファイル読み込みを含む</li>
@@ -676,7 +934,11 @@
         </tr>
     </tbody>
 </table>
-
+<p>
+egrep はバックトラックを行う grep である。
+バックトラックは、正規表現を先頭から読み込み、'|' や '*' が読み込まれた時に前に戻って再度マッチングさせる。
+CeriumGrep は'(a|b)'を増加させることで 1 秒ほどの増加で抑えられるが、egrep だと 5,6 秒ほど増加する。
+</p>

 <ul>
     <li>ファイルサイズ : 500MB(約2400万単語)</li>
@@ -713,35 +975,25 @@
         </tr>
     </tbody>
 </table>
+<p>
+全くマッチングしない場合も CeriumGrep bread が最も良い結果を出した。
+</p>
       </div>

+
+
       <div class='slide'>
     <h2>結論</h2>
     <ul>
-        <li> I/O と Task を分離し、同時に動くように改良し、どの環境でも安定した速度が出た。 </li>
-        <li> I/O 専用の Thread の追加 </li>
-        <li>
-        mmap でも一度に読み込む大きさを小さくすれば、Blocked Read とほぼ同じ速度が出る。
-        </li>
+        <li>並列処理時のファイルの読み込みについて改良を行なった結果、最大13\%速くなる。</li>
+        <li>ファイル読み込みを含め egrep と比較して最大 66 %速度がでる。</li>
     </ul>
     <h2>今後の課題</h2>
     <ul>
-        <li> Cerium の API として実装 </li>
-        <li>
-        様々な実装の試み<br>(I/O threads を 2つ使用したプログラム、分割 mmap)
-        </li>
-        <li>
-        様々な環境での測定
-        </li>
-        <li>
-        grepの実装
-        </li>
+        <li>文字単位に状態を割り振るのではなく、文字列単位に状態を割り振ることで状態数を抑える</li>
+        <li>現段階の実装では、最大の状態数は 64 に制限されている</li>
+        <li>状態数を抑えることで、より長い正規表現を検索できるようになる。</li>
     </ul>
-      </div>
-
-
-      <div class='slide'>
-    <h2>状態をまとめる</h2>
     <object data="images/regex/wordstate.svg" type="image/svg+xml" width="50%"></object><br>
       </div>