\chapter{ベンチマーク}
本項で行なった実験の環境は以下の通りである。
\begin{itemize}
\item Mac OS X 10.10.5
\item 2*2.66 GHz 6-Core Intel Xeon
\item Memory 16GB 1333MHz DDR3
\item 1TB HDD
\end{itemize}

Cerium で実装した Word Count と Mac の wc の比較と、今回実装した正規表現と Mac の egrep の比較を行なった。
また、それぞれの結果に実装した並列処理向け I/O の結果も含む。

\section{Word Count}
ファイルの大きさは 約500MByte で、このファイルには 約650万行、約8300万単語が含まれている。
図\ref{fig:wordcount} はファイル読み込みを含まない Word Count の結果である。

Mac の wc ではこのファイルを処理するのに 4.08 秒かかる。それに対して、Cerium Word Count は 1 CPU で 3.70 秒、12 CPU だと 0.40 秒で処理できる。

1 CPU で動作させると Mac の wc よりも 1.1 倍ほど速くなり、12 CPU で動作させると wc よりも 10.2 倍ほど速くなった。

1 CPU と 12 CPU で比較すると、9.25 倍ほど速くなった。
12 倍速くなるはずだが、Word Count の処理以外にも Word Count のタスクを作る、タスクを CPU に送るなどの通信部分も含まれるため理論値は出ない。

表\ref{table:metachar}

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \begin{tabular}[t]{r|r}
        \hline
        実行方式 & 実行速度(秒)\\
        \hline
        Mac(wc) & 4.08 \\
        \hline
        Cerium Word Count(CPU 1) & 3.70\\
        \hline
        Cerium Word Count(CPU 4) & 1.00\\
        \hline
        Cerium Word Count(CPU 8) & 0.52\\
        \hline
        Cerium Word Count(CPU 12) & 0.40\\
        \hline
      \end{tabular}
      \caption{ファイル読み込み無しの Word Count}
      \label{fig:wordcount}
    \end{center}
  \end{table}
\end{tiny}

図\ref{fig:IOwordcount} は、ファイル読み込みを含めた Word Count の結果である。
Mac の wc ではこのファイルを処理するのに 10.59 秒かかる。それに対して、Cerium Word Count は mmap Blocked Read 全ての状況で Mac の wc よりも速いことを示している。
Cerium Word Count 12 CPU のとき、7.83 秒で処理をしており、Mac の wc の 1.4 倍ほど速くなっている。

mmap は読み込みを OS が制御しており、書き手が制御できない。
また Word Count が走る際ファイルアクセスはランダムアクセスとなる。
mmap はランダムアクセスを想定していなくてグラフにばらつきが起こっていると考えられる。
Blocked Read では読み込みをプログラムの書き手が制御しており、ファイルの読み込みもファイルの先頭から順次読み込みを行なっている。
そのため、読み込みを含めた結果にばらつきが起こりにくくなっていると予想される。

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \begin{tabular}[t]{r|r|r|r}
        \hline
        CPU Num / 実行方式 & Mac(wc) & mmap & Blocked Read\\
        \hline
        1 & 10.590  & 9.96  & 9.33 \\
        \hline
        2 & ---     & 8.63  & 8.52 \\
        \hline
        4 & ---     & 10.35 & 8.04 \\
        \hline
        8 & ---     & 9.26  & 7.82 \\
        \hline
      \end{tabular}
  \caption{ファイル読み込みを含む Word Count}
  \label{table:IOwordcount}
    \end{center}
  \end{table}
\end{tiny}

\section{正規表現}

\begin{itemize}
\item DFA を生成後(NFA であれば、Subset Construction後)、逐次にDFAと照らし合わせる。
\item 並列処理時に NFA・DFA を分割した Task に配りそれぞれの Taskで 照らし合わせる。照らし合わせた際に NFA だとわかった場合にはその場で Subset Construction し DFA を生成する。
\end{itemize}

