Mercurial > hg > Papers > 2011 > yutaka-jssst
comparison paper/jssst.tex @ 5:67d7c43dc4ea
reduce section
author | Daichi TOMA <e085740@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 08 Aug 2011 20:21:36 +0900 |
parents | c3b2314920d7 |
children | a8812d132583 |
comparison
equal
deleted
inserted
replaced
4:cfe50cf740ce | 5:67d7c43dc4ea |
---|---|
71 % | 71 % |
72 \maketitle | 72 \maketitle |
73 | 73 |
74 \section{はじめに} | 74 \section{はじめに} |
75 | 75 |
76 %学生実験用にゲームフレームワーク Cerium を開発した。Cerium の TaskManager は | 76 \section{Ceriumとは} |
77 我々は並列プログラミング用のフレームーク Cerium TaskManager を開発している。Cerium は PS3/Cell, MacOSX, Linux | |
78 上で開発できる。それぞれのプラットフォームで同じプログラムで動作する。その中でも特にCellに特化しているといえる。 | |
79 Cerium TaskManager では、関数やサブルーチンを Task として扱う。Task は Task 同士の依存関係 | |
80 に従って、実行される。 | |
81 Cell 上の場合、各SPEに Task が割り当てられ、並列に実行される。 | |
82 Cerium は TaskManager に加え、SceneGraph, RenderingEngine で構成され、この3つでゲームフレームワークとして | |
83 動作する。 | |
84 %RenderingEngine は Task に分割され、並列に処理される。 | |
85 Task には input データ、output データ、依存関係を設定する。 | |
86 %Task ベースでプログラミングする場合、処理をTaskに分割、input, output データの分割、Task同士の依存関係に工夫が必要になってくる。 | |
87 ゲームや、WordCount, Sort を例題として実装した。 | |
88 TaskManagerと、TaskManager を使うユーザ側の両方の視点から、 | |
89 実装の際に直面した問題とその改良方法と効果について報告する。 | |
90 | 77 |
91 \section{Cell Broadband Engine} | 78 \section{Cell Broadband Engine} |
92 | 79 |
93 \begin{figure}[tb] | 80 \begin{figure}[tb] |
94 \begin{center} | 81 \begin{center} |
132 転送元と転送先のアドレスが 16 バイト境界に揃えられている必要がある。 | 119 転送元と転送先のアドレスが 16 バイト境界に揃えられている必要がある。 |
133 転送データが 16 バイト未満の場合、データサイズは 1,2,4,8 バイトで、 | 120 転送データが 16 バイト未満の場合、データサイズは 1,2,4,8 バイトで、 |
134 転送サイズに応じた自然なアライメントである (転送サイズのバイト境界に | 121 転送サイズに応じた自然なアライメントである (転送サイズのバイト境界に |
135 揃えられている) ことが条件となる。 | 122 揃えられている) ことが条件となる。 |
136 | 123 |
137 \section{Cerium の改良} | 124 \section{Ceriumでの並列プログラミングの問題点} |
138 | 125 |
139 Cerium TaskManager では PPE で Task を定義し、PPE から SPE に Task を割り振る。 | 126 \section{Continuation based C との相性} |
140 SPE は DMA転送(\ref{sec:dma}節)によって、Taskと、Taskで用いるデータを受け取る。 | 127 |
141 DMA転送を用いる場合、待ち時間が発生し、その間SPEの処理が止まる。 | 128 \section{C++ との相性} |
142 そのため、転送をパイプライン化し、DMA転送の待ち | 129 |
143 を隠す必要がある。Cerium では SPE にスケジューラを持ち Task とデータ の 読み込み、実行、書き出し | 130 \section{Data Segment を用いた Cerium の再設計} |
144 をパイプライン化している。(\ref{fig:scheduler})Task は一つずづ転送されるのではく、ある程度の | 131 |
145 数を集めて、TaskList として転送される。 | 132 \subsection{Data Segment の型} |
146 | 133 |
147 \begin{figure}[tb] | 134 \subsection{Data Segment のAPI} |
148 \begin{center} | 135 |
149 \scalebox{0.3}{\includegraphics{./images/scheduler.eps}} | 136 \subsection{Task Dependendcy} |
150 \end{center} | 137 |
151 \caption{スケジューラ} | 138 \subsection{Data Segment Storage Type} |
152 \label{fig:scheduler} | 139 |
153 \end{figure} | 140 \subsection{Data Segment の処理の記述} |
154 | 141 |
155 | 142 \section{期待される効果} |
156 \subsection{MailQueue} | |
157 Task には依存関係が設定でき、PPE 側で解決する。実行完了した Task の情報を SPE 側から PPE 側に 通知するために CellのMailbox機能を使用した(\ref{sec:mail-box})。 | |
158 SPEスケジューラは Task が処理完了になる毎に、Mailを Outbound Mailbox に書きこむので、PPE側でMailの読み込みが間に合わないと、待ちが入り、SPEの処理が止まってしまう。 | |
159 | |
160 | |
161 これを解消するためにMailQueueを導入した。MailQueueは、SPEから書き込みきれないMailを一時的にキューに退避させるものである。 | |
162 TaskListを書きだす時に溜まったQueueの中身をすべて書き出す。 | |
163 Task完了を知らせる Mail書き出しの待ちは、Task毎から、TaskList毎になる。 | |
164 TaskListのサイズは32。 | |
165 MailQueueを有効にしたときの実行速度は以下にようになる | |
166 速度比較には、RenderingEngineを使ったボールが跳ねる例題ball\_boundを用いた。 | |
167 | |
168 \begin{table}[!htb] | |
169 \begin{center} | |
170 \caption{MailQueue の効果(ball\_bound)} \label{tab:mailqueue} | |
171 \hbox to\hsize{\hfil | |
172 \begin{tabular}{|c|l|l|c|} \hline | |
173 & 改良前 & 改良後 & 性能\\ \hline | |
174 ball\_bound & 29 FPS & 33.3 FPS & 15\%向上 \\ \hline | |
175 \end{tabular}\hfil} | |
176 \end{center} | |
177 \end{table} | |
178 | |
179 MailQueue導入によって、27\%の処理性能の向上が見られた。Task毎からTaskList毎にMailの通知回数が減ったので、待ち時間が入る | |
180 タイミングが減った。それによって、SPEの稼働率が向上し、処理性能の向上につながったと考えられる。 | |
181 | |
182 \subsection{TaskArray} \label{taskarray} | |
183 | |
184 Task の依存関係を解決するために、SPEから Mail によってPPEへと処理が完了したTaskの情報が通知される。 | |
185 その際に、同じ種類のTaskは一つのMailでよい場合がある。 | |
186 そこで、我々は Task Array を提案、実装した。 | |
187 Task Array は、複数の Task をまとめて扱うことが出来る。Task Array に登録した順番で | |
188 依存関係を設定しているので、PPE で解決する Task の数が減り、 SPE からの TaskList 要求に応答しやすくなる。 | |
189 また、一度に多くの Task を TaskList に登録できるため、 SPE 側からの TaskList 要求の回数が減り、待ち時間が | |
190 生じる可能性が減る。 | |
191 | |
192 Rendering Engine の中で、最も数が多く生成される DrawSpanTask を Task Array 化した。 | |
193 ボールが跳ねる例題(ball\_bound)、地球と月を表示する例題を対象に効果を測った。 FPS(Frame Per Second) は、一秒間に | |
194 表示できる Frame 数のことである。TaskArray は MailQueue と同様に Mail通知に関係している。 | |
195 それぞれの有無の場合を計測した。 | |
196 | |
197 \begin{table}[!htb] | |
198 \begin{center} | |
199 \caption{TaskArrayの効果(ball\_bound)} \label{tab:taskarray} | |
200 \hbox to\hsize{\hfil | |
201 \begin{tabular}{|c|l|l|c|} \hline | |
202 & 改良前 & 改良後 & 性能\\ \hline | |
203 ball\_bound & 29 FPS & 34 FPS & 17\%向上 \\ \hline | |
204 \end{tabular}\hfil} | |
205 \end{center} | |
206 \end{table} | |
207 | |
208 \begin{table}[htb] | |
209 \begin{center} | |
210 \caption{Task Array と MailQueue の効果(universe)} | |
211 \label{tab:taskarray-mailqueue} | |
212 \begin{tabular}{|c|c|c|c|c|} | |
213 \hline | |
214 TaskArray & MailQueue & FPS & dma wait & mail wait\\ | |
215 \hline | |
216 あり & あり & 20 FPS & 1.78\% & 67\&\\ | |
217 \hline | |
218 あり & なし & 18.5 FPS & 1.88\% & 69\%\\ | |
219 \hline | |
220 なし & あり & 18.5 FPS & 1.4\% & 74\%\\ | |
221 \hline | |
222 なし & なし & 16.4 FPS & 3.3\% & 84\%\\ | |
223 \hline | |
224 \end{tabular} | |
225 \end{center} | |
226 \end{table} | |
227 | |
228 結果から DrawSpanTask を Task Array 化すると、FPS が上昇し、mail の wait 時間が減ったことが分かる。 | |
229 Rendering Engine では、 PPE 側でも処理をするべき Task があり、常に PPE が稼動している状態になって | |
230 いる。そのため mail を処理する時間が遅れ、SPE のmail 待ちが発生していると考えられる。 Task Array 化 | |
231 で Task をまとめることで SPE が一つの TaskList で多くの Task を実行できるようになったため、 TaskList | |
232 を要求する回数が減って、待ち時間が発生する回数も減少した。また、それは SPE からの mail の数が減った | |
233 ということなので、PPE 側の mail 処理の時間短縮になったと考えられる。 | |
234 | |
235 \subsection{PipeLine化} | |
236 | |
237 Cerium では RenderinEngine を実装している。RenderinEngine は大きく分けて、 | |
238 CreatePolygon, CreateSpan, DrawSpan, の | |
239 3つのTaskから構成されている。(\ref{fig:rendering-flow}) | |
240 | |
241 \begin{figure}[tb] | |
242 \begin{center} | |
243 \scalebox{0.3}{\includegraphics{./images/rendering3.eps}} | |
244 \end{center} | |
245 \caption{レンダリングエンジンの流れ} | |
246 \label{fig:rendering-flow} | |
247 \end{figure} | |
248 | |
249 Span とは、ポリゴンに対するある特定Y座に関するデータを抜き出したものである。 | |
250 この3つのTaskはそれぞれバリア同期を行いながら、順に実行される。 | |
251 Cerium において、バリア同期を行う場合には二つの待ち時間がある。 | |
252 \begin{itemize} | |
253 \item SPEが他のSPEを待つ時間 | |
254 \item バリア同期が完了し、PPE側で次のTaskが作られる時間 | |
255 \end{itemize} | |
256 | |
257 この二つの時間の間SPEの処理が止まり、処理性能の低下につながる。 | |
258 この待ち時間を回避するには、Taskの粒度を下げる、他のSPEの処理完了を待っているSPEに、別のTaskを割り当てる、等の方法がある。 | |
259 別のTaskを割り当てるにはTaskの実行をパイプライン化する方法がある。 | |
260 | |
261 そこで、特に処理の重いDrawSpanTask と、CreatePolygon,CreateSpan のTask でパイプライン化を行った。(\ref{fig:rend-dep}) | |
262 | |
263 \begin{figure}[tb] | |
264 \begin{center} | |
265 \scalebox{0.4}{\includegraphics{./images/rend-dep.eps}} | |
266 \end{center} | |
267 \caption{RenderingEngineのパイプライン化の様子} | |
268 \label{fig:rend-dep} | |
269 \end{figure} | |
270 | |
271 速度比較の対象として、SuperDandy と呼ばれる、学生実験で制作されたシューティングゲームを用いた。 | |
272 FPS は一秒あたりの Rendering Engine 全体の処理回数 (Frame per Scecond)、busy ration はSPE の | |
273 稼働率。 | |
274 | |
275 | |
276 \begin{table}[!htb] | |
277 \begin{center} | |
278 \caption{PipeLine化の結果} \label{tab:busy_ratio} | |
279 \hbox to\hsize{\hfil | |
280 \begin{tabular}{|c|l|l|c|} \hline | |
281 & 改良前 & 改良後 & 性能\\ \hline | |
282 FPS & 29.4 FPS & 49.5 FPS & 68\%向上 \\ \hline | |
283 busy\_ration & 47.2\% & 78.1\% & 30.9\&向上 \\ \hline | |
284 \end{tabular}\hfil} | |
285 \end{center} | |
286 \end{table} | |
287 | |
288 パイプライン化した結果(\ref{tab:busy_ratio})、SPEの稼働率が向上し、FPSも向上した。 | |
289 処理性能を維持するには、SPEはなるべく稼働させ続けなければならない。 | |
290 その為には処理をTaskに分割し、並列実行するだけでなく、バリア同期などで、 | |
291 SPEの待ち時間が発生することへ対処しないといけない。 | |
292 その対処の一つとしてそれにパイプライン化は有効である。 | |
293 | |
294 | |
295 \subsection{SPEでのキャッシュ効果} | |
296 | |
297 \subsubsection{テクスチャの管理} | |
298 Cerium ではソフトウェアレンダリングを、Task で定義し、処理している。描画の際には、SPEのLSへ必要なテクスチャの | |
299 情報を読み込む。SPE のメモリ領域は 256KB しかないため、テクスチャのデータを分割し転送する必要がある。 | |
300 そこで、Cerium ではテクスチャを8x8のブロックに分割し、必要な時に沿って、ブロックを転送する方法を取った。 | |
301 | |
302 \subsubsection{テクスチャの縮小} | |
303 遠くにあるオブジェクトは小さく描画される。この場合、使用されるテクスチャは原寸大である | |
304 必要がない。そこで、オリジナルのテクスチャの他に縮小したテクスチャを用意し、描画される | |
305 オブジェクトの大きさによって、使用するテクスチャを変更することにした。 | |
306 | |
307 テクスチャは Tile に分割しなければならないため、縦横ともに 8 の倍数を保つようにする。 | |
308 これまでは、テクスチャの縦横どちらかのサイズが最小 (8ドット) になったとき、縮小画像生成を終了 | |
309 していたが、テクスチャのサイズが縦横で違う場合、長い方に合わせて空のデータを埋め込み 8 の倍数 | |
310 の正方形にするように改良した。この改良によってテクスチャの最大縮小率を正確に求めることが出来るよう | |
311 になった。 | |
312 | |
313 \subsubsection{ハッシュの管理} | |
314 | |
315 この時に、頻繁にテクスチャを読み込む場合にはその読み込みがボトルネックとなる。そこでキャッシュを実装した。 | |
316 キャッシュは MemorySegment と呼ばれるデータ構造単位でハッシュで管理する。MemorySegment はある一定の | |
317 大きさに決め打った連続したメモリ領域のことである。キャッシュ実装の効果を示す。 | |
318 速度比較の対象には、使用するテクスチャ表示範囲が狭いball\_bound と、画面すべてにテクスチャを表示するpanelを用いる。 | |
319 | |
320 \begin{table}[!htb] | |
321 \begin{center} | |
322 \caption{1秒辺りの Rendering Engine 全体の処理回数} | |
323 \hbox to\hsize{\hfil | |
324 \begin{tabular}{|c|l|l|c|} \hline | |
325 & 改良前 & 改良後 & 性能\\ \hline | |
326 ball\_boud & 4 FPS & 30 FPS & 7.5倍向上 \\ \hline | |
327 panel & 0.2 FPS & 2.6 FPS & 13倍向上 \\ \hline | |
328 \end{tabular}\hfil} | |
329 \end{center} | |
330 \end{table} | |
331 | |
332 テクスチャような頻繁な転送が起こり得る場合には、キャッシュが非常に有効であることがわかった。 | |
333 Cellのような分散メモリでは、データの転送は慎重に管理しできるだけ転送回数を減らすことが性能 | |
334 向上につながる。 | |
335 | |
336 \subsection{Memory Access} | |
337 | |
338 Cellにおいて、SPEへのデータの割り振り方が性能に関わる場合がある。 | |
339 それはデータを得るために、DMA転送が頻繁に起きるときである。 | |
340 Cerium を用いて実装したWordCountを例にとってみる。 | |
341 WordCountのTaskは二つある。 | |
342 | |
343 \begin{enumerate} | |
344 \item WordCountTask | |
345 \item PrintTask | |
346 \end{enumerate} | |
347 | |
348 WordCountTaskは、inputで与えられたdataをword countし、output dataに書き出すTaskである。 | |
349 PrintTaskはすべてのWordCountTaskの実行完了を待ち、outputへ書き出された値を集計し出力するTaskである。 | |
350 一度にSPEに渡せるデータ容量はDMAの仕様上16Kbyteまでである。さらに転送する際には16の倍数byteである必要がある。 | |
351 | |
352 wcするfileをメモリへマッピングし、WordCountTask | |
353 のinputに、file dataのアドレスを16kbyteごとに指定していく(\ref{fig:wc-graf})。 | |
354 | |
355 \begin{figure}[tb] | |
356 \begin{center} | |
357 \scalebox{0.3}{\includegraphics{./images/wc_graf1.eps}} | |
358 \end{center} | |
359 \caption{WordCountのTaskの流れ} | |
360 \label{fig:wc-graf} | |
361 \end{figure} | |
362 | |
363 PrintTaskはWordCountTaskを待ちTaskと設定し、WordCountがすべて終わらないと、 | |
364 実行されない。 | |
365 | |
366 %このWordCountTaskにデータを渡す際には、メインメモリへのアクセスが局所性を保ちながら | |
367 %処理されるようにした方が良い。WC対象のデータを各SPEがバラバラな領域から取得する場合と | |
368 %ある程度まとまった領域から取得するようにした場合とで比較をした。取得のバラつきはTaskArray | |
369 %のTaskの設定である程度操作できる。 | |
370 | |
371 | |
372 WordCountにはTaskArrayを用いた。TaskArrayを用いる場合に注意すべき点がある。 | |
373 TaskArrayを使わず、Taskを用いる場合、Taskは生成された順番にそって各SPEに割り振られていく。 | |
374 ファイルをmmapし、その領域を上から順番にTaskに設定しているので各SPEは同時に近くのメモリ領域 | |
375 にアクセスすることになる。TaskArrayを用いた場合に生成された順にTaskArrayに設定するのはまずい。 | |
376 TaskArray一つは、一つのSPEのみで実行され、分割されない。 | |
377 TaskArrayに連続した領域を指すTaskばかりを格納すると、 | |
378 それによって、一つのSPEが連続領域を順番にアクセスして行く形になる。別のSPEは、16kB x TaskArrayのサイズ分離れた | |
379 領域からメモリアクセスを開始するので、 | |
380 離れたメモリ領域を各コアが同時にアクセスすることになる。 | |
381 なので、先に複数のTaskArrayを用意し、Taskが生成された順番にそって各TaskArrayに割り振るように改良した。 | |
382 | |
383 TaskArrayのサイズは64, Taskのinputデータの大きさは16KB, | |
384 wc対象のデータの大きさは約135MB。Taskの数は約8000。 | |
385 dma wait は処理全体にかかった時間のdma転送待ちの割合。 | |
386 改良前は各SPEが同時に離れた領域(各SPE間は 16KB x 64 離れる)にアクセスする。 | |
387 改良後は近くのメモリ領域(各SPE間はだいたい16KB 離れる)にアクセスする。 | |
388 | |
389 | |
390 \begin{table}[!htb] | |
391 \begin{center} | |
392 \caption{メモリアクセスの局所性を保った改良} \label{tab:memory-access} | |
393 \hbox to\hsize{\hfil | |
394 \begin{tabular}{|c|l|l|c|} \hline | |
395 & 改良前 & 改良後 & 性能\\ \hline | |
396 実行時間 & 30s & 1.9s & 15倍向上 \\ \hline | |
397 dma wait & 14\% & 8\% & 1.7倍向上 \\ \hline | |
398 \end{tabular}\hfil} | |
399 \end{center} | |
400 \end{table} | |
401 | |
402 | |
403 メモリアクセスの局所性を保った場合に処理性能の向上が見られた(\ref{tab:memory-access})。ページングや、スワッピングを | |
404 抑えることができたと考えられる。それに伴ってdma wait 時間も減少し、SPEの待ち時間が処理性能 | |
405 の向上に繋がっていると考える。 | |
406 | |
407 | |
408 \subsection{OpenGLとの比較} | |
409 | |
410 OpenGL (Open Graphics Library) とは、Silicon Graphics 社が開発した、3D グラフィックス | |
411 処理のためのプログラミングインターフェースである。 | |
412 上記で紹介した SuperDandy を Task を用いない OpneGL 上で動作するバージョンを用意して、Cerium | |
413 と性能を比較してみた。OpenGL は PPE だけで動作している。Cerium は今までの改良をすべて加えたもの。 | |
414 | |
415 \begin{table}[!htb] | |
416 \begin{center} | |
417 \caption{シューティングゲーム「dandy」の性能比較(OpenGL, Cerium))} \label{tab:dandy-compare} | |
418 \hbox to \hsize{\hfil | |
419 \begin{tabular}{|c|l|l|c|} \hline | |
420 & OpenGL & Cerium & 性能差\\ \hline | |
421 dandy & 17.5 FPS & 49.5 FPS & 2.9 倍\\ \hline | |
422 \end{tabular}\hfil} | |
423 \end{center} | |
424 \end{table} | |
425 | |
426 コアを1つ用いている OpenGL 版に比べて、Cerium では 2.9 倍の性能向上が見られた。 | |
427 SPEを活用し、改良によって待ち時間の削減ができ、性能の向上ができた。 | |
428 | |
429 \section{debug} | |
430 | |
431 並列プログラムの特徴として、デバッグが難しいことも挙げられる。 | |
432 実行が非決定的 (同じ状態で実行しても結果が異なる) な場合があり、 | |
433 バグの状態を再現することが難しい。 | |
434 また、個々の Core 上のデータを調べる必要があり、 | |
435 デバッガが複数の Core を取り扱えることが必須である。 | |
436 Cell の場合、動作している複数 の SPE の一つに対して | |
437 gdb で breakpoint を掛ければ、PPE や他の SPE も同時にストップするが、 | |
438 それら全ての CPU を手動で管理するのは厳しい。 | |
439 また、PPE と SPE ではメモリ空間が違うため、 | |
440 SPE から直接 PPE のデータを見ることができない。 | |
441 Cerium での開発工程は、 | |
442 | |
443 \begin{enumerate} | |
444 \item C によるシーケンシャルな実装 | |
445 \item 並列実行を考慮したデータ構造を持つ実装 | |
446 \item コードを分割し、シーケンシャルに実行する実装 | |
447 \item 分割したコードを並列実行する実装 | |
448 \end{enumerate} | |
449 | |
450 となっている。逐次的な実行で正常な動作を確認した後、並列に実行した場合に正常な | |
451 動作をしない場合がある。特にCell特有の問題として | |
452 データ構造が合っていない。つまり、DMA転送される際に、16アライメントに設定されていないか、 | |
453 データのサイズが16の倍数になっていない場合に注意しなければならない。またCeriumではPPE用と | |
454 SPE用が別個に存在するので、互いのコードが等価であるかもチェックしなければならない。 | |
455 一つのコードに統一しても良いが、別個で対応したい問題がでた時に対応してる。なるべく同一な | |
456 コードにするのがよい。 | |
457 本来SPEで動くべきTaskがPPEで動作するケースもあるので、それもチェックするべき。 | |
458 | |
459 \section{まとめ} | |
460 | |
461 本研究では ゲームフレーム Cerium TaskManager の改良を行った。 | |
462 特にCell上での実行の場合、SPEの活用が処理性能に大きく関わる。 | |
463 SPEからPPEへのMail通知には、PPEのMailを確認するタイミングが関わって | |
464 くるので、MailQueue, TaskArray を用いて | |
465 SPE側でなるべく通知にタイミングを減らし、待ち時間を減らした。 | |
466 SPEの稼働率を上げることで性能向上につながった。またキャッシュを用い、 | |
467 テクスチャなど頻繁に利用するデータをSPEのLSに常駐させることで、データ | |
468 転送の回数を減らし待ち時間を削減した。数種のTaskが混在し、バリア同期 | |
469 を行っている場合には、SPEの待ち時間が発生するので、Taskのパイプライン化 | |
470 によって解決した。またデータアクセスの局所性を保つことでデータ転送の待ち | |
471 時間を減少させることができる。Cerium は上記の改良を加え、改良前に比べ、 | |
472 約7倍の処理速度の向上が見られた。 | |
473 | |
474 Coreの待ち時間を減らすことは、Coreの稼働率の向上につながり処理性能が向上する。 | |
475 各Coreの待ち時間は並列プログラミングにおいて、特に注意しなければならない。 | |
476 それは、Amdahlの法則からも言える。 | |
477 | |
478 並列実行には Amdahl の法則(\cite{amdahl})があり、使用する CPU を増やしても、元のプログラムの並列化率 | |
479 が低ければ、その性能を活かすことができないとされている。例えば、プログラムの 8 割 | |
480 を並列化したとしても、6CPU で 3 倍程度の性能向上しか得られない(\ref{fig:amdahl}) | |
481 | |
482 \begin{figure}[htb] | |
483 \begin{center} | |
484 \scalebox{0.5}{\includegraphics{./images/amdahl.eps}} | |
485 \caption{Amdahl の法則} | |
486 \label{fig:amdahl} | |
487 \end{center} | |
488 \end{figure} | |
489 | |
490 このことから、恒常的に並列度を維持する必要があることが分かる。 | |
491 | |
492 \section{今後の課題} | |
493 | |
494 \subsection{依存関係の設定} | |
495 現在TaskのパイプラインはTaskの依存関係をユーザが明示的に記述している。 | |
496 Task の数が増えるとプログラミングの難易度が格段に上がってしまうという | |
497 問題がある。また、パイプライン化できる場所を特定することも難しくなる | |
498 この問題は Task の依存関係をユーザではなく、システム側が記述するようにすること | |
499 で解決できる。 Task の依存関係が、処理するデータの依存関係と直結しているので、 | |
500 データの依存関係をシステム側で監視し、その依存関係を元に処理を行うことでシステ | |
501 ム側からの依存関係の記述が実現できる。もしくは、Taskの依存関係は別の言語で記述 | |
502 し、TaskManager がその記述に沿って、定義されたTaskの実行する方法も考えられる。 | |
503 また、TaskArrayもTaskとデータの依存関係から、自動で作成できると考える。 | |
504 | |
505 \subsection{Code Load} | |
506 SPE は LS 以外のメモリに | |
507 直接アクセスすることができず、自身の LS の容量は 256KB である。 | |
508 現在Cerium では、プログラムを実行する前に、SPE で処理する Task のコードは事前に | |
509 SPE に転送している。しかし、Cerium の開発を続けていく上で、ついにコンパイルの最適化 | |
510 を行っていない状態のコードを SPE 上に置いておくことができなくなってしまった。 | |
511 この問題から、現在 Cerium が SPE 上にデータを転送している様にして、SPE 上に必要のない | |
512 コードの入れ替えを行う必要が出てきた。そこで、我々は SPE と PPE の間でやりとりする | |
513 データのすべてを Segment というデータ構造で行うことを提案する。その先駆けとして、 | |
514 現在は描画を行う Task にMemorySegment という形でデータの入れ替えのためのデータ構造 | |
515 を用いている。 | |
516 | |
517 \subsubsection{Taskの粒度} | |
518 Taskの粒度が大きい場合に、SPE間で、Taskの消化時間にバラつきがでやすい。 | |
519 それは特にバリア同期をしている場合に、待ち時間へ直結する。Taskを粒度が | |
520 小さい場合にはPPEとの通信時間がかさむ事になる。粒度が大きい場合には、 | |
521 他のTaskを投入することで解決できる。その方法がパイプラインである。 | |
522 実は粒度が小さい場合にも次のTaskを予想してdma転送などパイプライン化し | |
523 転送待ち時間を解消する対処法がある。 | |
524 しかし、CeriumのようにPPEへのMail通知で | |
525 同期ポイントがある場合にパイプライン化では対処できなかった。 | |
526 そこで今回、MailQueue,TaskArrayなど同期するタイミングの回数を | |
527 減らすことで、ある程度の改良を行った。TaskArrayはTaskの粒度が | |
528 大きくなる影響があり、また巨大なデータを分割アクセスする場合には | |
529 メモリアクセスの局所性に注意しながらのTaskの配分が必要である。 | |
530 キャッシュ、Task配分によるメモリアクセス、 | |
531 Taskスケジューリングのパイプライン化による必要なデータの先読み | |
532 など共通している項目はメモリの扱いに関係するものである。このさまざまな | |
533 データ構造を統一し管理しやすくするために、Taskも含め、すべてのデータの扱いはMemorySegment | |
534 で統一したほうが良いと考える。 | |
535 これらの一度に扱うデータのサイズ、Taskの粒度の大きさなど、最適な大きさはわかっていない。 | |
536 なるべく非同期にTaksを設定し、パイプライン化を行うにあたって、それらの項目も考慮していく。 | |
537 | 143 |
538 | 144 |
539 \begin{thebibliography}{10} | 145 \begin{thebibliography}{10} |
540 | 146 |
541 \bibitem{gongo} | 147 \bibitem{gongo} |