|
7
|
1 \chapter{並列処理向けI/O}
|
|
16
|
2 ファイル読み込みなどの I/O を含むプログラムは、読み込み時間が Task の処理時間と比較してオーバーヘッドになることが多い。
|
|
|
3 プログラムの並列化を行ったとしても、 I/O がボトルネックになってしまうと処理は高速にならない。
|
|
|
4 本項では Cerium に並列処理用の I/O の実装を行う。これにより I/O 部分の高速化を図る。
|
|
|
5
|
|
|
6 \section{mmap}
|
|
|
7 Cerium ではファイルの読み込みを mmap により実装していた。
|
|
|
8 しかし、mmap や read によりファイルを読み込んでから処理を実行させると、
|
|
|
9 読み込んでいる間は他の CPU が動作せず、並列度が落ちてしまう。
|
|
|
10 そこで、 I/O 部分も並列に動作するよう実装した。
|
|
|
11
|
|
|
12 Read を並列に行うには、File Open ではなく mmap を使う方法がある。
|
|
|
13 mmap はすぐにファイルを読みに行くのではなく、まず仮想メモリ空間にファイルの中身を対応させる。
|
|
|
14 メモリ空間にアクセスが行われると、OS が対応したファイルを読み込む。
|
|
|
15
|
|
|
16 mmap で読み込んだファイルに Task1、Task2 がアクセスし、それぞれの処理を行う際の例を図:\ref{fig:mmap}に示す。
|
|
|
17
|
|
|
18 \begin{figure}[htpb]
|
|
|
19 \begin{center}
|
|
|
20 \includegraphics[scale=0.7]{./images/mmap.pdf}
|
|
|
21 \end{center}
|
|
|
22 \caption{mmap の Model}
|
|
|
23 \label{fig:mmap}
|
|
|
24 \end{figure}
|
|
|
25
|
|
|
26 Task1 が実行される時、仮想メモリ上 Open されたファイルの読み込みを行い、Task1 の処理を行う。
|
|
|
27 その後、同様に Task2 も読み込みを行ってから処理を行う。この Task1 と Task2 の間に待ちが入る。
|
|
|
28
|
|
|
29 ファイルの読み込みが起こると、アクセスした Thread/Process には wait がかかってしまう。
|
|
|
30 しかし mmap による Read は Task と並列に実行されるべきである
|
|
|
31 mmap は逐次アクセスを仮定しているので、OS 内部で自動的にファイルの先読みを行う事も期待できる。
|
|
|
32 しかしそれは OS の実装に依存してしまう。
|
|
|
33 読み込みが並列に実行されない場合、 Task が読み込み待ちを起こしてしまう。
|
|
|
34 読み込みが OS 依存となるため、環境によって左右されやすく、汎用性を損なってしまう。
|
|
|
35
|
|
|
36 そこで、mmap を使わず、read を独立したスレッドで行い、読み込まれた部分に倒して並列に Task を起動する。
|
|
|
37 これを Blocked Read と呼ぶ。Blocked Read によるプログラミングは複雑になるが、高速化が期待できる。
|
|
|
38
|
|
|
39 \section{Blocked Read による I/O の並列化}
|
|
|
40 Blocked Read を実装するに辺り、WordCount を例に考える。
|
|
|
41 Blocked Read はファイル読み込み用の Task(以下、ReadTask) と
|
|
|
42 読み込んだファイルに対して処理を行う Task(今回はWordCount) を別々に生成する。
|
|
|
43 ReadTask はファイル全体を一度に全て読み込むのではなく、ある程度の大きさで分割してから読み込みを行う。
|
|
|
44 分割後の読み込みが終わると、読み込んだ範囲に対して WordCount を行う。
|
|
|
45
|
|
|
46 BlockedRead による WordCount を行う場合、図:\ref{fig:blockedread}のようになる。
|
|
|
47
|
|
|
48 \begin{figure}[htpb]
|
|
|
49 \begin{center}
|
|
|
50 \includegraphics[scale=0.5]{./images/blockedread.pdf}
|
|
|
51 \end{center}
|
|
|
52 \caption{BlockedRead による WordCount}
|
|
|
53 \label{fig:blockedread}
|
|
|
54 \end{figure}
|
|
|
55
|
|
|
56 Task を一定数まとめた単位で生成し、起動を行っている。この単位を Task Block と定義する。
|
|
|
57 TaskBlock が BlockedRead を追い越して実行してしまうと、まだ読み込まれてない領域に対して処理を行ってしまう。
|
|
|
58 その問題を解決するため、依存関係を設定する。
|
|
|
59 BlockedReadによる読み込みが終わってから TaskBlock が起動されるよう、
|
|
|
60 Cerium の API である wait\_for により依存関係を設定する。
|
|
|
61
|
|
|
62 以上を踏まえ、BlockedRead の実装を行った。
|
|
|
63 BlockedRead Task の生成はソースコード:\ref{src:blockedread_create}のように行う。
|
|
|
64
|
|
|
65 \begin{lstlisting}[frame=lrbt,label=src:blockedread_create,caption=BlockedRead を行う Task の生成,numbers=left]
|
|
|
66 HTaskPtr readTask = manager->create_task(READ_TASK)
|
|
|
67 readTask->set_cpu(DEVICE_TYPE);
|
|
|
68 readTask->set_outData(0, file_map + task_num * division_size, task_blocks * division_size);
|
|
|
69 readTask->set_param(0, fd);
|
|
|
70 readTask->set_param(1, task_num * division_size);
|
|
|
71 runTask();
|
|
|
72 readTask->set_param(2, task_num * division_size)
|
|
|
73 readTask->spawn();
|
|
|
74 \end{lstlisting}
|
|
|
75
|
|
|
76 \begin{itemize}
|
|
|
77 \item 3行目、set\_outData(0): ファイルを読み込んだ際の格納場所を設定
|
|
|
78 \item 4行目、set\_param(0): 読み込むファイルディスクリプタを設定
|
|
|
79 \item 5行目、set\_param(1): BlockedRead Task で読み込むファイルの範囲の先頭のポジションを設定
|
|
|
80 \item 7行目、set\_param(2): BlockedRead Task で読み込むファイルの範囲の末尾のポジションを設定
|
|
|
81 \end{itemize}
|
|
|
82
|
|
|
83 Cerium において、 WordCount で必要な Task を全て生成してしまうと、
|
|
|
84 その Task のデータ構造自体がメモリを消費してしまう。
|
|
|
85 そこである程度の量の Task を起動し、それが終了してから(正確には終了する前に)次の Task を生成するようになっている。
|
|
|
86 それらの機能を持った関数が6行目にあたる run\_tasks である。
|
|
|
87 run\_tasks に wait\_for による ReadTask との待ち合わせの処理を入れれば良い。
|
|
|
88
|
|
|
89 BlockedRead の Task をいかに示す。
|
|
|
90
|
|
|
91 \begin{lstlisting}[frame=lrbt,label=src:blockedread_task,caption=BlockedRead Task,numbers=left]
|
|
|
92 static int
|
|
|
93 read_task(SchedTask *s, void *rbuf, void *wbuf) {
|
|
|
94 long fd = (long)s->get_param(0);
|
|
|
95 long start = (long)s->get_param(1);
|
|
|
96 long end = (long)s->get_param(2);
|
|
|
97 char txt = (char*)s->get_output(wbuf, 0);
|
|
|
98 long size = end - start;
|
|
|
99
|
|
|
100 pread(fd, txt, size, start);
|
|
|
101 return 0;
|
|
|
102 }
|
|
|
103 \end{lstlisting}
|
|
|
104
|
|
|
105 Cerium の API により、生成部分で設定したパラメタをそれぞれ受け取る。
|
|
|
106 ファイル読み込みの先頭・末尾のポジションが渡されているので、ファイルから読み込むサイズは求められる。
|
|
|
107 受け取ったパラメタをそれぞれ pread 関数に渡すことで Blocked Read を実現している。
|
|
|
108 \newpage
|
|
|
109 \section{I/O 専用 Thread の実装}
|
|
|
110 Cerium Task Manager では、各種 Task にデバイスを設定することができる。
|
|
|
111 SPE\_ANY 設定を使用すると、 Task Manager で CPU の割り振りを自動的に行う。
|
|
|
112 BlockedRead は連続で読み込まれなければならないが、
|
|
|
113 SPE\_ANY 設定で実行すると BlockedRead 間に別の Task を割り込んでしまう場合がある。
|
|
|
114 (図:\ref{fig:spe_any_blockedread})
|
|
|
115
|
|
|
116 \begin{figure}[htpb]
|
|
|
117 \begin{center}
|
|
|
118 \includegraphics[scale=0.7]{./images/speblockedread.pdf}
|
|
|
119 \end{center}
|
|
|
120 \caption{BlockedRead と Task を同じ thread で動かした場合}
|
|
|
121 \label{fig:spe_any_blockedread}
|
|
|
122 \end{figure}
|
|
|
123
|
|
|
124 そこで I/O 専用の Thread である IO\_0 の追加を行った。
|
|
|
125
|
|
|
126 IO\_0 は SPE\_ANY とは別 Thread の Scheduler で動くので、SPE\_ANY で動いている Task に割り込まれることはない。
|
|
|
127 しかし、読み込みの終了を通知し、次の read を行う時に他の Task がスレッドレベルで割り込んでしまう事がある。
|
|
|
128 pthread\_getschedparam() で IO\_0 の priority の設定を行う必要がある(図:\ref{fig:iothread_blockedread})。
|
|
|
129
|
|
|
130 \begin{figure}[htpb]
|
|
|
131 \begin{center}
|
|
|
132 \includegraphics[scale=0.7]{./images/iothread.pdf}
|
|
|
133 \end{center}
|
|
|
134 \caption{IO Thread による BlockedRead}
|
|
|
135 \label{fig:iothread__blockedread}
|
|
|
136 \end{figure}
|
|
|
137 IO\_0 で実行される Task は BlockedRead のみなので、
|
|
|
138 IO\_0 のpriority を高く設定することで Blocked Read は連続で実行される。
|
|
|
139
|
|
|
140 また、以上の事から I/O を含む処理では、 I/O を行う Thread の priority を高くする必要があるという知見を得られた。
|
