Mercurial > hg > Papers > 2012 > yutaka-master
annotate paper/chapter3.tex @ 34:472f45ab9fca draft default tip
fix
| author | Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 16 Feb 2012 23:46:16 +0900 |
| parents | 140aec35135c |
| children |
| rev | line source |
|---|---|
| 1 | 1 \chapter{TaskManagerを使った例題} |
| 2 本章では、TaskManager を使った例題を紹介する | |
| 3 \section{WordCount} | |
| 4 例題としTaskManagerを使ったWordCountを実装した。Taskの構成は以下のである。 | |
| 5 \begin{enumerate} | |
| 6 \item WordCountTask | |
| 7 \item PrintTask | |
| 8 \end{enumerate} | |
| 17 | 9 |
| 1 | 10 WordCountTaskは、input された data を word count し、単語数と行数を output に指定された data 領域に書きこむTaskである。 |
| 11 分割されたデータが送られてくるため、分割された前後のテキストがどうなっているかはわからない。そのため担当範囲であるデータの先頭と末尾のパラメータを単語数と行数の他に付け加える。後にそのデータを他のword count 結果と照らし合わせ、分割されたテキストを正しく整合する。 | |
| 12 PrintTask は WordCountTask によって書き出された単語数と行数を集計し、出力するTaskである。WordCountTask を wait する設定で、すべてのWordCountTaskが終了したあとに、動作する。 | |
| 13 word count 対象として入力されたファイルは、mmapを用いてメモリに展開する。その後データを16kbyteの大きさに分割しながら、WordCountTaskに割り当てていく。(\figref{wc-graf}) | |
| 0 | 14 |
| 1 | 15 \begin{figure}[htb] |
| 16 \begin{center} | |
| 17 \includegraphics[scale=0.70]{./images/wc_graf1.pdf} | |
| 18 \end{center} | |
| 19 \caption{wordcount flow} | |
| 20 \label{fig:wc-graf} | |
| 21 \end{figure} | |
| 0 | 22 |
| 4 | 23 サイズを 100MB, 200MB としたテキストファイルを対象に、速度の測定を行った。Linux wc は PS3上の Linux のが提供するwcコマンドを用いた結果で PPE 1基を利用したものである。Cerium wc は SPE 6基 を用い今回実装した word count の計測結果である。(\tabref{wc_speed}) |
| 24 | |
| 25 \begin{table}[!htb] | |
| 26 \begin{center} | |
| 27 \caption{speed of WordCount} \label{tab:wc_speed} | |
| 28 \hbox to\hsize{\hfil | |
| 29 \begin{tabular}{|c|c|c|c|} \hline | |
| 30 wc & file size(MB) & time(sec) \\ \hline | |
| 31 Linux & 100 & 30.9 \\ \hline | |
| 32 Linux & 200 & 62.8 \\ \hline | |
| 33 Cerium & 100 & 2.2 \\ \hline | |
| 34 Cerium & 200 & 12.8 \\ \hline | |
| 35 \end{tabular}\hfil} | |
| 36 \end{center} | |
| 37 \end{table} | |
| 38 | |
| 39 100MBのテキストを扱う場合には、Linux と比べ15倍ほどの差が見られた。200MB の場合は約5倍ほどであるのは、PPE のメモリ容量が256MBとなっており、200MBのファイルを扱う場合には、頻繁にスワップなどが起きているため、ファイルのIOの部分でのオーバヘッドが高いと考えられる。通常のwcコマンドよりも Cerium を用いた wc が高い性能を示した。 | |
| 1 | 40 |
| 17 | 41 % 適当に加筆修正してください |
| 1 | 42 \section{Sort} |
|
3
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
43 例題としてTaskManagerを使ったSortを実装した。Taskの構成は以下の通りである。 |
|
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
44 \begin{enumerate} |
| 17 | 45 \item SortSimpleTask |
|
3
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
46 \item QuickSortTask |
|
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
47 \end{enumerate} |
| 17 | 48 |
| 49 指定された数の乱数を生成し、Sort を行う例題である。 | |
| 50 SortSimpleTask は、Task の割り当てを行う Task である。 | |
| 51 始めに乱数列を分割し、QuickSortTask に割り当てる。 | |
| 52 QuickSortTask は、割り当てられた範囲を Sort する。 | |
| 53 次に、SortSimpleTask は、最初に分割して割り当てた範囲の中間から次の範囲の中間までをQuickSortTaskに割り当てる。 | |
| 54 このようなTaskの割り当てを分割数分、繰り返し実行することで全体を Sort する。(\figref{sort-graf}) | |
| 55 | |
| 56 \begin{figure}[htb] | |
| 57 \begin{center} | |
| 58 \includegraphics[scale=0.70]{./images/sort.pdf} | |
| 59 \end{center} | |
| 60 \caption{Sort flow} | |
| 61 \label{fig:sort-graf} | |
| 62 \end{figure} | |
|
3
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
63 |
| 17 | 64 10万入力のソートの速度の測定を行った。 PPE 1基のみを利用したものと、SPE 6 基を利用したものの計測結果である。(\tabref{sort_speed}) |
| 65 | |
| 66 \begin{table}[!htb] | |
| 67 \begin{center} | |
| 68 \caption{speed of Sort} \label{tab:sort_speed} | |
| 69 \hbox to\hsize{\hfil | |
| 70 \begin{tabular}{|c|c|c|c|} \hline | |
| 71 Sort & time(sec) \\ \hline | |
| 72 PPE & 6.2 \\ \hline | |
| 73 PPE + SPE & 1.1 \\ \hline | |
| 74 \end{tabular}\hfil} | |
| 75 \end{center} | |
| 76 \end{table} | |
| 1 | 77 |
| 8 | 78 \section{Prime Counter} |
| 79 例題としてTaskManagerを使ったPrime Counterを実装した。Taskの構成は以下の通りである。 | |
|
3
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
80 \begin{enumerate} |
|
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
81 \item PrimeTask |
|
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
82 \item PrintTask |
|
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
83 \end{enumerate} |
| 17 | 84 |
|
3
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
85 PrimeTaskは、指示された範囲を素数判定し、渡された配列に結果を収めるTaskである。 |
| 8 | 86 ミラー-ラビン素数判定法を用いて、2, 3, 5, 7 及び 11 について調べることで、$2{,}152{,}302{,}898{,}747$以下において決定的アルゴリズムにしている。\cite{Jaeschke93} |
|
3
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
87 % 参考文献 http://primes.utm.edu/prove/prove2_3.html |
|
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
88 % Jaeschkeによる |
|
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
89 PrintTaskは、PrimeTaskによって判定された素数を出力するTaskである。出力指示がされている場合のみ、素数を出力する。 |
| 1 | 90 |
| 91 | |
| 17 | 92 10万までの範囲の全ての素数の数え上げを行った。 PPE 1基のみを利用したものと、SPE 6 基を利用したものの計測結果である。(\tabref{prime_speed}) |
| 93 | |
| 94 \begin{table}[!htb] | |
| 95 \begin{center} | |
| 96 \caption{speed of Prime Counter} \label{tab:prime_speed} | |
| 97 \hbox to\hsize{\hfil | |
| 98 \begin{tabular}{|c|c|c|c|} \hline | |
| 99 Sort & time(sec) \\ \hline | |
| 100 PPE & 2.1 \\ \hline | |
| 101 PPE + SPE & 0.6 \\ \hline | |
| 102 \end{tabular}\hfil} | |
| 103 \end{center} | |
| 104 \end{table} |