表\ref{table:AZaz} '[A-Z][A-Za-z0-9]*s'
ファイルサイズの側のかっこ書き内は与えられた正規表現にマッチした数
1GBのファイルには約1.7 億の単語が存在する。

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \begin{tabular}[t]{c|r|r|r}
        \hline
        実行方式/File Size(Match Num) & 500MB(500万) & 1GB(1000万) \\
        \hline
        DFAの状態遷移での逐次実行 & 20.62 & 40.10\\
        \hline
        CeriumGrep(CPU 12) mmap  & 18.00 & 26.96\\
        \hline
        CeriumGrep(CPU 12) bread & 12.48 & 21.14\\
        \hline
        egrep & 59.51 & 119.23\\
        \hline
      \end{tabular}
  \caption{[A-Z][A-Za-z0-9]*s のマッチング}
  \label{table:AZaz}
    \end{center}
  \end{table}
\end{tiny}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
表\ref{table:abab}
約500 MB 、単語数約2300万 abab がめちゃくちゃ含まれているファイル

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \begin{tabular}[t]{l|r|r|r}
        \hline
        正規表現 & マッチ数 & CeriumGrep time (s) & egrep time(s)\\
        \hline
        '(a|b)*a(a|b)(a|b)'                  & 約1950万  & 38.67 &  86.66 \\
        \hline
        '(a|b)*a(a|b)(a|b)(a|b)'             & 約1640万  & 38.72 &  94.25 \\
        \hline
        '(a|b)*a(a|b)(a|b)(a|b)(a|b)'        & 約1640万  & 39.59 & 100.98 \\
        \hline
        '(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)'   & 約1550万 & 38.68 & 104.82 \\
        \hline
      \end{tabular}
  \caption{abab}
  \label{table:abab}
    \end{center}
  \end{table}
\end{tiny}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

表\ref{table:nomatch} ab の文字列がならんでいるところに (W|w)ord の正規表現

全くマッチしないパターン
Filesize:500MB

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \begin{tabular}[t]{c|r|r|r}
        \hline
        実行方式/File Size(Match Num) & I/O含む & I/O 含まない & \\
        \hline
        DFAの状態遷移での逐次実行& 27.130 & 14.763 & \\
        \hline
        CeriumGrep(CPU 12) mmap  & 21.576 & 1.873 & \\
        \hline
        CeriumGrep(CPU 12) bread & 19.986 & & \\
        \hline
        egrep & 28.332 & & \\
        \hline
      \end{tabular}
  \caption{(W|w)ork のマッチング}
  \label{table:nomatch}
    \end{center}
  \end{table}
\end{tiny}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

表\ref{table:abab}

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \begin{tabular}[t]{r|r|r|r}
        \hline
        CPU Num / 実行方式 & egrep & mmap & Blocked Read\\
        \hline
        1 & 83.09   & 57.65 & 40.49 \\
        \hline
        2 & ---     & 43.96 & 33.72 \\
        \hline
        4 & ---     & 33.37 & 34.26 \\
        \hline
        8 & ---     & 35.48 & 32.46 \\
        \hline
      \end{tabular}
  \caption{abab}
  \label{table:abab}
    \end{center}
  \end{table}
\end{tiny}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

表\ref{table:metachar}

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \begin{tabular}[t]{c|r|r}
        \hline
        実行方式 & ファイル読み込み有 & ファイル読み込み無\\
        \hline
        DFAの状態遷移での逐次実行 & 21.171 & 16.150\\
        \hline
        並列処理(CPU 2) & 27.061 & 15.401\\
        \hline
        並列処理(CPU 12) & 10.419 & 7.386\\
        \hline
        egrep & 57.753 & --- \\
        \hline
      \end{tabular}
      \caption{実装したそれぞれのプログラムと egrep との比較}
      \label{table:metachar}
    \end{center}
  \end{table}
\end{tiny}