Mercurial > hg > Papers > 2016 > masa-master

comparison c3.tex @ 16:a3c5125aea03

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add images
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Wed, 20 Jan 2016 17:02:45 +0900
parents c686d33ba1c7
children 14545e517fb0
comparison
equal deleted inserted replaced
15:c686d33ba1c7 16:a3c5125aea03
1 \chapter{正規表現の設計と実装} 1 \chapter{並列処理向け I/O}
2 \section{正規表現構文木の生成} 2 ファイル読み込みなどの I/O を含むプログラムは、読み込み時間が Task の処理時間と比較してオーバーヘッドになることが多い。
3 \section{Transition List の生成} 3 計算処理の並列化を図ったとしても I/O がボトルネックになってしまい処理全体が高速にならない。
4 \section{Subset Construction} 4 本項では Cerium に実装した並列処理用 I/O を行ない、I/O 部分の高速化を図った。
5 \section{Cerium 上での実装} 5
6 Cerium の例題ではファイル読み込みを mmap にて実装していた。
7 しかし、mmap だとファイルを読み込んでから Task を実行するので、読み込んでいる間は他の CPU が動作せず並列度が落ちる。
8
9 mmap は function call 後にすぐにファイルを読みに行くのではなく、仮想メモリ領域にファイルの中身を対応させる。
10 その後メモリ空間にアクセスされたときに、OS が対応したファイルを読み込む。
11 また、読み込む方法が OS 依存となってしまうため環境に左右されやすく、プログラムの書き手が読み込みの制御をすることが難しい。
12
13 図\ref{fig:mmap}は mmap で読み込んだファイルに対して Task1 、 Task2 がアクセスしてそれぞれの処理を行うときのモデルである。
14
15 Task1 が実行されると仮想メモリ上に対応したファイルが読み込まれ、読み込み後 Task1 の処理が行われる。
16 その後 Task2 も Task1 と同様の処理が行われるが、これら 2 つの Task の間に待ちが入る。
6 17
7 \begin{figure}[htpb] 18 \begin{figure}[htpb]
8 \begin{center} 19 \begin{center}
9 \includegraphics[scale=0.2]{images/implementation/CharClassMergePattern.pdf} 20 \includegraphics[scale=0.7]{images/cerium/mmap.pdf}
10 \end{center} 21 \end{center}
11 \caption{2つの Character Class を merge するときの全パターン} 22 \caption{mmap Model}
12 \label{fig:CharClassMergePattern} 23 \label{fig:mmap}
13 \end{figure} 24 \end{figure}
25
26 mmap を使わず、読み込みを独立した Thread で行ない、ファイルを一度に全て読み込むのではなくある程度の大きさ(Block)分読み込み、読み込まれた部分に対して並列に Task を起動する。
27 これを Blocked Read と呼び、高速化を図った。
28
29 Blocked Read を実装するにあたり、WordCount を例題に挙げる。
30 ファイルを読み込む Task (以下、ReadTask) と、読み込んだファイルに対して計算を行う Task (以下、WordCount) を別々に生成する。ReadTask は一度にファイル全体を読み込むのではなく、ある程度の大きさで分割してから読み込みを行う。分割して読み込んだ範囲に対して WordCount を行う。
31
32 WordCount を Blocked Read で読み込み処理をしたとき以下の図\ref{fig:BlockedRead}の様になる。
14 33
15 \begin{figure}[htpb] 34 \begin{figure}[htpb]
16 \begin{center} 35 \begin{center}
17 \includegraphics[scale=0.2]{images/implementation/ccinsert1.pdf} 36 \includegraphics[scale=0.5]{./images/cerium/blockedread.pdf}
18 \end{center} 37 \end{center}
19 \caption{Character Class を二分木で表示} 38 \caption{BlockedRead による WordCount}
20 \label{fig:ccinsert1} 39 \label{fig:BlockedRead}
21 \end{figure} 40 \end{figure}
41
42 Task を一定の単位でまとめた Task Block ごとに生成して WordCount を行なっている。
43 Task Block で計算される領域が Blocked Read で読み込む領域を追い越して実行してしまうと、まだ読み込まれていない領域に対して計算されてしまう。
44 その問題を解決するために依存関係を適切に設定する必要がある。
45 Blocked Read による読み込みが終わってから TaskBlock が起動されるようにするため、Cerium の API である wait\_for にて依存関係を設定する。
46
47 また、ReadTask は連続で処理される必要がある。
48 なぜならば、ReadTask でファイルを読み込む前提で WordCount がその領域に対して計算を行うので、ReadTask の処理が遅くなってしまうだけでオーバーヘッドとなってしまう。\ref{fig:BlockedReadModel}
22 49
23 \begin{figure}[htpb] 50 \begin{figure}[htpb]
24 \begin{center} 51 \begin{center}
25 \includegraphics[scale=0.2]{images/implementation/ccinsert2.pdf} 52 \includegraphics[scale=0.5]{./images/cerium/blockedreadimage.pdf}
26 \end{center} 53 \end{center}
27 \caption{ある Character Class の二分木に対して、新しい Character Class を insert} 54 \caption{BlockedRead Model}
28 \label{fig:ccinsert2} 55 \label{fig:BlockedReadModel}
29 \end{figure} 56 \end{figure}
57
58 \newpage
59 Blocked Read を実装することにより、読み込み部分と処理部分の並列化を行なった。Blocked Read は連続で読み込まれる必要があるため、さらに I/O 専用 thread を実装した。
60
61 Cerium Task Manager では、それぞれの Task に対してデバイスを設定することができる。
62 SPE\_ANY 設定をすると、Task Manager が CPU の割り振りを自動的に行う。
63 Blocked Read は連続で読み込まれなければならないが、SPE\_ANY で設定すると Blocked Read 間に別の Task が割り込まれる恐れがある。(図\ref{fig:spe_any_blockedread})
30 64
31 \begin{figure}[htpb] 65 \begin{figure}[htpb]
32 \begin{center} 66 \begin{center}
33 \includegraphics[scale=0.2]{images/implementation/ccinsertresult.pdf} 67 \includegraphics[scale=0.7]{./images/cerium/speblockedread.pdf}
34 \end{center} 68 \end{center}
35 \caption{insert 後の Character Class の二分木} 69 \caption{BlockedRead と Task を同じ thread で動かした場合}
36 \label{fig:ccinsertresult} 70 \label{fig:spe_any_blockedread}
37 \end{figure} 71 \end{figure}
38 72
73 Task が Blocked Read 間に割り込まれないようにするため、I/O 専用 thread である iO\_0 の設定を追加した。
74
75 IO\_0 は SPE\_ANY とは別 thread の scheduler で動作するので、SPE\_ANY で動作している Task に割り込むことはない。
76 しかし、読み込みの終了を通知し、次の read を行う時に他の Task がスレッドレベルで割り込んでしまう事がある。
77 pthread\_getschedparam() で IO\_0 の priority の設定を行う必要がある(図:\ref{fig:iothread_blockedread})。
39 \begin{figure}[htpb] 78 \begin{figure}[htpb]
40 \begin{center} 79 \begin{center}
41 \includegraphics[scale=0.2]{images/implementation/cfab.pdf} 80 \includegraphics[scale=0.7]{./images/cerium/iothread.pdf}
42 \end{center} 81 \end{center}
43 \caption{cfab} 82 \caption{IO Thread による BlockedRead}
44 \label{fig:cfab} 83 \label{fig:iothread_blockedread}
45 \end{figure} 84 \end{figure}
46 85
47 \begin{figure}[htpb] 86 IO\_0 で実行される Task は Blocked Read のみで、さらに IO\_0 の priority を高く設定することにより Blocked Read が他の Task に割り込まれることなく連続に実行される。
48 \begin{center}
49 \includegraphics[scale=0.2]{images/implementation/cfdg.pdf}
50 \end{center}
51 \caption{cfdg}
52 \label{fig:cfdg}
53 \end{figure}
54
55 \begin{figure}[htpb]
56 \begin{center}
57 \includegraphics[scale=0.2]{images/implementation/cfdgab.pdf}
58 \end{center}
59 \caption{cfdgab}
60 \label{fig:cfdgab}
61 \end{figure}
62
63 \begin{figure}[htpb]
64 \begin{center}
65 \includegraphics[scale=0.2]{images/implementation/efgi.pdf}
66 \end{center}
67 \caption{efgi}
68 \label{fig:efgi}
69 \end{figure}
70
71 \begin{figure}[htpb]
72 \begin{center}
73 \includegraphics[scale=0.2]{images/implementation/dfa.pdf}
74 \end{center}
75 \caption{dfa}
76 \label{fig:dfa}
77 \end{figure}
78
79 \begin{figure}[htpb]
80 \begin{center}
81 \includegraphics[scale=0.2]{images/implementation/nfa.pdf}
82 \end{center}
83 \caption{nfa}
84 \label{fig:nfa}
85 \end{figure}
86