# HG changeset patch
# User gongo
# Date 1206427913 -32400
# Node ID bd8574dedd1be0d0e03586a0776a033bf7eea436
# Parent  a46c6f313a0b05e9c47f9ec254454ab04e8b65f0
*** empty log message ***

diff -r a46c6f313a0b -r bd8574dedd1b cerium-manager.tex
--- a/cerium-manager.tex	Tue Mar 25 11:28:28 2008 +0900
+++ b/cerium-manager.tex	Tue Mar 25 15:51:53 2008 +0900
@@ -30,6 +30,7 @@
   \end{tabular}\hfil}
 \end{table}
 
+
 以下に Task Manager を使った記述を示す。
 
 {\small
@@ -66,75 +67,5 @@
 \end{verbatim}
 }
 
-\subsection{並列処理}
-
-Cell ではあらゆるレベルで並列に動作させることが求められる。
-ダブルバッファがその一例として挙げられる。
-前述した通り、Cell ではそれぞれのコアがメインメモリを
-直接参照することは出来ず、DMA 転送によりデータをやりとりする。
-DMA は CPU を介さず直接データ転送を行う方式である。そのため、
-DMA している間は SPE は何らかの処理を行うことが出来る。
-また、ダブルバッファリングを行うことで
-パイプライン処理が可能となる (\figref{fig-pipeline}) 。
-
-\begin{figure}[tb]
-  \begin{center}
-    \includegraphics[scale=0.43]{figure/pipeline.pdf}
-    \caption{Pipeline}
-    \label{fig-pipeline}
-  \end{center}
-\end{figure}
-
-パイプライン処理を入れた Task Manager の Scheduler を以下に示す。
-
-\begin{verbatim}
-
-    do {
-        task3->write();
-        task2->exec();
-        task1->read();
-
-        taskTmp = task3;
-        task3 = task2;
-        task2 = task1;
-        task1 = task1->next(this, taskTmp);
-    } while (task1);
-
-\end{verbatim}
-
-Task Manager を \figref{fig-cerium} に適用させると、
-\figref{fig-manager-pipeline} のようにパイプライン的に動作する。
-
-\begin{figure}[tb]
-  \begin{center}
-    \includegraphics[scale=0.36]{figure/manager-pipeline.pdf}
-    \caption{Task Manager が行う Pipeline}
-    \label{fig-manager-pipeline}
-  \end{center}
-\end{figure}
-
-\subsection{SPURS}
-この Task Manager に似た研究として SPURS \cite{spurs} が挙げられる。
-
-SPURS は、閉じた並列分散と考えることができる Cell の環境で、
-いかに効率よく動作させるかということを考えたシステムである。
-
-Cerium のように SPE に入力データを与えるプログラムに関しては
-ほとんど同じ機能を持っている (\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}
+\input{manager-task}
+\input{manager-cr}
diff -r a46c6f313a0b -r bd8574dedd1b compare.tex
--- a/compare.tex	Tue Mar 25 11:28:28 2008 +0900
+++ b/compare.tex	Tue Mar 25 15:51:53 2008 +0900
@@ -32,6 +32,7 @@
 \end{table}
 
 \tabref{tab:hyoka2} より、SPE に対する最適化が非常に有効であるといえる。
+
 また、描画領域の大きさと実行速度は反比例すると考えると、
 1920x1080の時、OSMesa も合わせると \tabref{tab:hyoka3} のようになる。
 
@@ -49,9 +50,14 @@
 
 Cerium は 環境 3 の速度を下回っている。
 この理由としては、SPE 上で動かしていない Task があるのが挙げられる。
-現在、DMA で SPE 上にプログラムをロードする機能を実装していないため、
-必要なプログラムを入れ替えることができない。
+現在、Cerium には DMA で SPE 上にプログラムをロードする機能を
+実装していないため、必要なプログラムを入れ替えることができない。
 そのため、現在は Renderer の Task だけを SPE 上にマッピングしてある。
