% GPU が遅いのは cpu, GPU 間のデータの通信の分
% Meta Data で データが GPU にあるのか, CPU にあるのかをわかるようにする
% CPU で必要なったときに初めて取り出す

\chapter{Gears OS の評価}

\section{実験環境}
今回 Twice、 BitonicSort をそれぞれ CPU、GPU環境で Gears OS の測定を行う。

使用する実験環境を\tabref{powerEdge}、 GPU 環境を\tabref{gtx1070} に示す。
また、今回は LLVM/Clang で実装した CbC コンパイラを用いて Gears OS をコンパイルする。

\begin{table}[htbp]
    \begin{center}
        \begin{tabular}{|l|l|} \hline
            Model & Dell PowerEdgeR630 \\ \hline
            OS    & CentOS 7.4.1708 \\ \hline
            Memory & 768GB \\ \hline
            CPU & 2 x 18-Core Intel Xeon 2.30GHz \\ \hline
        \end{tabular}
         \caption{実行環境}
         \label{tab:powerEdge}
    \end{center}
\end{table}

\begin{table}[htbp]
    \begin{center}
        \begin{tabular}{|l||l|} \hline
            GPU & GeForce GTX 1070 \\ \hline
            Cores & 1920 \\ \hline
            Clock Speed & 1683MHz \\ \hline
            Memory Size & 8GB GDDR5 \\ \hline
            Memory Bandwidth & 256GB/s \\ \hline
        \end{tabular}
        \caption{GPU 環境}
        \label{tab:gtx1070}
    \end{center}
\end{table}

\section{Twice}
Twice は与えられた整数配列のすべての要素を2倍にする例題である。

Twice の Task は Gears OS のデータ並列で実行される。
CPU の場合は配列ある程度の範囲に分割してTaskを生成する。
これは要素毎に Task を生成するとその分の Context を生成するために時間を取ってしまうからである。

Twice は並列実行の依存関係もなく、データ並列での実行に適した課題である。
そのため、 通信時間を考慮しなければ CPU よりコア数が多い GPU が有利となる。

要素数$2^{27}$ のデータに対する Twice の実行結果を \tabref{twice}、\figref{twice}に示す。
CPU 実行の際は $2^{27}$ のデータを 64個のTask に分割して並列実行を行っている。
GPU では1次元の block 数を $2^{15}$、 block 内の thread 数を $2^{10}$ で kernel の実行を行った。
ここでの ``GPU`` は CPU、GPU 間のデータの通信時間も含めた時間、 ``GPU(kernel only)`` は kernel のみの実行時間である。

\begin{table}[htbp]
    \begin{center}
        \begin{tabular}{|l||l|} \hline
            Processor & Time(ms) \\ \hline
            1 CPU   & 1181.215 \\ \hline
            2 CPUs  & 627.914 \\ \hline
            4 CPUs  & 324.059 \\ \hline
            8 CPUs  & 159.932 \\ \hline
            16 CPUs & 85.518\\ \hline
            32 CPUs & 43.496 \\ \hline
            GPU & 127.018\\ \hline
            GPU(kernel only)& 6.018 \\ \hline
        \end{tabular}
        \caption{$2^{27}$ のデータに対する Twice}
        \label{tab:twice}
    \end{center}
\end{table}

\newpage

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[scale=0.6]{./fig/twice.pdf}
    \end{center}
    \caption{$2^{27}$ のデータに対する Twice}
    \label{fig:twice}
\end{figure}

1 CPU と 32 CPU では 約 27.1 倍の速度向上が見られた。
ある程度の台数効果があると考えられる。

GPU での実行は kernel のみの実行時間は 32 CPU に比べて 約 7.2 倍の速度向上が見られた。
しかし、通信時間を含めると 16 CPU より遅い結果となってしまった。
CPU、GPU の通信時間かオーバーヘッドになっている事がわかる。

\section{BitonicSort}
BitonicSort は並列処理向けのソートアルゴリズムである。
代表的なソートアルゴリズムである Quick Sort も並列処理 を行うことが可能であるが、 QuickSort では ソートの過程で並列度が変動するため、台数効果が出づらい。
一方でBitonic Sort は最初から最後まで並列度が変わらずに並列処理を行う。
\figref{bitonicNetwork} は要素数8のデータに対する BitonicSort のソートネットワークである。

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[scale=0.6]{./fig/bitonicNetwork.pdf}
    \end{center}
    \caption{要素数8の BitonicNetwork}
    \label{fig:bitonicNetwork}
\end{figure}

BitonicSort はステージ毎に決まった2点間の要素の入れ替えを並列に実行することによってソートを行う。
Gears OS ではこのステージ毎に Output Data Gear を書き出し、 次のステージの Code Gear の Input Data Gear として記述することで BitonicSort を実現する。

要素数$2^{24}$ のデータに対する BitonicSort の実行結果を \tabref{bitonicSort}、\figref{bitonicSort}に示す。
こちらも Twice と同じくCPU 実行の際は $2^{24}$ のデータを 64個のTask に分割して並列実行を行っている。
つまり生成される Task は 64 * ステージ数 となる。
GPU では1次元の block 数を $2^{14}$、 block 内の thread 数を $2^{10}$ で kernel の実行を行った。

