Mercurial > hg > Papers > 2016 > masa-master
changeset 97:c1738511433c
add tSearch Source code
| author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 18 Feb 2016 20:40:30 +0900 |
| parents | 98f32656ce56 |
| children | a099b533af0e |
| files | paper/.c4.tex.swp paper/abstract.tex paper/c4.tex paper/images/regex/bitvector.bb paper/images/regex/bitvector.pdf |
| diffstat | 5 files changed, 81 insertions(+), 1 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/abstract.tex Thu Feb 18 20:40:30 2016 +0900 @@ -0,0 +1,38 @@ +\begin{abstract} +Cerium は当研究室で開発している並列プログラミングフレームワークである。 + +従来はファイル読み込みを mmap で実装していたが、本論文では並列処理向け I/O の Blocked Read を実装を行った。 +Blocked Read とは、ファイルを一度に読み込まずに、あるサイズに分割して読み込む手法である。 + +Cerium にはファイルを読み込んで文字列処理を行う例題があり、Word Count 、Boyer-Moore String Search 、正規表現を実装し測定した。 +それぞれの例題によって結果の整合性を取る必要があるが、どのように整合性を取るかは問題によって考慮する必要がある。 + +本研究で実装した正規表現は、正規表現から正規表現木を生成し、その正規表現木に状態を割り振りながらNFA を生成する。 +もし NFA が生成した場合は Subset Construction で DFA に変換する。 +そして、DFA の生成後、ファイルとマッチングさせる。 + +それぞれの例題と Mac に built-in されている wc、egrep と比較し測定を行なった。 +\end{abstract} + +\begin{abstract_eng} +Cerium is a parallel programming framework, which developed by our laboratory. +We implemented file read with mmap in parallel string search. +It is easy to use mmap system call to read from file, but current implementation of mmap sometimes does work well. +So we implement `Blocked Read', that is reading file separated by a certain size. + +Examples of parallel string search are included in Cerium. +They are Word Count, Boyer-Moore String Search and Regular Explession. + +It needs to check for correct result in devided file every examples. + +Implemented Regular Explession sequential execute. +At first, convert Regular Explession to binary tree. +Second, allocated state to binary tree. +Third, convert state with Subset Construction. +Finally, implement parallel regular expression. + +We evaluate examples of Cerium, wc of Mac built-in, and egrep. + + + +\end{abstract_eng}
--- a/paper/c4.tex Thu Feb 18 20:32:59 2016 +0900 +++ b/paper/c4.tex Thu Feb 18 20:40:30 2016 +0900 @@ -772,11 +772,48 @@ } \end{lstlisting} +%tSearch の話 +\begin{lstlisting}[frame=lrbt,label=src:tSearch,caption=tSearch,numbers=left] +TSValue tSearch(TSValue tsv) { + next: while (tsv.buff.buffptr < tsv.buff.buffend) { + tsv = tsv.current->stateMatch(tsv); + if (tsv.current->ccvSize==0) { + // matched start again + 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; +} +\end{lstlisting} + % Print の分割部分の話追加 最後 分割されたファイルに対して正規表現によるマッチングを行う。 マッチングすると、マッチングの始まりのファイルの場所と終わりのファイルの場所を Result という構造体に格納する。 マッチングの数だけこの構造体が生成され、これらは List 構造として結果をまとめていく。 (ソースコード\ref{src:result}) -もし、分割されたファイル \begin{lstlisting}[frame=lrbt,label=src:result,caption=Resultの構造体,numbers=left] typedef struct result { unsigned char *begin;