Mercurial > hg > Papers > 2012 > yutaka-master

annotate paper/chapter3.tex @ 8:82de4669cc34 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix prime
author Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
date Thu, 09 Feb 2012 04:50:53 +0900
parents 20d87c5e225a
children 6e393cf72b37
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
1 \chapter{TaskManagerを使った例題}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
2 本章では、TaskManager を使った例題を紹介する
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
3 \section{WordCount}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
4 例題としTaskManagerを使ったWordCountを実装した。Taskの構成は以下のである。
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
5 \begin{enumerate}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
6 \item WordCountTask
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
7 \item PrintTask
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
8 \end{enumerate}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
9 WordCountTaskは、input された data を word count し、単語数と行数を output に指定された data 領域に書きこむTaskである。
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
10 分割されたデータが送られてくるため、分割された前後のテキストがどうなっているかはわからない。そのため担当範囲であるデータの先頭と末尾のパラメータを単語数と行数の他に付け加える。後にそのデータを他のword count 結果と照らし合わせ、分割されたテキストを正しく整合する。
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
11 PrintTask は WordCountTask によって書き出された単語数と行数を集計し、出力するTaskである。WordCountTask を wait する設定で、すべてのWordCountTaskが終了したあとに、動作する。
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
12 word count 対象として入力されたファイルは、mmapを用いてメモリに展開する。その後データを16kbyteの大きさに分割しながら、WordCountTaskに割り当てていく。(\figref{wc-graf})
0
6d80c2c895e4 first commit
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13
1
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
14 \begin{figure}[htb]
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
15 \begin{center}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
16 \includegraphics[scale=0.70]{./images/wc_graf1.pdf}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
17 \end{center}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
18 \caption{wordcount flow}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
19 \label{fig:wc-graf}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
20 \end{figure}
0
6d80c2c895e4 first commit
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21
4
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
22 サイズを 100MB, 200MB としたテキストファイルを対象に、速度の測定を行った。Linux wc は PS3上の Linux のが提供するwcコマンドを用いた結果で PPE 1基を利用したものである。Cerium wc は SPE 6基　を用い今回実装した word count の計測結果である。(\tabref{wc_speed})
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
23
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
24 \begin{table}[!htb]
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
25 \begin{center}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
26 \caption{speed of WordCount} \label{tab:wc_speed}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
27 \hbox to\hsize{\hfil
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
28 \begin{tabular}{|c|c|c|c|} \hline
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
29 wc & file size(MB) & time(sec) \\ \hline
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
30 Linux & 100 & 30.9 \\ \hline
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
31 Linux & 200 & 62.8 \\ \hline
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
32 Cerium & 100 & 2.2 \\ \hline
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
33 Cerium & 200 & 12.8 \\ \hline
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
34 \end{tabular}\hfil}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
35 \end{center}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
36 \end{table}
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
37
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
38 100MBのテキストを扱う場合には、Linux と比べ15倍ほどの差が見られた。200MB の場合は約5倍ほどであるのは、PPE のメモリ容量が256MBとなっており、200MBのファイルを扱う場合には、頻繁にスワップなどが起きているため、ファイルのIOの部分でのオーバヘッドが高いと考えられる。通常のwcコマンドよりも Cerium を用いた wc が高い性能を示した。
1
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
39
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
40 \section{Sort}
3
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
41 例題としてTaskManagerを使ったSortを実装した。Taskの構成は以下の通りである。
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
42 \begin{enumerate}
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
43 \item QuickSortTask
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
44 \item SortSimpleTask
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
45 \end{enumerate}
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
46 指定された数の乱数を生成し、Sortする例題である。
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
47
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
48
1
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
49
8
82de4669cc34 fix prime
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
50 \section{Prime Counter}
82de4669cc34 fix prime
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
51 例題としてTaskManagerを使ったPrime Counterを実装した。Taskの構成は以下の通りである。
3
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
52 \begin{enumerate}
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
53 \item PrimeTask
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
54 \item PrintTask
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
55 \end{enumerate}
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
56 PrimeTaskは、指示された範囲を素数判定し、渡された配列に結果を収めるTaskである。
8
82de4669cc34 fix prime
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
57 ミラー-ラビン素数判定法を用いて、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
58 % 参考文献 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
59 % Jaeschkeによる
181befc58e1d add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
60 PrintTaskは、PrimeTaskによって判定された素数を出力するTaskである。出力指示がされている場合のみ、素数を出力する。
1
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
61
Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
62