\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvips]{graphicx}

\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.eps}琉球大学主催 工学部情報工学科 卒業研究発表会}
\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{ソフトウェアRenderingEngineの高機能化と高速化}
\author{065725F 金城裕 {}{} 指導教員 : 河野真治}
\date{}
\maketitle
\thispagestyle{fancy}

\section{Cell上のソフトウェアレンダリング}

我々は、8SPU+2PPUのヘテロCPU構成を持つCell / PS3 上での
ソフトウェアレンダリングエンジン
を開発中である。これは、Cerium Task Manager 上に実装され、琉球大学情報工学科の
3年生の実験で使用中である。PS3 のGraphics Engine の仕様は公開されていない
ために、ソフトウェアレンダリングを
実装する必要がある。

ソフトウェアレンダリングは、SceneGraph、Polygon、Span、Z buffer の各段階があり、
それぞれの段階で、並列処理を行なう必要がある。現在は、Span の生成を1 SPU上で行ない、Z buffer を複数のSPU上で処理している。さらに、他の段階でも並列処理を
行なう必要がある。PPUよりもSPUの方が高速なので、1SPU 上で実行するだけでも
意味がある。

\vspace{-5mm}
\section{ヘテロジニアス・マルチコアプロセッサCell}
Cellは、1基の制御系プロセッサコア (PPE:PowerPc Processor ELement) と8基の演算系プロセッサコア (SPE:Synergistic Processor Element) で構成される。各プロセッサコアは、EIB (Element Interconnect Bus) と呼ばれる高速なバスで接続されている。また、EIBはメインメモリや外部入出力デバイスとも接続されていて、各プロセッサコアはEIBを経由してデータアクセスをおこなう。

この2種類のCPUをプログラマ自身が用途に合わせて適切に使い分けるように考慮する必要がある。

\vspace{0mm}
\begin{figure}[htbp]
  \begin{center}
    \includegraphics[scale=0.6]{pic/cell1.eps}
    \caption{Cellプロセッサの構成} \label{cell1}
  \end{center}
\end{figure}

\vspace{-6mm}
\section{Cerium}
当研究室ではCeriumと呼ばれるゲーム開発フレームワークがあり、以下の3つの要素から構成されている。\\

\vspace{-6mm}
\begin{itemize}
\item SceneGraph
\vspace{-3mm}
\item Rendering Engine
\vspace{-3mm}
\item Task Manager
\end{itemize}
 
Ceriumは独自にRenderingEngineを持つ。ゲーム中のオブジャクトの振る舞いやルールはSceneGraphで管理し、それらの動きやレンダリングの処理を動的にSPEに割り振るカーネルとして、TaskMnagerが用いられる。
TaskManagerは、Taskと呼ばれる、分割された各プログラムを管理する。Taskの単位はサブルーチンまたは関数とし、Task同士の依存関係を考慮しながら実行していく。
現在Ceriumはlinux,macosx上で動作し、コンパイル方法によってCellのspeを使うかどうかを選択できる。


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

\vspace{-6mm}
\subsection{光源}
RenderingEngineで、未実装だった光源の計算を実装した。各オブジェクトには自身の座標や親子関係などの情報を持っており、その中に法線がある。法線と光のベクトルとの内積をrgbにかけ算することにより光の計算を行っている。以下に光源の計算をした画像を示す。

\vspace{0mm}
\begin{figure}[htbp]
  \begin{center}
    \includegraphics[scale=0.4]{pic/ball.eps}
    \caption{光源計算をした描画画像} \label{ball}
  \end{center}
\end{figure}


%現在、光源はppeだけを使ったfifo形式のみに実装されている。

%\subsection{高速化}
%RenderingEngineの高速化に関して、以下のような案を提案する。
%\vspace{-3mm}
%\subsection{描画ルーチン}


%CeriumのRenderingEngineは描画する対象がない部分も毎フレーム描画計算をしている。それでは計算する必要のない部分も計算してしまい、無駄な時間が生じる。そこで、描画する対象がない部分の計算は行わないようにすれば高速化が望める。
%また画面に背景を描画する場合は、オブジェクトとは別に背景専用のルーチンを設け高速化を計る。さらにオブジャクトが重なり描画する必要のない部分は描画計算を行わない。

