Mercurial > hg > Papers > 2014 > masakoha-thesis > final
annotate paper/chapter4.tex @ 71:6bddfb10df11
fix
| author | Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 25 Feb 2014 21:40:27 +0900 |
| parents | 3988365f6f03 |
| children | 17c93faef65b |
| rev | line source |
|---|---|
|
11
5e67750b1c4f
write chapter label
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
6
diff
changeset
|
1 \chapter{並列処理向け I/O の設計と実装} |
| 0 | 2 \label{chap:poordirection} |
| 3 | |
|
68
9c5f2ffbeb4e
fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
4 \section{map reduce の設計} |
| 47 | 5 |
| 50 | 6 \begin{figure}[htbp] |
| 7 \begin{center} | |
|
68
9c5f2ffbeb4e
fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
8 \includegraphics[width=0.8\textwidth]{fig/mapreduce.pdf} |
| 50 | 9 \end{center} |
| 10 \caption{map reduce image} | |
| 11 \label{fig:mmap} \end{figure} | |
| 12 | |
|
69
3988365f6f03
add eclbkbox.sty
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
68
diff
changeset
|
13 \newpage |
|
3988365f6f03
add eclbkbox.sty
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
68
diff
changeset
|
14 |
| 47 | 15 \section{mmap での実装の問題点} |
| 50 | 16 mmap とは、sys/mman.h に含まれている関数で、ファイルの読み込み等に使用される関数である。 |
| 17 ファイルディスクリプタで指定したファイルを offset から len バイトの範囲を読み込む。 | |
| 18 この時にアドレス addr からメモリを確保するようにする。 | |
| 19 prot には、PROT\_READによるページの読み込み、PROT\_WRITEによるページへの書き込みなどを指定でき、 | |
|
52
1ae8a15f3e94
suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
51
diff
changeset
|
20 flags にはメモリ確保する際のオプションを指定することができる。(表\ref{table:mmap}) |
| 50 | 21 |
| 22 \begin{tiny} | |
| 23 \begin{table}[ht] | |
| 24 \begin{center} | |
| 25 \label{table:mmap} | |
| 26 \small | |
| 27 void * mmap(void *addr, size\_t len, int prot, int flags, int fd, off\_t offset); | |
| 0 | 28 |
| 50 | 29 \begin{tabular}[t]{c|l} |
| 30 \hline | |
| 31 void *addr & メモリに確保するときの先頭のアドレス\\ | |
| 32 \hline | |
| 33 size\_t len & メモリを確保するサイズ\\ | |
| 34 \hline | |
| 35 int prot & ファイルモード選択\\ | |
| 36 \hline | |
| 37 int flags & 確保するときのオプション指定\\ | |
| 38 \hline | |
| 39 int fd & 読み込むファイルのファイルディスクリプタ\\ | |
| 40 \hline | |
| 60 | 41 off\_t offset & ファイル先頭からの読み込み開始位置 \\ |
| 50 | 42 \hline |
| 43 \end{tabular} | |
| 44 \caption{mmap 関数の概要} | |
| 45 \end{center} | |
| 46 \end{table} | |
| 47 \end{tiny} | |
|
37
ce985cabf699
add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
11
diff
changeset
|
48 |
| 50 | 49 mmap でファイルを読み込むタイミングは、mmap 関数が呼ばれたときではなく、mmap した領域に対して何らかのアクセスをしたときに初めてファイルが読み込まれる。 |
| 50 | |
| 51 図\ref{fig:mmap}では、読み込んだファイルを分割して、それらの領域に何らかの処理を加えるときの図である。これらの処理を Task と呼ぶ。 | |
| 52 Task 1 という1個目の Task が実行される。実行されたときに初めてそれらの領域にファイルが読み込まれ、その後何らかの処理が行われ、そして Task 2 も同様に読み込みを行ってから処理が行われる。 | |
| 53 これら Task は並列に実行されるべきであるが、ファイル読み込みの I/O 部分がネックとなり、本来並列実行される Task が読み込み待ちを起こしてしまう恐れがある。 | |
| 54 その上、読み込み方法が OS 依存となるために環境によって左右されやすく、プログラムの書き手が読み込みに関して制御しにくい。 | |
| 55 | |
| 56 それらを解決するためには、ファイル読み込みと Task を分離し、ファイルの読み込みも制御しやすくでき、なおかつ高速で動くのではないかと考えた。 | |
| 49 | 57 |
| 58 \begin{figure}[htbp] | |
| 59 \begin{center} | |
|
59
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
60 \includegraphics[width=0.7\textwidth]{fig/mmap.pdf} |
| 49 | 61 \end{center} |
|
59
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
62 \caption{mmap image} |
| 49 | 63 \label{fig:mmap} \end{figure} |
| 64 | |
|
69
3988365f6f03
add eclbkbox.sty
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
68
diff
changeset
|
65 \newpage |
|
51
06f75bca7a70
suspend blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
50
diff
changeset
|
66 \section{Bloked Read の設計と実装} |
| 60 | 67 Blocked Read とは、読み込みの Task と、それに対する何らかの処理の Task を切り離すための実装方法で、pread 関数にて実装した。 |
| 68 pread 関数は、unistd.h に含まれているので、UNIX 専用の関数である。ファイルディスクリプタで指定したファイルの先頭 から | |
|
69
3988365f6f03
add eclbkbox.sty
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
68
diff
changeset
|
69 offset 分ずれた場所を基準として、その基準から count バイトを読み込み、それを buf に格納する。 |
|
3988365f6f03
add eclbkbox.sty
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
68
diff
changeset
|
70 \ref{table:pread} |
| 60 | 71 |
| 72 \begin{tiny} | |
| 73 \begin{table}[ht] | |
| 74 \begin{center} | |
| 75 \label{table:pread} | |
| 76 \small | |
| 77 ssize\_t pread(int d, void *buf, size\_t nbyte, off\_t offset); | |
| 78 | |
| 79 \begin{tabular}[t]{c|l} | |
| 80 \hline | |
| 81 int d & 読み込むファイルのファイルディスクリプタ\\ | |
| 82 \hline | |
| 83 void *buf & 読み込んだファイルの格納場所 \\ | |
| 84 \hline | |
| 85 size\_t nbyte & 読み込むファイル量\\ | |
| 86 \hline | |
| 87 off\_t offset & ファイル先頭からの読み込み開始位置\\ | |
| 88 \hline | |
| 89 \end{tabular} | |
| 90 \caption{pread 関数の概要} | |
| 91 \end{center} | |
| 92 \end{table} | |
| 93 \end{tiny} | |
| 94 | |
|
52
1ae8a15f3e94
suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
51
diff
changeset
|
95 mmap での実装との違いは、ファイルの読み込みがどのタイミングで起こるかである。 |
|
1ae8a15f3e94
suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
51
diff
changeset
|
96 mmap で実装したときは、Task 1つ 1つが読み込みを行ってから処理を行う。 |
|
1ae8a15f3e94
suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
51
diff
changeset
|
97 それに対して、Blocked Readは、読み込み専用の Read Task と、処理専用の Task を別々に生成する。 |
|
1ae8a15f3e94
suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
51
diff
changeset
|
98 Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行う。 |
|
1ae8a15f3e94
suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
51
diff
changeset
|
99 分割して読み込み終わったら、それぞれの Task が実行される。 |
|
1ae8a15f3e94
suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
51
diff
changeset
|
100 (図\ref{fig:block}) |
|
59
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
101 Read Task が生成されて、その後 Task の生成となるので、Read Task は常に走っている必要がある。 |
|
37
ce985cabf699
add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
11
diff
changeset
|
102 |
| 42 | 103 \begin{figure}[htbp] |
| 104 \begin{center} | |
|
59
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
105 \includegraphics[width=0.8\textwidth]{fig/blockedreadimage.pdf} |
| 42 | 106 \end{center} |
|
51
06f75bca7a70
suspend blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
50
diff
changeset
|
107 \caption{Blocked Read image} |
|
06f75bca7a70
suspend blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
50
diff
changeset
|
108 \label{fig:block} |
| 42 | 109 \end{figure} |
|
37
ce985cabf699
add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
11
diff
changeset
|
110 |
|
59
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
111 図\ref{fig:block} では、Read Task 1つに対して Task 1つ起動しているが、このように1つ1つ生成、起動をすると Task 生成でメモリを圧迫してしまい、全体的な動作に影響を与えてしまう。 |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
112 実際には Task をある一定数まとめた単位で生成し、起動を行っている。この単位を Task Block と定義する。 |
|
37
ce985cabf699
add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
11
diff
changeset
|
113 |
|
59
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
114 Task Block 1つ当たりの Task 量を $n$ とおく。Task 1つ当たりの読み込む量を $L$ とすると、Task Block 1つ当たりの読み込む量は $L \times n$ となる。 |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
115 Blocked Read が読み込み終わってから、Task Blockが起動するようにするので、Blocked Read 1つ当たりの読み込み量も $L \times n$となる。 |
|
37
ce985cabf699
add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
11
diff
changeset
|
116 |
|
59
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
117 もし、Task Block が Blocked Read よりも先走ってしまうとどうなるであろうか。 |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
118 まだ読み込まれていない領域に対して何らかの処理を行ってしまうので、正しい結果が返ってこなくなってしまう。 |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
119 それを防止するために、Blocked Read が読み込み終わってから Task Block が起動されるように wait をかけている。 |
| 42 | 120 |
|
59
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
121 (図\ref{fig:block}) |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
122 \begin{figure}[htbp] |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
123 \begin{center} |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
124 \includegraphics[width=1.0\textwidth]{fig/blockreadtask.pdf} |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
125 \end{center} |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
126 \caption{Blocked Read image} |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
127 \label{fig:block} |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
128 \end{figure} |
|
37
ce985cabf699
add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
11
diff
changeset
|
129 |
|
69
3988365f6f03
add eclbkbox.sty
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
68
diff
changeset
|
130 \newpage |
|
59
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
131 |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
132 \section{I/O 専用 thread の実装} |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
133 Cerium Task Manager では、各種 Task にデバイスを設定することができる。デバイスとは、GPU や CPU であり、GPUを利用するときは GPU\_ANY、CPU を利用するときは SPE\_ANYと設定することによってデバイスを利用できる。 |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
134 |
| 71 | 135 SPE\_ANY を使用すると、Task Manager で CPU の割り振りを自動的に行う。しかし、この機能を使用すると、Blocked Read に影響を与えてしまう。 |
|
59
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
136 |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
137 Blocked Read 、Task それぞれに SPE\_ANY で CPUを自動的に割り振ると、Task Manager 側で自動的に CPU を割り当てる。このように CPU を割り当ててしまうと、本来 Blocked Read は連続で読み込むはずが、他の Task を割り当てられてしまう。 |
|
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
138 (図\ref{fig:speany}) |
| 42 | 139 |
| 140 \begin{figure}[htbp] | |
| 141 \begin{center} | |
| 142 \includegraphics[width=1.0\textwidth]{fig/speany.pdf} | |
| 143 \end{center} | |
|
59
d6f83dd6301f
suspended to write io_0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
52
diff
changeset
|
144 \caption{SPE\_ANY での実装時} |
| 42 | 145 \label{fig:speany} |
| 146 \end{figure} | |
| 147 | |
| 71 | 148 この問題を解決するために、Task Manager に新しく I/O 専用の thread を用意した。(図\ref{fig:addio0}) |
|
68
9c5f2ffbeb4e
fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
149 %この問題を解決するために、Task Manager に IO\_0という新しいデバイス設定を追加した。 |
|
9c5f2ffbeb4e
fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
150 |
| 71 | 151 この設定は他のデバイス設定よりも priority を高く設定している。 |
|
68
9c5f2ffbeb4e
fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
152 |
|
9c5f2ffbeb4e
fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
153 \begin{figure}[htbp] |
|
9c5f2ffbeb4e
fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
154 \begin{center} |
|
9c5f2ffbeb4e
fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
155 \includegraphics[width=0.7\textwidth]{fig/addio_0.pdf} |
|
9c5f2ffbeb4e
fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
156 \end{center} |
|
9c5f2ffbeb4e
fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
157 \caption{IO\_0 の追加} |
|
9c5f2ffbeb4e
fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
158 \label{fig:addio0} |
|
9c5f2ffbeb4e
fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
159 \end{figure} |
|
9c5f2ffbeb4e
fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
160 |
| 71 | 161 SPE\_ANY で使用する CPU の設定よりも高く設定しているので、IO\_0 で設定を行う Read Task に SPE\_ANY で設定した 文字列検索 Task に割り込まれることがなくなる。 |
|
61
35248cabb84d
chaper4 finish??
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
162 (図\ref{fig:io0}) |
| 42 | 163 |
| 164 \begin{figure}[htbp] | |
| 165 \begin{center} | |
| 166 \includegraphics[width=1.0\textwidth]{fig/io0.pdf} | |
| 167 \end{center} | |
| 71 | 168 \caption{Blocked Read Task を IO\_0 での実装時} |
| 42 | 169 \label{fig:io0} |
| 170 \end{figure} | |
| 71 | 171 |
| 172 \newpage | |
| 173 IO\_0 の priority を高く実装したソースコードは以下のようになる。 | |
| 174 \begin{breakbox} | |
| 175 \begin{verbatim} | |
| 176 void * | |
| 177 CpuThreads::cpu_thread_run(void *args) | |
| 178 { | |
| 179 cpu_thread_arg_t *argt = (cpu_thread_arg_t *) args; | |
| 180 | |
| 181 ・・・ | |
| 182 | |
| 183 if (argt->cpuid >= argt->cpu_num) { | |
| 184 // set IO thread priory maximum | |
| 185 int policy; | |
| 186 struct sched_param param; | |
| 187 pthread_getschedparam(pthread_self(), &policy, ¶m); | |
| 188 param.sched_priority = 1; | |
| 189 pthread_setschedparam(pthread_self(), policy, ¶m); | |
| 190 } | |
| 191 | |
| 192 return NULL; | |
| 193 } | |
| 194 \end{verbatim} | |
| 195 \end{breakbox} | |
| 196 | |
| 197 (ソース説明) |