--- a/resume/A-6-1-055734.tex	Wed Feb 25 06:34:10 2009 +0900
+++ b/resume/A-6-1-055734.tex	Wed Feb 25 07:18:40 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{並列プログラミングを用いた \\\ ゲームフレームワークの設計と実装}
\author{055734A 多賀野海人　指導教員 : 河野真治}
\date{}
\maketitle
\thispagestyle{fancy}

\section{はじめに}
我々はこれまで、PlayStation2,PlayStation3等の家庭用ゲーム機を用いたゲームプログラミングを、
リアルタイムプログラム、ユーザインターフェイスの学生実験の一環として行ってきた。

しかし、Cell を用いる場合、データの転送やタスクの生成等のこれまで学んだことのない技術が多く存在する。
これにより、学生実験の短期間では新しい技術を学ぶことに多くの時間を取られ、ゲームの完成度が向上が困難である。

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

\section{Cell、SPEの問題点} \label{sec:cell}
Cell\cite{cell}はメインプロセッサである １基の PowerPC Processor Element (PPE) 
と８基のデータ処理プロセッサアーキテクチャー Synergistic Processor Element (SPE)
からなる非対称なマルチコアプロセッサであり、高速リングバスで構成されている。

PPE は 複数の SPU をコアプロセッサとして使用することができる汎用プロセッサである。
SPE は、 PPE のような複雑なプログラム制御よりも、計算を単純に繰り返すマルチメディア系の処理を得意とする
演算系プロセッサである。LS (Local Store) という256KBのメモリを持つ。
本研究で用いた PS3Linux では、６個の SPE を制御することができる。

SPE には 256KB しか搭載されていないという問題点がある。これは SPE 内で動作させるコードなども含めて
である。メインメモリからデータを持ってくることも可能だが、SPE が直接メインメモリにアクセスすることはできず、
メインメモリにアクセスするには DMA を用いる。

DMA (Direct Memory Access) 転送とは、CPU を介さずに周辺装置と
メモリとの間でデータ転送ことで、Cell の場合は
メインメモリと LS 間でデータの転送を行う。手順としては以下の様になる。

\begin{enumerate}
  \item SPE プログラムが MFC (Memory Flow Controller) に対して
    DMA 転送命令を発行する。
  \item MFC が DMA Controller を介して DMA 転送を開始。
    この間、SPE プログラムは停止しない。
  \item DMA 転送の終了を待つ場合、SPE プログラム内で転送の完了を待つ。
\end{enumerate}

SPE が直接メインメモリにアクセスできないことと、DMA 転送の待ち時間が
SPE でプログラミングを行う際の大きな問題となる。

% \subsection{Cerium Rendering Engine の提案}

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

\begin{figure}[hbp]
  \begin{center}
    \includegraphics[scale=0.5]{image/Cerium.pdf}
    \caption{Cerium の構成要素}
    \label{fig:cerium}
  \end{center}
\end{figure}

%ゲーム内で使用するオブジェクトの生成は Blender \cite{blender}というフリーの
%3D モデリングツールを使用し、Cerium 独自の xml 形式で出力する。
Rendering Engine では、SceneGraph から実際に表示するポリゴンの抽出、
ポリゴンから Span の生成、 Span に RGB をマッピングし描画する部分と３つに分けることが出来る。

Span とはポリゴンに対するある特定の Y 座標に関するデータを抜き出したものである。図\ref{fig:cerium}

Cerium では Span の生成、描画に必要な Texture の計算などあらゆる処理を SPE で並列実行できるように
設計されている。

\section{Rendering部分の高速化}

SPE を用いて計算を行う場合には、その処理（ソースコード）とデータを SPE の LS に転送して行う。
しかし、SPE の LS は 256KB しかないので、一度に Texture データを転送すると容量を超えてしまう可能性がある。

そこで、描画に必要な Texture データを分割して転送するという手法を用いる。
分割したデータを Tile とし、分割単位は 8 x 8 pixel とする。図\ref{fig:texture_split}
\cite{wataru}

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.5]{image/cerium_rendering_tile.pdf}
    \caption{Texture の分割 (Tile) }
    \label{fig:texture_split}
  \end{center}
\end{figure}

