# HG changeset patch
# User aaa
# Date 1256808199 -32400
# Node ID 58869ccf7389c94476479213444d8a11e8cdb231
# Parent  f35b244292d021bb9b322a16214680bda2fab1a6
add vacuum.png

diff -r f35b244292d0 -r 58869ccf7389 resume/A-6-1-065746.tex
--- a/resume/A-6-1-065746.tex	Thu Oct 29 18:16:37 2009 +0900
+++ b/resume/A-6-1-065746.tex	Thu Oct 29 18:23:19 2009 +0900
@@ -1,1 +1,1 @@
-\documentclass[twocolumn,twoside,9.5pt]{jarticle}
% \usepackage[dvips]{graphicx}
\usepackage[dvipdfm]{graphicx}
\usepackage{fancyhdr,picins}
\pagestyle{fancy}
\lhead{\parpic{
\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.pdf}}
琉球大学主催 工学部情報工学科 卒業研究発表会}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\begin{document}
\title{SceneGraph を用いた\\マルチコア CPU 向けゲームの処理}
\author{065746J 仲宗根広樹　指導教員 : 河野真治}
\date{\today}
\maketitle
\thispagestyle{fancy}

\section{概要}
ゲームプログラミングにおける並列処理は、データが処理される順番を把握することができないので出力結果などが特定しづらく、デバッグが困難である。データ転送やタスクの生成、管理等のこれまで学んだことのない技術が多く存在する。短期間の学生実験では新しい技術を習得することに時間を割かれ、ゲームの完成度を上げることが難しくなる。

本研究では、PlayStation3 上でゲームプログラミングを行う際に、Cell の性能を活かしながら、アーキテクチャに依存する記述を排除した、汎用的な並列プログラミングを目的としている
。

\section{SceneGraph を使ったゲーム作成}
SceneGraph とはゲーム中の１つの場面(Scene) を構成するオブジェクトやその振る舞い、ゲームのルールの集合のことである。SceneGraph のノードは親子関係を持つ tree で構成される(図\ref{fig:SceneGraph})。

SceneGraph を使用すると、ゲーム内のオブジェクトは個別に SceneGraph ノードに分けられているので、ノードを別個に処理すると自然と並列度がでてくる。

SceneGraph ノード は以下のようなデータと動作を持つ。
\begin{itemize}
  \item データ
    \begin{enumerate}
      \item Vertex ：ポリゴンオブジェクトの頂点座標
      \item Texture：ポリゴンオブジェクトのテクスチャ座標
      \item TextureImage：テクスチャイメージ
      \item TransMatrix ：ポリゴンオブジェクトの変換行列
      \item Coordinates ：オブジェクトの座標
      \item Angle：オブジェクトの角度
    \end{enumerate}
  \item 動作
    \begin{enumerate}
      \item Move：自律的なオブジェクトの動き
      \item Collision：他のノードとの衝突判定をする
    \end{enumerate}
\end{itemize}

%現在はゲームの main loop (PPE) で SceneGraph ノードのリストを辿り、シーケンシャルに Move, Collision を実行している。
ゲームは各ノードの Move, Collision を実行して SceneGraph の描画を繰り返す事で進行する。
%Move, Collision はノードの数だけ実行されるので、ゲームの規模が大きくなればそれに比例して増大する。制御系プロセッサ PPE に膨大な量の演算をさせるのは好ましくない。
%本研究では Move, Collision の処理を複数のコアを用いて処理させて全てのコアが常に busy 状態になることを目標とする。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.4]{image/SceneGraph.pdf}
    \caption{SceneGraph}
    \label{fig:SceneGraph}
  \end{center}
\end{figure}

%Cerium の並列度の向上を計り、プレイヤーが満足できるゲームの処理速度を実現させる。
%家庭用ゲーム機 PlayStation 3 には Cell というヘテロジニアスマルチコアプロセッサが搭載されている。
%当研究室では Cell 上でゲームプログラミングができる Cell Task Manager Cerium を開発した。
%Cerium は TaskManager, SceneGraph, Rendering Engine の３つの機能に分けられる。

