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