# HG changeset patch
# User mir3636
# Date 1524478754 -32400
# Node ID 5af2f3eace48abcf7ea879b80221eac7c20690f4
# Parent  b40dda8f52e7283f58ef6beec7e96e612a93cf64
updat

diff -r b40dda8f52e7 -r 5af2f3eace48 Paper/sigos.tex
--- a/Paper/sigos.tex	Mon Apr 23 16:48:56 2018 +0900
+++ b/Paper/sigos.tex	Mon Apr 23 19:19:14 2018 +0900
@@ -397,7 +397,7 @@
 \section{Gears OS の評価}
 
 \subsection{実験環境}
-今回 Twice、 BitonicSort をそれぞれ CPU、GPU環境で Gears OS の測定を行う。
+今回 Twice、を CPU、GPU環境で Gears OS の測定を行う。
 
 使用する実験環境を表\ref{tab:powerEdge}、 GPU 環境を表\ref{tab:gtx1070} に示す。
 また、今回は LLVM/Clang で実装した CbC コンパイラを用いて Gears OS をコンパイルする。
@@ -476,91 +476,6 @@
 しかし、通信時間を含めると 16 CPU より遅い結果となってしまった。
 CPU、GPU の通信時間かオーバーヘッドになっている事がわかる。
 
-\subsection{BitonicSort}
-BitonicSort は並列処理向けのソートアルゴリズムである。
-代表的なソートアルゴリズムである Quick Sort も並列処理 を行うことが可能であるが、 QuickSort では ソートの過程で並列度が変動するため、台数効果が出づらい。
-一方でBitonic Sort は最初から最後まで並列度が変わらずに並列処理を行う。
-図\ref{fig:bitonicNetwork} は要素数8のデータに対する BitonicSort のソートネットワークである。
-
-\begin{figure}[htbp]
-    \begin{center}
-        \includegraphics[width=70mm]{./pic/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 の実行結果を 表\ref{tab:bitonicSort}、図\ref{fig: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[width=70mm]{./pic/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 へデータの通
-信を行うメタ計算の実装が必要となる。
-
-\subsection{OpenMP との比較}
-OpenMP\cite{openmp} は C、 C++ のプログラムにアノテーションを付けることで並列化を行う。
-アノテーションを Code \ref{code: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 の実行結果の比較を図\ref{fig:vsopenmp} に示す。
-実行環境は 表\ref{tab:powerEdge}、 $2^{27}$ のデータに対して行い、Gears OS 側は配列を 64個のTaskに分割し、OpenMP は for 文を static スケジュールで並列実行した。
-static スケジュールはループの回数をプロセッサーの数で分割し、並列実行を行う openMP のスケジュール方法である。
-
-\begin{figure}[htbp]
-    \begin{center}
-        \includegraphics[width=70mm]{./pic/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 に比べて大幅に遅くなっている。
-
 \subsection{Go 言語との比較}
 Go 言語 は Google社が開発しているプログラミング言語である。
 Go 言語によるTwice の実装例を code \ref{code:go}に示す。
@@ -621,12 +536,12 @@
 これらのメタ計算の記述は煩雑であるため Perl スクリプトによる自動生成を行なった。
 これにより Gears OS のコードの煩雑さは改善され、ユーザーレベルではメタを意識する必要がなくなった。
 
-Twice と BitonicSort の例題の測定結果では 1CPU と 32CPU で Twice では約 27.1 倍、BitonicSort では 約 22.12 倍の速度向上が見られた。
-また、GPU 実行の測定も行い、kernel のみの実行時間では 32 CPU より Twice では約 7.2 倍、BitonicSort では約 11.48 倍の速度向上がみられ、
+Twice の例題の測定結果では 1CPU と 32CPU で約 27.1 倍、の速度向上が見られた。
+また、GPU 実行の測定も行い、kernel のみの実行時間では 32 CPU より約 7.2 倍の速度向上がみられ、
 GPU の性能を活かすことができた。
 
 今後の課題は、
-Go、OpenMP との比較から、 Gears OS が1CPU での動作が遅いということがわかった。
+Go、との比較から、 Gears OS が1CPU での動作が遅いということがわかった。
 Gears OS は par goto 文を使用することで Context を生成し、並列処理を行う。
 しかし、Context はメモリ空間の確保や使用する全ての Code/Data Gear を設定する必要があり、生成にある程度の時間がかかってしまう。
 そこで、 par goto のコンパイルタイミングで実行する Code Gear のフローをモデル検査で解析し、処理が軽い場合はContext を生成せずに、関数呼び出しを行う等の最適化を行なうといったチューニングが必要である。