\chapter{OSMesa}
PlayStaiton3では以前我々が扱っていたPlay Station2と違ってGPUに直接アクセスすることができない。しかし、ps3fbは扱うことができる。そこで我々は描画にSDLおよびOpenGLを用いて開発を行うことにした。SDLのfbcon driverにはOpenGLがないため、CPUはそれなりに早いが、グラフィックス性能はフレームバッファしかないという環境でよく用いられるOSMesaを使用し、移植開発を行った。
PPUのみで動作するOSMesaとSDLを用いて作ったSuper Dandy(s-dandy)はある程度のスピードでうごくが、そのスピードでは不十分である。そこでOSMesaを今回の実験材料として用い、OSMesaの一部の機能をSPUを使用して高速化を行った。
\section{OSMesaの機能}
\subsection{ポリゴンの回転・拡大・縮小}
まず最初にOSMesaはポリゴンと呼ばれる三角形の各頂点座標を入力値として利用している。図\ref{fig:texture}の左の図がポリゴンに相当する物となる。ポリゴンの頂点座標から次の動作の命令を汲み取った上で、動作に伴う行列演算を行う。
\subsection{spanの生成}
動作に伴う演算から得られたポリゴン情報はいったんspanという構造体に変換される。
図\ref{fig:texture}で線が引かれている部分がspanである。ポリゴン情報からy座標別に情報を分割し、図\ref{fig:texture}ではy=15のところのspanを示している。左端の点のx、y、z座標とRGB$\alpha$、右端のx、zとRGB$\alpha$から構成される。
\subsection{テクスチャの生成とマッピング}
テクスチャの読み込みはSDL\_imageを利用して行う。IMG\_Loadという関数でテクスチャの情報をメモリに格納し、そのテクスチャのx、yをO~1で扱う。図\ref{fig:texture}ではy=15のラインで、左端がテクスチャの値を(0.3,0.5)、右端が(0.5,0.7)という値で保持している。それは右のテクスチャの線が引かれた部分に相当する。つまり、y=15のラインはテクスチャの線の部分がマッピングされることになる。
\subsection{zバッファ}
OSMesaは描画を行う際、zバッファというメモリ領域を確保している。zバッファは描画する画面の大きさのメモリ空間を持ち、それぞれのx、y座標に対応するzの値を保持している。そのx、y座標が描画する際、zバッファにzの値を書き込んでおく。そうすると、今度同じx、y座標に描画する際、zの値をみてカメラに向かって、今書き込むもうとしているものがもとあるものより、手前にあるのか、おくにあるのかを判断する。手前にある場合はzバッファを更新するとともにそのx、y座標のRGB$\alpha$も更新し、おくにある場合はなにもしない。そうすることにより3Dをうまく表示している。

%OSMesaはポリゴンと呼ばれる三角形の各頂点座標からy座標ごとにspanと呼ばれる構造体を生成し、そのspanのZの値をみながらいったんメモリに書き出し、それをまとめてframe bufferに書き出す。\\
%テクスチャを使用する場合は、各頂点に対応したテクスチャ座標を持っており、その値からテクスチャのどのxy座標のRGBがその点に対応するかを計算してRGBを書き込むようなシステムになっている。図\ref{fig:texture}では左にポリゴンが書かれており、各頂点にはxyz座標とテクスチャに対応する相対比がある。その相対比からテクスチャのどの部分がポリゴンに対応しているかがわかる。それによりテクスチャの黒い線が左のポリゴン上の1行の線にマッピングされる。
\begin{figure}[htb]
\begin{center}
\includegraphics[width=17cm]{./fig/texture2.eps}
\end{center}
\caption{ポリゴンとテクスチャ}
\label{fig:texture}
\end{figure}
%\subsection{ダブルバッファリング}
%ダブルバッファリングとは1画面が描画している間に次に描画する画像を裏でいったん生成しておき、描画する画像を切り替える手法である。画面を一気に切り替えるため、ちらつきがなくなる。
\section{高速化する部分}
OSMesaの機能を分割し、SPUにTaskとして割り振る方法はいくつか考えることができる。我々は最初テクスチャのついてないオブジェクトを対象とし、spanをzバッファでみながら描画していく方法を高速化した。高速化する部分のコードは以下のようになっている。\\
\input{src/render_span_macro.c}
最初の３行が実際のコードに記述された物になる。しかし、OSMesaはマクロを多用して実装されている。このマクロを展開したコードをいかに示す。
\input{src/render_span.c}
コードを説明する前にコードで用いられているspanについて先に説明しておく。spanとは次のような構成からなっている。\\
\begin{table}[htb]
\begin{center}
\begin{tabular}{|c|l|}
\hline
x、y、z & 生成されるspanの左端のx、y、z座標 \\ \hline
red、green、blue、alpha & 生成されるspanの左端のRGB$\alpha$情報 \\ \hline
end & 生成されるspanの長さ \\
& (x、y)からこの長さの分だけ描画される\\ \hline
zStep  & 生成されるspanのxが1増加したときの\\
&zの増加量 \\ \hline
redStep,greenStep,blueStep,alphaStep & 生成されるspanのxが1増加したときの\\
&RGB$\alpha$の増加量 \\ \hline
\end{tabular}
\caption{SPANの情報}
\label{table:span}
\end{center}
\end{table}

