\documentclass[twocolumn, a4j, twoside]{jarticle}
\usepackage{master_proc}
%\usepackage[dvips]{graphicx}
\usepackage[dvipdfm]{graphicx}

\input{dummy.tex}

% dvipdfm を使って PDF ファイルに日本語の栞をつける
% \usepackage[dvipdfm]{color}
% \usepackage[dvipdfm,bookmarks=true,bookmarksnumbered=true,%
% bookmarkstype=toc]{hyperref}

\newcommand\figref[1]{図 \ref{fig:#1}}
\newcommand\tabref[1]{表 \ref{tab:#1}}

%和文タイトル
\jtitle{Cell 用の Fine-Grain Task Manager の実装}
%英文タイトル
\etitle{Implementation of Fine-grain Task Manager for Cell}
%著者名
\author{宮國 渡}
%学籍番号
\studentid{078519K}
%指導教官
\teacher{河野 真治}

\begin{document}

\maketitle

\section{はじめに}

現在、学生実験にて PlayStation 3 (PS3) で動作するゲーム開発を行っている。 
しかし、PS3 のアーキテクチャである Cell は、
Many Core を用いた並列プログラミングが求められており、
並列プログラミングの経験が浅い学生にとって、
Cell のようなアーキテクチャを理解した上でゲームを実装することは困難である。
また、現在 PS3 ゲーム開発用フレームワークが存在しないことで、
学生が一からプログラミングしていく必要がある。
%この様な問題から、例年、学生実験の期間の大半を
%アーキテクチャの勉強に費やさねばならず、残りの期間内でゲーム開発を行っている。
%そのため、制作されたゲームの完成度が一定以上にならない。

本研究では、Many Core Architetcure を用いた並列プログラムの開発をサポートする
フレームワークとして Fine-Grain Task Manager を実装し、それを組み込んだ、
PS3 ゲーム開発用フレームワークである Cerium を提案する。

%Cerium を用いた開発行程は以下の様になる。
%
%\begin{itemize}
%\item 逐次型プログラム
%\item データやコードを分割したプログラム
%\item 並列に動かすプログラム
%\end{itemize}
%
%これらのステップ毎にプログラムの仕様やアルゴリズムを確かめ、テストやデバッグを行い信頼性を確保しながら開発を進める。

Cerium は学生が Cell を理解しながら、一定期間内でゲーム開発が行える、
シンプルなマルチタスクフレームワークを目指している。

\vspace{-4mm}

\section{Cell Broadband Engine}
Cell \cite{cell} は、1個の Power PC Processor Element (PPE) と、
8個の Synergistic Processor Element (SPE) からなる非対称なマルチコアプロセッサ
である、高速なリングバスでである Element Interface Bus (EIB) で構成されている
(\figref{cell_arch})。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.3]{./images/cell_arch.pdf}
    \caption{Cell Broadband Engine Architecture}
    \label{fig:cell_arch}
  \end{center}
\end{figure}

\vspace{-8mm}

本研究で用いた PS3Linux (Fedora 10、Yellow Dog Linux 6.0) からは
6個の SPE が使用できる。SPE には 256KB の Local Store (LS) と呼ばれる
メモリ領域を持っている。また、SPE からメインメモリへは直接アクセスできず、
SPE が持つ Memory Flow Controller (MFC) へ、DMA 命令を発行することで行われる
。
%(\figref{cell_spe})。

%\begin{figure}[htb]
%  \begin{center}
%    \includegraphics[scale=0.25]{./images/cell_spe.pdf}
%    \caption{Synergistic Processor Element (SPE)}
%    \label{fig:cell_spe}
%  \end{center}
%\end{figure}

Cell が持つ基本的な機能として、Mailbox \cite{libspe2} がある。
Mailbox は SPE の MFC 内にある 32ビットメッセージの FIFO キューを保持しており、
PPE と SPE 間での同期に用いることができる。

\vspace{-4mm}
\section{Many Core プログラミングの特徴}
並列実行には Amdahl 則 \cite{amdahl}があり、
使用するCPUを増やしても、元のプログラムの 
並列化率が低ければ、その性能を生かすことは出来ないとされている
(\figref{amdahl})。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.35]{./images/amdahl.pdf}
    \caption{Amdahl則 (6CPUを用いた時の並列化率と性能向上率)}
    \label{fig:amdahl}
  \end{center}
\end{figure}

並列度を維持するためには、元のプログラム及びデータの分割による
データ並列、パイプライン処理を行うことが必要である。

並列プログラミングでは、以下の段階において、それぞれ実装とテストを行う。

\vspace{-2mm}

{\small
\begin{verbatim}
step1. C によるシーケンシャルな実装
step2. 並列実行を考慮したデータ構造を持つ実装
step3. コードを分割し、それらをシーケンシャルに実行する実装
step4. 分割したコードを並列実行する実装
step5. アーキテクチャに特化した実装
\end{verbatim}
}

\vspace{-2mm}

step3 まではシーケンシャルに実行されるためアーキテクチャに依存しない実装と
なっており、二分法によるデバッグが可能となっている。
step4、5 で異常が確認できた場合、一度 step3 に戻りアルゴリズムやデータ構造、
プログラム分割が正しいかを確認する。

\vspace{-4mm}
\section{TaskManager}

Task Manager は、Task と呼ばれる、分割された各プログラムの管理を行う。
Task の単位はサブルーチンとし、Task 同士の依存関係を考慮し、
実行可能状態になった Task を各 SPE に割り振る。
Task は通常 PPE スレッドで生成され、SPE スレッドに送られる。
SPE スレッドでは、受け取った Task をパイプラインに沿ってステージを遷移しながら
複数の Task を同時に実行していく。

Task Manager は、Task が実行される CPU を明示的に選択できる機能を
持っているため、違う環境へプログラムを移行する場合に大幅なコードの変更が
必要なく、環境依存のプログラム変換はタスク内部だけになる。

PPE スレッドと SPE スレッド間の同期は、Cell の機能である Mailbox を用いる。
メッセージ交換なので、スレッド間の待ち合わせは起こらない。

%\subsection{例題}
%Task Manager を用いて、実際に学生に並列プログラムを実装してもらった。
%プログラムは Bitonic Sort で、ソートデータを複数のブロックに分割し、
%隣り合ったブロック同士でソートするのを繰り返すソーティングである
%(\figref{sort})。
%
%\vspace{-2mm}
%
%\begin{figure}[htb]
%  \begin{center}
%    \includegraphics[scale=0.3]{./images/tm_sort.pdf}
%    \vspace{-4mm}
%    \caption{Bitonic Sort}
%    \label{fig:sort}
%  \end{center}
%\end{figure}
%
%\figref{sort_calc} が実行結果となる。
%SPE 6 個で、SPE 1 個の時より 5.1 の性能向上がみられる。
%これより、TaskManager 自体のオーバーヘッドは問題ないと考えられる。
%
%\vspace{-2mm}
%
%\begin{figure}[htb]
%  \begin{center}
%    \includegraphics[scale=0.3]{./images/tm_sort_calc1m.pdf}
%    \vspace{-4mm}
%    \caption{Bitonic Sort 実行結果}
%    \label{fig:sort_calc}
%    \vspace{-8mm}
%  \end{center}
%\end{figure}
%
\vspace{-2mm}

\section{Cerium}

Cerium \cite{cerium} は PS3 ゲーム開発用のフレームワークである。

Cerium は、オブジェクトのデータやその振る舞い、
またはゲームのルールなどゲームを構成する場面 (シーン) を木構造で持つ
Scene Graph、OSMesa に代表される Rendering Engine、
そしてそれらの実行単位を Task とし、
動的に全てのコアが動作する様な割り振りを行うカーネル
TaskManager で構成されている (\figref{cerium})。 

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.3]{./images/cerium.pdf}
    \vspace{-4mm}
    \caption{Cerium}
    \label{fig:cerium}
  \end{center}
\end{figure}

\vspace{-8mm}

\subsection{SceneGraph}
ゲームオブジェクトは オープンソースの3Dモデリングツールである
Blender \cite{blender} で作成し、Cerium 独自の XML 形式で出力する
\cite{chiaki}。
Cerium はXML が持つ情報 (頂点座標、テクスチャ情報など) から SceneGraph
を生成する。SceneGraph はポリゴン情報の他に、オブジェクトの操作に関する move や
他の SceneGraph との衝突処理を行う collision を持つ。

\subsection{Rendering Engine}
Cerium Rendering Engine では、SceneGraph の操作後、
実際に描画するポリゴン を SceneGraph から取得する {\bf SG2PP}、
ポリゴンの中から Span (ポリゴン内にある x軸に水平な線分) を抽出する
{\bf PP2SP}、Span を使って 1 ラインずつ描画していく {\bf DrawSpan} の
3つのタスクで構成されている (\figref{rendering})。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.25]{./images/rendering.pdf}
    \vspace{-4mm}
    \caption{Cerium Rendering Engine}
    \label{fig:rendering}
  \end{center}
