Mercurial > hg > Papers > 2016 > masa-master

<!DOCTYPE html>
<html>
  <head>
    <meta charset='utf-8'>
    <title>sigos</title>

    <!--
         Notes on CSS media types used:

         1) projection -> slideshow mode (display one slide at-a-time; hide all others)
         2) screen     -> outline mode (display all slides-at-once on screen)
         3) print      -> print (and print preview)

         Note: toggle between projection/screen (that is, slideshow/outline) mode using t-key

         Questions, comments?
         - send them along to the mailinglist/forum online @ http://groups.google.com/group/webslideshow
      -->

    <!-- style sheet links -->
    <link rel="stylesheet/less" href="themes/blank/projection.css.less"  media="screen,projection">
    <link rel="stylesheet/less" href="themes/blank/screen.css.less"      media="screen">
    <link rel="stylesheet/less" href="themes/blank/print.css.less"       media="print">

    <link rel="stylesheet/less" href="themes/blank/blank.css.less"    media="screen,projection">

    <!-- Notes about less css support
         - all less stylesheets (*.css.less) need to get listed/loaded first (before the less.js script)
         - find more info about less.js online @ http://lesscss.org

         ***** NOTE:
         less.js browser script currently won’t work if you’re using Google Chrome
         and the path to your page starts with "file:///" due to a known Chrome issue.
         (In the developer/js console you will see:
         XMLHttpRequest cannot load file:///../s6/shared/projection.css.less.
         Cross origin requests are only supported for HTTP.)
      -->

    <!-- add js libs (less, jquery) -->
    <script src="js/less-1.1.4.min.js"></script>
    <script src="js/jquery-1.7.min.js"></script>

    <!-- S6 JS -->
    <script src="js/jquery.slideshow.js"></script>
    <script src="js/jquery.slideshow.counter.js"></script>
    <script src="js/jquery.slideshow.controls.js"></script>
    <script src="js/jquery.slideshow.footer.js"></script>
    <script src="js/jquery.slideshow.autoplay.js"></script>
    <script>
      $(document).ready( function() {
      Slideshow.init();

      // Example 2: Start Off in Outline Mode
      // Slideshow.init( { mode: 'outline' } );

      // Example 3: Use Custom Transition
      // Slideshow.transition = transitionScrollUp;
      // Slideshow.init();

      // Example 4: Start Off in Autoplay Mode with Custom Transition
      // Slideshow.transition = transitionScrollUp;
      // Slideshow.init( { mode: 'autoplay' } );
      } );
    </script>

    <!-- Better Browser Banner for Microsoft Internet Explorer (IE) -->
    <!--[if IE]>
        <script src="js/jquery.microsoft.js"></script>
        <![endif]-->

  </head>
  <body>
    <div class="layout">
      <div id="header"></div>
      <div id="footer">
        <div align="right">
          <img src="images/concurrency.png" width="200">
        </div>
      </div>
    </div>

    <div class="presentation">

      <!-- add slides here; example -->

      <div class='slide cover'>
        <table width="90%" height="90%" border="0" align="center">
          <tr>
            <td><div align="center">
                <h1><font color="#808db5">Cerium による文字列処理の並列処理</font></h1>
            </div></td>
          </tr>
          <tr>
            <td><div align="left">
                Masataka Kohagura,Shinji Kono,
                <script>
                  var date = new Date();
                  var year = date.getFullYear();
                  var month = date.getMonth();
                  var day = date.getDate();

                  var monthList = new Array("January","February","March","April","May","June",
                  "July","August","September","October","November","December");

                  document.write(monthList[month]+" "+day+", "+year);

                </script>
                <hr style="color:#ffcc00;background-color:#ffcc00;text-align:left;border:none;width:300%;height:0.2em;">
            </div></td>
          </tr>
        </table>
      </div>

        <!--

        -->
      <div class='slide'>
        <h2>文字列処理の並列処理</h2>
        <p>
