16
|
1 <?xml version="1.0" encoding="utf-8"?>
|
|
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
|
|
3 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
|
4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
|
|
5 <head>
|
|
6 <title>DataSegment API を用いた分散フレームワークの設計</title>
|
|
7 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
|
|
8 <meta name="copyright" content="Copyright © 2010 Kazuki AKAMINE" />
|
|
9 <meta name="font-size-adjustment" content="-1" />
|
|
10 <link rel="stylesheet" href="./res/w3c-blue2.css"
|
|
11 type="text/css" media="screen, projection, print" />
|
|
12 <script src="./res/slidy.js" type="text/javascript">
|
|
13 </script>
|
|
14 </head>
|
|
15 <body>
|
|
16 <!-- this defines the slide background -->
|
|
17
|
|
18 <div class="background">
|
|
19 <div class="header">
|
|
20 <!-- sized and colored via CSS -->
|
|
21 </div>
|
|
22 <!-- hidden style graphics to ensure they are saved with other content -->
|
|
23 <img class="hidden" src="./res/bullet.png" alt="" />
|
|
24 <img class="hidden" src="./res/fold.bmp" alt="" />
|
|
25 <img class="hidden" src="./res/unfold.bmp" alt="" />
|
|
26 <img class="hidden" src="./res/fold-dim.bmp" alt="" />
|
|
27 <img class="hidden" src="./res/nofold-dim.bmp" alt="" />
|
|
28 <img class="hidden" src="./res/unfold-dim.bmp" alt="" />
|
|
29 <img class="hidden" src="./res/bullet-fold.gif" alt="" />
|
|
30 <img class="hidden" src="./res/bullet-unfold.gif" alt="" />
|
|
31 <img class="hidden" src="./res/bullet-fold-dim.gif" alt="" />
|
|
32 <img class="hidden" src="./res/bullet-nofold-dim.gif" alt="" />
|
|
33 <img class="hidden" src="./res/bullet-unfold-dim.gif" alt="" />
|
|
34
|
|
35 <div class="footer">
|
|
36 <!-- modify the following text as appropriate -->
|
|
37 Presentation Name<br />
|
|
38 Event, Location, Month Year
|
|
39 </div>
|
|
40 </div>
|
|
41
|
|
42 <div class="slide cover">
|
|
43 <div class="header">
|
|
44 <div class="block">
|
|
45 <h1>DataSegment API を用いた分散フレームワークの設計</h1>
|
|
46 <div class="name">琉球大学理工学研究科 情報工学専攻 並列信頼研 M2 赤嶺一樹</div>
|
|
47 </div>
|
|
48 </div>
|
|
49 </div>
|
|
50
|
|
51 <div class="slide">
|
|
52 <h1>研究目的</h1>
|
|
53 <p class="subhead">スケーラブルな分散プログラミングモデルの提案</p>
|
|
54 <ul>
|
|
55 <li>ブロードバンド環境やモバイル端末の普及により、ネットワーク上におけるサービスの巨大化は必至である</li>
|
|
56 <li>スケーラビリティ(サービスの大きさが増えてもリソースの追加のみでサービスの質を維持できること)を備えたプログラムを作成するためには、いろいろなプロトコルを提案し、実装し、検証していく必要がある</li>
|
18
|
57 <li>提案したプロトコルを<strong>シンプルに</strong>実験できるフレームワークが求められている</li>
|
16
|
58 </div>
|
|
59
|
|
60 <div class="slide">
|
|
61 <h1>DataSegment API</h1>
|
|
62 <p class="subhead">DataSegment API を用いた分散フレームワーク</p>
|
|
63 <div style="float: left; width: 55%;">
|
|
64 <ul>
|
|
65 <li>分散処理を CodeSegment と呼ばれる処理単位で記述し、そこで用いられるデータを DataSegment と呼ばれるデータ単位にまとめる。</li>
|
17
|
66 <li>必要な DataSegment を CodeSegment に記述していくことで、それらに依存関係が生まれ、自明に実行順序が決まる。</li>
|
16
|
67 <li>このフレームワークを設計するにあたって、 Federated Linda の実装から得られた見地が非常に役立った。</li>
|
|
68 <li>まず、 Federated Linda について紹介する。</li>
|
|
69 </ul>
|
|
70 </div>
|
|
71 <img src="img/csds.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
|
|
72 </div>
|
|
73
|
|
74 <div class="slide">
|
17
|
75 <h1>Federated Linda</h1>
|
16
|
76 <p class="subhead">Federated Linda とは</p>
|
|
77 <div style="float: left; width: 55%;">
|
|
78 <ul>
|
|
79 <li>本研究室では、分散フレームワーク Federated Linda の開発を行なってきた。</li>
|
|
80 <li>当初、並列言語 Linda を用いてアクセスできる Tuplespace を実装し、ネットワークゲームの通信ライブラリとして使用して来た。</li>
|
17
|
81 <li>それでは、クライアントが増えれば増えるほど通信がサーバー側に一極集中するため、スケールアウトできないという問題が発生した。</li>
|
16
|
82 </ul>
|
|
83 </div>
|
|
84 <img src="img/game.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
|
|
85 </div>
|
|
86
|
|
87 <div class="slide">
|
17
|
88 <h1>Federated Linda</h1>
|
16
|
89 <p class="subhead">Linda とは</p>
|
|
90 <div style="float: left; margin-left: 2em; width: 59%;">
|
|
91 <p>
|
17
|
92 Linda は、以下のAPIを用いてタプルスペース上のデータの更新を行う。
|
16
|
93 </p>
|
|
94 <table>
|
|
95 <tr>
|
|
96 <th>in(id)</th>
|
|
97 <td>データをタプルから取り出す<br>タプルにデータは残らない</td>
|
|
98 </tr>
|
|
99 <tr>
|
|
100 <th>rd(id)</th>
|
|
101 <td>データをタプルから取り出す<br>タプルにデータが残る</td>
|
|
102 </tr>
|
|
103 <tr>
|
|
104 <th>out(id,data)</th>
|
|
105 <td>データをタプルへ書き込む</td>
|
|
106 </tr>
|
|
107 </table>
|
|
108 </div>
|
|
109 <img src="./img/linda_server.png" style="display: block; width: 27%; margin-right: 10%; float: right;"/>
|
|
110 </div>
|
|
111
|
|
112 <div class="slide">
|
17
|
113 <h1>Federated Linda</h1>
|
16
|
114 <p class="subhead">Federated Linda とは</p>
|
|
115 <div style="display: block; float: left; width: 60%;">
|
|
116 <p>
|
17
|
117 タプルスペースを複数個つなげて、タプルの伝搬を基にデータを共有するモデルである。
|
16
|
118 </p>
|
|
119 <ul>
|
|
120 <li>タプルスペース間には データの伝搬などを管理する Protocol Engine と呼ばれるプログラムが存在</li>
|
|
121 <li>しかしタプルスペースと Protocol Engine は別プロセスであるため、同一サーバー上であってもソケットによる接続が必要だった。
|
|
122 </li>
|
|
123 </ul>
|
|
124 </div>
|
|
125 <img src="./img/prefedlinda.png" style="display: block; width: 37%; margin: auto; float: right; margin-right: 3%; margin-top: 2%;"/>
|
|
126 </div>
|
|
127
|
|
128 <div class="slide">
|
17
|
129 <h1>Federated Linda</h1>
|
16
|
130 <p class="subhead">Meta Engine とは</p>
|
|
131 <div style="display: block; float: left; width: 60%;">
|
|
132 <ul>
|
|
133 <li>Meta Engine と呼ばれる Protocol Engine の代替となるプログラムを、タプルスペースと同プロセス上に設置</li>
|
|
134 <li><strong>直接タプルスペースにアクセス可能になった</strong></li>
|
18
|
135 <li>ここまでが先行研究</li>
|
16
|
136 </ul>
|
|
137 </div>
|
|
138 <img src="./img/metafedlinda.png" style="display: block; width: 37%; margin: auto; float: right; margin-right: 3%; margin-top: 2%;"/>
|
|
139 </div>
|
|
140
|
|
141 <div class="slide">
|
17
|
142 <h1>Federated Linda の問題点</h1>
|
16
|
143 <p class="subhead">分散アプリケーションの3大構成要素</p>
|
|
144 <div style="display: block; float: left; width: 90%;">
|
|
145 <ul>
|
|
146 <li><strong>Configuration</strong></li>
|
|
147 <ul>
|
|
148 <li>各ノードの接続やルーティングを行う</li>
|
|
149 </ul>
|
|
150 <li><strong>Protocol Engine</strong></li>
|
|
151 <ul>
|
|
152 <li>Database へアクセスし、他のノードにデータを伝搬する</li>
|
|
153 </ul>
|
|
154 <li><strong>Database</strong></li>
|
|
155 <ul>
|
|
156 <li>通信した内容や計算結果などの各種データの保存領域</li>
|
|
157 </ul>
|
|
158 </ul>
|
|
159 <ul>
|
|
160 <li>しかし、 Federated Linda では Configuration も Protocol Engine 内で記述する必要があった。</li>
|
17
|
161 <li><strong>Protocol Engine の複雑化を招いていた</strong></li>
|
16
|
162 </ul>
|
|
163 </div>
|
|
164 </div>
|
|
165
|
17
|
166 <div class="slide">
|
|
167 <h1>Federated Linda の問題点</h1>
|
|
168 <p class="subhead">Protocol Engine の実行方法</p>
|
|
169 <ul>
|
18
|
170 <li><strong>Polling based</strong></li>
|
17
|
171 <ul>
|
|
172 <li>メインループで定期的に Protocol Engine を実行し、 Tuplespace からデータを取得し、確認する。 </li>
|
|
173 <li>通信が発生する度、記述した Tuple へのアクセスが発生する</li>
|
|
174 </ul>
|
18
|
175 <li><strong>Callback function based</strong></li>
|
17
|
176 <ul>
|
|
177 <li>とある Tuple が更新される度にその Tuple に設定された Callback function が実行される。</li>
|
|
178 <li>その Tuple が更新された時に適切に呼び出される。</li>
|
|
179 <li>Callback function がツリー状に連鎖されるため、プログラマがツリーを管理する必要がある。</li>
|
18
|
180 <li>コードをシーケンシャルに読めない。</li>
|
|
181 </ul>
|
|
182 </ul>
|
|
183 </div>
|
|
184
|
|
185 <div class="slide">
|
|
186 <h1>DataSegment API を用いた新設計</h1>
|
|
187 <p class="subhead">Geometric Routing</p>
|
|
188 <ul>
|
|
189 <li>分散アプリケーションにおいて Configuration が複雑になるという問題</li>
|
|
190 <li>具体的には <strong>Connection</strong> と <strong>Routing</strong></li>
|
|
191 <li>接続の自由度が高いと、記述するコード量が増えるため、トポロジーを固定的なものに限定することで簡単化</li>
|
|
192 <li>予めトポロジーを構成するロジックを別に用意しておく</li>
|
|
193 <ul>
|
|
194 <li>Ring</li>
|
|
195 <li>Tree</li>
|
|
196 <li>Mesh</li>
|
|
197 <li>etc...</li>
|
17
|
198 </ul>
|
|
199 </ul>
|
|
200 </div>
|
|
201
|
18
|
202 <div class="slide">
|
|
203 <h1>DataSegment API を用いた新設計</h1>
|
|
204 <p class="subhead">Geometric Routing - Connection</p>
|
|
205 <ul>
|
|
206 <li>参加するサーバーのリストとトポロジーを参加するサーバー全体に渡す。</li>
|
|
207 <li>個々のサーバーは、与えられたトポロジーに基づいて、接続を張る。</li>
|
|
208 <li>接続したサーバーには分かりやすい GeoAddress でアクセスできる。</li>
|
|
209 <li>ex) Ring Topology の場合、 RING_RIGHT 、 RING_LEFT などのアクセス可能な Address が得られる。</li>
|
|
210 <li>ex) Hypercube Topology なら、 HC_0010 、 HC_0110 など。</li>
|
|
211 </ul>
|
|
212 </div>
|
16
|
213
|
18
|
214 <div class="slide">
|
|
215 <h1>DataSegment API を用いた新設計</h1>
|
|
216 <p class="subhead">DataSegment API を用いた分散フレームワーク</p>
|
|
217 <div style="float: left; width: 55%;">
|
|
218 <ul>
|
|
219 <li>分散処理を CodeSegment と呼ばれる処理単位で記述し、そこで用いられるデータを DataSegment と呼ばれるデータ単位にまとめる。</li>
|
|
220 <li>必要な DataSegment を CodeSegment に記述していくことで、それらに依存関係が生まれ、自明に実行順序が決まる。</li>
|
|
221 </ul>
|
|
222 </div>
|
|
223 <img src="img/csds.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
|
|
224 </div>
|
16
|
225
|
|
226 <div class="slide">
|
18
|
227 <h1>DataSegment API を用いた新設計</h1>
|
|
228 <p class="subhead">DataSegment の型</p>
|
16
|
229 <ul>
|
18
|
230 <li>Federated Linda では、 Tuple の型は単なる byte[] であり、内部のデータ構造を自分で決める必要があった。</li>
|
16
|
231 <ul>
|
18
|
232 <li>バイトオーダー</li>
|
|
233 <li>浮動小数点</li>
|
|
234 <li>構造体</li>
|
|
235 </ul>
|
|
236 <li>DataSegment はシリアライズライブラリ MessagePack で扱えるフォーマット(like JSON)で型付けを行う。</li>
|
|
237 <li>list や hash のサポート</li>
|
|
238 <li>データがシリアライズ可能になるため、リモートへのデータ転送も容易に。</li>
|
|
239 </ul>
|
|
240 </div>
|
|
241
|
|
242 <div class="slide">
|
|
243 <h1>DataSegment API を用いた新設計</h1>
|
|
244 <p class="subhead">DataSegment の API</p>
|
|
245 <ul>
|
|
246 <li>DataSegment には以下の API が用意されている</li>
|
|
247 <ul>
|
|
248 <li>create</li>
|
|
249 <li>read</li>
|
|
250 <li>update</li>
|
|
251 <li>delete</li>
|
16
|
252 </ul>
|
|
253 </ul>
|
|
254 </div>
|
|
255
|
|
256 <div class="slide">
|
18
|
257 <h1>DataSegment API を用いた新設計</h1>
|
|
258 <p class="subhead">DataSegment の表現</p>
|
|
259 <div style="float: left; width: 55%;">
|
16
|
260 <ul>
|
18
|
261 <li>DataSegment はデータ型と ID で表現される。</li>
|
|
262 <li>データ型は MessagePack で表現できる構造体の名前</li>
|
|
263 <li>ID は <strong>GeoAddress</strong> と <strong>LocalAddress</strong> の2つの部分に分けて表現される。</li>
|
16
|
264 </ul>
|
|
265 </div>
|
18
|
266 <img src="img/datasegment.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
|
16
|
267 </div>
|
|
268
|
|
269 <div class="slide">
|
18
|
270 <h1>DataSegment API を用いた新設計</h1>
|
|
271 <p class="subhead">DataSegment の表現 - GeoAddress</p>
|
|
272 <div style="float: left; width: 55%;">
|
|
273 <ul>
|
|
274 <li>GeoAddress はトポロジー上のデータの所在を示す。</li>
|
|
275 <ul>
|
|
276 <li><strong>Persistent</strong></li>
|
|
277 <ul>
|
|
278 <li>KVS 上にある DataSegment</li>
|
|
279 </ul>
|
|
280 <li><strong>Remote</strong></li>
|
|
281 <ul>
|
|
282 <li>他のサーバー上にある DataSegment</li>
|
|
283 </ul>
|
|
284 <li><strong>Local</strong></li>
|
|
285 <ul>
|
|
286 <li>自サーバー上にある DataSegment</li>
|
|
287 </ul>
|
|
288 </ul>
|
|
289 </ul>
|
16
|
290 </div>
|
18
|
291 <img src="img/datasegment.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
|
16
|
292 </div>
|
|
293
|
18
|
294 <div class="slide">
|
|
295 <h1>DataSegment API を用いた新設計</h1>
|
|
296 <p class="subhead">DataSegment の表現 - LocalAddress</p>
|
|
297 <div style="float: left; width: 55%;">
|
|
298 <ul>
|
|
299 <li>LocalAddress は、自サーバー上の所在を表すアドレスである。</li>
|
|
300 </ul>
|
|
301 </div>
|
|
302 <img src="img/datasegment.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
|
|
303 </div>
|
16
|
304
|
|
305
|
|
306 <div class="slide">
|
18
|
307 <h1>DataSegment API を用いた新設計</h1>
|
|
308 <p class="subhead">Protocol Engine の代わりに CodeSegment を利用</p>
|
|
309 <div style="float: left; width: 55%;">
|
|
310 <ul>
|
|
311 <li>Federated Linda における Protocol Engine は、 Callback function で記述し、その接続を管理する機構がなかった。</li>
|
|
312 <li>シングルスレッドでつくられているため、 Protocol Engine の並列実行ができなかった。</li>
|
|
313 </ul>
|
|
314 </div>
|
|
315 <img src="img/dsandcs.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
|
16
|
316 </div>
|
18
|
317
|
|
318 <div class="slide">
|
|
319 <h1>DataSegment API を用いた新設計</h1>
|
|
320 <p class="subhead">Protocol Engine の代わりに CodeSegment を利用</p>
|
|
321 <div style="float: left; width: 55%;">
|
|
322 <ul>
|
|
323 <li>新設計では、 Protocol Engine に代わり、 CodeSegment という単位で処理を記述する。</li>
|
|
324 <li>CodeSegment は InputDataSegment と OutputDataSegment それぞれのリストを持っている。</li>
|
|
325 <li>InputDataSegment は CodeSegment が利用するデータ、 OutputDataSegment は CodeSegment が書きだすデータのことである。</li>
|
|
326 </ul>
|
|
327 </div>
|
|
328 <img src="img/dsandcs.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
|
|
329 </div>
|
|
330
|
|
331 <div class="slide">
|
|
332 <h1>DataSegment API を用いた新設計</h1>
|
|
333 <p class="subhead">CodeSegment の利用方法</p>
|
|
334 <div style="float: left; width: 55%;">
|
|
335 <ul>
|
|
336 <li>InputDataSegment と OutputDataSegment の ID を指定</li>
|
|
337 <li>OutputDataSegment の指定された ID が存在しない場合は新しく create を行う。</li>
|
|
338 <li>存在する ID だった場合は、 update を行う。</li>
|
|
339 </ul>
|
|
340 </div>
|
|
341 <img src="img/dsandcs.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
|
16
|
342 </div>
|
|
343
|
|
344 <div class="slide">
|
18
|
345 <h1>DataSegment API を用いた新設計</h1>
|
|
346 <p class="subhead">CodeSegment の利用方法</p>
|
|
347 <div style="float: left; width: 55%;">
|
|
348 <ul>
|
|
349 <li>OutputDataSegment が Remote サーバー上に存在する場合は、 Local のバッファーに書き出し、転送する CodeSegment を呼び出すことで表現できる。</li>
|
|
350 </ul>
|
16
|
351 </div>
|
18
|
352 <img src="img/remoteds.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
|
16
|
353 </div>
|
|
354
|
|
355 <div class="slide">
|
18
|
356 <h1>DataSegment API を用いた新設計</h1>
|
|
357 <p class="subhead">CodeSegment の利用方法</p>
|
|
358 <div style="float: left; width: 55%;">
|
16
|
359 <ul>
|
18
|
360 <li>TaskManager に CodeSegment を登録する。</li>
|
|
361 <li>TaskManager は必要な InputDataSegment が揃った CodeSegment を Executor に投げる。</li>
|
16
|
362 </ul>
|
|
363 </div>
|
18
|
364 <img src="img/dsandcs.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
|
16
|
365 </div>
|
|
366
|
|
367 <div class="slide">
|
18
|
368 <h1>DataSegment API を用いた新設計</h1>
|
|
369 <p class="subhead">競合的な DataSegment の書き出し</p>
|
16
|
370 <ul>
|
18
|
371 <li>DataSegment の update 方法にはいくつか種類がある。</li>
|
|
372 <li><strong>FIFO</strong></li>
|
|
373 <ul>
|
|
374 <li>実行された順に update する</li>
|
|
375 </ul>
|
|
376 <li><strong>Priority</strong></li>
|
|
377 <ul>
|
|
378 <li>優先順位が高いものが update する</li>
|
|
379 </ul>
|
|
380 <li><strong>Queueing</strong></li>
|
|
381 <ul>
|
|
382 <li>上書き update せずに書きこみを Queue に格納して順番に取り出す</li>
|
|
383 </ul>
|
16
|
384 </ul>
|
|
385 </div>
|
|
386
|
|
387 <div class="slide">
|
|
388 <h1>まとめと今後の課題</h1>
|
|
389 <ul>
|
18
|
390 <li>本研究では、本研究室で開発しているマルチコア向け並列フレームワーク Cerium の新設計のアイディアを分散フレームワークに応用した。</li>
|
|
391 <li>実際に実装して、実験してみないと分からないことが多い。</li>
|
|
392 <li><strong>頑張って実装します。</strong></li>
|
|
393 </ul>
|
|
394 </div>
|
|
395
|
|
396 <div class="slide">
|
|
397 <h1>まとめと今後の課題</h1>
|
|
398 <p class="subhead">実装に用いる言語の使い勝手</p>
|
|
399 <ul>
|
|
400 <li><strong>Java, Scala</strong></li>
|
|
401 <ul>
|
|
402 <li>Java や Scala には、 java.util.concurrent などの並列処理用のライブラリが充実しているため、実装が比較的容易。</li>
|
|
403 <li>Scala は言語レベルで並列処理を記述できる。(Actor を使ったメッセージ交換)</li>
|
|
404 </ul>
|
|
405 <li><strong>CbC</strong></li>
|
|
406 <ul>
|
|
407 <li>本研究室で開発している CbC (引数付き goto による継続ベースのC言語拡張)を使えば、 goto で CodeSegment 同士の繋がりを記述できる。</li>
|
|
408 <li>しかし、並列処理サポートがまだなため、 TaskManager などの実行カーネルからまずは作らなくてはならない。</li>
|
|
409 </ul>
|
16
|
410 </ul>
|
|
411 </div>
|
|
412
|
|
413
|
|
414 <!-- <div class="slide"> -->
|
|
415 <!-- <h1>ご清聴ありがとうございました</h1> -->
|
|
416 <!-- <img src="./img/nadeko.png" style="display: block; width: 80%; margin: auto"/> -->
|
|
417 <!-- </div> -->
|
|
418
|
|
419 </body>
|
|
420 </html>
|