# HG changeset patch # User gongo # Date 1206503296 -32400 # Node ID fea1ac32de2726fae802d09e46b9d4d79f51ae27 # Parent b70a62630a57ba8ad3f9181392c86d05df11295a *** empty log message *** diff -r b70a62630a57 -r fea1ac32de27 bibliography.tex --- a/bibliography.tex Tue Mar 25 20:45:05 2008 +0900 +++ b/bibliography.tex Wed Mar 26 12:48:16 2008 +0900 @@ -8,9 +8,7 @@ Simple DirectMedia Layer, \url{http://www.libsdl.org/}. \bibitem{akira} -{Akira KAMIZATO.}: Cell - を用いたゲームフレームワークの提案，琉球大学工学部情報工学科平成19年度学位論% -文(修士) (2008). +{Akira KAMIZATO.}: Cell を用いたゲームフレームワークの提案，琉球大学工学部情報工学科平成19年度学位論文(修士) (2008). \bibitem{amdahl} {Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, and Doug @@ -26,8 +24,7 @@ \bibitem{chiaki} {Chiaki SUGIYAMA.}: SceneGraph と StatePattern - を用いたゲームフレームワークの設計と実装，琉球大学工学部情報工学科平成19年度% -卒業論文 (2008). + を用いたゲームフレームワークの設計と実装，琉球大学工学部情報工学科平成19年度卒業論文 (2008). \bibitem{blender} {Satoshi Yamasaki.}: Blender.jp - Blender Japanese Website, diff -r b70a62630a57 -r fea1ac32de27 cell.tex --- a/cell.tex Tue Mar 25 20:45:05 2008 +0900 +++ b/cell.tex Wed Mar 26 12:48:16 2008 +0900 @@ -32,3 +32,33 @@ SPE はグラフィックスに適した、4 つの固定小数点、浮動小数点を 同時に演算する命令などを持ち、PPE に比べて高速な演算が可能である。 そのため、ほとんどの演算を SPE 上で行わせることが推奨されている。 + + +\subsection{SPURS} +ここでは、現在発表されている Cell の開発環境である SPURS について説明する。 + +SPURS は、閉じた並列分散と考えることができる Cell の環境で、 +いかに効率よく動作させるかということを考えたシステムである (\figref{fig-spurs-pipeline}) (\figref{fig-spurs-task}) 。 + +\begin{figure}[tb] + \begin{center} + \includegraphics[scale=0.36]{figure/spurs-pipeline.pdf} + \caption{SPURS Pipeline} + \label{fig-spurs-pipeline} + \end{center} +\end{figure} + +\begin{figure}[tb] + \begin{center} + \includegraphics[scale=0.36]{figure/spurs_task.pdf} + \caption{SPURS Task} + \label{fig-spurs-task} + \end{center} +\end{figure} + +Cell の性能を存分に生かすためには SPE を効率よく使い +切ることとあらゆるレベルで並列処理を行うことである。SPE を効率よく使い切るには +SPU の動作を止めることなく、同期を最小限に行う必要がある。 +そこでSPURSではSPUを効率よく利用するために、PPUに依存せずにSPUコードを +選択し、実行することと機能は効率重視で割り切ることを挙げている。 +現在 SPURS は一般には公開されていない。 diff -r b70a62630a57 -r fea1ac32de27 cerium-manager.tex --- a/cerium-manager.tex Tue Mar 25 20:45:05 2008 +0900 +++ b/cerium-manager.tex Wed Mar 26 12:48:16 2008 +0900 @@ -31,7 +31,7 @@ \end{table} -以下に Task Manager を使った記述を示す。 +以下に Task Manager を使った記述例を示す。 {\small \begin{verbatim} diff -r b70a62630a57 -r fea1ac32de27 cerium-scene_graph.tex --- a/cerium-scene_graph.tex Tue Mar 25 20:45:05 2008 +0900 +++ b/cerium-scene_graph.tex Wed Mar 26 12:48:16 2008 +0900 @@ -3,6 +3,8 @@ ゲームのルールの集合を Scene Graph とする \cite{chiaki} 。 Scene Graph のノードは 親子関係を持つ木構造で構成される (\figref{fig-scene_graph}) 。 +そのため、Scene Graph の各ノードに対してデータ並列実行することが +可能と言える。 \begin{figure}[tb] \begin{center} diff -r b70a62630a57 -r fea1ac32de27 cerium.tex --- a/cerium.tex Tue Mar 25 20:45:05 2008 +0900 +++ b/cerium.tex Wed Mar 26 12:48:16 2008 +0900 @@ -18,6 +18,13 @@ \end{center} \end{figure} + +Ceritum は、Scene Graph、PolygonPack、SpanPack に対してデータ並列実行を +行う。さらに、この 3 つのタスクは表示画面毎にパイプライン的に実行される。 +そのため、Ceritum では並列度を維持することができる。 + +ここからは、Cerium を構成する 3 つのシステムについて述べる。 + \input{cerium-scene_graph} % Scene Graph \input{cerium-rendering} % Rendering Engine \input{cerium-manager} % Task Manager diff -r b70a62630a57 -r fea1ac32de27 cerium_dev.tex --- a/cerium_dev.tex Tue Mar 25 20:45:05 2008 +0900 +++ b/cerium_dev.tex Wed Mar 26 12:48:16 2008 +0900 @@ -1,5 +1,5 @@ -\section{開発過程} -Cerium を用いた開発では、以下の段階にそれぞれ実装とテストを行う。 +\section{Cerium によるゲーム開発} +Cerium 自身や Cerium を用いた開発では、以下の段階にそれぞれ実装とテストを行う。 \begin{enumerate} \item C によるシーケンシャルな実装 \label{list_dev_1} diff -r b70a62630a57 -r fea1ac32de27 compare.tex --- a/compare.tex Tue Mar 25 20:45:05 2008 +0900 +++ b/compare.tex Wed Mar 26 12:48:16 2008 +0900 @@ -1,4 +1,4 @@ -\section{評価と考察} +\section{Cerium の評価と考察} Cerium Rendering Engine を用いて、 OSMesa と同様に立方体を回転させる処理を評価する。 @@ -34,7 +34,7 @@ \tabref{tab:hyoka2} より、SPE に対する最適化が非常に有効であるといえる。 また、描画領域の大きさと実行速度は反比例すると考えると、 -1920x1080の時、OSMesa も合わせると \tabref{tab:hyoka3} のようになる。 +1920x1080の時、先行研究の結果と合わせると \tabref{tab:hyoka3} のようになる。 \begin{table}[htbp] \caption{実行速度 (1920x1080)} \label{tab:hyoka3} @@ -48,11 +48,13 @@ \end{tabular}\hfil} \end{table} -Cerium は 環境 3 の速度を下回っている。 -この理由としては、SPE 上で動かしていない Task があるのが挙げられる。 +Cerium は 環境 1, 2 は上回っているものの、環境 3 の速度を下回っている。 +この理由としては、SPE 上で動かしていないタスクがあるのが挙げられる。 + 現在、Cerium には DMA で SPE 上にプログラムをロードする機能を -実装していないため、必要なプログラムを入れ替えることができない。 -そのため、現在は Renderer の Task だけを SPE 上にマッピングしてある。 +実装していないため、必要な時に必要なプログラムだけを SPE 上に置くという +ことができない。SPE の LS の容量では、全てのタスクを SPE 上に乗せることは +できないため、現在は Renderer のタスクだけを SPE 上にマッピングしてある。 また、Texture の分割と、Texture の必要な部分だけ DMA で 取得するという機能も実装されていない。 diff -r b70a62630a57 -r fea1ac32de27 introduction.tex --- a/introduction.tex Tue Mar 25 20:45:05 2008 +0900 +++ b/introduction.tex Wed Mar 26 12:48:16 2008 +0900 @@ -1,27 +1,24 @@ -\section{はじめに} - -\subsection{PS3 上でのレンダリング} -PlayStation 3 (以下 PS3) に搭載された Linux を用いて、 +\section{研究の目的} +PlayStation 3 (以下 PS3) では、搭載された Linux を用いて、 PS3 上で動くゲーム開発することができる。 -しかし、現在 GPU (Graphics Processing Unit) の詳細/API は +しかし、現在 GPU (Graphics Processing Unit) の API は 一般には公開されていないため、GPU を使った描画はできない。 -ps3fb という Frame Buffer 上に 直接描画することはできるため、 +Frame Buffer 上には直接描画することはできるため、 我々は Frame Buffer 上に描画するゲームフレームワークを提案してきた。 -まず我々は、OSMesa \cite{osmesa} という Frame Buffer Engine 用の -レンダリングエンジン、マルチメディアライブラリの SDL \cite{sdl}、これら -二つを用いて開発を行った。 +\subsection{先行研究とその問題点} +Frame Buffer Engine 用のレンダリングエンジンである +OSMesa \cite{osmesa} と、マルチメディアライブラリの SDL \cite{sdl} の二つを +用いて開発を行った \cite{akira} 。 +例題として、一つの立方体を回転させるというプログラムを用いた。 -最初は PPE のみを利用してゲームプログラミングを行ってきた。 -例題として、一つの立方体を回転させるというプログラムの実行速度は -約 18 FPS という結果となった。FPS (Frame Per Second) は、 -1秒間に何枚の画像が表示されているかを示している。 - +PPE のみを使用した場合の実行速度は約 18 FPS (Frame Per Second) +という結果になった。 これは非常に遅い結果で、その理由は、SPE を使用していないため、 Cell の能力を十分発揮できていないからだと考えられる。 -次に、OSMesa の一部の機能を SPE に演算させることにより高速化を図っている - \Cite{akira} 。 +次に、OSMesa の一部の機能を SPE に演算させることにより +高速化を図っている。 その際の実行結果を \tabref{tab:osmesa} に示す。 @@ -45,35 +42,16 @@ コピーの多用、巨大な構造体等があり、細分化はもちろん、 後に拡張をすることも難しい。 -\subsection{Many Core 上のプログラミング} -従来の逐次型のプログラムでは、Cell といった Many Core の性能を -十分に引き出すことは出来ない。 - -並列実行には Amdahl 則 \cite{amdahl} があり、 -プログラムの並列化率が低ければ、その性能を生かすことは出来ない。 -0.8 程度の並列化では、6 CPU でも -3 倍程度の性能向上しか得られない (\figref{fig-amdahl}) 。 +\subsection{Cerium の提案} +本研究では、PS3 上で高速な描画が可能な、独自のレンダリングエンジンとして、 +Cerium Rendering Engine の開発を行う。 +Cerium は、次の 3 つから構成される。 -\begin{figure}[tb] - \begin{center} - \includegraphics[scale=0.2]{figure/amdahl.pdf} - \caption{Amdahl 則} - \label{fig-amdahl} - \end{center} -\end{figure} - -並列プログラムの特徴として、デバッグが難しいことも挙げられる。 -実行が非決定的(同じ状態で実行しても同じ結果が異なる)場合があり、 -バグの状態を再現することが難しい。 -また、個々の Core 上のデータを調べる必要もある。 - - -\subsection{研究目的} -我々は独自のレンダリングエンジンである -Cerium を開発することにした。 -Cerium は、Rendering Engine、タスクの細分化を行い -Cell の性能を十分に引き出すことを目的とした -Task Manager、ゲームのルールを管理する Scene Graph で構成されている。 +\begin{itemize} + \item Scene Graph + \item Rendering Engine + \item Task Manager +\end{itemize} Cerium は Cell 上だけでなく、Linux や Mac OS X 上でも 動く、シーケンシャルなプログラムも実装することが出来る。 @@ -81,3 +59,5 @@ これにより、全体の動作のデバッグはシーケンシャルプログラムで行い、 仕様が正しいと確認できたら、 Cell 上などの特有の環境で 動作、デバッグを行えばいい。 + + diff -r b70a62630a57 -r fea1ac32de27 manager-cr.tex --- a/manager-cr.tex Tue Mar 25 20:45:05 2008 +0900 +++ b/manager-cr.tex Wed Mar 26 12:48:16 2008 +0900 @@ -1,12 +1,10 @@ - -\subsubsection{並列処理} +\subsubsection{パイプライン処理} +Cell ではそれぞれのコアがメインメモリを +直接参照することは出来ず、DMA 転送によりデータをやりとりする。 +DMA は CPU を介さず直接データ転送を行う方式である。 +SPE は DMA 完了を待たずに他の処理を行うことが出来るので、 +DMA のレイテンシを隠すことが出来る。 -Cell ではあらゆるレベルで並列に動作させることが求められる。 -ダブルバッファがその一例として挙げられる。 -前述した通り、Cell ではそれぞれのコアがメインメモリを -直接参照することは出来ず、DMA 転送によりデータをやりとりする。 -DMA は CPU を介さず直接データ転送を行う方式である。そのため、 -DMA している間は SPE は何らかの処理を行うことが出来る。 また、ダブルバッファリングを行うことで パイプライン処理が可能となる (\figref{fig-pipeline}) 。 @@ -45,33 +43,3 @@ \label{fig-manager-pipeline} \end{center} \end{figure} - -\subsubsection{SPURS} -この Task Manager に似た研究として SPURS \cite{spurs} が挙げられる。 - -SPURS は、閉じた並列分散と考えることができる Cell の環境で、 -いかに効率よく動作させるかということを考えたシステムである (\figref{fig-spurs-pipeline}) (\figref{fig-spurs-task}) 。 -Cell の性能を存分に生かすためには SPE を効率よく使い -切ることとあらゆるレベルで並列処理を行うことである。SPE を効率よく使い切るには -SPU の動作を止めることなく、同期を最小限に行う必要がある。 -そこでSPURSではSPUを効率よく利用するために、PPUに依存せずにSPUコードを -選択し、実行することと機能は効率重視で割り切ることを挙げている。 - -現在 SPURS は一般には公開されていないため、SPURS の考えを基に -Task Manager を作成した。 - -\begin{figure}[tb] - \begin{center} - \includegraphics[scale=0.36]{figure/spurs-pipeline.pdf} - \caption{SPURS Pipeline} - \label{fig-spurs-pipeline} - \end{center} -\end{figure} - -\begin{figure}[tb] - \begin{center} - \includegraphics[scale=0.36]{figure/spurs_task.pdf} - \caption{SPURS Task} - \label{fig-spurs-task} - \end{center} -\end{figure} diff -r b70a62630a57 -r fea1ac32de27 manager-task.tex --- a/manager-task.tex Tue Mar 25 20:45:05 2008 +0900 +++ b/manager-task.tex Wed Mar 26 12:48:16 2008 +0900 @@ -1,168 +1,39 @@ -\subsubsection{Task} -Task の定義は以下のようになる。 - -{\small -\begin{verbatim} - -class Task { -public: - int command; // 実行するタスクID - int size; // in_addr で取得するデータのバイト数 - unsigned int in_addr; // 入力データ元アドレス - unsigned int out_addr; // 出力データ先アドレス - - TaskQueue *wait_me; - TaskQueue *wait_i; - - CPU_TYPE cpu_type; // PPE or SPE - - void spawn(void); - void set_depend(Task*); - void set_cpu(Task*); -}; - -\end{verbatim} -} - -command, size, in\_addr, out\_addr は -create\_task() で引数で登録する。 - \subsubsection{Dependency} \label{sec:task} -「Task1 は Task2, Task3 が終わるまで実行されてはいけない」といった、 -Task 同士での依存関係を指定するには、API の set\_depend() を使う。 - -{\small -\begin{verbatim} - - // task2 は task1 が終了してから開始する - task2->set_depend(task1); - -\end{verbatim} -} - -set\_depend の実装を以下に示す。 - -{\small -\begin{verbatim} - -void -Task::set_depend(Task* master) -{ - Task *slave = this; +Task Manager はタスク依存を解決する機能を持っている (set\_depend) 。 +タスク依存が満たされたものをアクティブキューにいれ、SPE を起動する。 +SPE はアクティブキューから、処理するコードとデータを取得し、 +自律的に実行を行う。 +終了したタスクは PPE に対して終了のコマンドを発行し、PPE はそれを見て +ウェイトキューのタスクを調べ、タスク依存を満たしたものが出てきたら +アクティブキューに入れ、SPE を再び起動する。 - master->wait_me - = append_queue(master_wait_me, slave) - slave->wait_i - = append_queue(slave_wait_i, master); -} -\end{verbatim} -} - -各 Task が持つ wait\_me は、「自分を待っている Task」のキューで、 -wait\_i は、「自分が待っている Task 」のキューとなる。 - -Task が spawn された時、wait\_i が空であれば 実行 Queue へ、 -あれば WaitQueue へ追加される。 - -Task が終わる毎に、SPE から Task が終了したことを PPE に知らせる。 -PPE は、Task が終了したことを、WaitQueue にある Task に知らせる。 -WaitQueue の Task は、終了した Task が、自分が待っている Task であれば -自分の wait\_i からその Task を削除していく。 -自分の wait\_i が空になれば、Task 依存を満たしたので ActiveQueue に追加される。 -以上の記述を以下に示す。 - -{\small -\begin{verbatim} - -/** - * master : 終了した Task - * list : master->wait_me - */ -void -notify_waitQueue(Task *master,TaskQueue *list) -{ - Task* slave; - - while (list) { - slave = list->task; - slave->wait_i - = remove_taskQueue(slave->wait_i, master); - if (slave->wait_i == NULL) { - append_activeTask(slave); - } - list = list->next; - } -} - -\end{verbatim} -} - -\subsubsection{Mail} -\ref{sec:task} で述べたように、SPE から Task の終了を -PPE に伝える必要があるが、その際の待ち合わせは避けるべきである。 +\subsubsection{PPE と SPE 間の同期} +\ref{sec:task} で述べたように、PPE から SPE へタスクはの実行命令を、 +SPE から PPE へはタスクの終了などを伝える必要がある。 +その際、待ち合わせを行うと処理が止まってしまい、並列度が下がってしまう。 Cell では、PPE と SPE 間のメッセージのやりとりには -Mail box という FIFO メッセージキューを用いる。 +Mailbox という FIFO メッセージキューを用いることができる。 メッセージ交換なので待ち合わせを避けることが可能である。 -SPE $\rightarrow$ PPE だけでなく、PPE Kernel 内部でも -Mailbox と同じ方式でメッセージ交換をしている。 -Task は SPE だけでなく、PPE でも実行されているためである。 - -メールチェックをする関数 mail\_check() を以下に示す。 -この関数は、現在 PPE 側の ActiveQueue にある Task が -全て終わった後、次の ActiveQueue を取得する前に呼ばれる。 - -{\small -\begin{verbatim} - -MailQueuePtr -SpeTaskManager::mail_check(MailQueue *mail_list) -{ - MailQueue *list; - unsigned int data; - - // mail_list には、 - // 「PPE側」で終了した Task に関するメールがある - // list には、次の Task に関するメールがある - list = ppeTaskManager->mail_check(mail_list); - - do { - for (id = 0; id < SPE_NUM; id++) { - while (1) { - // data には、 - // 「SPE側」で終了した Task がある。 - // data がマイナスの場合、Mail box は空 - data = speThreads->get_mail(id); - if (data < 0) break; - check_task_finish(data); - } - } - } while (list == NULL && waitTaskQueue - && !activeTaskQueue); - - return list; -} - -\end{verbatim} -} - -PPE が SPE からメールを受け取る場合、 -spe\_out\_mbox\_read() という、SPE Runtime Management Library \cite{libspe2} を -用いる。しかし、spe\_out\_mbox\_read() は Non-blocking function のため、 -busy-wait なメールの待ち方は避けるべきである。 -今回は、PPE 側でメールチェックを行う際に、SPE からのメールをチェックする。 - -PPE と SPE のメールチェックを分離させたい場合、 -メールをチェックする Blocking Function を作る必要がある。 - -もしくは SPE Event Handling を用いる手法もある。 -これは、メールが来たら event を起こすことを Event Handler に登録する。 -この場合、通常の Mailbox ではない、割り込み用の interrupting Mailbox を -使用しなくてはならない。 -interrupting Mailbox を使用する spe\_out\_intr\_mbox\_read() は、 -Event が起きたときに呼ばれるため Blocking Function である。 -SPE のどれかからメッセージが来たらポーリングによってメールチェックを行う。 - -今回は、PPE と SPE のメールチェックは分離しない実装をした。 +%%PPE が SPE からメールを受け取る場合、 +%%\verb|spe_out_mbox_read()| という、 +%%SPE Runtime Management Library \cite{libspe2} を用いる。 +%%しかし、\verb|spe_out_mbox_read()| は Non-blocking function のため、 +%%busy-wait なメールの待ち方は避けるべきである。 +%%今回は、PPE 側でメールチェックを行う際に、SPE からのメールをチェックする。 +%% +%%PPE と SPE のメールチェックを分離させたい場合、 +%%メールをチェックする Blocking Function を作る必要がある。 +%% +%%もしくは SPE Event Handling を用いる手法もある。 +%%これは、メールが来たら event を起こすことを Event Handler に登録する。 +%%この場合、通常の Mailbox ではない、割り込み用の interrupting Mailbox を +%%使用しなくてはならない。 +%%interrupting Mailbox を使用する spe\_out\_intr\_mbox\_read() は、 +%%Event が起きたときに呼ばれるため Blocking Function である。 +%%SPE のどれかからメッセージが来たらポーリングによってメールチェックを行う。 +%% +%%今回は、PPE と SPE のメールチェックは分離しない実装をした。 +%% diff -r b70a62630a57 -r fea1ac32de27 manycore.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/manycore.tex Wed Mar 26 12:48:16 2008 +0900 @@ -0,0 +1,48 @@ +\section{Many Core 上のプログムの特徴} +従来の逐次型のプログラムでは、Cell といった Many Core の性能を +十分に引き出すことは出来ない。 + +\subsection{定常的な並列度の必要性} +並列実行には Amdahl 則 \cite{amdahl} があり、 +プログラムの並列化率が低ければ、その性能を生かすことは出来ない。 +0.8 程度の並列化では、6 CPU でも +3 倍程度の性能向上しか得られない (\figref{fig-amdahl}) 。 + +\begin{figure}[tb] + \begin{center} + \includegraphics[scale=0.2]{figure/amdahl.pdf} + \caption{Amdahl 則} + \label{fig-amdahl} + \end{center} +\end{figure} + +高い並列度ではなくとも、恒常的に並列度を維持する必要がある。 +このため、逐次型のプログラムの一部を並列化するという手法では不十分である。 +LSI などのハードウェアの場合は、演算の対象がもともと +多量の演算とデータパスを持つので、並列計算の効果を +定常的に得られることが多い。しかし、C 等で記述されたプログラムでは、 +for 文や配列のアクセス等に並列性が隠されてしまい、それを引き出すことが難しい。 + +プログラム中の並列度は、主に二つの形で取り出すことが出来る。 + +\begin{itemize} + \item データ並列 : + 配列や木の中の個々の要素に対して並列に実行する + \item パイプライン処理 : + 複数の逐次処理の隣同士を重ねて実行する +\end{itemize} + +この二つを同時に用いることで、定常的な並列度を維持することが +可能となることがある。パイプライン処理は、 +プログラム中で階層的に使われることが多い。 + +データ並列とパイプライン処理を可能にするためには、 +プログラムとデータの適切な分割を行う必要がある。 +for 文、あるいは、木をだとって処理する個々のステートメントがプログラムの +分割の対象となる。 + +\subsection{デバッグ　　} +並列プログラムの特徴として、デバッグが難しいことも挙げられる。 +実行が非決定的(同じ状態で実行しても同じ結果が異なる)場合があり、 +バグの状態を再現することが難しい。 +また、個々の Core 上のデータを調べる必要もある。 diff -r b70a62630a57 -r fea1ac32de27 sigos.tex --- a/sigos.tex Tue Mar 25 20:45:05 2008 +0900 +++ b/sigos.tex Wed Mar 26 12:48:16 2008 +0900 @@ -32,8 +32,8 @@ \eauthor{ Wataru MIYAGUNI\affiref{1}\and Shinji KONO\affiref{2}\and - Akira KAMIZATO\affiref{1}\and - Chiaki SUGIYAMA\affiref{2} + Akira KAMIZATO\affiref{3}\and + Chiaki SUGIYAMA\affiref{4} } % 連絡先（投稿時に必要．製版用では無視される．） @@ -70,6 +70,7 @@ \input{introduction} % 研究目的 \input{cell} % Cell +\input{manycore} % many core system \input{cerium} % Cerium \input{cerium_dev} % 開発過程 \input{compare} % 評価と考察