Mercurial > hg > Papers > 2014 > masakoha-thesis > final

comparison preliminary/final-thesis.tex @ 57:a56ad81ccdf9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fic
author Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
date Sat, 22 Feb 2014 16:36:51 +0900
parents 5d25f13493c3
children 6efbdf3218c5
comparison
equal deleted inserted replaced
56:5d25f13493c3 57:a56ad81ccdf9
43 Cerium Task Managerは、並列処理をTask単位で記述する。関数やサブルーチンをTaskとして扱い、そのTaskに対してInput Data、Output Data及び依存関係を設定する。そして、それに基づいた設定の元でTaskに管理し、実行される。本稿で述べるInput Dataとは、検索対象となるテキストファイルのことである。 43 Cerium Task Managerは、並列処理をTask単位で記述する。関数やサブルーチンをTaskとして扱い、そのTaskに対してInput Data、Output Data及び依存関係を設定する。そして、それに基づいた設定の元でTaskに管理し、実行される。本稿で述べるInput Dataとは、検索対象となるテキストファイルのことである。
44 44
45 Cerium Task ManagerはPlayStation 3/Cell、Mac OS X及びLinux上で利用することが可能で、近年ではGPUへの利用も可能となった。\cite{tomari} 45 Cerium Task ManagerはPlayStation 3/Cell、Mac OS X及びLinux上で利用することが可能で、近年ではGPUへの利用も可能となった。\cite{tomari}
46 46
47 \section{I/O を含む Task の概要} 47 \section{I/O を含む Task の概要}
48 ファイルを読み込んで一定の大きさでファイルを分割し (File Read)、それらに対してそれぞれ文字列検索等の処理 (Run Tasks)を行う。
49 そしてそれぞれの処理から返されたの結果 (Output Data)を最後に集計をして結果を返す(Run resultTask)。(図\ref{fig:includeio})
48 50
49 図\ref{fig:includeio} 51 図\ref{fig:includeio}
50 52
51 \begin{figure}[htbp] 53 \begin{figure}[htbp]
52 \begin{center} 54 \begin{center}
53 \includegraphics[width=0.4\textwidth]{pic/includeio.pdf} 55 \includegraphics[width=0.4\textwidth]{pic/includeio.pdf}
54 \end{center} 56 \end{center}
55 \caption{includeio} 57 \caption{I/O を含む Task}
56 \label{fig:includeio} 58 \label{fig:includeio}
57 \end{figure} 59 \end{figure}
58 60
61 先行研究では、File Readの部分は mmap 関数を使用して実装していた。mmap 関数での実装の場合はコードの記述が容易である。
59 62
60 \section{並列処理向け I/O の設計と実装} 63 \section{並列処理向け I/O の設計と実装}
61 64
62 図\ref{fig:blockedreadimage} 65 \subsection{mmap での実装の問題点}
63 66
64 \begin{figure}[htbp] 67 mmap でファイルを読み込むタイミングは、mmap 関数が呼ばれたときではなく、mmap した領域に対して何らかのアクセスをしたときに初めてファイルが読み込まれる。
65 \begin{center} 68 つまり、分割された Task は文字列検索をすぐに行うのではなく、文字列検索を行おうとした時に初めてファイルが格納される。
66 \includegraphics[width=0.4\textwidth]{pic/blockedreadimage.pdf} 69 Task は複数一斉に実行されることが望ましいが、mmap だとそれぞれの Task で読み込みが起こってしまうので、I/O ネックによる Task の待ちが発生する恐れがある。
67 \end{center}
68 \caption{Blocked Read image}
69 \label{fig:blockedreadimage}
70 \end{figure}
71 70
72 図\ref{fig:blockedreadwait} 71 \subsection{Blocked Read の設計と実装}
72 Blocked Read とは、あるサイズずつで読み込む処理と、それらに文字列検索行う処理を分離させるための実装方法である。
73 この方法では、読み込み専用の Blocked Read と、文字列検索を行う Task Blocks をを別々に生成し処理を行う。
74 Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行い、読み込みされ次第それぞれの文字列検索が行われる。
75
76 Task は 1つずつ起動すると、起動した Task でメモリを圧迫してしまうため、Task を複数まとめたブロック単位で起動を行う。
77 この1つのブロックで処理されるテキストファイルを、Blocked Read で読み込んでいき、読み込みが終わったら読み込まれた範囲の Task Blocks を起動する。
78 もし、Blocked Read で読み込まれる前にその範囲を担当する Task が起動してしまうと、正しい結果が返ってこない。
79 それを防止するために、Task Blocks は必ず Blocked Read が行われてから起動するように wait をかけている。
80 (図\ref{fig:blockedreadwait})
73 81
74 \begin{figure}[htbp] 82 \begin{figure}[htbp]
75 \begin{center} 83 \begin{center}
76 \includegraphics[width=0.4\textwidth]{pic/blockedreadwait.pdf} 84 \includegraphics[width=0.4\textwidth]{pic/blockedreadwait.pdf}
77 \end{center} 85 \end{center}
78 \caption{Wait for Blocked Read} 86 \caption{Wait for Blocked Read}
79 \label{fig:blockedreadwait} 87 \label{fig:blockedreadwait}
80 \end{figure} 88 \end{figure}
81 89
90 \subsection{I/O 専用 thread の実装}
91 Cerium Task Manager では Task 単位で CPU Type の設定を変更することができる。
92 SPE\_ANY という CPU Type を設定すると、Cerium Task Manager 側が自動的に CPU を割り振ってくれる。
93 しかし、今回の実装でこのCPU Type を使用してしまうと、Blocked Read Task の隙間時間に Task が割り振られてしまう問題がある。
94 (図\ref{fig:speany})
82 95
83 図\ref{fig:io0} 96 \begin{figure}[htbp]
97 \begin{center}
98 \includegraphics[width=0.4\textwidth]{pic/speany.pdf}
99 \end{center}
100 \caption{SPE\_ANYでの設定時}
101 \label{fig:speany}
102 \end{figure}
103
104 その問題を解決するために、IO\_0 という CPU Type を新しく実装した。
105 IO\_0 は他の CPU Type よりも priority を高く設定しているので、他の Task に割り込まれることがないようにした。
106 (図\ref{fig:io0})
84 107
85 \begin{figure}[htbp] 108 \begin{figure}[htbp]
86 \begin{center} 109 \begin{center}
87 \includegraphics[width=0.4\textwidth]{pic/io0.pdf} 110 \includegraphics[width=0.4\textwidth]{pic/io0.pdf}
88 \end{center} 111 \end{center}
89 \caption{io0} 112 \caption{IO\_0 での実装時}
90 \label{fig:io0} 113 \label{fig:io0}
91 \end{figure} 114 \end{figure}
92 115
116 \section{ベンチマーク}
93 117
94 図\ref{fig:speany} 118 \subsection{実験環境}
119 \begin{itemize}
120 \item Mac OS X Mavericks (10.9.1)
121 \item HDD 1TB、Memory 16GB、CPU 2*2.66 GHz 6-Core Intel Xeon
122 \item ファイルサイズ 10GBに対して検索文字列がいくつ含まれるのかカウント
123 \end{itemize}
124 \subsection{実験結果}
95 125
96 \begin{figure}[htbp] 126 \begin{tiny}
97 \begin{center} 127 \begin{table}[ht]
98 \includegraphics[width=0.4\textwidth]{pic/speany.pdf} 128 \begin{center}
99 \end{center} 129 \label{table:preaddata}
100 \caption{speany} 130 \small
101 \label{fig:speany} 131 \begin{tabular}[t]{c|l}
102 \end{figure} 132 \hline
133 読み込み方法 & 実行速度(s)\\
134 \hline
135 mmap & XX.XXX \\
136 \hline
137 Blocked Read \& SPE\_ANY & XX.XXX \\
138 \hline
139 Blocked Read \& IO\_0 & XX.XXX \\
140 \hline
141 \end{tabular}
142 \caption{file read の実行結果}
143 \end{center}
144 \end{table}
145 \end{tiny}
103 146
104 \section{ベンチマーク}
105 147
106 \section{まとめと今後の課題} 148 \section{まとめと今後の課題}
107 149
108 \thispagestyle{fancy} 150 \thispagestyle{fancy}
109 \begin{thebibliography}{9} 151 \begin{thebibliography}{9}
114 156
115 \bibitem{tomari}渡真利 勇飛、河野 真治(琉球大学)\\ 157 \bibitem{tomari}渡真利 勇飛、河野 真治(琉球大学)\\
116 Cerium Task Manager の GPGPU への対応\\ 158 Cerium Task Manager の GPGPU への対応\\
117 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)、May 2013 159 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)、May 2013
118 160
119 \bibitem{BM}J.S.Moore, R.S. Boyer.\\
120 A Fast String Searching Algorithm\\
121 Communications of the Association for Computing Machinery, 1977,pp.762-772.
122
123 \end{thebibliography} 161 \end{thebibliography}
124 \end{document} 162 \end{document}