# HG changeset patch # User masa # Date 1455786909 -32400 # Node ID 4b1ac04e01aaa437035a35e3e21591e95fa0d905 # Parent 3fbb30280a317fc1f204b6d61cabe671d7ae8a17 add diff -r 3fbb30280a31 -r 4b1ac04e01aa paper/c3.tex --- a/paper/c3.tex Thu Feb 18 17:14:07 2016 +0900 +++ b/paper/c3.tex Thu Feb 18 18:15:09 2016 +0900 @@ -34,17 +34,19 @@ \section{Blocked Read} mmap ではファイル読み込みを細かく設定することができないので、読み込みを制御できるように実装した。さらに、読み込みと Task が並列に動作するようにした。 -読み込みを独立した Thread で行ない、ファイルを一度に全て読み込むのではなくある程度の大きさ(Block)で読み込み、読み込まれた部分に対して並列に Task を起動する。 +読み込みを独立した Thread で行ない、ファイルをある程度の大きさ(Block)ごとに読み込む。 +そして、読み込まれた部分に対して並列に Task を起動する。 これを Blocked Read と呼び、I/O の読み込みと Task の並列化を図った。 ファイルを読み込む Task (以下、Blocked Read) と、読み込んだファイルに対して計算を行う Task を別々に生成する。 Blocked Read は一度にファイル全体を読み込むのではなく、ある程度の大きさで分割してから読み込みを行う。 分割して読み込んだ範囲に対して Task を実行する。 -図\ref{fig:BlockedReadModel} では、Task を一定の単位でまとめた Task Block ごとに生成して Task を行なっている。 +図\ref{fig:BlockedReadModel} では、Task をn 個単位でまとめた Task Block を生成する。1つのTask はファイルの長さ {\tt L} の部分を処理する。 +したがって、1つのTask Block は {\tt L x n} の部分を処理する。 + Task Block で計算される領域が Blocked Read で読み込む領域を追い越して実行してしまうと、まだ読み込まれていない領域に対して計算されてしまう。 -その問題を解決するために依存関係を適切に設定する必要がある。 -Blocked Read による読み込みが終わってから TaskBlock が起動されるようにするため、Cerium の API である wait\_for にて依存関係を設定する。 +Blocked Read による読み込みが終わってから TaskBlock が起動されるように、Cerium の API である wait\_for を使って待ち合わせを行う。 \begin{figure}[htpb] \begin{center} diff -r 3fbb30280a31 -r 4b1ac04e01aa paper/c4.tex --- a/paper/c4.tex Thu Feb 18 17:14:07 2016 +0900 +++ b/paper/c4.tex Thu Feb 18 18:15:09 2016 +0900 @@ -49,6 +49,14 @@ } \end{lstlisting} +% 箇条書きで +\verb+TASK_EXEC+ +\verb+TASK_EXEC_DATA_PARALLEL+ GPU +\verb+TASK_PRINT+ 集計 Task + +% run_start を説明する +% option を解釈して mmap や bread の説明 + 文字列処理の Task と結果の整合や表示を行う Print Task をそれぞれ決められたフォーマットに沿って記述すればよい。 ファイルを分割して文字列処理を行なった際、分割された部分でそれぞれの例題の整合性が取れなくなってしまうことがある。 @@ -91,7 +99,7 @@ \label{fig:wordcountseparate} \end{figure} -この問題の解決方法として、分割されたファイルの一つ目が文字で終わり、二つ目のファイルの先頭が改行または空白で始まった場合はそれぞれの単語数の合計数から 1 足すことにより整合性を取ることができる。 +この問題の解決方法として、分割されたファイルの一つ目が文字で終わり、二つ目のファイルの先頭が改行または空白で始まった場合はそれぞれの単語数の合計数から 1 足すことにより整合性を取ることができる。ソースコード\ref{}%check ソースコード\ref{src:Exec}は Word Count のメインルーチンである。 % 分割されたファイルを先頭から見ていき、まずは先頭が空白か改行かどうかをチェックする。 @@ -252,6 +260,7 @@ Boyer-Moore String Search は文字列処理の Task を生成する前に、Skip Table を生成している。 そして Boyer-Moore String Search に必要な情報を bm という構造体にまとめ、この構造体をそれぞれの Task に送信している。 (ソースコード\ref{src:bmTMmain}) +%check global の説明 \begin{lstlisting}[frame=lrbt,label=src:bmTMmain,caption=Boyer-Moore String Search の TMmain,numbers=left] typedef struct bm { @@ -525,10 +534,10 @@ これらのルールに則って正規表現木を構成し、それを元に DFA・NFA を生成していく。 \newpage -\subsection{正規表現木から DFA・NFA の生成} +\subsection{正規表現木への状態の割当} -次に正規表現木から非決定性有限オートマトン(NFA)、決定性有限オートマトン(DFA)を生成する。 -メタ文字のノードが現れた時に一定のルールに沿って文字のノードに状態を割り振っていく。 +次に正規表現木に状態を割り当てて、非決定性有限オートマトン(NFA)を生成する。 +正規表現木のノードに対して一定のルールに沿って状態を割り当てていく。 \begin{itemize} \item 左子ノードが `*' でない `+' は新しい状態を作る @@ -538,6 +547,8 @@ ノードに状態を割り振りながら次の状態の遷移先を設定することによって、オートマトンによる状態遷移を表現することができる。 +([a-zA-Z]|ab*)*aa + \begin{figure}[htpb] \begin{center} \includegraphics[scale=0.17]{images/regex/allostate.pdf} @@ -546,30 +557,30 @@ \label{fig:allostate} \end{figure} -これにより、正規表現木に状態の割り振りを行ない、入力を行なったら状態が遷移するようにできた。 -現在の状態(current state)と入力(input)によって次の状態(next state)が一意に決まっており、それをテーブル化して正規表現をファイルにかける。(図\ref{fig:dfaregex}) -このように、ある状態にある入力を与えると次の状態の遷移先が一意に決まるオートマトンのとこを決定性オートマトン(DFA)という。 - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.20]{images/regex/dfaregex.pdf} - \end{center} - \caption{どの状態もある入力を与えたとしても遷移先は一意に決定される(DFA)} - \label{fig:dfaregex} -\end{figure} - -生成された正規表現木によっては、現在の状態と入力による次の状態が一意に決まらない場合もある。 -1 つの入力に対して遷移先が複数存在するようなオートマトンを非決定性オートマトン(NFA)という。 - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.20]{images/regex/nfaex.pdf} - \end{center} - \caption{1 入力に対して遷移先が複数存在する(NFA)} - \label{fig:nfaex} -\end{figure} - -\newpage +% これにより、正規表現木に状態の割り振りを行ない、入力を行なったら状態が遷移するようにできた。 +% 現在の状態(current state)と入力(input)によって次の状態(next state)が一意に決まっており、それをテーブル化して正規表現をファイルにかける。(図\ref{fig:dfaregex}) +% このように、ある状態にある入力を与えると次の状態の遷移先が一意に決まるオートマトンのとこを決定性オートマトン(DFA)という。 +% +% \begin{figure}[htpb] +% \begin{center} +% \includegraphics[scale=0.20]{images/regex/dfaregex.pdf} +% \end{center} +% \caption{どの状態もある入力を与えたとしても遷移先は一意に決定される(DFA)} +% \label{fig:dfaregex} +% \end{figure} +% +% 生成された正規表現木によっては、現在の状態と入力による次の状態が一意に決まらない場合もある。 +% 1 つの入力に対して遷移先が複数存在するようなオートマトンを非決定性オートマトン(NFA)という。 +% +% \begin{figure}[htpb] +% \begin{center} +% \includegraphics[scale=0.20]{images/regex/nfaex.pdf} +% \end{center} +% \caption{1 入力に対して遷移先が複数存在する(NFA)} +% \label{fig:nfaex} +% \end{figure} +% +% \newpage 1 入力に対して遷移先が複数存在している場合は、文字によって場合分けをする必要がある。 図\ref{fig:nfaex} の @@ -596,13 +607,19 @@ \end{figure} \subsection{Subset Construction による状態の変換} - -Subset Construction は、ある複数の状態を 1 つの新しい状態としてまとめ、その新しい状態からの遷移先を構成する手法である。 +組み合わされた状態からそれぞれの状態の場合分けをたどって、さらに別な組み合われた状態が生成される。 +新しい状態の組み合わせが出てこなくなるまでこれを繰り返す。 +これを Subset Construction と呼ぶ。 +ここでは状態の表現に BitVector を用いる。 +1つの Bit が正規表現に割り振られた Base 状態に対応する。 +組み合わされた状態は、複数の Bit が立っていることにより表される。 +状態の組み合わせは、BitVector の論理和によって簡単に計算される。 ソースコード\ref{src:cc}は文字クラスの構造体である。正規表現木の各ノードそれぞれに、この構造体を持っている。 文字クラスは二分木で構築されており、それぞれの二分木に文字の範囲である Condition を持っている。 その Condition の範囲内の文字の入力があれば、次の状態 nextState に遷移する。 + % charclass 構造体 ソース \begin{lstlisting}[frame=lrbt,label=src:cc,caption=文字クラス(charClass)の構造体,numbers=left] typedef struct utf8Range { @@ -612,6 +629,7 @@ typedef struct condition { RangeList range; + Word w; } Condition, *ConditionList; typedef struct charClass { @@ -622,6 +640,7 @@ BitVector nextState; } CharClass, *CharClassPtr; \end{lstlisting} +%ソースコードの説明 図\ref{fig:sc} に2つの状態があり、それぞれに入力と遷移先がある。 これら 2 つの状態を一つの状態として表現し、新しく状態遷移図を生成する。