世界中のサーバには様々な情報や Log が保管されており、それらのテキストファイル全体のデータサイズを合計すると TB 単位ととても大きなサイズになると予想される。
</p>
        <p>
それらの中から特定の文字列や正規表現によるパターンマッチングを探すなどの文字列処理には膨大な時間がかかる。
検索時間を短縮するためには、ファイルの読み込み時間を軽減し、プログラムの並列度をあげる必要がある。
        </p>
        <p>
Cerium は並列プログラミングフレームワークであり当研究室で開発している。本研究では、
        </p>
        <p>
        <ul>
        <li>
        ファイル読み込みの改良
        </li>
        <li>
        Cerium 上での文字列処理の並列処理の実装(Word Count、Boyer-Moore  Search、正規表現)
        </li>
        </ul>
を行なった。
    </p>
<p>
文字列処理だけでなくファイルの読み込みまでを含む文字列処理を考慮した並列処理を実装し、処理全体の速度を上げるような実装を行なった。
        </p>
      </div>

      <div class='slide'>
    <h2>Cerium Task Manager</h2>
    <ul>
    <li>
 Cerium は、本研究室で開発している並列プログラミングフレームワークで、C/C++ で実装されている。
    </li>
    <li>
    Cerium は当初 Sony Computer Entertainment 社の PlayStation3 に搭載されいた Cell 向けに開発されていた。現在では Linux、MacOSX、GPU 上で動作する。
    </li>
    <li>
    本研究では汎用計算フレームワークの TaskManager を利用して文字列処理の並列処理を実装した。
    </li>
    </ul>
      </div>


      <div class='slide'>
    <h2>mmap の特徴</h2>
    これまで Cerium での文字列処理の例題では File 読み込みを mmap にて行なっていた。
    <br>
    <object data="images/cerium/mmap.svg" width="40%" type="image/svg+xml"></object><br>
    <br>

    <ul>
      <li>
      mmap は、仮想メモリ空間にファイルの中身を対応させ、そのメモリ空間に
      アクセスされたら、 OS が読み込みを行う。<br>
      </li>
      <li>
      code の記述はシンプルだが、スレッドが読み込み終わるまで待たされる。 <br>
      </li>
      <li>
      読み込みが OS 依存となるので、環境に左右されやすく、読み込みを細かく制御することが難しい。
      </li>
    </ul>
      </div>

      <div class='slide'>
    <h2>読み込みながら文字列処理を行う Blocked Read</h2>
    <p>mmap を使用せずに、読み込みを独立したスレッドで実行させる。そして、読み込んだ部分に対して Task を並列に起動する。
    </p>
    <br>
    <object data="images/cerium/blockedread.svg" width="70%" type="image/svg+xml"></object><br>
    <br>

    <ul>
        <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>

      <div class='slide'>
    <h2>I/O 専用 threadの追加</h2>
    <li>
    Blocked Read は読み込みを含む処理なので、処理時間が大きくなる。
    </li>
    <li>
    Cerium では読み込みや文字列処理の Task に対してデバイスを設定することができる。SPE_ANY 設定を利用すると Cerium 側が自動的に割り振りを行う。
    </li>
    <li>
    自動的にデバイスを割り振ると、Blocked Read Task 間に Task が割り込まれる可能性があり、読み込みが遅延する恐れがある。
    </li>
    <object data="images/cerium/speblockedread.svg" width="80%"  type="image/svg+xml"></object><br>

    <li>
    デバイスの設定に I/O専用 thread の IO_0 を追加して、他の Task に割り込まれないようにした。
    </li>
    <object data="images/cerium/iothread.svg"  width="80%"  type="image/svg+xml"></object><br>
      </div>

      <div class='slide'>
    <h2>文字列処理の並列処理</h2>
    <object data="images/example/dividefile.svg" width="70%"  type="image/svg+xml"></object><br>
    <ul>
    <li>
    ファイルをある程度の大きさに分割する。
    </li>
    <li>
    分割したファイルに対してそれぞれに文字列処理を行う。
    </li>
    <li>
    結果の集計後、Print Task にて結果を表示する。
    </li>
    <li>
    ファイルの分割部分で結果の整合性が取れない場合がある。その場合は例題によって様々な方法をとって整合を取る。
    </li>
    </ul>
    <p>
    ファイルを読み込んで文字列処理をする流れを 1 つのクラスとして Cerium 内に組み込んだ。
    このクラスは、ファイルをマッピングし処理をすることで小さいデータの集合を出力することから FileMapReduce と名付けた。
    </p>
    <p>FileMapReduce を利用するメリット</p>
    <ul>
    <li>
    cpu の数の設定や読み込み方法(mmap or Blocked Read)のオプションを解釈する。
    </li>
    <li>
    計算を行う Task とファイル読み込みを行う Task が生成される。さらに依存関係が設定される。
    </li>
    <li>