\end{figure}

\vspace{-8mm}
\subsection{Cerium を用いたゲーム開発}

\figref{dandy} は、学生が Cerium を用いて開発したPS3 で動作する
3Dシューティングゲームである。このゲームの実行結果を \tabref{game} に示す。
SPE 6 個で、SPE 1 個のものより 3.6 倍の性能向上となった。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.08]{./images/cerium_game_1.pdf}
    \caption{SuperDandy3D(仮)}
    \label{fig:dandy}
    \vspace{-4mm}
  \end{center}
\end{figure}

\begin{table}[htb]
  \begin{center}
    \caption{SuperDandy3D(仮) の各動作環境での実行速度} \label{tab:game}
{\small
    \hbox to\hsize{\hfil
      \begin{tabular}{l|r} \hline \hline
        MacOSX 10.5 & 5.7 FPS \\ \hline
        Linux (Fedora 10)  & 7.8 FPS \\ \hline
        PS3 SPE 1個 & 8.1 FPS \\ \hline
        PS3 SPE 6個 & {\bf 29.3 FPS} \\ \hline
      \end{tabular}\hfil}
}
  \end{center}
\end{table}

\section{比較}
\subsection{Gallium}
先行研究 \cite{akira} では、レンダリングエンジンに OSMesa \cite{osmesa}を用い、
その後 Galiium \cite{gallium} というOSMesa の Cell driver が登場した。
しかし、PS3 上のゲーム開発において、
レンダリングのみを SPE 上で実行させるのは Amdahl 則の問題もあり好ましくない。
したがって、レンダリングだけでなく、ゲームオブジェクトも SPE で処理させる
方針の Cerium では独自のレンダリングエンジンを用いている。
\subsection{OpenCL}
並列コンピューティングフレームワークである OpenCL \cite{opencl} は、
あらゆる Many Core Architecture に対応できるような汎用的な実装がされており、
開発環境に合わせた記述が必要となる。また、現在 OpenCL を用いた Cell 用の
実装は無い。
対して、Task Manager は Cell に重きを置いた記述で、ある程度決まった記述で
開発できる。また、大幅な変更無く Mac OSX や Linux など複数の環境で
動作させることが可能となっている。

\section{まとめと今後の課題}

本研究では、Many Core Architetcure を用いた並列プログラムの開発を
サポートするフレームワークとして Fine-Grain Task Manager を実装し、
それを組み込んだ、PS3 ゲーム開発用フレームワークである Cerium を提案した。

Cerium を用いれば、学生が手を付けやすい環境(Mac OS X、Linux)からの
開発を始めることができ、コードの大幅な変更無く PS3 での動作を確認できる。
その過程で、学生が Cell アーキテクチャの理解も行えるため、
教育効果も期待できる。

今後の課題には、レンダリング機能の追加、SceneGraph の操作の SPE 上での処理、
SPE に特化した演算の積極的な使用が上げられる。

\bibliographystyle{junsrt}
\bibliography{handout}

\end{document}