図\ref{fig:cerium}の SpanPack に含まれる Texture のアドレスはこの配列を
指している。描画に必要な Tile を計算し、メインメモリから DMA 転送し、pixel の
情報を取り出す。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.5]{image/Span-tile.pdf}
    \caption{Span からの Texture の計算 }
    \label{fig:span}
  \end{center}
\end{figure}

\begin{enumerate}
\item Span の 持っている Texture A の座標から A が含まれる Tile を求める。
\item Tile ID と Texture のTOP Adress から、描画に用いられる、Texture のpixel adress を求める
\item Texxture の座標から、pixel が持つ RGB 値を返す。
\end{enumerate}

また、描画されるオブジェクトが遠くにある場合、そのままの大きさの Texture は必要ないので、
縮小サイズの Texture (Scale) を用意し、Span の長さによって描画に必要な Texture を取捨選択することにする。
これにより、DMA 転送の待ち時間が減少し、ゲームの実行速度が向上すると考えられる。
　\\

以下に分割、Scale 作成のプログラムの一部と実行速度の比較を示す。

\begin{table}[htb]
  \begin{center}
    \caption{Scale を用いることによる実行速度の比較}
    \hbox to\hsize{\hfil
      \begin{tabular}{c|l|l} \hline \hline
         & Scaleなし(FPS) & Scaleあり (FPS)\\ \hline
        \hline
        Playstation 3 & 10.8 & 13.5 \\ \hline
        Mac OSX & 7.0 & 8.5\\ \hline
      \end{tabular}\hfil}
    \label{tb:scale}
  \end{center}
\end{table}
{\scriptsize* FPS とは Frame Per Second の略で、１秒間に何回画面を書き換えたかを表している。}

表\ref{tb:scale}から、Texture の Scale 選択により Playstation 3 上では 30% ほど
実行速度が向上していることが分かる。MacOSX 上でほとんど効果が見られないのは、
 PPU １つでゲームの処理を行っているからである。

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

現在 Cerium は SPE を 6 個使う場合と 1 つしか使わない場合で約 3.5 倍の上昇が見られる。\cite{wataru}


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

\bibitem{cell}Sony Corporation.

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

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

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

\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{並列プログラミングを用いた \\\ ゲームフレームワークの設計と実装}
\author{055734A 多賀野海人　指導教員 : 河野真治}
\date{}
\maketitle
\thispagestyle{fancy}

\section{はじめに}
我々はこれまで、PlayStation2,PlayStation3等の家庭用ゲーム機を用いたゲームプログラミングを、
リアルタイムプログラム、ユーザインターフェイスの学生実験の一環として行ってきた。

しかし、Cell を用いる場合、データの転送やタスクの生成等のこれまで学んだことのない技術が多く存在する。
これにより、学生実験の短期間では新しい技術を学ぶことに多くの時間を取られ、ゲームの完成度が向上が困難である。

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

\section{Cell、SPEの問題点} \label{sec:cell}
Cell\cite{cell}はメインプロセッサである １基の PowerPC Processor Element (PPE) 
と８基のデータ処理プロセッサアーキテクチャー Synergistic Processor Element (SPE)
からなる非対称なマルチコアプロセッサであり、高速リングバスで構成されている。

PPE は 複数の SPU をコアプロセッサとして使用することができる汎用プロセッサである。
SPE は、 PPE のような複雑なプログラム制御よりも、計算を単純に繰り返すマルチメディア系の処理を得意とする
演算系プロセッサである。LS (Local Store) という256KBのメモリを持つ。
本研究で用いた PS3Linux では、６個の SPE を制御することができる。

SPE には 256KB しか搭載されていないという問題点がある。これは SPE 内で動作させるコードなども含めて
である。メインメモリからデータを持ってくることも可能だが、SPE が直接メインメモリにアクセスすることはできず、
メインメモリにアクセスするには DMA を用いる。

DMA (Direct Memory Access) 転送とは、CPU を介さずに周辺装置と
メモリとの間でデータ転送ことで、Cell の場合は
メインメモリと LS 間でデータの転送を行う。手順としては以下の様になる。

\begin{enumerate}
  \item SPE プログラムが MFC (Memory Flow Controller) に対して
    DMA 転送命令を発行する。
  \item MFC が DMA Controller を介して DMA 転送を開始。
    この間、SPE プログラムは停止しない。
  \item DMA 転送の終了を待つ場合、SPE プログラム内で転送の完了を待つ。
