annotate paper/evaluation.tex @ 75:da3b145398a4

Fix
author Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
date Fri, 09 Feb 2018 15:27:41 +0900
parents ed207d6c511a
children 44f592c43324
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
38
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
1 % GPU が遅いのは cpu, GPU 間のデータの通信の分
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
2 % Meta Data で データが GPU にあるのか, CPU にあるのかをわかるようにする
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
3 % CPU で必要なったときに初めて取り出す
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
4
2
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 \chapter{Gears OS の評価}
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
6
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
7 \section{実験環境}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
8 今回 Twice、 BitonicSort をそれぞれ CPU、GPU環境で Gears OS の測定を行う。
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
9
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
10 使用する実験環境を\tabref{powerEdge}、 GPU 環境を\tabref{gtx1070} に示す。
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
11
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
12 \begin{table}[htbp]
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
13 \begin{center}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
14 \begin{tabular}{|l|l|} \hline
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
15 Model & Dell PowerEdgeR630 \\ \hline
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
16 OS & CentOS 7.4.1708 \\ \hline
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
17 Memory & 768GB \\ \hline
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
18 CPU & 2 x 18-Core Intel Xeon 2.30GHz \\ \hline
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
19 \end{tabular}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
20 \caption{実行環境}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
21 \label{tab:powerEdge}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
22 \end{center}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
23 \end{table}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
24
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
25 \begin{table}[htbp]
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
26 \begin{center}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
27 \begin{tabular}{|l||l|} \hline
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
28 GPU & GeForce GTX 1070 \\ \hline
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
29 Cores & 1920 \\ \hline
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
30 Clock Speed & 1683MHz \\ \hline
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
31 Memory Size & 8GB GDDR5 \\ \hline
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
32 Memory Bandwidth & 256GB/s \\ \hline
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
33 \end{tabular}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
34 \caption{GPU 環境}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
35 \label{tab:gtx1070}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
36 \end{center}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
37 \end{table}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
38
2
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 \section{Twice}
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
40 Twice は与えられた整数配列のすべての要素を2倍にする例題である。
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
41
49
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
42 Twice の Task は Gears OS のデータ並列で実行される。
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
43 CPU の場合は配列ある程度の範囲に分割してTaskを生成する。
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
44 これは要素毎に Task を生成するとその分の Context を生成するために時間を取ってしまうからである。
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
45
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
46 Twice は並列実行の依存関係もなく、データ並列での実行に適した課題である。
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
47 そのため、 通信時間を考慮しなければ CPU よりコア数が多い GPU が有利となる。
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
48
47
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
49 要素数$2^{27}$ のデータに対する Twice の実行結果を \tabref{twice}、\figref{twice}に示す。
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
50 CPU 実行の際は $2^{27}$ のデータを 64個のTask に分割して並列実行を行っている。
49
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
51 GPU では1次元の block 数を $2^{15}$、 block 内の thread 数を $2^{10}$ で kernel の実行を行った。
47
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
52 ここでの ``GPU`` は CPU、GPU 間のデータの通信時間も含めた時間、 ``GPU(kernel only)`` は kernel のみの実行時間である。
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
53
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
54 \begin{table}[htbp]
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
55 \begin{center}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
56 \begin{tabular}{|l||l|} \hline
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
57 Processor & Time(ms) \\ \hline
47
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
58 1 CPU & 1181.215 \\ \hline
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
59 2 CPUs & 627.914 \\ \hline
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
60 4 CPUs & 324.059 \\ \hline
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
61 8 CPUs & 159.932 \\ \hline
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
62 16 CPUs & 85.518\\ \hline
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
63 32 CPUs & 43.496 \\ \hline
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
64 GPU & 127.018\\ \hline
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
65 GPU(kernel only)& 6.018 \\ \hline
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
66 \end{tabular}
47
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
67 \caption{$2^{27}$ のデータに対する Twice}
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
68 \label{tab:twice}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
69 \end{center}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
70 \end{table}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
71
58
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
72 \newpage
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
73
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
74 \begin{figure}[htbp]
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
75 \begin{center}
58
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
76 \includegraphics[scale=0.6]{./fig/twice.pdf}
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
77 \end{center}
47
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
78 \caption{$2^{27}$ のデータに対する Twice}
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
79 \label{fig:twice}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
80 \end{figure}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
81
47
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
82 1 CPU と 32 CPU では 約 27.1 倍の速度向上が見られた。
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
83 ある程度の台数効果があると考えられる。
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
84
47
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
85 GPU での実行は kernel のみの実行時間は 32CPU に比べて 約 7.2 倍の実行向上が見られた。
7ddbad0c4b5d Update twice result
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
86 しかし、通信時間を含めると 16CPU より遅い結果となってしまった。
49
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
87 CPU、GPU の通信時間かオーバーヘッドになっている事がわかる。
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
88
2
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 \section{BitonicSort}
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
90 BitonicSort は並列処理向けのソートアルゴリズムである。
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
91 代表的なソートアルゴリズムである Quick Sort も並列処理 を行うことが可能であるが、 QuickSort では ソートの過程で並列度が変動するため、台数効果が出づらい。
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
92 一方でBitonic Sort は最初から最後まで並列度が変わらずに並列処理を行う。
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
93 \figref{bitonicNetwork} は要素数8のデータに対する BitonicSort のソートネットワークである。
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
94
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
95 \begin{figure}[htbp]
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
96 \begin{center}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
97 \includegraphics[scale=0.6]{./fig/bitonicNetwork.pdf}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
98 \end{center}
33
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
99 \caption{要素数8の BitonicNetwork}
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
100 \label{fig:bitonicNetwork}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
101 \end{figure}
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
102
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
103 BitonicSort はステージ毎に決まった2点間の要素の入れ替えを並列に実行することによってソートを行う。
33
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
104 Gears OS ではこのステージ毎に Output Data Gear を書き出し、 次のステージの Code Gear の Input Data Gear として記述することで BitonicSort を実現する。
32
ebcf093795f3 Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
105
33
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
106 要素数$2^{24}$ のデータに対する BitonicSort の実行結果を \tabref{bitonicSort}、\figref{bitonicSort}に示す。
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
107 こちらも Twice と同じくCPU 実行の際は $2^{24}$ のデータを 64個のTask に分割して並列実行を行っている。
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
108 つまり生成される Task は 64 * ステージ数 となる。
49
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
109 GPU では1次元の block 数を $2^{14}$、 block 内の thread 数を $2^{10}$ で kernel の実行を行った。
33
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
110
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
111 \begin{table}[htbp]
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
112 \begin{center}
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
113 \begin{tabular}{|l||l|} \hline
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
114 Processor & Time(s) \\ \hline
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
115 1 CPU & 41.416 \\ \hline
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
116 2 CPUs & 23.340\\ \hline
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
117 4 CPUs & 11.952\\ \hline
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
118 8 CPUs & 6.320\\ \hline
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
119 16 CPUs & 3.336\\ \hline
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
120 32 CPUs & 1.872\\ \hline
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
121 GPU & 5.420\\ \hline
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
122 GPU(kernel only)& 0.163\\ \hline
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
123 \end{tabular}
40
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
124 \caption{$2^{24}$ のデータに対する BitonicSort}
33
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
125 \label{tab:bitonicSort}
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
126 \end{center}
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
127 \end{table}
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
128
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
129 \begin{figure}[htbp]
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
130 \begin{center}
58
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
131 \includegraphics[scale=0.6]{./fig/bitonicSort.pdf}
33
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
132 \end{center}
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
133 \caption{$2^{24}$ のデータに対する BitonicSort}
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
134 \label{fig:bitonicSort}
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
135 \end{figure}
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
136
58
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
137 \newpage
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
138
33
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
139 1 CPU と 32 CPU で 約22.12 倍 の速度向上が見られた。
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
140 GPU では通信時間を含めると 8 CPU の約1.16倍となり、 kernel のみの実行では 32 CPU の約11.48倍となった。
6da0158a17a1 Add bitonicSort
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
141 現在の Gears OS の CUDA 実装では、 Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の実行結果の書き出しを行っており、その処理の時間で差が出たと考えられる。
35
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
142 GPU で実行される Task 同士の依存関係の解決の際はCuDevicePtr などのGPU のメモリへのポインタを渡し、CPU でデータが必要になったときに初めて GPU から CPU へデータの通信を行うメタ計算の実装が必要となる。
36
1008821ac2c7 Add semaphore section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
143
1008821ac2c7 Add semaphore section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
144 \section{OpenMP との比較}
41
5e604f9f9022 Add openMP
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 40
diff changeset
145 OpenMP\cite{openmp} は C、 C++ のプログラムにアノテーションを付けることで並列化を行う。
5e604f9f9022 Add openMP
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 40
diff changeset
146 アノテーションを \coderef{openMP} のように for 文の前につけることで、ループの並列化を行う。
5e604f9f9022 Add openMP
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 40
diff changeset
147
5e604f9f9022 Add openMP
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 40
diff changeset
148 \lstinputlisting[caption=OpenMP での Twice, label=code:openMP]{./src/openMP.c}
5e604f9f9022 Add openMP
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 40
diff changeset
149
5e604f9f9022 Add openMP
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 40
diff changeset
150 OpenMP は既存のコードにアノテーションを付けるだけで並列化を行えるため、変更が少なくて済む。
5e604f9f9022 Add openMP
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 40
diff changeset
151 しかし、 ループのみの並列化ではプログラム全体の並列度が上がらずアムダールの法則により性能向上が頭打ちになってしまう。
5e604f9f9022 Add openMP
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 40
diff changeset
152 OpenMP はループの並列化 ではなくブロック単位での並列実行もサポートしているが、アノテーションの記述が増えてしまう。
5e604f9f9022 Add openMP
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 40
diff changeset
153 また、 OpenMPはコードとデータを厳密に分離していないため、データの待ち合わせ処理をバリア等のアノテーションで記述する。
5e604f9f9022 Add openMP
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 40
diff changeset
154
5e604f9f9022 Add openMP
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 40
diff changeset
155 Gears OS では Input Data Gear が揃った Code Gear は並列に実行されるため、プログラム全体の並列度を高めることが出来る。
42
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
156 また 並列処理のコードとデータの依存関係を par goto 文で簡潔に記述することが出来る。
36
1008821ac2c7 Add semaphore section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
157
58
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
158 Gears OS と OpenMP で実装した Twice の実行結果の比較を\figref{vsopenmp} に示す。
56
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
159 実行環境は \tabref{powerEdge}、 $2^{27}$ のデータに対して行い、Gears OS 側は配列を 64個のTaskに分割し、OpenMP は for 文を static スケジュールで並列実行した。
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
160 static スケジュールはループの回数をプロセッサーの数で分割し、並列実行を行う openMP のスケジュール方法である。
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
161
58
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
162 \newpage
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
163
56
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
164 \begin{figure}[htbp]
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
165 \begin{center}
58
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
166 \includegraphics[scale=0.6]{./fig/vsopenmp.pdf}
56
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
167 \end{center}
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
168 \caption{vs OpenMP}
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
169 \label{fig:vsopenmp}
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
170 \end{figure}
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
171
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
172 OpenMP は 1CPUと 32CPU で約10.8 倍の速度向上がみられた。
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
173 一方 Gears OS では約 27.1 倍の速度向上のため、台数効果が高くなっている。
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
174 しかし、Gears OS は 1CPU での実行時間がOpenMP に比べて大幅に遅くなっている。
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
175
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
176 \section{Go 言語との比較}
59
ed207d6c511a Add abstract
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 58
diff changeset
177 Go 言語 は Google社が開発しているプログラミング言語である。
42
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
178 Go 言語によるTwice の実装例を\coderef{go}に示す。
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
179
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
180 \lstinputlisting[caption=Go 言語での Twice, label=code:go]{./src/go.go}
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
181
75
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 59
diff changeset
182 Go 言語は並列実行を ``go function(argv)'' のような構文で行う。
42
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
183 この並列実行を goroutine と呼ぶ。
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
184
75
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 59
diff changeset
185 Go 言語は goroutin 間のデータ送受信をチャネルというデータ構造で行う。
42
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
186 チャネルによるデータの送受信は ``\textless-'' を使って行われる。
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
187 例えばチャネルのデータ構造であるchannel に対して ``channel \textless- data'' とすると、 data を channel に送信を行う。
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
188 ``\textless- channel'' とすると、 channel から送信されたデータを1つ取り出す。
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
189 channel にデータが送信されていない場合はchannel にデータが送信されるまで実行をブロックする。
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
190 Go 言語はチャネルにより、データの送受信が簡潔に書ける。
43
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
191 しかし、チャネルは複数の goroutine で参照できるためデータの送信元が推測しづらい。
42
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
192
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
193 Gears OS では goroutine は par goto 文とほぼ同等に扱うことが出来る。
d6cf9ceea3d4 Add go section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 41
diff changeset
194 また、Code Gear は par goto 文で書き出す Output Data Gear を指定して実行するため、Data Gear の書き出し元が推測しやすい。
56
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
195
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
196 Go 言語での OpenMP と同様に Twice を実装しGears OS と比較を行う。
75
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 59
diff changeset
197 こちらも実行環境は \tabref{powerEdge}、 $2^{27}$ のデータに対して行い、Gears OS、Go 言語両方とも配列を64個のTask、 goroutineに分割して並列実行を行った。
56
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
198
58
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
199 \newpage
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
200
56
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
201 \begin{figure}[htbp]
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
202 \begin{center}
58
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
203 \includegraphics[scale=0.6]{./fig/vsgo.pdf}
56
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
204 \end{center}
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
205 \caption{vs Go}
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
206 \label{fig:vsgo}
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
207 \end{figure}
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
208
09ac2339b00d Add vs graph
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 52
diff changeset
209 Go 言語は 1CPUと32CPU で約4.33 倍の速度向上が見られた。
58
131b1274cbae Fix layout
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents: 56
diff changeset
210 こちらも OpenMP と同じく、台数効果自体は Gears OS が高いが、1CPU での実行時間はGo 言語が大幅に速くなっている。