# HG changeset patch
# User tkaito
# Date 1294594645 -32400
# Node ID 36bcb274f1ff24d95474a114b4ca3e2bee8d9d6c
# Parent  434ddc4a39703a272f0cd0fa76c24dac2c16ce3f
cell isn't done yet.

diff -r 434ddc4a3970 -r 36bcb274f1ff paper/cell.tex
--- a/paper/cell.tex	Sun Jan 09 23:41:20 2011 +0900
+++ b/paper/cell.tex	Mon Jan 10 02:37:25 2011 +0900
@@ -1,7 +1,269 @@
 \chapter{CELL BROADBAND ENGINE} \label{chapter:cell}
 
 \section{Cell Broadband Engineの構造}
+
+ここでは研究、実験題材の対象となった Cell アーキテクチャについて説明する。
+
+Cell Broadband Engine \cite{cell} は、ソニー・コンピュータエンタテインメント、
+ソニー、IBM , 東芝によって開発されたマルチコア CPU である。
+Cell は、１基の制御系プロセッサコア PPE ( PowerPc Processor ELement ) と
+８基の演算系プロセッサコア SPE ( Synergistic Processor Element ) で構成される。
+各プロセッサコアは、EIB (Element Interconnect Bus) 
+と呼ばれる高速なバスで接続されている。また、EIB はメインメモリや
+外部入出力デバイスとも接続されていて、
+各プロセッサコアは EIB を経由してデータアクセスをおこなう。
+本研究で用いた PS3Linux (Yellow Dog Linux 6.2) では、6 個の SPE を
+使うことが出来る ( \figref{cell_arch} )
+
+この PPE と SPE の2種類の CPU を、プログラマ自身が用途に
+合わせて適切に使い分けるように考慮する必要がある。
+
+\begin{comment}
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.8]{./images/cell_arch.pdf}
+  \end{center}
+  \caption{Cell Broadband Engine Architecture}
+  \label{fig:cell_arch}
+\end{figure}
+\end{comment}
+
+
 \section{PPE (PowerPC Processor Element)}
+
+PPE は Cell Broadband Engine のメインプロセッサで、複数の SPE を
+コアプロセッサとして使用することができる汎用プロセッサである。
+メインメモリや外部デバイスへの入出力、SPEを制御する役割を担っている。
+PPU (PowerPC Processor Unit) は、
+PPE の演算処理を行うユニットで、PowerPC アーキテクチャをベースとした
+命令セットを持つ。PPSS (PowerPC Processor Storage Subsystem) は
+PPU からメインメモリへのデータアクセスを制御する
+ユニットである (\figref{cell_ppe}) 。
+
+\begin{comment}
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.8]{./images/cell_ppe.pdf}
+  \end{center}
+  \caption{PPE (PowerPC Processor Element)}
+  \label{fig:cell_ppe}
+\end{figure}
+\end{comment}
+
+
 \section{SPE (Synergistic Processor Element)}
+
+SPE には 256KB の Local Store (LS) と呼ばれる、SPE から唯一、
+直接参照できるメモリ領域があり、バスに負担をかける事無く
+並列に計算を進めることが出来る。SPE からメインメモリへは、
+直接アクセスすることは出来ず、SPE を構成する一つである
+MFC (Memory Flow Controller) へ、チャネルを介して DMA (Direct Memory Access)
+命令を送ることで行われる (\figref{cell_spe}) 。
+
+\begin{comment}
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.8]{./images/cell_spe.pdf}
+  \end{center}
+  \caption{SPE (Synergistic Processor Element)}
+  \label{fig:cell_spe}
+\end{figure}
+\end{comment}
+
 \section{Cell の基本性能}