+
+また、Texture の分割と、Texture の必要な部分だけ DMA で
+取得するという機能も実装されていない。
+そのため、ここでは開始直後に Texture を全て SPE 上にロードしている。
+
 Cerium の描画領域の横幅が 640 に抑えてあるのも、上記の問題が原因で
 1920 pixel 分の Z Buffer を SPE 上に置くスペースが無いからである。
 オーバーレイ機能を導入するという手法もあるが、
diff -r a46c6f313a0b -r bd8574dedd1b conclusion.tex
--- a/conclusion.tex	Tue Mar 25 11:28:28 2008 +0900
+++ b/conclusion.tex	Tue Mar 25 15:51:53 2008 +0900
@@ -39,5 +39,12 @@
 並列プログラミングの経験がない学生には難しいため、
 何らかのひな形を示す必要がある。
 
+\figref{fig-pipeline} では、Task Exec の中で DMA の処理を
+行うことを想定した実装にはなっていない。
+Exec の中でアドレスの計算をし、それを元に DMA 転送をする、というのもありえる。
+しかし、ユーザが勝手に DMA 命令を発効すると、DMA 完了待ちやデータ重複など、
+パイプラインの流れが崩れてしまう恐れがある。
+それを回避する実装が必要である。
+
 現在は C++ で記述しているが、CbC に書き換えることで
 モデル検査を行うことができ、高い信頼性を得られる。
