\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvips]{graphicx}
\usepackage{picins}
\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.eps}}琉球大学主催 工学部情報工学科 卒業研究中間発表}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\begin{document}
\title{Cerium Task Managerによる正規表現の実装}
\author{085726C {古波倉}{正隆} 指導教員 : 河野真治}
\date{}
\maketitle
\thispagestyle{fancy}

\section{はじめに}
\subsection{研究背景}
近年、CPU 1コア当たりのクロック数が頭打ちとなっているので、シングルコアでの処理能力はほとんど上がっていない。
それを解決した結果、シングルコアからマルチコアへの移行によって CPU 性能が向上している。
しかし、マルチコア CPU を最大限に活かすためには、並列プログラミングによる並列度を向上させなければならない。

現在のプログラミング手法だと並列プログラミングが難しいので、当研究室では Cerium Library を提供することによって並列プログラミングを容易にしている。

\subsection{研究目的}
先行研究による Task の並列化によって、プログラム全体の処理速度は飛躍的に向上しているが\cite{kinjyo} 、
ファイル読み込み等のI/Oに対して並列で動作するようなAPIは実装されていない。
しかし、ファイル読み込みとTaskを並列化させることにより、さらなる処理速度の向上が見込まれる。
I/O部分が並列に動作し、高速かつ容易に記述できるようなAPIをCerium Libraryが提供することにより、様々な人が容易に並列プログラミングが記述できるようになるであろうと考えている。

本研究ではその例題として正規表現を実装し、
I/Oの並列化の設計・実装によって既存の正規表現の処理速度、処理効率を上げることを目指す。

\section{Cerium Task Manager}
Cerium Task Managerは、並列処理をTask単位で記述する。関数やサブルーチンをTaskとして扱い、そのTaskに対してInput Data、Output Data及び依存関係を設定する。そして、それに基づいた設定の元でTaskに管理し、実行される。本稿で述べるInput Dataとは、検索対象となるテキストファイルのことである。

Cerium Task ManagerはPlayStation 3/Cell、Mac OS X及びLinux上で利用することが可能で、近年ではGPUへの利用も可能となった。\cite{tomari}

\section{実装}
検索対象の文字列が、固定長文字列か正規表現によって文字列検索アルゴリズムが変化する実装にする。
固定長の場合は Boyer-Moore String Search Algorithm \cite{BM}、正規表現の場合は先行研究の正規表現マッチング\cite{shinya} を実装する。

\subsection{Boyer-Moore\\String Search Algorithm}
文字列検索アルゴリズムの一種であり、
Input Dataと検索文字列(pattern)の末尾から比較し、末尾が一致していれば一つ前を比較し、さらに一致すれば比較を繰り返すアルゴリズムである。
もし不一致が起こった場合は、patternの移動が発生するが、不一致が起こった場所のInput Dataを参照し、その文字によってpatternの移動量が決定される。
(図\ref{fig:bms})
(図\ref{fig:bmt})
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.5\textwidth]{pic/bm-search.eps}
\end{center}
\caption{Boyer-Moore String Search の比較法}
\label{fig:bms}
\end{figure}

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.5\textwidth]{pic/bm-table.eps}
\end{center}
\caption{不一致時のpatternの移動量}
\label{fig:bmt}
\end{figure}

\newpage

\subsection{Input Data分割時の問題点}
Input Dataを分割し、各Taskに割り振るのだが、分割時に検索対象となる文字列が含まれてしまうおそれがある。

本来の1 Taskの分割データ量 $L$ に加え、検索文字列の長さ $s$だけ多く読み込むように設計することで、この問題は解決できる。
しかし、1 Taskの読み込むデータ量が$L + s$の場合だと、検索文字列がTask 0に含まれ、Task 1にも含まれることになる。
このように検索対象の文字列が分割されるポイントに含まれ、なおかつ1 Taskに読み込む量を正しく設定しなければ、正確な結果が得られなくなる。
(図\ref{fig:iodiv_failed})

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.5\textwidth]{pic/iodiv_failed.eps}
\end{center}
\caption{分割周りの処理・失敗時(例:文字列``doing"の検索)}
\label{fig:iodiv_failed}
\end{figure}

それを解決するために、1 Taskの分割データ量に、検索文字列の長さを加えてから$1$引いた数だけ多く読み込むように設計する。
よって、実際の1 Taskの読み込むデータ量は$L + s - 1$となる。このような処理を行うことで、検索文字列がTask 0に含まれ、Task 1には含まれないという結果が返ってくる。
これによって、分割周りの部分が正しく処理される。
(図\ref{fig:iodiv_success})

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.5\textwidth]{pic/iodiv_success.eps}
\end{center}
\caption{分割周りの処理・成功時}
\label{fig:iodiv_success}
\end{figure}


\newpage

\section{まとめと今後の課題}
これまでにBoyer-Moore String Search Algorithmと、Input Data分割時の処理の実装を行った。
検索文字列の数が未分割、分割時に正しい結果が返ってきていることを確認した。
しかし検索文字列については、現在ハードコーディングのため実行時に指定することができないので、それを改良する必要がある。

プログラムの全体的な処理速度を向上させるには、並列I/Oを実装することにより実現できるが、
それについてはこれから実装、検証していく。

\thispagestyle{fancy}
\begin{thebibliography}{9}

\bibitem{kinjyo}金城裕、河野真治、多賀野海人、小林佑亮 (琉球大学)\\
ゲームフレームワーク Cerium Task Manager の改良\\
情報処理学会システムソフトウェアとオペレーティング・システム研究会 (OS), April 2011

\bibitem{tomari}渡真利 勇飛、河野 真治(琉球大学)\\
Cerium Task Manager の GPGPU への対応\\
情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)、May 2013

\bibitem{BM}J.S.Moore, R.S. Boyer.\\
A Fast String Searching Algorithm\\
Communications of the Association for Computing Machinery, 1977,pp.762-772.

\bibitem{shinya}新屋 良磨，光成 滋生，佐々 政孝(東京大学)\\
並列化と実行時コード生成を用いた正規表現マッチングの高速化\\
日本ソフトウェア科学会大会第28回大会 、2011/9/24

\end{thebibliography}
\end{document}