Mercurial > hg > Papers > 2012 > yutaka-master

comparison paper/chapter3.tex @ 17:6e393cf72b37 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
16:598336b53547 17:6e393cf72b37
4 例題としTaskManagerを使ったWordCountを実装した。Taskの構成は以下のである。 4 例題としTaskManagerを使ったWordCountを実装した。Taskの構成は以下のである。
5 \begin{enumerate} 5 \begin{enumerate}
6 \item WordCountTask 6 \item WordCountTask
7 \item PrintTask 7 \item PrintTask
8 \end{enumerate} 8 \end{enumerate}
9
9 WordCountTaskは、input された data を word count し、単語数と行数を output に指定された data 領域に書きこむTaskである。 10 WordCountTaskは、input された data を word count し、単語数と行数を output に指定された data 領域に書きこむTaskである。
10 分割されたデータが送られてくるため、分割された前後のテキストがどうなっているかはわからない。そのため担当範囲であるデータの先頭と末尾のパラメータを単語数と行数の他に付け加える。後にそのデータを他のword count 結果と照らし合わせ、分割されたテキストを正しく整合する。 11 分割されたデータが送られてくるため、分割された前後のテキストがどうなっているかはわからない。そのため担当範囲であるデータの先頭と末尾のパラメータを単語数と行数の他に付け加える。後にそのデータを他のword count 結果と照らし合わせ、分割されたテキストを正しく整合する。
11 PrintTask は WordCountTask によって書き出された単語数と行数を集計し、出力するTaskである。WordCountTask を wait する設定で、すべてのWordCountTaskが終了したあとに、動作する。 12 PrintTask は WordCountTask によって書き出された単語数と行数を集計し、出力するTaskである。WordCountTask を wait する設定で、すべてのWordCountTaskが終了したあとに、動作する。
12 word count 対象として入力されたファイルは、mmapを用いてメモリに展開する。その後データを16kbyteの大きさに分割しながら、WordCountTaskに割り当てていく。(\figref{wc-graf}) 13 word count 対象として入力されたファイルは、mmapを用いてメモリに展開する。その後データを16kbyteの大きさに分割しながら、WordCountTaskに割り当てていく。(\figref{wc-graf})
13 14
35 \end{center} 36 \end{center}
36 \end{table} 37 \end{table}
37 38
38 100MBのテキストを扱う場合には、Linux と比べ15倍ほどの差が見られた。200MB の場合は約5倍ほどであるのは、PPE のメモリ容量が256MBとなっており、200MBのファイルを扱う場合には、頻繁にスワップなどが起きているため、ファイルのIOの部分でのオーバヘッドが高いと考えられる。通常のwcコマンドよりも Cerium を用いた wc が高い性能を示した。 39 100MBのテキストを扱う場合には、Linux と比べ15倍ほどの差が見られた。200MB の場合は約5倍ほどであるのは、PPE のメモリ容量が256MBとなっており、200MBのファイルを扱う場合には、頻繁にスワップなどが起きているため、ファイルのIOの部分でのオーバヘッドが高いと考えられる。通常のwcコマンドよりも Cerium を用いた wc が高い性能を示した。
39 40
41 % 適当に加筆修正してください
40 \section{Sort} 42 \section{Sort}
41 例題としてTaskManagerを使ったSortを実装した。Taskの構成は以下の通りである。 43 例題としてTaskManagerを使ったSortを実装した。Taskの構成は以下の通りである。
42 \begin{enumerate} 44 \begin{enumerate}
45 \item SortSimpleTask
43 \item QuickSortTask 46 \item QuickSortTask
44 \item SortSimpleTask
45 \end{enumerate} 47 \end{enumerate}
46 指定された数の乱数を生成し、Sortする例題である。
47 48
49 指定された数の乱数を生成し、Sort を行う例題である。
50 SortSimpleTask は、Task の割り当てを行う Task である。
51 始めに乱数列を分割し、QuickSortTask に割り当てる。
52 QuickSortTask は、割り当てられた範囲を Sort する。
53 次に、SortSimpleTask は、最初に分割して割り当てた範囲の中間から次の範囲の中間までをQuickSortTaskに割り当てる。
54 このようなTaskの割り当てを分割数分、繰り返し実行することで全体を Sort する。(\figref{sort-graf})
48 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}
63
64 サイズを 100MB, 200MB としたテキストファイルを対象に、速度の測定を行った。Linux wc は PS3上の Linux のが提供するwcコマンドを用いた結果で PPE 1基を利用したものである。Cerium wc は SPE 6基　を用い今回実装した word count の計測結果である。(\tabref{wc_speed})
65
66 10万入力のソートの速度の測定を行った。 PPE 1基のみを利用したものと、SPE 6 基を利用したものの計測結果である。(\tabref{sort_speed})
67
68 \begin{table}[!htb]
69 \begin{center}
70 \caption{speed of Sort} \label{tab:sort_speed}
71 \hbox to\hsize{\hfil
72 \begin{tabular}{|c|c|c|c|} \hline
73 Sort & time(sec) \\ \hline
74 PPE & 6.2 \\ \hline
75 PPE + SPE & 1.1 \\ \hline
76 \end{tabular}\hfil}
77 \end{center}
78 \end{table}
49 79
50 \section{Prime Counter} 80 \section{Prime Counter}
51 例題としてTaskManagerを使ったPrime Counterを実装した。Taskの構成は以下の通りである。 81 例題としてTaskManagerを使ったPrime Counterを実装した。Taskの構成は以下の通りである。
52 \begin{enumerate} 82 \begin{enumerate}
53 \item PrimeTask 83 \item PrimeTask
54 \item PrintTask 84 \item PrintTask
55 \end{enumerate} 85 \end{enumerate}
86
56 PrimeTaskは、指示された範囲を素数判定し、渡された配列に結果を収めるTaskである。 87 PrimeTaskは、指示された範囲を素数判定し、渡された配列に結果を収めるTaskである。
57 ミラー-ラビン素数判定法を用いて、2, 3, 5, 7 及び 11 について調べることで、$2{,}152{,}302{,}898{,}747$以下において決定的アルゴリズムにしている。\cite{Jaeschke93} 88 ミラー-ラビン素数判定法を用いて、2, 3, 5, 7 及び 11 について調べることで、$2{,}152{,}302{,}898{,}747$以下において決定的アルゴリズムにしている。\cite{Jaeschke93}
58 % 参考文献 http://primes.utm.edu/prove/prove2_3.html 89 % 参考文献 http://primes.utm.edu/prove/prove2_3.html
59 % Jaeschkeによる 90 % Jaeschkeによる
60 PrintTaskは、PrimeTaskによって判定された素数を出力するTaskである。出力指示がされている場合のみ、素数を出力する。 91 PrintTaskは、PrimeTaskによって判定された素数を出力するTaskである。出力指示がされている場合のみ、素数を出力する。
61 92
62 93
94 10万までの範囲の全ての素数の数え上げを行った。 PPE 1基のみを利用したものと、SPE 6 基を利用したものの計測結果である。(\tabref{prime_speed})
95
96 \begin{table}[!htb]
97 \begin{center}
98 \caption{speed of Prime Counter} \label{tab:prime_speed}
99 \hbox to\hsize{\hfil
100 \begin{tabular}{|c|c|c|c|} \hline
101 Sort & time(sec) \\ \hline
102 PPE & 2.1 \\ \hline
103 PPE + SPE & 0.6 \\ \hline
104 \end{tabular}\hfil}
105 \end{center}
106 \end{table}