diff -r a46c6f313a0b -r bd8574dedd1b figure/amdahl.bb
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/figure/amdahl.bb	Tue Mar 25 15:51:53 2008 +0900
@@ -0,0 +1,5 @@
+%%Title: ./amdahl.pdf
+%%Creator: ebb Version 0.5.2 (+ArtBox)
+%%BoundingBox: 0 0 1040 450
+%%CreationDate: Tue Mar 25 15:23:09 2008
+
diff -r a46c6f313a0b -r bd8574dedd1b figure/amdahl.pdf
Binary file figure/amdahl.pdf has changed
diff -r a46c6f313a0b -r bd8574dedd1b introduction.tex
--- a/introduction.tex	Tue Mar 25 11:28:28 2008 +0900
+++ b/introduction.tex	Tue Mar 25 15:51:53 2008 +0900
@@ -0,0 +1,83 @@
+\section{はじめに}
+
+\subsection{PS3 上でのレンダリング}
+PlayStation 3 (以下 PS3) に搭載された Linux を用いて、
+PS3 上で動くゲーム開発することができる。
+しかし、現在 GPU (Graphics Processing Unit) の詳細/API は
+一般には公開されていないため、GPU を使った描画はできない。
+ps3fb という Frame Buffer 上に 直接描画することはできるため、
+我々は Frame Buffer 上に描画するゲームフレームワークを提案してきた。
+
+まず我々は、OSMesa \cite{osmesa} という Frame Buffer Engine 用の
+レンダリングエンジン、マルチメディアライブラリの SDL \cite{sdl}、これら
+二つを用いて開発を行った。
+
+最初は PPE のみを利用してゲームプログラミングを行ってきた。
+例題として、一つの立方体を回転させるというプログラムの実行速度は
+約 18 FPS という結果となった。FPS (Frame Per Second) は、
+1秒間に何枚の画像が表示されているかを示している。
+
+これは非常に遅い結果で、その理由は、SPE を使用していないため、
+Cell の能力を十分発揮できていないからだと考えられる。
+
+次に、OSMesa の一部の機能を SPE に演算させることにより高速化を図っている
+ \Cite{akira} 。
+
+その際の実行結果を \tabref{tab:osmesa} に示す。
+
+\begin{table}[htbp]
+  \caption{実行速度 (描画領域:1920x1080)} \label{tab:osmesa}
+  \hbox to\hsize{\hfil
+    \begin{tabular}{l|l} \hline \hline
+      実行環境 & 実行速度\\ \hline
+      SDL(1.2)+OSMesa(6.5.2) & 18 FPS \\ 
+      SDL(1.2)+OSMesa(6.5.2) with SPE & 24 FPS \\ 
+      SDL(1.2.13)+OSMesa(7.0.2) with SPE & 43 FPS \\ \hline
+    \end{tabular}\hfil}
+\end{table}
+
+\tabref{tab:osmesa}より、SPE に処理を任せれば実行速度は
+速くなるということを示している。同時に、OSMesa を細分化し、
+できるだけ SPE を使うような設計ができれば
+より速くなる可能性を示すものである。
+
+しかし、OSMesa は巨大なマクロによるプログラム記述や
+コピーの多用、巨大な構造体等があり、細分化はもちろん、
+後に拡張をすることも難しい。
+
+\subsection{Many Core 上のプログラミング}
+従来の逐次型のプログラムでは、Cell といった Many Core の性能を
+十分に引き出すことは出来ない。
+
+並列実行には 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}
+
+並列プログラムの特徴として、デバッグが難しいことも挙げられる。
+実行が非決定的(同じ状態で実行しても同じ結果が異なる)場合があり、
+バグの状態を再現することが難しい。
+また、個々の Core 上のデータを調べる必要もある。
+
+
+\subsection{研究目的}
+我々は独自のレンダリングエンジンである
+Cerium \cite{gongo} を開発することにした。
+Cerium は、Rendering Engine、タスクの細分化を行い
+Cell の性能を十分に引き出すことを目的とした
+Task Manager、ゲームのルールを管理する Scene Graph で構成されている。
+
+Cerium は Cell 上だけでなく、Linux や Mac OS X 上でも
+動く、シーケンシャルなプログラムも実装することが出来る。
+並列プログラムとシーケンシャルプログラムの相互の変換は容易である。
+これにより、全体の動作のデバッグはシーケンシャルプログラムで行い、
+仕様が正しいと確認できたら、 Cell 上などの特有の環境で
+動作、デバッグを行えばいい。
diff -r a46c6f313a0b -r bd8574dedd1b manager-cr.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/manager-cr.tex	Tue Mar 25 15:51:53 2008 +0900
@@ -0,0 +1,77 @@
+
+\subsection{並列処理}
+
+Cell ではあらゆるレベルで並列に動作させることが求められる。
+ダブルバッファがその一例として挙げられる。
+前述した通り、Cell ではそれぞれのコアがメインメモリを
+直接参照することは出来ず、DMA 転送によりデータをやりとりする。
+DMA は CPU を介さず直接データ転送を行う方式である。そのため、
+DMA している間は SPE は何らかの処理を行うことが出来る。
+また、ダブルバッファリングを行うことで
+パイプライン処理が可能となる (\figref{fig-pipeline}) 。
+
+\begin{figure}[tb]
+  \begin{center}
+    \includegraphics[scale=0.43]{figure/pipeline.pdf}
+    \caption{Pipeline}
+    \label{fig-pipeline}
+  \end{center}
+\end{figure}
+
+パイプライン処理を入れた Task Manager の Scheduler を以下に示す。
+
+\begin{verbatim}
+
+    do {
+        task3->write();
+        task2->exec();
+        task1->read();
+
+        taskTmp = task3;
+        task3 = task2;
+        task2 = task1;
+        task1 = task1->next(this, taskTmp);
+    } while (task1);
+
+\end{verbatim}
+
+Task Manager を \figref{fig-cerium} に適用させると、
+\figref{fig-manager-pipeline} のようにパイプライン的に動作する。
+
+\begin{figure}[tb]
+  \begin{center}
+    \includegraphics[scale=0.36]{figure/manager-pipeline.pdf}
+    \caption{Task Manager が行う Pipeline}
+    \label{fig-manager-pipeline}
+  \end{center}
+\end{figure}
+
+\subsection{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 a46c6f313a0b -r bd8574dedd1b manager-task.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/manager-task.tex	Tue Mar 25 15:51:53 2008 +0900
@@ -0,0 +1,168 @@
+\subsection{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() で引数で登録する。
+
+\subsection{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;
+
+    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}
+}
+
+\subsection{Mail}
+\ref{sec:task} で述べたように、SPE から Task の終了を
+PPE に伝える必要があるが、その際の待ち合わせは避けるべきである。
+
+Cell では、PPE と SPE 間のメッセージのやりとりには
+Mail box という 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 のメールチェックは分離しない実装をした。
diff -r a46c6f313a0b -r bd8574dedd1b ps3.tex
--- a/ps3.tex	Tue Mar 25 11:28:28 2008 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,35 +0,0 @@
-\section{PS3 上でのゲーム開発}
-PlayStation 3 に 搭載された Linux を用いてゲーム開発する。
-しかし、GPU (RSX) の詳細が一般には公開されていないため、
-ps3fb という Frame Buffer 上に 直接描画する。
-
-先行研究 \Cite{akira} では、レンダリングエンジンとして
-OSMesa \cite{osmesa} + SDL \cite{sdl} を採用し、OSMesa の
-一部の機能を SPE に演算させることにより高速化を図っている。
-その際の実行結果を \tabref{tab:osmesa} に示す。
-FPS (Frame Per Second) は、1秒間に何枚の画像が表示されているかを示している。
-
-\begin{table}[htbp]
-  \caption{実行速度 (描画領域:1920x1080)} \label{tab:osmesa}
-  \hbox to\hsize{\hfil
-    \begin{tabular}{l|l} \hline \hline
-      実行環境 & 実行速度\\ \hline
-      SDL(1.2)+OSMesa(6.5.2) & 18 FPS \\ 
-      SDL(1.2)+OSMesa(6.5.2) with SPE & 24 FPS \\ 
-      SDL(1.2.13)+OSMesa(7.0.2) with SPE & 43 FPS \\ \hline
-    \end{tabular}\hfil}
-\end{table}
-
-\tabref{tab:osmesa}より、SPE に処理を任せれば実行速度は
-速くなるということを示している。同時に、OSMesa を細分化し、
-できるだけ SPE を使うような設計ができれば
-より速くなる可能性を示すものである。
-
-しかし、OSMesa は巨大なマクロによるプログラム記述や
-コピーの多用、巨大な構造体等があり、細分化はもちろん、
-後に拡張をすることも難しい。
-
-そこで、我々は独自のレンダリングエンジン (Cerium) を開発することにした。
-Cerium には、Rendering Engine、タスクの細分化を行い、
-Cell の性能を十分に引き出すことを目的とした
-Task Manager、ゲームのルールを管理する Scene Graph が実装されている。
diff -r a46c6f313a0b -r bd8574dedd1b sigos.bib
--- a/sigos.bib	Tue Mar 25 11:28:28 2008 +0900
+++ b/sigos.bib	Tue Mar 25 15:51:53 2008 +0900
@@ -47,3 +47,21 @@
 title = "Cell プロセッサ向け実行環境（SPU Centric Execution Model)",
 journal = "先進的計算基盤システムシンポジウム SACSIS",
 year  = 2006}
+
+@manual{libspe2,
+author = "{International Business Machines Corporation, Sony Computer Entertainment Incorporated, Toshiba Corporation.}",
+title  = "SPE Runtime Management Library",
+year   = 2006}
+
+@article{amdahl,
+author = "{Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, 
+David Holmes, and Doug Lea.}",
+title = "Java Concurrency in Prac-tice",
+journal = "Addison-Wesley Professional",
+year  = 2005},
+
+@misc{gongo,
+author = "{Wataru MIYAGUNI, Shinji KONO}",
+title  = "SourceForge.JP: Project Info - Cerium Rendering Engine", 
+howpublished = "\url{https://sourceforge.jp/projects/cerium/}"}
+
diff -r a46c6f313a0b -r bd8574dedd1b sigos.tex
--- a/sigos.tex	Tue Mar 25 11:28:28 2008 +0900
+++ b/sigos.tex	Tue Mar 25 15:51:53 2008 +0900
@@ -68,8 +68,7 @@
 
 % 本文はここから始まる
 
-%\input{introduction}   % はじめに
-\input{ps3}
+\input{introduction}   % 研究目的
 \input{cell}           % Cell
 \input{cerium}         % Cerium
 \input{cerium_dev}     % 開発過程