計算を行う Task と結果の整合や表示を行う Print Task をそれぞれ決められたフォーマットに沿って記述すればよい。
    </li>
    <p></p>
      </div>

<!--
      <div class='slide'>
    <h2>FileMapReduce を利用した Task の記述 </h2>
    <p>
    Task の生成で渡された DATA を w->global で受け取ることができる。
    </p>
    <p>
    o_data にはTask の結果を格納する。これは、Print Task に渡される data である。
    </p>
      </div>

      <div class='slide'>
    <h2>Print の記述 </h2>
    <p>
    Task の o_data で渡されたデータを Print Task で集計する。
    </p>
    <p>
    例題によって分割された部分の処理が必要である。その処理もここに記述する。
    </p>
      </div>
-->


      <div class='slide'>
    <h2>文字列処理の例題 : Word Count</h2>
    <object data="images/example/wordcount.svg" width="70%"  type="image/svg+xml"></object><br>
    <li>
    Word Count は読み込んだファイルの単語数を数える。
    </li>
    <li>
    改行が読み込まれたら行数のカウントを増やし、空白または改行が読み込まれたら単語数のカウントを増やす。
    </li>

    <object data="images/example/wordcountseparate.svg" width="70%"  type="image/svg+xml"></object><br>
    <li>
    1つ目の分割されたファイルは空白または改行が 1 つしか無いため、単語数 1 となってしまっている。
    </li>
    <li>
    ファイルの先頭の空白または改行の場合、単語数はカウントされない。
    </li>
    <li>
    このように分割された場合、分割されたファイルの一つ目の末尾が文字で終わり、二つ目のファイルの先頭が改行または空白で始まった場合はそれぞれの単語数の合計数に1加えることにより整合性を取ることができる。
    </li>
      </div>

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

      <div class='slide'>
    <h2>正規表現マッチャの実装</h2>
    今回実装した正規表現マッチャのアルゴリズムは以下の通りである。
    <ul>
<li>与えられた正規表現を構文解析し、正規表現木に変換</li>
<li>正規表現木への状態の割当</li>
<li>Subset Construction による状態の変換</li>
<li>正規表現マッチャの並列処理の実装</li>
    </ul>
    <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>
    <p>正規表現木を二分木で構成する。</p>
    <object data="images/regex/parser.svg" width="50%"  type="image/svg+xml"></object><br>
<ul>
<li>
文字列を一文字ずつ読み込み、文字の種類によってノードの結合方法を変える。
</li>
<li>
'*' が読み込まれたら左ノードに接続する。
</li>
<li>
'|' が読み込まれたら左ノードに接続し、右ノードは再帰で返されたノードを接続する。
</li>
<li>
それ以外(文字か文字クラス)が読み込まれたら左ノードに接続する。そして右ノードはその後に続く文字を接続する。
</li>
</ul>

      </div>

      <div class='slide'>
    <h2>文字クラスの構造体</h2>
