Mercurial > hg > Papers > 2016 > masa-master
changeset 15:c686d33ba1c7
change file name
| author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Wed, 20 Jan 2016 16:16:46 +0900 |
| parents | e7cbdb30cf74 |
| children | a3c5125aea03 |
| files | benchmark.tex c1.tex c2.tex c3.tex c4.tex c5.tex c6.tex cerium.tex ceriumex.tex conclusion.tex images/image.graffle implregex.tex introduction.tex master_paper.tex paper.mm |
| diffstat | 15 files changed, 524 insertions(+), 353 deletions(-) [+] |
line wrap: on
line diff
--- a/benchmark.tex Tue Jan 19 18:11:19 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1 +0,0 @@ -\chapter{ベンチマーク}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/c1.tex Wed Jan 20 16:16:46 2016 +0900 @@ -0,0 +1,9 @@ +\chapter{introduction} +正規表現はオートマトンに変換することができ、そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。 +この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。 +コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。 +本研究では Cerium 上に正規表現を実装することにより。 + +word count などを早く処理するため +I/Oの並列化 +膨大なファイル
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/c2.tex Wed Jan 20 16:16:46 2016 +0900 @@ -0,0 +1,231 @@ +\chapter{Cerium} +Cerium は、Cell 向けに開発された並列プログラミングフレームワークである。 +Cell は Sony Computer Entertainment 社が販売した PlayStation3 に搭載されているヘテロジニアスマルチコア・プロセッサである。 +本章では Cerium の実装について説明する。 + +\section{Cerium の概要} +Cerium は当初 Cell 向けに開発され、C/C++ で実装されている。 +現在では Linux、 MacOS X 上で動作する並列プログラミングフレームワークである。 + +Cerium は TaskManager、SceneGraph、Rendering Engine の3要素から構成されている。 +本研究では汎用計算フレームワークである TaskManager を利用して文字列の並列計算を行なった。 + +図\ref{fig:TaskManager}は Cerium が Task の生成/実行する場合のクラス構成図である。 +TaskManager で依存関係が解消され、実行可能になった Task は ActiveTaskList に格納される。 +ActiveTaskList に格納された Task は、依存関係が解消されているのでどのような順番で実行されても問題はない。 +Task は転送を行いやすい TaskList に変換され、CpuType に対応した Scheduler に転送される。 +なお、転送はSynchronozed Queue である mail を通して行われる。 + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.7]{images/cerium/createTask.pdf} + \end{center} + \caption{Task Manager} + \label{fig:TaskManager} +\end{figure} + +\newpage + +\section{Cerium TaskManager} +Cerium TaskManager では、処理の単位を Task として記述していく。 +関数やサブルーチンを Task として取り扱い、その Task にて Input Data/Output Data 及び Task の依存関係を設定する。 +そして Task は設定された依存関係を考慮しながら実行される。 + +Input Data で格納した 2 つの数を乗算し、Output Data に演算結果を格納する multiply という例題のソースコード\ref{src:createTask}を以下に示す。 + +また、Task の生成時に用いる API 一覧を表\ref{table:TaskCreateAPI}に示す。 +\begin{lstlisting}[frame=lrbt,label=src:createTask,caption=Task の生成,numbers=left] +multi_init(TaskManager *manager) +{ + float *A, *B, *C; + + // create Task + HTaskPtr multiply = manager->create_task(MULTIPLY_TASK); + + // set device + multiply->set_cpu(SPE_ANY); + + // set inData + multiply->set_inData(0, (memaddr)A, sizeof(float)*length); + multiply->set_inData(1, (memaddr)B, sizeof(float)*length); + + // set outData + multiply->set_outData(0, (memaddr)C, sizeof(float)*length); + + // set parameter + multiply->set_param(0,(long)length); + + // spawn task + multiply->spawn(); +} +\end{lstlisting} + +\begin{tiny} + \begin{table}[ht] + \begin{center} + \label{table:TaskCreateAPI} + \small + \begin{tabular}[t]{c|l} + \hline + create\_task& Task を生成する \\ + \hline + set\_inData & Task への入力データのアドレスを追加 \\ + \hline + set\_outData & Task への出力データのアドレスを追加 \\ + \hline + set\_param & Task へ値を一つ渡す。ここでは length \\ + \hline + set\_cpu & Task を実行するデバイスの設定 \\ + \hline + spawn & 生成した Task を TaskList に set \\ + \hline + \end{tabular} + \caption{Task 生成における API} + \end{center} + \end{table} +\end{tiny} + +次に、デバイス側で実行される Task のソースコードを\ref{src:task}に示す。 +\begin{lstlisting}[frame=lrbt,label=src:task,caption=Task,numbers=left] +static int +run(SchedTask *s) { + // get input + float *i_data1 = (float*)s->get_input(0); + float *i_data2 = (float*)s->get_input(1); + + // get output + float *o_data = (float*)s->get_output(0); + + // get parameter + long length = (long)s->get_param(0); + + // calculate + for (int i=0; i<length; i++) { + o_data[i] = i_data1[i] * i_data2[i]; + } + return 0; +} +\end{lstlisting} +また表\ref{table:taskAPI}は Task 側で利用する API である。 +Task 生成時に設定した Input Data や parameter を取得することができる。 + +\begin{tiny} + \begin{table}[ht] + \begin{center} + \caption{Task 側で使用する API} + \label{table:taskAPI} + \small + \begin{tabular}[t]{c|l} + \hline + get\_input & Scheduler から input data を取得 \\ + \hline + get\_output & Scheduler から output data を取得 \\ + \hline + get\_param & set\_param した値を取得 \\ + \hline + \end{tabular} + \end{center} + \end{table} +\end{tiny} + +\newpage + +Task 生成時に設定できる要素を以下に列挙する。 + +\begin{itemize} +\item Input Data +\item Output Data +\item Parameter +\item CpuType +\item Dependency +\end{itemize} + +Input/Output Data、Parameter は関数の引数に相当する。 +Cpu Type は Task を動作させるデバイスを設定することができ、Dependency は他の Task との依存関係を設定することができる。 +\newpage +\section{並列処理向け I/O} +ファイル読み込みなどの I/O を含むプログラムは、読み込み時間が Task の処理時間と比較してオーバーヘッドになることが多い。 +計算処理の並列化を図ったとしても I/O がボトルネックになってしまい処理全体が高速にならない。 +本項では Cerium に実装した並列処理用 I/O を行ない、I/O 部分の高速化を図った。 + +Cerium の例題ではファイル読み込みを mmap にて実装していた。 +しかし、mmap だとファイルを読み込んでから Task を実行するので、読み込んでいる間は他の CPU が動作せず並列度が落ちる。 + +mmap は function call 後にすぐにファイルを読みに行くのではなく、仮想メモリ領域にファイルの中身を対応させる。 +その後メモリ空間にアクセスされたときに、OS が対応したファイルを読み込む。 +また、読み込む方法が OS 依存となってしまうため環境に左右されやすく、プログラムの書き手が読み込みの制御をすることが難しい。 + +図\ref{fig:mmap}は mmap で読み込んだファイルに対して Task1 、 Task2 がアクセスしてそれぞれの処理を行うときのモデルである。 + +Task1 が実行されると仮想メモリ上に対応したファイルが読み込まれ、読み込み後 Task1 の処理が行われる。 +その後 Task2 も Task1 と同様の処理が行われるが、これら 2 つの Task の間に待ちが入る。 + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.7]{images/cerium/mmap.pdf} + \end{center} + \caption{mmap Model} + \label{fig:mmap} +\end{figure} + +mmap を使わず、読み込みを独立した Thread で行ない、ファイルを一度に全て読み込むのではなくある程度の大きさ(Block)分読み込み、読み込まれた部分に対して並列に Task を起動する。 +これを Blocked Read と呼び、高速化を図った。 + +Blocked Read を実装するにあたり、WordCount を例題に挙げる。 +ファイルを読み込む Task (以下、ReadTask) と、読み込んだファイルに対して計算を行う Task (以下、WordCount) を別々に生成する。ReadTask は一度にファイル全体を読み込むのではなく、ある程度の大きさで分割してから読み込みを行う。分割して読み込んだ範囲に対して WordCount を行う。 + +WordCount を Blocked Read で読み込み処理をしたとき以下の図\ref{fig:BlockedRead}の様になる。 + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.5]{./images/cerium/blockedread.pdf} + \end{center} + \caption{BlockedRead による WordCount} + \label{fig:BlockedRead} +\end{figure} + +Task を一定の単位でまとめた Task Block ごとに生成して WordCount を行なっている。 +Task Block で計算される領域が Blocked Read で読み込む領域を追い越して実行してしまうと、まだ読み込まれていない領域に対して計算されてしまう。 +その問題を解決するために依存関係を適切に設定する必要がある。 +Blocked Read による読み込みが終わってから TaskBlock が起動されるようにするため、Cerium の API である wait\_for にて依存関係を設定する。 + +また、ReadTask は連続で処理される必要がある。 +なぜならば、ReadTask でファイルを読み込む前提で WordCount がその領域に対して計算を行うので、ReadTask の処理が遅くなってしまうだけでオーバーヘッドとなってしまう。\ref{fig:BlockedReadModel} + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.5]{./images/cerium/blockedreadimage.pdf} + \end{center} + \caption{BlockedRead Model} + \label{fig:BlockedReadModel} +\end{figure} + +\newpage +Blocked Read を実装することにより、読み込み部分と処理部分の並列化を行なった。Blocked Read は連続で読み込まれる必要があるため、さらに I/O 専用 thread を実装した。 + +Cerium Task Manager では、それぞれの Task に対してデバイスを設定することができる。 +SPE\_ANY 設定をすると、Task Manager が CPU の割り振りを自動的に行う。 +Blocked Read は連続で読み込まれなければならないが、SPE\_ANY で設定すると Blocked Read 間に別の Task が割り込まれる恐れがある。(図\ref{fig:spe_any_blockedread}) + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.7]{./images/cerium/speblockedread.pdf} + \end{center} + \caption{BlockedRead と Task を同じ thread で動かした場合} + \label{fig:spe_any_blockedread} +\end{figure} + +Task が Blocked Read 間に割り込まれないようにするため、I/O 専用 thread である iO\_0 の設定を追加した。 + +IO\_0 は SPE\_ANY とは別 thread の scheduler で動作するので、SPE\_ANY で動作している Task に割り込むことはない。 +しかし、読み込みの終了を通知し、次の read を行う時に他の Task がスレッドレベルで割り込んでしまう事がある。 +pthread\_getschedparam() で IO\_0 の priority の設定を行う必要がある(図:\ref{fig:iothread_blockedread})。 +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.7]{./images/cerium/iothread.pdf} + \end{center} + \caption{IO Thread による BlockedRead} + \label{fig:iothread_blockedread} +\end{figure} + +IO\_0 で実行される Task は Blocked Read のみで、さらに IO\_0 の priority を高く設定することにより Blocked Read が他の Task に割り込まれることなく連続に実行される。
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/c3.tex Wed Jan 20 16:16:46 2016 +0900 @@ -0,0 +1,86 @@ +\chapter{正規表現の設計と実装} +\section{正規表現構文木の生成} +\section{Transition List の生成} +\section{Subset Construction} +\section{Cerium 上での実装} + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/implementation/CharClassMergePattern.pdf} + \end{center} + \caption{2つの Character Class を merge するときの全パターン} + \label{fig:CharClassMergePattern} +\end{figure} + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/implementation/ccinsert1.pdf} + \end{center} + \caption{Character Class を二分木で表示} + \label{fig:ccinsert1} +\end{figure} + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/implementation/ccinsert2.pdf} + \end{center} + \caption{ある Character Class の二分木に対して、新しい Character Class を insert} + \label{fig:ccinsert2} +\end{figure} + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/implementation/ccinsertresult.pdf} + \end{center} + \caption{insert 後の Character Class の二分木} + \label{fig:ccinsertresult} +\end{figure} + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/implementation/cfab.pdf} + \end{center} + \caption{cfab} + \label{fig:cfab} +\end{figure} + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/implementation/cfdg.pdf} + \end{center} + \caption{cfdg} + \label{fig:cfdg} +\end{figure} + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/implementation/cfdgab.pdf} + \end{center} + \caption{cfdgab} + \label{fig:cfdgab} +\end{figure} + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/implementation/efgi.pdf} + \end{center} + \caption{efgi} + \label{fig:efgi} +\end{figure} + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/implementation/dfa.pdf} + \end{center} + \caption{dfa} + \label{fig:dfa} +\end{figure} + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/implementation/nfa.pdf} + \end{center} + \caption{nfa} + \label{fig:nfa} +\end{figure} +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/c4.tex Wed Jan 20 16:16:46 2016 +0900 @@ -0,0 +1,3 @@ +\chapter{Cerium による文字列処理の例題} +\section{WordCount} +\section{Boyer Moore Search}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/c5.tex Wed Jan 20 16:16:46 2016 +0900 @@ -0,0 +1,1 @@ +\chapter{ベンチマーク}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/c6.tex Wed Jan 20 16:16:46 2016 +0900 @@ -0,0 +1,1 @@ +\chapter{結論}
--- a/cerium.tex Tue Jan 19 18:11:19 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,231 +0,0 @@ -\chapter{Cerium} -Cerium は、Cell 向けに開発された並列プログラミングフレームワークである。 -Cell は Sony Computer Entertainment 社が販売した PlayStation3 に搭載されているヘテロジニアスマルチコア・プロセッサである。 -本章では Cerium の実装について説明する。 - -\section{Cerium の概要} -Cerium は当初 Cell 向けに開発され、C/C++ で実装されている。 -現在では Linux、 MacOS X 上で動作する並列プログラミングフレームワークである。 - -Cerium は TaskManager、SceneGraph、Rendering Engine の3要素から構成されている。 -本研究では汎用計算フレームワークである TaskManager を利用して文字列の並列計算を行なった。 - -図\ref{fig:TaskManager}は Cerium が Task の生成/実行する場合のクラス構成図である。 -TaskManager で依存関係が解消され、実行可能になった Task は ActiveTaskList に格納される。 -ActiveTaskList に格納された Task は、依存関係が解消されているのでどのような順番で実行されても問題はない。 -Task は転送を行いやすい TaskList に変換され、CpuType に対応した Scheduler に転送される。 -なお、転送はSynchronozed Queue である mail を通して行われる。 - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.7]{images/cerium/createTask.pdf} - \end{center} - \caption{Task Manager} - \label{fig:TaskManager} -\end{figure} - -\newpage - -\section{Cerium TaskManager} -Cerium TaskManager では、処理の単位を Task として記述していく。 -関数やサブルーチンを Task として取り扱い、その Task にて Input Data/Output Data 及び Task の依存関係を設定する。 -そして Task は設定された依存関係を考慮しながら実行される。 - -Input Data で格納した 2 つの数を乗算し、Output Data に演算結果を格納する multiply という例題のソースコード\ref{src:createTask}を以下に示す。 - -また、Task の生成時に用いる API 一覧を表\ref{table:TaskCreateAPI}に示す。 -\begin{lstlisting}[frame=lrbt,label=src:createTask,caption=Task の生成,numbers=left] -multi_init(TaskManager *manager) -{ - float *A, *B, *C; - - // create Task - HTaskPtr multiply = manager->create_task(MULTIPLY_TASK); - - // set device - multiply->set_cpu(SPE_ANY); - - // set inData - multiply->set_inData(0, (memaddr)A, sizeof(float)*length); - multiply->set_inData(1, (memaddr)B, sizeof(float)*length); - - // set outData - multiply->set_outData(0, (memaddr)C, sizeof(float)*length); - - // set parameter - multiply->set_param(0,(long)length); - - // spawn task - multiply->spawn(); -} -\end{lstlisting} - -\begin{tiny} - \begin{table}[ht] - \begin{center} - \label{table:TaskCreateAPI} - \small - \begin{tabular}[t]{c|l} - \hline - create\_task& Task を生成する \\ - \hline - set\_inData & Task への入力データのアドレスを追加 \\ - \hline - set\_outData & Task への出力データのアドレスを追加 \\ - \hline - set\_param & Task へ値を一つ渡す。ここでは length \\ - \hline - set\_cpu & Task を実行するデバイスの設定 \\ - \hline - spawn & 生成した Task を TaskList に set \\ - \hline - \end{tabular} - \caption{Task 生成における API} - \end{center} - \end{table} -\end{tiny} - -次に、デバイス側で実行される Task のソースコードを\ref{src:task}に示す。 -\begin{lstlisting}[frame=lrbt,label=src:task,caption=Task,numbers=left] -static int -run(SchedTask *s) { - // get input - float *i_data1 = (float*)s->get_input(0); - float *i_data2 = (float*)s->get_input(1); - - // get output - float *o_data = (float*)s->get_output(0); - - // get parameter - long length = (long)s->get_param(0); - - // calculate - for (int i=0; i<length; i++) { - o_data[i] = i_data1[i] * i_data2[i]; - } - return 0; -} -\end{lstlisting} -また表\ref{table:taskAPI}は Task 側で利用する API である。 -Task 生成時に設定した Input Data や parameter を取得することができる。 - -\begin{tiny} - \begin{table}[ht] - \begin{center} - \caption{Task 側で使用する API} - \label{table:taskAPI} - \small - \begin{tabular}[t]{c|l} - \hline - get\_input & Scheduler から input data を取得 \\ - \hline - get\_output & Scheduler から output data を取得 \\ - \hline - get\_param & set\_param した値を取得 \\ - \hline - \end{tabular} - \end{center} - \end{table} -\end{tiny} - -\newpage - -Task 生成時に設定できる要素を以下に列挙する。 - -\begin{itemize} -\item Input Data -\item Output Data -\item Parameter -\item CpuType -\item Dependency -\end{itemize} - -Input/Output Data、Parameter は関数の引数に相当する。 -Cpu Type は Task を動作させるデバイスを設定することができ、Dependency は他の Task との依存関係を設定することができる。 -\newpage -\section{並列処理向け I/O} -ファイル読み込みなどの I/O を含むプログラムは、読み込み時間が Task の処理時間と比較してオーバーヘッドになることが多い。 -計算処理の並列化を図ったとしても I/O がボトルネックになってしまい処理全体が高速にならない。 -本項では Cerium に実装した並列処理用 I/O を行ない、I/O 部分の高速化を図った。 - -Cerium の例題ではファイル読み込みを mmap にて実装していた。 -しかし、mmap だとファイルを読み込んでから Task を実行するので、読み込んでいる間は他の CPU が動作せず並列度が落ちる。 - -mmap は function call 後にすぐにファイルを読みに行くのではなく、仮想メモリ領域にファイルの中身を対応させる。 -その後メモリ空間にアクセスされたときに、OS が対応したファイルを読み込む。 -また、読み込む方法が OS 依存となってしまうため環境に左右されやすく、プログラムの書き手が読み込みの制御をすることが難しい。 - -図\ref{fig:mmap}は mmap で読み込んだファイルに対して Task1 、 Task2 がアクセスしてそれぞれの処理を行うときのモデルである。 - -Task1 が実行されると仮想メモリ上に対応したファイルが読み込まれ、読み込み後 Task1 の処理が行われる。 -その後 Task2 も Task1 と同様の処理が行われるが、これら 2 つの Task の間に待ちが入る。 - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.7]{images/cerium/mmap.pdf} - \end{center} - \caption{mmap Model} - \label{fig:mmap} -\end{figure} - -mmap を使わず、読み込みを独立した Thread で行ない、ファイルを一度に全て読み込むのではなくある程度の大きさ(Block)分読み込み、読み込まれた部分に対して並列に Task を起動する。 -これを Blocked Read と呼び、高速化を図った。 - -Blocked Read を実装するにあたり、WordCount を例題に挙げる。 -ファイルを読み込む Task (以下、ReadTask) と、読み込んだファイルに対して計算を行う Task (以下、WordCount) を別々に生成する。ReadTask は一度にファイル全体を読み込むのではなく、ある程度の大きさで分割してから読み込みを行う。分割して読み込んだ範囲に対して WordCount を行う。 - -WordCount を Blocked Read で読み込み処理をしたとき以下の図\ref{fig:BlockedRead}の様になる。 - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.5]{./images/cerium/blockedread.pdf} - \end{center} - \caption{BlockedRead による WordCount} - \label{fig:BlockedRead} -\end{figure} - -Task を一定の単位でまとめた Task Block ごとに生成して WordCount を行なっている。 -Task Block で計算される領域が Blocked Read で読み込む領域を追い越して実行してしまうと、まだ読み込まれていない領域に対して計算されてしまう。 -その問題を解決するために依存関係を適切に設定する必要がある。 -Blocked Read による読み込みが終わってから TaskBlock が起動されるようにするため、Cerium の API である wait\_for にて依存関係を設定する。 - -また、ReadTask は連続で処理される必要がある。 -なぜならば、ReadTask でファイルを読み込む前提で WordCount がその領域に対して計算を行うので、ReadTask の処理が遅くなってしまうだけでオーバーヘッドとなってしまう。\ref{fig:BlockedReadModel} - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.5]{./images/cerium/blockedreadimage.pdf} - \end{center} - \caption{BlockedRead Model} - \label{fig:BlockedReadModel} -\end{figure} - -\newpage -Blocked Read を実装することにより、読み込み部分と処理部分の並列化を行なった。Blocked Read は連続で読み込まれる必要があるため、さらに I/O 専用 thread を実装した。 - -Cerium Task Manager では、それぞれの Task に対してデバイスを設定することができる。 -SPE\_ANY 設定をすると、Task Manager が CPU の割り振りを自動的に行う。 -Blocked Read は連続で読み込まれなければならないが、SPE\_ANY で設定すると Blocked Read 間に別の Task が割り込まれる恐れがある。(図\ref{fig:spe_any_blockedread}) - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.7]{./images/cerium/speblockedread.pdf} - \end{center} - \caption{BlockedRead と Task を同じ thread で動かした場合} - \label{fig:spe_any_blockedread} -\end{figure} - -Task が Blocked Read 間に割り込まれないようにするため、I/O 専用 thread である iO\_0 の設定を追加した。 - -IO\_0 は SPE\_ANY とは別 thread の scheduler で動作するので、SPE\_ANY で動作している Task に割り込むことはない。 -しかし、読み込みの終了を通知し、次の read を行う時に他の Task がスレッドレベルで割り込んでしまう事がある。 -pthread\_getschedparam() で IO\_0 の priority の設定を行う必要がある(図:\ref{fig:iothread_blockedread})。 -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.7]{./images/cerium/iothread.pdf} - \end{center} - \caption{IO Thread による BlockedRead} - \label{fig:iothread_blockedread} -\end{figure} - -IO\_0 で実行される Task は Blocked Read のみで、さらに IO\_0 の priority を高く設定することにより Blocked Read が他の Task に割り込まれることなく連続に実行される。
--- a/ceriumex.tex Tue Jan 19 18:11:19 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,3 +0,0 @@ -\chapter{Cerium による文字列処理の例題} -\section{WordCount} -\section{Boyer Moore Search}
--- a/conclusion.tex Tue Jan 19 18:11:19 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1 +0,0 @@ -\chapter{結論}
--- a/images/image.graffle Tue Jan 19 18:11:19 2016 +0900 +++ b/images/image.graffle Wed Jan 20 16:16:46 2016 +0900 @@ -26,7 +26,7 @@ <key>MasterSheets</key> <array/> <key>ModificationDate</key> - <string>2016-01-19 09:00:13 +0000</string> + <string>2016-01-19 12:25:52 +0000</string> <key>Modifier</key> <string>MasaKoha</string> <key>NotesVisible</key> @@ -2341,6 +2341,173 @@ <array> <dict> <key>Bounds</key> + <string>{{23.67716556008412, 1094.1732382740561}, {436.95275987912339, 35}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>Vertical</string> + <key>Flow</key> + <string>Resize</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>0</string> + </dict> + </dict> + <key>ID</key> + <integer>33</integer> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Align</key> + <integer>0</integer> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\partightenfactor0 + +\f0\fs32 \cf0 101000 or 001000 = 001000}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{23.67716556008412, 1069.2874108819276}, {436.95275987912339, 36}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>Vertical</string> + <key>Flow</key> + <string>Resize</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>0</string> + </dict> + </dict> + <key>ID</key> + <integer>32</integer> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Align</key> + <integer>0</integer> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;\f1\fnil\fcharset128 HiraginoSans-W3;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\partightenfactor0 + +\f0\fs32 \cf0 file2 +\f1 \'82\'cc\'90\'e6\'93\'aa\'82\'a9\'82\'e7\'88\'ea\'95\'b6\'8e\'9a\'82\'b7\'82\'b7\'82\'df\'82\'bd\'8e\'9e\'82\'cc\'8f\'f3\'91\'d4 : 001000}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{23.67716556008412, 1044.5669386113721}, {297.63779797610323, 36}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>Vertical</string> + <key>Flow</key> + <string>Resize</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>0</string> + </dict> + </dict> + <key>ID</key> + <integer>31</integer> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Align</key> + <integer>0</integer> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;\f1\fnil\fcharset128 HiraginoSans-W3;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\partightenfactor0 + +\f0\fs32 \cf0 file2 +\f1 \'82\'cc\'90\'e6\'93\'aa\'82\'cc\'8f\'f3\'91\'d4 : 111111 (\'89\'bc\'92\'e8)}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> <string>{{198.21653722698295, 572.21575695577349}, {63.779528137736406, 30}}</string> <key>Class</key> <string>ShapedGraphic</string> @@ -3212,7 +3379,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{18.007874170063104, 1094.3504034258485}, {411.02362577652366, 84}}</string> + <string>{{19.925197017568394, 1206.1417432269711}, {411.02362577652366, 180}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>FitText</key> @@ -3265,7 +3432,9 @@ \f0\fs32 \cf0 \'81\'45 \f1 file1 \f0 \'82\'cc\'96\'96\'92\'5b\'82\'cc\'8f\'f3\'91\'d4\'82\'f0\'95\'db\'91\'b6\ -\'81\'45file2 \'82\'cc\'90\'e6\'93\'aa\'82\'cc\'8f\'f3\'91\'d4\'82\'f0\'91\'53\'82\'c4\'82\'cc\'83\'72\'83\'62\'83\'67\'97\'f1\'82\'aa1\'82\'c9\'82\'c8\'82\'c1\'82\'c4\'82\'a2\'82\'e9\'82\'c6\'89\'bc\'92\'e8\'82\'b5\'82\'c4 grep \'82\'f0\'82\'a9\'82\'af\'82\'e9}</string> +\'81\'45file2 \'82\'cc\'90\'e6\'93\'aa\'82\'cc\'8f\'f3\'91\'d4\'82\'f0\'91\'53\'82\'c4\'82\'cc\'83\'72\'83\'62\'83\'67\'97\'f1\'82\'aa1\'82\'c9\'82\'c8\'82\'c1\'82\'c4\'82\'a2\'82\'e9\'82\'c6\'89\'bc\'92\'e8\'82\'b5\'82\'c4 file2 \'82\'cc\'90\'e6\'93\'aa1\'95\'b6\'8e\'9a\'82\'be\'82\'af grep \'82\'f0\'82\'a9\'82\'af\'82\'e9\ +\'81\'45\'90\'e6\'93\'aa\'88\'ea\'95\'b6\'8e\'9a\'82\'be\'82\'af grep \'82\'f0\'82\'a9\'82\'af\'82\'bd\'82\'a0\'82\'c6\'82\'cc\'8f\'f3\'91\'d4(\'83\'72\'83\'62\'83\'67\'97\'f1)\'82\'c6 file1 \'82\'cc\'96\'96\'92\'5b\'82\'cc\'8f\'f3\'91\'d4\'82\'cc or \'82\'aa 1 \'82\'c2\'82\'c5\'82\'e0\'97\'a7\'82\'c1\'82\'c4\'82\'a2\'82\'ea\'82\'ce\'81\'41\'90\'b3\'8b\'4b\'95\'5c\'8c\'bb\'92\'86\'82\'c9\'83\'74\'83\'40\'83\'43\'83\'8b\'95\'aa\'8a\'84\'82\'b3\'82\'ea\'82\'bd\'82\'c6\'82\'dd\'82\'c8\'82\'b7\'81\'42\ +}</string> </dict> </dict> <dict> @@ -21647,13 +21816,13 @@ <key>WindowInfo</key> <dict> <key>CurrentSheet</key> - <integer>6</integer> + <integer>1</integer> <key>Expanded_Canvases</key> <array> <string>キャンバス 7</string> </array> <key>Frame</key> - <string>{{245, 195}, {1279, 982}}</string> + <string>{{153, 25}, {1767, 1072}}</string> <key>ShowInfo</key> <true/> <key>ShowRuler</key> @@ -21665,9 +21834,9 @@ <key>TopSlabHeight</key> <real>682</real> <key>VisibleRegion</key> - <string>{{-56, 0}, {670.17544700608482, 722.8070266138925}}</string> + <string>{{-86, 855.55553646967621}, {732.74852166541643, 534.50291205282576}}</string> <key>Zoom</key> - <real>1.1399999856948853</real> + <real>1.7100000381469727</real> <key>ZoomValues</key> <array> <array> @@ -21702,8 +21871,8 @@ </array> <array> <string>キャンバス 9</string> - <real>1.4099999666213989</real> - <real>1.4099999999999999</real> + <real>1.7100000381469727</real> + <real>1.7100000000000002</real> </array> </array> </dict>
--- a/implregex.tex Tue Jan 19 18:11:19 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,86 +0,0 @@ -\chapter{正規表現の設計と実装} -\section{正規表現構文木の生成} -\section{Transition List の生成} -\section{Subset Construction} -\section{Cerium 上での実装} - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.2]{images/implementation/CharClassMergePattern.pdf} - \end{center} - \caption{2つの Character Class を merge するときの全パターン} - \label{fig:CharClassMergePattern} -\end{figure} - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.2]{images/implementation/ccinsert1.pdf} - \end{center} - \caption{Character Class を二分木で表示} - \label{fig:ccinsert1} -\end{figure} - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.2]{images/implementation/ccinsert2.pdf} - \end{center} - \caption{ある Character Class の二分木に対して、新しい Character Class を insert} - \label{fig:ccinsert2} -\end{figure} - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.2]{images/implementation/ccinsertresult.pdf} - \end{center} - \caption{insert 後の Character Class の二分木} - \label{fig:ccinsertresult} -\end{figure} - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.2]{images/implementation/cfab.pdf} - \end{center} - \caption{cfab} - \label{fig:cfab} -\end{figure} - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.2]{images/implementation/cfdg.pdf} - \end{center} - \caption{cfdg} - \label{fig:cfdg} -\end{figure} - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.2]{images/implementation/cfdgab.pdf} - \end{center} - \caption{cfdgab} - \label{fig:cfdgab} -\end{figure} - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.2]{images/implementation/efgi.pdf} - \end{center} - \caption{efgi} - \label{fig:efgi} -\end{figure} - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.2]{images/implementation/dfa.pdf} - \end{center} - \caption{dfa} - \label{fig:dfa} -\end{figure} - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.2]{images/implementation/nfa.pdf} - \end{center} - \caption{nfa} - \label{fig:nfa} -\end{figure} -
--- a/introduction.tex Tue Jan 19 18:11:19 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,5 +0,0 @@ -\chapter{introduction} -正規表現はオートマトンに変換することができ、そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。 -この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。 -コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。 -本研究では Cerium 上に正規表現を実装することにより。
--- a/master_paper.tex Tue Jan 19 18:11:19 2016 +0900 +++ b/master_paper.tex Wed Jan 20 16:16:46 2016 +0900 @@ -7,9 +7,9 @@ \usepackage{comment} %\input{dummy.tex} %% font -\jtitle{Cerium 上での正規表現の設計と実装} +\jtitle{Cerium による文字列の並列処理} %\etitle{Title} -\etitle{Title} +\etitle{Parallel processing of strings using Cerium} \year{平成27年度 3月} \affiliation{\center% \includegraphics[clip,keepaspectratio,width=.15\textwidth] @@ -78,17 +78,12 @@ %chapters \pagenumbering{arabic} -\input{introduction.tex} -\input{cerium.tex} -\input{ceriumex.tex} -\input{implregex.tex} -\input{benchmark.tex} -\input{conclusion.tex} - -%謝辞 -\input{acknowledgment.tex} - -%参考文献 +\input{c1.tex} +\input{c2.tex} +\input{c3.tex} +\input{c4.tex} +\input{c5.tex} +\input{c6.tex} \nocite{*} \bibliographystyle{junsrt} \bibliography{master_paper}
--- a/paper.mm Tue Jan 19 18:11:19 2016 +0900 +++ b/paper.mm Wed Jan 20 16:16:46 2016 +0900 @@ -1,6 +1,6 @@ <map version="1.0.1"> <!-- To view this file, download free mind mapping software FreeMind from http://freemind.sourceforge.net --> -<node CREATED="1449662891330" ID="ID_1874183783" MODIFIED="1452653720805" STYLE="fork" TEXT="ファイル読み込みを含む並列処理に関する研究"> +<node CREATED="1449662891330" ID="ID_1874183783" MODIFIED="1453273921446" STYLE="fork" TEXT="ファイル読み込みを含む並列処理に関する研究"> <node CREATED="1452175089101" ID="ID_489351997" MODIFIED="1452653423743" POSITION="right" TEXT="Introduction"/> <node CREATED="1452180902873" ID="ID_1353978827" MODIFIED="1452332585021" POSITION="right" TEXT="並列プログラミングフレームワーク Cerium"> <node CREATED="1452181971497" ID="ID_274969374" MODIFIED="1452181977121" TEXT="Cerium の概要"/> @@ -19,8 +19,8 @@ <node CREATED="1452338371523" ID="ID_869857867" MODIFIED="1452338386316" TEXT="Boyer Moore Search"/> <node CREATED="1452653003540" ID="ID_1626034226" MODIFIED="1452653009934" TEXT="正規表現"> <node CREATED="1452656805318" ID="ID_1977223147" MODIFIED="1452656823609" TEXT="正規表現木の生成"/> -<node CREATED="1452656823978" ID="ID_823196937" MODIFIED="1452656838057" TEXT="Transition List の生成"/> -<node CREATED="1452656839202" ID="ID_954086839" MODIFIED="1452656868949" TEXT="Subset Construction よる状態の merge"/> +<node CREATED="1452656823978" ID="ID_823196937" MODIFIED="1453273979603" TEXT="正規表現木から NFA の生成"/> +<node CREATED="1452656839202" ID="ID_954086839" MODIFIED="1453273998498" TEXT="Subset Construction よる NFA から DFA への変換"/> </node> </node> <node CREATED="1452175345187" ID="ID_741844249" MODIFIED="1452175358409" POSITION="right" TEXT="ベンチマーク"> @@ -42,7 +42,10 @@ </node> </node> <node CREATED="1452653032927" ID="ID_551349889" MODIFIED="1452653043365" POSITION="left" TEXT="I/Oを含む並列処理"> -<node CREATED="1452653079109" ID="ID_1791879692" MODIFIED="1452653084748" TEXT="ファイル分割"/> +<node CREATED="1452653079109" ID="ID_1791879692" MODIFIED="1452653084748" TEXT="ファイル分割"> +<node CREATED="1453273848514" ID="ID_557173317" MODIFIED="1453273864288" TEXT="ファイル読み込みと同時にタスクも走る"/> +<node CREATED="1453273864559" ID="ID_1848333286" MODIFIED="1453273890054" TEXT="問題によってファイルの分割サイズを変更"/> +</node> <node CREATED="1452653085077" ID="ID_982761763" MODIFIED="1452654198709" TEXT="読み込み"> <node CREATED="1452654199172" ID="ID_1254434912" MODIFIED="1452654201099" TEXT="mmap"> <node CREATED="1452654320900" ID="ID_1311623373" MODIFIED="1452654343237" TEXT="MAP_FILE などの Flag Option"/>