view paper/early.tex @ 2:bd91d56ca33a

chapter 3 finish.
author koba <koba@cr.ie.u-ryukyu.ac.jp>
date Tue, 01 Feb 2011 18:33:29 +0900
parents d557035f6f61
children 398e732edfb6
line wrap: on
line source

\chapter{先行研究} \label{chapter:early}
ここでは先行研究である Game Framework Cerium、および同じ並列プログラミングの
フレームワークである OpenCL について説明する。

\section{Game Framework Cerium}\label{sec:cerium}
Game Framework Cerium は我々が提案したゲーム開発フレームワークで、独自に
Rendering Engine を持つ。ゲーム中のオブジェクトの振る舞いやルールは 
SceneGraph で管理し、それらの動きやレンダリングの処理を動的に SPE に割り振る
カーネルとして Task Manager が用いられる。Cerium は C++ で実装されており、
画像の読み込みや入力デバイスは SDL を用いて行っている。

\section{Task Manager}\label{sec:taskmanager}
Task Manager は、Task と呼ばれる分割された各プログラムを管理する。Task の
単位はサブルーチンまたは関数とし、Task 同士の依存関係を考慮しながら実行していく。

\section{Task Manager の API}

\section{SceneGraph}\label{sec:scenegraph}
ゲーム中の一つの場面(Scene)を構成するオブジェクトやその振る舞いを格納したノードの
集合を SceneGraph とする。SceneGraph のノードは親子関係を持つ tree で
構成される。(図\ref{fig:sgtree})親子関係とは、親オブジェクトの回転や平行移動などの
行列計算による頂点座標の変更が、子オブジェクトにも反映する関係のことである。
これは子に対してスタックに積まれた親の変換行列を掛けることで実現できる。

SceneGraph のノードは以下のようなデータを持つ。

\begin{enumerate}
\item Vertex: ポリゴンオブジェクトの頂点座標
\item Texture: ポリゴンオブジェクトのテクスチャ座標
\item TextureImage: テクスチャイメージ
\item TransMatrix: ポリゴンオブジェクトの変換行列
\item Coordinates: オブジェクトの座標
\item Angle: オブジェクトの角度
\end{enumerate}

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.6]{images/sgtree.pdf}
\end{center}
\caption{SceneGraph Tree}
\label{fig:sgtree}
\end{figure}

\section{Rendering Engine}\label{sec:rendering}
Cerium の Rendering Engine は主に以下の 3 つの Task を持つ。

\begin{itemize}
\item CreatePolygonFromSceneGraph: SceneGraph が持つ Polygon の座標から、実際に画面に表示する座標の計算を行い、
  PolygonPack(\ref{sec:renddata}節) を生成する Task
\item CreateSpan: PolygonPack から同じ Y 座標を持つ線分の集合である SpanPack(\ref{sec:renddata}節) を生成する Task
\item DrawSpan: SpanPack を Texture を読み込みながら Z Buffer を用いて描画する Task
\end{itemize}

Rendering Engine では、SceneGraph から、実際に表示するポリゴンを抽出、
ポリゴンから Span の生成、Span に RGB をマッピングし描画する部分と 
3 つに分けることができる。
ここでいう Span とは、ポリゴンに対するある特定の Y 座標に関するデータを
抜き出したものである。(図\ref{fig:span})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{images/span.pdf}
\end{center}
\caption{Span}
\label{fig:span}
\end{figure}

\subsection{Rendering で使うデータ構造}\label{sec:renddata}
レンダリング処理は SPE で行う事を前提とし、それに合わせたデータ構造を
採用している。

\subsubsection*{PolygonPack}
PolygonPack は SceneGraph から抽出されたポリゴンの集合である。
光源やテクスチャ、頂点の座標から構成される。

\subsubsection*{SpanPack}
SpanPack はポリゴンから抽出された Span の集合である。
Span はその座標と、対応するテクスチャの座標を持つ。(図\ref{fig:spack})

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{images/spack.pdf}
\end{center}
\caption{Span 構造}
\label{fig:spack}
\end{figure}

\section{OpenCL}
OpenCL(Open Computing Language) とは、マルチコア CPU や GPU、その他の
プロセッサによる、ヘテロジニアスコンピューティングのフレームワークである。
OpenCL C プログラミング言語は ISO/IEC 9899:1999(C99) 規格をベースとしている。
 OpenCL のプラットフォームモデルは図 \ref{fig:opencl} のようになり、一つの 
Host と複数の OpenCL Device で構成されている。OpenCL devices の中では Compute 
Units(CUs) として分割され、その中でさらに Processing Elements(PEs) として
分割される。

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{images/opencl.pdf}
\end{center}
\caption{OpenCL Platform}
\label{fig:opencl}
\end{figure}

OpenCL アプリケーションでは、実行する処理コマンドが Host から PEs へ送られる。
PEs では SIMD(Single Instruction Multiple Data)もしくは SPMD(Single Program 
Multiple Data) で実行される。

OpenCL devices や Host には kernel があり、Host kernel では OpenCL devices 
context や実行コマンドの処理を行う。Host は OpenCL devices での kernel の
実行を調整するために、 command-queue を生成し、context へ渡す。
command-queue には 以下のコマンドがある。

\begin{itemize}
\item Kernel execution commands\\
  実行コマンド queue
\item Memory commands\\
  データの送受信に関する情報(Host アドレス空間)
\item Synchronization commands\\
  commannd の依存や同期等に関する情報
\end{itemize}

また、OpenCL Device は 4 つの違うメモリ領域 (Global Memory, Constant Memory, 
Local Memory, Private Memory) を持ち、それぞれ Host や CUs、PEs からの
アクセス権限が異なる(アドレス空間が異なる)。

プログラミングモデルとしては、データ並列、タスク並列をサポートしている。
OpenCL は Host や各 device に kernel があることや、device 毎にメモリアドレス
空間が違う、プログラミングモデル等、TaskManager とよく似ている。

OpenCL は汎用的な実装となっているため、例えば Task のメモリアクセス API も
複雑な記述となっている。対して Task Manager は、現在 Cell 環境に重きを
置いているため、メモリアクセスは DMA に対応した記述が行われる。DMA では
明示的にアドレスを指定することになるので、OpenCL よりも簡潔な記述が可能と
なっている。このことから、Task Manager は OpenCL の軽めな実装の一つという
捉え方もできる。

OpenCL に対して Task Manager が優れている点は、Mac OSX や Linux、Cell といった
複数の環境で動作する事による信頼性の確保のしやすさにある。Task Manager では、
Task 毎に実行する CPU を選択できるため、動作環境が変わっても大幅なコードの
変更が必要なく、Single Core プログラムとして動作させることができる。
これにより、 Task 単体やそれらを繋げたプログラム全体を逐次型プログラムとみなし、
二分法などのデバッグ手法を用いる事ができる。このことは図\ref{fig:devstep} 
のような段階に沿って開発が可能になることに繋がる。