\begin{table}[htbp]
    \begin{center}
        \begin{tabular}{|l||l|} \hline
            Processor & Time(s) \\ \hline
            1 CPU &  41.416 \\ \hline
            2 CPUs & 23.340\\ \hline
            4 CPUs & 11.952\\ \hline
            8 CPUs & 6.320\\ \hline
            16 CPUs & 3.336\\ \hline
            32 CPUs & 1.872\\ \hline
            GPU & 5.420\\ \hline
            GPU(kernel only)& 0.163\\ \hline
        \end{tabular}
        \caption{$2^{24}$ のデータに対する BitonicSort}
        \label{tab:bitonicSort}
    \end{center}
\end{table}

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[scale=0.6]{./fig/bitonicSort.pdf}
    \end{center}
    \caption{$2^{24}$ のデータに対する BitonicSort}
    \label{fig:bitonicSort}
\end{figure}

\newpage

1 CPU と 32 CPU で 約22.12 倍 の速度向上が見られた。
GPU では通信時間を含めると 8 CPU の約1.16倍となり、 kernel のみの実行では 32 CPU の約11.48倍となった。
現在の Gears OS の CUDA 実装では、 Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の実行結果の書き出しを行っており、その処理の時間で差が出たと考えられる。
GPU で実行される Task 同士の依存関係の解決の際はCuDevicePtr などのGPU のメモリへのポインタを渡し、CPU でデータが必要になったときに初めて GPU から CPU へデータの通信を行うメタ計算の実装が必要となる。

\section{OpenMP との比較}
OpenMP\cite{openmp} は C、 C++ のプログラムにアノテーションを付けることで並列化を行う。
アノテーションを \coderef{openMP} のように for 文の前につけることで、ループの並列化を行う。

\lstinputlisting[caption=OpenMP での Twice, label=code:openMP]{./src/openMP.c}

OpenMP は既存のコードにアノテーションを付けるだけで並列化を行えるため、変更が少なくて済む。
しかし、 ループのみの並列化ではプログラム全体の並列度が上がらずアムダールの法則により性能向上が頭打ちになってしまう。
OpenMP はループの並列化 ではなくブロック単位での並列実行もサポートしているが、アノテーションの記述が増えてしまう。
また、 OpenMPはコードとデータを厳密に分離していないため、データの待ち合わせ処理をバリア等のアノテーションで記述する。

Gears OS では Input Data Gear が揃った Code Gear は並列に実行されるため、プログラム全体の並列度を高めることが出来る。
また 並列処理のコードとデータの依存関係を par goto 文で簡潔に記述することが出来る。

Gears OS と OpenMP で実装した Twice の実行結果の比較を\figref{vsopenmp} に示す。
実行環境は \tabref{powerEdge}、 $2^{27}$ のデータに対して行い、Gears OS 側は配列を 64個のTaskに分割し、OpenMP は for 文を static スケジュールで並列実行した。
static スケジュールはループの回数をプロセッサーの数で分割し、並列実行を行う openMP のスケジュール方法である。

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[scale=0.6]{./fig/vsopenmp.pdf}
    \end{center}
    \caption{vs OpenMP}
    \label{fig:vsopenmp}
\end{figure}

実行結果として OpenMP は 1CPUと 32CPU で約10.8 倍の速度向上がみられた。
一方 Gears OS では約 27.1 倍の速度向上のため、台数効果が高くなっている。
しかし、Gears OS は 1CPU での実行時間がOpenMP に比べて大幅に遅くなっている。

\section{Go 言語との比較}
Go 言語 は Google社が開発しているプログラミング言語である。
Go 言語によるTwice の実装例を\coderef{go}に示す。

\lstinputlisting[caption=Go 言語での Twice, label=code:go]{./src/go.go}

Go 言語は並列実行を ``go function(argv)'' のような構文で行う。
この並列実行を goroutine と呼ぶ。

Go 言語は goroutin 間のデータ送受信をチャネルというデータ構造で行う。
チャネルによるデータの送受信は ``\textless-'' を使って行われる。
例えばチャネルのデータ構造であるchannel に対して ``channel \textless- data'' とすると、 data を channel に送信を行う。
``\textless- channel'' とすると、 channel から送信されたデータを1つ取り出す。
channel にデータが送信されていない場合はchannel にデータが送信されるまで実行をブロックする。
Go 言語はチャネルにより、データの送受信が簡潔に書ける。
しかし、チャネルは複数の goroutine で参照できるためデータの送信元が推測しづらい。

Gears OS では goroutine は par goto 文とほぼ同等に扱うことが出来る。
また、Code Gear は par goto 文で書き出す Output Data Gear を指定して実行するため、Data Gear の書き出し元が推測しやすい。

Go 言語での OpenMP と同様に Twice を実装しGears OS と比較を行う。
こちらも実行環境は \tabref{powerEdge}、 $2^{27}$ のデータに対して行い、Gears OS、Go 言語両方とも配列を64個のTask、 goroutineに分割して並列実行を行った。

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[scale=0.6]{./fig/vsgo.pdf}
    \end{center}
    \caption{vs Go}
    \label{fig:vsgo}
\end{figure}

実行結果として Go 言語は 1CPUと32CPU で約4.33 倍の速度向上が見られた。
こちらも OpenMP と同じく、台数効果自体は Gears OS が高いが、1CPU での実行時間はGo 言語が大幅に速くなっている。