Mercurial > hg > Papers > 2009 > gongo-master
changeset 29:57a914ebe900 default tip
fix
| author | gongo@gendarme.cr.ie.u-ryukyu.ac.jp |
|---|---|
| date | Tue, 17 Feb 2009 17:11:52 +0900 |
| parents | 356077fb1c38 |
| children | |
| files | paper/master_paper.bib resume/handout.bib resume/handout.tex resume/images/tm_sm_pipeline_wait.bb resume/images/tm_sm_pipeline_wait.graffle resume/images/tm_sm_pipeline_wait.pdf |
| diffstat | 6 files changed, 84 insertions(+), 80 deletions(-) [+] |
line wrap: on
line diff
--- a/paper/master_paper.bib Tue Feb 17 12:27:00 2009 +0900 +++ b/paper/master_paper.bib Tue Feb 17 17:11:52 2009 +0900 @@ -89,8 +89,8 @@ } @misc{blender, -title = "{Blender.jp - Blender Japanese Website}", -howpublished = "{http://blender.jp/}" +title = "{blender.org}", +howpublished = "{http://blender.org/}" } @article{spufs,
--- a/resume/handout.bib Tue Feb 17 12:27:00 2009 +0900 +++ b/resume/handout.bib Tue Feb 17 17:11:52 2009 +0900 @@ -89,8 +89,8 @@ } @misc{blender, -title = "{Blender.jp - Blender Japanese Website}", -howpublished = "{http://blender.jp/}" +title = "{blender.org}", +howpublished = "{http://www.blender.org/}" } @article{spufs,
--- a/resume/handout.tex Tue Feb 17 12:27:00 2009 +0900 +++ b/resume/handout.tex Tue Feb 17 17:11:52 2009 +0900 @@ -30,36 +30,21 @@ \section{はじめに} -現在、学生実験にて PlayStation 3 (PS3) で動作するゲーム開発を行っている。 -しかし、PS3 のアーキテクチャである Cell は、 -Many Core を用いた並列プログラミングが求められており、 +現在、学生実験にて PlayStation 3 (PS3) で動作するゲーム開発を行っている。 +PS3 が持つ Cell アーキテクチャを用いたプログラムでは、 +Many Core を用いた並列プログラミングが求められているため、 並列プログラミングの経験が浅い学生にとって、 -Cell のようなアーキテクチャを理解した上でゲームを実装することは困難である。 +Cell アーキテクチャを理解した上でゲームを実装することは困難である。 また、現在 PS3 ゲーム開発用フレームワークが存在しないことで、 学生が一からプログラミングしていく必要がある。 -%この様な問題から、例年、学生実験の期間の大半を -%アーキテクチャの勉強に費やさねばならず、残りの期間内でゲーム開発を行っている。 -%そのため、制作されたゲームの完成度が一定以上にならない。 本研究では、Many Core Architetcure を用いた並列プログラムの開発をサポートする フレームワークとして Fine-Grain Task Manager を実装し、それを組み込んだ、 PS3 ゲーム開発用フレームワークである Cerium を提案する。 -%Cerium を用いた開発行程は以下の様になる。 -% -%\begin{itemize} -%\item 逐次型プログラム -%\item データやコードを分割したプログラム -%\item 並列に動かすプログラム -%\end{itemize} -% -%これらのステップ毎にプログラムの仕様やアルゴリズムを確かめ、テストやデバッグを行い信頼性を確保しながら開発を進める。 - Cerium は学生が Cell を理解しながら、一定期間内でゲーム開発が行える、 シンプルなマルチタスクフレームワークを目指している。 -\vspace{-4mm} - \section{Cell Broadband Engine} Cell \cite{cell} は、1個の Power PC Processor Element (PPE) と、 8個の Synergistic Processor Element (SPE) からなる非対称なマルチコアプロセッサ @@ -74,67 +59,84 @@ \end{center} \end{figure} -\vspace{-8mm} - -本研究で用いた PS3Linux (Fedora 10、Yellow Dog Linux 6.0) からは +本研究で用いた PS3Linux (Fedora 10 及び Yellow Dog Linux 6.0) からは 6個の SPE が使用できる。SPE には 256KB の Local Store (LS) と呼ばれる メモリ領域を持っている。また、SPE からメインメモリへは直接アクセスできず、 SPE が持つ Memory Flow Controller (MFC) へ、DMA 命令を発行することで行われる 。 -%(\figref{cell_spe})。 - -%\begin{figure}[htb] -% \begin{center} -% \includegraphics[scale=0.25]{./images/cell_spe.pdf} -% \caption{Synergistic Processor Element (SPE)} -% \label{fig:cell_spe} -% \end{center} -%\end{figure} Cell が持つ基本的な機能として、Mailbox \cite{libspe2} がある。 Mailbox は SPE の MFC 内にある 32ビットメッセージの FIFO キューを保持しており、 PPE と SPE 間での同期に用いることができる。 -\vspace{-4mm} \section{Many Core プログラミングの特徴} -並列実行には Amdahl 則 \cite{amdahl}があり、 -使用するCPUを増やしても、元のプログラムの -並列化率が低ければ、その性能を生かすことは出来ないとされている -(\figref{amdahl})。 + +Many Core プログラムではデータ並列、パイプライン処理を行うことが必要となる。 + +複数の CPU が干渉しあうデータを用いる場合、整合性を維持するために +待ち合わせる必要があり、その待ち時間が無駄になってしまう。 +したがって、 +%データ並列を行うには、 +使用するデータを各 CPU が独立に +アクセスできるように分割する必要がある。 + +パイプライン処理では、read() や write() の DMA 待ちの間に、 +exec() を行うことで DMA の待ち時間を隠蔽することが出来る。 +しかし、各ステージ終了のタイミングによっては待ちが入ってしまう場合がある +(\figref{tm_sm_pipeline_wait})。 \begin{figure}[htb] \begin{center} - \includegraphics[scale=0.35]{./images/amdahl.pdf} - \caption{Amdahl則 (6CPUを用いた時の並列化率と性能向上率)} - \label{fig:amdahl} + \includegraphics[scale=0.5]{images/tm_sm_pipeline_wait.pdf} + \caption{パイプラインの待ち時間の発生} + \label{fig:tm_sm_pipeline_wait} \end{center} + \vspace{-4mm} \end{figure} -並列度を維持するためには、元のプログラム及びデータの分割による -データ並列、パイプライン処理を行うことが必要である。 +step1では全てのステージが同じタイミングで終了しているが、 +step2では、read()以外は早く終わり、step3ではexec()以外が早く終わっている。 +このことにより、早くに終了したステージには待ち時間が入ってしまう。 +待ち時間を減らすには、早く終わったステージの余った時間を +他のタスクに割り当てたり、 +終了するタイミングが同じタスクが同時に実行されるようなスケジューリングが +必要となる。 -並列プログラミングでは、以下の段階において、それぞれ実装とテストを行う。 - -\vspace{-2mm} -{\small -\begin{verbatim} -step1. C によるシーケンシャルな実装 -step2. 並列実行を考慮したデータ構造を持つ実装 -step3. コードを分割し、それらをシーケンシャルに実行する実装 -step4. 分割したコードを並列実行する実装 -step5. アーキテクチャに特化した実装 -\end{verbatim} -} +%並列実行には Amdahl 則 \cite{amdahl}があり、 +%使用するCPUを増やしても、元のプログラムの +%並列化率が低ければ、その性能を生かすことは出来ないとされている +%(\figref{amdahl})。 +% +%\begin{figure}[htb] +% \begin{center} +% \includegraphics[scale=0.35]{./images/amdahl.pdf} +% \caption{Amdahl則 (6CPUを用いた時の並列化率と性能向上率)} +% \label{fig:amdahl} +% \end{center} +%\end{figure} +% +%並列度を維持するためには、元のプログラム及びデータの分割による +%データ並列、パイプライン処理を行うことが必要である。 +% +%並列プログラミングでは、以下の段階において、それぞれ実装とテストを行う。 +% +%{\small +%\begin{verbatim} +%step1. C によるシーケンシャルな実装 +%step2. 並列実行を考慮したデータ構造を持つ実装 +%step3. コードを分割し、それらをシーケンシャルに実行する実装 +%step4. 分割したコードを並列実行する実装 +%step5. アーキテクチャに特化した実装 +%\end{verbatim} +%} +% +%step3 まではシーケンシャルに実行されるためアーキテクチャに依存しない実装と +%なっており、二分法によるデバッグが可能となっている。 +%step4、5 で異常が確認できた場合、一度 step3 に戻りアルゴリズムやデータ構造、 +%プログラム分割が正しいかを確認する。 +% -\vspace{-2mm} - -step3 まではシーケンシャルに実行されるためアーキテクチャに依存しない実装と -なっており、二分法によるデバッグが可能となっている。 -step4、5 で異常が確認できた場合、一度 step3 に戻りアルゴリズムやデータ構造、 -プログラム分割が正しいかを確認する。 - -\vspace{-4mm} \section{TaskManager} Task Manager は、Task と呼ばれる、分割された各プログラムの管理を行う。 @@ -144,9 +146,14 @@ SPE スレッドでは、受け取った Task をパイプラインに沿ってステージを遷移しながら 複数の Task を同時に実行していく。 +%Task Manager は、Task が実行される CPU を明示的に選択できる機能を +%持っているため、違う環境へプログラムを移行する場合に大幅なコードの変更が +%必要なく、環境依存のプログラム変換はタスク内部だけになる。 + Task Manager は、Task が実行される CPU を明示的に選択できる機能を -持っているため、違う環境へプログラムを移行する場合に大幅なコードの変更が -必要なく、環境依存のプログラム変換はタスク内部だけになる。 +持っているため、環境依存のコードを Task の中だけで閉じ込めることが可能となる。 +このことから、違う環境へプログラムを移行する場合には、大幅なコードの +変更が必要ない。 PPE スレッドと SPE スレッド間の同期は、Cell の機能である Mailbox を用いる。 メッセージ交換なので、スレッド間の待ち合わせは起こらない。 @@ -184,7 +191,6 @@ % \end{center} %\end{figure} % -\vspace{-2mm} \section{Cerium} @@ -200,15 +206,12 @@ \begin{figure}[htb] \begin{center} \includegraphics[scale=0.3]{./images/cerium.pdf} - \vspace{-4mm} \caption{Cerium} \label{fig:cerium} \end{center} + \vspace{-8mm} \end{figure} -\vspace{-8mm} - -\subsection{SceneGraph} ゲームオブジェクトは オープンソースの3Dモデリングツールである Blender \cite{blender} で作成し、Cerium 独自の XML 形式で出力する \cite{chiaki}。 @@ -216,7 +219,6 @@ を生成する。SceneGraph はポリゴン情報の他に、オブジェクトの操作に関する move や 他の SceneGraph との衝突処理を行う collision を持つ。 -\subsection{Rendering Engine} Cerium Rendering Engine では、SceneGraph の操作後、 実際に描画するポリゴン を SceneGraph から取得する {\bf SG2PP}、 ポリゴンの中から Span (ポリゴン内にある x軸に水平な線分) を抽出する @@ -226,15 +228,12 @@ \begin{figure}[htb] \begin{center} \includegraphics[scale=0.25]{./images/rendering.pdf} - \vspace{-4mm} \caption{Cerium Rendering Engine} \label{fig:rendering} \end{center} + \vspace{-8mm} \end{figure} -\vspace{-8mm} -\subsection{Cerium を用いたゲーム開発} - \figref{dandy} は、学生が Cerium を用いて開発したPS3 で動作する 3Dシューティングゲームである。このゲームの実行結果を \tabref{game} に示す。 SPE 6 個で、SPE 1 個のものより 3.6 倍の性能向上となった。 @@ -244,8 +243,8 @@ \includegraphics[scale=0.08]{./images/cerium_game_1.pdf} \caption{SuperDandy3D(仮)} \label{fig:dandy} - \vspace{-4mm} \end{center} + \vspace{-8mm} \end{figure} \begin{table}[htb] @@ -263,15 +262,15 @@ \end{center} \end{table} + \section{比較} -\subsection{Gallium} 先行研究 \cite{akira} では、レンダリングエンジンに OSMesa \cite{osmesa}を用い、 その後 Galiium \cite{gallium} というOSMesa の Cell driver が登場した。 しかし、PS3 上のゲーム開発において、 レンダリングのみを SPE 上で実行させるのは Amdahl 則の問題もあり好ましくない。 したがって、レンダリングだけでなく、ゲームオブジェクトも SPE で処理させる 方針の Cerium では独自のレンダリングエンジンを用いている。 -\subsection{OpenCL} + 並列コンピューティングフレームワークである OpenCL \cite{opencl} は、 あらゆる Many Core Architecture に対応できるような汎用的な実装がされており、 開発環境に合わせた記述が必要となる。また、現在 OpenCL を用いた Cell 用の