Mercurial > hg > Papers > 2008 > gongo-ess

--- a/cerium.tex	Mon Jul 14 20:09:16 2008 +0900
+++ b/cerium.tex	Mon Jul 14 20:37:12 2008 +0900
@@ -28,49 +28,50 @@
 \subsection{Scene Graph}
 本研究では、ゲーム中の一つの場面 (Scene) を構成するオブジェクトやその振る舞い、
 ゲームのルールの集合を Scene Graph とする \cite{chiaki} 。
-Scene Graph のノードは
-親子関係を持つ木構造で構成される (\figref{fig:scene_graph}) 。
-そのため、Scene Graph の各ノードに対してデータ並列実行することが
-可能と言える。

-\begin{figure}[tb]
-  \begin{center}
-    \includegraphics[scale=0.35]{figure/scene_graph.pdf}
-    \caption{Scene Graph Structure}
-    \label{fig:scene_graph}
-  \end{center}
-\end{figure}
-
-Scene Graph によりプログラムが個々のゲーム場面に分割され、
-ゲーム場面の遷移を StatePattern を用いて記述すると、
-if,case 文が排除できるので、プログラムの可読性と独立性が向上する。
-これにより、過去の PS、PS2 によるゲームプログラムの移植や改良にかかる
-作業時間短縮が見込める。
-
-Scene Graph Node は以下のようなデータと動作を持つ。
-
-\begin{itemize}
-  \item データ
-    \begin{itemize}
-      \item Vervatim : ポリゴンオブジェクトの頂点座標
-      \item Texture : ポリゴンオブジェクトのテクスチャ座標
-      \item TextureImage : テクスチャイメージ
-      \item TransMatrix : ポリゴンオブジェクトの変換行列
-      \item Coordinates : オブジェクトの座標
-      \item Angle : オブジェクトの角度
-    \end{itemize}
-  \item 動作
-    \begin{itemize}
-    \item Move : 自律的なオブジェクトの動き
-    \item Collision : 他ノードと衝突したときの動き
-    \end{itemize}
-\end{itemize}
-
-今回は Scene Graph の作成に、オープンソースの 3D モデリングツールである
-Blender \cite{blender}  を用いる。Blender でオブジェクトを作成し、
-ポリゴン情報やテクスチャ情報が記述された xml ファイルを出力する。
-その xml ファイルを Rendering Engine が受け取って Polygon を生成する。
-
+%%Scene Graph のノードは
+%%親子関係を持つ木構造で構成される (\figref{fig:scene_graph}) 。
+%%そのため、Scene Graph の各ノードに対してデータ並列実行することが
+%%可能と言える。
+%%
+%%\begin{figure}[tb]
+%%  \begin{center}
+%%    \includegraphics[scale=0.35]{figure/scene_graph.pdf}
+%%    \caption{Scene Graph Structure}
+%%    \label{fig:scene_graph}
+%%  \end{center}
+%%\end{figure}
+%%
+%%Scene Graph によりプログラムが個々のゲーム場面に分割され、
+%%ゲーム場面の遷移を StatePattern を用いて記述すると、
+%%if,case 文が排除できるので、プログラムの可読性と独立性が向上する。
+%%これにより、過去の PS、PS2 によるゲームプログラムの移植や改良にかかる
+%%作業時間短縮が見込める。
+%%
+%%Scene Graph Node は以下のようなデータと動作を持つ。
+%%
+%%\begin{itemize}
+%%  \item データ
+%%    \begin{itemize}
+%%      \item Vervatim : ポリゴンオブジェクトの頂点座標
+%%      \item Texture : ポリゴンオブジェクトのテクスチャ座標
+%%      \item TextureImage : テクスチャイメージ
+%%      \item TransMatrix : ポリゴンオブジェクトの変換行列
+%%      \item Coordinates : オブジェクトの座標
+%%      \item Angle : オブジェクトの角度
+%%    \end{itemize}
+%%  \item 動作
+%%    \begin{itemize}
+%%    \item Move : 自律的なオブジェクトの動き
+%%    \item Collision : 他ノードと衝突したときの動き
+%%    \end{itemize}
+%%\end{itemize}
+%%
+%%今回は Scene Graph の作成に、オープンソースの 3D モデリングツールである
+%%Blender \cite{blender}  を用いる。Blender でオブジェクトを作成し、
+%%ポリゴン情報やテクスチャ情報が記述された xml ファイルを出力する。
+%%その xml ファイルを Rendering Engine が受け取って Polygon を生成する。
+%%

 \subsection{Rendering Engine} \label{sec:rendering-engine}
 Rendering Engine は Polygon から Span を生成する部分と Span に RGB を
