Mercurial > hg > Papers > 2018 > parusu-master
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 |
rev | line source |
---|---|
38 | 1 % GPU が遅いのは cpu, GPU 間のデータの通信の分 |
2 % Meta Data で データが GPU にあるのか, CPU にあるのかをわかるようにする | |
3 % CPU で必要なったときに初めて取り出す | |
4 | |
2 | 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 | 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 | 42 Twice の Task は Gears OS のデータ並列で実行される。 |
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 | 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 | 72 \newpage |
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 | 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 | 87 CPU、GPU の通信時間かオーバーヘッドになっている事がわかる。 |
32
ebcf093795f3
Add twice examples
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
88 |
2 | 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 | 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 | 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 | 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 | 137 \newpage |
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 | 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 | 145 OpenMP\cite{openmp} は C、 C++ のプログラムにアノテーションを付けることで並列化を行う。 |
146 アノテーションを \coderef{openMP} のように for 文の前につけることで、ループの並列化を行う。 | |
147 | |
148 \lstinputlisting[caption=OpenMP での Twice, label=code:openMP]{./src/openMP.c} | |
149 | |
150 OpenMP は既存のコードにアノテーションを付けるだけで並列化を行えるため、変更が少なくて済む。 | |
151 しかし、 ループのみの並列化ではプログラム全体の並列度が上がらずアムダールの法則により性能向上が頭打ちになってしまう。 | |
152 OpenMP はループの並列化 ではなくブロック単位での並列実行もサポートしているが、アノテーションの記述が増えてしまう。 | |
153 また、 OpenMPはコードとデータを厳密に分離していないため、データの待ち合わせ処理をバリア等のアノテーションで記述する。 | |
154 | |
155 Gears OS では Input Data Gear が揃った Code Gear は並列に実行されるため、プログラム全体の並列度を高めることが出来る。 | |
42 | 156 また 並列処理のコードとデータの依存関係を par goto 文で簡潔に記述することが出来る。 |
36
1008821ac2c7
Add semaphore section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
157 |
58 | 158 Gears OS と OpenMP で実装した Twice の実行結果の比較を\figref{vsopenmp} に示す。 |
56 | 159 実行環境は \tabref{powerEdge}、 $2^{27}$ のデータに対して行い、Gears OS 側は配列を 64個のTaskに分割し、OpenMP は for 文を static スケジュールで並列実行した。 |
160 static スケジュールはループの回数をプロセッサーの数で分割し、並列実行を行う openMP のスケジュール方法である。 | |
161 | |
58 | 162 \newpage |
163 | |
56 | 164 \begin{figure}[htbp] |
165 \begin{center} | |
58 | 166 \includegraphics[scale=0.6]{./fig/vsopenmp.pdf} |
56 | 167 \end{center} |
168 \caption{vs OpenMP} | |
169 \label{fig:vsopenmp} | |
170 \end{figure} | |
171 | |
172 OpenMP は 1CPUと 32CPU で約10.8 倍の速度向上がみられた。 | |
173 一方 Gears OS では約 27.1 倍の速度向上のため、台数効果が高くなっている。 | |
174 しかし、Gears OS は 1CPU での実行時間がOpenMP に比べて大幅に遅くなっている。 | |
175 | |
176 \section{Go 言語との比較} | |
59 | 177 Go 言語 は Google社が開発しているプログラミング言語である。 |
42 | 178 Go 言語によるTwice の実装例を\coderef{go}に示す。 |
179 | |
180 \lstinputlisting[caption=Go 言語での Twice, label=code:go]{./src/go.go} | |
181 | |
75 | 182 Go 言語は並列実行を ``go function(argv)'' のような構文で行う。 |
42 | 183 この並列実行を goroutine と呼ぶ。 |
184 | |
75 | 185 Go 言語は goroutin 間のデータ送受信をチャネルというデータ構造で行う。 |
42 | 186 チャネルによるデータの送受信は ``\textless-'' を使って行われる。 |
187 例えばチャネルのデータ構造であるchannel に対して ``channel \textless- data'' とすると、 data を channel に送信を行う。 | |
188 ``\textless- channel'' とすると、 channel から送信されたデータを1つ取り出す。 | |
189 channel にデータが送信されていない場合はchannel にデータが送信されるまで実行をブロックする。 | |
190 Go 言語はチャネルにより、データの送受信が簡潔に書ける。 | |
43 | 191 しかし、チャネルは複数の goroutine で参照できるためデータの送信元が推測しづらい。 |
42 | 192 |
193 Gears OS では goroutine は par goto 文とほぼ同等に扱うことが出来る。 | |
194 また、Code Gear は par goto 文で書き出す Output Data Gear を指定して実行するため、Data Gear の書き出し元が推測しやすい。 | |
56 | 195 |
196 Go 言語での OpenMP と同様に Twice を実装しGears OS と比較を行う。 | |
75 | 197 こちらも実行環境は \tabref{powerEdge}、 $2^{27}$ のデータに対して行い、Gears OS、Go 言語両方とも配列を64個のTask、 goroutineに分割して並列実行を行った。 |
56 | 198 |
58 | 199 \newpage |
200 | |
56 | 201 \begin{figure}[htbp] |
202 \begin{center} | |
58 | 203 \includegraphics[scale=0.6]{./fig/vsgo.pdf} |
56 | 204 \end{center} |
205 \caption{vs Go} | |
206 \label{fig:vsgo} | |
207 \end{figure} | |
208 | |
209 Go 言語は 1CPUと32CPU で約4.33 倍の速度向上が見られた。 | |
58 | 210 こちらも OpenMP と同じく、台数効果自体は Gears OS が高いが、1CPU での実行時間はGo 言語が大幅に速くなっている。 |