%Cerium の並列度の向上を計り、プレイヤーが満足できる処理速度を実現させる
%当研究室では家庭用ゲーム機 PlayStation 3 上でゲームプログラミングができる Cell Task Manager Cerium を開発した。
%現在、PlayStation 3 の GPU にアクセスする API は公開されていないため Cerium は独自に Rendering Engine を持っている。
%Cerium は TaskManager, Rendering, SceneGraph の三つで構成されている。



\section{Cell Broadband Engine} \label{sec:cell}
Cell\cite{cell} は１基の PowerPC Processor Element (PPE) と８基の Synergistic Processor Element (SPE) で構成されるヘテロジニアスマルチコアプロセッサである。各プロセッサは高速バスで接続されている。本研究では６基の SPE が使用可能となっている。

PPE は汎用プロセッサでありオペレーティングシステムやアプリケーションの実行、SPE を制御する役割を持っている。SPE は演算を繰り返すマルチメディア系の処理を得意とする演算系プロセッサである。SPE は 演算処理を行う SPU、256 KByte の Local Store、メインメモリや他の SPE とデータをやり取りする Memory Flow Controller の３つで構成されている。

\section{Cerium}
Cerium とは当研究室で開発した Cell 上で動作するゲームフレームワークである。
Cerium は SceneGraph、OSMesa に代表される Rendering Engine、そしてそれらの実行単位を Task とし、動的に全てのコアが動作する様な割り振りを行うカーネル TaskManager で構成されている。

現在、Cerium では SceneGraph の Move, Collision を PPE でシーケンシャルに処理しているので、この部分の処理を SPE を用いて並列に処理するように変更する。

%ゲーム内で使用するオブジェクトは Cerium 独自の xml 形式で書かれており、xml ファイルを読込んで SceneGraph を生成する。
%Rendering に関しては処理を Task 単位に分割して SPE に投入して処理しているが、SceneGraph の処理は PPE １つで行っている。
%SceneGraph の move, collision の処理は PPE で行っている。しかし PPE に単純な演算の繰り返しをさせるのは好ましくない。
%そこで、SceneGraph の処理も Task に分割して SPE に投入し、Rendering と並行に走らせる事で処理速度の向上を計る。

\section{SceneGraph の並列処理}
Rendering と SceneGraph の処理を並行に実行するために SceneGraph の tree と後述する Property のバッファは2つずつ用意する。
一方の SceneGraph tree と Property を Rendering で使用し、もう一方を Move, Collision で使用し、両方の処理が終わったらバッファを切り替えてやる。
%ゲーム内のオブジェクトは個別に SceneGraph ノードに分けられているので、SceneGraph を別個に処理するだけで並列処理になる。
\subsection{vacuum}
6基の SPE を用いたSceneGraph の処理の例題として、学生実験で作成されたゲーム vacuum を使用する。
vacuum には自機と吸収ブロック、敵ブロックの３種類のオブジェクトがあり、自機を上下左右に移動させ、ボタンを押している間は自機の周りのブロックを引き寄せ、うまく吸収ブロックだけを自機と衝突させるゲームである。

Move, Collision を SPE で処理する際に、SPE には SceneGraph ノードは送らない。代わりに vacuum の Move, Collision に必要な情報をまとめた Property を送る。

Property は SceneGraph ノードと1対1で対応しており、Coordinates, Angle, 親子関係の情報, 生成消滅の情報を持つ。
%SceneGraph ノードにはポリゴンを形成するための点やテクスチャの座標等が含まれている。これらの情報を全て SPE に送ると Local Store に入りきらない。そのため Move、Collision に必要な Coordinates, Angle, 親子関係の情報、生成消滅の情報を持つ Property の配列を作成する。
%SceneGraph の tree と Property のバッファは二つ用意する。

\subsection{Move}
vacuum のオブジェクトは全て独立して動くので、使用する SPE に均等に Property を割り振る。
SPE でオブジェクトの種類毎の Move 処理を行い、Property を更新して PPE に返す。

\if0
\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.43]{image/Move.pdf}
    \caption{vacuum の Move}
    \label{fig:Move}
  \end{center}
\end{figure}
\fi

