\chapter{並列プログラミングフレームワーク Cerium}
Cerium は PlayStation 3(PS3) に搭載された Cell Broadband Engine(Cell) 向けの Fine-Grain TaskManager として当研究室で設計・開発されたフレームワークである。
本章では Cerium の実装について説明する。

\section{Cerium の概要}
Cerium は、TaskManager, SceneGraph, Rendering Engine の3つの要素から構成される。
Cell 用のゲームフレームワークとして開発されたが、現在では Multi-Core CPU, GPU も計算資源として利用可能な汎用計算フレームワークとなっている。

\section{TaskManager}
TaskManager は、Task と呼ばれる分割されたプログラムを管理する。
サブルーチンまたは関数が Task の単位となる。
TaskManager が提供する API を表:\ref{table:TaskManager_api}に示す。

\begin{table}[htpb]
  \begin{center}
    \small
    \begin{tabular}[htpb]{|c|l|} \hline
      create\_task & Task の生成 \\ \hline
      allocate     & 環境のアライメントに考慮した allocator \\ \hline
      set\_inData  & Task への入力データのアドレスを追加 \\ \hline
      set\_outData & Task からのデータ出力先アドレスを追加 \\ \hline
      set\_param   & Task のパラメータ(32 bits) \\ \hline
      wait\_for    & Task の依存関係を設定 \\ \hline
      set\_cpu     & Task を実行する Device の設定 \\ \hline
      spawn        & Task を Queue に登録 \\ \hline
      iterate      & データ並列で実行する Task として Queue に登録 \\ \hline
    \end{tabular}
    \caption{TaskManager API}
    \label{table:TaskManager_api}
  \end{center}
\end{table}

TaskManager は ActiveTaskList と WaitTaskList の2種類の Queue を持つ。
依存関係を解決する必要がある Task は WaitTaskList に入れられる。
TaskManger によって依存関係が解決されると ActiveTaskList に移され、実行可能な状態となる。
実行可能な状態となった Task は set\_cpu で指定された Device に対応した Scheduler に転送し実行される。
図:\ref{fig:createTask}は Cerium が Task を生成/実行する場合のクラスの構成である。

\begin{figure}[!ht]
  \begin{center}
    \includegraphics[scale=0.6]{images/createTask.pdf}
  \end{center}
  \caption{TaskManager}
  \label{fig:createTask}
\end{figure}

\section{Cerium における Task}
Task は TaskManager の API を利用して生成する。
生成された Task には以下の要素を設定することができる。

\begin{itemize}
\item input data \\
  set\_inData を用いて設定する Task が実行する処理に必要なデータの入力元となるアドレス。
  関数を呼び出す際の引数に相当する。
  汎用ポインタ(void* 型) なので Task 側で適切なキャストを行う必要がある。
\item output data \\
  set\_outData を用いて設定する Task が処理したデータの出力先となるアドレス。
  関数の戻り値に相当する。
\item parameter \\
  set\_param を用いて設定するデータの処理に必要な実数値(index 等)。
\item cpu type \\
  set\_cpu を用いて設定する Task が実行される Device の組み合わせ。
  Cell, Multi-Core CPU, GPU またはこれらの組み合わせを指定することができる。
\item dependency \\
  wait\_for を用いて設定する他の Task との依存関係。
  依存関係が解決された Task は実行可能な状態となる。
\end{itemize}

ソースコード:\ref{inittwice_cerium} に Task を生成する例題を示す。

input data として int 型の配列を受け取り、各要素を2倍にして output data に格納する twice という例題である。
CPU を用いてデータ並列で実行する Task を生成している。
set\_cpu で GPU を指定することで GPU を用いて実行される。

\lstinputlisting[label=inittwice_cerium, caption=Task の生成]{src/init_twice_cerium.cc}

CPU 上で実行される Task, GPU 上で実行される kernel はソースコード:\ref{twice_task_cerium}, ソースコード\ref{twice_task_cuda} の通りになる。

Task には実行時に必要なデータが格納されている SchedTask, 設定した Input/Output Data が格納されている Buffer が渡される。

\lstinputlisting[label=twice_task_cerium, caption=実行される Task]{src/twice_cerium.cc}
\lstinputlisting[label=twice_task_cuda, caption=実行される kernel]{src/twice_cuda.cu}

