Mercurial > hg > Papers > 2014 > masakoha-thesis > final

annotate paper/chapter4.tex @ 52:1ae8a15f3e94

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
suspended blocked read
author Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
date Fri, 21 Feb 2014 19:04:12 +0900
parents 06f75bca7a70
children d6f83dd6301f
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
9bf2694ed231 add some files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 \label{chap:poordirection}
9bf2694ed231 add some files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3
47
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
4 \section{map reduce}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
5
50
22740fb4d522 write mmap
masa
parents: 49
diff changeset
6 \begin{figure}[htbp]
22740fb4d522 write mmap
masa
parents: 49
diff changeset
7 \begin{center}
22740fb4d522 write mmap
masa
parents: 49
diff changeset
8 \includegraphics[width=1.0\textwidth]{fig/mapreduce.pdf}
22740fb4d522 write mmap
masa
parents: 49
diff changeset
9 \end{center}
22740fb4d522 write mmap
masa
parents: 49
diff changeset
10 \caption{map reduce image}
22740fb4d522 write mmap
masa
parents: 49
diff changeset
11 \label{fig:mmap} \end{figure}
22740fb4d522 write mmap
masa
parents: 49
diff changeset
12
47
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
13 \section{mmap での実装の問題点}
50
22740fb4d522 write mmap
masa
parents: 49
diff changeset
14 mmap とは、sys/mman.h に含まれている関数で、ファイルの読み込み等に使用される関数である。
22740fb4d522 write mmap
masa
parents: 49
diff changeset
15 ファイルディスクリプタで指定したファイルを offset から len バイトの範囲を読み込む。
22740fb4d522 write mmap
masa
parents: 49
diff changeset
16 この時にアドレス addr からメモリを確保するようにする。
22740fb4d522 write mmap
masa
parents: 49
diff changeset
17 prot には、PROT\_READによるページの読み込み、PROT\_WRITEによるページへの書き込みなどを指定でき、
52
1ae8a15f3e94 suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 51
diff changeset
18 flags にはメモリ確保する際のオプションを指定することができる。(表\ref{table:mmap})
50
22740fb4d522 write mmap
masa
parents: 49
diff changeset
19
22740fb4d522 write mmap
masa
parents: 49
diff changeset
20 \begin{tiny}
22740fb4d522 write mmap
masa
parents: 49
diff changeset
21 \begin{table}[ht]
22740fb4d522 write mmap
masa
parents: 49
diff changeset
22 \begin{center}
22740fb4d522 write mmap
masa
parents: 49
diff changeset
23 \label{table:mmap}
22740fb4d522 write mmap
masa
parents: 49
diff changeset
24 \small
22740fb4d522 write mmap
masa
parents: 49
diff changeset
25 void * mmap(void *addr, size\_t len, int prot, int flags, int fd, off\_t offset);
0
9bf2694ed231 add some files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26
50
22740fb4d522 write mmap
masa
parents: 49
diff changeset
27 \begin{tabular}[t]{c|l}
22740fb4d522 write mmap
masa
parents: 49
diff changeset
28 \hline
22740fb4d522 write mmap
masa
parents: 49
diff changeset
29 void *addr & メモリに確保するときの先頭のアドレス\\
22740fb4d522 write mmap
masa
parents: 49
diff changeset
30 \hline
22740fb4d522 write mmap
masa
parents: 49
diff changeset
31 size\_t len & メモリを確保するサイズ\\
22740fb4d522 write mmap
masa
parents: 49
diff changeset
32 \hline
22740fb4d522 write mmap
masa
parents: 49
diff changeset
33 int prot & ファイルモード選択\\
22740fb4d522 write mmap
masa
parents: 49
diff changeset
34 \hline
22740fb4d522 write mmap
masa
parents: 49
diff changeset
35 int flags & 確保するときのオプション指定\\
22740fb4d522 write mmap
masa
parents: 49
diff changeset
36 \hline
22740fb4d522 write mmap
masa
parents: 49
diff changeset
37 int fd & 読み込むファイルのファイルディスクリプタ\\
22740fb4d522 write mmap
masa
parents: 49
diff changeset
38 \hline
22740fb4d522 write mmap
masa
parents: 49
diff changeset
39 off\_t offset & ファイル読み込みの先頭からの開始位置 \\
22740fb4d522 write mmap
masa
parents: 49
diff changeset
40 \hline
22740fb4d522 write mmap
masa
parents: 49
diff changeset
41 \end{tabular}
22740fb4d522 write mmap
masa
parents: 49
diff changeset
42 \caption{mmap 関数の概要}
22740fb4d522 write mmap
masa
parents: 49
diff changeset
43 \end{center}
22740fb4d522 write mmap
masa
parents: 49
diff changeset
44 \end{table}
22740fb4d522 write mmap
masa
parents: 49
diff changeset
45 \end{tiny}
37
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
46
50
22740fb4d522 write mmap
masa
parents: 49
diff changeset
47 mmap でファイルを読み込むタイミングは、mmap 関数が呼ばれたときではなく、mmap した領域に対して何らかのアクセスをしたときに初めてファイルが読み込まれる。
22740fb4d522 write mmap
masa
parents: 49
diff changeset
48
22740fb4d522 write mmap
masa
parents: 49
diff changeset
49 図\ref{fig:mmap}では、読み込んだファイルを分割して、それらの領域に何らかの処理を加えるときの図である。これらの処理を Task と呼ぶ。
22740fb4d522 write mmap
masa
parents: 49
diff changeset
50 Task 1 という1個目の Task が実行される。実行されたときに初めてそれらの領域にファイルが読み込まれ、その後何らかの処理が行われ、そして Task 2 も同様に読み込みを行ってから処理が行われる。
22740fb4d522 write mmap
masa
parents: 49
diff changeset
51 これら Task は並列に実行されるべきであるが、ファイル読み込みの I/O 部分がネックとなり、本来並列実行される Task が読み込み待ちを起こしてしまう恐れがある。
22740fb4d522 write mmap
masa
parents: 49
diff changeset
52 その上、読み込み方法が OS 依存となるために環境によって左右されやすく、プログラムの書き手が読み込みに関して制御しにくい。
22740fb4d522 write mmap
masa
parents: 49
diff changeset
53
22740fb4d522 write mmap
masa
parents: 49
diff changeset
54 それらを解決するためには、ファイル読み込みと Task を分離し、ファイルの読み込みも制御しやすくでき、なおかつ高速で動くのではないかと考えた。
49
masa
parents: 47
diff changeset
55
masa
parents: 47
diff changeset
56 \begin{figure}[htbp]
masa
parents: 47
diff changeset
57 \begin{center}
masa
parents: 47
diff changeset
58 \includegraphics[width=1.0\textwidth]{fig/mmap.pdf}
masa
parents: 47
diff changeset
59 \end{center}
masa
parents: 47
diff changeset
60 \caption{mmap のイメージ}
masa
parents: 47
diff changeset
61 \label{fig:mmap} \end{figure}
masa
parents: 47
diff changeset
62
51
06f75bca7a70 suspend blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
63 \section{Bloked Read の設計と実装}
52
1ae8a15f3e94 suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 51
diff changeset
64 Blocked Read とは、読み込みの Task と、それに対する何らかの処理の Task を切り離すための実装方法で、pread 関数で実装した。
1ae8a15f3e94 suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 51
diff changeset
65 mmap での実装との違いは、ファイルの読み込みがどのタイミングで起こるかである。
1ae8a15f3e94 suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 51
diff changeset
66 mmap で実装したときは、Task 1つ 1つが読み込みを行ってから処理を行う。
1ae8a15f3e94 suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 51
diff changeset
67 それに対して、Blocked Readは、読み込み専用の Read Task と、処理専用の Task を別々に生成する。
1ae8a15f3e94 suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 51
diff changeset
68 Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行う。
1ae8a15f3e94 suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 51
diff changeset
69 分割して読み込み終わったら、それぞれの Task が実行される。
1ae8a15f3e94 suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 51
diff changeset
70 (図\ref{fig:block})
1ae8a15f3e94 suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 51
diff changeset
71 Read Task は常に実行されている必要があり、
1ae8a15f3e94 suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 51
diff changeset
72
1ae8a15f3e94 suspended blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 51
diff changeset
73
37
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
74
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
75 ・ TaskManager で allocate して、Task として呼び出した pread で allocate 部分に格納している
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
76
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
77 ・ pread で実装したものを、Task と IO が並列に動くようにしないといけない
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
78
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
79 ・ pread は常に走っていているのが理想
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
80
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
81
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
82
42
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
83 \begin{figure}[htbp]
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
84 \begin{center}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
85 \includegraphics[width=1.0\textwidth]{fig/blockedreadimage.pdf}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
86 \end{center}
51
06f75bca7a70 suspend blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
87 \caption{Blocked Read image}
06f75bca7a70 suspend blocked read
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
88 \label{fig:block}
42
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
89 \end{figure}
37
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
90
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
91 ・ これで IO と Task が同時にはしるようになった
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
92
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
93 ・ 実験結果??
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
94
42
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
95 ・ Task は実際には 1個1個生成しているのではなく
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
96
37
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
97 ・ Cerium の Task に CPU Type を設定することができる。しかし、同じCPU Type を使用すると、IO を担当している CPU に Task が割り振られて、read 全体の速度が遅くなってしまう。
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
98
42
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
99
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
100 図\ref{fig:speany}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
101
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
102 \begin{figure}[htbp]
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
103 \begin{center}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
104 \includegraphics[width=1.0\textwidth]{fig/speany.pdf}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
105 \end{center}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
106 \caption{[image]priority を上げる前の image 図}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
107 \label{fig:speany}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
108 \end{figure}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
109
37
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
110
47
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
111 \section{I/O 専用 thread の実装}
37
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
112 ・ Cerium では ptherad で並列処理を記述している
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
113
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
114 ・ SPY\_ANY という CPU Type は、Cerium 側が自動的に CPU 割り当てを行う便利なマクロ
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
115
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
116 ・ SPE\_ANY を使用すると、IO の部分にも割り込まれてしまうので、これをどうにかしたい。
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
117
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
118 ・ IO\_0 という新しい CPU Type を追加
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
119
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
120 ・ pthread の API で CPU の priority をあげることができる。
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
121
42
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
122
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
123 図\ref{fig:io0}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
124
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
125 \begin{figure}[htbp]
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
126 \begin{center}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
127 \includegraphics[width=1.0\textwidth]{fig/io0.pdf}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
128 \end{center}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
129 \caption{[image]priority を上げたときの image 図}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
130 \label{fig:io0}
6bb9cae3f7e4 add images
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 37
diff changeset
131 \end{figure}
37
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
132
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
133 ・ これで IO 部分に割り込みがおこらないよね!!