--- a/paper/jssst.tex	Mon Aug 08 19:56:20 2011 +0900
+++ b/paper/jssst.tex	Mon Aug 08 20:21:36 2011 +0900
@@ -73,20 +73,7 @@
 
 \section{はじめに}
 
-%学生実験用にゲームフレームワーク Cerium を開発した。Cerium の TaskManager は
-我々は並列プログラミング用のフレームーク Cerium TaskManager を開発している。Cerium は PS3/Cell, MacOSX, Linux
-上で開発できる。それぞれのプラットフォームで同じプログラムで動作する。その中でも特にCellに特化しているといえる。
-Cerium TaskManager では、関数やサブルーチンを Task として扱う。Task は Task 同士の依存関係
-に従って、実行される。
-Cell 上の場合、各SPEに Task が割り当てられ、並列に実行される。
-Cerium は TaskManager に加え、SceneGraph, RenderingEngine で構成され、この3つでゲームフレームワークとして
-動作する。
-%RenderingEngine は Task に分割され、並列に処理される。
-Task には input データ、output データ、依存関係を設定する。
-%Task ベースでプログラミングする場合、処理をTaskに分割、input, output データの分割、Task同士の依存関係に工夫が必要になってくる。
-ゲームや、WordCount, Sort を例題として実装した。
-TaskManagerと、TaskManager を使うユーザ側の両方の視点から、
-実装の際に直面した問題とその改良方法と効果について報告する。
+\section{Ceriumとは}
 
 \section{Cell Broadband Engine}
 
@@ -134,406 +121,25 @@
 転送サイズに応じた自然なアライメントである (転送サイズのバイト境界に
 揃えられている) ことが条件となる。
 