\section{Task のパイプライン実行}
Cell(図:\ref{fig:cellarch})や GPU(図:\ref{fig:gpuarch})のように異なるメモリ空間を持つ Device を計算資源として利用するにはデータの転送が必要になる。
このデータ転送がボトルネックとなり、並列度が低下してしまう。
転送処理をオーバーラップし、並列度を維持するために Cerium では Task のパイプライン実行をサポートしている。

\begin{figure}[htpd]
  \begin{minipage}[t]{0.5\hsize}
    \begin{center}
      \includegraphics[scale=0.5]{images/cell_arch.pdf}
    \end{center}
    \caption{Cell Architecture}
    \label{fig:cellarch}
  \end{minipage}
  \begin{minipage}[t]{0.5\hsize}
    \begin{center}
      \includegraphics[scale=0.5]{images/gpu_arch.pdf}
    \end{center}
    \caption{GPU Architecture}
    \label{fig:gpuarch}
  \end{minipage}
\end{figure}

TaskManager である程度の Task をまとめた TaskList を生成し、実行する Device に対応した Scheduler に転送する。
受け取った TaskList に沿ってパイプラインを組み Task を実行していく。
TaskList でまとめられている Task は依存関係が解決されているので自由にパイプラインを組むことが可能である。
実行完了は TaskList 毎ではなく、Task 毎に通知される。
図:\ref{fig:scheduler}は TaskList を受け取り、Task をパイプラインで処理していく様子である。

\newpage

\begin{figure}[ht]
  \begin{center}
    \includegraphics[scale=0.6]{images/scheduler.pdf}
  \end{center}
  \caption{Scheduler}
  \label{fig:scheduler}
\end{figure}

\section{マルチコアへの対応}
Cell には MailBox という機能がある。
MailBox を用いることで双方向のデータの受け渡しが可能になる。
FIFO キュー構造を持つ MailBox に対応させる形で Synchronized Queue 用いて Multi Core CPU 用の TaskManager に MailBox を移植した。
Synchronized Queue は Queue を操作しているスレッドが常に1つになるようにバイナリセマフォを用いて制御する。

Cell では MailBox 以外に DMA 転送を使用してデータの受け渡しすることができる。
DMA 転送は CPU を介さずに周辺装置とメモリ間でデータ転送を行う方式である。
Cerium では DMA 転送を用いて Cell で実行することが可能である。
Multi Core CPU 上で実行する場合、メモリ空間を共有しているので DMA 転送を行なっている部分をポインタ渡しを行うように修正し、直接アクセスさせることでデータ転送の速度の向上が見込める。

\newpage

\section{データ並列による実行}
並列処理の方法としてタスク並列とデータ並列の2つがある。

タスク並列は Task 毎にデータを準備し、管理スレッドが個別に生成した Task を CPU に割り当てることで並列処理する方法である。
異なる処理を同時に実行することができるというメリットがあるが、データ群の各要素に対して同じ処理をしたいときタスク並列では要素毎に同じ処理をする Task を生成する必要があり、ほとんど同一な大量の Task によってメモリを圧迫する場合がある。
また、大量な Task の生成自体が大きなオーバーヘッドになる。

データ並列はあるデータ群を大量な Task で共有し、Task 実行時に処理範囲を計算し、その範囲にのみ処理を行うことで並列処理する方法である。
実行スレッドで Task の生成・実行が行われるので、メモリの圧迫や Task 生成によるオーバーヘッドを抑えられる。
並列化部分が全て同じ処理である場合、データ並列による実行のほうがタスク並列より有効である。

いままで Cerium における並列処理はタスク並列だったが、データ並列のよる実行もサポートした。

データ並列による実行では処理範囲を決定するための情報として index が必要になる。
CPU による実行では SchedTask を参照(ソースコード:\ref{twice_task_cerium} 23行目)、GPU による実行では組み込み変数を参照(ソースコード:\ref{twice_task_cuda} 11行目)することで index を取得することができる。

データの長さが10、CPU の数が4でデータ並列による実行をした場合の index の割当は表\ref{table:dataparallel_index} の通りになる。

\begin{table}[htpb]
  \begin{center}
    \small
    \begin{tabular}[htpb]{|c||c|c|c|c|}
      \hline
      stage & CPU0 & CPU1 & CPU2 & CPU3 \\
      \hline
      \hline
      1 & 0 & 1 & 2 & 3 \\
      \hline
      2 & 4 & 5 & 6 & 7 \\
      \hline
      3 & 8 & 9 &   &   \\
      \hline
    \end{tabular}
    \caption{index の割り当て}
    \label{table:dataparallel_index}
  \end{center}