<pre>
typedef struct utf8Range {
    unsigned long begin;
    unsigned long end;
} RangeList , *RangeListPtr;

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

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

      <div class='slide'>
    <h2>正規表現木をオートマトンの状態遷移に沿って状態割当</h2>
    <object data="images/regex/allostate.svg" width="50%"  type="image/svg+xml"></object><br>

    <ul>
    <li>
    '+'ノードの左に'*'無かった場合は、右のノードに新しく状態を作る。
    </li>
    <li>
    '|' のとき、左右のノードの先頭の状態に同じ状態を割り振る。
    </li>
    <li>
    '*' のとき、先頭の状態と'*'を子にしている親ノードの後ろのノードと同じ状態にする。
    </li>
    </ul>
      </div>

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


      <div class='slide'>
    <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>並列処理時の正規表現のマッチング</h2>
<pre>
typedef struct tState {
    State *state;
    tsValue (*stateSkip)(tsValue);
    tsValue (*stateMatch)(tsValue);
    int ccvSize;
    CCVPtr ccv;
} TState, *TStatePtr;
</pre>

<ul>
<li>
tState は状態を持ってる。
</li>
<li>
文字クラスの Range の情報と状態の遷移先は ccv に格納している。
</li>
<li>
ある状態が Range にマッチする文字が入力された場合は次の状態に遷移する。
</li>
<li>
ある状態が受理状態で Range にマッチしない文字が入力されたら、tState->stateSkip には stateSkip、tState->stateMatch には stateMatch を設定する。<br>
受理状態でない場合は、tState->stateMatch には stateNothing を設定する。
</li>
<li>
tState は新しい状態に遷移するときに初めて生成される。<br>
thread ごとに on the fly で生成されるので、使わない状態は生成されない。
</li>
</ul>
      </div>


  <div class='slide'>
<h2>マッチング結果の Print</h2>
<pre>
typedef struct result {
    unsigned char *begin;
    unsigned char *end;
    bool continued;
    struct result *next;
} Result, *ResultPtr;
</pre>
<ul>
<li>
Result はマッチした結果を保存するための構造体である。
</li>
<li>
マッチングの始まりと終わりの位置を保存する。
</li>
<li>
マッチングの数だけこの構造体が生成される。これらは List 構造として結果をまとめていく。
</li>
<li>
全ての分割されたファイルに対してマッチングが終了すると、Print Task にてまとめてマッチした部分を表示する。
</li>
</ul>
</div>

<div class='slide'>
<h2>ファイル分割時の処理</h2>
<p>
正規表現をファイル分割して並列処理をする際、本来マッチングする文章がファイル分割によってマッチングしない場合がある。
</p>
<object data="images/regex/regexdivide.svg" width="60%"  type="image/svg+xml"></object><br>
<p>
再度マッチするかどうかは Print Task で行われる。
<p>
  </div>

      <div class='slide'>
<h2>実験概要</h2>
<p>実験環境</p>
<ul>
    <li>OS：MacOS 10.10.5</li>
    <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'>
  <h2>実験1:Word Count</h2>
<ul>
    <li>FileSize : 500MB</li>
    <li>単語数 : 約8500万</li>
    <li>ファイル読み込みを含む時間</li>
</ul>
<table  border="2" cellpadding="0" cellspacing="0">
    <tbody>
        <tr>
            <td align=center>CPU Num\実行方式</td>
            <td></td>
            <td align=center>Mac(wc)</td>
            <td align=center>Cerium wc (mmap)</td>
            <td align=center>Cerium wc (bread)</td>
        </tr>
        <tr>
            <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=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=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=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>
<p>
wc は 10.59秒で実行され、bread を用いた Cerium Word Count は CPU 12 のとき 7.82 秒となる。
Cerium wc が最大 1.4 倍速くなった。
</p>


<ul>
    <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>