+
+\subsection{DMA (Direct Memory Access)}
+
+\ref{sec:cell_spe}節 で述べた通り、SPE は LS 以外のメモリに
+直接アクセスすることができず、PPE が利用するメインメモリ上のデータに
+アクセスするには DMA を用いる。
+DMA (Direct Memory Access) 転送とは、CPU を介さずに周辺装置と
+メモリとの間でデータ転送ことで、Cell の場合は
+メインメモリと LS 間でデータの転送を行う。手順としては以下の様になる。
+
+\begin{comment}
+\begin{enumerate}
+  \item SPE プログラムが MFC (Memory Flow Controller) に対して
+    DMA 転送命令を発行
+  \item MFC が DMA Controller を介して DMA 転送を開始。
+    この間、SPE プログラムは停止しない。
+  \item DMA 転送の終了を待つ場合、SPE プログラム内で転送の完了を待つ
+\end{enumerate}
+\end{comment}
+
+この時、DMA 転送するデータとアドレスにはいくつか制限がある。
+転送データが 16 バイト以上の場合、データサイズは 16 バイトの倍数で、
+転送元と転送先のアドレスが 16 バイト境界に揃えられている必要がある。
+転送データが 16 バイト未満の場合、データサイズは 1,2,4,8 バイトで、
+転送サイズに応じた自然なアライメントである (転送サイズのバイト境界に
+揃えられている) ことが条件となる。
+
+\subsection{SIMD (Single Instruction Multiple Data)}
+Cell では、SPE に実装されている 128 ビットレジスタを用いて
+SIMD を行うことが出来る。SIMD とは、1 つの命令で
+複数のデータに対して処理を行う演算方式である (\figref{cell_simd}) 。
+
+\begin{comment}
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.8]{./images/cell_simd.pdf}
+  \end{center}
+  \caption{SIMD (Single Instruction Multiple Data)}
+  \label{fig:cell_simd}
+\end{figure}
+\end{comment}
+
+\figref{cell_simd} のスカラ演算は以下のような式に当てはまる。
+
+\begin{verbatim}
+int a[4] = {1, 2, 3, 4};
+int b[4] = {5, 6, 7, 8};
+int c[4];
+
+for (int i = 0; i < 4; i++) {
+    a[i] + b[i] = c[i];
+}
+\end{verbatim}
+
+これに対し、SIMD 演算は以下のようになる。
+
+\begin{verbatim}
+vector signed int va = {1, 2, 3, 4};
+vector signed int vb = {5, 6, 7, 8};
+vector signed int vc;
+
+vc = spu_add(va, vb);
+\end{verbatim}
+
+Cell の SIMD 演算では、vector 型の変数を用いる。
+
+このように、通常は 4 回計算するところを 1 回の計算で行うことが
+できる反面、すべての演算を 128 ビットで計算するため、なるべく
+効果的に行う様に工夫する必要がある。
+
+\begin{verbatim}
+int a, b, c;
+
+c = a + b;
+\end{verbatim}
+
+この様な計算の場合でも 128 ビット同士の演算を行うため、無駄が生じる。
+
+\subsection{Mailbox} \label{sec:cell_mailbox}
+
+Mailbox とは SPE の MFC 内の FIFO キューであり、PPE と SPE 間の 32 ビット
+メッセージの交換に用いられる。Mailbox では 3 つの振る舞いが
+出来る様に設計されている (\figref{cell_mailbox}) 。
+
+\begin{comment}
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.8]{./images/cell_mailbox.pdf}
+  \end{center}
+  \caption{Mailbox}
+  \label{fig:cell_mailbox}
+\end{figure}
+\end{comment}
+
+\begin{enumerate}
+\item SPU Inbound Mailbox \\
+  PPE から SPE へデータを渡すためのキュー。キューのエントリ数は
+  実装依存による \cite{cell} が、研究環境では最大4個までのデータを蓄積できる。
+  このキューが空の場合は、SPE は、データがメールボックスに書き込まれるまでは、 
+  命令でストールする。読み出すデータの順番は書き込んだ順番に保証されている。
+\item SPU Outbound Mailbox \\
+  SPE から PPE へのデータを渡すためのキュー。研究環境では最大1個までしか
+  データが蓄積できない。
+\item SPU Outbound interrupt Mailbox \\
+  SPU Outbound Mailbox とほとんど同じだが、このキューでは SPE から
+  キューにデータが書き込まれると、PPE に対して割り込みイベントが
+  発生し、データの読み出しタイミングを通知する事が出来る。
+\end{enumerate}
+
 \section{開発環境}
