# HG changeset patch
# User admin@mb22-no-macbook.local
# Date 1237182570 -32400
# Node ID 25b7a105f66572e2fd40e0b5f138c4818c6019e4

test

diff -r 000000000000 -r 25b7a105f665 Makefile
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Makefile	Mon Mar 16 14:49:30 2009 +0900
@@ -0,0 +1,79 @@
+TARGET = sigos
+
+LATEX   = platex-utf8
+BIBTEX  = jbibtex
+DVIPS   = dvips
+DVIPDFM = dvipdfmx
+RM      = rm -f
+
+#  Option definitions
+DVIPDFMOPT = 
+DVIPSOPT   = -D 720 -mode esphi -O 0mm,0mm -N0 
+
+#  Suffixes definitions
+.SUFFIXES: .tex .dvi
+
+#  Recipes
+all: pdf# $(TARGET).ps
+	open $(TARGET).pdf
+dvi:
+	@echo "----------- make dvi file ($(TARGET).dvi) ----------"
+	$(LATEX) $(TARGET)
+	$(BIBTEX) $(TARGET)
+	$(LATEX) $(TARGET)
+	$(LATEX) $(TARGET)
+pdf: dvi
+	$(DVIPDFM) $(DVIPDFMOPT) $(TARGET)
+ps: dvi
+	$(DVIPS) $(DVIPSOPT) $(TARGET)
+
+clean:
+	$(RM) *~ \#*
+	@if [ -f $(TARGET).aux ];\
+		then $(RM) $(TARGET).aux;\
+	fi
+	@if [ -f $(TARGET).log ];\
+		then $(RM) $(TARGET).log;\
+	fi
+	@if [ -f $(TARGET).toc ];\
+		then $(RM) $(TARGET).toc;\
+	fi
+	@if [ -f $(TARGET).lof ];\
+		then $(RM) $(TARGET).lof;\
+	fi
+	@if [ -f $(TARGET).lot ];\
+		then $(RM) $(TARGET).lot;\
+	fi
+	@if [ -f $(TARGET).big ];\
+		then $(RM) $(TARGET).big;\
+	fi
+	@if [ -f $(TARGET).bbl ];\
+		then $(RM) $(TARGET).bbl;\
+	fi
+	@if [ -f $(TARGET).ilg ];\
+		then $(RM) $(TARGET).ilg;\
+	fi
+	@if [ -f $(TARGET).idx ];\
+		then $(RM) $(TARGET).idx;\
+	fi
+	@if [ -f $(TARGET).ind ];\
+		then $(RM) $(TARGET).ind;\
+	fi
+	@if [ -f $(TARGET).dvi ];\
+		then $(RM) $(TARGET).dvi;\
+	fi
+	@if [ -f $(TARGET).ps ];\
+		then $(RM) $(TARGET).ps;\
+	fi
+	@if [ -f $(TARGET).pdf ];\
+		then $(RM) $(TARGET).pdf;\
+	fi
+	@if [ -f $(TARGET).out ];\
+		then $(RM) $(TARGET).out;\
+	fi
+	@if [ -f $(TARGET).bbl ];\
+		then $(RM) $(TARGET).bbl;\
+	fi
+	@if [ -f $(TARGET).blg ];\
+		then $(RM) $(TARGET).blg;\
+	fi
diff -r 000000000000 -r 25b7a105f665 paper/Makefile
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/Makefile	Mon Mar 16 14:49:30 2009 +0900
@@ -0,0 +1,79 @@
+TARGET = sigos
+
+LATEX   = platex-utf8
+BIBTEX  = jbibtex
+DVIPS   = dvips
+DVIPDFM = dvipdfmx
+RM      = rm -f
+
+#  Option definitions
+DVIPDFMOPT = 
+DVIPSOPT   = -D 720 -mode esphi -O 0mm,0mm -N0 
+
+#  Suffixes definitions
+.SUFFIXES: .tex .dvi
+
+#  Recipes
+all: pdf# $(TARGET).ps
+	open $(TARGET).pdf
+dvi:
+	@echo "----------- make dvi file ($(TARGET).dvi) ----------"
+	$(LATEX) $(TARGET)
+	$(BIBTEX) $(TARGET)
+	$(LATEX) $(TARGET)
+	$(LATEX) $(TARGET)
+pdf: dvi
+	$(DVIPDFM) $(DVIPDFMOPT) $(TARGET)
+ps: dvi
+	$(DVIPS) $(DVIPSOPT) $(TARGET)
+
+clean:
+	$(RM) *~ \#*
+	@if [ -f $(TARGET).aux ];\
+		then $(RM) $(TARGET).aux;\
+	fi
+	@if [ -f $(TARGET).log ];\
+		then $(RM) $(TARGET).log;\
+	fi
+	@if [ -f $(TARGET).toc ];\
+		then $(RM) $(TARGET).toc;\
+	fi
+	@if [ -f $(TARGET).lof ];\
+		then $(RM) $(TARGET).lof;\
+	fi
+	@if [ -f $(TARGET).lot ];\
+		then $(RM) $(TARGET).lot;\
+	fi
+	@if [ -f $(TARGET).big ];\
+		then $(RM) $(TARGET).big;\
+	fi
+	@if [ -f $(TARGET).bbl ];\
+		then $(RM) $(TARGET).bbl;\
+	fi
+	@if [ -f $(TARGET).ilg ];\
+		then $(RM) $(TARGET).ilg;\
+	fi
+	@if [ -f $(TARGET).idx ];\
+		then $(RM) $(TARGET).idx;\
+	fi
+	@if [ -f $(TARGET).ind ];\
+		then $(RM) $(TARGET).ind;\
+	fi
+	@if [ -f $(TARGET).dvi ];\
+		then $(RM) $(TARGET).dvi;\
+	fi
+	@if [ -f $(TARGET).ps ];\
+		then $(RM) $(TARGET).ps;\
+	fi
+	@if [ -f $(TARGET).pdf ];\
+		then $(RM) $(TARGET).pdf;\
+	fi
+	@if [ -f $(TARGET).out ];\
+		then $(RM) $(TARGET).out;\
+	fi
+	@if [ -f $(TARGET).bbl ];\
+		then $(RM) $(TARGET).bbl;\
+	fi
+	@if [ -f $(TARGET).blg ];\
+		then $(RM) $(TARGET).blg;\
+	fi
diff -r 000000000000 -r 25b7a105f665 paper/bib.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/bib.tex	Mon Mar 16 14:49:30 2009 +0900
@@ -0,0 +1,2 @@
+\bibliographystyle{ipsjunsrt}
+\bibliography{sigos}
diff -r 000000000000 -r 25b7a105f665 paper/bibliography.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/bibliography.tex	Mon Mar 16 14:49:30 2009 +0900
@@ -0,0 +1,51 @@
+
+\begin{thebibliography}{10}
+
+\bibitem{osmesa}
+The Mesa 3D Graphics Library, \url{http://www.mesa3d.org/}.
+
+\bibitem{sdl}
+Simple DirectMedia Layer, \url{http://www.libsdl.org/}.
+
+\bibitem{akira}
+{Akira KAMIZATO.}: Cell を用いたゲームフレームワークの提案，琉球大学工学部情報工学科平成19年度学位論文(修士) (2008).
+
+\bibitem{amdahl}
+{Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, and Doug
+  Lea.}: Java Concurrency in Prac-tice, {\em Addison-Wesley Professional}
+  (2005).
+
+\bibitem{gongo}
+{Wataru MIYAGUNI, Shinji KONO}: SourceForge.JP: Project Info - Cerium Rendering
+  Engine, \url{https://sourceforge.jp/projects/cerium/}.
+
+\bibitem{cell}
+{Sony Corporation.}: {\em Cell broadband engine architecture} (2005).
+
+\bibitem{chiaki}
+{Chiaki SUGIYAMA.}: SceneGraph と StatePattern
+  を用いたゲームフレームワークの設計と実装，琉球大学工学部情報工学科平成19年度卒業論文 (2008).
+
+\bibitem{blender}
+{Satoshi Yamasaki.}: Blender.jp - Blender Japanese Website,
+  \url{http://blender.jp/}.
+
+\bibitem{libspe2}
+{International Business Machines Corporation, Sony Computer Entertainment
+  Incorporated, Toshiba Corporation.}: {\em SPE Runtime Management Library}
+  (2006).
+
+\bibitem{spurs}
+{Keisuke INOUE.}: Cell プロセッサ向け実行環境（SPU Centric Execution
+  Model)，先進的計算基盤システムシンポジウム SACSIS (2006).
+
+\bibitem{kono}
+{Shinji KONO.}: 検証を自身で表現できるハードウェア、ソフトウェア記述言語
+  Continuation ba sed C と、その Cell
+  への応用，電子情報通信学会VLSI設計技術研究会 (2008).
+
+\bibitem{fuchita}
+{Yoshihiko, FUCHITA.}: 分散プログラミングモデル Federated Linda
+  と分散デバッグ開発，琉球大学工学部情報工学科平成19年度学位論文(修士) (2008).
+
+\end{thebibliography}
diff -r 000000000000 -r 25b7a105f665 paper/cell.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/cell.tex	Mon Mar 16 14:49:30 2009 +0900
@@ -0,0 +1,63 @@
+\section{Cell}
+Cell Broadband Engine \cite{cell} は、SCEI と IBM によって開発された
+CPU である。2 thread の PPE (PowerPC Processor Element) と、
+8 個の SPE (Synergetic Processor Element) を持ち、
+EIB と呼ばれる高速リングバスで構成されている。
+本研究で用いた PS3Linux (Fedora 8) では、
+6 個の SPE を使うことができる (\figref{fig-cbe}) 。
+
+\begin{figure}[tb]
+  \begin{center}
+    \includegraphics[scale=0.41]{figure/cbe.pdf}
+    \caption{Cell Architecture}
+    \label{fig-cbe}
+  \end{center}
+\end{figure}
+
+SPE には 256KB の Local Store (LS) と呼ばれる、SPE から唯一直接参照できる
+メモリ領域があり、バスに負担をかけることなく並列に計算を進めることが出来る。
+SPE からメインメモリへは、直接アクセスすることは出来ず、
+SPE を構成する一つである MFC (Memory Flow Controller) へ、チャネルを介して
+DMA (Direct Memory Access) 命令を送ることで行われる (\figref{fig-cbe-spe}) 。
+
+\begin{figure}[tb]
+  \begin{center}
+    \includegraphics[scale=0.6]{figure/cbe-spe.pdf}
+    \caption{Synergetic Processor Element}
+    \label{fig-cbe-spe}
+  \end{center}
+\end{figure}
+
+
+SPE はグラフィックスに適した、4 つの固定小数点、浮動小数点を
+同時に演算する命令などを持ち、PPE に比べて高速な演算が可能である。
+そのため、ほとんどの演算を SPE 上で行わせることが推奨されている。
+
+
+\subsection{SPURS}
+ここでは、現在発表されている Cell の開発環境である SPURS \cite{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 の動作を止めることなく、同期を最小限に行う必要がある。 
+そこで SPURS では SPE を効率よく利用するために、PPE に依存せずに SPE コードを 
+選択し、実行することと機能は効率重視で割り切ることを挙げている。
+現在 SPURS は一般には公開されていない。
diff -r 000000000000 -r 25b7a105f665 paper/cerium-manager.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/cerium-manager.tex	Mon Mar 16 14:49:30 2009 +0900
@@ -0,0 +1,277 @@
+\subsection{Task Manager}
+Task Manager は、Task と呼ばれる分割された各プログラムを
+管理するライブラリである。Task 同士の依存関係を考慮しながら
+メモリ上にマッピングし、SPE 上ではそのプログラムを
+DMA 転送によりロードする (\figref{fig-manager-load}) 。
+SPE は 256KB という小さなデータ量しか持てず、
+大量のプログラムを全て SPE 上に置いておくことはできない可能性がある。
+そのため、必要な時に必要な実行プログラムだけが SPE 上にロード
+されていることが望ましい。
+
+\begin{figure}[tb]
+  \begin{center}
+    \includegraphics[scale=0.45]{figure/manager-load.pdf}
+    \caption{Task Manager}
+    \label{fig-manager-load}
+  \end{center}
+\end{figure}
+
+現在実装されている Task Manager の API を \tabref{tab:manager-api} に示す。
+
+\begin{table}[htbp]
+  \caption{Task Manager API} \label{tab:manager-api}
+  \hbox to\hsize{\hfil
+  \begin{tabular}{r|l} \hline \hline
+    create\_task & Task を生成する \\ \hline
+    spawn        & Task を実行 Task Queue に登録する \\ \hline
+    set\_depend  & Task の依存関係の考慮 \\\hline
+    set\_cpu     & Task を実行する CPU の設定 \\ \hline
+    run          & 実行 Task Queue の実行 \\ \hline
+  \end{tabular}\hfil}
+\end{table}
+
+
+以下に Task Manager を使った記述例を示す。
+
+{\small
+\begin{verbatim}
+
+int
+main(void)
+{
+    TaskManager *manager = new TaskManager;
+    Task *task1, *task2;
+
+    /**
+     * cmd  : 実行するタスクID
+     * size : in_addr で取得するデータのバイト数
+     * in_addr  : 入力データ元アドレス
+     * out_addr : 出力データ先アドレス
+     */
+    task1 = create_task(CMD_RUN1, size1,
+                        in_addr1, out_addr2);
+    task2 = create_task(CMD_RUN2, size2,
+                        in_addr2, out_addr2);
+
+    task1->spawn();
+    task2->spawn();
+
+    manager->run();
+
+    return 0;
+}
+
+\end{verbatim}
+}
+
+ここからは、Task Manager を構成する特徴について述べる。
+
+\subsubsection{Task の定義}
+タスクの定義を以下に示す。
+
+\begin{verbatim}
+
+    class Task {
+    public:
+        int command;
+        int size;
+        unsigned int in_addr;
+        unsigned int out_addr;
+        struct task *self;
+    };
+
+    class HTask : public Task {
+    public:
+        // 自分を待っているタスクキュー
+        TaskQueue wait_me;
+
+        // 自分が待つタスクキュー
+        TaskQueue wait_i;
+
+        // 実行する CPU 
+        CPU_TYPE  cpu_type;
+    };
+
+\end{verbatim}
+
+Task クラスは SPE が実行するタスクの単位オブジェクトである。
+SPE はメインメモリの \verb|in_addr| から DMA で入力データを取得し、
+command に対応するコードを実行し、
+結果を メインメモリの \verb|out_addr| に DMA で送信する。
+これらの処理はパイプラインに沿って動作する (\ref{sec:pipeline}) 。
+
+また、SPE が Task を取得する際、一つずつではなく、Task の集合である
+TaskList を DMA で取得する。DMA の回数を抑えることで
+実行速度を上げるためであるが、TaskList のサイズを大きくしすぎると
+SPE の LS に入らなくなる可能性がある。本研究で並列に実行するタスクの数は、
+\figref{fig-cerium} の (SceneGraph $\rightarrow$ Polygonpack) タスクと
+(PolygonPack $\rightarrow$ SpanPack) タスク、そして SpanPack の数 $\times$
+Rendering タスクとなる。そのため、SPE を 6 個使うと考えると
+TaskList に格納する Task の数は最大で 25 としている。
+
+HTask クラスは TaskManager で管理する実行前のタスクオブジェクトである。
+\verb|wait_me, wait_i| はタスク依存の条件 (\ref{sec:task}) に、
+\verb|cpu_type| は PPE と SPE のタスクの切り替え (\ref{sec:change}) に用いる。
+
+
+\subsubsection{スケジューラ} \label{sec:pipeline}
+Cell ではそれぞれのコアがメインメモリを
+直接参照することは出来ず、DMA 転送によりデータをやりとりする。
+DMA は CPU を介さず直接データ転送を行う方式である。
+SPE は DMA 完了を待たずに他の処理を行うことが出来るので、
+DMA のレイテンシを隠すことが出来る。
+また、ダブルバッファリングを行うことで
+パイプライン処理が可能となる (\figref{fig-pipeline}) 。
+
+\begin{figure}[tb]
+  \begin{center}
+    \includegraphics[scale=0.43]{figure/pipeline.pdf}
+    \caption{Pipeline}
+    \label{fig-pipeline}
+  \end{center}
+\end{figure}
+
+パイプライン処理を入れたスケジューラを以下に示す。
+
+\begin{verbatim}
+
+    SpeTaskBase *task1, *task2, *task3;
+
+    do {
+        task3->write();
+        task2->exec();
+        task1->read();
+
+        taskTmp = task3;
+        task3 = task2;
+        task2 = task1;
+        task1 = task1->next();
+    } while (task1);
+
+\end{verbatim}
+
+TaskList にある Task が全て終了し、PPE からプログラム終了のメッセージを
+受け取ったら while 文を抜ける。
+
+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}
+
+SpeTaskBase クラスは、スケジューラによって実行されるオブジェクトである。
+スケジューラ自身のタスクとして、以下のようなタスクがある。
+これらのオブジェクトは全て SpeTaskBase を継承している。
+
+\begin{itemize}
+\item SpeMail : PPE からのメッセージを待つ
+\item SpeTaskList : PPE から TaskList を取得する
+\item SpeTask : TaskList にある Task を実行する
+\item SpeExit : SPE を終了させる
+\end{itemize}
+
+
+\subsubsection{タスク依存}  \label{sec:task}
+Task Manager はタスク依存を解決する機能を持っている。