\end{table}

\newpage

\section{GPGPU への対応}
GPU の演算資源を Cerium から利用するために OpenCL, CUDA を用いた GpuScheduler, CudaScheduler を実装した。
OpenCL, CUDA 単体を用いて GPGPU を行う場合、依存関係を記述する必要がある
しかし、Cerium には依存関係を解決する TaskManager があるので GpuScheduler, CudaScheduler は受け取った TaskList を元に GPU を制御して GPGPU を行えばよい。

GPU はメモリ空間が異なる(図\ref{fig:gpuarch})のでデータ転送が大きなオーバーヘッドになる。
なので、kernel 実行中にデータ転送を行うなどしてデータ転送をオーバーラップする必要がある。
CUDA で GPU を制御するには同期命令を使う方法と非同期命令を使う方法があるが、同期命令ではデータ転送をオーバーラップすることが出来ないので非同期命令を利用して GPU を制御する。
非同期命令は Stream に発行することで利用することができる。
Stream に発行された命令は発行された順序で実行される。
非同期命令と Stream を利用してデータ転送をオーバラップするには複数の Stream を準備して、Host から Device への転送・kernel の実行・Device から Host への転送を1セットとして各 Stream に発行することで実現できる。
同期命令を使う場合と非同期命令を使う場合の実行の様子は図:\ref{fig:stream}の通りである。

\begin{figure}[ht]
  \begin{center}
    \includegraphics[scale=0.45]{images/stream.pdf}
  \end{center}
  \caption{Overlap Data Transfer}
  \label{fig:stream}
\end{figure}

\newpage

\section{Cerium の評価}
Bitonic Sort, Word Count, Fast Fourier Transform(FFT) の3つの例題を用いて Cerium を評価する。

測定環境は表:\ref{table:firefly}、測定に用いる GPU は表\ref{table:k5000}の通りである。

\begin{table}[htpb]
  \begin{center}
    \small
    \begin{tabular}[htpb]{|c||c|}
      \hline
      Model & MacPro Mid 2010 \\
      \hline
      OS & Mac OS X 10.10.\\
      \hline
      Memory & 16GB \\
      \hline
      CPU & 2 x 6-Core Intel Xeon 2.66GHz \\
      \hline
      GPU & NVIDIA Quadro K5000 \\
      \hline
    \end{tabular}
    \caption{測定環境}
    \label{table:firefly}
  \end{center}
\end{table}

\begin{table}[htpb]
  \begin{center}
    \small
    \begin{tabular}[htpb]{|c||c|}
      \hline
      Cores & 1536 \\
      \hline
      Clock Speed & 706MHz \\
      \hline
      Memory Size & 4GB GDDR5 \\
      \hline
      Memory Bandwidth & 173 GB/s \\
      \hline
    \end{tabular}
    \caption{Quadro K5000}
    \label{table:k5000}
  \end{center}
\end{table}

\subsection{Bitonic Sort}
Bitonic Sort は並列処理に向いたソートアルゴリズムである。
代表的なソートアルゴリズムである Quick Sort も並列処理することが、Quick Sort はソートの過程で並列度が変動するので自明な台数効果が出づらい。
一方、Bitonic Sort は最初から最後まで並列度が変わらずに並列処理による恩恵を得やすい。
図:\ref{fig:bitonic}は要素数8のデータに対する Bitonic Sort のソーティングネットワークである。

\newpage

\begin{figure}[!h]
  \begin{center}
    \includegraphics[scale=0.5]{images/bitonic.pdf}
  \end{center}
  \caption{Sorting Network : bitonic sort}
  \label{fig:bitonic}
\end{figure}

Bitonic Sort の並列処理に用いられる Task は2点間のの比較・交換を行うだけの小さい処理なので、1コア当たりのクロック数よりもコアの数が結果に与える影響が大きいと考えられる。
よって、通信時間を考慮しなければ CPU よりコア数が多い GPU が有利となる。

Cerium を用いて Bitonic Sort を実装し、要素数$2^{20}$のデータに対してコア数・プロセッサの種類を変更して測定を行なった結果は表\ref{table:bitonic}、図\ref{fig:bitonic_box}の通りである。