\end{enumerate}

SPE が直接メインメモリにアクセスできないことと、DMA 転送の待ち時間が
SPE でプログラミングを行う際の大きな問題となる。

% \subsection{Cerium Rendering Engine の提案}

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

\begin{figure}[hbp]
  \begin{center}
    \includegraphics[scale=0.5]{image/Cerium.pdf}
    \caption{Cerium の構成要素}
    \label{fig:cerium}
  \end{center}
\end{figure}

%ゲーム内で使用するオブジェクトの生成は Blender \cite{blender}というフリーの
%3D モデリングツールを使用し、Cerium 独自の xml 形式で出力する。
Rendering Engine では、SceneGraph から実際に表示するポリゴンの抽出、
ポリゴンから Span の生成、 Span に RGB をマッピングし描画する部分と３つに分けることが出来る。

Span とはポリゴンに対するある特定の Y 座標に関するデータを抜き出したものである。図\ref{fig:cerium}

Cerium では Span の生成、描画に必要な Texture の計算などあらゆる処理を SPE で並列実行できるように
設計されている。

\section{Rendering部分の高速化}

SPE を用いて計算を行う場合には、その処理（ソースコード）とデータを SPE の LS に転送して行う。
しかし、SPE の LS は 256KB しかないので、一度に Texture データを転送すると容量を超えてしまう可能性がある。

そこで、描画に必要な Texture データを分割して転送するという手法を用いる。
分割したデータを Tile とし、分割単位は 8 x 8 pixel とする。図\ref{fig:texture_split}
\cite{wataru}

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.5]{image/cerium_rendering_tile.pdf}
    \caption{Texture の分割 (Tile) }
    \label{fig:texture_split}
  \end{center}
\end{figure}

図\ref{fig:cerium}の SpanPack に含まれる Texture のアドレスはこの配列を
指している。描画に必要な Tile を計算し、メインメモリから DMA 転送し、pixel の
情報を取り出す。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.5]{image/Span-tile.pdf}
    \caption{Span からの Texture の計算 }
    \label{fig:span}
  \end{center}
\end{figure}

\begin{enumerate}
\item Span の 持っている Texture A の座標から A が含まれる Tile を求める。
\item Tile ID と Texture のTOP Adress から、描画に用いられる、Texture のpixel adress を求める
\item Texxture の座標から、pixel が持つ RGB 値を返す。
\end{enumerate}

また、描画されるオブジェクトが遠くにある場合、そのままの大きさの Texture は必要ないので、
縮小サイズの Texture (Scale) を用意し、Span の長さによって描画に必要な Texture を取捨選択することにする。
Texture は縦横ともに 1/2、1/4、1/8 と、2分の1ずつ縮小させる。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.4]{image/Scale.pdf}
    \caption{縮小画像(Scale)}
    \label{fig:span}
  \end{center}
\end{figure}　

以下に最大限に Scale を用いたときの実行速度の比較を示す。

\begin{table}[htb]
  \begin{center}
    \caption{Scale を用いることによる実行速度の比較}
    \hbox to\hsize{\hfil
      \begin{tabular}{c|l|l} \hline \hline
         & Scaleなし(FPS) & Scaleあり (FPS)\\ \hline
        \hline
        Playstation 3 & 10.8 & 13.5 \\ \hline
        Mac OSX & 7.0 & 8.5\\ \hline
      \end{tabular}\hfil}
    \label{tb:scale}
  \end{center}
\end{table}
{\scriptsize* FPS とは Frame Per Second の略で、１秒間に何回画面を書き換えたかを表している。}

表\ref{tb:scale}から、Texture の Scale 選択により Playstation 3 上では 30% ほど
実行速度が向上していることが分かる。これは、Scale (縮小 Texture) を用いることによって描画に必要な pixel データ
のヒット率が上昇していることが要因である。

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

現在 Cerium は SPE を 6 個使う場合と 1 つしか使わない場合で実行速度に約 3.5 倍の上昇が見られる。
SPE に特化したチューニングを行い、更なる速度の向上を目指す。


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

\bibitem{cell}Sony Corporation.

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

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

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

\bibitem{wataru} Wataru MIYAGUNI.

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

\end{thebibliography}
\end{document}
\ No newline at end of file