# HG changeset patch # User Tatsuki IHA # Date 1517665608 -32400 # Node ID 6da0158a17a1d7b8bf2360b0807afc7ee5aa1ec2 # Parent ebcf093795f32e559b2ba135562a495c2f905314 Add bitonicSort diff -r ebcf093795f3 -r 6da0158a17a1 paper/evaluation.tex --- a/paper/evaluation.tex Sat Feb 03 20:56:35 2018 +0900 +++ b/paper/evaluation.tex Sat Feb 03 22:46:48 2018 +0900 @@ -44,8 +44,8 @@ Twice は並列実行の依存関係もなく、データ並列での実行に適した課題である。 そのため、 通信時間を考慮しなければ CPU よりコア数が多い GPU が有利となる。 -要素数$2^{23}$ のデータに対する Twice の実行結果を \tabref{twice}、\figref{twice}に示す。 -CPU 実行の際は $2^{23}$ のデータを 64 個のTask に分割して並列実行を行っている。 +要素数$2^{24}$ のデータに対する Twice の実行結果を \tabref{twice}、\figref{twice}に示す。 +CPU 実行の際は $2^{24}$ のデータを 64個のTask に分割して並列実行を行っている。 ここでの ``GPU`` は CPU、 GPU 間のデータの通信時間を含めた時間、 ``GPU(kernel only)`` は kernel のみの実行時間である。 \begin{table}[htbp] @@ -61,7 +61,7 @@ GPU & 542.816\\ \hline GPU(kernel only)& 0.755\\ \hline \end{tabular} - \caption{$2^{23}$ のデータに対する Twice} + \caption{$2^{24}$ のデータに対する Twice} \label{tab:twice} \end{center} \end{table} @@ -91,9 +91,44 @@ \begin{center} \includegraphics[scale=0.6]{./fig/bitonicNetwork.pdf} \end{center} - \caption{要素数8の BtionicNetwork} + \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}$ のデータに対する Twice} + \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 へデータの通信を行う実装が必要となる。 diff -r ebcf093795f3 -r 6da0158a17a1 paper/fig/twice.pdf Binary file paper/fig/twice.pdf has changed diff -r ebcf093795f3 -r 6da0158a17a1 paper/fig/twice.svg --- a/paper/fig/twice.svg Sat Feb 03 20:56:35 2018 +0900 +++ b/paper/fig/twice.svg Sat Feb 03 22:46:48 2018 +0900 @@ -42,96 +42,91 @@ - + 0 - + 100 - + 200 - + 300 - + 400 - + 500 - + 600 - + 1 cpu - + 2 cpus - + 4 cpus - + 8 cpus - + 16 cpus - + 32 cpus - + gpu - - gpu(only) + + gpu(kernel only) - + - + time(ms) - - CPUs - - - - + twice benchmark @@ -140,44 +135,44 @@ - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + @@ -186,7 +181,7 @@ - + diff -r ebcf093795f3 -r 6da0158a17a1 paper/fig/twice.xbb --- a/paper/fig/twice.xbb Sat Feb 03 20:56:35 2018 +0900 +++ b/paper/fig/twice.xbb Sat Feb 03 22:46:48 2018 +0900 @@ -2,7 +2,7 @@ %%Creator: extractbb 20170318 %%BoundingBox: 0 0 600 480 %%HiResBoundingBox: 0.000000 0.000000 600.000000 480.000000 -%%PDFVersion: 1.3 +%%PDFVersion: 1.5 %%Pages: 1 -%%CreationDate: Sat Feb 3 18:15:19 2018 +%%CreationDate: Sat Feb 3 22:27:55 2018 diff -r ebcf093795f3 -r 6da0158a17a1 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed