changeset 10:e95d7edab4c8

final!?
author tkaito@nw0534.st.ie.u-ryukyu.ac.jp
date Wed, 25 Feb 2009 17:44:01 +0900
parents 63d256a7851a
children f813141366d4
files resume/A-6-1-055734.aux resume/A-6-1-055734.dvi resume/A-6-1-055734.log resume/A-6-1-055734.pdf resume/A-6-1-055734.tex
diffstat 5 files changed, 19 insertions(+), 19 deletions(-) [+]
line wrap: on
line diff
--- a/resume/A-6-1-055734.aux	Wed Feb 25 16:47:26 2009 +0900
+++ b/resume/A-6-1-055734.aux	Wed Feb 25 17:44:01 2009 +0900
@@ -5,10 +5,10 @@
 \newlabel{sec:cell}{{2}{1}}
 \@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Cerium の構成要素}}{1}}
 \newlabel{fig:cerium}{{1}{1}}
+\@writefile{toc}{\contentsline {section}{\numberline {3}Rendering部分の高速化}{1}}
 \citation{wataru}
 \bibcite{cell}{1}
 \bibcite{wataru}{2}
-\@writefile{toc}{\contentsline {section}{\numberline {3}Rendering部分の高速化}{2}}
 \@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Texture の分割 (Tile) }}{2}}
 \newlabel{fig:texture_split}{{2}{2}}
 \@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Span からの Texture の計算 }}{2}}
@@ -17,4 +17,4 @@
 \newlabel{fig:span}{{4}{2}}
 \@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Scale を用いることによる実行速度の比較}}{2}}
 \newlabel{tb:scale}{{1}{2}}
-\@writefile{toc}{\contentsline {section}{\numberline {4}まとめと今後の課題}{2}}
+\@writefile{toc}{\contentsline {section}{\numberline {4}今後の課題}{2}}
Binary file resume/A-6-1-055734.dvi has changed
--- a/resume/A-6-1-055734.log	Wed Feb 25 16:47:26 2009 +0900
+++ b/resume/A-6-1-055734.log	Wed Feb 25 17:44:01 2009 +0900
@@ -1,4 +1,4 @@
-This is pTeX, Version 3.141592-p3.1.10 (utf8.euc) (Web2C 7.5.4) (format=platex-euc 2009.2.10)  25 FEB 2009 16:46
+This is pTeX, Version 3.141592-p3.1.10 (utf8.euc) (Web2C 7.5.4) (format=platex-euc 2009.2.10)  25 FEB 2009 17:43
 **A-6-1-055734
 (./A-6-1-055734.tex
 pLaTeX2e <2006/11/10>+0 (based on LaTeX2e <2003/12/01> patch level 0)
@@ -144,7 +144,7 @@
 (Font)              Font shape `JY1/gt/m/n' tried instead on input line 29.
 File: image/Cerium.pdf Graphic file (type eps)
  <image/Cerium.pdf>
-Overfull \hbox (22.02818pt too wide) in paragraph at lines 81--82
+Overfull \hbox (22.02818pt too wide) in paragraph at lines 79--80
  [] 
  []
 
@@ -166,25 +166,25 @@
  <image/Span-tile.pdf>
 File: image/Scale.pdf Graphic file (type eps)
  <image/Scale.pdf>
-LaTeX Font Info:    Try loading font information for OMS+cmr on input line 147.
+LaTeX Font Info:    External font `cmex10' loaded for size
+(Font)              <7> on input line 143.
+LaTeX Font Info:    External font `cmex10' loaded for size
+(Font)              <5> on input line 143.
 
+Overfull \hbox (12.12494pt too wide) detected at line 149
+ [] 
+ []
+
+LaTeX Font Info:    Try loading font information for OMS+cmr on input line 155.
 
 (/opt/local/share/texmf-dist/tex/latex/base/omscmr.fd
 File: omscmr.fd 1999/05/25 v2.5h Standard LaTeX font definitions
 )
 LaTeX Font Info:    Font shape `OMS/cmr/m/n' in size <7> not available
-(Font)              Font shape `OMS/cmsy/m/n' tried instead on input line 147.
-LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <7> on input line 156.
-LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <5> on input line 156.
-
-Overfull \hbox (12.12494pt too wide) detected at line 162
- [] 
- []
-
+(Font)              Font shape `OMS/cmsy/m/n' tried instead on input line 155.
 File: pic/emblem-bitmap.pdf Graphic file (type eps)
-<pic/emblem-bitmap.pdf> [2] (./A-6-1-055734.aux)
+ <pic/emblem-bitmap.pdf>
+[2] (./A-6-1-055734.aux)
 
 LaTeX Warning: There were multiply-defined labels.
 
@@ -196,6 +196,6 @@
  4027 multiletter control sequences out of 10000+50000
  13256 words of font info for 52 fonts, out of 1200000 for 2000
  14 hyphenation exceptions out of 8191
- 27i,15n,43p,213b,573s stack positions out of 5000i,500n,6000p,200000b,5000s
+ 27i,16n,43p,213b,573s stack positions out of 5000i,500n,6000p,200000b,5000s
 
-Output written on A-6-1-055734.dvi (2 pages, 11840 bytes).
+Output written on A-6-1-055734.dvi (2 pages, 11736 bytes).
Binary file resume/A-6-1-055734.pdf has changed
--- a/resume/A-6-1-055734.tex	Wed Feb 25 16:47:26 2009 +0900
+++ b/resume/A-6-1-055734.tex	Wed Feb 25 17:44:01 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 , SPU を用いたプログラミング} \label{sec:cell}
Cell\cite{cell}はメインプロセッサである 1基の PowerPC Processor Element (PPE) 
と8基のデータ処理プロセッサアーキテクチャー Synergistic Processor Element (SPE)
からなる非対称なマルチコアプロセッサであり、高速リングバスで構成されている。

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

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

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

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

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

% \subsection{Cerium Rendering Engine の提案}

Cell 用いたゲームプログラミングを行うために、我々の研究室では Cerium を用意した。
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 をマッピングし描画する部分と3つに分けることが出来る。

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

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

\section{Rendering部分の高速化}

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

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

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.4]{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.4]{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}

現在、SPU に転送された Tile は SPU 上に 128 個まで保存される。
ハッシュを用いて、既に SPU に Tile が存在するかどうかを調べて、DMA 転送の無駄を省いている。\\

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

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.35]{image/Scale.pdf}
    \caption{縮小画像(Scale)}
    \label{fig:span}
  \end{center}
\end{figure} \\
以下に最大限に Scale を用いたときの実行速度の比較を示す。\\
{\scriptsize
\begin{itemize}
\item FPS とは Frame Per Second の略で、1秒間に何回画面を書き換えたかを表している。
\item 比較に使用したオブジェクトの総 Polygon 数は 19860、Texture は合計 10 枚 ( 512x384(2)
8x8(3)、616x123(4)、1024x768(1) )
\end{itemize}
}
\begin{table}[htb]
  \begin{center}
    \caption{Scale を用いることによる実行速度の比較}
    \hbox to\hsize{\hfil
      \begin{tabular}{c|l|l} \hline \hline
         & Scaleなし(FPS) & Scaleあり (FPS)\\ \hline
        \hline
        Mac OSX & 7.0 & 8.5\\ \hline
        PS3Linux (SPU 1) & 4.3 & 5.6 \\ \hline
        PS3Linux (SPU 6) & 10.8 & 13.5 \\ \hline
      \end{tabular}\hfil}
    \label{tb:scale}
  \end{center}
\end{table} 

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

SPU に特化したチューニングを行い、更なる速度の向上を目指す。

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

\bibitem{cell}Sony Corporation.

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

\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 , SPU を用いたプログラミング} \label{sec:cell}
Cell\cite{cell}は 1 基の PowerPC Processor Element (PPE) と 
8 基の Synergistic Processor Element (SPE)
からなる非対称なマルチコアプロセッサであり、高速リングバスで構成されている。

SPE は、LS (Local Store) という256KBのメモリを持つ。
本研究で用いた PS3Linux では、6個の SPE を制御することができる。

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

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

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

SPE が直接メインメモリにアクセスできないことと、DMA 転送の待ち時間が
SPE でプログラミングを行う際の大きな問題となる。問題の解決策として、
DMA の待ち時間の間にも DMA 転送を必要としないような処理を行い、パイプラインを組む
また、SPE を複数用いた並列処理で DMA の待ち時間を隠す方法がある。\\

Cell 用いたゲームプログラミングを行うために、我々の研究室では Cerium を用意した。
Cerium は、オブジェクトのデータやその振る舞い、
またはゲームのルールなどゲームを構成する場面 (Scene) を木構造で持つ
Scene Graph に代表される 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 をマッピングし描画する部分と3つに分けることが出来る。

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

\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.4]{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.4]{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}

現在、SPE に転送された Tile は SPE 上に 128 個まで保存される。
ハッシュを用いて、既に SPE に Tile が存在するかどうかを調べて、DMA 転送の無駄を省いている。\\

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

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.35]{image/Scale.pdf}
    \caption{縮小画像(Scale)}
    \label{fig:span}
  \end{center}
\end{figure} \\
以下に最大限に Scale を用いたときの実行速度の比較を示す。\\
\begin{table}[htb]
  \begin{center}
    \vskip -\lastskip \vskip -20pt
    \caption{Scale を用いることによる実行速度の比較}
    \hbox to\hsize{\hfil
      \begin{tabular}{c|l|l} \hline \hline
         & Scaleなし(FPS) & Scaleあり (FPS)\\ \hline
        \hline
        Mac OSX & 7.0 & 8.5\\ \hline
        PS3Linux (SPU 1) & 4.3 & 5.6 \\ \hline
        PS3Linux (SPU 6) & 10.8 & 13.5 \\ \hline
      \end{tabular}\hfil}
    \label{tb:scale}
  \end{center}
\end{table} 
{\scriptsize
\begin{itemize}
\item FPS とは Frame Per Second の略で、1秒間に何回画面を書き換えたかを表している。
\item 比較に使用したオブジェクトの総 Polygon 数は 19860、Texture は合計 10 枚 ( 512x384(2)
8x8(3)、616x123(4)、1024x768(1) )
\end{itemize}
}

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

現在、Polygon から Span の生成、描画の処理を SPE を用いて行っているが、
さらに SceneGraph から Polygon 生成の処理、SPE 上のコードの入れ替えを実装する。

また、評価をする際に、FPS だけではなく、特定の命令数などもっと細かいレベル
のデータを用いて検証を行う。

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

\bibitem{cell}Sony Corporation.

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

\bibitem{wataru} Wataru MIYAGUNI.

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

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