Mercurial > hg > Papers > 2010 > jsst-yutaka

comparison resume/jssst.tex @ 10:e5f74d4de3ad

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add file
author Yutaka_Kinjyo
date Wed, 08 Sep 2010 01:05:10 +0900
parents
children
comparison
equal deleted inserted replaced
9:b781dc4132f8 10:e5f74d4de3ad
1 % Sample file for the use of compsoft style file.
2 %
3 \documentclass[T]{compsoft}
4
5 % Preamble
6 %
7 % 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
8 % 巻数，号数，開始ページ，終了ページを指定する．
9 %\volNoPp{16}{5}{78}{83}
10
11 % ワークショップによる推薦論文の場合，ワークショップ名を指定する．
12 % \suisen{ワークショップ名}
13
14 % 特集の場合，特集のタイトルを与える．
15 % \tokushu{特集のタイトル}
16
17 % 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
18 % 大会の回数は計算される．
19 \taikai{2010}
20
21 % ここに，使用するパッケージを列挙する．
22 \usepackage[dvipdfm]{graphics}
23
24 % ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
25 % 再定義は原則として避けること．
26
27 \begin{document}
28
29 % 論文のタイトル
30 \title{Fine Grain Task Manager Cerium のチューニング}
31
32 % 著者
33 % 和文論文の場合，姓と名の間には半角スペースを入れ，
34 % 複数の著者の間は全角スペースで区切る
35 %
36 \author{金城 裕 \and 河野 真治
37 %
38 % ここにタイトル英訳 (英文の場合は和訳) を書く．
39 %
40 \ejtitle{Tuning of Fine Grain Task Manager Cerium}
41 %
42 % ここに著者英文表記 (英文の場合は和文表記) および
43 % 所属 (和文および英文) を書く．
44 % 複数著者の所属はまとめてよい．
45 %
46 \shozoku{Yutaka Kinjyo, Shinij KONO}{琉球大学大学院理工学研究科情報工学専攻並列信頼研}%
47 {Dept.Concurrency Reliance Laboratory, Information Engineering Course, Faculty of Engineering Graduate School of Engineering and Science, University of the Ryukyus}
48 %
49 % 出典情報は \shutten とすれば出力される．
50 %\shutten
51 %
52 % 受付年月日，記事カテゴリなどは自動的に生成される．
53 %\uketsuke{1999}{8}{3}
54 %
55 % その他，脚注に入れるものがあれば，\note に記述する．
56 %\note{脚注に入れる内容}
57 }
58
59 %
60 % 和文アブストラクト
61 \Jabstract{%
62 現在Cell/PS3またはMac OS X上で動作するFine Grain Task Manager であるCeirumを開発中である。
63 Cerium Task Managerは、Cell/PS3またはMac OS X上で動作するOpen CL 的なFine Grain Task Manager である。
64 ソフトウェアレンダリングエンジンとWord countを例題として、Task Manager の実装時の問題を洗い出している。
65 メインメモリ上のTaskを各Coreが受け取る際や、その終了を通知する際に待ち時間が生じる。
66 その待ち時間を削減するために、Task arrayを提案し実装した。その効果について報告する。
67 }
68 %
69 % 英文アブストラクト（大会論文には必要なし)
70 % \Eabstract{}
71 %
72 \maketitle
73
74 \section{概要}
75
76 CPUの処理速度の向上ためのクロック周波数の増加は、
77 発熱や消費電力の増大により難しくなっている。そのため、クロック周波数を上げる代わりに、CPUコア数を増やす傾向になった。
78 マルチコアなCPUの性能を発揮するには、処理をできるだけ並列化しなければならない。それはアムダールの法則により、並列化できない部分が並列化による性能向上を制限することから言える。つまり処理速度の性能向上は、ハードウェアだけでなく、ソフトウェアを並列処理に適したように実装することにもかかっている。そのためにはプログラミングの支援をするフレームワークが必要になってくる。そこでFine Grain Task Manager であるCeirumを開発中である。現在Ceriumは、マルチコアCPUの例題としてCellに対応している。また、支援するプログラミングの対象の１つとしてゲームを選択し、PS3,Mac OS X上でのゲームフレームワークとしても動作する。
79 そのCerium のチューニングをするうちに、各Coreにおいて、割り当てられたTaskが終わり、次のTaskを待つ時間が処理速度を遅くしていることがわかった。そこで待ち時間を削減するために、各Task生成方法、スケジュールリング方法の変更、複数のTaskをまとめて扱うTaskArrayを提案し実装した。その効果について報告する。
80
81
82 \section{Cell Broadband Engine}
83
84 Cell Broadband Engine は、ソニー・コンピュータエンタテインメント、ソニー、IBM, 東芝によって開発されたマルチコアCPUである。
85 Cellは、1基の制御系プロセッサコア (PPE:PowerPc Processor ELement) と8基の演算系プロセッサコア (SPE:Synergistic Processor Element) で構成される。各プロセッサコアは、EIB (Element Interconnect Bus) と呼ばれる高速なバスで接続されている。また、EIBはメインメモリや外部入出力デバイスとも接続されていて、各プロセッサコアはEIBを経由してデータアクセスをおこなう。
86
87 このPPEとSPEの2種類のCPUを、プログラマ自身が用途に合わせて適切に使い分けるように考慮する必要がある。
88
89 \begin{figure}[htbp]
90 \begin{center}
91 \scalebox{0.3}{\includegraphics{pic/cell_arch.pdf}}　　　　
92 \caption{Cell Broadband Engine Architecture} \label{cell}
93 \end{center}
94 \end{figure}
95
96 \subsection{PPE}
97 PPEはCell BroadbandEngineのメインプロセッサで、複数のSPEをコアプロセッ
98 サとして使用することができる汎用プロセッサである。メインメモリや外部デバイスへ
99 の入出力、SPEを制御する役割を担っている。PPU(PowerPCProcessorUnit)は、PPE
100 の演算処理を行うユニットで、PowerPCアーキテクチャをベースとした命令セットを持
101 つ。
102
103 \subsection{SPE}
104 SPEには256KBのLocal Store(LS)と呼ばれる、SPEから唯一、直接参照できるメ
105 モリ領域があり、バスに負担をかける事無く並列に計算を進めることが出来る。SPEか
106 らメインメモリへは、直接アクセスすることは出来ず、SPEを構成する一つであるMFC
107 (MemoryFlowController)へ、チャネルを介してDMA(DirectMemoryAccess)命令を
108 送ることで行われる
109
110 \subsection{DMA}
111 SPEはLS以外のメモリに直接アクセスすることができず、PPE
112 が利用するメインメモリ上のデータにアクセスするにはDMAを用いる。DMA(Direct
113 MemoryAccess)転送とは、CPUを介さずに周辺装置とメモリとの間でデータ転送こと
114 で、Cell の場合はメインメモリとLS間でデータの転送を行う。手順としては以下の様に
115 なる。
116
117 {\small
118 \begin{enumerate}
119 \item SPEプログラムがMFC(MemoryFlowController)に対してDMA転送命令を発行
120 \item MFCがDMAControllerを介してDMA転送を開始。この間、SPEプログラムは
121 停止しない。
122 \item DMA転送の終了を待つ場合、SPEプログラム内で転送の完了を待つ
123 \end{enumerate}
124 }
125
126 \subsection{Mailbox} \label{sec:cell_mailbox}
127
128 Mailbox とは PPE と SPE 間の 32 ビット
129 メッセージの交換に用いられる。Mailbox では 3 つの振る舞いが
130 出来る様に設計されている。
131
132 \begin{enumerate}
133 \item SPU Inbound Mailbox \\
134 PPE から SPE へデータを渡すためのキュー。キューのエントリ数は
135 実装依存による が、研究環境では最大4個までのデータを蓄積できる。
136 このキューが空の場合は、SPE は、データがメールボックスに書き込まれるまでは、
137 命令でストールする。読み出すデータの順番は書き込んだ順番に保証されている。
138 \item SPU Outbound Mailbox \\
139 SPE から PPE へのデータを渡すためのキュー。研究環境では最大1個までしか
140 データが蓄積できない。
141 \item SPU Outbound interrupt Mailbox \\
142 SPU Outbound Mailbox とほとんど同じだが、このキューでは SPE から
143 キューにデータが書き込まれると、PPE に対して割り込みイベントが
144 発生し、データの読み出しタイミングを通知する事が出来る。
145 \end{enumerate}
146
147
148 \section{Ceriumとは}
149
150 CeriumはTaskManager、レンダリングエンジンとSceneGrpahの3つの要素から構成されており、
151 PS3、Mac OS X、Linux上でゲームフレームワークとして動作する。ゲーム中のオブジャクトの振る舞いやルールはSceneGraphで管理し、それらの動きやレンダリングの処理を動的にSPEに割り振るカーネルとして、TaskMnagerが用いられる。PS3のGraphics Engineの仕様は公開されておらず、ソフトウェアレンダリングエンジンを実装する必要があった。
152
153 %% \begin{itemize}
154 %% \item SceneGraph
155 %% \item Rendering Engine
156 %% \item Task Manager
157 %% \end{itemize}
158
159 \subsection{TaskManager}
160 TaskManagerは、Taskと呼ばれる、分割された各プログラムを管理する。
161 Taskの単位はサブルーチンまたは関数とし、Task同士の依存関係を考慮し、実行可能状態になったTaskを各SPEに割り振る。
162 Taskは通常PPEで生成され、SPEに送られる。SPEでは、受け取ったTaskをパイプラインに沿ってステージを遷移しながら複数のTaskを同時に実行していく。
163
164 \section{CeriumにおけるTask}
165
166 TaskはTaskManagerを使って生成する。
167 Taskを生成する際に以下のような要素が設定可能である。
168
169 {\small
170 \begin{enumerate}
171 \item input data
172 \item output data
173 \item paramater
174 \item cpu type
175 \item dependency
176 \end{enumerate}
177 }
178
179 input,output data, paramaterは関数でいうところの引数にあたいする。cpu typeはTaskがPPE,または6基あるSPEのどれかで実行されるかを示すもの。
180 dependencyは他のTaskとの依存関係を示す。依存関係の情報はPPE側が持っている。SPEからPPEへ実行し終わったTaskが通知され、PPE側ではその通知に沿って
181 依存関係を処理していく。例えば、Task A が Task B の実行完了をまって、実行可能状態になるとする。はじめTask B はどのTaskも待つ必要がないので、
182 SPEに送られ、実行される。Task Bの実行が完了すると、SPEからTask B の完了通知がMailでPPE側へ通知される。Task Bが実行完了の通知がきたので、Task Aの待ちTask
183 から、Task BがはずされTask AはSPEに送られる。以上のようにSPEからのMailを使った通知によって、Taskの依存関係を解決している。
184 待ちTaskを持っているTaskはwait queueと呼ばれるキューに、待ちTaskのないTaskはactive queueと呼ばれるキューに入れられる。active queueにあるTaskをSPEに送る。()
185
186 \begin{figure}[htbp]
187 \begin{center}
188 \scalebox{0.4}{\includegraphics{pic/dependency.pdf}}　　　　
189 \caption{依存関係の解決} \label{fig:dependency}
190 \end{center}
191 \end{figure}
192
193 \subsection{Taskのスケジューリング}
194 SPEは、Taskを一つずつ受け取るのではなく、ある程度まとめて受け取る。それをTaskListと呼んでいる。TaskListに沿ってTaskを実行していき、Task毎に実行完了のMailを
195 送る。TaskListのTaskを全て実行すると、次のTaskListを要求するMailをPPE側に送る。
196
197 \section{TaskArray}
198 WordCountの場合,　対象となるファイルによって大量のTaskが生成される。レンダリングエンジンの場合、PPE側で実行すべきTaskがある。その時に、PPEが自分のTaskを完了し、Taskの依存関係を解決するのに時間がかかってしまう。そうなるとSPEからのTaskList要求への反応が送れ、SPEの待ち時間が生じるはずである。それを解決するためにTaskArrayを提案、実装した。TaskArrayは、複数のTaskをまとめて扱うことができる。それによって依存関係を解決すべきTaskの数が減り、解決の手間が省け、SPEからのTaskList要求に応答しやすくなる。また、一度にTaskListに多くのTaskを登録できるため、SPE側からのTaskList要求の回数が減り、待ち時間が生じる可能性が減る。さらにTaskArrayの長さによっては、パイプラインが長くなり、DMAの転送時間を多く隠すことができる。WordCountとレンダリングエンジンのおいて、TaskをTaskArrayにし、効果を検証した。
199
200 \subsection{WordCountのTask}
201
202 まずは例題のWordCountのTaskについて説明する。
203 WordCountのTaskは以下の二つである。
204
205 {\small
206 \begin{enumerate}
207 \item WordCountTask
208 \item PrintTask
209 \end{enumerate}
210 }
211
212 WordCountTaskは、inputで与えられたdataをword countし、output dataに書き出すTaskである。
213 PrintTaskはすべてのWordCountTaskの実行完了を待ち、outputへ書き出された値を集計し出力するTaskである。
214 一度にSPEに渡せるデータ容量はDMAの仕様上16Kbyteまでである。さらに転送する際には16の倍数byteである必要がある。
215
216 \subsection{WordCountのTask設定}
217
218 wcするfileをメモリへマッピングし、WordCountTask
219 のinputに、file dataのアドレスを16kbyteごとに指定していく。
220
221 \begin{figure}[htbp]
222 \begin{center}
223 \scalebox{0.3}{\includegraphics{pic/wc_graf1.png}}
224 \caption{WordCountにおけるTaskの流れ} \label{wordcoutntask1}
225 \end{center}
226 \end{figure}
227
228 PrintTaskはWordCountTaskを待ちTaskと設定し、WordCountがすべて終わらないと、
229 実行されない。
230
231 \subsection{WordCountTaskのTaskArray化}
232 WordCountTaskをTaskArray化した。TaskArray１つに、64個のTaskが入るようにし、WordCount対象は166Mのテキストファイルとした。TaskArrayを適応した場合と、そうで
233 ない場合で比較する。
234 SPEは6個使用した。timeは実行にかかった時間、dma waitは、SPEが起動していた時間においての、dma転送の待ち時間の割合。
235 mail wait はSPEが起動していた時間においての、次のTaskListのmailを待っている時間の割合である。以下に、表にして示す。dma,mailそれぞれのwait割合に関してはspe6個の平均を示しており、この時のTaskの数は約一万個である。
236
237 \vspace{5mm}
238 \begin{table}[htb]
239 \begin{center}
240 \vskip -\lastskip \vskip -20pt
241 \caption{WordCountTaskのTaskArray化による比較}
242 \hbox to\hsize{\hfil
243 \begin{tabular}{c|l|l|l} \hline \hline
244 & Task & TaskArray\\ \hline
245 \hline
246 %Mac OSX & 7.0 & 8.5\\ \hline
247 time & 2.184s & 2.109s \\ \hline
248 %dma wait & 28685142 & 21266467 \\ \hline
249 %mail wait & 9302079 & 12025955 \\ \hline
250 dma wait & 18\% & 12\% \\ \hline
251 mail wait & 5\% & 8\% \\ \hline
252 \end{tabular}\hfil}
253 \label{tb:lightspeed}
254 \end{center}
255 \end{table}
256 \vspace{-5mm}
257
258 表に示した結果より、著しいTaskArrayの効果は見られなかった。この結果はWordCountにおいては誤差の範囲内である。効果が見られなかった原因はおそらくWordCountの場合はPPE側のTaskがないので、依存関係の解決にあまり待ち時間が発生しないからだと考えられる。また、WordCountにおいてはファイルをメモリにマッピングするので、ファイルの容量が大きい場合に大量にメモリを消費してしまう。その結果スワップが起きやすくなり、dma転送の待ち時間が長くなっている可能性がある。この解決として、一度にファイル全てをマッピングするのではなく、何回かに切り分けてマッピンするのがよい。ある程度のWordCountし終わった領域に、次のWordCount領域を入れ替えて使うことでメモリを節約でき、スワップを減らすことができるはずである。その結果メモリアクセスが高速になり、dma転送の待ち時間も削減できる。
259
260 \subsection{レンダリングのTask}
261
262 レンダリングエンジンは主に、CreatePolygon、CreateSpan、DrawSpanという3つのTaskから構成されている。
263 それぞれのTaskの動作とレンダリングの流れを示す。
264
265 {\small
266 \begin{enumerate}
267 \item CreatePolygonTaskによってSceneGraphをもとにモデリングデータから、実際に表示するポリゴンを生成する。
268 \item CreateSpanTaskで生成したポリゴンからSpanの生成する。
269 \item DrawSpanTaskでSpanをRGBにマッピングし描画する。
270 ここでいうSpanとは、ポリゴンに対するある特定のY座標に関するデータを抜き出したものである。
271 \end{enumerate}
272 }
273
274 \begin{figure}[htbp]
275 \begin{center}
276 \scalebox{0.3}{\includegraphics{pic/rendering3.pdf}}
277 \caption{レンダリングエンジンの流れ} \label{rendering}
278 \end{center}
279 \end{figure}
280
281
282 \subsection{レンダリングエンジンのTaskArray化}
283
284 レンダリングエンジンの中で、もっとも数が多く生成されるDrawSpanTaskをTaskArray化した。
285 地球と月を表示する例題を対象に効果を検証した。FPS(Frame Per Second)は、一秒間に表示できる
286 Frame数のことである。
287
288 \begin{figure}[htbp]
289 \begin{center}
290 \scalebox{0.5}{\includegraphics{pic/lightearth.pdf}}
291 \caption{地球と月を表示する例題} \label{rendering}
292 \end{center}
293 \end{figure}
294
295
296 \vspace{5mm}
297 \begin{table}[htb]
298 \begin{center}
299 \vskip -\lastskip \vskip -20pt
300 \caption{レンダリングTaskのTaskArray化による比較}
301 \hbox to\hsize{\hfil
302 \begin{tabular}{c|l|l|l} \hline \hline
303 & Task & TaskArray\\ \hline
304 \hline
305 %Mac OSX & 7.0 & 8.5\\ \hline
306 FPS & 3.94 & 4.32 \\ \hline
307 %dma wait & 28685142 & 21266467 \\ \hline
308 %mail wait & 9302079 & 12025955 \\ \hline
309 dma wait & 0.06\% & 0.07\% \\ \hline
310 mail wait & 55\% & 42\% \\ \hline
311 \end{tabular}\hfil}
312 \label{tb:lightspeed}
313 \end{center}
314 \end{table}
315 \vspace{-5mm}
316
317 結果からDrawSpanTaskをTaskArray化すると、FPSが多くなり、mailのwait時間が減ったことがわかる。レンダリングエンジンでは、PPE側でも
318 処理すべきTaskがあり、常にPPEが忙しい状態になっている。そのためmailを処理する時間が送れSPEのmail待ちが発生していると考えられる。
319 TaskArray化でTaskをまとめることでSPEが１つのTaskListで多くのTaskを実行できるようになったため、TaskListを要求する回数が減って、待ち時間が発生する
320 回数も減少した。またそれはSPEからのmailの数が減ったということなので、PPE側のmail処理の時間短縮になったと考えられる。
321
322
323 \section{まとめ}
324 今回はTaskを複数にまとめるTaskArrayを提案、実装し効果を測った。
325 TaskArrayの効果があるのは、PPE側にも実行すべきTaskがありPPEが忙しい場合ということがわかった。WordCountでは、PPE側のTask
326 がなく、mail待ちがネックではなく、TaskArrayの効果がなかった。大量のファイルをマッピングし、メモリを多く消費するのでメモリアクセス、
327 dma転送に待ち時間があると考えられ、TaskArrayを用いてもうまくdma転送が隠れてないようだ。dma転送をスケジュールリングによって
328 うまく隠す、またはメモリ領域の節約をすることができれば、今回のWordCountのような大量のデータを用いる場合の速度向上が期待できる。
329
330 \subsection{メインメモリアクセス}
331 WordCountを実装している際に極端に処理速度が遅くなる時があった。
332 それは複数のSPEが同時にメインメモリにアクセスする際に、それぞれ離れたメモリにアクセスする時である。Taskにはそれぞれアクセスすべき
333 メインメモリのアドレスを持っており、そのTaskがうまくSPEに割り振られてなかったため、そのようなことがおこった。TaskをSPEに割り振る際には
334 なるべく複数のSPEが近くのメモリをアクセスするようにした方がよい。また一定周期でSPEを同期させ、特定のSPEのTask実行が遅くなりすぎたり、速くなり
335 すぎたりするのを防ぐことでも、メモリアクセス先が離れることを回避できる。
336
337
338
339 %{\bf 謝辞}\
340 %
341 \begin{adjustvboxheight} % needed only when Appendix follows
342 \begin{thebibliography}{99}
343 \bibitem{} 宮國渡 "Implementation of Fine-grain Task Manager for Cell" 平成20年度 学位論文(修士)
344 \bibitem{} fixstars:http://cell.fixstars.com/ps3linux/index.php/メインページ
345 \bibitem{} 高山 征大「CELL REGZA」が搭載する並列化技術「Molatomium」
346 \bibitem{} OpenCL:http://www.khronos.org/opencl/
347 \bibitem{} Mark Deloura "Game Programming Gems"
348
349 %% \bibitem{ST85} Sleator, D. D. and Tarjan, R. E.：Self-Adjusting Binary Search
350 %% Trees, {\it J. ACM}, Vol.~32, No.~3 (1985), pp.~652--686．
351
352 %% \bibitem{S89} Shapiro E.：The Family of Concurrent Logic Programming Languages.
353 %% {\it ACM Computing Surveys}, Vol.~21, No.~3 (1989), pp.~413--510．
354
355 %% \bibitem{T85} Tarjan, R. E.：Amortized Computational Complexity, {\it
356 %% SIAM J.\ Alg.\ Disc.\ Math.}, Vol.~6, No.~2 (1985), pp.~306--318.
357
358 %% \bibitem{W90} 和田久美子：スプレイ木の並列データ探索, Proc.\ KL1
359 %% Programming Workshop '90, Tokyo, ICOT, 1990, pp.~42--49．
360 \end{thebibliography}
361 \end{adjustvboxheight} % needed only when Appendix follows
362
363 \appendix
364 %\section{付録: \LaTeX による論文作成のガイド}
365
366 %ここに，以前の \verb|sample.tex| では，論文作成のガイドがあったが，
367 %その内容は \verb|guide.tex| に移動した．
368
369 \end{document}