3
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 \documentclass[twocolumn,twoside,9.5pt]{jarticle}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 \usepackage[dvips]{graphicx}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 \usepackage{picins}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 \usepackage{fancyhdr}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 \pagestyle{fancy}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 \lhead{\parpic{\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.eps}}琉球大学主催 工学部情報工学科 卒業研究中間発表}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 \rhead{}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 \cfoot{}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 \setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 \setlength{\headheight}{0mm}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 \setlength{\headsep}{5mm}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 \setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 \setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 \setlength{\textwidth}{181mm}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16 \setlength{\textheight}{261mm}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
17 \setlength{\footskip}{0mm}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18 \pagestyle{empty}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
19
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20 \begin{document}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
21 \title{Cerium Task Managerによる正規表現の実装}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
22 \author{085726C {古波倉}{正隆} 指導教員 : 河野真治}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
23 \date{}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 \maketitle
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
25 \thispagestyle{fancy}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
26
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27 \section{はじめに}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28 \subsection{研究背景}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29 近年、CPU 1コア当たりのクロック数が頭打ちとなっているので、シングルコアでの処理能力はほとんど上がっていない。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30 それを解決した結果、シングルコアからマルチコアへの移行によって CPU 性能が向上している。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31 しかし、マルチコア CPU を最大限に活かすためには、並列プログラミングによる並列度を向上させなければならない。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33 現在のプログラミング手法だと並列プログラミングが難しいので、当研究室では Cerium Library を提供することによって並列プログラミングを容易にしている。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35 \subsection{研究目的}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36 先行研究による Task の並列化によって、プログラム全体の処理速度は飛躍的に向上しているが\cite{kinjyo} 、
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 ファイル読み込み等のI/Oに対して並列で動作するようなAPIは実装されていない。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38 しかし、ファイル読み込みとTaskを並列化させることにより、さらなる処理速度の向上が見込まれる。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
39 I/O部分が並列に動作し、高速かつ容易に記述できるようなAPIをCerium Libraryが提供することにより、様々な人が容易に並列プログラミングが記述できるようになるであろうと考えている。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
40
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41 本研究ではその例題として正規表現を実装し、
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 I/Oの並列化の設計・実装によって既存の正規表現の処理速度、処理効率を上げることを目指す。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
44 \section{Cerium Task Manager}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
45 Cerium Task Managerは、並列処理をTask単位で記述する。関数やサブルーチンをTaskとして扱い、そのTaskに対してInput Data、Output Data及び依存関係を設定する。そして、それに基づいた設定の元でTaskに管理し、実行される。本稿で述べるInput Dataとは、検索対象となるテキストファイルのことである。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 Cerium Task ManagerはPlayStation 3/Cell、Mac OS X及びLinux上で利用することが可能で、近年ではGPUへの利用も可能となった。\cite{tomari}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
49 \section{実装}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
50 検索対象の文字列が、固定長文字列か正規表現によって文字列検索アルゴリズムが変化する実装にする。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51 固定長の場合は Boyer-Moore String Search Algorithm \cite{BM}、正規表現の場合は先行研究の正規表現マッチング\cite{shinya} を実装する。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
53 \subsection{Boyer-Moore\\String Search Algorithm}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
54 文字列検索アルゴリズムの一種であり、
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
55 Input Dataと検索文字列(pattern)の末尾から比較し、末尾が一致していれば一つ前を比較し、さらに一致すれば比較を繰り返すアルゴリズムである。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
56 もし不一致が起こった場合は、patternの移動が発生するが、不一致が起こった場所のInput Dataを参照し、その文字によってpatternの移動量が決定される。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
57 %(図\ref{fig:bmt})
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
58
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
59 %\begin{figure}[htbp]
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 %\begin{center}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61 %\includegraphics[width=0.5\textwidth]{pic/bm-search.eps}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62 %\end{center}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
63 %\caption{Boyer-Moore String Search の比較法}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
64 %\label{fig:bms}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65 %\end{figure}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
66
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67 \subsection{Input Data分割時の問題点}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68 Input Dataを分割し、各Taskに割り振るのだが、分割時に検索対象となる文字列が含まれてしまうおそれがある。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
69
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70 本来の1 Taskの分割データ量 $L$ に加え、検索文字列の長さ $s$だけ多く読み込むように設計することで、この問題は解決できる。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
71 しかし、1 Taskの読み込むデータ量が$L + s$の場合だと、検索文字列がTask 0に含まれ、Task 1にも含まれることになる。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
72 このように検索対象の文字列が分割されるポイントに含まれ、なおかつ1 Taskに読み込む量を正しく設定しなければ、正確な結果が得られなくなる。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
73
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74 それを解決するために、1 Taskの分割データ量に、検索文字列の長さを加えてから$1$引いた数だけ多く読み込むように設計する。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 よって、実際の1 Taskの読み込むデータ量は$L + s - 1$となる。このような処理を行うことで、検索文字列がTask 0に含まれ、Task 1には含まれないという結果が返ってくる。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76 これによって、分割周りの部分が正しく処理される。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
78
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
79 \newpage
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
80
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 \section{まとめと今後の課題}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82 これまでにBoyer-Moore String Search Algorithmと、Input Data分割時の処理の実装を行った。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83 検索文字列の数が未分割、分割時に正しい結果が返ってきていることを確認した。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
84 しかし検索文字列については、現在ハードコーディングのため実行時に指定することができないので、それを改良する必要がある。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
86 プログラムの全体的な処理速度を向上させるには、並列I/Oを実装することにより実現できるが、
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87 それについてはこれから実装、検証していく。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
88
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
89 \thispagestyle{fancy}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
90 \begin{thebibliography}{9}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
91
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
92 \bibitem{kinjyo}金城裕、河野真治、多賀野海人、小林佑亮 (琉球大学)\\
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
93 ゲームフレームワーク Cerium Task Manager の改良\\
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
94 情報処理学会システムソフトウェアとオペレーティング・システム研究会 (OS), April 2011
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
95
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
96 \bibitem{tomari}渡真利 勇飛、河野 真治(琉球大学)\\
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
97 Cerium Task Manager の GPGPU への対応\\
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
98 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)、May 2013
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
99
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
100 \bibitem{BM}J.S.Moore, R.S. Boyer.\\
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
101 A Fast String Searching Algorithm\\
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
102 Communications of the Association for Computing Machinery, 1977,pp.762-772.
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
103
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
104 \bibitem{shinya}新屋 良磨,光成 滋生,佐々 政孝(東京大学)\\
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
105 並列化と実行時コード生成を用いた正規表現マッチングの高速化\\
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
106 日本ソフトウェア科学会大会第28回大会 、2011/9/24
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
107
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
108 \end{thebibliography}
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
109 \end{document}
|