\chapter{CELL BROADBAND ENGINE} \label{chapter:cell}

\section{Cell Broandband Engineの構造}

ここでは研究、実験題材の対象となった Cell アーキテクチャについて説明する。
Cell Brodband Engine \cite{cell} は、SCEI と IBM によって開発された
CPU である。
2 thread の PPE (PowerPC Processor Element) と、8個の SPE
(Synergistic Processor Element) からなる 非対称なマルチコアプロセッサであり、
高速リングバス である EIB (Element Interface Bus) で構成されている。
本研究で用いた PS3Linux (Fedora 10, Yellow Dog Linux 6.0) では、
6個の SPE を使う事ができる (\figref{cell_arch}) 。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.8]{./images/cell_arch.pdf}
  \end{center}
  \caption{Cell Brodband Engine Architecture}
  \label{fig:cell_arch}
\end{figure}



\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{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}

\section{SPE (Synergistic Processor Element)} \label{sec:cell_spe}

SPE には 256KB の Local Store (LS) と呼ばれる、SPE から唯一、
直接参照できるメモリ領域がり、バスに負担をかける事無く
並列に計算を進めることが出来る。SPE からメインメモリへは、
直接アクセスすることは出来ず、SPE を構成する一つである
MFC (Memory Flow Controller) へ、チャネルを介して DMA (Direct Memory Access)
命令を送ることで行われる (\figref{cell_spe}) 。

\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}


\section{Cell の基本機能}

\subsection{DMA}
\ref{sec:cell_spe}節 で述べた通り、SPE は LS 以外のメモリに
直接アクセスすることができず、PPE が利用するメインメモリ上のデータに
アクセスするには DMA を用いる。
DMA (Direct Memory Access) 転送とは、CPU を介さずに周辺装置と
メモリとの間でデータ転送ことで、Cell の場合は
メインメモリと LS 間でデータの転送を行う。手順としては以下の様になる。

\begin{enumerate}
  \item SPE プログラムが MFC (Memory Flow Controller) に対して
    DMA 転送命令を発行
  \item MFC が DMA Controller を介して DMA 転送を開始。
    この間、SPE プログラムは停止しない。
  \item DMA 転送の終了を待つ場合、SPE プログラム内で転送の完了を待つ
\end{enumerate}

この時、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{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}

\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{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.8]{./images/cell_mailbox.pdf}
  \end{center}
  \caption{Mailbox}
  \label{fig:cell_mailbox}
\end{figure}

\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 Acceess 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 は、閉じた並列分散と考えることができる Cell の環境で、
いかに効率よく動作させるかということを考えたシステムである。

Cell の性能を存分に生かすためには SPE を効率よく使い切ることであり、
SPE の動作を止めることなく、同期を最小限に行う必要がある。 
そこで SPURS では SPE を効率よく利用するために、PPE に依存せずに SPE コードを 
選択し、実行することと機能は効率重視で割り切ることを挙げている。
そのため、SPE 上にカーネルを組み込んでいる。

アプリケーションを複数 SPE で実行するとき、アプリケーションプログラムを
出来るだけ小さな単位(タスク)に分割し、通信ライブラリを用いて
タスク間を依存関係で結合する。
LS 常駐のカーネルが、実行可能なタスクを選んで実行していく
(\figref{cell_spurs_task}) 。

\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}

%また、アプリケーションを分割するとき、プログラムがデータを伴うとき、
%ジョブに分割し、並べ替えた上で、カーネルがジョブリストから
%ジョブを取得して実行する。

これらの処理はデータを扱うため、SPURS はパイプラインで実行される
(\figref{cell_spurs_pipeline}) 。

\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}

以上から、SPURS は複数の SPE を効率よく使うためのライブラリとして
優れた物であると思われるが、現在一般には公開されていない。