view paper/chapter3.tex @ 9:e2b7c59f3d65

push pdf
author Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
date Thu, 29 Jan 2015 16:51:03 +0900 (2015-01-29)
parents 8fa7b93195cf
children 712576635154
line wrap: on
line source
\chapter{Ceriumを用いた例題}
Cerium は様々な例題を含んでいる。本論文では Bitonic Sort、 Word Count、 FFT の3つの例題を扱う。

Bitonic Sort は、ベンチマークをとる際の一般的な例題として選択した。

Word Count は、計算自体は条件に合う word をカウントアップしていくシンプルな内容である。
シンプルな計算でも並列化する事で大きな性能向上を狙える事を示す。

FFT:Fast Fourier Transform(高速フーリエ変換) は、
信号処理や画像処理から大規模シミュレーションに至るまで幅広い分野で活用されている計算である。
バタフライ演算などの計算の性質上、データ並列と相性がよく、 GPGPU で高い並列度を維持できる事が知られている。

以上3つの例題を用いてベンチマークを行っていく。本論文で使用する各種例題について紹介する。

\section{Bitonic Sort}
Cerium Task Manager を使った Sort である。
Bitonic Sort は配列の分割を行い、分割した部分に対して sort を行う。
分割後の Sort には QuickSort を使用している。Task の構成は以下のようになる。

\begin{itemize}
\item SortSimpleTask
\item QuickSortTask
\end{itemize}
指定された数の乱数を生成し、sort する例題である。
SortSimpleTask は Task の割り当てを行う Task である。
QuickSortTask は割り当てられた範囲を QuickSort により Sort する Task である。
図:\ref{fig:sort}に Bitonic Sort の例を示す。
SimpleSortTask は乱数列を分割し、 QuickSortTask に割り当てる。QuickSortTask は割り当てられた部分を Sortする。
分割した部分をQuickSortTaskに割り当て、繰り返し起動していく事でSort を行う。

\begin{enumerate}
  \item SimpleSortTask が乱数列を分割し、 QuickSortTask に割り当てる
  \item QuickSortTask が割り当てられた部分を Sort する
  \item SimpleSortTask が最初に割り当てた範囲の中間から次の範囲の中間までを QuickSortTask に割り当てる
  \item QuickSortTask が割り当てられた部分を Sort する
\end{enumerate}
このようなTaskの分割 →Sort を分割数分繰り返し実行することで全体をSortする。

本論文では Bitonic Sort による測定を行う場合、10万入力を Input とするベンチマークを行う。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/sort.pdf}
  \end{center}
  \caption{Bitonic Sort の例}
  \label{fig:sort}
\end{figure}
\newpage

\section{Word Count}
WordCount は Input としてファイルを受け取り、ファイルの単語数と行数を集計し、表示する。
空白で区切られたものを単語として扱う。

Word Count の Task の構成は以下の通りである。

\begin{itemize}
\item WordCountTask
\item PrintTask
\end{itemize}

WordCountTask は Input された data を Word Count し、
単語数と行数を Output として指定された Data 領域に書き込む Task である。

Task には分割されたテキストが送られてくるため、送られてきたテキストの前後の状態によっては振る舞いを変える必要がある。
分割により Word の途中で切れてしまう場合があり、その場合だとword数-1する処理が必要になる。
そのため、 WordCountTask は自分が割り当てられた範囲である data の先頭と末尾のパラメータを返す。

PrintTask は WordCountTask によって書き出された単語数と行数を集計し、出力する Task である。
集計時は全 WordCount の結果を照らし合わせ、分割されたテキストを正しく整合する。
PrintTask は WordCountTask を wait する設定で、全ての WordCountTask が終了したあとに動作する。

WordCount の対象として入力されたファイルは、 mmap を用いてメモリに展開する。
その後データを 16KByte の大きさに分割しながら WordCountTask に割り当てていく。

各 Task 間の data の流れを図:\ref{fig:wordcount}に示す。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/wordcount.pdf}
  \end{center}
  \caption{WordCountのフロー}
  \label{fig:wordcount}
\end{figure}

\clearpage

\section{FFT}
FFT:Fast Fourier Transform(高速フーリエ変換) は、フーリエ変換と周波数フィルタによる画像処理を行う例題である。
今回は入力として受け取った画像に対してハイパスフィルターを行う例題である。

FFT の Task の構成は以下のとおりである。

\begin{itemize}
\item BitReverse
\item Butteerfly
\item HighPassFilter
\item SpinFact
\item Transpose
\end{itemize}

FFT は画像 Data に対して様々な Task を割り当てる。
入力は比較的大きなサイズを想定している。
Input と Output を繰り返し行うと、特に GPU だとボトルネックになってしまう。
このベンチマークで並列度を維持するにはデータ並列実行に対応し、データ依存で並列化を可能にする必要がある。