0
|
1 \documentclass[twocolumn,twoside,9.5pt]{jarticle}
|
|
2 \usepackage[dvipdfmx]{graphicx}
|
|
3 \usepackage{picins}
|
|
4 \usepackage{fancyhdr}
|
|
5 \pagestyle{fancy}
|
|
6 \lhead{\parpic{\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 卒業研究発表会}
|
|
7 \rhead{}
|
|
8 \cfoot{}
|
|
9
|
|
10 \setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
|
|
11 \setlength{\headheight}{0mm}
|
|
12 \setlength{\headsep}{5mm}
|
|
13 \setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
|
|
14 \setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
|
|
15 \setlength{\textwidth}{181mm}
|
|
16 \setlength{\textheight}{261mm}
|
|
17 \setlength{\footskip}{0mm}
|
|
18 \pagestyle{empty}
|
|
19
|
|
20 \begin{document}
|
1
|
21 \title{Implement asynchronous read of Cerium}
|
2
|
22 \author{148585H {Masataka}{KOHAGURA}}
|
0
|
23 \date{}
|
|
24 \maketitle
|
|
25 \thispagestyle{fancy}
|
|
26
|
1
|
27 \section{Abstract}
|
|
28 We are developing a Parallel task manager Cerium.
|
|
29 I/O Included programming, read times is more heavy than processing time of Task.
|
|
30 We assume to inplement included I/O programm by parallel programming. If I/O time is heavy, it is slowly included I/O programm.
|
|
31 In the conventional implementation, we implemented file read with "mmap()" or "read()".
|
|
32 Inplementation this function down the degree of parallelism because another CPU stop while reading files.
|
|
33 In real read situation, asynchronous read sometimes gives good result on word count example. We gives the result and analysis.
|
0
|
34 \section{Cerium Task Manager}
|
2
|
35 We program parallel per tashs with Task Manager.
|
|
36 It is treated function and sub routins as task and we set depending, Input Data, and output data.
|
|
37 And, it is managed Task Manager setting. This paper's ``Input Data" is text file of search subject.
|
0
|
38
|
2
|
39 Cerium Task Manager can use on PlayStaion 3/Cell, MacOS X and Linux.
|
0
|
40
|
2
|
41 \section{Outline included I/O Task}
|
|
42 Split the file constant size after file reading and splits file are excluded string search.
|
|
43 And returns the results to the last counting.
|
|
44 (fig\ref{fig:includeio})
|
0
|
45
|
|
46 \begin{figure}[htbp]
|
|
47 \begin{center}
|
|
48 \includegraphics[width=0.5\textwidth]{pic/includeio.pdf}
|
|
49 \end{center}
|
2
|
50 \caption{include I/O Task}
|
0
|
51 \label{fig:includeio}
|
|
52 \end{figure}
|
|
53
|
|
54 \section{並列処理向け I/O の設計と実装}
|
|
55
|
|
56 \subsection{mmap での実装の問題点}
|
|
57 先行研究では mmap によるファイルの読み込みを行っていた。
|
|
58 mmap でファイルを読み込むタイミングは、mmap 関数が呼ばれたときではなく、mmap した領域に対して何らかのアクセスをしたときに初めてファイルが読み込まれる。
|
|
59 つまり、分割された Task は文字列検索をすぐに行うのではなく、文字列検索を行おうとした時に初めてファイルが格納される。
|
|
60 Task は複数一斉に実行されることが望ましいが、mmap ではそれぞれの Task で読み込みが起こってしまうため、I/O ネックによる Task の待ちが発生する。
|
|
61
|
|
62 \subsection{Blocked Read の設計と実装}
|
|
63 Blocked Read とは、あるサイズずつで読み込む処理と、それらに文字列検索を行う処理を分離させるための実装方法である。
|
|
64 この方法では、読み込み専用の Blocked Read と、文字列検索を行う Task Blocks を別々に生成し処理を行う。
|
|
65 Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行い、読み込みされ次第それぞれの文字列検索が行われる。
|
|
66
|
|
67 Task は 1つずつ起動すると、起動した Task でメモリを圧迫してしまうため、Task を複数まとめたブロック単位で起動を行う。
|
|
68 この1つのブロックで処理されるテキストファイルを、Blocked Read で読み込んでいき、読み込みが終わったら読み込まれた範囲の Task Blocks を起動する。
|
|
69 もし、Blocked Read で読み込まれる前にその範囲を担当する Task が起動してしまうと、正しい結果が返ってこない。
|
|
70 それを防止するために、Task Blocks は必ず Blocked Read が行われてから起動するように wait をかけている。
|
|
71 (図\ref{fig:blockedreadwait})
|
|
72
|
|
73 \begin{figure}[htbp]
|
|
74 \begin{center}
|
|
75 \includegraphics[width=0.5\textwidth]{pic/blockedreadwait.pdf}
|
|
76 \end{center}
|
|
77 \caption{Wait for Blocked Read}
|
|
78 \label{fig:blockedreadwait}
|
|
79 \end{figure}
|
|
80
|
|
81 \subsection{I/O 専用 thread の実装}
|
|
82 Cerium Task Manager では Task 単位で CPU Type の設定を変更することができる。
|
|
83 SPE\_ANY という Type を設定すると、Cerium Task Manager 側が自動的に CPU を割り振る。
|
|
84 しかし、今回の実装でこの Type を使用してしまうと、Blocked Read Task に割り込んで Task が割り振られてしまう問題がある。
|
|
85 その問題を解決するために、IO\_0 という I/O 専用の thread を実装した。
|
|
86 この Thread は I/O を最優先に実行されるようにチューニングを行った。
|
|
87 (図\ref{fig:io0})
|
|
88 %%
|
|
89 %(図\ref{fig:speany})
|
|
90 %
|
|
91 %\begin{figure}[htbp]
|
|
92 %\begin{center}
|
|
93 %\includegraphics[width=0.4\textwidth]{pic/speany.pdf}
|
|
94 %\end{center}
|
|
95 %\caption{SPE\_ANYでの設定時}
|
|
96 %\label{fig:speany}
|
|
97 %\end{figure}
|
|
98
|
|
99
|
|
100 \begin{figure}[htbp]
|
|
101 \begin{center}
|
|
102 \includegraphics[width=0.4\textwidth]{pic/io0.pdf}
|
|
103 \end{center}
|
2
|
104 \caption{implement IO\_0}
|
0
|
105 \label{fig:io0}
|
|
106 \end{figure}
|
|
107
|
|
108 \newpage
|
|
109
|
2
|
110 \section{Benchmark}
|
0
|
111
|
|
112 \begin{itemize}
|
|
113 \item Mac OS X Mavericks (10.9.1)
|
|
114 \item HDD 1TB、Memory 16GB、CPU 2*2.66 GHz 6-Core Intel Xeon
|
|
115 \item CPU NUM 12
|
|
116 \item 10GB のファイルに対して Booye-Moore String Search をかけ、検索文字列がいくつ含まれているのかカウント
|
|
117 \item 測定はファイルの読み込みから結果が返ってくるまでの時間
|
|
118 \end{itemize}
|
|
119
|
|
120 %以下の表\ref{table:result}に実行結果を示す。
|
|
121 以下の表1に実行結果を示す。
|
|
122
|
|
123 \begin{tiny}
|
|
124 \begin{table}[ht]
|
|
125 \begin{center}
|
|
126 \label{table:result}
|
|
127 \small
|
|
128 \begin{tabular}[t]{c|r}
|
|
129 \hline
|
2
|
130 Read Method & Spend Average Time(s)\\
|
0
|
131 \hline
|
|
132 mmap & 154.6 \\
|
|
133 \hline
|
|
134 一括 Read & 114.9 \\
|
|
135 \hline
|
|
136 Blocked Read \& SPE\_ANY & 106.0 \\
|
|
137 \hline
|
|
138 Blocked Read \& IO\_0 & 99.2 \\
|
|
139 \hline
|
|
140 \end{tabular}
|
2
|
141 \caption{result}
|
0
|
142 \end{center}
|
|
143 \end{table}
|
|
144 \end{tiny}
|
|
145
|
|
146 %\ref{table:result}より、mmap より Blocked Read \& IO\_0 の実行速度が 36 \% 改善された。
|
|
147 表1より、mmap より Blocked Read \& SPE\_ANY の実行速度が 31\% 改善された。
|
|
148 また、Blocked Read の CPU Type も SPE\_ANY から IO\_0 に変更することによって更に 4 \% の改善が見られた。
|
|
149 これより、I/O を含む並列処理を行う場合は、mmap で実装することによって自動的に読み込ませるのではなく、自分自身で読み込みを制御したほうが速くなることがわかる。
|
|
150
|
2
|
151 \section{conclusion}
|
0
|
152 mmap で I/O を含む Task を実装するとき、mmap した領域に対して何らかの処理が加わった時にしか読み込みが行わないので、それぞれの Task に読み込みを任せてしまうことになる。
|
|
153 それを解決する方法として、Blocked Read と Task を並列に行う実装を行った。
|
|
154 また、Blocked Read が、他の Task に割り込まれないように改善した結果、35 \% の実行速度の改善が見られた。
|
|
155 本研究より、I/O を含む Task は、チューニング次第で更に改善する余地があると考える。
|
|
156
|
|
157
|
|
158 \thispagestyle{fancy}
|
|
159 \begin{thebibliography}{9}
|
|
160
|
|
161 \bibitem{kinjyo}金城裕、河野真治、多賀野海人、小林佑亮 (琉球大学)\\
|
|
162 ゲームフレームワーク Cerium Task Manager の改良\\
|
|
163 情報処理学会システムソフトウェアとオペレーティング・システム研究会 (OS), April 2011
|
|
164
|
|
165 \end{thebibliography}
|
|
166 \end{document}
|