-\section{Cerium の改良}
-
-Cerium TaskManager では PPE で Task を定義し、PPE から SPE に Task を割り振る。
-SPE は DMA転送（\ref{sec:dma}節）によって、Taskと、Taskで用いるデータを受け取る。
-DMA転送を用いる場合、待ち時間が発生し、その間SPEの処理が止まる。
-そのため、転送をパイプライン化し、DMA転送の待ち
-を隠す必要がある。Cerium では SPE にスケジューラを持ち Task とデータ の 読み込み、実行、書き出し
-をパイプライン化している。(\ref{fig:scheduler}）Task は一つずづ転送されるのではく、ある程度の
-数を集めて、TaskList として転送される。
-
-\begin{figure}[tb]
-\begin{center}
-\scalebox{0.3}{\includegraphics{./images/scheduler.eps}}
-\end{center}
-\caption{スケジューラ}
-\label{fig:scheduler}
-\end{figure}
-
-
-\subsection{MailQueue} 
-Task には依存関係が設定でき、PPE 側で解決する。実行完了した Task の情報を SPE 側から PPE 側に 通知するために CellのMailbox機能を使用した（\ref{sec:mail-box}）。
-SPEスケジューラは Task が処理完了になる毎に、Mailを Outbound Mailbox に書きこむので、PPE側でMailの読み込みが間に合わないと、待ちが入り、SPEの処理が止まってしまう。
-
-
-これを解消するためにMailQueueを導入した。MailQueueは、SPEから書き込みきれないMailを一時的にキューに退避させるものである。
-TaskListを書きだす時に溜まったQueueの中身をすべて書き出す。
-Task完了を知らせる Mail書き出しの待ちは、Task毎から、TaskList毎になる。
-TaskListのサイズは32。
-MailQueueを有効にしたときの実行速度は以下にようになる
-速度比較には、RenderingEngineを使ったボールが跳ねる例題ball\_boundを用いた。
-
-\begin{table}[!htb]
-  \begin{center}
-    \caption{MailQueue の効果(ball\_bound)} \label{tab:mailqueue}
-    \hbox to\hsize{\hfil
-      \begin{tabular}{|c|l|l|c|} \hline
-         & 改良前 & 改良後 & 性能\\ \hline
-         ball\_bound & 29 FPS & 33.3 FPS & 15\%向上 \\ \hline
-      \end{tabular}\hfil}
-  \end{center}
-\end{table}
-
-MailQueue導入によって、27\%の処理性能の向上が見られた。Task毎からTaskList毎にMailの通知回数が減ったので、待ち時間が入る
-タイミングが減った。それによって、SPEの稼働率が向上し、処理性能の向上につながったと考えられる。
-
-\subsection{TaskArray} \label{taskarray}
+\section{Ceriumでの並列プログラミングの問題点}
 
-Task の依存関係を解決するために、SPEから Mail によってPPEへと処理が完了したTaskの情報が通知される。
-その際に、同じ種類のTaskは一つのMailでよい場合がある。
-そこで、我々は Task Array を提案、実装した。
-Task Array は、複数の Task をまとめて扱うことが出来る。Task Array に登録した順番で
-依存関係を設定しているので、PPE で解決する Task の数が減り、 SPE からの TaskList 要求に応答しやすくなる。
-また、一度に多くの Task を TaskList に登録できるため、 SPE 側からの TaskList 要求の回数が減り、待ち時間が
-生じる可能性が減る。
-
-Rendering Engine の中で、最も数が多く生成される DrawSpanTask を Task Array 化した。
-ボールが跳ねる例題(ball\_bound)、地球と月を表示する例題を対象に効果を測った。 FPS(Frame Per Second) は、一秒間に
-表示できる Frame 数のことである。TaskArray は MailQueue と同様に Mail通知に関係している。
-それぞれの有無の場合を計測した。
-
-\begin{table}[!htb]
-  \begin{center}
-    \caption{TaskArrayの効果(ball\_bound)} \label{tab:taskarray}
-    \hbox to\hsize{\hfil
-      \begin{tabular}{|c|l|l|c|} \hline
-         & 改良前 & 改良後 & 性能\\ \hline
-         ball\_bound & 29 FPS & 34 FPS & 17\%向上 \\ \hline
-      \end{tabular}\hfil}
-  \end{center}
-\end{table}
-
-\begin{table}[htb]
-  \begin{center}
-    \caption{Task Array と MailQueue の効果(universe)}
-    \label{tab:taskarray-mailqueue}
-    \begin{tabular}{|c|c|c|c|c|}
-      \hline
-      TaskArray & MailQueue & FPS & dma wait & mail wait\\
-      \hline
-      あり & あり & 20 FPS & 1.78\% & 67\&\\
-      \hline
-      あり & なし & 18.5 FPS & 1.88\% & 69\%\\
-      \hline
-      なし & あり & 18.5 FPS & 1.4\% & 74\%\\
-      \hline
-      なし & なし & 16.4 FPS & 3.3\% & 84\%\\
-      \hline
-    \end{tabular}
-  \end{center}
-\end{table}
-
-結果から DrawSpanTask を Task Array 化すると、FPS が上昇し、mail の wait 時間が減ったことが分かる。
-Rendering Engine では、 PPE 側でも処理をするべき Task があり、常に PPE が稼動している状態になって
-いる。そのため mail を処理する時間が遅れ、SPE のmail 待ちが発生していると考えられる。 Task Array 化
-で Task をまとめることで SPE が一つの TaskList で多くの Task を実行できるようになったため、 TaskList
-を要求する回数が減って、待ち時間が発生する回数も減少した。また、それは SPE からの mail の数が減った
-ということなので、PPE 側の mail 処理の時間短縮になったと考えられる。
+\section{Continuation based C との相性}
 
-\subsection{PipeLine化}
-
-Cerium では RenderinEngine を実装している。RenderinEngine は大きく分けて、
-CreatePolygon, CreateSpan, DrawSpan, の
-3つのTaskから構成されている。（\ref{fig:rendering-flow}）
-
-\begin{figure}[tb]
-\begin{center}
-\scalebox{0.3}{\includegraphics{./images/rendering3.eps}}
-\end{center}
-\caption{レンダリングエンジンの流れ}
-\label{fig:rendering-flow}
-\end{figure}
-
-Span とは、ポリゴンに対するある特定Y座に関するデータを抜き出したものである。
-この3つのTaskはそれぞれバリア同期を行いながら、順に実行される。
-Cerium において、バリア同期を行う場合には二つの待ち時間がある。
-\begin{itemize}
-\item SPEが他のSPEを待つ時間
-\item バリア同期が完了し、PPE側で次のTaskが作られる時間
-\end{itemize}
-
-この二つの時間の間SPEの処理が止まり、処理性能の低下につながる。
-この待ち時間を回避するには、Taskの粒度を下げる、他のSPEの処理完了を待っているSPEに、別のTaskを割り当てる、等の方法がある。
-別のTaskを割り当てるにはTaskの実行をパイプライン化する方法がある。
-
-そこで、特に処理の重いDrawSpanTask と、CreatePolygon,CreateSpan のTask でパイプライン化を行った。(\ref{fig:rend-dep})
-
-\begin{figure}[tb]
-  \begin{center}
-	\scalebox{0.4}{\includegraphics{./images/rend-dep.eps}}
-  \end{center}
-  \caption{RenderingEngineのパイプライン化の様子}
-  \label{fig:rend-dep}
-\end{figure}
-
-速度比較の対象として、SuperDandy と呼ばれる、学生実験で制作されたシューティングゲームを用いた。
-FPS は一秒あたりの Rendering Engine 全体の処理回数 (Frame per Scecond)、busy ration はSPE の
-稼働率。
-
+\section{C++ との相性}
 
-\begin{table}[!htb]
-  \begin{center}
-    \caption{PipeLine化の結果} \label{tab:busy_ratio}
-    \hbox to\hsize{\hfil
-      \begin{tabular}{|c|l|l|c|} \hline
-         & 改良前 & 改良後 & 性能\\ \hline
-         FPS & 29.4 FPS & 49.5 FPS & 68\%向上 \\ \hline
-         busy\_ration & 47.2\% & 78.1\% & 30.9\&向上 \\ \hline
-      \end{tabular}\hfil}
-  \end{center}
-\end{table}
-
-パイプライン化した結果（\ref{tab:busy_ratio}）、SPEの稼働率が向上し、FPSも向上した。
-処理性能を維持するには、SPEはなるべく稼働させ続けなければならない。
-その為には処理をTaskに分割し、並列実行するだけでなく、バリア同期などで、
-SPEの待ち時間が発生することへ対処しないといけない。
-その対処の一つとしてそれにパイプライン化は有効である。
-
-
-\subsection{SPEでのキャッシュ効果}
-
-\subsubsection{テクスチャの管理}
-Cerium ではソフトウェアレンダリングを、Task で定義し、処理している。描画の際には、SPEのLSへ必要なテクスチャの
-情報を読み込む。SPE のメモリ領域は 256KB しかないため、テクスチャのデータを分割し転送する必要がある。
-そこで、Cerium ではテクスチャを8x8のブロックに分割し、必要な時に沿って、ブロックを転送する方法を取った。
+\section{Data Segment を用いた Cerium の再設計}
 
-\subsubsection{テクスチャの縮小}
-遠くにあるオブジェクトは小さく描画される。この場合、使用されるテクスチャは原寸大である
-必要がない。そこで、オリジナルのテクスチャの他に縮小したテクスチャを用意し、描画される
-オブジェクトの大きさによって、使用するテクスチャを変更することにした。
-
-テクスチャは Tile に分割しなければならないため、縦横ともに 8 の倍数を保つようにする。
-これまでは、テクスチャの縦横どちらかのサイズが最小 (8ドット) になったとき、縮小画像生成を終了
-していたが、テクスチャのサイズが縦横で違う場合、長い方に合わせて空のデータを埋め込み 8 の倍数
-の正方形にするように改良した。この改良によってテクスチャの最大縮小率を正確に求めることが出来るよう
-になった。
-
-\subsubsection{ハッシュの管理}
-
-この時に、頻繁にテクスチャを読み込む場合にはその読み込みがボトルネックとなる。そこでキャッシュを実装した。
-キャッシュは MemorySegment と呼ばれるデータ構造単位でハッシュで管理する。MemorySegment はある一定の
-大きさに決め打った連続したメモリ領域のことである。キャッシュ実装の効果を示す。
-速度比較の対象には、使用するテクスチャ表示範囲が狭いball\_bound と、画面すべてにテクスチャを表示するpanelを用いる。
-
-\begin{table}[!htb]
-  \begin{center}
-    \caption{１秒辺りの Rendering Engine 全体の処理回数} 
-    \hbox to\hsize{\hfil
-      \begin{tabular}{|c|l|l|c|} \hline
-         & 改良前 & 改良後 & 性能\\ \hline
-         ball\_boud & 4 FPS & 30 FPS & 7.5倍向上 \\ \hline
-         panel & 0.2 FPS & 2.6 FPS & 13倍向上 \\ \hline
-      \end{tabular}\hfil}
-  \end{center}
-\end{table}
-
-テクスチャような頻繁な転送が起こり得る場合には、キャッシュが非常に有効であることがわかった。
-Cellのような分散メモリでは、データの転送は慎重に管理しできるだけ転送回数を減らすことが性能
-向上につながる。
+\subsection{Data Segment の型}
 
-\subsection{Memory Access}
-
-Cellにおいて、SPEへのデータの割り振り方が性能に関わる場合がある。
-それはデータを得るために、DMA転送が頻繁に起きるときである。
-Cerium を用いて実装したWordCountを例にとってみる。
-WordCountのTaskは二つある。
-
-\begin{enumerate}
-\item WordCountTask
-\item PrintTask
-\end{enumerate}
-
-WordCountTaskは、inputで与えられたdataをword countし、output dataに書き出すTaskである。
-PrintTaskはすべてのWordCountTaskの実行完了を待ち、outputへ書き出された値を集計し出力するTaskである。
-一度にSPEに渡せるデータ容量はDMAの仕様上16Kbyteまでである。さらに転送する際には16の倍数byteである必要がある。
-
-wcするfileをメモリへマッピングし、WordCountTask
-のinputに、file dataのアドレスを16kbyteごとに指定していく（\ref{fig:wc-graf}）。
-
-\begin{figure}[tb]
-  \begin{center}
-	\scalebox{0.3}{\includegraphics{./images/wc_graf1.eps}}
-  \end{center}
-  \caption{WordCountのTaskの流れ}
-  \label{fig:wc-graf}
-\end{figure}
-
-PrintTaskはWordCountTaskを待ちTaskと設定し、WordCountがすべて終わらないと、
-実行されない。
-
-%このWordCountTaskにデータを渡す際には、メインメモリへのアクセスが局所性を保ちながら
-%処理されるようにした方が良い。WC対象のデータを各SPEがバラバラな領域から取得する場合と
-%ある程度まとまった領域から取得するようにした場合とで比較をした。取得のバラつきはTaskArray
-%のTaskの設定である程度操作できる。
-
-
-WordCountにはTaskArrayを用いた。TaskArrayを用いる場合に注意すべき点がある。
-TaskArrayを使わず、Taskを用いる場合、Taskは生成された順番にそって各SPEに割り振られていく。
-ファイルをmmapし、その領域を上から順番にTaskに設定しているので各SPEは同時に近くのメモリ領域
-にアクセスすることになる。TaskArrayを用いた場合に生成された順にTaskArrayに設定するのはまずい。
-TaskArray一つは、一つのSPEのみで実行され、分割されない。
-TaskArrayに連続した領域を指すTaskばかりを格納すると、
-それによって、一つのSPEが連続領域を順番にアクセスして行く形になる。別のSPEは、16kB x TaskArrayのサイズ分離れた
-領域からメモリアクセスを開始するので、
-離れたメモリ領域を各コアが同時にアクセスすることになる。
-なので、先に複数のTaskArrayを用意し、Taskが生成された順番にそって各TaskArrayに割り振るように改良した。
+\subsection{Data Segment のAPI}
 
-TaskArrayのサイズは64, Taskのinputデータの大きさは16KB,
-wc対象のデータの大きさは約135MB。Taskの数は約8000。
-dma wait は処理全体にかかった時間のdma転送待ちの割合。
-改良前は各SPEが同時に離れた領域(各SPE間は 16KB x 64 離れる)にアクセスする。
-改良後は近くのメモリ領域(各SPE間はだいたい16KB 離れる)にアクセスする。
-
-
-\begin{table}[!htb]
-  \begin{center}
-    \caption{メモリアクセスの局所性を保った改良} \label{tab:memory-access}
-    \hbox to\hsize{\hfil
-      \begin{tabular}{|c|l|l|c|} \hline
-         & 改良前 & 改良後 & 性能\\ \hline
-         実行時間 & 30s   & 1.9s & 15倍向上 \\ \hline
-         dma wait & 14\% & 8\% & 1.7倍向上 \\ \hline
-      \end{tabular}\hfil}
-  \end{center}
-\end{table}
-
-
-メモリアクセスの局所性を保った場合に処理性能の向上が見られた（\ref{tab:memory-access}）。ページングや、スワッピングを
-抑えることができたと考えられる。それに伴ってdma wait 時間も減少し、SPEの待ち時間が処理性能
-の向上に繋がっていると考える。
-
-
-\subsection{OpenGLとの比較}
-
-OpenGL (Open Graphics Library) とは、Silicon Graphics 社が開発した、3D グラフィックス
-処理のためのプログラミングインターフェースである。
-上記で紹介した SuperDandy を Task を用いない OpneGL 上で動作するバージョンを用意して、Cerium
-と性能を比較してみた。OpenGL は PPE だけで動作している。Cerium は今までの改良をすべて加えたもの。
-
-\begin{table}[!htb]
-  \begin{center}
-    \caption{シューティングゲーム「dandy」の性能比較(OpenGL, Cerium))} \label{tab:dandy-compare}
-    \hbox to \hsize{\hfil
-      \begin{tabular}{|c|l|l|c|} \hline
-         & OpenGL  & Cerium & 性能差\\ \hline
-        dandy & 17.5 FPS & 49.5 FPS & 2.9 倍\\ \hline
-      \end{tabular}\hfil}
-  \end{center}
-\end{table}
-
-コアを１つ用いている OpenGL 版に比べて、Cerium では 2.9 倍の性能向上が見られた。
-SPEを活用し、改良によって待ち時間の削減ができ、性能の向上ができた。
-
-\section{debug}
+\subsection{Task Dependendcy}
 