%\vspace{0mm}
%\begin{figure}[htbp]
%  \begin{center}
%    \includegraphics[scale=0.45]{pic/rendering1.eps}
%    \caption{描画計算の範囲} \label{rendering1}
%  \end{center}
%\end{figure}

\vspace{-7mm}
\subsection{SceneGraphからSpanを作るまで}
CeriumではSceneGraphからRenderingに至るまでに以下で示すような流れがある。\\
1.SceneGraphから、SPEのLSに収まるサイズのSceneGraphPackを生成する。\\
2.SceneGraphが持つ情報から、Polygonの座標を計算し、PolygonPackを生成する。\\
3.PolygonPackから、同じY座標を持つ線分の集合SpanPackを生成する。\\
4.Spanに対応する、描画に必要なTextureをSpanPackに付与する。\\
5.SpanPackとTextureをZ Bufferを用いて描画する\\

\vspace{0mm}
\begin{figure}[htbp]
  \begin{center}
    \includegraphics[scale=0.4]{pic/rendering2.eps}
    \caption{SceneGraphからRenderingするまでの流れ} \label{rendering2}
  \end{center}
\end{figure}

以上の工程でそれぞれSPEにTaskを渡し、処理を行っているが、Taskは一つにまとめられて一基のSPEで実行されている。%この部分のTaskを複数に分割、複数のSPEに割当て並列処理を行うことによって高速化を計る。

\section{現状とこれからの課題}
\subsection{TaskManagerの例題}
CeriumのTaskManagerの勉強としてTaskMangerを用いたWordCountを実装した。inputされたfileをmmapでメモリにマッピングし、そのdataを分割。各SPEに、WordCountのTaskと分割されたdataを渡す。SPEは渡されたdataをwordcountし、指定されたoutput領域に書き込む。全てのwordcountが実行し終えるとその結果をppe側で集計し、結果を出力する。
\subsection{Cell上での光源の実装}
RenderingEngineの機能として光源の計算を実装した。現在、光源はppeだけを使ったfifo形式のみに実装されているので、これからCellのspe上での実装をしなければならない。
%..... 光源をCell 
\subsection{各Rendering工程の並列化}
SceneGraphからSpanを生成するまでの各段階でTaskを分割、複数のSPEに割り振り並列に処理を行うように実装する。\\
・SceceGraph → Polgonの並列化\\
不要な場合もある\\
%↑ここよくわかってない。
・Polygon → Spanの並列化\\
ここで生成されたSpanは同じ X, Y 領域でまとめて、次のSPU taskに渡す必要がある。バラバラな領域のSpanを渡すと幾つかのTextureをSPEのLSへローディングしなければならず、DMA転送待ちが入ってしまう。

\subsection{Clipping}
%Zバッファ法？
描画対象のオブジャクトが重なり描画する必要のない部分が生じることがある。描画する必要のない部分を描画の早い段階で明確にし、描画対象から削除する必要がある。

%Clipping 完全に隠れたpolygonを早い段階で削除する

\subsection{背景の特別扱い}

%背景の特別扱い。どう特別扱いするのかな

背景は1 dot ずつ書くのではなく、特別扱いする

オブジェクトは1dotずつ計算し描画しているが、背景はあらかじめ予想できる描画領域である。

\subsection{描画対象がない空間の扱い}

CeriumのRenderingEngineは描画する対象がない部分も毎フレーム描画計算をしている。それでは計算する必要のない部分も計算してしまい、無駄な時間が生じる。そこで、描画する対象がない部分の判定を行い、zero clear DMAなどを用いて計算の手間を省く必要がある。

%zero clear DMA


%その流れを以下に示す。
%\vspace{0mm}
%\begin{figure}[htbp]
%  \begin{center}
%    \includegraphics[scale=0.3]{pic/wc_graf3.eps}
%    \caption{WordCountのTask生成、実行の流れ} \label{wordcount}
%  \end{center}
%\end{figure}


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

\bibitem{1} 宮國渡 "Implementation of Fine-grain Task Manager for Cell" 平成20年度 学位論文(修士)

\bibitem{2} 多賀野海人 "並列プログラミングを用いたゲームフレームワークの設計と実装" 2008年 卒業研究中間報告資料

\bibitem{3} fixstars:
http://cell.fixstars.com/ps3linux/index.php/メインページ

\bibitem{4} OpenCL:
http://www.khronos.org/opencl/

\end{thebibliography}
\end{document}