Mercurial > hg > Papers > 2016 > nozomi-thesis

comparison presen/sample.markdown @ 10:90aaf305aed6 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add presen
author Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
date Thu, 18 Feb 2016 09:06:13 +0900
parents b2869724949d
children
comparison
equal deleted inserted replaced
9:b2869724949d 10:90aaf305aed6
1 title: 分散フレームワークAliceのPC画面配信システムへの応用 1 title: 分散フレームワークAliceのMeta Data Segment
2 author: 照屋のぞみ 河野真治 2 author: 照屋のぞみ
3 profile:琉球大学 工学部 情報工学科 3 profile:琉球大学 工学部 情報工学科 河野研
4 4
5 # 研究目的(1/3) 5 # 研究目的(1/3)
6 * 当研究室が開発している並列分散フレームワークAliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。 6 * 当研究室が開発している並列分散フレームワークAliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する
7 * ここで言う信頼性とは定められた環境下で安定して仕様に従った動作を行うことを指す。　　 7 * ここで言う信頼性とは定められた環境下で安定して仕様に従った動作を行うことを指す
8 * Aliceでは当研究室が提案しているデータを Data Segment、タスクを Code Segment という単位で分割して記述するプログラミング手法を採用している。 8 * Aliceでは当研究室が提案しているデータを Data Segment、タスクを Code Segment という単位で分割して記述するプログラミング手法を採用している
9 9
10 # 研究目的(2/3) 10 # 研究目的(2/3)
11 * Aliceでは、処理をComputationとMetaComputationに階層化し、コアな仕様と複雑な例外処理に分離する。 11 * Aliceでは、ComputationとMetaComputationに階層化し、コアな仕様と複雑な例外処理に分離する。
12 * 分散環境構築などの複雑な処理はAliceがMeta Computationとして提供する 12 * 分散環境構築などの複雑な処理はAliceがMeta Computationとして提供する
13 * 仕様を大きく変更することなくプログラムの挙動が変えられる 13 * コードの変更を抑え、変更前の信頼性を保ったまま拡張可能にする
14 * 変更前の信頼性を保ったまま拡張可能にする
15 14
16 # 研究目的(3/3) 15 # 研究目的(3/3)
17 * 本研究では、 Alice上に実用的な分散アプリケーションが制作できることを示すために画面配信システムTreeVNCを構築する。 16 * 本研究では、Alice上に実用的な分散アプリケーションが制作できることを示すために画面配信システムTreeVNCを構築する
18 * 構築するにあたり必要となった圧縮機能をAliceのMeta Computationとして実装した。 17 * 構築するにあたり必要となった圧縮機能をAliceのMeta Computationとして実装した
19 * もとのTreeVNCとの比較を行うことでMetaComputationの役割と有効性を示す。 18 * もとのTreeVNCとの比較を行うことでMeta Computationの役割と有効性を示す
20 19
21 20
22 # Data Segment と Code Segment 21 # Data Segment と Code Segment
23 * Aliceではデータを **Data Segment(DS)** 、タスクを **Code Segment(CS)** という単位に分割して依存関係を記述することでプログラミングを行う。 22 * Aliceではデータを **Data Segment(DS)** 、タスクを **Code Segment(CS)** という単位に分割して依存関係を記述することでプログラミングを行う。
24 * CSはInput DS(入力されるDS)とOutput DS(出力されるDS)を持つ。 23 * CSはInput DS(入力されるDS)とOutput DS(出力されるDS)を持つ。
25 * CSはkeyで指定されたDSが揃うと実行されるという性質を持つ。 24 * CSはkeyで指定されたDSが全て揃うと実行されるという性質を持つ。
26 ![opt](./images/dsandcs.svg){:width="60%"} 25 ![opt](./images/dsandcs.svg){:width="50%"}
27 26
28 # CodeSegmentの依存関係 27 # CodeSegmentの依存関係
29 * データの依存関係にないCSは並列実行される 28 * データの依存関係にないCSは並列実行される
30 * データの依存関係がある場合は Input DS が揃うと順に実行される 29 * データの依存関係がある場合は Input DS が揃うと順に実行される
31 * DSはCSに専有されるためロックの記述を必要としない 30 * DSはCSに専有されるためロックの記述を必要としない
32 ![opt](./images/dsandcs2.svg){:width="60%"} 31 ![opt](./images/dsandcs2.svg){:width="60%"}
33 32
34 # Data Segment と CodeSegment
35 * AliceはJavaで実装されており、DSはJava-Object、CSはRunnableに相当する
36 * ユーザーが記述する際には CodeSegment.class を継承することでDSを操作するためのAPIを利用して依存関係を記述することができる。
37 * DSはAliceが内部にもつデータベース(DS Manager)により管理されており、CSはDSに対応する一意のkeyを使ってDSを操作する。
38
39 # Data Segment Manager 33 # Data Segment Manager
40 * DS の集合体であるデータベースを Alice では **DS Manager(DSM)** と呼ぶ。 34 * DS の集合体であるデータベースを **DS Manager(DSM)** と呼ぶ。
35 * Local DSM … 各ノード固有のデータベース。
36 * Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在する。
41 * DSM 内の DS には対になる String型のkey が存在し、 DSM 名と key を指定しすることで DS の保存、取得を行う。 37 * DSM 内の DS には対になる String型のkey が存在し、 DSM 名と key を指定しすることで DS の保存、取得を行う。
42 * keyに対して複数のDSを保存する際はFIFO的に処理される
43 ![opt](./images/KeyDS.svg){:width="50%"}
44
45 # Data Segment Manager
46 * Local DSM … 各ノード固有のデータベース。
47 * Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在する。
48 ![opt](./images/remote_datasegment.svg){:width="50%"} 38 ![opt](./images/remote_datasegment.svg){:width="50%"}
49 39
50 # Data Segment API
51 * DS の追加
52 * put(String managerKey, String key, Object val)
53 * update(String managerKey, String key, Object val) ※先頭DSを削除してからput
54 * flip(String managerKey, String key, Receiver receiver) ※ゼロコピー転送用
55 * DS の取得
56 * take(String managerKey, String key)
57 * peek(String managerKey, String key) ※DSMから削除されない
58
59 * take/peekは実際にはcreate()とsetKey()によって行われる
60 * create()でDSの受け皿を作っておき、setKey()にkeyをセットすることで Input DS を指定する
61 40
62 # Computation と Meta Computation 41 # Computation と Meta Computation
63 * Aliceでは、計算の本質的な処理をComputatin、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。 42 * Aliceでは、計算の本質的な処理をComputatin、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。
64 * Alice のComputationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理。 43 * 分散トポロジーの構成、通信の切断・再接続時の処理などはMeta ComputationとしてAliceが提供
65 * 分散トポロジーの構成、通信の切断・再接続時の処理やデータの表現形式の選択など、Computationを支えている処理。 44 * プログラマは目的の処理だけ記述し通信部分などはMeta Computationを指定することでシンプルな記述を実現
66 45
67 # Computation と Meta Computation 46 # Computation と Meta Computation
68 * DS/CSの接続の間にMeta Computationが実行されている 47 * DS/CSの接続の間にMeta Computationが実行されている
69 * AliceのMeta ComputationもCS/DSにより実現される 48 * AliceのMeta ComputationもCS/DSにより実現される
70 * Meta ComputationはCS の処理を支えるMeta CSとMeta CSに管理されるMeta DSに分けられる 49 * Meta ComputationはCS の処理を支えるMeta CSとMeta CSに管理されるMeta DSに分けられる
71 ![opt](./pictures/MetaCSDS.svg){:width="70%"} 50 ![opt](./pictures/MetaCSDS.svg){:width="70%"}
72 51
73 # Computation と Meta Computation 52
74 * 分散環境構築などの複雑な処理をAliceがMeta Computationとして提供する 53 # TreeVNCへの応用
75 * プログラマは目的の処理だけ記述し通信部分などはMeta Computationを指定する 54 * AliceのMeta Computationの有効性を示すため実用的な例題であるTreeVNCを実装する
76 55 * TightVNCをもとにした木構造画面配信システム
77 # TreeVNC
78 * Aliceを用いて実装する実用的な分散プログラムの例題
79 * 当研究室で開発したノードを木構造に配置して負荷分散を行う授業向け画面共有システム
80 * TightVNCがもとになっている
81 * 画面処理や分散処理が混在する複雑なTreeVNCも、Aliceを用いればTightVNCからの変更が少ない見通しの良い記述で構成可能 56 * 画面処理や分散処理が混在する複雑なTreeVNCも、Aliceを用いればTightVNCからの変更が少ない見通しの良い記述で構成可能
82 57
83 # TreeVNCで必要な機能 58 # TreeVNCで必要な機能
84 TreeVNCのComputation（VNCサーバからデータを受け取り表示）を支える機能をMeta Computationとして実装する 59 TreeVNCのComputation（VNCサーバからデータを受け取り表示）を支える機能をMeta Computationとして実装する
85 60
90 * データの圧縮 65 * データの圧縮
91 66
92 # Meta Computationの追加 67 # Meta Computationの追加
93 * TreeVNCの数MByteの画面差分データを配信し続けるためデータを圧縮している 68 * TreeVNCの数MByteの画面差分データを配信し続けるためデータを圧縮している
94 * 画面データを圧縮して送る → 解凍して画面表示 → 再圧縮して子ノードへ転送 69 * 画面データを圧縮して送る → 解凍して画面表示 → 再圧縮して子ノードへ転送
95 * 再圧縮オーバーヘッドなしにゼロコピー転送する機能が必要 70 * 圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮 するオーバーヘッドを無くすことができる
96 * 圧縮のMeta Computationと転送のMeta Computationを追加した 71 * 圧縮のMeta Computationと転送のMeta Computationを追加した
97 72
98 # 圧縮表現(Meta DS)の追加 73 # 圧縮表現(Meta DS)の追加
99 * DSを複数作るのではなく、１つのDSに対しMeta DSとして以下の表現を同時に持たせる 74 * DSを複数作るのではなく、１つのDSに対しMeta DSとして以下の表現を同時に持たせる
100 75
101 <table style="border:none;"> 76 <table style="border:none;">
102 <tr><td> 77 <tr><td width="550px">
103 1. 一般的なJavaのオブジェクト<br> 78 1. 一般的なJavaのオブジェクト<br>
104 　　　　LocalDSMにputしたときの形式 <br> 79 　LocalDSMにputしたときの形式 <br>
105 2. MessagePackでシリアライズ化されたバイナリオブジェクト <br> 80 <br>
106 　　　　RemoteDSMにputしたときの形式 <br> 81 2. シリアライズ化されたバイナリオブジェクト <br>
107 3. 2をさらに圧縮したバイナリオブジェクト <br> 82 　RemoteDSMにputしたときの形式 <br>
108 　　　　今回追加した形式 <br> 83 <br>
84 3. 2を圧縮したバイナリオブジェクト <br>
85 　今回追加した形式 <br>
109 </td> 86 </td>
110 <td> 87 <td width="500px">
111 <img src="./pictures/compressDS.svg" width="90%"> 88 <img src="./pictures/compressDS.svg" width="100%">
112 </td> 89 </td>
113 </tr> 90 </tr>
114 </table> 91 </table>
115 92
116
117 # MessagePackとは
118 * Sadayuki Furuhashiが開発したシリアライズのための機能をまとめたオープンソースライブラリ。
119 * シリアライズ/デシリアライズを高速に行うことができ、整数、浮動小数点数、Boolean、文字列、配列、連想配列、nilをバイト列にシリアライズできる。
120 * JSONのようにプログラミング言語に依存しないデータの表現形式として使用できる。
121 93
122 94
123 # 圧縮表現を扱うDSMとAPIの追加 95 # 圧縮表現を扱うDSMとAPIの追加
124 * Local と Remote それぞれに圧縮表現を扱う Compressed DSM を追加 96 * Local と Remote それぞれに圧縮表現を扱う Compressed DSM を追加
125 * DSを圧縮したい場合は指定する DSM を Compressed DSM に変える 97 * DSを圧縮したい場合は指定する DSM を Compressed DSM に変える
128 put("Remote", "Key", val); 100 put("Remote", "Key", val);
129 put("compressedRemote", "Key", val); 　 101 put("compressedRemote", "Key", val); 　
130 ``` 102 ```
131 103
132 # 圧縮表現がオンデマンドに作られる 104 # 圧縮表現がオンデマンドに作られる
133 * NodeAでNodeBのcompressed RemoteDSM に対してDSをput
134 ![opt](./pictures/flow1.svg){:width="80%"}
135
136 # 圧縮表現がオンデマンドに作られる
137 * DS が圧縮表現を持っていなければCompressed DSM内部で圧縮表現を生成してput
138 ![opt](./pictures/flow2.svg){:width="80%"}
139
140 # 圧縮表現がオンデマンドに作られる
141 * RemoteDSMがAliceの送信パケットをNodeBのLocalDSMに送る
142 ![opt](./pictures/flow3.svg){:width="80%"}
143
144 # 圧縮表現がオンデマンドに作られる
145 * NodeBのLocalDSMでは圧縮表現のみのDSとして保存する
146 ![opt](./pictures/flow4.svg){:width="80%"}
147
148 # 圧縮表現がオンデマンドに作られる
149 * setKey()でtake/peekで呼ばれたらReceiverにDSが渡される
150 ![opt](./pictures/flow5.svg){:width="80%"}
151
152 # 圧縮表現がオンデマンドに作られる
153 * castメソッドである **asClass()** が解凍・デシリアライズされた表現を作って渡す
154 ![opt](./pictures/flow6.svg){:width="80%"}
155
156 # 圧縮表現がオンデマンドに作られる
157 * DS はオブジェクト表現と圧縮表現を同時にもつため、TreeVNCでは受け取った画面データを解凍した後、転送のためにコピーや再圧縮をすることはない。 105 * DS はオブジェクト表現と圧縮表現を同時にもつため、TreeVNCでは受け取った画面データを解凍した後、転送のためにコピーや再圧縮をすることはない。
158 * 複数表現は必要最低限にしか作られない。 106 * 複数表現は必要最低限にしか作られない。
159 * 一つのKeyに対し様々な表現のDSが対応するが、asClass()によってユーザーは送られてくるDSの表現を気にせず扱える。 107 * 一つのKeyに対し様々な表現のDSが対応するが、キャストメソッドであるasClass()によってユーザーは送られてくるDSの表現を気にせず任意の型で取り出せる。
160 108
161 # Meta Computationの評価 109 # Meta Computationの評価
162 TreeVNCとAliceVNCを比較した 110 TreeVNCとAliceVNCを比較した
163 111
164 * 性能比較 112 * 性能比較
166 同等の性能が実現できたか 114 同等の性能が実現できたか
167 * コード比較 115 * コード比較
168 コード量・コード複雑度を比較 116 コード量・コード複雑度を比較
169 シンプルな記述で仕様の変更が抑えられているか 117 シンプルな記述で仕様の変更が抑えられているか
170 118
171 # 性能比較 - 実験内容
172 * 木の段数ごとにメッセージの到達にどれぐらい時間がかかっているかを計測
173 * 講義内で学生に協力してもらい、最大 17 名の接続があった
174 ![](./pictures/delay.svg){:width="50%"}![](./pictures/delay2.svg){:width="50%"}
175
176 # 性能比較 - 実験結果 119 # 性能比較 - 実験結果
177 * 3段目の計測結果 120 * 3段目の計測結果
178 * 同じ傾向から同等の処理性能があることがわかった 121 * 同じ傾向から同等の処理性能があることがわかった
179 122
180 <table style="border:none;"> 123 <table style="border:none;">
219 </table> 162 </table>
220 163
221 # コード複雑度比較 164 # コード複雑度比較
222 * 循環的複雑度を用いる 165 * 循環的複雑度を用いる
223 コード内の線形独立な経路の数。if や forが多いほど複雑度が高い。 166 コード内の線形独立な経路の数。if や forが多いほど複雑度が高い。
224 * 計測にはIntelliJのプラグイン「MetricsReloaded」を使用
225 167
226 <table style="border-collapse: collapse;border:1px solid #000000;"> 168 <table style="border-collapse: collapse;border:1px solid #000000;">
227 <th style="border:1px solid #000000;padding:5px 15px 5px 15px;"></th> 169 <th style="border:1px solid #000000;padding:5px 15px 5px 15px;"></th>
228 <th style="border:1px solid #000000;padding:5px 15px 5px 15px;"> 平均値 </th> 170 <th style="border:1px solid #000000;padding:5px 15px 5px 15px;"> 平均値 </th>
229 <th style="border:1px solid #000000;padding:5px 15px 5px 15px;">最高値</th> 171 <th style="border:1px solid #000000;padding:5px 15px 5px 15px;">最高値</th>
250 * AliceVNCで最も複雑度が高いSwingViewerWindow.classは、TightVNCから変更がほとんどないため、AliceVNCの持っている複雑度はTightVNCが元来持っていた複雑度 192 * AliceVNCで最も複雑度が高いSwingViewerWindow.classは、TightVNCから変更がほとんどないため、AliceVNCの持っている複雑度はTightVNCが元来持っていた複雑度
251 193
252 194
253 195
254 # まとめ 196 # まとめ
255 * Alice が実用的なアプリケーションを記述するための Meta Computation として、Meta Data Segmentに複数の表現のデータを同時に持たせることで圧縮機能を実装した。 197 * Alice が実用的なアプリケーションを記述するための Meta Computation として、Meta Data Segmentに複数の表現のデータを同時に持たせることで圧縮機能を実装した。同様の手法を用いれば暗号表現などへの対応もでき自由度の高い通信を行うことが可能になる。
256 * TreeVNCをAlice上で実装し比較を行った結果、シンプルな記述でTreeVNCの基本機能を実現でき、同等の性能を出すことに成功した。 198 * TreeVNCをAlice上で実装し比較を行った結果、変更量の少ないシンプルな記述でTreeVNCの基本機能を実現でき、同等の性能を出すことに成功した。
257 * AliceのMeta Computationが信頼性の高い実 用的な分散アプリケーションの構築に有用であることが確認された。 199 * AliceのMeta Computationが拡張性・信頼性の高い実用的な分散アプリケーションの構築に有用であることが確認された。
200
201 # 今後の課題
202 * TreeVNCでは拡張が困難であった別ネットワーク間の通信もTopology Manager を用いれば容易に拡張できると考えられる
203 ![opt](./pictures/overNAT.svg){:width="60%"}
258 204
259 # 今後の課題 205 # 今後の課題
260 * APIの再設計 206 * APIの再設計
261 * put/updateに対しtake/peekがcreate()・setKey()の操作はわかりにくい 207 * put/updateに対しtake/peekがcreate()・setKey()の操作はわかりにくい
262 * DSの型情報のマネジメント 208 * DSの型情報のマネジメント
263 * 型情報がないのでpeek/takeする際にわかりにくい 209 * 型情報がないのでpeek/takeする際にわかりにくい
264 * セキュリティをサポートしていない 210 * セキュリティをサポートしていない
265 * 圧縮と同様の手法で暗号形式のデータ表現を扱えるように拡張可能 211 * 圧縮と同様の手法で暗号形式のデータ表現を扱えるように拡張可能
266 212
267 # 今後の課題 213
268 * TreeVNCでは拡張が困難であった別ネットワーク間の通信もTopology Manager を用いれば容易に拡張できると考えられる 214
269 ![opt](./pictures/overNAT.svg){:width="60%"}
270
271 # Dynamic Topology Manager
272 ![](./pictures/tree1.svg){:width="33%"}![](./pictures/tree2.svg){:width="33%"}![](./pictures/tree3.svg){:width="33%"}
273
274
275 # CodeSegment の 例
276 * RemoteDSM から DSをtakeし、LocalDSM に put を10回繰り返す　　
277 ![opt](./pictures/remoteTest.svg){:width="70%"}
278
279 # CodeSegment の 例
280 * RemoteDSM から DSをtakeし、LocalDSM に put を10回繰り返す
281 * CSはInputDSを持たないStartCSからはじまる
282 ![opt](./pictures/remoteTest2.svg){:width="70%"}
283
284 # StartCodeSegmentの例
285 ```java
286 public class RemoteStartCodeSegment extends CodeSegment {
287
288 @Override
289 public void run() {
290 RemoteIncrement cs = new RemoteIncrement();//CSを生成
291 ods.put("local", "num", 0);
292 }
293
294 }
295 ```
296
297 # StartCodeSegmentの例
298 ```java
299 public class RemoteStartCodeSegment extends CodeSegment {
300
301 @Override
302 public void run() {
303 RemoteIncrement cs = new RemoteIncrement();
304 ods.put("local", "num", 0);//DSをLocalDSMにput
305 }
306
307 }
308 ```
309
310 # CodeSegment の 例
311 ```java
312 public class RemoteIncrement extends CodeSegment {
313
314 public Receiver num = ids.create(CommandType.TAKE);//DSの受け皿を作る
315
316 public RemoteIncrement(){
317 num.setKey("remote", "num");
318 }
319
320 @Override
321 public void run() {
322 int n = num.asClass(Integer.class);
323 if (n == 10) System.exit(0);
324 RemoteIncrement cs = new RemoteIncrement();
325 ods.put("local", "num", ++n);
326 }
327
328 }
329 ```
330
331 # CodeSegment の 例
332 ```java
333 public class RemoteIncrement extends CodeSegment {
334
335 public Receiver num = ids.create(CommandType.TAKE);
336
337 public RemoteIncrement(){
338 num.setKey("remote", "num");//CSにInputDSをセット。待ち合わせが発生。
339 }
340
341 @Override
342 public void run() {
343 int n = num.asClass(Integer.class);
344 if (n == 10) System.exit(0);
345 RemoteIncrement cs = new RemoteIncrement();
346 ods.put("local", "num", ++n);
347 }
348
349 }
350 ```
351
352 # CodeSegment の 例
353 ```java
354 public class RemoteIncrement extends CodeSegment {
355
356 public Receiver num = ids.create(CommandType.TAKE);
357
358 public RemoteIncrement(){
359 num.setKey("remote", "num");
360 }
361
362 @Override
363 public void run() {
364 int n = num.asClass(Integer.class);//InputDSをキャストして取得
365 if (n == 10) System.exit(0);
366 RemoteIncrement cs = new RemoteIncrement();
367 ods.put("local", "num", ++n);
368 }
369
370 }
371 ```
372
373 # CodeSegment の 例
374 ```java
375 public class RemoteIncrement extends CodeSegment {
376
377 public Receiver num = ids.create(CommandType.TAKE);
378
379 public RemoteIncrement(){
380 num.setKey("remote", "num");
381 }
382
383 @Override
384 public void run() {
385 int n = num.asClass(Integer.class);
386 if (n == 10) System.exit(0);//num=10なら終了
387 RemoteIncrement cs = new RemoteIncrement();
388 ods.put("local", "num", ++n);
389 }
390
391 }
392
393 ```
394
395
396 # CodeSegment の 例
397 ```java
398 public class RemoteIncrement extends CodeSegment {
399
400 public Receiver num = ids.create(CommandType.TAKE);
401
402 public RemoteIncrement(){
403 num.setKey("remote", "num");
404 }
405
406 @Override
407 public void run() {
408 int n = num.asClass(Integer.class);
409 if (n == 10) System.exit(0);
410 RemoteIncrement cs = new RemoteIncrement();//次のCSを生成
411 ods.put("local", "num", ++n);
412 }
413
414 }
415 ```
416
417 # CodeSegment の 例
418 ```java
419 public class RemoteIncrement extends CodeSegment {
420
421 public Receiver num = ids.create(CommandType.TAKE);
422
423 public RemoteIncrement(){
424 num.setKey("remote", "num");
425 }
426
427 @Override
428 public void run() {
429 int n = num.asClass(Integer.class);
430 if (n == 10) System.exit(0);
431 RemoteIncrement cs = new RemoteIncrement();
432 ods.put("local", "num", ++n);//インクリメントしたDSをput
433 }
434
435 }
436 ```
437 215
438 216
439 <style type="text/css"> 217 <style type="text/css">
440 <!-- 218 <!--
441 *{ 219 *{