@@ -105,3 +106,6 @@
     \label{fig:manager-pipeline}
   \end{center}
 \end{figure}
+
+このパイプラインは Scheduler レベルではなく、
+Task Level でのパイプラインを表している。
--- a/compare.tex	Mon Jul 14 20:09:16 2008 +0900
+++ b/compare.tex	Mon Jul 14 20:37:12 2008 +0900
@@ -71,7 +71,8 @@
 %全てのタスクを SPE 上で実行できるようになれば、
 %実行速度はさらに向上すると考えられる。

-また、Rendering のタスクだけを SPE 上で実行しているのは、
+\subsection{Cerium の今後の課題}
+Rendering のタスクだけを SPE 上で実行しているのは、
 SPE の 256KB という容量では、現在の Cerium の全てのタスクを
 SPE 上に乗せる事が出来ないからである。
 これを回避するために、SPE プログラムの on-demand load の実装が必要となる。
--- a/conclusion.tex	Mon Jul 14 20:09:16 2008 +0900
+++ b/conclusion.tex	Mon Jul 14 20:37:12 2008 +0900
@@ -2,12 +2,18 @@
 本研究では、Many Core Architecture 向けの Fine Grain Task Manager を実装した。
 また、例題として Cell 上で動作する、ゲームプログラム用フレームワークである
 Cerium を開発した。PS3 上という限られた環境だけでなく、
-Linux や Mac OS X でもテストやデバッグを行うことが出来るため、
-並列プログラミング経験の低い学生の実験にも使用できる。
+Linux や Mac OS X でもテストやデバッグを行うことが出来る。
+
+TaskManager を使用することで、
+並列プログラミング経験の低い学生の実験も、
+並列効果が見られる並列プログラムを作成する事が出来た。

-シーケンシャルプログラムから並列プログラムへ変換する際、
-コードをタスクとして分割したり、データ構造をタスクや SPE などの特殊な環境に
-合うような構造に変換する必要があるため、
-並列処理の経験がないプログラマに対しては、何らかの雛形が必要である。
+TODO
+(ちょっとここ言い回し変？)
+
+%シーケンシャルプログラムから並列プログラムへ変換する際、
+%コードをタスクとして分割したり、データ構造をタスクや SPE などの特殊な環境に
+%合うような構造に変換する必要があるため、
+%並列処理の経験がないプログラマに対しては、何らかの雛形が必要である。
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/figure/step.bb	Mon Jul 14 20:37:12 2008 +0900
@@ -0,0 +1,5 @@
+%%Title: ./step.pdf
+%%Creator: ebb Version 0.5.2 (+ArtBox)
+%%BoundingBox: 0 0 549 335
+%%CreationDate: Mon Jul 14 20:34:48 2008
+
Binary file figure/step.graffle has changed
Binary file figure/step.pdf has changed
--- a/introduction.tex	Mon Jul 14 20:09:16 2008 +0900
+++ b/introduction.tex	Mon Jul 14 20:37:12 2008 +0900
@@ -1,21 +1,23 @@
 \section{研究の目的}
 本研究室では、PS3Linux を用いて学生によるゲーム開発を行っている。