\begin{table}[!h]
  \begin{center}
    \small
    \begin{tabular}[htpb]{|c||c|}
      \hline
      Processor & Time(ms) \\
      \hline
      \hline
      1 CPU & 6143 \\
      \hline
      2 CPUs & 4633 \\
      \hline
      4 CPUs & 2557 \\
      \hline
      8 CPUs & 1630 \\
      \hline
      12 CPUs & 1318 \\
      \hline
      GPU &  155 \\
      \hline
    \end{tabular}
    \caption{要素数$2^{20}$に対するソート}
    \label{table:bitonic}
  \end{center}
\end{table}

\newpage

\begin{figure}[!h]
  \begin{center}
    \includegraphics[scale=1.0]{images/bitonic_sort_03.pdf}
  \end{center}
  \caption{要素数$2^{20}$に対するソート}
  \label{fig:bitonic_box}
\end{figure}

1 CPU と 12 CPU では約4.6倍の速度向上が見られた。
これは Task の粒度が小さいため1コア当たりのクロック数の高さが活かしづらく、並列化によるオーバーヘッドが結果に影響を与えたと考えられる。
CPU を用いた並列化には Task の粒度をある程度大きくし1コア当たりの仕事量を増やして CPU のクロック数の高さを活かすことが重要であることがわかる。

12 CPU と GPU では約8.5倍の速度向上が見られた。
GPU の特徴であるコア数の多さによって CPU より高い並列度を発揮した結果だと考えられる。
GPU の場合はその超並列性を活かすため Task を細かく分割することが重要であることがわかる。

測定結果から CPU と GPU で並列化の方法を変更する必要があることがわかった。
Cerium を用いてヘテロジニアス環境で並列実行する場合、混在しているプロセッサの特徴に合わせたスケジューリングを行い並列実行するように Scheduler を改良する必要がある。

次に要素数も変更して測定を行なった。
結果は図:\ref{fig:bitonic_result_2}、図:\ref{fig:bitonic_result_1}の通りである。

\newpage

\begin{figure}[!h]
  \begin{center}
    \includegraphics[scale=1.0]{images/bitonic_sort_02.pdf}
  \end{center}
  \caption{Bitonic Sort(from $2^{14}$ to $2^{17}$)}
  \label{fig:bitonic_result_2}
\end{figure}

\begin{figure}[!h]
  \begin{center}
    \includegraphics[scale=1.0]{images/bitonic_sort_01.pdf}
  \end{center}
  \caption{Bitonic Sort(from $2^{14}$ to $2^{20}$)}
  \label{fig:bitonic_result_1}
\end{figure}

\newpage

GPGPU では通信時間を考慮する必要がある。
図:\ref{fig:bitonic_result_2}を見ると要素数$2^{14}$のソートでは GPU が一番遅い。
これはソート処理の時間より通信時間が大きいことが原因であると考えられる。
通信時間を含めた処理時間が GPU が CPU を上回るのは要素数$2^{17}$を超えてからである。

\subsection{Word Count}
並列処理を行う際に Task を大量に生成する場合がある。
一度に大量の Task を生成してしまうと Task がメモリを圧迫して処理速度が著しく低下する。
改善策としては Task の生成と実行を平行して行えばよい。
Cerium では Task を生成する Task を記述することが可能なので Task の生成と実行を平行して行うことができる。

Word Count を並列処理する場合、与えられたテキストを分割して、分割されたデータごとに並列処理を行う。
分割したデータの数だけ Task が必要なのでテキストサイズによっては一度に Task を生成するとメモリを圧迫する可能性がある。
よって、Task を生成する Task が必要になる。
Word Count の処理の流れは図\ref{fig:wordcount}の通りである。

\begin{figure}[!h]
  \begin{center}
    \includegraphics[scale=0.7]{images/wordcount.pdf}
  \end{center}
  \caption{Word Count の流れ}
  \label{fig:wordcount}
\end{figure}

\newpage

Cerium が複雑な並列処理を記述可能でその上、高い並列度を保てること示すため Cerium 上に Word Count を実装し、100MB のテキストデータに対して測定を行なった。
結果は表:\ref{table:word_count}, 図:\ref{fig:word_count}の通りである。

