# HG changeset patch # User Masataka Kohagura # Date 1454047830 -32400 # Node ID 4e9812eb52dd8806fde9ebf2f366ca7f5ccfd7c0 # Parent b54668f3f96b748e9066aaaea67f27ca6247c967 add 0129.html diff -r b54668f3f96b -r 4e9812eb52dd 2015/0129.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2015/0129.html Fri Jan 29 15:10:30 2016 +0900 @@ -0,0 +1,215 @@ + + + + + seminar + + + + + + + + + + + + + + + + + + + + + + + +
+ +
+ + + + + + + + +
+

Cerium による文字列の並列処理

+
+
+ Masataka Kohagura +
+
+ +
+

研究目的

+ 当研究室では並列プログラミングフレームワーク Cerium を開発している。 + Cerium の例題にはファイルの読み込みと文字列処理を行う Word Count があり、先行研究では文字列処理の並列化によってプログラム全体の処理速度は向上している。 + ファイルの読み込みを含むプログラムは読み込みがオーバーヘッドとなり並列度が下がる。 + ファイルの読み込みから文字列処理までのオーバーヘッドが軽減されると、読み込みから文字列処理までの処理速度は向上する。 + また、読み込むファイルによっては 数GB 単位の大きなファイルになる可能性もあるので、ファイル読み込みのオーバーヘッドは無視できない。 + + 本研究ではファイルの読み込みまで含む文字列処理を考慮した並列処理を実装し、プログラム全体の処理速度を軽減する。 +
+ +
+

実装している正規表現エンジンの全体の要約

+
    +
  • 与えられた正規表現から正規表現木(Parser)を生成する。
    • +
  • Parser に状態を割り振り、NFA を構成する。
    • +
  • 構成した NFA を DFA に変換する。(Subset Construction)
    • +
  • DFA に変換後、読み込んだファイルと照らし合わせてファイル内の文字列が正規表現にマッチするかどうか実行する。
    • +
+
+ +
+

正規表現にマッチさせる方法

+
    +
  • DFA変換後、状態遷移を C のコードで生成してコンパイル。その実行ファイルでファイルを読み込ませてマッチング。
    • +
  • DFA変換後、状態遷移をオンデマンドに呼び実行し、状態遷移と読み込んだファイルがマッチするかどうかチェック。
    • +
+
+ + + + + + + + + +
+ +