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

\chapter{Gears OS の評価}

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

使用する実験環境を\tabref{powerEdge}、 GPU 環境を\tabref{gtx1070} に示す。

\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生成の方針として、CPU の場合は配列ある程度の範囲に分割してTaskを生成する。
これは要素毎に Task を生成するとその分の Context を生成するために時間を取ってしまうからである。

GPU での実行は データ並列を使用して行う。
GPU でデータ並列を実行する場合は Context とコピーなどは発生しないため、1要素に1スレッドを割り振って実行を行う。

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

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

\begin{table}[htbp]
    \begin{center}
        \begin{tabular}{|l||l|} \hline
            Processor & Time(ms) \\ \hline
            1 CPU & 147.946 \\ \hline
            2 CPUs & 80.773\\ \hline
            4 CPUs & 40.527\\ \hline
            8 CPUs & 20.267\\ \hline
            16 CPUs & 10.936\\ \hline
            32 CPUs & 5.878\\ \hline
            GPU & 542.816\\ \hline
            GPU(kernel only)& 0.755\\ \hline
        \end{tabular}
        \caption{$2^{24}$ のデータに対する Twice}
        \label{tab:twice}
    \end{center}
\end{table}

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

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

GPU での実行は kernel のみの実行時間は 32CPU に比べて 約 7.8 倍の実行向上が見られた。
しかし、通信時間を含めると 1 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 * ステージ数 となる。

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

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'' で簡潔に記述することが出来る。

\section{Go との比較}
Go言語\cite{go}