Mercurial > hg > Papers > 2015 > yuhi-master
annotate paper/chapter3.tex @ 15:712576635154
gpgpu
| author | Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 09 Feb 2015 11:32:28 +0900 |
| parents | 8fa7b93195cf |
| children | 8d6a0f047d5a |
| rev | line source |
|---|---|
| 0 | 1 \chapter{Ceriumを用いた例題} |
| 7 | 2 Cerium は様々な例題を含んでいる。本論文では Bitonic Sort、 Word Count、 FFT の3つの例題を扱う。 |
| 3 | |
| 4 Bitonic Sort は、ベンチマークをとる際の一般的な例題として選択した。 | |
| 5 | |
| 6 Word Count は、計算自体は条件に合う word をカウントアップしていくシンプルな内容である。 | |
| 7 シンプルな計算でも並列化する事で大きな性能向上を狙える事を示す。 | |
| 8 | |
| 9 FFT:Fast Fourier Transform(高速フーリエ変換) は、 | |
| 10 信号処理や画像処理から大規模シミュレーションに至るまで幅広い分野で活用されている計算である。 | |
| 11 バタフライ演算などの計算の性質上、データ並列と相性がよく、 GPGPU で高い並列度を維持できる事が知られている。 | |
| 12 | |
| 13 以上3つの例題を用いてベンチマークを行っていく。本論文で使用する各種例題について紹介する。 | |
| 14 | |
| 15 \section{Bitonic Sort} | |
| 16 Cerium Task Manager を使った Sort である。 | |
| 17 Bitonic Sort は配列の分割を行い、分割した部分に対して sort を行う。 | |
| 18 分割後の Sort には QuickSort を使用している。Task の構成は以下のようになる。 | |
| 19 | |
| 20 \begin{itemize} | |
| 21 \item SortSimpleTask | |
| 22 \item QuickSortTask | |
| 23 \end{itemize} | |
| 24 指定された数の乱数を生成し、sort する例題である。 | |
| 25 SortSimpleTask は Task の割り当てを行う Task である。 | |
| 26 QuickSortTask は割り当てられた範囲を QuickSort により Sort する Task である。 | |
| 27 図:\ref{fig:sort}に Bitonic Sort の例を示す。 | |
| 28 SimpleSortTask は乱数列を分割し、 QuickSortTask に割り当てる。QuickSortTask は割り当てられた部分を Sortする。 | |
| 29 分割した部分をQuickSortTaskに割り当て、繰り返し起動していく事でSort を行う。 | |
| 30 | |
| 31 \begin{enumerate} | |
| 32 \item SimpleSortTask が乱数列を分割し、 QuickSortTask に割り当てる | |
| 33 \item QuickSortTask が割り当てられた部分を Sort する | |
| 34 \item SimpleSortTask が最初に割り当てた範囲の中間から次の範囲の中間までを QuickSortTask に割り当てる | |
| 35 \item QuickSortTask が割り当てられた部分を Sort する | |
| 36 \end{enumerate} | |
| 37 このようなTaskの分割 →Sort を分割数分繰り返し実行することで全体をSortする。 | |
| 38 | |
| 39 本論文では Bitonic Sort による測定を行う場合、10万入力を Input とするベンチマークを行う。 | |
|
8
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
40 |
| 7 | 41 \begin{figure}[htpb] |
| 42 \begin{center} | |
| 15 | 43 \includegraphics[scale=0.7]{./images/sort_benchmark.pdf} |
| 7 | 44 \end{center} |
| 45 \caption{Bitonic Sort の例} | |
| 46 \label{fig:sort} | |
| 47 \end{figure} | |
|
8
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
48 \newpage |
| 7 | 49 |
| 50 \section{Word Count} | |
|
8
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
51 WordCount は Input としてファイルを受け取り、ファイルの単語数と行数を集計し、表示する。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
52 空白で区切られたものを単語として扱う。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
53 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
54 Word Count の Task の構成は以下の通りである。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
55 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
56 \begin{itemize} |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
57 \item WordCountTask |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
58 \item PrintTask |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
59 \end{itemize} |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
60 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
61 WordCountTask は Input された data を Word Count し、 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
62 単語数と行数を Output として指定された Data 領域に書き込む Task である。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
63 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
64 Task には分割されたテキストが送られてくるため、送られてきたテキストの前後の状態によっては振る舞いを変える必要がある。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
65 分割により Word の途中で切れてしまう場合があり、その場合だとword数-1する処理が必要になる。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
66 そのため、 WordCountTask は自分が割り当てられた範囲である data の先頭と末尾のパラメータを返す。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
67 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
68 PrintTask は WordCountTask によって書き出された単語数と行数を集計し、出力する Task である。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
69 集計時は全 WordCount の結果を照らし合わせ、分割されたテキストを正しく整合する。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
70 PrintTask は WordCountTask を wait する設定で、全ての WordCountTask が終了したあとに動作する。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
71 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
72 WordCount の対象として入力されたファイルは、 mmap を用いてメモリに展開する。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
73 その後データを 16KByte の大きさに分割しながら WordCountTask に割り当てていく。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
74 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
75 各 Task 間の data の流れを図:\ref{fig:wordcount}に示す。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
76 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
77 \begin{figure}[htpb] |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
78 \begin{center} |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
79 \includegraphics[scale=0.7]{./images/wordcount.pdf} |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
80 \end{center} |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
81 \caption{WordCountのフロー} |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
82 \label{fig:wordcount} |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
83 \end{figure} |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
84 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
85 \clearpage |
| 7 | 86 |
| 0 | 87 \section{FFT} |
|
8
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
88 FFT:Fast Fourier Transform(高速フーリエ変換) は、フーリエ変換と周波数フィルタによる画像処理を行う例題である。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
89 今回は入力として受け取った画像に対してハイパスフィルターを行う例題である。 |
| 0 | 90 |
|
8
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
91 FFT の Task の構成は以下のとおりである。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
92 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
93 \begin{itemize} |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
94 \item BitReverse |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
95 \item Butteerfly |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
96 \item HighPassFilter |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
97 \item SpinFact |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
98 \item Transpose |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
99 \end{itemize} |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
100 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
101 FFT は画像 Data に対して様々な Task を割り当てる。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
102 入力は比較的大きなサイズを想定している。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
103 Input と Output を繰り返し行うと、特に GPU だとボトルネックになってしまう。 |
|
8fa7b93195cf
multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
104 このベンチマークで並列度を維持するにはデータ並列実行に対応し、データ依存で並列化を可能にする必要がある。 |
| 0 | 105 |
| 106 |