Mercurial > hg > Papers > 2015 > yuhi-master

annotate paper/chapter3.tex @ 48:8d6a0f047d5a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
create task in sort bench example
author Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
date Tue, 17 Feb 2015 03:31:37 +0900
parents 712576635154
children f9b73e12a52f
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
48
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
1 \chapter{Cerium を用いた例題}
7
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
2 Cerium は様々な例題を含んでいる。本論文では Bitonic Sort、 Word Count、 FFT の3つの例題を扱う。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
3
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
4 Bitonic Sort は、ベンチマークをとる際の一般的な例題として選択した。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
5
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
6 Word Count は、計算自体は条件に合う word をカウントアップしていくシンプルな内容である。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
7 シンプルな計算でも並列化する事で大きな性能向上を狙える事を示す。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
8
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
9 FFT:Fast Fourier Transform(高速フーリエ変換) は、
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
10 信号処理や画像処理から大規模シミュレーションに至るまで幅広い分野で活用されている計算である。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
11 バタフライ演算などの計算の性質上、データ並列と相性がよく、 GPGPU で高い並列度を維持できる事が知られている。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
12
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
13 以上3つの例題を用いてベンチマークを行っていく。本論文で使用する各種例題について紹介する。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
14
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
15 \section{Bitonic Sort}
48
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
16 \label{sec:about_sort}
7
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
17 Cerium Task Manager を使った Sort である。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
18 Bitonic Sort は配列の分割を行い、分割した部分に対して sort を行う。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
19 分割後の Sort には QuickSort を使用している。Task の構成は以下のようになる。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
20
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
21 \begin{itemize}
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
22 \item SortSimpleTask
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
23 \item QuickSortTask
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
24 \end{itemize}
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
25 指定された数の乱数を生成し、sort する例題である。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
26 SortSimpleTask は Task の割り当てを行う Task である。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
27 QuickSortTask は割り当てられた範囲を QuickSort により Sort する Task である。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
28 図:\ref{fig:sort}に Bitonic Sort の例を示す。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
29 SimpleSortTask は乱数列を分割し、 QuickSortTask に割り当てる。QuickSortTask は割り当てられた部分を Sortする。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
30 分割した部分をQuickSortTaskに割り当て、繰り返し起動していく事でSort を行う。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
31
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
32 \begin{enumerate}
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
33 \item SimpleSortTask が乱数列を分割し、 QuickSortTask に割り当てる
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
34 \item QuickSortTask が割り当てられた部分を Sort する
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
35 \item SimpleSortTask が最初に割り当てた範囲の中間から次の範囲の中間までを QuickSortTask に割り当てる
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
36 \item QuickSortTask が割り当てられた部分を Sort する
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
37 \end{enumerate}
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
38 このようなTaskの分割 →Sort を分割数分繰り返し実行することで全体をSortする。
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
39
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
40 本論文では Bitonic Sort による測定を行う場合、10万入力を Input とするベンチマークを行う。
8
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
41
7
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
42 \begin{figure}[htpb]
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
43 \begin{center}
15
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
44 \includegraphics[scale=0.7]{./images/sort_benchmark.pdf}
7
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
45 \end{center}
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
46 \caption{Bitonic Sort の例}
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
47 \label{fig:sort}
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
48 \end{figure}
8
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
49 \newpage
7
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
50
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
51 \section{Word Count}
8
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
52 WordCount は Input としてファイルを受け取り、ファイルの単語数と行数を集計し、表示する。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
53 空白で区切られたものを単語として扱う。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
54
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
55 Word Count の Task の構成は以下の通りである。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
56
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
57 \begin{itemize}
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
58 \item WordCountTask
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
59 \item PrintTask
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
60 \end{itemize}
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
61
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
62 WordCountTask は Input された data を Word Count し、
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
63 単語数と行数を Output として指定された Data 領域に書き込む Task である。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
64
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
65 Task には分割されたテキストが送られてくるため、送られてきたテキストの前後の状態によっては振る舞いを変える必要がある。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
66 分割により Word の途中で切れてしまう場合があり、その場合だとword数-1する処理が必要になる。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
67 そのため、 WordCountTask は自分が割り当てられた範囲である data の先頭と末尾のパラメータを返す。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
68
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
69 PrintTask は WordCountTask によって書き出された単語数と行数を集計し、出力する Task である。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
70 集計時は全 WordCount の結果を照らし合わせ、分割されたテキストを正しく整合する。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
71 PrintTask は WordCountTask を wait する設定で、全ての WordCountTask が終了したあとに動作する。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
72
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
73 WordCount の対象として入力されたファイルは、 mmap を用いてメモリに展開する。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
74 その後データを 16KByte の大きさに分割しながら WordCountTask に割り当てていく。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
75
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
76 各 Task 間の data の流れを図:\ref{fig:wordcount}に示す。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
77
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
78 \begin{figure}[htpb]
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
79 \begin{center}
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
80 \includegraphics[scale=0.7]{./images/wordcount.pdf}
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
81 \end{center}
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
82 \caption{WordCountのフロー}
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
83 \label{fig:wordcount}
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
84 \end{figure}
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
85
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
86 \clearpage
7
786db8c94c6e Bitonic sort example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
87
0
aae08d907517 first commit
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 \section{FFT}
8
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
89 FFT:Fast Fourier Transform(高速フーリエ変換) は、フーリエ変換と周波数フィルタによる画像処理を行う例題である。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
90 今回は入力として受け取った画像に対してハイパスフィルターを行う例題である。
0
aae08d907517 first commit
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
91
8
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
92 FFT の Task の構成は以下のとおりである。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
93
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
94 \begin{itemize}
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
95 \item BitReverse
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
96 \item Butteerfly
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
97 \item HighPassFilter
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
98 \item SpinFact
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
99 \item Transpose
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
100 \end{itemize}
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
101
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
102 FFT は画像 Data に対して様々な Task を割り当てる。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
103 入力は比較的大きなサイズを想定している。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
104 Input と Output を繰り返し行うと、特に GPU だとボトルネックになってしまう。
8fa7b93195cf multicore(benchmark is not yet)
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
105 このベンチマークで並列度を維持するにはデータ並列実行に対応し、データ依存で並列化を可能にする必要がある。
0
aae08d907517 first commit
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
106
48
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
107 \section{Task の生成}
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
108 Cerium において並列処理を行う場合、 Task を大量に生成する場合がある。
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
109 WordCount や BitonicSort がそれにあたり、データの分割数分 Task の生成を行う必要がある。
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
110 しかし、そういった場合において一気に Task を生成して実行を行うと著しく性能が低下する。
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
111 起動していなくても Task そのものがメモリを圧迫してしまい、処理速度が低下する。
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
112 Task の生成と実行を並行して行う必要があり、Task は徐々に一定数ごとに生成されるべきである。
0
aae08d907517 first commit
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
113
48
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
114 Sort の例題を元に Task の生成について考える。
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
115 Sort の手順は\ref{sec:about_sort}節でも述べたが、
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
116 「乱数列を分割して Sort 」と
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
117 「割り当てた範囲の中間から次の範囲の中間までを Sort 」2つの Sort により構成される。
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
118 「乱数列を分割して Sort」を fsort 、
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
119 「割り当てた範囲の中間から次の範囲の中間までを Sort 」を bsort とする。
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
120 2つの Sort の構成を図:\ref{fig:fsort_bsort}に示す。
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
121
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
122 \begin{figure}[htpb]
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
123 \begin{center}
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
124 \includegraphics[scale=0.7]{./images/fsort_bsort.pdf}
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
125 \end{center}
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
126 \caption{fsort と bsort}
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
127 \label{fig:sort}
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
128 \end{figure}
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
129
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
130 bsort は fsort の結果に対して Sort を行う。つまりこの2つの Sort 間には依存関係が存在する。
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
131 更にステージが次へ進むと fsort は前のステージの bsort の結果に対して Sort を行うため、
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
132 更に依存関係が存在する。
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
133 例題に関する依存関係を記述しながら、Task を徐々に生成する依存関係も記述するため、
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
134 Task 生成部分は複雑になるという問題がある。
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
135 Sort の例題における依存関係の記述を行う Task を SortSimple とし、ソースコード:\ref{src:sort_dependency}に示す。
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
136
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
137 \begin{lstlisting}[frame=lrbt,label=src:sort_rependency,caption=Sort の例題における依存関係の記述,numbers=left]
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
138 static int
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
139 sort_start(SchedTask *manager, void *d, void *e)
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
140 {
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
141 Sort *s = (Sort*)manager->get_param(0);
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
142 long half_num = s->split_num-1;
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
143
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
144 for (int i = 0; i < s->split_num-1; i++) {
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
145 s->fsort[i] = manager->create_task(QUICK_SORT,
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
146 (memaddr)&s->data[i*block_num], sizeof(Data)*block_num,
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
147 (memaddr)&s->data[i*block_num], sizeof(Data)*block_num);
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
148
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
149 if (i>0 && s->bsort[i-1]) {
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
150 s->fsort[i]->wait_for(s->bsort[i-1]);
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
151 }
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
152 if (i<s->split_num-2 && s->bsort[i]) {
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
153 s->fsort[i]->wait_for(s->bsort[i]);
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
154 }
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
155 }
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
156
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
157 HTaskPtr restart = manager->create_task(SortSimple,0,0,0,0);
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
158 restart->set_param(0,(memaddr)s);
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
159 if (!all) restart->wait_for(s->fsort[0]);
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
160 for (int i = 0; i < s->split_num; i++) {
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
161 s->fsort[i]->spawn();
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
162 }
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
163 if (sort_count == 1) {
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
164 // last loop wait for all task
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
165 for (int i = 0; i < half_num; i++) {
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
166 restart->wait_for(s->bsort[i]);
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
167 s->bsort[i]->auto_free();
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
168 }
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
169 }
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
170 restart->spawn();
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
171
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
172 return 0;
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
173 }
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
174 \end{lstlisting}
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
175
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
176 \begin{itemize}
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
177 \item 13行目 : fsort が前のステージの fsort の結果を wait する
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
178 \item 16行目 : bsort が fsort の結果に対して wait する
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
179 \item 20行目 : SortSimple 内で SortSimple Task を生成する事で再起を行う
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
180 \item 23行目 : このループで分割ブロックの分だけ Task を生成している
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
181 \item 28行目 : ループの最後は全ての Task が終了するのを待つ
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
182 \end{itemize}
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
183
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
184 このように例題ごとの依存関係と、Task をブロックで区切って徐々に生成していくための依存関係
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
185 の両方を記述しなければならない。
8d6a0f047d5a create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
186 Task 間で wait\_for することで依存関係を設定するのではなく、 Data Dependency により依存関係を記述できる事が望ましい。