% Sample file for the use of compsoft style file.
%
\documentclass[T]{compsoft}

% Preamble
%
% 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
% 巻数，号数，開始ページ，終了ページを指定する．
%\volNoPp{16}{5}{78}{83}

% ワークショップによる推薦論文の場合，ワークショップ名を指定する．
% \suisen{ワークショップ名}

% 特集の場合，特集のタイトルを与える．
% \tokushu{特集のタイトル}

% 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
% 大会の回数は計算される．
\taikai{2011}

% ここに，使用するパッケージを列挙する．
\usepackage[dvips]{graphics}

% ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
% 再定義は原則として避けること．

\begin{document}

% 論文のタイトル
\title{Cerium TaskManager における DataSegment API の設計}

% 著者
% 和文論文の場合，姓と名の間には半角スペースを入れ，
% 複数の著者の間は全角スペースで区切る
%
\author{金城 裕 \and 河野 真治
%
% ここにタイトル英訳 (英文の場合は和訳) を書く．
%
\ejtitle{Improvement of Game Framework Cerium TaskManager}
%
% ここに著者英文表記 (英文の場合は和文表記) および
% 所属 (和文および英文) を書く．
% 複数著者の所属はまとめてよい．
%
\shozoku{Yutaka Kinjyo, Shinij KONO}{琉球大学大学院理工学研究科情報工学専攻並列信頼研}%
{Dept.Concurrency Reliance Laboratory, Information Engineering Course, Faculty of Engineering Graduate School of Engineering and Science, University of the Ryukyus}
%
% 出典情報は \shutten とすれば出力される．
%\shutten
%
% 受付年月日，記事カテゴリなどは自動的に生成される．
%\uketsuke{1999}{8}{3}
%
% その他，脚注に入れるものがあれば，\note に記述する．
%\note{脚注に入れる内容}
}

%
% 和文アブストラクト
\Jabstract{%
本研究では並列プログラミング用フレームワーク Cerium TaskManager を開発している.
Cerium ではユーザが処理を Task として定義し,必要なパラメータを設定すると,自動で各コアへと割り振られ並列実行される.
例題としてゲームを実装したところ, Task 内での動的なデータ取得や, Task 間の依存関係の設定などデータ操作の抽象化が必要なことがわかった.
そこで DataSegment というデータ構造を用意し,データ操作を抽象化するAPIを設計する.
}

%
% 英文アブストラクト（大会論文には必要なし)
% \Eabstract{}
%
\maketitle

\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{Cell Broadband Engine}

\begin{figure}[tb]
\begin{center}
\scalebox{0.4}{\includegraphics{./images/cell-main.eps}}
\caption{Cell Broadband Engine Architecture}
\label{fig:cell_arch}
\end{center}
\end{figure}

Cell Broadband Engine %\cite{cell}
 は、ソニー・コンピュータエンタテインメント、
ソニー、IBM , 東芝によって開発されたマルチコア CPU である。
Cell は、１基の制御系プロセッサコア PPE ( PowerPC Processor Element ) と
８基の演算系プロセッサコア SPE ( Synergistic Processor Element ) で構成される。
各プロセッサコアは、EIB (Element Interconnect Bus)
と呼ばれる高速なバスで接続されている。また、EIB はメインメモリや
外部入出力デバイスとも接続されていて、
各プロセッサコアは EIB を経由してデータアクセスをおこなう。
PPE はメインメモリにアクセスすることができるが、SPE は、246KBのLSにのみ直接アクセスできる。
DMAを用いると、SPE はメインメモリにアクセスできる。
本研究で用いた PS3Linux (Yellow Dog Linux 6.2) では、6 個の SPE を
使うことが出来る ( \ref{fig:cell_arch} )
この PPE と SPE の2種類の CPU を、プログラマ自身が用途に
合わせて適切に使い分けるように考慮する必要がある。

\subsection{Mailbox} \label{sec:mail-box}
Cellの機能にMailboxがある。
Mailbox は PPEとSPEとの間を双方向で、32bitのデータの受け渡しが可能であり、FIFOキュー構造になっている。
MailboxのひとつにSPEからPPEへデータを渡すためのキュー、SPU Outbound Mailbox があり、最大1個までのデータを蓄積できる。
もし、Outbound Mailbox がすでに1個のデータを保持している場合には、
SPEプログラムはPPEプログラム側でキューからデータを読み出すまでデータの書き込みを待ち続ける。

\subsection{DMA転送} \label{sec:dma}
SPE は LS 以外のメモリに
直接アクセスすることができず、PPE が利用するメインメモリ上のデータに
アクセスするには DMA (Direct Memory Access) を用いる。
DMA 転送とは、CPU を介さずに周辺装置とメモリとの間でデータ転送ことで、
Cell の場合はメインメモリと LS 間でデータの転送を行う。
DMA 転送するデータとアドレスにはいくつか制限がある。
転送データが 16 バイト以上の場合、データサイズは 16 バイトの倍数で、
転送元と転送先のアドレスが 16 バイト境界に揃えられている必要がある。
転送データが 16 バイト未満の場合、データサイズは 1,2,4,8 バイトで、
転送サイズに応じた自然なアライメントである (転送サイズのバイト境界に
揃えられている) ことが条件となる。

