Mercurial > hg > Papers > 2012 > yutaka-master
diff paper/chapter3.tex @ 17:6e393cf72b37 draft
add explanation
author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Sat, 11 Feb 2012 13:18:32 +0900 |
parents | 82de4669cc34 |
children | 140aec35135c |
line wrap: on
line diff
--- a/paper/chapter3.tex Fri Feb 10 18:37:22 2012 +0900 +++ b/paper/chapter3.tex Sat Feb 11 13:18:32 2012 +0900 @@ -6,6 +6,7 @@ \item WordCountTask \item PrintTask \end{enumerate} + WordCountTaskは、input された data を word count し、単語数と行数を output に指定された data 領域に書きこむTaskである。 分割されたデータが送られてくるため、分割された前後のテキストがどうなっているかはわからない。そのため担当範囲であるデータの先頭と末尾のパラメータを単語数と行数の他に付け加える。後にそのデータを他のword count 結果と照らし合わせ、分割されたテキストを正しく整合する。 PrintTask は WordCountTask によって書き出された単語数と行数を集計し、出力するTaskである。WordCountTask を wait する設定で、すべてのWordCountTaskが終了したあとに、動作する。 @@ -37,15 +38,44 @@ 100MBのテキストを扱う場合には、Linux と比べ15倍ほどの差が見られた。200MB の場合は約5倍ほどであるのは、PPE のメモリ容量が256MBとなっており、200MBのファイルを扱う場合には、頻繁にスワップなどが起きているため、ファイルのIOの部分でのオーバヘッドが高いと考えられる。通常のwcコマンドよりも Cerium を用いた wc が高い性能を示した。 +% 適当に加筆修正してください \section{Sort} 例題としてTaskManagerを使ったSortを実装した。Taskの構成は以下の通りである。 \begin{enumerate} +\item SortSimpleTask \item QuickSortTask -\item SortSimpleTask \end{enumerate} -指定された数の乱数を生成し、Sortする例題である。 + +指定された数の乱数を生成し、Sort を行う例題である。 +SortSimpleTask は、Task の割り当てを行う Task である。 +始めに乱数列を分割し、QuickSortTask に割り当てる。 +QuickSortTask は、割り当てられた範囲を Sort する。 +次に、SortSimpleTask は、最初に分割して割り当てた範囲の中間から次の範囲の中間までをQuickSortTaskに割り当てる。 +このようなTaskの割り当てを分割数分、繰り返し実行することで全体を Sort する。(\figref{sort-graf}) + +\begin{figure}[htb] + \begin{center} + \includegraphics[scale=0.70]{./images/sort.pdf} + \end{center} + \caption{Sort flow} + \label{fig:sort-graf} +\end{figure} +サイズを 100MB, 200MB としたテキストファイルを対象に、速度の測定を行った。Linux wc は PS3上の Linux のが提供するwcコマンドを用いた結果で PPE 1基を利用したものである。Cerium wc は SPE 6基 を用い今回実装した word count の計測結果である。(\tabref{wc_speed}) +10万入力のソートの速度の測定を行った。 PPE 1基のみを利用したものと、SPE 6 基を利用したものの計測結果である。(\tabref{sort_speed}) + +\begin{table}[!htb] + \begin{center} + \caption{speed of Sort} \label{tab:sort_speed} + \hbox to\hsize{\hfil + \begin{tabular}{|c|c|c|c|} \hline + Sort & time(sec) \\ \hline + PPE & 6.2 \\ \hline + PPE + SPE & 1.1 \\ \hline + \end{tabular}\hfil} + \end{center} +\end{table} \section{Prime Counter} 例題としてTaskManagerを使ったPrime Counterを実装した。Taskの構成は以下の通りである。 @@ -53,6 +83,7 @@ \item PrimeTask \item PrintTask \end{enumerate} + PrimeTaskは、指示された範囲を素数判定し、渡された配列に結果を収めるTaskである。 ミラー-ラビン素数判定法を用いて、2, 3, 5, 7 及び 11 について調べることで、$2{,}152{,}302{,}898{,}747$以下において決定的アルゴリズムにしている。\cite{Jaeschke93} % 参考文献 http://primes.utm.edu/prove/prove2_3.html @@ -60,3 +91,16 @@ PrintTaskは、PrimeTaskによって判定された素数を出力するTaskである。出力指示がされている場合のみ、素数を出力する。 +10万までの範囲の全ての素数の数え上げを行った。 PPE 1基のみを利用したものと、SPE 6 基を利用したものの計測結果である。(\tabref{prime_speed}) + +\begin{table}[!htb] + \begin{center} + \caption{speed of Prime Counter} \label{tab:prime_speed} + \hbox to\hsize{\hfil + \begin{tabular}{|c|c|c|c|} \hline + Sort & time(sec) \\ \hline + PPE & 2.1 \\ \hline + PPE + SPE & 0.6 \\ \hline + \end{tabular}\hfil} + \end{center} +\end{table}