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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
36
b7fb46ffac37 add ui directory to o2s5 directory
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
3 --author: 河野 真治, 杉本 優
35
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4
39
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
5 --並列分散フレームワーク
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
6
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
7 本研究室では分散プログラミングと並列プログラミングのツールを開発してきた。
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
8
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
9 分散プログラミング用のFederated Lidna
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
10 並列プログラミング用のCerium
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
11
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
12 これらの経験から並列分散を統一的に扱えるプログラミングフレームワークを考えたい。
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
13
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
14 そこで、
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
15
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
16 data segment と code segment で書くというのを考えた
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
17 Java で実装して評価した
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
18
39
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
19 --並列分散フレームワークには何が求められるのか
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
20
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
21 並列実行単位の記述
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
22 プロトコルの記述
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
23 実用的な実装
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
24 高い対障害性
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
25 Scalability
39
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
26 実験環境の用意
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
27 Version up への対応
39
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
28 多言語対応
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
29 検証や証明への対応
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
30
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
31 --Federated Linda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
32
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
33 データの塊である Tuple を使って通信するフレームワーク
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
34
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
35 in Tuple を取り出す
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
36 out Tuple 書きだす
35
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
38 in, out で待ち合わせを行う
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
39
39
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
40 --Federated Linda の Pros and Cons
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
41
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
42 in/out のAPIさえあれば良いので、言語独立 (良)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
43
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
44 Tuple のキーが文字列でわかりやすい (良)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
45
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
46 切断に強い (良)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
47
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
48 記述部分がスパゲティになりやすい (悪)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
49
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
50 call back を使うと、さらにダメな記述に (悪)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
51
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
52 --Linda の だめな記述の例
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
53
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
54 left.in(Up, new PSXCallback() {public void callback(ByteBuffer reply) {
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
55 if (debug) System.out.println("Up from left at"+nodeId);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
56 left.in(Up,this);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
57 leftWaiter.add(reply);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
58 checkSend(ml);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
59 }
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
60
39
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
61 --Cerium
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
62
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
63 Task 単位で並列実行するツール
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
64
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
65 Task を作って scheduler に投入
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
66
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
67 Task のデータは暗黙に通信される
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
68
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
69 Open CL 、Spurs Engine などの実装がある
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
70
39
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
71 --Cerium の Pros and Cons
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
72
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
73 Task は短く単純になる (良)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
74
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
75 アセンブラ的なので性能は出やすい (良)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
76
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
77 Task の依存関係は自分で管理 (悪)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
78
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
79 データ構造は基本的に配列になりやすい (悪)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
80
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
81 Task 管理部分が極めて複雑になる (悪)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
82
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
83 --Cerium の だめな記述の例
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
84
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
85 {
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
86 int i = half_num-1;
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
87
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
88 if (s->bsort[i]) manager->free_htask(s->bsort[i]);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
89 s->bsort[i] = manager->create_task(QUICK_SORT,
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
90 (memaddr)&s->data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num,
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
91 (memaddr)&s->data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
92 s->bsort[i]->flip();
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
93 s->bsort[i]->set_cpu(GPU_0);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
94 s->bsort[i]->set_param(0,(memaddr)last_half_block_num);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
95 }
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
96
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
97 for (int i = 0; i < half_num; i++) {
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
98 s->bsort[i]->wait_for(s->fsort[i]);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
99 s->bsort[i]->wait_for(s->fsort[i+1]);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
100 s->bsort[i]->no_auto_free();
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
101 s->bsort[i]->spawn();
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
102 }
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
103
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
104
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
105 --Linda と Cerium の良いとこ取りをしたい
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
106
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
107 Task 依存は、Tuple の依存で決まる
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
108
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
109 コードをTaskに分割する
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
110 Code Segment
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
111
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
112 データをTupleに分割する
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
113 Data Segment
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
114
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
115 Code と Data は双対になるはず
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
116
39
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
117 --Data segment と Code Segment
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
118
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
119 Code segment には input data segment と output data segment がある
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
120
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
121 <center><img src="images/reconnection.jpg"></center>
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
122
39
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
123 --Java Implmentation : Alice
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
124
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
125 data segment は key (strig) でアクセスされる
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
126
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
127 input data segment は書き込みを待つ
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
128
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
129 --Local / Remote data segment Manager
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
130
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
131 Data Segmentを管理するのが、Data Segment Manager 各ノード毎に、Local DS ManagerとRemote DS Managerが存在する。
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
132
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
133 Local DS Managerはノード固有のKey Value Storeであり、Remote DS Managerは他のノードのLocal DS Managerのproxyである。
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
134
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
135 <center><img src="images/lrds.png"></center>
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
136
39
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
137 --CS/DS API
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
138
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
139 input data segment の作成 (PEEKとTAKE)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
140 public Receiver ds1 = ids.create(CommandType.TAKE);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
141 key の設定
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
142 ds1.setKey("finish");
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
143 output data segment の書き出し (put と update)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
144 ods.put("local", "finish", ValueFactory.createNilValue());
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
145
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
146 これらを用いてデータの送受信を行う。
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
147
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
148 --Data segment の型
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
149
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
150 MessagePack を使用すると、そのままオブジェクトを data segment に使える
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
151
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
152 import org.msgpack.annotation.Message;
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
153 @Message
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
154 public class FishPoint {
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
155 public float x = 0.0f;
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
156 public float y = 0.0f;
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
157 public float z = 0.0f;
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
158 }
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
159
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
160
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
161 --Example
39
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
162
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
163 public class SendWidth extends CodeSegment {
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
164 Receiver width = ids.create(CommandType.PEEK);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
165 @Override
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
166 public void run() {
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
167 int width = this.width.asInteger();
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
168 ods.put("parent", "widths", width);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
169 System.out.println("send widths: " + width);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
170 SendWidth cs = new SendWidth();
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
171 cs.width.setKey("local", "width", this.width.index);
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
172 }
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
173 }
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
174
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
175
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
176 --Sample Application 水族館の例題
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
177
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
178 複数の魚が複数のディスプレイ上を移動する。
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
179
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
180 魚のうち一匹はクライアントが操作することができる。
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
181
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
182 トポロジーはツリー状に構成してある。
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
183 <center><img src="images/aquarium.png"></center>
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
184
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
185 --CS/DS Java 版 Alice
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
186
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
187 Java で SEDA をしようして実装
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
188
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
189 MessagePack を使って Marshaling
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
190
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
191 --SEDA
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
192
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
193 Thread pool を使ったパイプラインによるサーバ実装
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
194
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
195 応答よりもスループット重視
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
196
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
197 <center><img src="images/SEDA.jpg"></center>
39
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
198
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
199 --Experiment
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
200
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
201 AliceとFederated Linda で性能比較を行った。
35
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
202 Ring型のトポロジーを構成、メッセージが100周する時間を計測。
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
203 1周あたりの平均時間を求めた。
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
204 <center><img src="images/ringTest.png"></center>
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
205
35
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
206 パケットのサイズは10byte,10Kbyte,100kbtyeで実験
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
207
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
208 --何故 Ring?
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
209
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
210 なぜ、不利なベンチマークを取るのか?
35
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
211
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
212 SEDA でレスポンスをはかっちゃだめだろう?
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
213
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
214 SEDA はCPU食い。Core Duo とかで全然ダメ。
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
215
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
216 なので、Core i7 を用意しました。
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
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
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
243
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
244
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
245 --実験結果 小さいデータ
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
246
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
247 <strong>10byte</strong>
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
248 <center><img src="images/ring10B.png"></center>
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
249
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
250 Single threaded な Federated Linda に負けている
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
251
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
252 --実験結果 大きなデータ
35
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
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
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
255 <center><img src="images/ring100KB.png"></center>
35
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
256 データ量が増えると差が縮まっている。これはここの通信の手間の影響が大きことを示している。
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
257
40
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
258
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
259 --実験結果 スレッドプールなし
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
260
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
261 スレッドプールを使わないほうが、Ringの結果は良い<
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
262 <center><img src="images/notp.png"></center>
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
263
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
264
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
265 --わかりやすい記述になったのか?
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
266
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
267 Input DS と Output DS の記述が対称にならない
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
268
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
269 CS/DS の関係を CS 内部に書くのはダメな戦略?
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
270
35
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
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
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
279
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
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
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
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
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
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
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
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
5f961785fb0c add o2s5
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
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>