\subsection{Collision}
vaccum の Collision は自機と吸収ブロック(Collision A)、自機と敵ブロック(Collision B)の二つがある。
Collision の種類毎に SPE で動作する Collision Task を作成する。どちらの Collision も自機とブロックの衝突判定しか行わないので SPE には自機とブロックの Property を送り、SPE で2者間の衝突判定を行い、Property を更新して PPE に返す。(図\ref{fig:Collision})\\

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.43]{image/Collision.pdf}
    \caption{Collision に使う Property を各 SPE に渡す}
    \label{fig:Collision}
  \end{center}
\end{figure}

PPE 側では返されてきた Property を元に SceneGraph を作成し Tree を再構成して Rendering に渡す。

\section{まとめと今後の課題}
\begin{itemize}
\item 現在は SPE 1基で SceneGraph を処理する例題の作成途中なので、複数 SPE に均等に処理を割り振る例題の作成。
\item Property から SceneGraph を生成し tree を構築する部分において、SceneGraph の新規生成と削除を考慮した設計を行う。
\item xml から作成された SceneGraph はオリジナルとして配列に順次格納されている。現在は SceneGraph を create する場合はオリジナルの配列をリニアサーチしてきた物をコピーしている。このオリジナルの配列を Texture を管理している hash テーブルを用いてまとめて管理できるようにする。
\end{itemize}

\thispagestyle{fancy}
\begin{thebibliography}{9}

\bibitem{cell}Sony Corporation.

Cell BroadbandEngine \texttrademark アーキテクチャ, 2006

\bibitem{spursengine}TOSHIBA: SpursEngine

\verb|http://www.semicon.toshiba.co.jp|\\
\verb|/product/assp/selection/spursengine/index.html|

\bibitem{cerium} SourceForge.JP: Cerium Rendering Engine

\verb|https//sourceforge.jp/projects/cerium/|

\bibitem{opencl} OpenCL

\verb|http://www.khronos.org/opencl/|

\bibitem{wataru} Wataru MIYAGUNI.

Cell 用の Fine-Grain Task Manager の実装, 2009

\end{thebibliography}
\end{document}
\ No newline at end of file
+\documentclass[twocolumn,twoside,9.5pt]{jarticle}
% \usepackage[dvips]{graphicx}
\usepackage[dvipdfm]{graphicx}
\usepackage{fancyhdr,picins}
\pagestyle{fancy}
\lhead{\parpic{
\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.pdf}}
琉球大学主催 工学部情報工学科 卒業研究発表会}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\begin{document}
\title{SceneGraph を用いた\\マルチコア CPU 向けゲームの処理}
\author{065746J 仲宗根広樹　指導教員 : 河野真治}
\date{\today}
\maketitle
\thispagestyle{fancy}

\section{概要}
ゲームプログラミングにおける並列処理は、データが処理される順番を把握することができないので出力結果などが特定しづらく、デバッグが困難である。データ転送やタスクの生成、管理等のこれまで学んだことのない技術が多く存在する。短期間の学生実験では新しい技術を習得することに時間を割かれ、ゲームの完成度を上げることが難しくなる。

本研究では、PlayStation3 上でゲームプログラミングを行う際に、Cell の性能を活かしながら、アーキテクチャに依存する記述を排除した、汎用的な並列プログラミングを目的としている
。

\section{SceneGraph を使ったゲーム作成}
SceneGraph とはゲーム中の１つの場面(Scene) を構成するオブジェクトやその振る舞い、ゲームのルールの集合のことである。SceneGraph のノードは親子関係を持つ tree で構成される(図\ref{fig:SceneGraph})。

SceneGraph を使用すると、ゲーム内のオブジェクトは個別に SceneGraph ノードに分けられているので、ノードを別個に処理すると自然と並列度がでてくる。

SceneGraph ノード は以下のようなデータと動作を持つ。
\begin{itemize}
  \item データ
    \begin{enumerate}
      \item Vertex ：ポリゴンオブジェクトの頂点座標
      \item Texture：ポリゴンオブジェクトのテクスチャ座標
      \item TextureImage：テクスチャイメージ
      \item TransMatrix ：ポリゴンオブジェクトの変換行列
      \item Coordinates ：オブジェクトの座標
      \item Angle：オブジェクトの角度
    \end{enumerate}
  \item 動作
    \begin{enumerate}
      \item Move：自律的なオブジェクトの動き
      \item Collision：他のノードとの衝突判定をする
    \end{enumerate}
