Mercurial > hg > Papers > 2016 > masa-master
annotate c3.tex @ 24:beadec12c1e7
write bm_search
| author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 05 Feb 2016 17:07:52 +0900 |
| parents | 1803c5766d06 |
| children | 7a74aa1fe42f |
| rev | line source |
|---|---|
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
1 \chapter{並列処理向け I/O} |
| 23 | 2 ファイル読み込みなどの I/O を含むプログラムは、読み込み時間が Task の処理時間と比較して大きくなることが多い。 |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
3 計算処理の並列化を図ったとしても I/O がボトルネックになってしまい処理全体が高速にならない。 |
| 23 | 4 従来の例題のファイル読み込み部分では mmap を利用していたが、読み込みと Task が並列に動くような実装を行ない、プログラム全体の高速化を図った。 |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
5 |
| 23 | 6 本項では mmap による読み込みと、今回実装した並列処理向け I/O について述べる。 |
| 7 | |
| 8 \section{mmap} | |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
9 Cerium の例題ではファイル読み込みを mmap にて実装していた。 |
| 23 | 10 |
| 11 mmap は function call 後にすぐにファイルを読みに行くのではなく、仮想メモリ領域にファイルの中身を対応させ、 その後メモリ空間にアクセスされたときに、OS が対応したファイルを読み込む。 | |
| 10 | 12 |
| 23 | 13 そのため、mmap によるファイルを読み込みは読み込み後に Task を実行するので、その間は他の CPU が動作せず並列度が落ちる。 |
| 14 | |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
15 また、読み込む方法が OS 依存となってしまうため環境に左右されやすく、プログラムの書き手が読み込みの制御をすることが難しい。 |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
16 |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
17 図\ref{fig:mmap}は mmap で読み込んだファイルに対して Task1 、 Task2 がアクセスしてそれぞれの処理を行うときのモデルである。 |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
18 |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
19 Task1 が実行されると仮想メモリ上に対応したファイルが読み込まれ、読み込み後 Task1 の処理が行われる。 |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
20 その後 Task2 も Task1 と同様の処理が行われるが、これら 2 つの Task の間に待ちが入る。 |
| 10 | 21 |
| 22 \begin{figure}[htpb] | |
| 23 \begin{center} | |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
24 \includegraphics[scale=0.7]{images/cerium/mmap.pdf} |
| 10 | 25 \end{center} |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
26 \caption{mmap Model} |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
27 \label{fig:mmap} |
| 10 | 28 \end{figure} |
| 29 | |
| 23 | 30 \section{Blocked Read} |
| 31 読み込みを独立した Thread で行ない、ファイルを一度に全て読み込むのではなくある程度の大きさ(Block)分読み込み、読み込まれた部分に対して並列に Task を起動する。 | |
| 32 これを Blocked Read と呼び、I/O の読み込みと Task の並列化を図った。 | |
| 10 | 33 |
| 23 | 34 ファイルを読み込む Task (以下、Blocked Read) と、読み込んだファイルに対して計算を行う Task を別々に生成する。 |
| 35 Blocked Read は一度にファイル全体を読み込むのではなく、ある程度の大きさで分割してから読み込みを行う。 | |
| 36 分割して読み込んだ範囲に対して Task を実行する。 | |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
37 |
| 23 | 38 ファイル読み込みを含むプログラムを Blocked Read で読み込み処理をしたとき以下の図\ref{fig:BlockedRead}の様になる。 |
| 10 | 39 |
| 40 \begin{figure}[htpb] | |
| 41 \begin{center} | |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
42 \includegraphics[scale=0.5]{./images/cerium/blockedread.pdf} |
| 10 | 43 \end{center} |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
44 \caption{BlockedRead による WordCount} |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
45 \label{fig:BlockedRead} |
| 10 | 46 \end{figure} |
| 47 | |
| 23 | 48 Task を一定の単位でまとめた Task Block ごとに生成して Task を行なっている。 |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
49 Task Block で計算される領域が Blocked Read で読み込む領域を追い越して実行してしまうと、まだ読み込まれていない領域に対して計算されてしまう。 |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
50 その問題を解決するために依存関係を適切に設定する必要がある。 |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
51 Blocked Read による読み込みが終わってから TaskBlock が起動されるようにするため、Cerium の API である wait\_for にて依存関係を設定する。 |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
52 |
| 23 | 53 (図\ref{fig:BlockedReadModel}) |
| 10 | 54 |
| 55 \begin{figure}[htpb] | |
| 56 \begin{center} | |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
57 \includegraphics[scale=0.5]{./images/cerium/blockedreadimage.pdf} |
| 10 | 58 \end{center} |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
59 \caption{BlockedRead Model} |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
60 \label{fig:BlockedReadModel} |
| 10 | 61 \end{figure} |
| 62 | |
| 23 | 63 \section{I/O 専用 thread の追加} |
| 64 | |
| 65 Blocked Read は読み込みを含む処理なので、Task 1 つあたりの処理時間が大きくなる。 | |
| 66 Blocked Read がファイルを読み込む前提で Task がその領域に対して計算を行うので、ReadTask の処理によってプログラム全体の処理速度が左右されてしまう。 | |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
67 |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
68 Cerium Task Manager では、それぞれの Task に対してデバイスを設定することができる。 |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
69 SPE\_ANY 設定をすると、Task Manager が CPU の割り振りを自動的に行う。 |
| 23 | 70 しかし、自動的に割り振りを行なってしまうと、Blocked Read Task 間に Task が割り込まれてしまい、読み込みが遅延してしまう可能性がある。 |
| 71 (図\ref{fig:spe_any_blockedread}) | |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
72 |
| 10 | 73 \begin{figure}[htpb] |
| 74 \begin{center} | |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
75 \includegraphics[scale=0.7]{./images/cerium/speblockedread.pdf} |
| 10 | 76 \end{center} |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
77 \caption{BlockedRead と Task を同じ thread で動かした場合} |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
78 \label{fig:spe_any_blockedread} |
| 10 | 79 \end{figure} |
| 80 | |
| 23 | 81 そこで、Task が Blocked Read Task 間に割り込まれないようにするため、I/O 専用 thread である iO\_0 の設定を追加した。 |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
82 |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
83 IO\_0 は SPE\_ANY とは別 thread の scheduler で動作するので、SPE\_ANY で動作している Task に割り込むことはない。 |
| 23 | 84 しかし、読み込みの終了を通知し、次の read を行う時に他の Task がスレッドレベルで割り込んでしまう事があるため、 |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
85 pthread\_getschedparam() で IO\_0 の priority の設定を行う必要がある(図:\ref{fig:iothread_blockedread})。 |
| 23 | 86 |
| 10 | 87 \begin{figure}[htpb] |
| 88 \begin{center} | |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
89 \includegraphics[scale=0.7]{./images/cerium/iothread.pdf} |
| 10 | 90 \end{center} |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
91 \caption{IO Thread による BlockedRead} |
|
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
92 \label{fig:iothread_blockedread} |
| 10 | 93 \end{figure} |