Mercurial > hg > Papers > 2009 > gongo-master
changeset 5:42b2f2540153
4章終わり(要修正だろうけど
line wrap: on
line diff
--- a/paper/cerium.tex Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/cerium.tex Thu Feb 05 16:51:20 2009 +0900 @@ -1,1 +1,31 @@ \chapter{Cerium} \label{chapter:cerium} + +Cerium \cite{cerium} は SceneGraph (\ref{sec:cerium_scene_graph}節)、 +Rendering Engine (\ref{sec:cerium_rendering}節)、Task Manager から構成され、 +主に以下の３つのタスクを持つ (\figref{cerium_task})。 + +\begin{itemize} +\item SceneGraph が持つ Polygon の座標から、実際に画面に表示する座標の + 計算を行い、PolygonPack (\ref{sec:cerium_rendering_pp}節) を生成する +\item PolygonPack から、同じ Y 座標を持つ線分の集合 + SpanPack (\ref{sec:cerium_rendering_span}節) を生成する +\item SpanPack を、Texture を読み込みながら Z Buffer を用いて描画する +\end{itemize} + +\begin{figure}[htb] + \begin{center} + \includegraphics[scale=0.8]{images/cerium_task.pdf} + \caption{Cerium の要素} + \label{fig:cerium_task} + \end{center} +\end{figure} + +Cerium は SceneGraph、PolygonPack、SpanPack に対してデータ並列実行を行う。 +さらに、この3つのタスクは表示画面毎にパイプライン的に実行される。 +そのため、Cerium では並列度を維持することが出来る。 + +Cerium は C++ で実装されており、プログラム行数は 6919 行である。 + +\section{SceneGraph} \label{sec:cerium_scene_graph} + +\section{Rendering Engine} \label{sec:cerium_rendering}
--- a/paper/images/amdahl.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/amdahl.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./amdahl.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 360 252 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/cell_arch.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/cell_arch.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_arch.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 505 339 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/cell_mailbox.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/cell_mailbox.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_mailbox.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 514 342 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/cell_ppe.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/cell_ppe.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_ppe.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 370 327 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/cell_simd.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/cell_simd.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_simd.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 402 261 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/cell_spe.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/cell_spe.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_spe.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 380 340 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/cell_spurs_pipeline.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/cell_spurs_pipeline.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_spurs_pipeline.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 533 187 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/cell_spurs_task.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/cell_spurs_task.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_spurs_task.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 507 229 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/cerium_task.bb Thu Feb 05 16:51:20 2009 +0900 @@ -0,0 +1,5 @@ +%%Title: ./cerium_task.pdf +%%Creator: ebb Version 0.5.2 (+ArtBox) +%%BoundingBox: 0 0 470 535 +%%CreationDate: Thu Feb 5 16:40:16 2009 +
--- a/paper/images/manycore_data_split.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/manycore_data_split.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./manycore_data_split.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 587 154 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/manycore_step.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/manycore_step.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./manycore_step.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 549 335 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/tm_scheduler.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/tm_scheduler.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./tm_scheduler.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 517 492 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/tm_sm_rbuf.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/tm_sm_rbuf.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./tm_sm_rbuf.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 405 225 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/tm_sm_state.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/tm_sm_state.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./tm_sm_state.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 370 342 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/tm_sm_wbuf.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/tm_sm_wbuf.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./tm_sm_wbuf.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 505 487 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/tm_sort.bb Thu Feb 05 16:51:20 2009 +0900 @@ -0,0 +1,5 @@ +%%Title: ./tm_sort.pdf +%%Creator: ebb Version 0.5.2 (+ArtBox) +%%BoundingBox: 0 0 553 371 +%%CreationDate: Thu Feb 5 16:40:16 2009 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/tm_sort_calc.bb Thu Feb 05 16:51:20 2009 +0900 @@ -0,0 +1,5 @@ +%%Title: ./tm_sort_calc.pdf +%%Creator: ebb Version 0.5.2 (+ArtBox) +%%BoundingBox: 0 0 360 216 +%%CreationDate: Thu Feb 5 16:40:16 2009 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/tm_sort_calc.txt Thu Feb 05 16:51:20 2009 +0900 @@ -0,0 +1,6 @@ +1 1 1 +2 1.9746994 2 +3 2.9360519 3 +4 3.8560168 4 +5 4.7757995 5 +6 5.6169992 6
--- a/paper/images/tm_sync.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/tm_sync.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./tm_sync.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 577 554 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/tm_task_post.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/tm_task_post.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./tm_task_post.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 335 388 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/images/tm_task_struct.bb Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/images/tm_task_struct.bb Thu Feb 05 16:51:20 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./tm_task_struct.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 591 364 -%%CreationDate: Wed Feb 4 19:27:04 2009 +%%CreationDate: Thu Feb 5 16:40:16 2009
--- a/paper/master_paper.bib Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/master_paper.bib Thu Feb 05 16:51:20 2009 +0900 @@ -36,10 +36,10 @@ year = "2005" } -@misc{gongo, +@misc{cerium, author = "", -title = "{SourceForge.JP: Project Info - Cerium Rendering Engine}", -howpublished = "\url{https://sourceforge.jp/projects/cerium/}" +title = "{SourceForge.JP: Cerium Rendering Engine}", +howpublished = "{https//sourceforge.jp/projects/cerium/}" } @misc{spurs, @@ -111,5 +111,5 @@ @misc{sdl, author = "", title = "{Simple DirectMedia Layer}", -howpublished = "\url{http://www.libsdl.org/}" +howpublished = "{http://www.libsdl.org/}" } \ No newline at end of file
--- a/paper/taskmanager.tex Wed Feb 04 19:27:38 2009 +0900 +++ b/paper/taskmanager.tex Thu Feb 05 16:51:20 2009 +0900 @@ -314,7 +314,8 @@ 複雑で大量なタスクの依存関係も設定することが可能となっている。 -\section{CPU スレッド} +\section{CPU スレッドの実装} + 各 CPU では、メインスレッドで生成された Task を受け取り、 その情報を元に、タスクを実行する。 ここでは、Task を扱うスケジューラの実装と、 @@ -535,11 +536,84 @@ \begin{figure}[htb] \begin{center} - \includegraphics[scale=0.8]{images/tm_sync.pdf} + \includegraphics[scale=0.7]{images/tm_sync.pdf} \caption{PPE, SPE threads} \label{fig:tm_sync} \end{center} \end{figure} -\section{学生による TaskManager を用いた開発} +\section{評価} + +TaskManager は、第 \ref{chapter:cerium} 章で述べる Cerium を構築するもので、 +特にユーザが触れることが一番多い機能である。 + +ここでは、実際に TaskManager を用いて学生に並列プログラミングを行ってもらい、 +その結果と学生の総評から、TaskManager の評価を述べる。 + +\subsection{並列ソーティングプログラム} + +今回は整数のデータをソートするプログラムを学生に記述してもらった。 +SPE のメモリ領域(LS) は 256KB と少ないため、 +データ全てを SPE に送った場合、領域が足りない可能性がある。 +そこで、データを複数のブロックに分割して、 +それらのブロック毎に SPE に送ってソートする。 +ブロック内ではクイックソートを行う。 +その後、ソートし終わったブロックの隣同士でソートを行う。 +この作業を分割回数だけ繰り返せば全体のデータのソートが完了となる +(\figref{tm_sort}) 。 + +\begin{figure}[htb] + \begin{center} + \includegraphics[scale=0.8]{images/tm_sort.pdf} + \caption{Sort} + \label{fig:tm_sort} + \end{center} +\end{figure} + +ブロックのサイズは 一回の DMA の制限である 16KB に設定した。 +この手法では、各ブロックのソートを独立して行えるため、 +他タスクとの待ち合わせの回数を最小限に抑えることが出来る。 + +このプログラムを、使用する SPE の個数を 1から6に変化させて、その +実行速度を計測した (\figref{tm_sort_calc} ) 。 +今回はソートする整数の数は 10 万とした。 +横軸が使用した SPE の数、縦が、SPE 1個の時の実行結果を 1 をしたときの +台数効果である。 + +\begin{figure}[htb] + \begin{center} + \includegraphics[scale=1.2]{images/tm_sort_calc.pdf} + \caption{Sort 実験結果} + \label{fig:tm_sort_calc} + \end{center} +\end{figure} + +SPE 6個の台数効果が 5.6 となり、理論値にはおよばないものの、 +充分な台数効果が出ていると言える。 + +\subsection{画像の拡大縮小回転、色の変換} + +変換を行う画像の読み込みは SDL \cite{sdl} を使用しており、 +当初学生は生成された SDL のデータ構造 (SDL\_Surface) を +そのまま SPE に送っていた。しかし、SDL\_Surface が持つ画像データは +メインメモリ空間のアドレスで、SPE 側で参照できないという問題で +つまづく学生が多かった。 + +その問題を回避するためには、SDL\_Surface ではない新しい構造体を +作成する必要がある。アドレスではなく画像データそのものを持ち +変換タスクに対応するデータ構造への変換を行った。 + +\subsection{総評} +学生の反応で多かったのは、シーケンシャルプログラムから並列プログラムへ +変換する際に、データやコードの分割を行うのに苦労していたことである。 +分割したデータ構造の設計や使用方法がシーケンシャルなプログラミングとは +違うためだと考えられる。 +並列処理の経験が浅いプログラマに対しては、コードやデータの分割に際して、 +何らかの雛形が必要であると言える。 + +また、Cell 特有の制限(DMA サイズ制限、アライメント) や、 +SPE と PPE でのアドレス空間の違いなど、Cell の使用に関する問題も起きた。 +そういった意見を反映し、環境使用は TaskManager 側で意識しない様に +実装している。しかし、アーキテクチャに対応した、タスクの最適化を行う場合、 +ユーザ自身がターゲットアーキテクチャの使用を学ぶ必要がある。