|
14
|
1 \documentclass[techrep]{ipsjpapers}
\usepackage{graphicx}
% 巻数，号数などの設定
\setcounter{年数}{2011}
% ユーザが定義したマクロなど．
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)\nobreak}
\def\>{\nobreak\(\rangle\)}
\def\|{\verb|}
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\LATEX{\iLATEX\Large}
\def\LATEx{\iLATEX\normalsize}
\def\LATex{\iLATEX\small}
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
\def\Quote{\list{}{}\item[]}
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
$\backslash$#1\fi}
%\checklines % 行送りを確認する時に使用
\begin{document}%{
% 和文表題
\title[学生用 PS3 GameFrameWork Cerium での Pipeline ストールの検出]%
{学生用 PS3 GameFrameWork Cerium での\\Pipeline ストールの検出}
% 英文表題
\etitle{Detecting pipeline stall on PS3 GameFrameWork Cerium}
% 所属ラベル
\affilabel{UNI}{琉球大学 理工学研究科 情報工学専攻 並列信頼研究室\\
Concurrency Reliance Laboratory, Information Engineering Course,
Faculty of Engineering Graduate School of Engineering and Science,
University of the Ryukyus.}
% 和文著者名
\author{小林 佑亮\affiref{UNI}\and
河野 真治\affiref{UNI}\and
多賀野 海人\affiref{UNI}\and
金城 裕\affiref{UNI}}
% 英文著者名
\eauthor{Yusuke Kobayashi\affiref{UNI}\and
Shinji Kono\affiref{UNI}\and
Kaito Tagano\affiref{UNI}\and
Yutaka Kinjo\affiref{UNI}}
% 和文概要
\begin{abstract}
我々は PlayStation3 上でのゲームプログラミングをサポートする Cerium Engine を開発した。
Cerium におけるゲーム開発ではオブジェクトの描画や動作を Task という単位で管理しており、
この Task を SPE に送り、Pipeline で実行することによってプログラムの並列化を図っている。
この Pipeline におけるストールによって実行速度の低下が発生することが分かっている。
本研究ではこのストールを検出することを考える。
\end{abstract}
% 英文概要
\begin{eabstract}
We developed Cerium Engine which support Game Programming on PlayStation3.
Cerium managed drawing objects and movement in unit called Task.
By sending SPE a Task and executing on pipeline,we attempt parallelize program.
Stalling of this pipeline reduce execution speed.
Ins this paper, we detect this stall.
\end{eabstract}
% 表題
\maketitle
\newpage
% 本文
\section{はじめに}
当研究室ではこれまで家庭用ゲーム機上でのゲームプログラミングの開発を行ってきた。
過去には PlayStation や PlayStation2、GameBoyAdvance を用いており、
現在は PlayStation3(以下 PS3) で 動作するゲーム開発を行っている。
PS3 では Fedora や Yellow Dog Linux といった Linux O を動作させることができるので
(現在の公式のサポートは終了している)C や C++ といったプログラム言語を用いて
Linux 上でプログラミングすることが可能となっている。しかし、PS3 の Architecture である
CellBroadbandEngine は複数の SPE を使用する並列プログラミングが求められている。
そこで我々は Cell のような ManyCoreArchitecture を用いた、並列プログラムの開発を
サポートするフレームワークとして FineGrainTaskManager を開発した。
この TaskManager を用いたゲーム開発フレームワークが Cerium である。
Cerium を用いたゲーム開発ではプログラムの動作を Task という単位で管理し、
この Task と必要なデータを複数の SPE に転送して処理させる。
転送された各 TASK は並列に処理され、Pipeline で実行される。
本研究では Cerium に対して様々なテストを行い、
Cerium の チューニングやゲームプログラミングを補助するテスト手法を提案する。
% }{
\section{Cell Broadband Engine}\label{sec:Cell}
CellBroadbandEngine は SCEI と IBM、東芝によって開発された CPU である。
2 thread の PPE(PowerPC Processor Element)と
8個の SPE(Synergistic Processor Element)からなる非対称なマルチコアプロセッサであり、
高速リングバスであるEIB(Element Interface Bus)で構成されている。
PS3 Linux では6個の SPE を使うことが出来る。(図\ref{fig:cell})
\subsection{PPE(PowerPC Processor Element)}\label{ssec:PPE}
PPE は Cell Broadband Engine のメインプロセッサで、
複数の SPE をコアプロセッサとして使用することができる汎用プロセッサである。
メインメモリや外部デバイスへの入出力、SPE を制御する役割を担っている。
PPU(PowerPC Processor Unit)は、PPEの演算処理を行うユニットで、
PowerPC アーキテクチャをベースとした命令セットを持つ。
PPSS(PowerPC Processor Storage Subsystem)は PPU からメインメモリへのデータアクセスを
制御するユニットである。
\subsection{SPE(Synergistic Processor Element)}\label{ssec:SPE}
SPE には 256KB の Local Store(LS)と呼ばれる直接参照できるメモリ領域があり、
バスに負担をかける事なく並列に計算を進めることが出来る。
SPE からメインメモリへは、直接アクセスすることは出来ず、SPE を構成する一つである
MFC (Memory Flow Controller)へ、チャネルを介してDMA(Direct Memory Access)命令を送ることで行われる。
\begin{figure}[tb]
\begin{center}
\includegraphics[scale=0.7]{figure/cell.eps}
\end{center}
\caption{Cell Broadband Engine}
\label{fig:cell}
\end{figure}
\section{Cerium Engine}
Cerium は 独自の Rendering Engine と Scene Graph、Task Manager の3つによって構成される。
ゲーム中のオブジェクトの振る舞いやルール、Polygon Data は SceneGraph によって管理され、
それらの動きや Rendering の処理を動的に SPE に割り振るカーネルとして TaskManager が用いられる。
Cerium は C++ で実装されており、画像の読み込みや入力デバイスはSDL\footnote[1]{
Simple DirectMedia Layer。グラフィックやサウンドなどの API を提供するフリーのライブラリ。
} を用いて行っている。
\subsection{Scene Graph}
Cerium ではゲーム中の一つの場面(Scene)を構成するオブジェクトの頂点座標やテクスチャー、
そしてその振る舞いの集合を SceneGraph としている。
SceneGraph のノードは親子関係を持つ tree で構成される。親子関係とは、親オブジェクトの回転や
並列移動等の行列計算による頂点座標の変更が、子オブジェクトにも反映する関係のことである。
これは子に対してスタックに積まれた親の変換行列を掛けることで実現できる。(図\ref{sg})
\subsection{Task Manager}
Task Manager は Task と呼ばれる、分割された各プログラムを管理する。
Task の単位はサブルーチンまたは関数とする。
Task は主に PPE 内で生成され、処理する内容と必要なデータを設定する。
実行可能になった Task から各 SPE 割り当てられ、Task を受け取った SPE はその情報を元に
処理を実行する。
\subsection{Rendering Engine}\label{ssec:rendering}
現在、PlayStation3 の GPU にアクセスする API が公開されていないため、
Cerium の Rendering Engine では、オブジェクトの描画を Cell で並列処理している。
描画処理を段階別に以下の3種類の Task に分けている。
\begin{itemize*}
\item
SceneGraph が持つ Polygon の座標から、実際に画面に表示する座標の計算を行い、
それを格納した PolyPack を生成する SceneGraph2PolygonPack Task
\item
PolygonPack から同じ Y 座標を持つ線分の集合である SpanPack を生成する
PolygonPack2SpanPack Task
\item
SpanPack を Texture を読み込みながら Z Buffer を用いて描画する DrawSpan Task
\end{itemize*}
この3つの Task に依存関係を持たせ、順番に SPE に送ることにより画面の描画を実現している。
\begin{figure}[tb]
\begin{center}
\includegraphics[width=5cm]{figure/scenegraph.eps}
\end{center}
\caption{Scene Graph Tree}
\label{fig:sg}
\end{figure}
\newpage
\section{Cerium の Task}
\subsection{Task ID}
Task ID とは、各 Task に割り振られたグローバル ID である。通常の逐次型プログラムでは
Task を選択して実行する場合、その関数ポインタを指定して実行すればいい。
しかし Cell の場合、PPE と SPE 上ではアドレス空間が異なるため、SPE 上で実行される
Task を PPE から直接アドレス指定することはできない。そこで、Task 毎に ID を割り振り、
その ID から、SPE 上にある Task が格納された配列を参照して実行する。
\subsection{Task で入出力されるデータ}\label{ssec:inout}
Task に渡すデータとして、{\bf add\_inData}と{\bf add\_param}がある。
{\bf add\_inDara(addr, size)}は、Task に渡すデータのアドレスと、そのデータの
サイズを引数として入力する。このデータは DMA 命令により転送される。
{\bf add\_param(param)}は、Task に32 bit のデータを渡す。param はアドレスとして
ではなく、値を Task オブジェクトが直接持っているので DMA 命令による転送は行わない。
\subsection{Task 間の共用領域}
各 Task は独立して動作するため、使用するメモリ領域も他の Task と干渉することは無い。
しかし、処理によっては Task 間で同じデータを使用する場合がある。
その場合、Task 毎に同じデータを持つよりも、LS 上に一つロードしてそのデータを
各 Task が参照することが望ましい。
共用領域を allocate するには、{\bf global\_alloc(int id, int size)}を使う。id は
allocate した領域に割り振る番号で、size が allocate するバイト数を表す。
allocate した領域のアドレスは{\bf glbal\_get(int id)}で、global\_alloc() 時に
指定した id を渡すことで取得できる。 global\_alloc() した領域は、TaskManager 側で
解放することな無いのでユーザが{\bf global\_free(int id)}を実行する必要がある。
共用領域は各 SPE 上に置かれるので、違う SPE の領域を参照することはできない。
\subsection{Task の Dependency}\label{ssec:dependency}
Task に依存関係(Dependency)を持たせるには{\bf wait\_for}を使用する。
\setbox0\vbox{
\hbox{//task2 は task1 が終了してから開始する}
\hbox{task2\|->|wait\_for(task1);}
}\fbox{\box0}
\label{fig:single}
上記の場合には task1 は Active Queue へ、task2 は Wait Queue へ格納される。
Active Queue に格納された Task は各 SPE に送られ処理される。
終了した Task から PPE の Task Manager へタスク終了のコマンドを発行する。
コマンドを受け取った Task Manager は Wait Queue を調べ、依存関係を満たした Task から
Active Queue に移し、SPE へ送る。(図\ref{fig:dependency})
\begin{figure}[tb]
\begin{center}
\includegraphics[scale=0.45]{figure/dependency.eps}
\end{center}
\caption{Task の Dependency}
\label{fig:dependency}
\end{figure}
\subsection{Task 終了時に実行される関数}\label{ssec:set_post}
{\bf set\_post}を使うことでTask が終了した際に PPE で実行される関数と、
その引数を指定できる。
{\bf set\_post}により、ユーザ側でも Task が終了したということを検知できる。
また、大量の Task に依存関係を設定する場合、一度に {bf create\_task}で生成し、
{\bf wait\_for}で繋げるというのは難しい。その場合、ある一定数の Task だけ
生成しておき、{\bf set\_post}を使って終了したことを確認して、その中で新たに
Task を生成していくという方法により依存関係を設定することができる。(図\ref{fig:set_post})
\begin{figure}[tb]
\setbox0\vbox{
\hbox{int data = 3;}
\hbox{task\|->|set\_post(func1, (void*)data);}
\hbox{}
\hbox{void}
\hbox{func1(void *data)}
\hbox{\|{|}
\hbox{\ \ printf\|("func1: data = %d\n", (int)data)|;}
\hbox{\|}|}
\hbox{//実行結果}
\hbox{func1: data = 3}
}\fbox{\box0}
\caption{set\_post による関数の設定}
\label{fig:set_post}
\end{figure}
\section{Super Dandy}
{\bf SuperDandy}は当研究室が PlayStation でのゲーム開発を行っていた時期に
開発されたシューティングゲームである。{\bf SuperDandy}は開発する環境が変わる度に
移植されており、過去には PlayStation2、MacOSX 用も作られた。今回、新たに
MacOSX バージョンをベースとして Cerium で動作するバージョンを作成した。
SuperDandyが伝統的に移植されてきた背景には、ある程度のボリュームのあるゲームであること、
動作結果を過去の環境と比較することで新たな環境のチューニングが行えることが挙げられる。
\subsection{Super Dandy の Cerium への移植}
Cerium ではオブジェクトの管理は SceneGraph を用いて行っているが、
Super Dandy は独自にオブジェクトの管理を行なっている。また PutSprite という
描画用の関数が存在する。この関数は
OpenGL\footnote[2]{
2D, 3D オブジェクトの描画の為のプログラムインターフェース
}
を使用しており、XY座標、テクスチャの指定を行うことによってオブジェクトの描画を
行うことができる。また、PutSprite の他にオブジェクトの拡大縮小が可能な PutSpriteEx
が存在する。Super Dandy を Cerium へ移植する場合には、この PutSprite, PutSpriteEx
と同名の関数を用意し、その中で SceneGraph tree への登録を行うことで Cerium 上への
移植に成功した。また、この方法で移植することによってSuper Dandy 内で設定された
細かなパラメータを再利用でき、旧バージョンとの比較によって Cerium の機能の洗い出しを
することができる。具体的にはテクスチャの表示のズレ、光源処理のチューニングなどである。
また、元の PutSprite,PutSpriteEX を使うことにより旧バージョンを動かすことができる。
これにより異なる環境での動作の確認が容易に行える。
\subsection{Super Dandy on PlayStation3}
Super Dandy を Task 化して PlayStation3 上で動かす場合、Cell Broadband Architecture
を意識する必要がある。Super Dandy は move(動作)やcollision(衝突判定)を関数ポインタ
で持っているが、それを Task 化して並列で動かす場合、PPE と SPE のメモリ領域は
異なるので関数ポインタのアドレスは使用できない。Cerium では Task を ID で管理しているので
それを使用して move や collision を行うのが望ましい。
Super Dandy を始め、ゲームには相互に干渉するパラメータが多数存在する。
共通のパラメータを必要とする Task 群を global\_alloc を使用して同じ Task 内で
処理させたり、Task 同士に依存関係を持たせる事が必要となる。
しかし、Task に複雑な依存関係を持たせると、Pipeline 処理がストールしてしまう原因となる。
\section{Pipeline のストール}
例えばある Task の処理を複数の Task が待つような dependency が設定されていたとき、
まだ処理していない Task があるにもかかわらず、動作していない SPE が発生してしまう。(図\ref{fig:stall})
これにより Task 処理の並列度が低下し、全体的なパフォーマンスの低下に繋がる。
Cerium で実行される各 Task は Pipeline 状に処理することによって全ての SPE を
常に busy 状態することにより、並列度を維持することが望ましい。(図\ref{fig:pipeline})
そこで Pipeline 上のストールを検出し、並列度の低い箇所を発見するテスト機構を実装した。
\begin{figure}[tb]
\begin{center}
\includegraphics[scale=0.6]{figure/stall.eps}
\end{center}
\caption{dependency によるストール}
\label{fig:stall}
\end{figure}
\begin{figure}[tb]
\begin{center}
\includegraphics[scale=0.5]{figure/pipeline.eps}
\end{center}
\caption{各 SPE による Task の Pipeline 実行}
\label{fig:pipeline}
\end{figure}
\subsection{Pipeline ストールの検出}
依存関係を解決していない Task がキューに積まれ、
かつ SPE の稼働率が低い場合、Pipeline ストールが起きている可能性がある。
そこで waitTaskQueue から activeTaskQueue へ Task が移動したときの
SPE の稼働率を調べることで Pipeline ストールを検出することにした。
また、その時の activeTaskQueue の長さと格納されている Task ID を
表示し、どの Task がどれくらい積まれているかを調べた。
\subsection{ball\_bound}
ball\_bound は 3D のボールが画面内で跳ねる初歩的なプログラムである。
このボールの描画には Cerium の機能の一つである Rendering Engine が使われている。
\begin{figure}[tb]
\setbox0\vbox{
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = StartTask ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = CreatePolygonFromSceneGraph ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 6 }
\hbox{task\_name = CreateSpan ,task\_name = CreateSpan ,task\_name = CreateSpan ,}
\hbox{task\_name = CreateSpan ,task\_name = CreateSpan ,task\_name = CreateSpan ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = StartTask ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 1 }
\hbox{task\_name = CreatePolygonFromSceneGraph ,}
\hbox{spu\_idle! spe\_running = 0 : activeTaskQueue\|->|length = 6}
\hbox{...}
}\fbox{\box0}
\caption{実行結果}
\label{fig:result}
\end{figure}
図\ref{fig:result}を見ると3種類の Task が表示されているのが分かる。
{\bf StartTask }は全ての Task の一番初めに実行される Task でループの同期をしている。
{\bf CreatePolygonFromSceneGraph}と{\bf CreateSpan}は\ref{ssec:rendering}節で述べたように
Rendering Engine の Task である。Rendering Engine では
SceneGraph\|->|PolygonPack\|->|SpanPack\|->|DrawSpan
といったように段階的にオブジェクトを処理するため、依存関係が存在していた。
実行結果より CreatePolygonFromSceneGraph と CreateSpan には図\ref{fig:barrier}のような
バリア同期の関係が見られ、これが並列度を下げていることが分かる。
しかしここでは DrawSpan が表示されていない。
DrawSpan は\ref{ssec:set_post}にあるset\_postによってバリア同期されている Task である。
set\_post によって格納された関数は Task の関数ポインタとして登録されているので
これを調べて表示させてやればよい。
\begin{figure}[tb]
\begin{center}
\includegraphics[scale=0.5]{figure/barrier.eps}
\end{center}
\caption{CreatePolygonFromSceneGraph と CreateSpan の依存関係}
\label{fig:barrier}
\end{figure}
\section{まとめ}
activeTaskQueue に格納された Task と SPE の稼働率により、並列度の低い箇所を
知ることができた。しかし、この方法だけでは局所的な情報だけであり
Task がどのように展開されているのか、どの程度並列度が落ちているのかまではわからない。
登録された Task には set\_post や wait\_for で設定された依存関係が保存されており、
この情報のログを取り、依存関係の樹形図を可視化することができれば
Cerim における並列プログラミングを強力にバックアップすることができる。
\begin{thebibliography}{3}
\bibitem{article1}
宮國 渡: Cell 用の Fine-Grain Task Manager の実装.
琉球大学大学院 理工学研究科 情報工学専攻 平成20年度 学位論文 2008.
\bibitem{article2}
FIXSTARS:http://cell.fixstars.com/ps3linux/index.php/メインページ
\bibitem{article3}
Mark Deloura:Game Programming Gems
株式会社ボーンデジタル 2001
\end{thebibliography}
\end{document}
|
