Papers/2015/yuhi-master: paper/chapter3.tex annotate

annotate paper/chapter3.tex @ 8:8fa7b93195cf

multicore(benchmark is not yet)

author	Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
date	Thu, 29 Jan 2015 16:49:43 +0900
parents	786db8c94c6e
children	712576635154

rev	line source
0 aae08d907517 first commit Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	1 \chapter{Ceriumを用いた例題}
7 786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	2 Cerium は様々な例題を含んでいる。本論文では Bitonic Sort、 Word Count、 FFT の3つの例題を扱う。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	3
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	4 Bitonic Sort は、ベンチマークをとる際の一般的な例題として選択した。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	5
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	6 Word Count は、計算自体は条件に合う word をカウントアップしていくシンプルな内容である。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	7 シンプルな計算でも並列化する事で大きな性能向上を狙える事を示す。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	8
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	9 FFT:Fast Fourier Transform(高速フーリエ変換) は、
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	10 信号処理や画像処理から大規模シミュレーションに至るまで幅広い分野で活用されている計算である。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	11 バタフライ演算などの計算の性質上、データ並列と相性がよく、 GPGPU で高い並列度を維持できる事が知られている。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	12
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	13 以上3つの例題を用いてベンチマークを行っていく。本論文で使用する各種例題について紹介する。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	14
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	15 \section{Bitonic Sort}
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	16 Cerium Task Manager を使った Sort である。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	17 Bitonic Sort は配列の分割を行い、分割した部分に対して sort を行う。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	18 分割後の Sort には QuickSort を使用している。Task の構成は以下のようになる。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	19
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	20 \begin{itemize}
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	21 \item SortSimpleTask
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	22 \item QuickSortTask
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	23 \end{itemize}
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	24 指定された数の乱数を生成し、sort する例題である。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	25 SortSimpleTask は Task の割り当てを行う Task である。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	26 QuickSortTask は割り当てられた範囲を QuickSort により Sort する Task である。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	27 図:\ref{fig:sort}に Bitonic Sort の例を示す。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	28 SimpleSortTask は乱数列を分割し、 QuickSortTask に割り当てる。QuickSortTask は割り当てられた部分を Sortする。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	29 分割した部分をQuickSortTaskに割り当て、繰り返し起動していく事でSort を行う。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	30
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	31 \begin{enumerate}
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	32 \item SimpleSortTask が乱数列を分割し、 QuickSortTask に割り当てる
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	33 \item QuickSortTask が割り当てられた部分を Sort する
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	34 \item SimpleSortTask が最初に割り当てた範囲の中間から次の範囲の中間までを QuickSortTask に割り当てる
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	35 \item QuickSortTask が割り当てられた部分を Sort する
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	36 \end{enumerate}
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	37 このようなTaskの分割 →Sort を分割数分繰り返し実行することで全体をSortする。
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	38
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	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 786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	41 \begin{figure}[htpb]
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	42 \begin{center}
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	43 \includegraphics[scale=0.7]{./images/sort.pdf}
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	44 \end{center}
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	45 \caption{Bitonic Sort の例}
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	46 \label{fig:sort}
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	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 786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	49
786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	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 786db8c94c6e Bitonic sort example Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: 0 diff changeset	86
0 aae08d907517 first commit Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	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 aae08d907517 first commit Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	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 aae08d907517 first commit Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	105
aae08d907517 first commit Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	106

Mercurial > hg > Papers > 2015 > yuhi-master

annotate paper/chapter3.tex @ 8:8fa7b93195cf