|
14
|
1 <!DOCTYPE html>
|
|
|
2 <html>
|
|
|
3 <head>
|
|
|
4 <meta http-equiv="content-type" content="text/html;charset=utf-8">
|
|
|
5 <title>Code Gear、 Data Gear に基づく OS のプロトタイプ</title>
|
|
|
6
|
|
|
7 <meta name="generator" content="Slide Show (S9) v2.5.0 on Ruby 2.3.1 (2016-04-26) [x86_64-darwin15]">
|
|
|
8 <meta name="author" content="伊波 立樹" >
|
|
|
9
|
|
|
10 <!-- style sheet links -->
|
|
|
11 <link rel="stylesheet" href="s6/themes/projection.css" media="screen,projection">
|
|
|
12 <link rel="stylesheet" href="s6/themes/screen.css" media="screen">
|
|
|
13 <link rel="stylesheet" href="s6/themes/print.css" media="print">
|
|
|
14 <link rel="stylesheet" href="s6/themes/blank.css" media="screen,projection">
|
|
|
15
|
|
|
16 <!-- JS -->
|
|
|
17 <script src="s6/js/jquery-1.11.3.min.js"></script>
|
|
|
18 <script src="s6/js/jquery.slideshow.js"></script>
|
|
|
19 <script src="s6/js/jquery.slideshow.counter.js"></script>
|
|
|
20 <script src="s6/js/jquery.slideshow.controls.js"></script>
|
|
|
21 <script src="s6/js/jquery.slideshow.footer.js"></script>
|
|
|
22 <script src="s6/js/jquery.slideshow.autoplay.js"></script>
|
|
|
23
|
|
|
24 <!-- prettify -->
|
|
|
25 <link rel="stylesheet" href="scripts/prettify.css">
|
|
|
26 <script src="scripts/prettify.js"></script>
|
|
|
27
|
|
|
28 <script>
|
|
|
29 $(document).ready( function() {
|
|
|
30 Slideshow.init();
|
|
|
31
|
|
|
32 $('code').each(function(_, el) {
|
|
|
33 if (!el.classList.contains('noprettyprint')) {
|
|
|
34 el.classList.add('prettyprint');
|
|
|
35 el.style.display = 'block';
|
|
|
36 }
|
|
|
37 });
|
|
|
38 prettyPrint();
|
|
|
39 } );
|
|
|
40
|
|
|
41
|
|
|
42 </script>
|
|
|
43
|
|
|
44 <!-- Better Browser Banner for Microsoft Internet Explorer (IE) -->
|
|
|
45 <!--[if IE]>
|
|
|
46 <script src="s6/js/jquery.microsoft.js"></script>
|
|
|
47 <![endif]-->
|
|
|
48
|
|
|
49
|
|
|
50
|
|
|
51 </head>
|
|
|
52 <body>
|
|
|
53
|
|
|
54 <div class="layout">
|
|
|
55 <div id="header"></div>
|
|
|
56 <div id="footer">
|
|
|
57 <div align="right">
|
|
|
58 <img src="s6/images/logo.svg" width="200px">
|
|
|
59 </div>
|
|
|
60 </div>
|
|
|
61 </div>
|
|
|
62
|
|
|
63 <div class="presentation">
|
|
|
64
|
|
|
65 <div class='slide cover'>
|
|
|
66 <table width="90%" height="90%" border="0" align="center">
|
|
|
67 <tr>
|
|
|
68 <td>
|
|
|
69 <div align="center">
|
|
|
70 <h1><font color="#808db5">Code Gear、 Data Gear に基づく OS のプロトタイプ</font></h1>
|
|
|
71 </div>
|
|
|
72 </td>
|
|
|
73 </tr>
|
|
|
74 <tr>
|
|
|
75 <td>
|
|
|
76 <div align="left">
|
|
|
77 伊波 立樹
|
|
18
|
78 琉球大学理工学研究科
|
|
14
|
79 <hr style="color:#ffcc00;background-color:#ffcc00;text-align:left;border:none;width:100%;height:0.2em;">
|
|
|
80 </div>
|
|
|
81 </td>
|
|
|
82 </tr>
|
|
|
83 </table>
|
|
|
84 </div>
|
|
|
85
|
|
|
86 <div class='slide '>
|
|
|
87 <!-- === begin markdown block ===
|
|
|
88
|
|
|
89 generated by markdown/1.2.0 on Ruby 2.3.1 (2016-04-26) [x86_64-darwin15]
|
|
21
|
90 on 2016-05-31 11:06:27 +0900 with Markdown engine kramdown (1.11.1)
|
|
14
|
91 using options {}
|
|
|
92 -->
|
|
|
93
|
|
|
94 <!-- _S9SLIDE_ -->
|
|
17
|
95 <h2 id="gears-os">Gears OS</h2>
|
|
|
96 <ul>
|
|
18
|
97 <li>当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて
|
|
|
98 <ul>
|
|
|
99 <li>並列性</li>
|
|
|
100 <li>柔軟性</li>
|
|
|
101 <li>信頼性</li>
|
|
|
102 </ul>
|
|
|
103 </li>
|
|
|
104 </ul>
|
|
|
105
|
|
|
106 <p>を指標とした Gears OS を設計してきた</p>
|
|
|
107
|
|
|
108 <ul>
|
|
21
|
109 <li>本研究では Gears OS のプロトタイプとして並列処理機構を Continuation based C(CbC) で実装を行う</li>
|
|
17
|
110 </ul>
|
|
|
111
|
|
|
112
|
|
|
113 </div>
|
|
|
114 <div class='slide '>
|
|
|
115 <!-- _S9SLIDE_ -->
|
|
16
|
116 <h2 id="gears-os-">Gears OS の並列性</h2>
|
|
14
|
117 <ul>
|
|
18
|
118 <li>Gears OS はプログラムの単位として Gear を用いる</li>
|
|
|
119 <li>Gear には プログラムの処理を示す Code Gear、 Data を示す Data Gear がある</li>
|
|
16
|
120 <li>Code/Data Gear を用いて記述することでプログラム全体の並列度を高め、効率的に並列処理することが可能</li>
|
|
14
|
121 </ul>
|
|
|
122
|
|
18
|
123 <div style="text-align: center;">
|
|
|
124 <img src="./images/codeGear_dataGear.svg" alt="message" width="450" />
|
|
|
125 </div>
|
|
|
126
|
|
14
|
127
|
|
|
128 </div>
|
|
|
129 <div class='slide '>
|
|
|
130 <!-- _S9SLIDE_ -->
|
|
16
|
131 <h2 id="gears-os--1">Gears OS の柔軟性</h2>
|
|
14
|
132 <ul>
|
|
18
|
133 <li>Gears OS は Meta Computation を使用することで
|
|
|
134 <ul>
|
|
|
135 <li>データ拡張や機能の追加</li>
|
|
|
136 <li>GPU 等のさまざまなアーキテクチャでも同じプログラムの動作</li>
|
|
|
137 <li>バージョンが異なる者同士がネットワーク接続しても通信</li>
|
|
|
138 </ul>
|
|
|
139 </li>
|
|
15
|
140 </ul>
|
|
|
141
|
|
18
|
142 <p>等を柔軟に対応する</p>
|
|
|
143
|
|
|
144 <ul>
|
|
|
145 <li>Meta Computation は 通常の Computaiton と階層を分けて処理を行う</li>
|
|
|
146 </ul>
|
|
|
147
|
|
|
148 <div style="text-align: center;">
|
|
|
149 <img src="./images/meta_gear.svg" alt="message" width="800" />
|
|
|
150 </div>
|
|
|
151
|
|
15
|
152
|
|
|
153 </div>
|
|
|
154 <div class='slide '>
|
|
|
155 <!-- _S9SLIDE_ -->
|
|
16
|
156 <h2 id="gears-os--2">Gears OS の信頼性</h2>
|
|
15
|
157 <ul>
|
|
16
|
158 <li>検証
|
|
|
159 <ul>
|
|
|
160 <li>モデル検査を行う</li>
|
|
18
|
161 <li>モデル検査は状態の数が膨大になると検査するのが難しい</li>
|
|
|
162 <li>そのため、不必要な状態である環境やスタックをなるべく取り除き、処理を行う</li>
|
|
16
|
163 </ul>
|
|
|
164 </li>
|
|
|
165 <li>証明
|
|
|
166 <ul>
|
|
18
|
167 <li>Code Gear と Data Gear を理論的に定義</li>
|
|
16
|
168 </ul>
|
|
|
169 </li>
|
|
14
|
170 </ul>
|
|
|
171
|
|
|
172
|
|
|
173 </div>
|
|
|
174 <div class='slide '>
|
|
|
175 <!-- _S9SLIDE_ -->
|
|
18
|
176 <h2 id="section">この発表は</h2>
|
|
14
|
177 <ul>
|
|
18
|
178 <li>Gears OS でのGear</li>
|
|
|
179 <li>Meta Computation</li>
|
|
|
180 <li>Continuation based C(CbC)</li>
|
|
|
181 <li>CbC を用いた Gears OS の記述</li>
|
|
21
|
182 <li>Gears OS の並列処理のプロトタイプ</li>
|
|
18
|
183 <li>まとめ</li>
|
|
|
184 <li>課題</li>
|
|
14
|
185 </ul>
|
|
|
186
|
|
|
187
|
|
|
188 </div>
|
|
|
189 <div class='slide '>
|
|
|
190 <!-- _S9SLIDE_ -->
|
|
15
|
191 <h2 id="code-gear-data-gear">Code Gear、 Data Gear</h2>
|
|
14
|
192 <ul>
|
|
19
|
193 <li>Gears OS は Code Gear、 Data Gear という Gear で構成される</li>
|
|
14
|
194 <li>Code Gear はプログラムの処理そのものを表す</li>
|
|
16
|
195 <li>Data Gear は int や 文字列などの Data そのものを表す</li>
|
|
|
196 <li>Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する</li>
|
|
18
|
197 <li>Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を行う</li>
|
|
14
|
198 </ul>
|
|
16
|
199
|
|
15
|
200 <div style="text-align: center;">
|
|
18
|
201 <img src="./images/codeGear_dataGear_dependency.svg" alt="message" width="600" />
|
|
14
|
202 </div>
|
|
|
203
|
|
|
204
|
|
|
205 </div>
|
|
|
206 <div class='slide '>
|
|
|
207 <!-- _S9SLIDE_ -->
|
|
|
208 <h2 id="meta-computation">Meta Computation</h2>
|
|
|
209 <ul>
|
|
16
|
210 <li>Meta Computation は通常の Computation のための Computation</li>
|
|
18
|
211 <li>並列処理の依存関係の解決、 GPUなどのアーキテクチャでの実行のために行う処理などを行う</li>
|
|
16
|
212 <li>Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現</li>
|
|
14
|
213 </ul>
|
|
|
214
|
|
|
215
|
|
|
216 </div>
|
|
|
217 <div class='slide '>
|
|
|
218 <!-- _S9SLIDE_ -->
|
|
|
219 <h2 id="meta-gear">Meta Gear</h2>
|
|
|
220 <ul>
|
|
18
|
221 <li>Meta Computation は Code/Data Gearの接続の間に行われる</li>
|
|
|
222 <li>Meta Computation の処理も Code/Data Gear で実現する</li>
|
|
|
223 <li>この Gear を Meta Code/Data Gearと呼ぶ
|
|
|
224 <ul>
|
|
|
225 <li>Meta Code Gear は Meta Computation のプログラム部分</li>
|
|
|
226 <li>Meta Data Gear は Meta Code Gear で管理されるデータ部分</li>
|
|
|
227 </ul>
|
|
|
228 </li>
|
|
20
|
229 <li>Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 接続部分は見えないように実装を行う</li>
|
|
14
|
230 </ul>
|
|
|
231
|
|
15
|
232 <div style="text-align: center;">
|
|
20
|
233 <img src="./images/meta_cg_dg.svg" alt="message" width="850" />
|
|
15
|
234 </div>
|
|
|
235
|
|
14
|
236
|
|
|
237 </div>
|
|
|
238 <div class='slide '>
|
|
|
239 <!-- _S9SLIDE_ -->
|
|
|
240 <h2 id="continuation-based-c">Continuation based C</h2>
|
|
|
241 <ul>
|
|
21
|
242 <li>Gears OS の実装は本研究室で開発している Continuation based C(CbC) を用いる</li>
|
|
14
|
243 <li>CbC は処理を Code Segment を用いて記述する事を基本とする</li>
|
|
16
|
244 <li>Code Segment は Code Gear を同等のものため、 Gears OS を記述するのに適している</li>
|
|
14
|
245 </ul>
|
|
|
246
|
|
|
247
|
|
|
248 </div>
|
|
|
249 <div class='slide '>
|
|
|
250 <!-- _S9SLIDE_ -->
|
|
|
251 <h2 id="continuation-based-c-1">Continuation based C</h2>
|
|
|
252 <ul>
|
|
18
|
253 <li>Code Segment の定義は <code>__code CS名</code> で行う</li>
|
|
14
|
254 <li>Code Segment 間は <code>goto CS名</code> で移動する。この移動を継続と呼ぶ</li>
|
|
20
|
255 <li>Code Segment の継続は C の関数呼び出しとは異なり、戻り値を持たないためスタックの変更を行わない
|
|
|
256 <ul>
|
|
|
257 <li>このような環境を持たない継続を軽量継続と呼ぶ</li>
|
|
|
258 </ul>
|
|
|
259 </li>
|
|
14
|
260 </ul>
|
|
|
261
|
|
18
|
262
|
|
|
263 </div>
|
|
|
264 <div class='slide '>
|
|
|
265 <!-- _S9SLIDE_ -->
|
|
|
266 <h2 id="continuation-based-c-2">Continuation based C</h2>
|
|
|
267 <ul>
|
|
|
268 <li>このコードは code1、code2 の2つの Code Segment を定義している</li>
|
|
|
269 <li>code1 内の <code>goto code2</code> でcode2 への継続を行っている</li>
|
|
|
270 </ul>
|
|
|
271
|
|
16
|
272 <pre lang="c"><code>/* code1 define */
|
|
|
273 __code code1(List list) {
|
|
|
274 ....
|
|
|
275 goto code2(list)
|
|
|
276 }
|
|
|
277
|
|
|
278 /* code2 define */
|
|
|
279 __code code2(List list) {
|
|
|
280 ...
|
|
|
281 }
|
|
|
282 </code></pre>
|
|
|
283
|
|
|
284
|
|
|
285 </div>
|
|
|
286 <div class='slide '>
|
|
|
287 <!-- _S9SLIDE_ -->
|
|
18
|
288 <h2 id="cbc--gears-os-">CbC を用いた Gears OS の記述</h2>
|
|
|
289 <ul>
|
|
|
290 <li>Gears OS での Code Gear も Code Segment の定義のように記述する</li>
|
|
|
291 <li>各 Code Gear の引数は 必要な Data Gear を示す</li>
|
|
|
292 <li>このコードでは 2つの Code Gear と 1つの Meta Code Gear を定義しており、 code1 から code2への継続を行っている</li>
|
|
|
293 </ul>
|
|
|
294
|
|
|
295 <pre lang="c"><code>__code code1(struct Array* array, struct LoopCounter* loopCounter) {
|
|
|
296 ...
|
|
|
297 goto code2(array);
|
|
|
298 }
|
|
|
299
|
|
|
300 __code meta_code1(struct Context* context, enum Code next) {
|
|
|
301 goto (context->code[next])(context);
|
|
|
302 }
|
|
|
303
|
|
|
304 __code code2(struct Array* array) {
|
|
|
305 ...
|
|
|
306 }
|
|
|
307 </code></pre>
|
|
|
308
|
|
|
309
|
|
|
310 </div>
|
|
|
311 <div class='slide '>
|
|
|
312 <!-- _S9SLIDE_ -->
|
|
|
313 <h2 id="cbc--gears-os--1">CbC の Gears OS サポート</h2>
|
|
|
314 <ul>
|
|
|
315 <li>実際は code1 から code2 への継続の間には Meta Code Gear である meta_code1 が実行される</li>
|
|
19
|
316 <li>通常は Meta Level の継続をプログラマーは意識する必要はない</li>
|
|
18
|
317 <li>そこで、CbC は Code Gear 間の接続に自動的に Meta Code Gear を挟むというサポートを行う</li>
|
|
|
318 <li>CbC のサポートを行うとこのコードのように展開される</li>
|
|
|
319 <li>メタレベルのサポートの際は <strong>context</strong> という Meta Data Gear を使用する</li>
|
|
|
320 </ul>
|
|
|
321
|
|
|
322 <pre lang="c"><code>__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) {
|
|
|
323 ...
|
|
|
324 goto meta_code1(context, Code2);
|
|
|
325 }
|
|
|
326
|
|
|
327 __code code1_stub(struct Context* context) {
|
|
|
328 goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter);
|
|
|
329 }
|
|
|
330
|
|
|
331 __code meta_code1(struct Context* context, enum Code next) {
|
|
|
332 goto (context->code[next])(context);
|
|
|
333 }
|
|
|
334
|
|
|
335 __code code2(struct Context* context, struct Array* array) {
|
|
|
336 ...
|
|
|
337 }
|
|
|
338 </code></pre>
|
|
|
339
|
|
|
340
|
|
|
341 </div>
|
|
|
342 <div class='slide '>
|
|
|
343 <!-- _S9SLIDE_ -->
|
|
16
|
344 <h2 id="context">Context</h2>
|
|
|
345 <ul>
|
|
18
|
346 <li>Context は
|
|
|
347 <ul>
|
|
|
348 <li>接続可能な Code/Data Gear のリスト</li>
|
|
|
349 <li>独立したメモリ空間
|
|
|
350 をもっている</li>
|
|
|
351 </ul>
|
|
|
352 </li>
|
|
|
353 <li>各 Code/Data Gear にアクセスする際は Context を経由する</li>
|
|
16
|
354 </ul>
|
|
|
355
|
|
|
356
|
|
15
|
357 </div>
|
|
16
|
358 <div class='slide '>
|
|
|
359 <!-- _S9SLIDE_ -->
|
|
|
360 <h2 id="context-1">Context</h2>
|
|
|
361 <ul>
|
|
18
|
362 <li>Context は
|
|
|
363 <ul>
|
|
20
|
364 <li>実行可能な Code Gear の数を示す <strong>codeNum</strong></li>
|
|
|
365 <li>実行可能な Code Gear のリストを示す <strong>code</strong></li>
|
|
18
|
366 <li>Data Gear の Allocate 用の <strong>heapStart</strong>, <strong>heap</strong>, <strong>heapLimit</strong></li>
|
|
|
367 <li>Data Gear の数を示す <strong>dataNum</strong></li>
|
|
|
368 <li>Data Gear のリストを示す <strong>data</strong>
|
|
|
369 で構成される</li>
|
|
|
370 </ul>
|
|
|
371 </li>
|
|
16
|
372 </ul>
|
|
|
373
|
|
|
374 <pre lang="c"><code>/* context define */
|
|
|
375 struct Context {
|
|
|
376 int codeNum;
|
|
|
377 __code (**code) (struct Context*);
|
|
|
378 void* heapStart;
|
|
|
379 void* heap;
|
|
|
380 long heapLimit;
|
|
|
381 int dataNum;
|
|
|
382 union Data **data;
|
|
|
383 };
|
|
|
384 </code></pre>
|
|
|
385
|
|
18
|
386
|
|
|
387 </div>
|
|
|
388 <div class='slide '>
|
|
|
389 <!-- _S9SLIDE_ -->
|
|
|
390 <h2 id="context-2">Context</h2>
|
|
16
|
391 <ul>
|
|
18
|
392 <li>実行可能な Code Gear の名前は <strong>enum code</strong> で定義する</li>
|
|
|
393 <li>Context の初期化時に名前と関数ポインタを対応付ける</li>
|
|
|
394 <li>現在の Gears ではこの enum code 使って接続先の Code Gear を指定する</li>
|
|
16
|
395 </ul>
|
|
15
|
396
|
|
18
|
397 <pre lang="c"><code>enum Code {
|
|
|
398 Code1,
|
|
|
399 Code2,
|
|
|
400 Code3,
|
|
|
401 Exit,
|
|
|
402 };
|
|
|
403 </code></pre>
|
|
|
404
|
|
14
|
405
|
|
|
406 </div>
|
|
|
407 <div class='slide '>
|
|
|
408 <!-- _S9SLIDE_ -->
|
|
16
|
409 <h2 id="data-gear-">Data Gear の表現</h2>
|
|
|
410 <ul>
|
|
|
411 <li>使用する Data Gear は C の共用体と構造体を用いた表現をする</li>
|
|
|
412 <li>これを元に Gears OS は 必要な Data Gear を allocate する</li>
|
|
|
413 </ul>
|
|
|
414
|
|
|
415 <pre lang="c"><code>/* data Gear define */
|
|
|
416 union Data {
|
|
|
417 struct Time {
|
|
|
418 enum Code next;
|
|
|
419 double time;
|
|
|
420 } time;
|
|
|
421 struct LoopCounter {
|
|
|
422 int i;
|
|
|
423 } loopCounter;
|
|
|
424 ....
|
|
|
425 };
|
|
|
426 </code></pre>
|
|
|
427
|
|
|
428
|
|
|
429 </div>
|
|
|
430 <div class='slide '>
|
|
|
431 <!-- _S9SLIDE_ -->
|
|
|
432 <h2 id="code-gear--stub">Code Gear の stub</h2>
|
|
|
433 <ul>
|
|
18
|
434 <li>Data Gear にアクセスするにはContext を経由する</li>
|
|
|
435 <li>だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある</li>
|
|
|
436 <li>Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する</li>
|
|
|
437 <li>stub は一種の Meta Code Gear であるため、 CbC で自動生成される</li>
|
|
|
438 <li>このコードでは Array と LoopCounter が必要な code1 の stub を示している</li>
|
|
16
|
439 </ul>
|
|
|
440
|
|
|
441 <pre lang="c"><code>__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) {
|
|
|
442 ...
|
|
|
443 }
|
|
|
444
|
|
|
445 /* stub define */
|
|
|
446 __code code1_stub(struct Context* context) {
|
|
|
447 goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter);
|
|
|
448 }
|
|
|
449 </code></pre>
|
|
|
450
|
|
|
451
|
|
|
452 </div>
|
|
|
453 <div class='slide '>
|
|
|
454 <!-- _S9SLIDE_ -->
|
|
20
|
455 <h2 id="section-1">プロトタイプ の構成</h2>
|
|
14
|
456 <ul>
|
|
20
|
457 <li>今回は並列処理を行う機構の実装を行う</li>
|
|
|
458 <li>必要な要素は大きく5つ
|
|
14
|
459 <ul>
|
|
20
|
460 <li>Context</li>
|
|
|
461 <li>TaskQueue
|
|
|
462 <ul>
|
|
|
463 <li>実行される Task のリストを扱う</li>
|
|
|
464 </ul>
|
|
|
465 </li>
|
|
|
466 <li>Persistent Data Tree
|
|
|
467 <ul>
|
|
|
468 <li>Code Gear によって参照される Data Gear の管理を行う</li>
|
|
|
469 </ul>
|
|
|
470 </li>
|
|
21
|
471 <li>Worker
|
|
|
472 <ul>
|
|
|
473 <li>TaskQueue から Task を取得し、実行する</li>
|
|
|
474 </ul>
|
|
|
475 </li>
|
|
20
|
476 <li>TaskManager
|
|
|
477 <ul>
|
|
|
478 <li>Persistent Data Tree を監視し、 Task の依存関係を解決する</li>
|
|
|
479 </ul>
|
|
|
480 </li>
|
|
14
|
481 </ul>
|
|
|
482 </li>
|
|
|
483 </ul>
|
|
|
484
|
|
21
|
485 <p>※ TaskManager は今回未実装</p>
|
|
|
486
|
|
14
|
487
|
|
|
488 </div>
|
|
|
489 <div class='slide '>
|
|
|
490 <!-- _S9SLIDE_ -->
|
|
|
491 <h2 id="taskqueue">TaskQueue</h2>
|
|
|
492 <ul>
|
|
20
|
493 <li>Task Queue は Task のリストを扱う</li>
|
|
|
494 <li>すべての Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する</li>
|
|
14
|
495 <li>TaskQueue は 2つで Data Gear で表現される
|
|
|
496 <ul>
|
|
|
497 <li>先頭と末尾の要素を持った Queue 表す Data Gear</li>
|
|
20
|
498 <li>Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear</li>
|
|
14
|
499 </ul>
|
|
|
500 </li>
|
|
|
501 </ul>
|
|
|
502
|
|
17
|
503 <pre lang="c"><code>// Data Gear define
|
|
14
|
504 union Data {
|
|
|
505 struct Queue {
|
|
|
506 struct Element* first;
|
|
|
507 struct Element* last;
|
|
|
508 } queue;
|
|
|
509
|
|
|
510 struct Element {
|
|
|
511 struct Task* task;
|
|
|
512 struct Elemen* next;
|
|
|
513 } element
|
|
|
514 };
|
|
|
515 </code></pre>
|
|
|
516
|
|
|
517
|
|
|
518 </div>
|
|
|
519 <div class='slide '>
|
|
|
520 <!-- _S9SLIDE_ -->
|
|
|
521 <h2 id="taskqueueenqueue">TaskQueueの操作(Enqueue)</h2>
|
|
|
522 <ul>
|
|
|
523 <li>Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定</li>
|
|
18
|
524 <li>正しく最後の要素が変更できたことを CAS で 保証し、末尾の変更を行う必要がある</li>
|
|
14
|
525 </ul>
|
|
|
526
|
|
18
|
527 <pre lang="c"><code>__code putQueue3(struct Queue* queue, struct Element* new_element) {
|
|
14
|
528 struct Element* last = queue->last;
|
|
|
529
|
|
|
530 if (__sync_bool_compare_and_swap(&queue->last, last, new_element)) {
|
|
|
531 last->next = new_element;
|
|
|
532
|
|
18
|
533 goto exit();
|
|
14
|
534 } else {
|
|
18
|
535 goto putQueue3(queue, new_element);
|
|
14
|
536 }
|
|
|
537 }
|
|
|
538
|
|
|
539 </code></pre>
|
|
|
540
|
|
|
541
|
|
|
542 </div>
|
|
|
543 <div class='slide '>
|
|
|
544 <!-- _S9SLIDE_ -->
|
|
|
545 <h2 id="persistent-data-tree">Persistent Data Tree</h2>
|
|
|
546 <ul>
|
|
|
547 <li>Persistent Data Tree は Data Gear の管理を行う</li>
|
|
18
|
548 <li>TaskQueue と同じですべての Thread で共有される</li>
|
|
|
549 <li>Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ</li>
|
|
19
|
550 <li>木構造から読み出される Data Gear は Code Gear の Input Data Gear, 書き出すData Gear は Output Data Gear になる</li>
|
|
|
551 </ul>
|
|
|
552
|
|
|
553 <div style="text-align: center;">
|
|
20
|
554 <img src="./images/persistent_date_tree_2.svg" alt="message" width="800" />
|
|
19
|
555 </div>
|
|
|
556
|
|
|
557
|
|
|
558 </div>
|
|
|
559 <div class='slide '>
|
|
|
560 <!-- _S9SLIDE_ -->
|
|
|
561 <h2 id="persistent-data-tree-1">Persistent Data Tree</h2>
|
|
|
562 <ul>
|
|
|
563 <li>Persistent Data Tree は
|
|
|
564 <ul>
|
|
|
565 <li>Tree 自体を示す Data Gear</li>
|
|
|
566 <li>Node を示す Data Gear</li>
|
|
|
567 </ul>
|
|
|
568 </li>
|
|
14
|
569 </ul>
|
|
|
570
|
|
19
|
571 <p>を用いて木構造を表現する</p>
|
|
|
572
|
|
|
573 <pre lang="c"><code>union Data {
|
|
|
574 struct Tree {
|
|
|
575 struct Node* root;
|
|
|
576 } tree;
|
|
|
577 struct Node {
|
|
|
578 int key; // comparable data segment
|
|
|
579 union Data* value;
|
|
|
580 struct Node* left;
|
|
|
581 struct Node* right;
|
|
|
582 // need to balancing
|
|
|
583 enum Color {
|
|
|
584 Red,
|
|
|
585 Black,
|
|
|
586 } color;
|
|
|
587 } node;
|
|
|
588 };
|
|
|
589 </code></pre>
|
|
|
590
|
|
14
|
591
|
|
|
592 </div>
|
|
|
593 <div class='slide '>
|
|
|
594 <!-- _S9SLIDE_ -->
|
|
|
595 <h2 id="worker">Worker</h2>
|
|
|
596 <ul>
|
|
|
597 <li>Worker は TaskQueue から Task を取得して実行する</li>
|
|
19
|
598 </ul>
|
|
|
599
|
|
|
600 <table align="center">
|
|
|
601 <tbody>
|
|
|
602 <tr>
|
|
|
603 <td>
|
|
|
604 <div>
|
|
|
605 <img src="./images/worker.svg" alt="message" width="600" />
|
|
|
606 </div>
|
|
|
607 </td>
|
|
|
608 <td>
|
|
20
|
609 <ol>
|
|
19
|
610 <li> Worker は Task Queue から Task を取り出す(1. Dequeue Task)</li>
|
|
|
611 <li> 取り出した Task には Tree の key が入っているため Tree からその key に対応した Input Data Gear を読み込む(2. Read Data Gear) </li>
|
|
|
612 <li> Task に格納されている Code Gear を実行する </li>
|
|
|
613 <li> Code Gear を実行した結果、生成された Output Data Gear を Tree に書き出す(3.Write Data Gear) </li>
|
|
20
|
614 </ol>
|
|
19
|
615 </td>
|
|
|
616 </tr>
|
|
|
617 </tbody>
|
|
|
618 </table>
|
|
|
619
|
|
|
620 <ul>
|
|
14
|
621 <li>Task が完了したら次の Task を取得する</li>
|
|
|
622 </ul>
|
|
|
623
|
|
|
624
|
|
|
625 </div>
|
|
|
626 <div class='slide '>
|
|
|
627 <!-- _S9SLIDE_ -->
|
|
|
628 <h2 id="taskmanger">TaskManger</h2>
|
|
|
629 <ul>
|
|
|
630 <li>TaskManager は Task の依存関係の解決を行う</li>
|
|
18
|
631 <li>Thread の作成と停止も行う</li>
|
|
14
|
632 </ul>
|
|
|
633
|
|
21
|
634 <div style="text-align: center;">
|
|
|
635 <img src="./images/taskManager.svg" alt="message" width="800" />
|
|
|
636 </div>
|
|
14
|
637
|
|
|
638
|
|
|
639 </div>
|
|
|
640 <div class='slide '>
|
|
|
641 <!-- _S9SLIDE_ -->
|
|
20
|
642 <h2 id="section-2">プロトタイプの実行</h2>
|
|
14
|
643 <ul>
|
|
|
644 <li>今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った</li>
|
|
|
645 <li>これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった</li>
|
|
|
646 </ul>
|
|
|
647
|
|
|
648
|
|
|
649 </div>
|
|
|
650 <div class='slide '>
|
|
|
651 <!-- _S9SLIDE_ -->
|
|
20
|
652 <h2 id="gears-os--code-gear-">Gears OS で実行する Code Gear 例</h2>
|
|
14
|
653 <ul>
|
|
18
|
654 <li>プロトタイプのタスクの例題として Twice を実装した</li>
|
|
14
|
655 <li>Twice は与えられた整数配列を2倍にする例題である</li>
|
|
|
656 </ul>
|
|
|
657
|
|
|
658 <pre lang="c"><code>// Twice Code Gear
|
|
18
|
659 __code twice(struct LoopCounter* loopCounter, int index, int alignment, int* array) {
|
|
14
|
660 int i = loopCounter->i;
|
|
|
661
|
|
|
662 if (i < alignment) {
|
|
|
663 array[i+index*alignment] = array[i+index*alignment]*2;
|
|
|
664 loopCounter->i++;
|
|
|
665
|
|
18
|
666 goto twice(loopCounter, index, alignment, array);
|
|
14
|
667 }
|
|
|
668
|
|
|
669 loopCounter->i = 0;
|
|
|
670
|
|
18
|
671 goto exit();
|
|
14
|
672 }
|
|
|
673 </code></pre>
|
|
|
674
|
|
|
675
|
|
|
676 </div>
|
|
|
677 <div class='slide '>
|
|
|
678 <!-- _S9SLIDE_ -->
|
|
20
|
679 <h2 id="section-3">並列処理の確認</h2>
|
|
14
|
680 <ul>
|
|
18
|
681 <li>Twice を使用し、Gears OS が実際に並列処理されているかどうかの確認を行った</li>
|
|
|
682 <li>環境
|
|
14
|
683 <ul>
|
|
|
684 <li>Memory : 16GB</li>
|
|
|
685 <li>CPU : 6-core Intel Xeon 2.66GHZ x 2</li>
|
|
|
686 </ul>
|
|
|
687 </li>
|
|
17
|
688 <li>要素数 : 2^17 * 1000</li>
|
|
14
|
689 <li>分割数 : 640 タスク</li>
|
|
|
690 <li>1 Task 当たりの処理量 : 2^11 * 100 elements</li>
|
|
|
691 </ul>
|
|
|
692
|
|
|
693 <table border="1" align="center" width="50%">
|
|
|
694 <tbody>
|
|
|
695 <tr>
|
|
|
696 <td style="text-align: center;">Number of Processors</td>
|
|
|
697 <td style="text-align: center;">Time(ms)</td>
|
|
|
698 </tr>
|
|
|
699 <tr>
|
|
|
700 <td style="text-align: center;">1 CPU</td>
|
|
|
701 <td style="text-align: right;">1315</td>
|
|
|
702 </tr>
|
|
|
703 <tr>
|
|
|
704 <td style="text-align: center;">2 CPUs</td>
|
|
|
705 <td style="text-align: right;">689</td>
|
|
|
706 </tr>
|
|
|
707 <tr>
|
|
|
708 <td style="text-align: center;">4 CPUs</td>
|
|
|
709 <td style="text-align: right;">366</td>
|
|
|
710 </tr>
|
|
|
711 <tr>
|
|
|
712 <td style="text-align: center;">8 CPUs</td>
|
|
|
713 <td style="text-align: right;">189</td>
|
|
|
714 </tr>
|
|
|
715 <tr>
|
|
|
716 <td style="text-align: center;">12 CPUs</td>
|
|
|
717 <td style="text-align: right;">111</td>
|
|
|
718 </tr>
|
|
|
719 </tbody>
|
|
|
720 </table>
|
|
|
721
|
|
|
722 <ul>
|
|
18
|
723 <li>1cpu と 12cpu では 11.8 倍の向上が見られた</li>
|
|
14
|
724 </ul>
|
|
|
725
|
|
|
726
|
|
|
727 </div>
|
|
|
728 <div class='slide '>
|
|
|
729 <!-- _S9SLIDE_ -->
|
|
17
|
730 <h2 id="cerium-">Cerium との比較</h2>
|
|
|
731 <ul>
|
|
|
732 <li>Cerium は本研究室で開発していた並列プログラミングフレームワーク</li>
|
|
21
|
733 <li>Cerium では Task を依存関係に沿って実行することで並列実行を可能にする
|
|
17
|
734 <ul>
|
|
18
|
735 <li>本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することが出来ない</li>
|
|
17
|
736 <li>Gears OS の Task 中身は Code Gear になっており、必要な Input Data Gear が揃わない限り実行しないため、データの依存関係を保証できる</li>
|
|
|
737 </ul>
|
|
|
738 </li>
|
|
18
|
739 <li>Task には汎用ポインタとしてデータの受け渡しを行う
|
|
17
|
740 <ul>
|
|
18
|
741 <li>型情報がなく、型の検査を行うことが出来ない</li>
|
|
17
|
742 <li>Gears OS では 型情報をもつ Data Gear を定義</li>
|
|
|
743 </ul>
|
|
|
744 </li>
|
|
|
745 </ul>
|
|
14
|
746
|
|
|
747
|
|
|
748 </div>
|
|
|
749 <div class='slide '>
|
|
|
750 <!-- _S9SLIDE_ -->
|
|
20
|
751 <h2 id="os-">既存の OS への対応</h2>
|
|
15
|
752 <ul>
|
|
17
|
753 <li>Gears OS は従来の OS が行ってきたネットワーク管理、メモリ管理、並行制御などのメタな部分を Meta Code/Data Gear として定義</li>
|
|
20
|
754 <li>通常の Code Gear から必要な制御を Meta Code Gear で行うことで従来のOSが行ってきた制御の提供を行う</li>
|
|
17
|
755 </ul>
|
|
|
756
|
|
|
757
|
|
|
758 </div>
|
|
|
759 <div class='slide '>
|
|
|
760 <!-- _S9SLIDE_ -->
|
|
20
|
761 <h2 id="section-4">まとめ</h2>
|
|
17
|
762 <ul>
|
|
20
|
763 <li>Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った</li>
|
|
18
|
764 <li>依存関係のない Twice を実装し、並列処理が行えることを確認した</li>
|
|
15
|
765 </ul>
|
|
|
766
|
|
|
767
|
|
|
768 </div>
|
|
|
769 <div class='slide '>
|
|
|
770 <!-- _S9SLIDE_ -->
|
|
20
|
771 <h2 id="section-5">今後の課題</h2>
|
|
15
|
772 <ul>
|
|
16
|
773 <li>一般的に並列処理には依存関係が存在する
|
|
|
774 <ul>
|
|
20
|
775 <li>複雑な並列処理を実行できるようにするために Task Manager の実装を行い、 依存関係のある並列処理の例題を作成し、評価する</li>
|
|
16
|
776 </ul>
|
|
|
777 </li>
|
|
|
778 <li>GPUなどの他のプロセッサ演算に利用することが出来ない
|
|
|
779 <ul>
|
|
|
780 <li>Data Gear などのデータをGPUにマッピングするための機構が必要</li>
|
|
|
781 </ul>
|
|
|
782 </li>
|
|
|
783 <li>Gears OS でのデバック手法
|
|
|
784 <ul>
|
|
20
|
785 <li>継続はスタックを積まないため、スタックトレースを使わないデバック手法の考案</li>
|
|
16
|
786 <li>並列処理でのデバック手法も考案する必要がある</li>
|
|
|
787 </ul>
|
|
|
788 </li>
|
|
|
789 <li>型情報の検査
|
|
|
790 <ul>
|
|
18
|
791 <li>プログラムの正しさを保証するために Data Gear の情報を検査するシステムを Meta Computation として実装する</li>
|
|
|
792 </ul>
|
|
|
793 </li>
|
|
|
794 <li>Contextの動的生成
|
|
|
795 <ul>
|
|
|
796 <li>今は静的に自分で生成している</li>
|
|
|
797 <li>CbC 用の Runtime をつくり、 Context を動的に生成</li>
|
|
16
|
798 </ul>
|
|
|
799 </li>
|
|
15
|
800 </ul>
|
|
14
|
801 <!-- === end markdown block === -->
|
|
|
802 </div>
|
|
|
803
|
|
|
804
|
|
|
805 </div><!-- presentation -->
|
|
|
806 </body>
|
|
|
807 </html>
|