\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}

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 処理の時間短縮になったと考えられる。

\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 の
稼働率。


\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のブロックに分割し、必要な時に沿って、ブロックを転送する方法を取った。

\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{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に割り振るように改良した。

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}

並列プログラムの特徴として、デバッグが難しいことも挙げられる。
実行が非決定的 (同じ状態で実行しても結果が異なる) な場合があり、
バグの状態を再現することが難しい。
また、個々の 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})

\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{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を設定し、パイプライン化を行うにあたって、それらの項目も考慮していく。


\begin{thebibliography}{10}

\bibitem{gongo}
{多賀野海人}.
\newblock {Cell Task Manager Cerium における Task を用いたパイプラインの改良}.
\newblock {琉球大学理工学研究科情報工学専攻 平成22年度学位論文}, {Feb} 2011.

\bibitem{gongo}
{宮國渡}.
\newblock {Cell用の Fine-Grain Task Manager の実装}.
\newblock {琉球大学理工学研究科情報工学専攻 平成20年度学位論文}, {Feb} 2009.

\bibitem{amdahl}
{Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, and Doug
  Lea}.
\newblock {\em {Java Concurrency in Prac-tice}}.
\newblock {Addison-Wesley Professional}, 2005.

\bibitem{cell}
{Sony Corporation}.
\newblock {Cell BroadbandEngine \texttrademark アーキテクチャ}, 2006.

\bibitem{libspe2}
{International Business Machines Corporation, Sony Computer Entertainment
  Incorporated, Toshiba Corporation}.
\newblock {\em {SPE Runtime Management Library Version 2.3}}, 2008.

\bibitem{cell_cpp}
{International Business Machines Corporation, Sony Computer Entertainment
  Incorporated, Toshiba Corporation}.
\newblock {\em {C/C++ Language Extensions for Cell Broadband Engine                                                         
  Architecture Version 2.6}}, 2008.

\bibitem{spurs}
{Keisuke Inoue}.
\newblock {SPU Centric Execution Model}, 2006.

\bibitem{chiaki}
{Chiaki SUGIYAMA}.
\newblock {SceneGraph と StatePattern
  を用いたゲームフレームワークの設計と実装}.
\newblock {琉球大学工学部情報工学科 平成19年度卒業論文}, 2008.

\bibitem{blender}
{blender.org}.
\newblock {http://blender.org/}.

\bibitem{akamine}
{赤嶺一樹, 河野真治}.
\newblock {Meta Engine を用いた Federated Linda の実験}.
\newblock {日本ソフトウェア科学会第 27 会大会(2010 年度)}, {Sep} 2010.

\bibitem{akira}
{Akira KAMIZATO}.
\newblock {Cell を用いたゲームフレームワークの提案}.
\newblock {琉球大学理工学研究科情報工学専攻 平成19年度学位論文}, 2008.

\bibitem{cell_abi}
{International Business Machines Corporation, Sony Computer Entertainment
  Incorporated, Toshiba Corporation}.
\newblock {\em {Cell Broadband Engine Linux Reference Implementation                                                        
  Application Binary Interface Specification}},

\bibitem{webpage1}                                                                                        
{SourceForge.JP: Cerium Rendering Engine}.
\newblock {https//sourceforge.jp/projects/cerium/}.

bibitem{osmesa}
{The Mesa 3D Graphics Library}.
\newblock {http://www.mesa3d.org/}.

\bibitem{fedora}
{Fedora Project}.
\newblock {http://fedoraproject.org/}.

\bibitem{ydl}
{Yellow Dog Linux for PowerPC Computers}.
\newblock {http://us.fixstars.com/products/ydl/}.

\bibitem{cerium}
{SourceForge.JP: Cerium Rendering Engine}.
\newblock {https//sourceforge.jp/projects/cerium/}.

\bibitem{cell_sdk}
{International Business Machines Corporation}.
\newblock {\em {Software Development Kit for Multicore Acceleration Version                                                 
  3.1}}, 2008.

\bibitem{gongo2}
{Wataru MIYAGUNI}.
\newblock {Cell 用の Fine-grain Task Manager の実装}.
\newblock {情報処理学会
  システムソフトウェアとオペレーティング・システム研究会}, April 2008.

\bibitem{sdl}
{Simple DirectMedia Layer}.
\newblock {http://www.libsdl.org/}.

\bibitem{opencl}
{Aaftab Munshi, Khronos OpenCL Working Group}.
\newblock {\em {The OpenCL Specification Version 1.0}}, 2007.

\bibitem{gallium}
{Gallium3D}.
\newblock {http://www.tungstengraphics.com/wiki/index.php/Gallium3D}.


\end{thebibliography}

\end{document}