\end{itemize}

%現在はゲームの main loop (PPE) で SceneGraph ノードのリストを辿り、シーケンシャルに Move, Collision を実行している。
ゲームは各ノードの Move, Collision を実行して SceneGraph の描画を繰り返す事で進行する。
%Move, Collision はノードの数だけ実行されるので、ゲームの規模が大きくなればそれに比例して増大する。制御系プロセッサ PPE に膨大な量の演算をさせるのは好ましくない。
%本研究では Move, Collision の処理を複数のコアを用いて処理させて全てのコアが常に busy 状態になることを目標とする。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.4]{image/SceneGraph.pdf}
    \caption{SceneGraph}
    \label{fig:SceneGraph}
  \end{center}
\end{figure}

%Cerium の並列度の向上を計り、プレイヤーが満足できるゲームの処理速度を実現させる。
%家庭用ゲーム機 PlayStation 3 には Cell というヘテロジニアスマルチコアプロセッサが搭載されている。
%当研究室では Cell 上でゲームプログラミングができる Cell Task Manager Cerium を開発した。
%Cerium は TaskManager, SceneGraph, Rendering Engine の３つの機能に分けられる。

%Cerium の並列度の向上を計り、プレイヤーが満足できる処理速度を実現させる
%当研究室では家庭用ゲーム機 PlayStation 3 上でゲームプログラミングができる Cell Task Manager Cerium を開発した。
%現在、PlayStation 3 の GPU にアクセスする API は公開されていないため Cerium は独自に Rendering Engine を持っている。
%Cerium は TaskManager, Rendering, SceneGraph の三つで構成されている。



\section{Cell Broadband Engine} \label{sec:cell}
Cell\cite{cell} は１基の PowerPC Processor Element (PPE) と８基の Synergistic Processor Element (SPE) で構成されるヘテロジニアスマルチコアプロセッサである。各プロセッサは高速バスで接続されている。本研究では６基の SPE が使用可能となっている。

PPE は汎用プロセッサでありオペレーティングシステムやアプリケーションの実行、SPE を制御する役割を持っている。SPE は演算を繰り返すマルチメディア系の処理を得意とする演算系プロセッサである。SPE は 演算処理を行う SPU、256 KByte の Local Store、メインメモリや他の SPE とデータをやり取りする Memory Flow Controller の３つで構成されている。

\section{Cerium}
Cerium とは当研究室で開発した Cell 上で動作するゲームフレームワークである。
Cerium は SceneGraph、OSMesa に代表される Rendering Engine、そしてそれらの実行単位を Task とし、動的に全てのコアが動作する様な割り振りを行うカーネル TaskManager で構成されている。

現在、Cerium では SceneGraph の Move, Collision を PPE でシーケンシャルに処理しているので、この部分の処理を SPE を用いて並列に処理するように変更する。

%ゲーム内で使用するオブジェクトは Cerium 独自の xml 形式で書かれており、xml ファイルを読込んで SceneGraph を生成する。
%Rendering に関しては処理を Task 単位に分割して SPE に投入して処理しているが、SceneGraph の処理は PPE １つで行っている。
%SceneGraph の move, collision の処理は PPE で行っている。しかし PPE に単純な演算の繰り返しをさせるのは好ましくない。
%そこで、SceneGraph の処理も Task に分割して SPE に投入し、Rendering と並行に走らせる事で処理速度の向上を計る。

\section{SceneGraph の並列処理}
Rendering と SceneGraph の処理を並行に実行するために SceneGraph の tree と後述する Property のバッファは2つずつ用意する。
一方の SceneGraph tree と Property を Rendering で使用し、もう一方を Move, Collision で使用し、両方の処理が終わったらバッファを切り替えてやる。
%ゲーム内のオブジェクトは個別に SceneGraph ノードに分けられているので、SceneGraph を別個に処理するだけで並列処理になる。
\subsection{vacuum}
6基の SPE を用いたSceneGraph の処理の例題として、学生実験で作成されたゲーム vacuum を使用する。
vacuum には自機と吸収ブロック、敵ブロックの３種類のオブジェクトがあり、自機を上下左右に移動させ、ボタンを押している間は自機の周りのブロックを引き寄せ、うまく吸収ブロックだけを自機と衝突させるゲームである。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.7]{image/vacuum.png}
    \caption{vacuum のゲーム画面}
    \label{fig:vacuum}
  \end{center}
