Mercurial > hg > Papers > 2017 > ikkun-sigos
comparison sigos.tex~ @ 0:38b037c42c34
first commit
author | ikkun |
---|---|
date | Mon, 17 Apr 2017 20:05:26 +0900 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:38b037c42c34 |
---|---|
1 \documentclass[techrep]{ipsjpapers} | |
2 \usepackage[dvipdfmx]{graphicx} | |
3 \usepackage{url} | |
4 \usepackage{listings,jlisting} | |
5 \usepackage{enumitem} | |
6 | |
7 \lstset{ | |
8 language=C, | |
9 tabsize=2, | |
10 frame=single, | |
11 basicstyle={\ttfamily\footnotesize},% | |
12 identifierstyle={\footnotesize},% | |
13 commentstyle={\footnotesize\itshape},% | |
14 keywordstyle={\footnotesize\bfseries},% | |
15 ndkeywordstyle={\footnotesize},% | |
16 stringstyle={\footnotesize\ttfamily}, | |
17 breaklines=true, | |
18 captionpos=b, | |
19 columns=[l]{fullflexible},% | |
20 xrightmargin=0zw,% | |
21 xleftmargin=1zw,% | |
22 aboveskip=1zw, | |
23 numberstyle={\scriptsize},% | |
24 stepnumber=1, | |
25 numbersep=0.5zw,% | |
26 lineskip=-0.5ex, | |
27 } | |
28 \renewcommand{\lstlistingname}{Code} | |
29 | |
30 \input{dummy.tex} %% Font | |
31 | |
32 % ユーザが定義したマクロなど. | |
33 \makeatletter | |
34 | |
35 \begin{document} | |
36 | |
37 % 和文表題 | |
38 \title{Code Gear、 Data Gear に基づく OS のプロトタイプ} | |
39 % 英文表題 | |
40 \etitle{} | |
41 | |
42 % 所属ラベルの定義 | |
43 \affilabel{1}{琉球大学大学院理工学研究科情報工学専攻 \\Interdisciplinary Information Engineering, Graduate School of Engineering and Science, University of the Ryukyus.} | |
44 \affilabel{2}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.} | |
45 | |
46 % 和文著者名 | |
47 \author{ | |
48 伊波 立樹\affiref{1} | |
49 \and | |
50 東恩納 琢偉 \affiref{2} | |
51 \and | |
52 河野 真治\affiref{2} | |
53 } | |
54 | |
55 % 英文著者名 | |
56 \eauthor{ | |
57 Tatsuki IHA\affiref{1} | |
58 \and | |
59 Takui HIGASHIONNA\affiref{2} | |
60 \and | |
61 Shinji KONO\affiref{2} | |
62 } | |
63 | |
64 % 連絡先(投稿時に必要.製版用では無視される.) | |
65 \contact{伊波 立樹\\ | |
66 〒903-0213 沖縄県西原町千原1番地\\ | |
67 琉球大学工学部情報工学科\\ | |
68 TEL: (098)895-2221\qquad FAX: (098)895-8727\\ | |
69 email: innparusu@cr.ie.u-ryukyu.ac.jp} | |
70 | |
71 % 和文概要 | |
72 \begin{abstract} | |
73 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて並列実行を行う Gears OS を開発している | |
74 Gears OS では 並列実行をするための Task を Code Gear と Data Gear の組で表現する。 | |
75 Task の依存関係は Code Gear を実行するために必要なInput Data Gear と Code Gearで作られる Output Data Gear によって決定し、それにそって並列実行を行う。 | |
76 依存関係の解決などの Meta Computation の実行は Meta Code Gear で行われる。 | |
77 Meta Code Gear は Code Gear に対応しており、 Code Gear が実行した後にそれに対応した Meta Code Gear が実行される。 | |
78 本論文ではGears OS のプロトタイプとして並列処理機構を設計し、 CbC(Continuation based C) で実装する。 | |
79 \end{abstract} | |
80 | |
81 % 英文概要 | |
82 \begin{eabstract} | |
83 \end{eabstract} | |
84 | |
85 % 表題などの出力 | |
86 \maketitle | |
87 | |
88 % 本文はここから始まる | |
89 | |
90 % Introduce | |
91 \section{Gears OS} | |
92 CPU の処理速度の向上のためクロック周波数の増加は発熱や消費電力の増大により難しくなっている。 | |
93 そのため、クロック周波数を上げる代わりに CPU のコア数を増やす傾向にある。 | |
94 マルチコア CPU の性能を発揮するには、処理をできるだけ並列化しなければならない。 | |
95 また、PC の処理性能を上げるためにマルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサが登場している。 | |
96 並列処理をする上でこれらのリソースを無視することができない。 | |
97 しかし、これらのプロセッサで性能を出すためにはこれらのアーキテクチャに合わせた並列プログラミングが必要になる。 | |
98 並列プログラミングフレームワークではこれらのプロセッサを抽象化し、CPU と同等に扱えるようにすることも求められる。 | |
99 本研究では Cerium を開発して得られた知見を元にこれらの性質を持つ並列プログラミングフレームワークとして Gears OS の設計・実装を行う。 | |
100 | |
101 Cerium\cite{cerium} は本研究室で開発していた並列プログラミングフレームワークである。 | |
102 Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする。 | |
103 Cerium では依存関係を Task 間で設定するが、本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することができない。 | |
104 また、Task には汎用ポインタとしてデータの受け渡しを行うため、型情報がない。 | |
105 そのため、汎用ポインタをキャストして利用するしか無く、型の検査を行う事ができない。 | |
106 | |
107 Gears OS\cite{gears} は Code Gear と Data Gear によって構成される。 | |
108 Code Gear は処理の単位、Data Gear はデータの単位となる。 | |
109 Gears OS では Code/Data Gear を用いて記述することでプログラム全体の並列度を高めて、効率的に並列処理することが可能になることを目的とする。 | |
110 また、Gears OS の実装自体が Code/Data Gear を用いたプログラミングの指針となるように実装する。 | |
111 Gears OS における Task は実行する Code Gear と実行に必要な Input Data Gear, 出力される Output Data Gear の組で表現される。 | |
112 Input/Output Data Gear によって依存関係が決定し、それに沿って並列実行する。 | |
113 依存関係の解決などの Meta Computation の実行は Meta Code Gear で行われる。 | |
114 Meta Code Gear は Code Gear に対応しており、 Code Gear が実行した後にそれに対応した Meta Code Gear が実行される。 | |
115 本論文ではGears OS のプロトタイプとして Data Gear を管理する Persistent Data Tree, Task を管理する TaskQueue, 並列処理を行う Worker を実装し、簡単な例題を用いて Gears OS の評価を行う。 | |
116 | |
117 \section{Code Gear と Data Gear} | |
118 Gears OS はプログラムの単位として Gear を用いる。 | |
119 Gear は並列実行の単位、データの分割、Gear 間の接続等になる。 | |
120 | |
121 Code Gear はプログラムの処理そのものである。 | |
122 Code Gear は任意の数の Input Data Gear を参照し、 処理が完了すると任意の数の Output Data Gear に書き込む。 | |
123 Code Gear は接続された Data Gear 以外には参照を行わない。 | |
124 | |
125 Data Gear は Data そのものを表しており、int や文字列などの Primitive Data Type が入っている。 | |
126 | |
127 Code Gear、 Data Gear は 本研究室で開発されている Alice\cite{alice} で使われている単位である Code Segment、 Data Segment\cite{segment} にそれぞれ対応する。 | |
128 | |
129 Gears OS では Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を可能とする。 | |
130 | |
131 Gear の特徴として処理やデータの構造が Code Gear、 Data Gear に閉じていることにある。 | |
132 これにより、実行時間、メモリ使用量などを予想可能なものにする事が可能になる。 | |
133 | |
134 \section{Meta Computation} | |
135 Gears OS では通常の処理を Computation、 Computation のための Computation を Meta Computation として扱う。 | |
136 Meta Computation の例として並列処理の依存関係の解決や、 OS が行うネットワーク管理、メモリ管理等の資源制御などが挙げられる。 | |
137 | |
138 Gears OS では Meta Computation を Meta Code Gear、 Meta Data Gear で表現する。 | |
139 Meta Code Gear は通常の Code Gear 直後に遷移され、 Meta Computation を実行する。 | |
140 Meta Computation の実行後は通常の Code Gear で指定した Code Gear を実行する。 | |
141 つまり Code Gear の実行後は何かしらの Meta Code Gear を実行する。 | |
142 | |
143 \section{Continuation based C} | |
144 Gears OS の実装は本研究室で開発している CbC(Continuation based C)\cite{cbc-lola}を用いて行う。 | |
145 CbC は処理を Code Segment を用いて記述することを基本としているため、 Gears OS の Code Gear を記述するのに適している。 | |
146 | |
147 CbC のプログラムでは C の関数の代わりに Code Segment を用いてい処理を記述している。 Code Segment は C の関数と異なり戻り値を持たない。 | |
148 Code Segment の宣言は C の関数の構文と同様に行い、 型に \_\_code を使うことで宣言できる。 | |
149 | |
150 Code Segment から Code Segment への移動は goto の後に Code Segment 名と引数を並べた記述するという構文を用いて行う。 | |
151 この goto による処理の遷移を継続と呼ぶ。 図\ref{fig:cbc_goto} は Code Segment 間の継続関係を表している。 | |
152 | |
153 C では関数呼び出しを行うたび、関数の引数の値がスタックに積まれていくが、Code Segment では戻り値を持たないため、スタックに値を積んでいく必要がなくスタックを変更する必要が無い。 | |
154 このようなスタックに値を積まない継続、つまり呼び出し元の環境を持たない継続を軽量継続と呼ぶ。 | |
155 軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようにする。 | |
156 | |
157 \begin{figure}[ht] | |
158 \begin{center} | |
159 \includegraphics[width=70mm]{./pic/cbc_goto.pdf} | |
160 \end{center} | |
161 \caption{gotoによる Code Segment 間の接続} | |
162 \label{fig:cbc_goto} | |
163 \end{figure} | |
164 | |
165 \section{CbC での Gears OS の構文サポート} | |
166 CbC は Gears OS の構文のサポートを行う。 | |
167 | |
168 Gesrs OS では Contextという接続可能な Data Gear のリストからデータを取り出して処理行う。 | |
169 しかし、 Context を直接扱うのはセキュリティ上好ましくない。 | |
170 そこで Gears OS では Context から必要なデータを取り出して Code Gear に接続する stub を定義する。 | |
171 stub は Code Gear から推論することが可能のため、 CbC は自動的に stub の生成を行う。 | |
172 | |
173 また、Code Gear の遷移には Meta computation を行うために Meta Code Gear を挟む。 | |
174 CbC では Meta Code Gear への接続も自動的に行うようにする。 | |
175 | |
176 \section{Gears OS の構成} | |
177 Gears OS は以下の要素で構成される。 | |
178 | |
179 \begin{itemize} | |
180 \item Context | |
181 \item TaskQueue | |
182 \item TaskManager | |
183 \item Persistent Data Tree | |
184 \item Worker | |
185 \end{itemize} | |
186 | |
187 図\ref{fig:gearsos} に Gears OS の構成図を示す。 | |
188 | |
189 \begin{figure}[ht] | |
190 \begin{center} | |
191 \includegraphics[width=70mm]{./pic/gearsos.pdf} | |
192 \end{center} | |
193 \caption{Gears OS の構成図} | |
194 \label{fig:gearsos} | |
195 \end{figure} | |
196 | |
197 \section{Context} | |
198 Context は接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、 Persistent Data Tree へのポインタ、 Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear である。 | |
199 Gears OS では必要な Code/Data Gear に参照したい場合、このContext を通す必要がある。 | |
200 | |
201 メインとなる Context と Worker 用 Context があり、 TaskQueue と Persistent Data Tree は共有される。 | |
202 Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはない。 | |
203 Worker 間の相互作用は Persistent Data Tree への読み書きのみで行う。 | |
204 | |
205 Code \ref{src:context}, Code \ref{src:initContext} に実際の Context の定義と生成を示す。 | |
206 | |
207 \lstinputlisting[label=src:context, caption=Context]{./src/context.h} | |
208 \lstinputlisting[label=src:initContext, caption=initContext]{./src/context.c} | |
209 | |
210 Code \ref{src:context}, Code \ref{src:initContext} は以下の事を定義している。 | |
211 | |
212 \paragraph* {Code Gear の名前とポインタのリスト} | |
213 Code Gear の名前とポインタの対応は Code \ref{src:context} の enum Codeと 関数ポインタによって表現される。 | |
214 実際に Code Gear に接続する際は enum Code を指定することで接続を行う。 | |
215 これにより、実行時のルーチンなどを動的に変更することが可能となる。 | |
216 | |
217 \paragraph* {Data Gear の Allocation 用の情報} | |
218 Context の生成時(Code \ref{src:initContext})、 Allocation 用に Code \ref{src:context} の ALLOCATE\_SIZE 分の領域を確保する。 | |
219 Context にはその領域へのポインタとサイズが格納されている(Code \ref{src:context}の struct Context 内の heap, heapLimit)。 | |
220 実際に Allocation する際は heap を 必要な Data Gear のサイズに応じてインクリメントすることで Data Gear の Allocation を実現する。 | |
221 | |
222 \paragraph* {Data Gear へのポインタ} | |
223 Context には Allocation 等で生成した Data Gear へのポインタが格納されている。 | |
224 Code Gear は Context を通して Data Gear へアクセスする。 | |
225 | |
226 \paragraph* {Data Gear に格納される Data Type の情報} | |
227 Data Gear は Code \ref{src:context} の union Data と その中の struct によって表現される。 | |
228 Context には Data Gear の Data Type の情報が格納されている。 | |
229 この情報から確保される Data Gear のサイズなどを決定する。 | |
230 | |
231 \section{TaskQueue} | |
232 Gears OS における Task Queue は Synchronized Queue で実現される。 | |
233 メインとなる Context と Worker 用 の Context で共有され、 Worker が TaskQueue から Task を取得し、実行することで並列処理を行う。 | |
234 | |
235 Gears OS の Queue は Queue を表す Data Gear と List を表現する Element という名前の Data Gear を組み合わせて表現する。 | |
236 Queue を表す Data Gear には List 構造の先頭の Element を指す first, 末尾の Element を指す last, Element の個数を示す count が格納される。 | |
237 Element を表す Data Gear は、Task を示す task、 次の Element を示す next が格納される。 | |
238 | |
239 Queue に対して操作を行う場合、 Queue 自体の Data Gear を書き換える。 | |
240 Task を 挿入する場合、 新しく Element を生成し、 Queue の last から List 構造の末尾に新しい Element を追加し、 Queue の last を書き換える。 | |
241 Task を 取得する場合、 Queue の first から List 構造を最初の要素を取り出し、 取り出した要素の次の要素の参照を Queue の first に書き込む。 | |
242 | |
243 Gears OS の TaskQueue はマルチスレッドでの操作を想定しているため、データの一貫性を保証する必要がある。 | |
244 そのため、データの一貫性を並列実行時でも保証するために Compare and Swap(CAS) を利用して Queue の操作を行っている。 | |
245 CAS はデータの比較・置換をアトミックに行う命令である。 | |
246 メモリからデータの読みだし、変更、メモリへのデータの書き出しという一連の処理を CAS を利用することで処理の間に他のスレッドがメモリに変更を加えないことを保証することができる。 | |
247 CAS に失敗した場合は置換を行わず、再びデータの呼び出しから始める。 | |
248 | |
249 Code \ref{src:sync_enqueue} に CAS を使用した Task 挿入を示している。 | |
250 Code \ref{src:sync_enqueue} は 2つのCode Gear を定義しており、 putQueue3 は Queue に要素がある場合、 putQueue4 は Queue に要素がない場合の Task 挿入を示している。 | |
251 | |
252 \lstinputlisting[label=src:sync_enqueue, caption=Enqueue]{./src/sync_enqueue.c} | |
253 | |
254 \section{Persistent Data Tree} | |
255 Gears OS は Persistent Data Gear の管理に木構造を用いる。 | |
256 この木構造は非破壊的で構成される。 | |
257 非破壊木構造とは図\ref{fig:persistent_data_tree}のように一度構築した木構造を破壊すること無く新しい木構造を構築することで、木構造を編集する方法である。 | |
258 非破壊木構造は木構造を書き換えることなく編集を行うため、読み書きを平行して行うことが可能である。 | |
259 | |
260 \begin{figure}[ht] | |
261 \begin{center} | |
262 \includegraphics[width=80mm]{./pic/persistent_date_tree.pdf} | |
263 \end{center} | |
264 \caption{木構造の非破壊的編集} | |
265 \label{fig:persistent_data_tree} | |
266 \end{figure} | |
267 | |
268 Gears OS では Data Tree として木構造を利用する。 | |
269 その場合、普通に木構造を構築するだけでは偏った木構造が構築される可能性がある。 | |
270 最悪なケースでは線形リストになり、計算量が O(n) となる。 | |
271 | |
272 そのため、挿入・削除・検索における処理時間を保証するため Red-Black Tree を用いて木構造の平衡性を保証する。 | |
273 Red-Black Tree は通常の二分探索木としての条件の他に以下の条件を持つ。 | |
274 | |
275 \begin{itemize} | |
276 \item 各ノードは赤または黒の色を持つ。 | |
277 \item ルートの色は黒である。 | |
278 \item 赤ノードは2つの黒ノードを子として持つ(赤ノードが続くことはない)。 | |
279 \item ルートから最下位ノードへのパスに含まれる黒ノードの数はどの最下位ノードでも一定である。 | |
280 \end{itemize} | |
281 | |
282 これらの条件によってルートから最も遠い最下位ノードへのパスの長さはルートから最も近い最下位ノードへのパスの長さの2倍に収まることが保証される。 | |
283 | |
284 \section{Worker} | |
285 Worker は TaskQueue から Task を取得し、実行する。 | |
286 Task には実行する Code Gear と実行に必要な Code Gear の key が格納されている。 | |
287 実行に必要な Code Gear は Persistent Data Tree から key を使って取得する。 | |
288 | |
289 各 Worker は個別の Context を参照しており、 メモリ空間も独立しているのでメモリを確保する処理で他の Thread を止めることはない。 | |
290 ただし、Persistent Data Tree への書き出しは競合する可能性があるので CAS を利用してデータの一貫性を保証する必要がある。 | |
291 | |
292 Worker が TaskQueue から Task の取得を行う Code Gear を Code \ref{src:sync_dequeue} に示す。 | |
293 Task Queue から取得した Task から実行する Code Gear と必要な Data Gear の key を Worker Context に書き込むことで実行される。 | |
294 | |
295 \lstinputlisting[label=src:sync_dequeue, caption=GetTask]{./src/sync_dequeue.c} | |
296 | |
297 Worker から取得された Task の Code Gear は並列実行される。 | |
298 並列実行される Code Gear と言っても他の Code Gear と同じである。 | |
299 これは Gears OS 自体が Code Gear によって構成されていることに起因する。 | |
300 つまり、 Gears OS を利用して書かれたプログラムで定義されている Code Gear に依存関係がないとき、全て並列に実行することができる。 | |
301 | |
302 \section{TaskManager} | |
303 Gears OS の TaskManager は WaitTaskQueue に入っている Task の依存関係を解決する。 | |
304 Task には Input/Output Data Gear の情報が格納されている。 | |
305 Input Data Gear は Task に必要な Data Gear で揃ったら Task は実行可能な状態になる。 | |
306 Output Data Gear は Task が Persistent Data Tree に書き出す Data Gear である。 | |
307 この Input と Output の関係が依存関係となる。 | |
308 TaskManager は Persistent Data Tree を監視しており、WaitTaskQueue に入っている Task の Input Data Gear が揃っているのを確認したら実行可能な Task として AcitiveTaskQueue へ移動させる。 | |
309 | |
310 \section{プロトタイプの動作} | |
311 Gears OS の評価として依存関係のない例題の並列実行を行った。 | |
312 | |
313 今回使用した例題は Twice という整数配列を2倍にする例題である。 | |
314 Code \ref{src:twice} に Twice の処理を行う Code Gear を示す。 | |
315 | |
316 \lstinputlisting[label=src:twice, caption=Twice]{./src/twice.c} | |
317 | |
318 以下に今回の処理の流れを示す。 | |
319 | |
320 \begin{itemize} | |
321 \item 配列サイズを元に index, alignment, 配列へのポインタを持つ Data Gear に分割。 | |
322 \item Data Gear を Persistent Data Tree に挿入。 | |
323 \item 実行する Code Gear(Twice) と実行に必要な Data Gear への key を持つ Task を生成。 | |
324 \item 生成した Task を TaskQueue に挿入。 | |
325 \item Worker の起動。 | |
326 \item Worker が TaskQueue から Task を取得。 | |
327 \item 取得した Task を元に必要な Data Gear を Persistent Data Tree から取得。 | |
328 \item 並列の処理される Code Gear(Twice) を実行。 | |
329 \end{itemize} | |
330 | |
331 要素数$2^{17}$*1000 のデータを640個の Task に分割し、コア数を変更して測定を行った結果を表\ref{table:result}、図\ref{fig:result}に示す。 | |
332 | |
333 \begin{table}[ht] | |
334 \begin{center} | |
335 \small | |
336 \begin{tabular}[htpb]{|c||c|c|c|} | |
337 \hline | |
338 Processor & Time(ms) \\ | |
339 \hline | |
340 \hline | |
341 1 CPU & 1315 \\ | |
342 \hline | |
343 2 CPUs & 689 \\ | |
344 \hline | |
345 4 CPUs & 366 \\ | |
346 \hline | |
347 8 CPUs & 189 \\ | |
348 \hline | |
349 12 CPUs & 111 \\ | |
350 \hline | |
351 \end{tabular} | |
352 \caption{要素数$2^{17}$*1000 のデータに対する Twice} | |
353 \label{table:result} | |
354 \end{center} | |
355 \end{table} | |
356 | |
357 \begin{figure}[ht] | |
358 \begin{center} | |
359 \includegraphics[width=70mm]{pic/twice_640.pdf} | |
360 \end{center} | |
361 \caption{要素数$2^{17}$*1000 のデータに対する Twice} | |
362 \label{fig:result} | |
363 \end{figure} | |
364 | |
365 結果から、 1 CPU と 12 CPU で約 11.8 倍の速度向上が見られた。 | |
366 しかし、 タスクの粒度が小さすぎると CAS の失敗が多くなり、性能がでないことがある。 | |
367 Code Gear には実行時間を予想可能なものにするという特徴があるため、タスクが最適な粒度なのかを検査する機能が必要になると考えられる。 | |
368 | |
369 \section{比較} | |
370 本章では今回設計・実装した Gears OS と既存の並列フレームワークとの比較を行う。 | |
371 また、Gears OS は以下のような性質を有している。 | |
372 | |
373 \begin{itemize} | |
374 \item リソース管理 \\ | |
375 Context 毎に異なるメモリ空間を持ち、それを管理する。 | |
376 Meta Code Gear, Meta Data Gear を用いてネットワーク管理、並行制御等を行う。 | |
377 \item 処理の効率化 \\ | |
378 依存関係のない Code Gear は並列実行することが可能である。 | |
379 また、Code Gear 自体が処理の最小単位となっており Code Gear を利用してプログラムを記述するとプログラム全体の並列度を高めることに繋がる。 | |
380 \item プロセッサ利用の抽象化 \\ | |
381 Multi Core CPU, GPU を同等の実行機構で実行可能である。 | |
382 \end{itemize} | |
383 | |
384 これらの性質を有する Gears OS はオペレーティングシステムであると言えるので既存の OS との比較も行う。 | |
385 | |
386 \paragraph*{Cerium} | |
387 \begin{itemize} | |
388 \item 依存関係 \\ | |
389 Cerium では Task 間で依存関係を設定する。 | |
390 Task の途中でデータが破損しても完了を TaskManager に通知し、依存関係を解決して次の Task が実行される。 | |
391 これではデータの正しさを保証することができない。 | |
392 | |
393 Gears OS では Task に Input/Output Data Gear を設定することで Input と Output の関係から依存関係を決定する。 | |
394 TaskManager は Persistent Data Tree を監視し、必要な Data Gear が揃っていることを確認すると依存関係を解決する。 | |
395 \item データの型情報 \\ | |
396 Cerium では Task にデータを引き渡すとき汎用ポインタを用いる。 | |
397 このときデータの型情報が落ちるので Task の組み合わせが型的に安全なのか保証することができない。 | |
398 | |
399 Gears OS では型情報を持つ分割されたデータとして Data Gear を定義し、Data Gear 単位でデータを Task に引き渡す。 | |
400 Data Gear を型シグネチャとして Task の組み合わせが正しいことを保証する。 | |
401 \item Allocator \\ | |
402 Cerium では Thread 間で Allocator を共有している。 | |
403 ある Thread がメモリ確保を行うとその間、他の Thread はメモリを確保することができず並列度が低下する。 | |
404 | |
405 Gears OS では Thraed ごとに Context を割り当てる。 | |
406 Context は独立したメモリ空間を持つので他の Thread と干渉することないメモリの確保を行うことができる。 | |
407 \item 並列処理との相性 \\ | |
408 Cerium はオブジェクト指向言語である C++ で実装されている。 | |
409 オブジェクト指向は保守性と再利用性を高めるためにカプセル化とポリモフィズムを重視する。 | |
410 オブジェクトの状態によって振る舞いが変わるため参照透過な処理でなくなり並列処理との相性が悪い。 | |
411 | |
412 Gears OS は本研究で開発している CbC を用いて実装する。 | |
413 CbC は Code Segment という単位でプログラムを記述する。 | |
414 Code Segment はスタックに値を積まない軽量継続を用いて他の Code Segment に遷移する。 | |
415 この軽量継続により並列化、ループ制御などを意識した最適化がソースコードレベルで行うことができる。 | |
416 \end{itemize} | |
417 | |
418 \paragraph*{OpenCL/CUDA} | |
419 OpenCL\cite{opencl}/CUDA\cite{cuda} では並列処理に用いる関数を kernel として定義する。 | |
420 OpenCL では CommandQueue, CUDA では Stream という命令キューに命令を発行することで GPU を利用することができる。 | |
421 命令キューは発行された順番通りに命令が実行されることが保証されている。 | |
422 複数の命令キューを準備して、各命令キューに命令を発行することで命令を並列に実行することができる。 | |
423 命令キュー単位で依存関係を設定することができる。 | |
424 つまり、命令キューに入っている最後の命令次第でデータを待っているのか kernel の実行を待っているのか変わるので依存関係の記述が複雑になる。 | |
425 データは kernel の引数の定義に型変換され渡される。 | |
426 データ転送の際には型情報が落として渡す必要があり、型を意識したプログラミングが必要になる。 | |
427 | |
428 一方、Gears OS ではデータによって依存関係が決定する。 | |
429 また、データを Data Segment という単位で分割して管理しており型情報を保ったままデータの受け渡しを行うことができる。 | |
430 | |
431 \paragraph*{OpenMP} | |
432 OpenMP ではループ制御構文の前にアノテーションを付ける(Code \ref{openmp})ことでコンパイラが解釈し、スレッド処理を行うように変換して並列処理を行う。 | |
433 | |
434 \lstinputlisting[label=openmp, caption=OpenMP]{src/openmp.c} | |
435 | |
436 他の並列化手法に比べて既存のコードに対する変更が少なくて済む。 | |
437 しかし、この方法ではプログラム全体の並列度が上がらずアムダールの法則により性能向上が頭打ちになる。 | |
438 | |
439 一方、Gears OS では初めから Code Gear, Data Gear という単位でプログラムを分割して記述するのでプログラム全体の並列度を高めることができる。 | |
440 | |
441 \paragraph*{従来の OS} | |
442 従来の OS が行ってきたネットワーク管理、メモリ管理、平行制御などのメタな部分を Gears OS では Meta Code/Data Gear として定義する。 | |
443 通常の Code Gear から必要な制御を推論し、Meta Code Gear を接続することで従来の OS が行ってきた制御を提供する。 | |
444 このメタ計算は関数型言語で用いられる Monad に基づいて実現する。 | |
445 \section{まとめ} | |
446 本論文では Code Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った。 | |
447 | |
448 Code Gear は処理、 Data Gear はデータの単位である。 | |
449 Code Gear は戻り値を持たないので、関数呼び出しのようにスタックに値を積む必要がなく、スタックは変更されない。 | |
450 そのため並列化、ループ制御、関数コールとスタックの操作を意識した最適化をソースコードレベルで行える。 | |
451 また、プログラム Code/Data Gear に分割して記述することで並列度を高めることができる。 | |
452 | |
453 Gears OS の基本的な機能として、 TaskQueue, Persistent Data Tree, Workerの実装を Code/Data Gear に基づいて行った。 | |
454 Gears OS では Context というデータ構造に Code/Data Gear のリスト、 TaskQueue へのポインタ Persistent Data Tree へのポインタ、Temporal Data Gear を確保するためのメモリ空間などがある。 | |
455 Context はスレッド毎に存在し、それぞれが異なる Context を参照している。 | |
456 TaskQueue は並列処理される Task を管理する。 | |
457 TaskQueue はすべての Context で共有され、マルチスレッドで動作する必要がある。 | |
458 そのためデータの一貫性を保つために Compare and Swap(CAS) を用いた実装を行った。 | |
459 Persistent Data Tree は 並列処理 での Data Gearの管理を行う。 | |
460 そのためすべての Context で共有される。 | |
461 Persistent Data Tree は非破壊木構造で構成することで読み書きのを平行して行う事が可能となった。 | |
462 また、Red-Black Tree アルゴリズムを用いて実装することで木の平衡性が保たれる。 | |
463 Worker は TaskQueue から Task を取り出し、 Persistent Data Tree から Data Gear を取得し、 Task 内の Code Gear の並列実行を行う。 | |
464 また、個別の Context を参照しているので、メモリ空間が独立しており、メモリを確保する処理で他の Worker を止めることはない。 | |
465 | |
466 今後の課題として、 依存関係のある並列処理の実現、 GPU などのプロセッサ等での実行、 デバック手法、 型検査が上げられる。 | |
467 | |
468 今回の例題では Twice を用いて並列処理の性能を示したが、 Twice は依存関係のない並列処理である。 | |
469 本来、並列処理には依存関係が存在するため、 複雑な並列処理でも安定した実行ができることを依存関係がある並列処理の例題を作成し、評価する必要がある。 | |
470 | |
471 Gears OS 上でマルチコア CPU を用いた実行を可能にしたが、 GPU などの他のプロセッサを演算に用いることができない。 | |
472 そのため、 Data Gear 等のデータを GPU などの各プロセッサにマッピングするための機構を用意する必要がある。 | |
473 | |
474 Gears OS は 関数呼び出しではなく、スタックを積まない軽量継続を使用して実装されているため、スタックトレースが見えず、従来のデバック手法が使えない。 | |
475 そのため、Gears OS 用の 新しい デバック手法を考案する必要がある。 | |
476 Gears OS は Context から Data Gear の情報を取得できるため、そこから今の状況を把握することができる。 | |
477 その性質から、 Context を見ることができるコードを Meta Code Gear に入れることで、 Code Gear を止めて Data Gear の状況を見ることが可能となる。 | |
478 しかし、この方法では並列で動いている Code Gear に対しては綺麗にデバック出来ない。 | |
479 そのため、並列処理でのデバック手法も考案する必要がある。 | |
480 | |
481 また、型情報を残すために Data Gear を定義しているが、 Data Gear の型情報を検査していない。 | |
482 プログラムの正しさを保証するために Data Gear の型情報を検査するシステムを 実装する必要がある。 | |
483 % GPU の方も書く | |
484 % debug 手法 | |
485 | |
486 \nocite{*} | |
487 \bibliographystyle{ipsjunsrt} | |
488 \bibliography{sigos} | |
489 | |
490 \end{document} |