-並列プログラムの特徴として、デバッグが難しいことも挙げられる。
-実行が非決定的 (同じ状態で実行しても結果が異なる) な場合があり、
-バグの状態を再現することが難しい。
-また、個々の Core 上のデータを調べる必要があり、
-デバッガが複数の Core を取り扱えることが必須である。
-Cell の場合、動作している複数 の SPE の一つに対して
-gdb で breakpoint を掛ければ、PPE や他の SPE も同時にストップするが、
-それら全ての CPU を手動で管理するのは厳しい。
-また、PPE と SPE ではメモリ空間が違うため、
-SPE から直接 PPE のデータを見ることができない。
-Cerium での開発工程は、
-
-\begin{enumerate}
-\item C によるシーケンシャルな実装
-\item 並列実行を考慮したデータ構造を持つ実装
-\item コードを分割し、シーケンシャルに実行する実装
-\item 分割したコードを並列実行する実装
-\end{enumerate}
-
-となっている。逐次的な実行で正常な動作を確認した後、並列に実行した場合に正常な
-動作をしない場合がある。特にCell特有の問題として
-データ構造が合っていない。つまり、DMA転送される際に、16アライメントに設定されていないか、
-データのサイズが16の倍数になっていない場合に注意しなければならない。またCeriumではPPE用と
-SPE用が別個に存在するので、互いのコードが等価であるかもチェックしなければならない。
-一つのコードに統一しても良いが、別個で対応したい問題がでた時に対応してる。なるべく同一な
-コードにするのがよい。
-本来SPEで動くべきTaskがPPEで動作するケースもあるので、それもチェックするべき。
-
-\section{まとめ}
-
-本研究では ゲームフレーム Cerium TaskManager の改良を行った。
-特にCell上での実行の場合、SPEの活用が処理性能に大きく関わる。
-SPEからPPEへのMail通知には、PPEのMailを確認するタイミングが関わって
-くるので、MailQueue, TaskArray を用いて
-SPE側でなるべく通知にタイミングを減らし、待ち時間を減らした。
-SPEの稼働率を上げることで性能向上につながった。またキャッシュを用い、
-テクスチャなど頻繁に利用するデータをSPEのLSに常駐させることで、データ
-転送の回数を減らし待ち時間を削減した。数種のTaskが混在し、バリア同期
-を行っている場合には、SPEの待ち時間が発生するので、Taskのパイプライン化
-によって解決した。またデータアクセスの局所性を保つことでデータ転送の待ち
-時間を減少させることができる。Cerium は上記の改良を加え、改良前に比べ、
-約7倍の処理速度の向上が見られた。
-
-Coreの待ち時間を減らすことは、Coreの稼働率の向上につながり処理性能が向上する。
-各Coreの待ち時間は並列プログラミングにおいて、特に注意しなければならない。
-それは、Amdahlの法則からも言える。
-
-並列実行には Amdahl の法則(\cite{amdahl})があり、使用する CPU を増やしても、元のプログラムの並列化率
-が低ければ、その性能を活かすことができないとされている。例えば、プログラムの 8 割
-を並列化したとしても、6CPU で 3 倍程度の性能向上しか得られない(\ref{fig:amdahl})
+\subsection{Data Segment Storage Type}
 
