Mercurial > hg > Papers > 2012 > sugi-prosym

comparison presen/alice-presen.ind @ 35:5f961785fb0c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add o2s5
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Tue, 08 Jan 2013 17:17:09 +0900
parents
children b7fb46ffac37
comparison
equal deleted inserted replaced
33:08e9d220c445 35:5f961785fb0c
1 <!DOCTYPE html>
2
3 <!--
4 Google HTML5 slide template
5
6 Authors: Luke Mahé (code)
7 Marcin Wichary (code and design)
8
9 Dominic Mazzoni (browser compatibility)
10 Charles Chen (ChromeVox support)
11
12 URL: http://code.google.com/p/html5slides/
13 -->
14
15 <html>
16 <head>
17 <title>Presentation</title>
18
19 <meta charset='utf-8'>
20 <script
21 src='./slides.js'></script>
22 </head>
23
24 <style>
25 /* Your individual styles here, or just use inline styles if that’s
26 what you want. */
27
28
29 </style>
30
31 <body style='display: none'>
32
33 <section class='slides layout-regular template-default'>
34
35 <!-- Your slides (<article>s) go here. Delete or comment out the
36 slides below. -->
37
38 <article>
39 <h1>
40 <font size="6">CodeSegmentとDataSegmentによるプログラミング手法</font>
41
42 </h1>
43 <p>
44 河野 真治<br>
45 杉本 優
46 </p>
47 琉球大学 並列信頼研究室
48 </article>
49
50 <article>
51 <h3>研究背景</h3>
52 <ul>
53 <p>本研究室では分散プログラミングに置いて、タスクをCode Segment、データをData Segmentという単位に分割して記述する方法を提唱している。</p>
54 <p>しかし、前述したプログラムをプログラマーが一から記述していくことは大変である。</p>
55 <p>そこで、本研究室の卒業生である赤嶺一樹氏が分散ネットフレームワークAliceのプロトタイプを作成した。</p>
56 <p>本研究では実際にAliceを利用して、水族館の例題を作成した。また、Federated Lindaとの性能比較を行った。そして、Aliceの問題点の洗い出し、APIの見直しを行った。</p>
57
58 </ul>
59 </article>
60
61 <article>
62 <h3>発表内容</h3>
63 <ul>
64 <li>Aliceの紹介
65 <li>プログラムの記述方法
66 <li>水族館の例題と性能評価
67 <li>まとめと課題
68 </ul>
69 </article>
70
71 <article>
72 <h3>Alice</h3>
73 <ul>
74 <p>Alice は本研究室で開発を行なっている分散タスク管理フレームワークである。</p>
75 <p>Cell用のOpen CL に似たTask管理用フレームワークCeriumと
76 Lindaを相互接続した分散フレームワークであるFederated Lindaの開発を通して得られた知見を生かされている。</p>
77 <ul>
78 </article>
79
80 <article>
81 <h3>Cerium</h3>
82 <ul>
83 <p>Ceriumは当研究室で開発を行なっている並列プログラミングフレームワークである。</p>
84 <p>CeriumではTaskを小さく分割して並列実行し、データ転送はパイプライン実行により隠される。</p>
85 <p>Taskには依存関係がありデータの依存関係がそのままTaskの依存関係になることが多い。</p>
86 <p>繰り返し使われるデータの管理が重要であり、実行時にわかるデータ構造間の依存関係がTaskを複雑にしている。</p>
87 </ul>
88 </article>
89
90 <article>
91 <h3>Data Segment API</h3>
92 <ul>
93 <p>Data Segmentは数値や文字などのデータを構造体的に保持するが、分散プログラムにおいてData Segmentの相互参照が問題になってくる。</p>
94 <p>AliceではData SegmentにユニークなKeyを持たせ、Key Value Storeとして扱っている。Key毎のキューがあり、Key毎に順に実行される。<br>
95 <div align="center">
96 <img src="images/dataSegment_key.png">
97 </div>
98
99 </ul>
100 </article>
101
102
103 <article>
104 <h3>Data Segment API</h3>
105 <ul>
106 <p>Data Segmentを管理するのが、Data Segment Manager
107 各ノード毎に、Local DS ManagerとRemote DS Managerが存在する。</p>
108 <p>Local DS Managerはノード固有のKey Value Storeであり、Remote DS Managerは他のノードのLocal DS Managerのproxyである。
109 AliceのTopology Managerが自動的に構成する。</p>
110 <div align="center">
111 <img src="images/lrds.png" width=500>
112 </div>
113 </ul>
114 </article>
115
116
117 <article>
118 <h3>Data Segment API</h3>
119 <ul>
120 以下が用意されているData Segment APIである。
121 <li>void put(String key, Value val)</li>
122 <li>void update(String key, Value val)</li>
123 <li>void peek(Receiver receiver, String key)</li>
124 <li>void take(Receiver receiver, String key)</li>
125 <p>これらを用いてデータの送受信を行う。</p>
126 </ul>
127 </article>
128
129 <article>
130 <h3>Data Segment API - put</h3>
131 <ul>
132 <li>データを追加する</li>
133 </ul>
134 <div align="center">
135 <img src="images/put.png" width=70%>
136 </div>
137 <ul>
138 <p>putを行うとデータがenqueueされる。</p>
139 <p>putするたびにKeyが持つindexがincrementされる。</p>
140 </ul>
141 </article>
142
143 <article>
144 <h3>Data Segment API - update</h3>
145 <ul><li>データを置き換える</li></ul>
146 <div align="center">
147 <img src="images/update.png" width=70%>
148 </div>
149 <ul>
150 putと異なる点は先頭データを削除し、データを追加する。
151 </ul>
152 </article>
153
154 <article>
155 <h3>Data Segment API - peek</h3>
156 <ul><li>データを取得する</li></ul>
157 <div align="center">
158 <img src="images/peek.png" width=50%><br>
159 </div>
160 <ul>
161 peekはデータを取得しreceiverに渡す。
162 </ul>
163 </article>
164
165 <article>
166 <h3>Data Segment API - peek</h3>
167 <div align="center">
168 <img src="images/peek1.png" width=60%><br>
169 </div>
170 <ul>
171 <p>要求したデータがない場合にはwaitListに登録する。</p>
172 データがput、updateされる際に要求したデータがあるかどうかを再びチェックする。
173
174 </ul>
175 </article>
176
177 <article>
178 <h3>Data Segment API - take</h3>
179 <ul><li>データを取得して取得されたデータはdequeueされる</li></ul>
180 <div align="center">
181 <img src="images/take.png" width=50%><br>
182 </div>
183 <ul>
184 <p>基本的な動作はpeekと同じである。</p>
185 <p>peekと異なる点は取得されたデータがdequeueされる。</p>
186 </ul>
187 </article>
188
189 <article>
190 <h3>Data Segmentの実装</h3>
191 <ul>
192 Data Segmentのデータ表現はMessagePackを使用。
193 </ul>
194 <ul><p>JavaにおけるMessagePackのデータ表現</p>
195 <li>一般的なJavaのクラスオブジェクト</li>
196 <li>MessagePack for JavaのValueオブジェクト</li>
197 <li>byte[]で表現されたバイナリ</li>
198 </ul>
199 <ul>
200 <p>Data Segment APIでは</p>
201 MessagePack for javaのValueオブジェクトを使用</p>
202 MessagePackのバイナリにシリアライズできる型のみで
203 構成されているため自己記述式のデータ形式
204 </ul>
205 </article>
206
207 <article>
208 <h3>Data Segmentの実装</h3>
209 <ul>
210 <p>Valueオブジェクトは通信に関わる際には、シリアライズ、デシリアライズを高速に行うことができる</p>
211 <img src="images/FishPoint.png" width=700><br>
212 ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを記述することが可能
213 </ul>
214 </article>
215
216 <article>
217 <h3>CodeSegment</h3>
218 <ul>
219 <li>Code Segmentはタスクのこと</li>
220 <li>ユーザーが記述する際にCode Segment内で使用する<br>Data Segmentの作成を記述</li>
221 <li>Input Data SegmentとOutput Data Segmentを作るAPI</li>
222 <li>必要なInput Data Segmentが揃った時に実行される</li>
223 </ul>
224 </article>
225
226 <article>
227 <h3>Input Data SegmentとOutput Data Segment</h3>
228 <ul>
229 <li>localかremoteを指定</li>
230 <li>Data Segmentに関連付けされているKEYを指定</li>
231 </ul>
232 </article>
233
234 <article>
235 <ul>
236 <h3>Data Segmentの例</h3>
237 <img src="images/SendWidth.png" width=600>
238 </ul>
239 </article>
240
241 <article>
242 <h3>Input Data Segmentの例</h3>
243 <ul>
244 <img src="images/ids.png" width=400><br>
245 Receiverの作成<br>
246 PEEK,TAKEのどちらかを選択
247 </ul>
248 <ul>
249 <img src="images/idsSetkey.png" width=600><br>
250 第1引数 マシン名<br>
251 第2引数 Data Segmentに関連付けられているKEY<br>
252 第3引数 index(指定しない場合は先頭データが取得される)<br>
253 </ul>
254 </article>
255
256 <article>
257 <h3>Output Data Segmentの例</h3>
258 <ul>
259 <img src="images/ods.png" width=400><br>
260 putかupdateのどちらかを選択
261 </ul>
262 <ul>
263 第1引数 マシン名<br>
264 第2引数 Data Segmentに関連付けるKEY<br>
265 第3引数 Data Segment<br>
266 </ul>
267 </article>
268
269 <article>
270 <h3>Code Segmentの実行方法</h3>
271 <ul>
272 <img src="images/StartCS.png" width=600><br>
273 </ul>
274 <ul>
275 AliceにはCのmainに相当するStart Code SegmentというCode Segmentが存在する。<br>
276 Start Code SegmentはInput Data Segmentが存在しない。
277 </ul>
278 </article>
279
280 <article>
281 <h3>Code Segmentの実行方法</h3>
282 <ul>
283 <img src="images/execute.png" width=600><br>
284 </ul>
285 <ul>
286 このStart Code Segmentをnewし、executeメソッドを呼ぶことでCode Segmentを実行することができる。
287 </ul>
288 </article>
289
290 <article>
291 <h3>Code Segmentの記述方法</h3>
292 <ul>
293 <img src="images/TestCodeSegment.png" width=600><br>
294 </ul>
295 ユーザがCode Segmentを記述する際にはCode Segmentを継承する。<br>
296 runの中に実際にさせたい処理を記述する。
297 </article>
298
299 <article>
300 <h3>Topology Manager</h3>
301 <ul>
302 Alice同士の接続トポロジーを管理する。<br>
303 トポロジーファイルを読み込み、参加を表明したクライアントに接続すべきクライアントのIPアドレスやポート番号、接続名を送る。
304 <div align="center">
305 <img src="images/topology.png" width=350>
306 </div>
307 </ul>
308 </article>
309
310 <article>
311 <h3>Topology Manager</h3>
312 <ul>
313 Topology Manager関連の通信は全て、Code Segmentで実装されている。
314 </ul>
315 </article>
316
317 <article>
318 <h3>トポロジーファイル</h3>
319 <ul>
320 <p>トポロジーファイルはDOT Languageと言う言語で記述される。</p>
321 DOT Languageはプレーンテキストを用いてデータ構造としてのグラフを表現するデータ記述言語の一つ。<br>
322 DOT Languageのグラフ構造を用いてTopology Node間の接続を表現する。<br>
323 </ul>
324 </article>
325
326 <article>
327 <h3>トポロジーファイルの記述方法</h3>
328 <ul>
329 <img src="images/topologyfile.png">
330 <p>dotコマンドを用いて、グラフの画像ファイルを生成することができるのでトポロジーが正しいか確認することができる。</p>
331
332 </ul>
333 </article>
334
335 <article>
336 <h3>トポロジーファイルの確認方法</h3>
337 <ul>
338 <p><strong>dot -T png ring.dot -o ring.png</strong></p>
339 <div align="center">
340 <img src="images/dot.png">
341 </div>
342 </ul>
343 </article>
344
345 <article>
346 <h3>水族館の例題</h3>
347 <ul>
348 <p>複数の魚が複数のディスプレイ上を移動する。</p>
349 <p>魚のうち一匹はクライアントが操作することができる。</p>
350 <p>トポロジーはツリー状に構成してある。</p>
351 </ul>
352 <div align="center">
353 <img src="images/aquarium.png" width=800>
354 </div>
355 </article>
356
357 <article>
358 <div align="center">
359 <img src="images/commnuication.png" width=600>
360 </div>
361 </article>
362
363 <article>
364 <h3>性能比較 - 実験概要</h3>
365 <ul>
366 AliceとFederated Linda で性能比較を行った。<br>
367 Ring型のトポロジーを構成、メッセージが100周する時間を計測。
368 1周あたりの平均時間を求めた。
369 <div align="center">
370 <img src="images/ringTest.png">
371 </div>
372 パケットのサイズは10byte,10Kbyte,100kbtyeで実験
373 </ul>
374 </article>
375
376 <article>
377 <h3>実験環境</h3>
378 <ul>
379 ブレードサーバー上の仮想マシンによる仮想クラスタ環境を用いて実験した。<br>
380 <p><strong>ブレードサーバー詳細</strong></p>
381 <table style="font:Osaka;text-align:right;" border="2" >
382 <tr>
383 <td>マシン台数</td>
384 <td>8台</td>
385 </tr>
386 <tr>
387 <td>CPU</td>
388 <td>Intel(R) Xeon(R) X5650 @ 2.67GHz</td>
389 </tr>
390 <tr>
391 <td>物理コア数</td>
392 <td>12</td>
393 </tr>
394 <tr>
395 <td>論理コア数</td>
396 <td>24</td>
397 </tr><tr>
398 <td>CPU キャッシュ</td>
399 <td>12MB</td>
400 </tr>
401 <tr>
402 <td>Memory</td>
403 <td>132GB</td>
404 </tr>
405 </table>
406
407 </ul>
408 </article>
409 <article>
410 <h3>実験環境</h3>
411 <ul>
412 <p><strong>仮想クラスタ詳細</strong></p>
413 <table style="font:Osaka;text-align:right;" border="2" >
414 <tr>
415 <td>マシン台数</td>
416 <td>48台</td>
417 </tr>
418 <tr>
419 <td>CPU</td>
420 <td>Intel(R) Xeon(R) X5650 @ 2.67GHz</td>
421 </tr>
422 <tr>
423 <td>物理コア数</td>
424 <td>2</td>
425 </tr>
426 <tr>
427 <td>論理コア数</td>
428 <td>4</td>
429 </tr><tr>
430 <td>CPU キャッシュ</td>
431 <td>12MB</td>
432 </tr>
433 <tr>
434 <td>Memory</td>
435 <td>8GB</td>
436 </tr>
437 </table>
438 </ul>
439 </article>
440
441 <article>
442 <h3>実験結果</h3>
443 <ul>
444 <strong>10byte</strong><br>
445 <img src="images/ring10B.png" width=650>
446 </ul>
447 </article>
448
449 <article>
450 <h3>実験結果</h3>
451 <ul>
452 <strong>10kbyte</strong><br>
453 <img src="images/ring10KB.png" width=650>
454 </ul>
455 </article>
456
457 <article>
458 <h3>実験結果</h3>
459 <ul>
460 <strong>100kbyte</strong>
461 <img src="images/ring100KB.png" width=650><br>
462 データ量が増えると差が縮まっている。これはここの通信の手間の影響が大きことを示している。
463 </ul>
464 </article>
465
466 <article>
467 <h3>評価と考察</h3>
468 <ul>
469 今回の実装はJavaによりCode SegmentとData Segmentに必要なAPIを洗い出すものだった。この実装でも問題をいくつか発見した。<br>
470 <p><strong>API</strong></p>
471 <li>Class継承したりData Segmentの作成にFactory objectを使うのはJavaを使う際の技術的な問題</li>
472 <li>JavaのObject指向な記述が全体を煩雑にしている部分がある</li>
473 <li>updateはData Segmentの競合的な更新に使われるべきだと思われる</li>
474 </ul>
475 </article>
476
477 <article>
478 <h3>評価と考察</h3>
479 <p><strong>SEDA</strong></p>
480 <ul>
481 <li>Federated Lindaに比べ遅い原因の一つはSEDA architectureのせいと思われる</li>
482 <li>SEDAはスループット重視の実装であり、多段パイプラインのせいでレスポンスが遅れてしまう</li>
483
484 </ul>
485 </article>
486
487 <article>
488 <h3>評価と考察</h3>
489 <ul>
490 <li>スレッドプールを使わないほうが、Ringの結果は良い</li>
491 <img src="images/notp.png" width=650><br>
492 </ul>
493 </article>
494
495 <article>
496 <h3>評価と考察</h3>
497 <p><strong>MessagePack</strong></p>
498 <ul>
499 <li>今回の実装では単純なMessageの転送時にもMessagePackのdecode/encodeをしているが、overheadになってしまうため、decode/encode抜きに直接操作できるほうが望ましい</li>
500 <li>Data Segmentの一部の修正をするたびにData Segmentが再構成されているがこれは望ましくない</li>
501 <li>AliceもCeriumのようにInput Data SegmentとOutput Data SegmentをswapするAPIがあるとよいと思われる</li>
502 </ul>
503 </article>
504
505
506 <article>
507 <h3>評価と考察</h3>
508 <p><strong>Key</strong></p>
509 <ul>
510 <li>分散実装においてはData Segmentの相互参照はKey経由が打倒であるが、並列実装では全てのData SegmentをKey Value Storeに格納するのは、性能的な問題を引き起こす</li>
511 <li>分散記述と並列記述を分ければ解決するが、2つの記述がかけ離れるのは好ましくない</li>
512 <li>本来Key Value storeは持続性を持たせる必要がある</li>
513 </ul>
514 </article>
515
516 <article>
517 <h3>評価と考察</h3>
518 <p><strong>Java</strong></p>
519 <ul>
520 <li>Data SegmentはCode Segmentがactiveの時のみメモリ上にあり、その最大値はActive Taskの量を見積もればよいのでAliceにGarbage Collectionの機能は必要ない</li>
521 <li>key Value Store 上のデータは決してGarbage Collectionの対象にはならないが、それがGarbage Collectionに負荷をかける結果となるためAliceとJavaの相性は悪い</li>
522 </ul>
523 </article>
524
525 <article>
526 <h3>評価と考察</h3>
527 <p><strong>拡張性</strong></p>
528 <ul>
529 <li>分散アプリケーションのプロトコルは常に変更されるため、Aliceもそれに対応する必要がある</li>
530 <li>Keyとトポロジーマネージャーをプロトコル毎に別に用意すれば複数のプロトコルを同時に走らせることが可能</li>
531 <li>Data SegmentとCode Segmentの結びつきは弱いため、Data Segmentに余計な値がある場合、値が足りない場合に適切な値を設定することで古いCode Segmentを変更するとこなしにプロトコルを拡張できる</li>
532 </ul>
533 </article>
534
535 <article>
536 <h3>まとめと課題</h3>
537 <ul>
538 <p>今回Code SegmentとData Segmentによる並列分散フレームワークのJavaによる実装を示した。実装でしかえられない知見を得ることができた。</p>
539 <p>今回Javaによる実装を行ったがJavaがAliceの実装に不向きであるということもわかった。</p>
540 <p>
541 <li>Code Segment/Data Segmentを見たコンパイラ的アプローチ</li>
542 <li>実行時最適化</li>
543 <li>CbCによる実装</li>
544 などが有効、効果的だと思われる。</p>
545 <p>今回はノード内の並列実行やGPGPUによる並列実行などは考慮していない。将来的にそれを含め実装をしていきたい。</p>
546 </ul>
547 </article>
548
549 </Section>
550 </body>
551 </html>