\begin{figure}[htb]
\begin{center}
\includegraphics{./fig/span_data.eps}
\end{center}
\caption{span data}
\label{fig:span_data}
\end{figure}
図\ref{fig:span_data}で、spanの構造体を表している。同じy座標に対しての描画する一番左端のx、y、z座標とその位置に対するRGB$\alpha$が与えられ、その位置から描画される長さ(end)、xが1増加したときの各情報の増加量がこのコードに達するまでに計算されてきた。\\
つまりこのコードでは、まず与えられたspanのx、y座標からzバッファのアドレ
スを計算する。次にそのx、y座標からzが計算され今まで計算されてきたzとの比
較を行う。この比較によって今まで与えられたポリゴン情報と今与えられたポリ
ゴン情報のどちらがカメラからみて手前にあるかを計算する。もし、対応する
spanが手前にある場合はそのx、y座標にRGB$\alpha$を更新し、zバッファを更新
しておく。こうすることにより、今までのspanからどれが一番手前の情報化を保
持しておく。その後で、x座標を1ずらす際にRGB$\alpha$とzの更新が行われる。
それをend(長さ）分繰り返しておく。それが1画面分終了したら、描画にうつる。



\section{実装}
zバッファは1ピクセルのx座標、y座標に対してのz情報である。それを各SPUで大
量(現在の日本のテレビ規格だと1920×1080)に持つと、
$1920\times1080\times4=8294400$byteのメモリ量が必要となりモリが不足する。また、同じx座標、y座標のzバッファに対し、別のSPUで処理すると、同じ1ピクセルを別のSPUが描画することになるため、単純に分割することはできない。\\
そこで我々はspanを生成し、描画するルーチンからy座標ごとにspanをソートして持っておく。各SPUには、y座標が一致しているspanが送信される。y座標が一致しているspanが複数のSPUに対して送信されることはない。\\
例えば、同じy座標のspanが複数のポリゴンから生成されたとする。そのspanはすべて同じリストに追加される。y座標毎にspanのリストを一定数とり、そのリストを更にDMA量にあわせてリスト化する。ここではy座標ごとのspanのリストをspanlistとする。\\
そうすることにより、各SPUは1ライン分のフレームバッファだけを持つだけでよ
く、メモリの問題も解決する。まず最初に高速化するルーチンのところにきた
span情報をy座標ごとに生成する。(図\ref{fig:y_list})\\
\begin{figure}[htb]
\begin{center}
\includegraphics[height=5cm]{./fig/y_list.eps}
\end{center}
\caption{spanlist}
\label{fig:y_list}
\end{figure}
しかし、y座標ごとに生成されたspanを使用するSPUの数に単純に分割するだけではあまり効率が良くない。そこで、y座標ごとに生成されたspanのリストを更にまとめたうえで、リスト化する。ここでは64個のy座標ごとのspanのリストをまとめている。それをSPUの数分つくり、図\ref{fig:span_list}のようなリストにする。ここではSPUが受け取る最初のリストをspanpacklistと呼ぶことにする。ここで64個のy座標ごとのリストを作るのはアドレスの転送回数を減らすことにある。\\
\begin{figure}[htb]
\begin{center}
\includegraphics[height=7cm]{./fig/span_list.eps}
\end{center}
\caption{spanpacklist}
\label{fig:span_list}
\end{figure}
そこからy座標ごとのspanのリストをDMAでとってくる。SPUが実際に持つspanは同じy座標のみで、zバッファは1行分だけでよい。
\subsection{ダブルバッファリング}
spanを生成して、描画している間にもPPUは動くことができる。今回の実装ではダブルバッファを用いている。つまり、PPUではSPUが描画している間、次のSpanを生成し、SPUに送るSpanのリストを作っている。SPUも同時にspanを読み込むときにダブルバッファで読み込んでいる。(図\ref{fig:parallel})\\
\begin{figure}[htb]
\begin{center}
\includegraphics{./fig/parallel.eps}
\end{center}
\caption{parallel}
\label{fig:parallel}
\end{figure}
そうすることにより、PPUとSPUが効率よく使われ更なる高速化が得られている。
\subsection{パイプライン}
CellはDMAの機能を持っているので、パイプライン的な処理が可能となる。基本的な要素
としてRead、Exec、Writeから構成できる。(図\ref{fig:pipeline})\\
\begin{figure}[htb]
\begin{center}
\includegraphics{./fig/pipeline.eps}
\end{center}
\caption{pipeline実行}
\label{fig:pipeline}
\end{figure}
\subsection{SPUプログラム}
spanpacklistとダブルバッファを用いてSPUのプログラムを記述すると以下のようになる。
\input{src/spe_main.c}

ほとんどの部分がダブルバッファのDMA制御を行っている。計算を行っている部分はPPUのみで行われていたコードにDMAのダブルバッファを考慮したものである。
\input{src/calc.c}
ダブルバッファは入力用の構造体を二つ、出力用の構造体二つで構成されている。
\section{評価}
\subsection{実行速度比較}
単純にSDLとOSMesaを用いたものとSPUを使ったOSMesaを使用したものとを比較した。例題としてはSDLに付属しているtestglというCubeが回転しているテクスチャがはられていないものを利用した。実行時間はSDLに標準で出ろくされるFPSを用いる。FPSは１秒間に何枚の画像が表示されているかを表す物である。計測結果は以下のようになる(表\ref{table:exectime})。これはCellの上ではやはりSPUをなるべく使った方が実行速度ははやくなるということを示していると同時によりOSMesaを細分化し、できるだけSPUをつかうよな設計をすると、よりはやくなる可能性を示す物であった。OSMesaがメジャーアップデートされると、それにOSMesaの最適化が加わり、更に1.8倍早くなった。
\begin{table}[htb]
\begin{center}
\begin{tabular}{|l|c|}
\hline
SDL(1.2)+OSMesa(6.5.2) & 18FPS \\ \hline
SDL(1.2)+OSMesa(6.5.2) with SPU & 24FPS \\ \hline
SDL(1.2.13)+OSMesa(7.0.2) with SPU & 43FPS \\ \hline
\end{tabular}
\end{center}
\caption{OSMesaの実行時間比較}
\label{table:exectime}
\end{table}
\subsection{総合評価}
実行速度比較から高速化には成功したが、巨大なマクロによるプログラム記述やコピーの多用、巨大な構造体などがあり、遅くなっている要因がわかった。さらに高速化を行うためにはテクスチャの計算などを並列に行う必要があった。しかし、テクスチャ処理がメインメモリ依存で記述されているため、拡張がとても難しく、OSMesaは時代遅れなライブラリ群といえる。また、OSMesaの機能などをSPUに分割すると、OSMesaよりもわかりやすいという教育効果を得ることができる。