-\begin{figure}[htb]
-  \begin{center}
-	\scalebox{0.5}{\includegraphics{./images/amdahl.eps}}
-    \caption{Amdahl の法則}
-    \label{fig:amdahl}
-  \end{center}
-\end{figure}
-
-このことから、恒常的に並列度を維持する必要があることが分かる。
-
-\section{今後の課題}
-
-\subsection{依存関係の設定}
-現在TaskのパイプラインはTaskの依存関係をユーザが明示的に記述している。
-Task の数が増えるとプログラミングの難易度が格段に上がってしまうという
-問題がある。また、パイプライン化できる場所を特定することも難しくなる
-この問題は Task の依存関係をユーザではなく、システム側が記述するようにすること
-で解決できる。 Task の依存関係が、処理するデータの依存関係と直結しているので、
-データの依存関係をシステム側で監視し、その依存関係を元に処理を行うことでシステ
-ム側からの依存関係の記述が実現できる。もしくは、Taskの依存関係は別の言語で記述
-し、TaskManager がその記述に沿って、定義されたTaskの実行する方法も考えられる。
-また、TaskArrayもTaskとデータの依存関係から、自動で作成できると考える。
+\subsection{Data Segment の処理の記述}
 
-\subsection{Code Load}
-SPE は LS 以外のメモリに
-直接アクセスすることができず、自身の LS の容量は 256KB である。
-現在Cerium では、プログラムを実行する前に、SPE で処理する Task のコードは事前に
-SPE に転送している。しかし、Cerium の開発を続けていく上で、ついにコンパイルの最適化
-を行っていない状態のコードを SPE 上に置いておくことができなくなってしまった。
-この問題から、現在 Cerium が SPE 上にデータを転送している様にして、SPE 上に必要のない
-コードの入れ替えを行う必要が出てきた。そこで、我々は SPE と PPE の間でやりとりする
-データのすべてを Segment というデータ構造で行うことを提案する。その先駆けとして、
-現在は描画を行う Task にMemorySegment という形でデータの入れ替えのためのデータ構造
-を用いている。
-
-\subsubsection{Taskの粒度}
-Taskの粒度が大きい場合に、SPE間で、Taskの消化時間にバラつきがでやすい。
-それは特にバリア同期をしている場合に、待ち時間へ直結する。Taskを粒度が
-小さい場合にはPPEとの通信時間がかさむ事になる。粒度が大きい場合には、
-他のTaskを投入することで解決できる。その方法がパイプラインである。
-実は粒度が小さい場合にも次のTaskを予想してdma転送などパイプライン化し
-転送待ち時間を解消する対処法がある。
-しかし、CeriumのようにPPEへのMail通知で
-同期ポイントがある場合にパイプライン化では対処できなかった。
-そこで今回、MailQueue,TaskArrayなど同期するタイミングの回数を
-減らすことで、ある程度の改良を行った。TaskArrayはTaskの粒度が
-大きくなる影響があり、また巨大なデータを分割アクセスする場合には
-メモリアクセスの局所性に注意しながらのTaskの配分が必要である。
-キャッシュ、Task配分によるメモリアクセス、
-Taskスケジューリングのパイプライン化による必要なデータの先読み
-など共通している項目はメモリの扱いに関係するものである。このさまざまな
-データ構造を統一し管理しやすくするために、Taskも含め、すべてのデータの扱いはMemorySegment
-で統一したほうが良いと考える。
-これらの一度に扱うデータのサイズ、Taskの粒度の大きさなど、最適な大きさはわかっていない。
-なるべく非同期にTaksを設定し、パイプライン化を行うにあたって、それらの項目も考慮していく。
+\section{期待される効果}
 
 
 \begin{thebibliography}{10}