|
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 とするベンチマークを行う。
|
|
|
40 \begin{figure}[htpb]
|
|
|
41 \begin{center}
|
|
|
42 \includegraphics[scale=0.7]{./images/sort.pdf}
|
|
|
43 \end{center}
|
|
|
44 \caption{Bitonic Sort の例}
|
|
|
45 \label{fig:sort}
|
|
|
46 \end{figure}
|
|
|
47
|
|
|
48 \section{Word Count}
|
|
|
49
|
|
0
|
50 \section{FFT}
|
|
|
51
|
|
|
52
|
|
|
53
|
|
|
54
|
|
|
55
|
|
|
56
|