\begin{table}[!h]
  \begin{center}
    \small
    \begin{tabular}[htpb]{|c||c|}
      \hline
      Processor & Time(ms) \\
      \hline
      \hline
      1 CPU & 716 \\ 
      \hline
      2 CPUs & 373 \\
      \hline
      4 CPUs & 197 \\
      \hline
      8 CPUs & 105 \\
      \hline
      12 CPUs & 87 \\
      \hline
      GPU & 9899 \\
      \hline
      GPU(Data Parallel) & 514 \\
      \hline
    \end{tabular}
    \caption{100MB のテキストデータに対する WordCount}
    \label{table:word_count}
  \end{center}
\end{table}

\begin{figure}[!h]
  \begin{center}
    \includegraphics[scale=0.8]{images/word_count.pdf}
  \end{center}
  \caption{100MB のテキストデータに対する WordCount}
  \label{fig:word_count}
\end{figure}

1 CPU と 12 CPU では約8.2倍の速度向上が見られた。
複雑な並列処理でも高い並列度が保てていることがわかる。

GPU を用いたタスク並列による実行は実用に耐えない速度である。
これはタスク並列による実行では小さなデータを十数回 GPU に転送する必要があるからで、GPU で高速に処理するためにはデータ転送を如何にして抑えるかが重要かわかる。
一方、GPU を用いたデータ並列による実行速度は 1 CPU の約1.4倍となった。
元々 WordCount は GPU に不向きな例題ではあるが、データ並列による実行ではデータ転送の回数を抑えることができるので GPU でもある程度の速度を出せることがわかる。

\subsection{FFT}
FFT は信号処理や画像処理、大規模シミュレーションに至るまで幅広い分野で活用されている計算である。
バタフライ演算などの計算の性質上、大量の演算資源を持つ GPU と相性が良い。
Cerium に実装した GPU 実行機構の評価を行うために適切な例題であると考えられる。

Cerium 上に FFT を実装し、測定を行なった結果は表:\ref{table:fft}, 図:\ref{fig:fft}の通りである。
測定には 1MB の画像データを用いた。

\begin{table}[!h]
  \begin{center}
    \small
    \begin{tabular}[htpb]{|c||c|}
      \hline
      Processor & Time(ms) \\
      \hline
      \hline
      1 CPU & 1958 \\
      \hline
      2 CPUs & 1174 \\
      \hline
      4 CPUs & 711 \\
      \hline
      8 CPUs & 451 \\
      \hline
      12 CPUs & 373 \\
      \hline
      GPU & 418 \\
      \hline
    \end{tabular}
    \caption{1MB の画像データに対する FFT}
    \label{table:fft}
  \end{center}
\end{table}
 
\begin{figure}[!h]
  \begin{center}
    \includegraphics[scale=0.8]{images/fft.pdf}
  \end{center}
  \caption{1MB の画像データに対する FFT}
  \label{fig:fft}
\end{figure}

1 CPU に対して 12 CPU では約5.2倍、GPU では約4.7倍の速度向上が見られる。
ある程度の速度向上が見られたが、CPU に劣る結果となった。
データ転送の最適化が十分になされていない可能性があるので、GPU の実行機構を見直す必要がある。

\section{Cerium の問題点}
Cerium では Task 間の依存関係を記述することで並列処理を実現する。
しかし、本来 Task はデータが揃えば実行可能になるものである。
Task 間の依存関係だけでは待っている Task が不正な処理を行いデータがおかしくなっても Task の終了は通知され、そのまま処理が続行されてしまう。
その場合、どこでデータがおかしくなったのか特定するのは難しくデバッグに多くの時間が取られてしまう。
また、Cerium の Task は汎用ポインタでデータを受け取るので型の情報がない。
型の情報がないので Task を実行するまで正しい型かどうか判断することが出来ない。
不正な型でも強制的に型変換され実行されるのでデータの構造を破壊する可能性がある。
型システムによってプログラムの正しさを保証することも出来ず、バグが入り込む原因になる。

Cerium の Allocator は Thread 間で共有されている。
共有されているので、ある Thread がメモリを確保しようとすると他の Thread は終了を待つ必要がある
その間メモリを確保することができないので処理が止まり、なにもしない時間が生まれてしまう。
これが並列度の低下に繋がり、処理速度が落ちる原因になる。

今回設計した Gears OS はこれらの問題を解決することを目的としている。