-しかし、Cell のような Many Core プログラミングは非決定的であり、
-デバッグが難しい。
-
-(ここまだ直し中です)
-
-そこで、Many Core プログラミングの手助けになるようなフレームワークを設計する。
-このフレームワークは
+しかし、通常のシーケンシャルなプログラムと違い、
+Cell のような Many Core プログラミングは非決定的であり、デバッグが難しい。

-本研究では、Many Core Architecture 向けの Fine Grain Task Manager を設計する。
-Fine Grain Task の単位はサブルーチンまたは関数とし、
-全ての Core が絶えず動くようにすることで全体の並列化率を高める。
+Many Core プログラムを記述する場合、最初に逐次的なプログラムから記述して、
+仕様やアルゴリズムの正しさを確認できたら、データやコードを分割し
+並列に実行する。これらのステップ毎にプログラムの信頼性を得ながら
+一つずつこなしていくことが大事である。
+本研究では、こういった開発行程をサポートするフレームワークとして、
+Many Core Architecture 向けのFine Grain Task Manager を設計する。

-Fine Grain Task 自身や、タスク全体のデバッグを容易にするために、
-同じタスクが Mac OS X や Linux、PS3 上など複数の環境で動くようにする。
-また、Thread を多用せず、細粒度タスク内での同期は行わない。
-これにより、並列プログラミングの経験の低いプログラマでも容易に使用できる。
+%本研究では、Many Core Architecture 向けの Fine Grain Task Manager を設計する。
+%Fine Grain Task の単位はサブルーチンまたは関数とし、
+%全ての Core が絶えず動くようにすることで全体の並列化率を高める。
+%
+%Fine Grain Task 自身や、タスク全体のデバッグを容易にするために、
+%同じタスクが Mac OS X や Linux、PS3 上など複数の環境で動くようにする。
+%また、Thread を多用せず、細粒度タスク内での同期は行わない。
+%これにより、並列プログラミングの経験の低いプログラマでも容易に使用できる。

 例題として、本研究室で作成した、Rendering を含む PS3 上のゲームプログラム用
 フレームワークである Cerium を用いる。Cerium は、次の 3 つから構成される。
@@ -26,5 +28,6 @@
   \item Fine Grain Task Manager
 \end{itemize}

-Cerium は学生実験で使用しており、並列プログラミング経験の浅い学生でも、
-移植や改良、拡張が容易に行えるツールを目的としている
+Cerium は、先に述べた学生実験で使用しており、
+並列プログラミング経験の浅い学生でも、
+移植や改良、拡張が容易に行えるツールを目的としている。
--- a/task_manager.tex	Mon Jul 14 20:09:16 2008 +0900
+++ b/task_manager.tex	Mon Jul 14 20:37:12 2008 +0900
@@ -208,18 +208,13 @@

 メインスレッド内でもタスクを実行する事が可能なため、これを用いる事により、
 環境依存によるプログラム変換はタスクの部分だけとなり、全体の変換は必要ない。
-
-このことはデバッグにおいても有効であると言える。
-デバッグが困難な並列プログラムの前に、まずはメインスレッド単体で動く
-シーケンシャルプログラムを記述する。
-仕様やアルゴリズムの正しさを確認できたら、\verb|set_cpu| により
-各 Core へタスクを渡し、並列プログラムへ移行する。
-デバッグに関する詳細は第 \ref{sec:debug} 節で述べる。
+(TODO)

 \subsection{メインスレッドと各 Core 間との同期}
 メインスレッドと各 Core 間では、32 ビットメッセージの
 交換により同期を行っている。これは Cell の機能の一つである、
 Mailbox を元に実装した。
+今回、メッセージは busy wait の形で受け取っている。

 Mailbox とは SPE の MFC 内の FIFO キューであり、
 PPE と SPE 間の 32 ビットメッセージの交換に用いられる \cite{mailbox} 。