\end{figure}

Move, Collision を SPE で処理する際に、SPE には SceneGraph ノードは送らない。代わりに vacuum の Move, Collision に必要な情報をまとめた Property を送る。

Property は SceneGraph ノードと1対1で対応しており、Coordinates, Angle, 親子関係の情報, 生成消滅の情報を持つ。
%SceneGraph ノードにはポリゴンを形成するための点やテクスチャの座標等が含まれている。これらの情報を全て SPE に送ると Local Store に入りきらない。そのため Move、Collision に必要な Coordinates, Angle, 親子関係の情報、生成消滅の情報を持つ Property の配列を作成する。
%SceneGraph の tree と Property のバッファは二つ用意する。

\subsection{Move}
vacuum のオブジェクトは全て独立して動くので、使用する SPE に均等に Property を割り振る。
SPE でオブジェクトの種類毎の Move 処理を行い、Property を更新して PPE に返す。

\if0
\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.43]{image/Move.pdf}
    \caption{vacuum の Move}
    \label{fig:Move}
  \end{center}
\end{figure}
\fi

\subsection{Collision}
vaccum の Collision は自機と吸収ブロック(Collision A)、自機と敵ブロック(Collision B)の二つがある。
Collision の種類毎に SPE で動作する Collision Task を作成する。どちらの Collision も自機とブロックの衝突判定しか行わないので SPE には自機とブロックの Property を送り、SPE で2者間の衝突判定を行い、Property を更新して PPE に返す。(図\ref{fig:Collision})\\

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.43]{image/Collision.pdf}
    \caption{Collision に使う Property を各 SPE に渡す}
    \label{fig:Collision}
  \end{center}
\end{figure}

PPE 側では返されてきた Property を元に SceneGraph を作成し Tree を再構成して Rendering に渡す。

\section{まとめと今後の課題}
\begin{itemize}
\item 現在は SPE 1基で SceneGraph を処理する例題の作成途中なので、複数 SPE に均等に処理を割り振る例題の作成。
\item Property から SceneGraph を生成し tree を構築する部分において、SceneGraph の新規生成と削除を考慮した設計を行う。
\item xml から作成された SceneGraph はオリジナルとして配列に順次格納されている。現在は SceneGraph を create する場合はオリジナルの配列をリニアサーチしてきた物をコピーしている。このオリジナルの配列を Texture を管理している hash テーブルを用いてまとめて管理できるようにする。
\end{itemize}

\thispagestyle{fancy}
\begin{thebibliography}{9}

\bibitem{cell}Sony Corporation.

Cell BroadbandEngine \texttrademark アーキテクチャ, 2006

\bibitem{spursengine}TOSHIBA: SpursEngine

\verb|http://www.semicon.toshiba.co.jp|\\
\verb|/product/assp/selection/spursengine/index.html|

\bibitem{cerium} SourceForge.JP: Cerium Rendering Engine

\verb|https//sourceforge.jp/projects/cerium/|

\bibitem{opencl} OpenCL

\verb|http://www.khronos.org/opencl/|

\bibitem{wataru} Wataru MIYAGUNI.

Cell 用の Fine-Grain Task Manager の実装, 2009

\end{thebibliography}
\end{document}
\ No newline at end of file
diff -r f35b244292d0 -r 58869ccf7389 resume/image/vacuum.bb
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/resume/image/vacuum.bb	Thu Oct 29 18:23:19 2009 +0900
@@ -0,0 +1,5 @@
+%%Title: ./vacuum.png
+%%Creator: ebb Version 0.5.2 (+ArtBox)
+%%BoundingBox: 0 0 257 156
+%%CreationDate: Thu Oct 29 18:22:21 2009
+
diff -r f35b244292d0 -r 58869ccf7389 resume/image/vacuum.png
Binary file resume/image/vacuum.png has changed