# HG changeset patch # User Masataka Kohagura # Date 1455014595 -32400 # Node ID 49614a7deaaab61069d339fec05a20c997c16f5e # Parent 466a8ed9c372cdd79996dbd79b391a5ecb0e3b69 c1 diff -r 466a8ed9c372 -r 49614a7deaaa c1.tex --- a/c1.tex Tue Feb 09 18:59:23 2016 +0900 +++ b/c1.tex Tue Feb 09 19:43:15 2016 +0900 @@ -1,9 +1,15 @@ \chapter{introduction} -正規表現はオートマトンに変換することができ、そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。 -この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。 -コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。 -本研究では Cerium 上に正規表現を実装することにより。 +世界中のサーバには様々な情報や Log が保管されており、それらのテキストファイル全体のデータサイズを合計すると TB 単位ととても大きなサイズになると予想される。 +それらの中から特定の文字列や正規表現によるパターンマッチングを探すなどの文字列処理には膨大な時間がかかる。 +検索時間を短縮するためには、ファイルの読み込み時間を軽減し、プログラムの並列度をあげる必要がある。 -word count などを早く処理するため -I/Oの並列化 -膨大なファイル +Cerium は並列プログラミングフレームワークであり当研究室で開発している。 +文字列処理を Cerium に実装するにあたり、ファイルの読み込み方法について改良を行なった。 +ファイルの読み込みを行なったあとに文字列処理が走っていたが、ファイルの読み込みと文字列処理が同時に走るように改良した。 + +文字列の並列処理の例題として、Word Count、Boyer Moore String Search、正規表現の実装を行なった。 +文字列処理を並列実行する際、ファイルを一定の大きさに分割して、それぞれに対して文字列処理を行う。 +それぞれの分割されたファイルに対して処理を行なったあと、結果が出力される。 +それぞれの結果を合計する際に、分割された部分に対して各例題様々な工夫をすることによって整合性を取る必要がある。 + +本論文では文字列処理だけでなくファイルの読み込みまでを含む文字列処理を考慮した並列処理を実装し、処理全体の速度を上げるような実装を行なった。 diff -r 466a8ed9c372 -r 49614a7deaaa c4.tex --- a/c4.tex Tue Feb 09 18:59:23 2016 +0900 +++ b/c4.tex Tue Feb 09 19:43:15 2016 +0900 @@ -449,9 +449,15 @@ \subsection{Subset Construction による NFA から DFA の変換} +on the fly +subset construction で使わない状態は生成しないで済む \subsection{DFA を元にパターンマッチを行う} +\subsection{(Word をノードに含める話)} + +IBM stream processing + \begin{figure}[htpb] \begin{center} \includegraphics[scale=0.2]{images/regex/dfa.pdf} diff -r 466a8ed9c372 -r 49614a7deaaa master_paper.pdf Binary file master_paper.pdf has changed