+
+\subsection{libSPE2}
+
+libSPE2 とは、PPE が SPE を扱うためのライブラリ群である \cite{libspe2} 。
+libSPE2 は SPE Context Creation、SPE Program Image Handling、
+SPE Run Control、SPE Event Handling、SPE MFC Problem State Facilities、
+Direct SPE Access for Applications という基本構成でできている。
+Cell の基本プログラムは次の様になる。
+
+\begin{enumerate}
+\item create N SPE context
+\item Load the appropriate SPE executable object into each SPE context's local store
+\item Create N threads
+\item Wait for all N threads to terminate
+\end{enumerate}
+
+\subsection{SPU C/C++ 言語拡張}
+SPE では基本的な C 言語の機能の他に、Cell 特有の拡張が行われている
+\cite{cell_cpp} 。
+\tabref{cell_cpp} に主な API を記す。
+
+\begin{table}[htb]
+  \begin{center}
+    \caption{SPU C/C++ 言語拡張 API}
+    \label{tab:cell_cpp}
+    \begin{tabular}{|l|l|}
+      \hline
+      spu\_mfcdma32 & DMA 転送を開始する \\
+      \hline
+      spu\_read\_in\_mbox & PPE からの mail を取得する \\
+      \hline
+      spu\_write\_out\_mbox & PPE へ mail を送信する \\
+      \hline
+      spu\_add、spu\_sub、spu\_mul & SIMD 演算 (加算、減算、乗算) \\
+      \hline
+    \end{tabular}
+  \end{center}
+\end{table}
+
+SPE を効率よく使う上で \tabref{cell_cpp} の様な Cell 特有の API や、
+SPE アセンブラ命令を学ぶことが必要となる。
+
+\subsection{SPURS}
+
+ここでは、現在発表されている Cell の開発環境である SPURS について説明する。
+
+SPURS \cite{spurs} は、閉じた並列分散と考えることができる Cell の環境で、
+いかに効率よく動作させるかということを考えたシステムである。
+
+Cell の性能を存分に生かすためには SPE を効率よく使い切ることであり、
+SPE の動作を止めることなく、同期を最小限に行う必要がある。 
+そこで SPURS では SPE を効率よく利用するために、PPE に依存せずに SPE コードを 
+選択し、実行することと機能は効率重視で割り切ることを挙げている。
+そのため、SPE 上にカーネルを組み込んでいる。
+
+アプリケーションを複数 SPE で実行するとき、アプリケーションプログラムを
+出来るだけ小さな単位(タスク)に分割し、通信ライブラリを用いて
+タスク間を依存関係で結合する。
+LS 常駐のカーネルが、実行可能なタスクを選んで実行していく
+(\figref{cell_spurs_task}) 。
+
+\begin{comment}
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.6]{./images/cell_spurs_task}
+  \end{center}
+  \caption{SPURS Task}
+  \label{fig:cell_spurs_task}
+\end{figure}
+\end{comment}
+
+これらの処理はデータを扱うため、SPURS はパイプラインで実行される
+(\figref{cell_spurs_pipeline}) 。
+
+\begin{comment}
+\begin{figure}[htb]
+  \begin{center}
+    \includegraphics[scale=0.6]{./images/cell_spurs_pipeline}
+  \end{center}
+  \caption{SPURS Pipeline}
+  \label{fig:cell_spurs_pipeline}
+\end{figure}
+\end{comment}
+
+以上から、SPURS は複数の SPE を効率よく使うためのライブラリとして
+優れた物であると思われるが、現在一般には公開されていない。