Mercurial > hg > Papers > 2016 > masa-master

annotate c3.tex @ 42:8576011b8447

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