comparison presen/alice-presen.ind @ 40:bb43d09406e1

final
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Fri, 11 Jan 2013 15:15:59 +0900
parents fcf3b09ef1a3
children
comparison
equal deleted inserted replaced
39:fcf3b09ef1a3 40:bb43d09406e1
8 8
9 分散プログラミング用のFederated Lidna 9 分散プログラミング用のFederated Lidna
10 並列プログラミング用のCerium 10 並列プログラミング用のCerium
11 11
12 これらの経験から並列分散を統一的に扱えるプログラミングフレームワークを考えたい。 12 これらの経験から並列分散を統一的に扱えるプログラミングフレームワークを考えたい。
13
14 そこで、
15
16 data segment と code segment で書くというのを考えた
17 Java で実装して評価した
13 18
14 --並列分散フレームワークには何が求められるのか 19 --並列分散フレームワークには何が求められるのか
15 20
16 並列実行単位の記述 21 並列実行単位の記述
17 プロトコルの記述 22 プロトコルの記述
18 実用的な実装 23 実用的な実装
24 高い対障害性
25 Scalability
19 実験環境の用意 26 実験環境の用意
27 Version up への対応
20 多言語対応 28 多言語対応
21 検証や証明への対応 29 検証や証明への対応
22 30
23 --Federated Linda 31 --Federated Linda
24 32
25 データの塊である Tuple を使って通信するフレームワーク 33 データの塊である Tuple を使って通信するフレームワーク
26 34
27 in Tuple を取り出す 35 in Tuple を取り出す
28 out Tuple 書きだす 36 out Tuple 書きだす
29 37
38 in, out で待ち合わせを行う
39
30 --Federated Linda の Pros and Cons 40 --Federated Linda の Pros and Cons
31 41
42 in/out のAPIさえあれば良いので、言語独立 (良)
43
44 Tuple のキーが文字列でわかりやすい (良)
45
46 切断に強い (良)
47
48 記述部分がスパゲティになりやすい (悪)
49
50 call back を使うと、さらにダメな記述に (悪)
51
52 --Linda の だめな記述の例
53
54 left.in(Up, new PSXCallback() {public void callback(ByteBuffer reply) {
55 if (debug) System.out.println("Up from left at"+nodeId);
56 left.in(Up,this);
57 leftWaiter.add(reply);
58 checkSend(ml);
59 }
60
32 --Cerium 61 --Cerium
33 62
34 Task 単位で並列実行するツール 63 Task 単位で並列実行するツール
35 64
65 Task を作って scheduler に投入
66
67 Task のデータは暗黙に通信される
68
69 Open CL 、Spurs Engine などの実装がある
70
36 --Cerium の Pros and Cons 71 --Cerium の Pros and Cons
37 72
73 Task は短く単純になる (良)
74
75 アセンブラ的なので性能は出やすい (良)
76
77 Task の依存関係は自分で管理 (悪)
78
79 データ構造は基本的に配列になりやすい (悪)
80
81 Task 管理部分が極めて複雑になる (悪)
82
83 --Cerium の だめな記述の例
84
85 {
86 int i = half_num-1;
87
88 if (s->bsort[i]) manager->free_htask(s->bsort[i]);
89 s->bsort[i] = manager->create_task(QUICK_SORT,
90 (memaddr)&s->data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num,
91 (memaddr)&s->data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num);
92 s->bsort[i]->flip();
93 s->bsort[i]->set_cpu(GPU_0);
94 s->bsort[i]->set_param(0,(memaddr)last_half_block_num);
95 }
96
97 for (int i = 0; i < half_num; i++) {
98 s->bsort[i]->wait_for(s->fsort[i]);
99 s->bsort[i]->wait_for(s->fsort[i+1]);
100 s->bsort[i]->no_auto_free();
101 s->bsort[i]->spawn();
102 }
103
104
105 --Linda と Cerium の良いとこ取りをしたい
106
107 Task 依存は、Tuple の依存で決まる
108
109 コードをTaskに分割する
110 Code Segment
111
112 データをTupleに分割する
113 Data Segment
114
115 Code と Data は双対になるはず
116
38 --Data segment と Code Segment 117 --Data segment と Code Segment
39 118
119 Code segment には input data segment と output data segment がある
120
121 <center><img src="images/reconnection.jpg"></center>
122
40 --Java Implmentation : Alice 123 --Java Implmentation : Alice
41 124
125 data segment は key (strig) でアクセスされる
126
127 input data segment は書き込みを待つ
128
129 --Local / Remote data segment Manager
130
131 Data Segmentを管理するのが、Data Segment Manager 各ノード毎に、Local DS ManagerとRemote DS Managerが存在する。
132
133 Local DS Managerはノード固有のKey Value Storeであり、Remote DS Managerは他のノードのLocal DS Managerのproxyである。
134
135 <center><img src="images/lrds.png"></center>
136
42 --CS/DS API 137 --CS/DS API
43 138
44 --Alice Architecture 139 input data segment の作成 (PEEKとTAKE)
45 140 public Receiver ds1 = ids.create(CommandType.TAKE);
46 --Sample Application 141 key の設定
142 ds1.setKey("finish");
143 output data segment の書き出し (put と update)
144 ods.put("local", "finish", ValueFactory.createNilValue());
145
146 これらを用いてデータの送受信を行う。
147
148 --Data segment の型
149
150 MessagePack を使用すると、そのままオブジェクトを data segment に使える
151
152 import org.msgpack.annotation.Message;
153 @Message
154 public class FishPoint {
155 public float x = 0.0f;
156 public float y = 0.0f;
157 public float z = 0.0f;
158 }
159
160
161 --Example
162
163 public class SendWidth extends CodeSegment {
164 Receiver width = ids.create(CommandType.PEEK);
165 @Override
166 public void run() {
167 int width = this.width.asInteger();
168 ods.put("parent", "widths", width);
169 System.out.println("send widths: " + width);
170 SendWidth cs = new SendWidth();
171 cs.width.setKey("local", "width", this.width.index);
172 }
173 }
174
175
176 --Sample Application 水族館の例題
177
178 複数の魚が複数のディスプレイ上を移動する。
179
180 魚のうち一匹はクライアントが操作することができる。
181
182 トポロジーはツリー状に構成してある。
183 <center><img src="images/aquarium.png"></center>
184
185 --CS/DS Java 版 Alice
186
187 Java で SEDA をしようして実装
188
189 MessagePack を使って Marshaling
190
191 --SEDA
192
193 Thread pool を使ったパイプラインによるサーバ実装
194
195 応答よりもスループット重視
196
197 <center><img src="images/SEDA.jpg"></center>
47 198
48 --Experiment 199 --Experiment
49 200
50 --Ring 201 AliceとFederated Linda で性能比較を行った。
51
52
53
54
55
56 に置いて、タスクをCode Segment、データをData Segmentという単位に分割して記述する方法を提唱している。</p>
57 <p>しかし、前述したプログラムをプログラマーが一から記述していくことは大変である。</p>
58 <p>そこで、本研究室の卒業生である赤嶺一樹氏が分散ネットフレームワークAliceのプロトタイプを作成した。</p>
59 <p>本研究では実際にAliceを利用して、水族館の例題を作成した。また、Federated Lindaとの性能比較を行った。そして、Aliceの問題点の洗い出し、APIの見直しを行った。</p>
60
61 --発表内容
62 <ul>
63 <li>Aliceの紹介
64 <li>プログラムの記述方法
65 <li>水族館の例題と性能評価
66 <li>まとめと課題
67 </ul>
68
69 --Alice
70 <ul>
71 <p>Alice は本研究室で開発を行なっている分散タスク管理フレームワークである。</p>
72 <p>Cell用のOpen CL に似たTask管理用フレームワークCeriumと
73 Lindaを相互接続した分散フレームワークであるFederated Lindaの開発を通して得られた知見を生かされている。</p>
74 <ul>
75
76 --Cerium
77 <ul>
78 <p>Ceriumは当研究室で開発を行なっている並列プログラミングフレームワークである。</p>
79 <p>CeriumではTaskを小さく分割して並列実行し、データ転送はパイプライン実行により隠される。</p>
80 <p>Taskには依存関係がありデータの依存関係がそのままTaskの依存関係になることが多い。</p>
81 <p>繰り返し使われるデータの管理が重要であり、実行時にわかるデータ構造間の依存関係がTaskを複雑にしている。</p>
82 </ul>
83
84 --Data Segment API
85 <ul>
86 <p>Data Segmentは数値や文字などのデータを構造体的に保持するが、分散プログラムにおいてData Segmentの相互参照が問題になってくる。</p>
87 <p>AliceではData SegmentにユニークなKeyを持たせ、Key Value Storeとして扱っている。Key毎のキューがあり、Key毎に順に実行される。<br>
88 <div align="center">
89 <img src="images/dataSegment_key.png">
90 </div>
91
92 </ul>
93
94
95 --Data Segment API
96 <ul>
97 <p>Data Segmentを管理するのが、Data Segment Manager
98 各ノード毎に、Local DS ManagerとRemote DS Managerが存在する。</p>
99 <p>Local DS Managerはノード固有のKey Value Storeであり、Remote DS Managerは他のノードのLocal DS Managerのproxyである。
100 AliceのTopology Managerが自動的に構成する。</p>
101 <div align="center">
102 <img src="images/lrds.png" width=500>
103 </div>
104 </ul>
105
106
107 --Data Segment API
108 <ul>
109 以下が用意されているData Segment APIである。
110 <li>void put(String key, Value val)</li>
111 <li>void update(String key, Value val)</li>
112 <li>void peek(Receiver receiver, String key)</li>
113 <li>void take(Receiver receiver, String key)</li>
114 <p>これらを用いてデータの送受信を行う。</p>
115 </ul>
116
117 --Data Segment API - put
118 <ul>
119 <li>データを追加する</li>
120 </ul>
121 <div align="center">
122 <img src="images/put.png" width=70%>
123 </div>
124 <ul>
125 <p>putを行うとデータがenqueueされる。</p>
126 <p>putするたびにKeyが持つindexがincrementされる。</p>
127 </ul>
128
129 --Data Segment API - update
130 <ul><li>データを置き換える</li></ul>
131 <div align="center">
132 <img src="images/update.png" width=70%>
133 </div>
134 <ul>
135 putと異なる点は先頭データを削除し、データを追加する。
136 </ul>
137
138 --Data Segment API - peek
139 <ul><li>データを取得する</li></ul>
140 <div align="center">
141 <img src="images/peek.png" width=50%><br>
142 </div>
143 <ul>
144 peekはデータを取得しreceiverに渡す。
145 </ul>
146
147 --Data Segment API - peek
148 <div align="center">
149 <img src="images/peek1.png" width=60%><br>
150 </div>
151 <ul>
152 <p>要求したデータがない場合にはwaitListに登録する。</p>
153 データがput、updateされる際に要求したデータがあるかどうかを再びチェックする。
154
155 </ul>
156
157 --Data Segment API - take
158 <ul><li>データを取得して取得されたデータはdequeueされる</li></ul>
159 <div align="center">
160 <img src="images/take.png" width=50%><br>
161 </div>
162 <ul>
163 <p>基本的な動作はpeekと同じである。</p>
164 <p>peekと異なる点は取得されたデータがdequeueされる。</p>
165 </ul>
166
167 --Data Segmentの実装
168 <ul>
169 Data Segmentのデータ表現はMessagePackを使用。
170 </ul>
171 <ul><p>JavaにおけるMessagePackのデータ表現</p>
172 <li>一般的なJavaのクラスオブジェクト</li>
173 <li>MessagePack for JavaのValueオブジェクト</li>
174 <li>byte[]で表現されたバイナリ</li>
175 </ul>
176 <ul>
177 <p>Data Segment APIでは</p>
178 MessagePack for javaのValueオブジェクトを使用</p>
179 MessagePackのバイナリにシリアライズできる型のみで
180 構成されているため自己記述式のデータ形式
181 </ul>
182
183 --Data Segmentの実装
184 <ul>
185 <p>Valueオブジェクトは通信に関わる際には、シリアライズ、デシリアライズを高速に行うことができる</p>
186 <img src="images/FishPoint.png" width=700><br>
187 ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを記述することが可能
188 </ul>
189
190 --CodeSegment
191 <ul>
192 <li>Code Segmentはタスクのこと</li>
193 <li>ユーザーが記述する際にCode Segment内で使用する<br>Data Segmentの作成を記述</li>
194 <li>Input Data SegmentとOutput Data Segmentを作るAPI</li>
195 <li>必要なInput Data Segmentが揃った時に実行される</li>
196 </ul>
197
198 --Input Data SegmentとOutput Data Segment
199 <ul>
200 <li>localかremoteを指定</li>
201 <li>Data Segmentに関連付けされているKEYを指定</li>
202 </ul>
203
204 <ul>
205 --Data Segmentの例
206 <img src="images/SendWidth.png" width=600>
207 </ul>
208
209 --Input Data Segmentの例
210 <ul>
211 <img src="images/ids.png" width=400><br>
212 Receiverの作成<br>
213 PEEK,TAKEのどちらかを選択
214 </ul>
215 <ul>
216 <img src="images/idsSetkey.png" width=600><br>
217 第1引数 マシン名<br>
218 第2引数 Data Segmentに関連付けられているKEY<br>
219 第3引数 index(指定しない場合は先頭データが取得される)<br>
220 </ul>
221
222 --Output Data Segmentの例
223 <ul>
224 <img src="images/ods.png" width=400><br>
225 putかupdateのどちらかを選択
226 </ul>
227 <ul>
228 第1引数 マシン名<br>
229 第2引数 Data Segmentに関連付けるKEY<br>
230 第3引数 Data Segment<br>
231 </ul>
232
233 --Code Segmentの実行方法
234 <ul>
235 <img src="images/StartCS.png" width=600><br>
236 </ul>
237 <ul>
238 AliceにはCのmainに相当するStart Code SegmentというCode Segmentが存在する。<br>
239 Start Code SegmentはInput Data Segmentが存在しない。
240 </ul>
241
242 --Code Segmentの実行方法
243 <ul>
244 <img src="images/execute.png" width=600><br>
245 </ul>
246 <ul>
247 このStart Code Segmentをnewし、executeメソッドを呼ぶことでCode Segmentを実行することができる。
248 </ul>
249
250 --Code Segmentの記述方法
251 <ul>
252 <img src="images/TestCodeSegment.png" width=600><br>
253 </ul>
254 ユーザがCode Segmentを記述する際にはCode Segmentを継承する。<br>
255 runの中に実際にさせたい処理を記述する。
256
257 --Topology Manager
258 <ul>
259 Alice同士の接続トポロジーを管理する。<br>
260 トポロジーファイルを読み込み、参加を表明したクライアントに接続すべきクライアントのIPアドレスやポート番号、接続名を送る。
261 <div align="center">
262 <img src="images/topology.png" width=350>
263 </div>
264 </ul>
265
266 --Topology Manager
267 <ul>
268 Topology Manager関連の通信は全て、Code Segmentで実装されている。
269 </ul>
270
271 --トポロジーファイル
272 <ul>
273 <p>トポロジーファイルはDOT Languageと言う言語で記述される。</p>
274 DOT Languageはプレーンテキストを用いてデータ構造としてのグラフを表現するデータ記述言語の一つ。<br>
275 DOT Languageのグラフ構造を用いてTopology Node間の接続を表現する。<br>
276 </ul>
277
278 --トポロジーファイルの記述方法
279 <ul>
280 <img src="images/topologyfile.png">
281 <p>dotコマンドを用いて、グラフの画像ファイルを生成することができるのでトポロジーが正しいか確認することができる。</p>
282
283 </ul>
284
285 --トポロジーファイルの確認方法
286 <ul>
287 <p><strong>dot -T png ring.dot -o ring.png</strong></p>
288 <div align="center">
289 <img src="images/dot.png">
290 </div>
291 </ul>
292
293 --水族館の例題
294 <ul>
295 <p>複数の魚が複数のディスプレイ上を移動する。</p>
296 <p>魚のうち一匹はクライアントが操作することができる。</p>
297 <p>トポロジーはツリー状に構成してある。</p>
298 </ul>
299 <div align="center">
300 <img src="images/aquarium.png" width=800>
301 </div>
302
303 <div align="center">
304 <img src="images/commnuication.png" width=600>
305 </div>
306
307 --性能比較 - 実験概要
308 <ul>
309 AliceとFederated Linda で性能比較を行った。<br>
310 Ring型のトポロジーを構成、メッセージが100周する時間を計測。 202 Ring型のトポロジーを構成、メッセージが100周する時間を計測。
311 1周あたりの平均時間を求めた。 203 1周あたりの平均時間を求めた。
312 <div align="center"> 204 <center><img src="images/ringTest.png"></center>
313 <img src="images/ringTest.png"> 205
314 </div>
315 パケットのサイズは10byte,10Kbyte,100kbtyeで実験 206 パケットのサイズは10byte,10Kbyte,100kbtyeで実験
316 </ul> 207
317 208 --何故 Ring?
318 --実験環境 209
319 <ul> 210 なぜ、不利なベンチマークを取るのか?
320 ブレードサーバー上の仮想マシンによる仮想クラスタ環境を用いて実験した。<br> 211
321 <p><strong>ブレードサーバー詳細</strong></p> 212 SEDA でレスポンスをはかっちゃだめだろう?
213
214 SEDA はCPU食い。Core Duo とかで全然ダメ。
215
216 なので、Core i7 を用意しました。
217
322 <table style="font:Osaka;text-align:right;" border="2" > 218 <table style="font:Osaka;text-align:right;" border="2" >
323 <tr> 219 <tr>
324 <td>マシン台数</td> 220 <td>マシン台数</td>
325 <td>8台</td> 221 <td>8台</td>
326 </tr> 222 </tr>
342 <tr> 238 <tr>
343 <td>Memory</td> 239 <td>Memory</td>
344 <td>132GB</td> 240 <td>132GB</td>
345 </tr> 241 </tr>
346 </table> 242 </table>
347 243
348 </ul> 244
349 --実験環境 245 --実験結果 小さいデータ
350 <ul> 246
351 <p><strong>仮想クラスタ詳細</strong></p> 247 <strong>10byte</strong>
352 <table style="font:Osaka;text-align:right;" border="2" > 248 <center><img src="images/ring10B.png"></center>
353 <tr> 249
354 <td>マシン台数</td> 250 Single threaded な Federated Linda に負けている
355 <td>48台</td> 251
356 </tr> 252 --実験結果 大きなデータ
357 <tr> 253
358 <td>CPU</td> 254 <strong>100kbyte</strong>
359 <td>Intel(R) Xeon(R) X5650 @ 2.67GHz</td> 255 <center><img src="images/ring100KB.png"></center>
360 </tr> 256 データ量が増えると差が縮まっている。これはここの通信の手間の影響が大きことを示している。
361 <tr>
362 <td>物理コア数</td>
363 <td>2</td>
364 </tr>
365 <tr>
366 <td>論理コア数</td>
367 <td>4</td>
368 </tr><tr>
369 <td>CPU キャッシュ</td>
370 <td>12MB</td>
371 </tr>
372 <tr>
373 <td>Memory</td>
374 <td>8GB</td>
375 </tr>
376 </table>
377 </ul>
378
379 --実験結果
380 <ul>
381 <strong>10byte</strong><br>
382 <img src="images/ring10B.png" width=650>
383 </ul>
384
385 --実験結果
386 <ul>
387 <strong>10kbyte</strong><br>
388 <img src="images/ring10KB.png" width=650>
389 </ul>
390 257
391 --実験結果 258
392 <ul> 259 --実験結果 スレッドプールなし
393 <strong>100kbyte</strong> 260
394 <img src="images/ring100KB.png" width=650><br> 261 スレッドプールを使わないほうが、Ringの結果は良い<
395 データ量が増えると差が縮まっている。これはここの通信の手間の影響が大きことを示している。 262 <center><img src="images/notp.png"></center>
396 </ul> 263
397 264
398 --評価と考察 265 --わかりやすい記述になったのか?
399 <ul> 266
400 今回の実装はJavaによりCode SegmentとData Segmentに必要なAPIを洗い出すものだった。この実装でも問題をいくつか発見した。<br> 267 Input DS と Output DS の記述が対称にならない
401 <p><strong>API</strong></p> 268
402 <li>Class継承したりData Segmentの作成にFactory objectを使うのはJavaを使う際の技術的な問題</li> 269 CS/DS の関係を CS 内部に書くのはダメな戦略?
403 <li>JavaのObject指向な記述が全体を煩雑にしている部分がある</li> 270
404 <li>updateはData Segmentの競合的な更新に使われるべきだと思われる</li>
405 </ul>
406
407 --評価と考察
408 <p><strong>SEDA</strong></p>
409 <ul>
410 <li>Federated Lindaに比べ遅い原因の一つはSEDA architectureのせいと思われる</li>
411 <li>SEDAはスループット重視の実装であり、多段パイプラインのせいでレスポンスが遅れてしまう</li>
412
413 </ul>
414
415 --評価と考察
416 <ul>
417 <li>スレッドプールを使わないほうが、Ringの結果は良い</li>
418 <img src="images/notp.png" width=650><br>
419 </ul>
420 271
421 --評価と考察 272 --評価と考察
422 <p><strong>MessagePack</strong></p> 273 <p><strong>MessagePack</strong></p>
423 <ul> 274 <ul>
424 <li>今回の実装では単純なMessageの転送時にもMessagePackのdecode/encodeをしているが、overheadになってしまうため、decode/encode抜きに直接操作できるほうが望ましい</li> 275 <li>今回の実装では単純なMessageの転送時にもMessagePackのdecode/encodeをしているが、overheadになってしまうため、decode/encode抜きに直接操作できるほうが望ましい</li>