<p>
ファイル読み込みを含まない場合、wc と比較して最大10.2倍速くなった。
1 CPU と 12 CPU で比較すると、9.25 倍ほど速くなった。
</p>


</div>

      <div class='slide'>
    <h2>実験2 : Boyer-Moore 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 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>
<p>
ファイル読み込みを含まないで計測している。力任せ法と比較すると、Boyer-Moore Search が最大 63 % ほど速くなる。
</p>
      </div>

      <div class='slide'>
    <h2>実験3:正規表現(1/2)</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>
<p>
egrep は繰返し実行しても、ファイルがキャッシュに入らない。毎回ファイルを読み込みにいく。
CeriumGrep(CPU 12)bread で検索すると、egrep で検索するよりも 4 倍ほど速くなる。
</p>

<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>実行方式\ FileSize(Match Num)</td>
            <td></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=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=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=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=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>
<p>
ファイルサイズが小さいと single thread grep や egrep のほうが速い。
</p>
      </div>

      <div class='slide'>
    <h2>実験3:正規表現(2/2)</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>
<p>
egrep はバックトラックを行う grep である。
バックトラックは、正規表現を先頭から読み込み、'|' や '*' が読み込まれた時に前に戻って再度マッチングさせる。
CeriumGrep は'(a|b)'を増加させることで 1 秒ほどの増加で抑えられるが、egrep だと 5,6 秒ほど増加する。
</p>

<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>
<p>
全くマッチングしない場合も CeriumGrep bread が最も良い結果を出した。
</p>
      </div>


      <div class='slide'>
    <h2>結論</h2>
    <ul>
        <li>並列処理時のファイルの読み込みについて改良を行なった結果、最大13%速くなる。</li>
        <li>ファイル読み込みを含め egrep と比較して最大 66 %速度がでる。</li>
    </ul>
    <h2>今後の課題</h2>
    <ul>
        <li>文字単位に状態を割り振るのではなく、文字列単位に状態を割り振ることで状態数を抑える</li>
        <li>現段階の実装では、最大の状態数は 64 に制限されている</li>
        <li>状態数を抑えることで、より長い正規表現を検索できるようになる</li>
        <li>このときの検索を Boyer-Moore Search で行うことでさらに高速化できることが期待される</li>
    </ul>
    <object data="images/regex/wordstate.svg" type="image/svg+xml" width="30%"></object><br>
      </div>

      <div class='slide'>
    <h2>Search 部分のソースコード</h2>
<pre>
TSValue tSearch(TSValue tsv) {
    next: while (tsv.buff.buffptr < tsv.buff.buffend) {
        tsv = tsv.current->stateMatch(tsv);
        if (tsv.current->ccvSize==0) {
            tsv.current = tsv.tg->stateStart->tState;
        }
        unsigned char c = *tsv.buff.buffptr++;
        for (int i = 0; i < tsv.current->ccvSize; i++) {
            CCVPtr ccv = &tsv.current->ccv[i];
            if (c<ccv->begin) {
                tsv.current = tsv.tg->stateStart->tState;
                tsv = tsv.current->stateSkip(tsv);
                goto next;
            } else if (c<=ccv->end) {
                // range matched.
                if (ccv->w.word) {
                    // match the word.
                    // if (not match) continue;
                }
                if (ccv->tState) {
                    tsv.current = ccv->tState;
                } else {
                    tsv.current = nextTState(ccv->state,tsv.tg);
                    ccv->tState = tsv.current;
                }
                goto next;
            }
        }
        tsv.current = tsv.tg->stateStart->tState;
        tsv = tsv.current->stateSkip(tsv);
    }
    return tsv;
}
</pre>
    <ul>
    <li>
    </li>
    <li>
    </li>
    </ul>
      </div>

</div> <!-- presentation -->
</body>
</html>
author	Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
date	Fri, 26 Feb 2016 17:40:40 +0900
parents	199561d48b97
children