Mercurial > hg > Papers > 2012 > sugi-prosym
annotate 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 |
rev | line source |
---|---|
36
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
1 -title: CodeSegmentとDataSegmentによるプログラミング手法 |
35 | 2 |
36
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
3 --author: 河野 真治, 杉本 優 |
35 | 4 |
39 | 5 --並列分散フレームワーク |
6 | |
7 本研究室では分散プログラミングと並列プログラミングのツールを開発してきた。 | |
8 | |
9 分散プログラミング用のFederated Lidna | |
10 並列プログラミング用のCerium | |
11 | |
12 これらの経験から並列分散を統一的に扱えるプログラミングフレームワークを考えたい。 | |
13 | |
40 | 14 そこで、 |
15 | |
16 data segment と code segment で書くというのを考えた | |
17 Java で実装して評価した | |
18 | |
39 | 19 --並列分散フレームワークには何が求められるのか |
20 | |
21 並列実行単位の記述 | |
22 プロトコルの記述 | |
23 実用的な実装 | |
40 | 24 高い対障害性 |
25 Scalability | |
39 | 26 実験環境の用意 |
40 | 27 Version up への対応 |
39 | 28 多言語対応 |
29 検証や証明への対応 | |
30 | |
31 --Federated Linda | |
32 | |
33 データの塊である Tuple を使って通信するフレームワーク | |
34 | |
35 in Tuple を取り出す | |
36 out Tuple 書きだす | |
35 | 37 |
40 | 38 in, out で待ち合わせを行う |
39 | |
39 | 40 --Federated Linda の Pros and Cons |
41 | |
40 | 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 | |
39 | 61 --Cerium |
62 | |
63 Task 単位で並列実行するツール | |
64 | |
40 | 65 Task を作って scheduler に投入 |
66 | |
67 Task のデータは暗黙に通信される | |
68 | |
69 Open CL 、Spurs Engine などの実装がある | |
70 | |
39 | 71 --Cerium の Pros and Cons |
72 | |
40 | 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 | |
39 | 117 --Data segment と Code Segment |
118 | |
40 | 119 Code segment には input data segment と output data segment がある |
120 | |
121 <center><img src="images/reconnection.jpg"></center> | |
122 | |
39 | 123 --Java Implmentation : Alice |
124 | |
40 | 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 | |
39 | 137 --CS/DS API |
138 | |
40 | 139 input data segment の作成 (PEEKとTAKE) |
140 public Receiver ds1 = ids.create(CommandType.TAKE); | |
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 | |
39 | 162 |
40 | 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> | |
39 | 198 |
199 --Experiment | |
200 | |
40 | 201 AliceとFederated Linda で性能比較を行った。 |
35 | 202 Ring型のトポロジーを構成、メッセージが100周する時間を計測。 |
203 1周あたりの平均時間を求めた。 | |
40 | 204 <center><img src="images/ringTest.png"></center> |
205 | |
35 | 206 パケットのサイズは10byte,10Kbyte,100kbtyeで実験 |
40 | 207 |
208 --何故 Ring? | |
209 | |
210 なぜ、不利なベンチマークを取るのか? | |
35 | 211 |
40 | 212 SEDA でレスポンスをはかっちゃだめだろう? |
213 | |
214 SEDA はCPU食い。Core Duo とかで全然ダメ。 | |
215 | |
216 なので、Core i7 を用意しました。 | |
217 | |
36
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
218 <table style="font:Osaka;text-align:right;" border="2" > |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
219 <tr> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
220 <td>マシン台数</td> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
221 <td>8台</td> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
222 </tr> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
223 <tr> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
224 <td>CPU</td> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
225 <td>Intel(R) Xeon(R) X5650 @ 2.67GHz</td> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
226 </tr> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
227 <tr> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
228 <td>物理コア数</td> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
229 <td>12</td> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
230 </tr> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
231 <tr> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
232 <td>論理コア数</td> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
233 <td>24</td> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
234 </tr><tr> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
235 <td>CPU キャッシュ</td> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
236 <td>12MB</td> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
237 </tr> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
238 <tr> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
239 <td>Memory</td> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
240 <td>132GB</td> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
241 </tr> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
242 </table> |
40 | 243 |
244 | |
245 --実験結果 小さいデータ | |
246 | |
247 <strong>10byte</strong> | |
248 <center><img src="images/ring10B.png"></center> | |
249 | |
250 Single threaded な Federated Linda に負けている | |
251 | |
252 --実験結果 大きなデータ | |
35 | 253 |
36
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
254 <strong>100kbyte</strong> |
40 | 255 <center><img src="images/ring100KB.png"></center> |
35 | 256 データ量が増えると差が縮まっている。これはここの通信の手間の影響が大きことを示している。 |
257 | |
40 | 258 |
259 --実験結果 スレッドプールなし | |
260 | |
261 スレッドプールを使わないほうが、Ringの結果は良い< | |
262 <center><img src="images/notp.png"></center> | |
263 | |
264 | |
265 --わかりやすい記述になったのか? | |
266 | |
267 Input DS と Output DS の記述が対称にならない | |
268 | |
269 CS/DS の関係を CS 内部に書くのはダメな戦略? | |
270 | |
35 | 271 |
36
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
272 --評価と考察 |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
273 <p><strong>MessagePack</strong></p> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
274 <ul> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
275 <li>今回の実装では単純なMessageの転送時にもMessagePackのdecode/encodeをしているが、overheadになってしまうため、decode/encode抜きに直接操作できるほうが望ましい</li> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
276 <li>Data Segmentの一部の修正をするたびにData Segmentが再構成されているがこれは望ましくない</li> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
277 <li>AliceもCeriumのようにInput Data SegmentとOutput Data SegmentをswapするAPIがあるとよいと思われる</li> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
278 </ul> |
35 | 279 |
280 | |
36
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
281 --評価と考察 |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
282 <p><strong>Key</strong></p> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
283 <ul> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
284 <li>分散実装においてはData Segmentの相互参照はKey経由が打倒であるが、並列実装では全てのData SegmentをKey Value Storeに格納するのは、性能的な問題を引き起こす</li> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
285 <li>分散記述と並列記述を分ければ解決するが、2つの記述がかけ離れるのは好ましくない</li> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
286 <li>本来Key Value storeは持続性を持たせる必要がある</li> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
287 </ul> |
35 | 288 |
36
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
289 --評価と考察 |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
290 <p><strong>Java</strong></p> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
291 <ul> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
292 <li>Data SegmentはCode Segmentがactiveの時のみメモリ上にあり、その最大値はActive Taskの量を見積もればよいのでAliceにGarbage Collectionの機能は必要ない</li> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
293 <li>key Value Store 上のデータは決してGarbage Collectionの対象にはならないが、それがGarbage Collectionに負荷をかける結果となるためAliceとJavaの相性は悪い</li> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
294 </ul> |
35 | 295 |
36
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
296 --評価と考察 |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
297 <p><strong>拡張性</strong></p> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
298 <ul> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
299 <li>分散アプリケーションのプロトコルは常に変更されるため、Aliceもそれに対応する必要がある</li> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
300 <li>Keyとトポロジーマネージャーをプロトコル毎に別に用意すれば複数のプロトコルを同時に走らせることが可能</li> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
301 <li>Data SegmentとCode Segmentの結びつきは弱いため、Data Segmentに余計な値がある場合、値が足りない場合に適切な値を設定することで古いCode Segmentを変更するとこなしにプロトコルを拡張できる</li> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
302 </ul> |
35 | 303 |
36
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
304 --まとめと課題 |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
305 <ul> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
306 <p>今回Code SegmentとData Segmentによる並列分散フレームワークのJavaによる実装を示した。実装でしかえられない知見を得ることができた。</p> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
307 <p>今回Javaによる実装を行ったがJavaがAliceの実装に不向きであるということもわかった。</p> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
308 <p> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
309 <li>Code Segment/Data Segmentを見たコンパイラ的アプローチ</li> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
310 <li>実行時最適化</li> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
311 <li>CbCによる実装</li> |
35 | 312 などが有効、効果的だと思われる。</p> |
36
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
313 <p>今回はノード内の並列実行やGPGPUによる並列実行などは考慮していない。将来的にそれを含め実装をしていきたい。</p> |
b7fb46ffac37
add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
314 </ul> |