--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/resume/handout.tex	Tue Feb 17 12:27:00 2009 +0900
@@ -0,0 +1,300 @@
+\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}