Mercurial > hg > Papers > 2018 > nozomi-master

comparison presen/sigOS/sample.markdown @ 175:7e7fe5e28ba4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add presen directory
author Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
date Mon, 05 Feb 2018 17:54:31 +0900
parents
children
comparison
equal deleted inserted replaced
174:f0e9cc7d13f9 175:7e7fe5e28ba4
1 title: 分散フレームワークAliceの圧縮機能
2 author: 照屋のぞみ
3 profile:琉球大学 工学部 情報工学科 4年
4
5 # 研究目的
6 * 当研究室が開発している並列分散フレームワークAliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。
7 * Aliceのメタ計算として、通信が切断した際の処理やデータを圧縮する処理等を提供することで、プログラマがコードを大きく変更することなくプログラムの振る舞いを変えることを可能にする。
8
9 # Data Segment と Code Segment
10 * Aliceではデータを **Data Segment(DS)** 、タスクを **Code Segment(CS)** という単位に分割してプログラミングを行う。
11 * AliceはJavaで実装されており、CS をユーザーが記述する際には CodeSegment.class を継承することで CS で使用する API を利用する事ができる。
12 * DSはAliceが内部にもつデータベースにより管理されており、CSはDSに対応する一意のkeyを使ってDSを操作する。
13
14 # Data Segment と Code Segment
15 * CSはInput DS(入力されるDS)とOutput DS(出力されるDS)を持つ。
16 * CSはkeyで指定されたDSが揃うと実行されるという性質を持つ。
17 ![opt](./images/dsandcs.svg)
18
19 # CodeSegmentの依存関係
20 * データの依存関係にないCSは並列実行される
21 * データの依存関係がある場合は Input DS が揃うと順に実行される
22 ![opt](./images/dsandcs2.svg)
23
24 # Data Segment
25 * 整数や文字列などの基本的なデータの集まり
26 * Aliceの場合はJavaオブジェクトに対応
27
28 # Data Segment Manager
29 * DS の集合体であるデータベースを Alice では DS Manager(DSM) と呼ぶ。
30 * DSM 内の DS には対になる String型のkey が存在し、 DSM 名と key を指定しすることで DS の保存、取得を行う。
31 * DS の追加
32 put(String managerKey, String key, Object val)
33 * DS の取得
34 take(String managerKey, String key)
35
36 <!--![opt](./images/dsm.svg)-->
37
38 # Data Segment Manager
39 * Local DSM … 各ノード固有のデータベース。
40 * Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在する。
41 ![opt](./images/remote_datasegment.svg){:width="450px"}
42
43
44 # Data Segment の表現
45 * DSは複数の表現を同時に持っており、現在は3種類の表現がある。
46 1. 一般的な Java のクラスオブジェクト
47 2. MessagePack for Java でシリアライズ化されたバイナリオブジェクト。Remoteとの通信の際に用いる。
48 3. 2 を圧縮したバイナリオブジェクト。圧縮機能の一部として今回追加。
49
50 # MessagePackとは
51 * Sadayuki Furuhashiが開発したシリアライズのための機能をまとめたオープンソースライブラリ。
52 * シリアライズ/デシリアライズを高速に行うことができ、整数、浮動小数点数、Boolean、文字列、配列、連想配列、nilをバイト列にシリアライズできる。
53 * JSONのようにプログラミング言語に依存しないデータの表現形式として使用できる。
54
55 # CS と Input DS の対応付け
56 * setKey()にtakeコマンドをセットすることで Input DS を指定する
57 * 実際にtakeしたデータを参照するときには、asClass()を用いて任意のJavaのオブジェクトとして扱えるようにする
58
59 # CS の 例
60 RemoteDSM から DSをtakeし、LocalDSM に put を10回繰り返す
61 ```java
62 public class RemoteIncrement extends CodeSegment {
63
64 public Receiver num = ids.create(CommandType.TAKE);
65
66 @Override
67 public void run() {
68 int num = this.num.asClass(Integer.class);
69 if (num == 10) System.exit(0);
70
71 RemoteIncrement cs = new RemoteIncrement();
72 cs.num.setKey("remote", "num");
73
74 ods.put("local", "num", num);
75 }
76
77 }
78 ```
79
80 # TreeVNC
81 * Aliceを用いて実装する実用的な分散プログラムの例題
82 * 当研究室で開発したノードを木構造に配置して負荷分散を行う授業向け画面共有システム
83 * TightVNCがもとになっている
84 ![opt](./images/treeVNC.svg)
85
86 # Computation
87 * Aliceでは、計算の本質的な処理をComputatin、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。
88 * Alice の Computationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理。
89 * TreeVNC の Computationは、VNCサーバからデータを受け取って表示する処理。
90
91 # Meta Computation
92 * 通信の切断・再接続時の処理や分散トポロジーの構成、データの表現形式の選択など、Computationを支えている処理。
93 * TreeVNCの場合、VNCサーバのデータを各VNCノードにコピーする処理。
94 * Aliceの機能を追加するということは Meta Computation を追加すると言い換えられる
95
96 # TreeVNCで用いるAliceのMeta Computation
97 * TreeTopologyの構成
98 * ノード間通信の切断時・再接続時の処理
99 * データの圧縮
100 * 子ノードへのデータの複製
101
102
103 # データの転送 - DSMとAPIの追加
104 * Local と Remote それぞれに圧縮表現を扱う Compressed DSM を追加。
105 * 指定する DSM を Compressed DSM に変えるだけで扱うデータ表現を変更できる
106 put(String **"compressed"** + managerKey, String key, Object val)
107 take(String **"compressed"** + managerKey, String key)
108
109 # データの転送 - データ表現の自動生成
110 * DS が圧縮表現を持っていれはそれをそのまま子ノードにputする
111 * 持っていなければその時点でCompressed DSM内部で圧縮表現を生成してputする
112 * DS はオブジェクト表現と圧縮表現を同時にもつため、TreeVNCでは受け取った画面データを伸長をした後、転送のために再圧縮することはない。
113
114 # データの受け取り - 任意の形式での取得
115 * 圧縮表現で画面データ受け取り、Compressed DSM 内に格納。
116 * TightVNCが画面表示のためにデータを必要としたときに、 asClass() を用いて任意の形式でデータを取り出す。
117 * asClass() は DS のcastメソッドであり、内部で伸長と MessagePack での変換を行う。
118
119 # データの受け取り - Aliceの通信パケット変更
120 * 通信ヘッダにデータの状態を表すフラグを追加したことで、受け取ったデータを適切な形式でDSM内に格納できる。
121 * 圧縮前と圧縮後のデータサイズを入れたことにより、受け取ったデータの適切な伸長が可能。
122
123 <table style="border-collapse: collapse;border:1px solid #000000;">
124 <td style="border:1px solid #000000;"> serialized </td>
125 <td style="border:1px solid #000000;">データ本体のシリアライズ状態を示す</td>
126 </tr>
127 <tr>
128 <td style="border:1px solid #000000;"> compressed </td>
129 <td style="border:1px solid #000000;">データ本体の圧縮状態を示す</td>
130 </tr>
131 <tr>
132 <td style="border:1px solid #000000;"> objectDataSize </td>
133 <td style="border:1px solid #000000;">圧縮前のオブジェクトのデータサイズを表す</td>
134 </tr>
135 <tr>
136 <td style="border:1px solid #000000;"> dataSize </td>
137 <td style="border:1px solid #000000;">送信するDSのデータサイズを表す</td>
138 </tr>
139 </table>
140
141 # Aliceと他言語等との比較(1) - Erlang
142 * ネットワークに依存しない通信が可能
143
144 * Topologyは自分で管理
145
146 # Aliceと他言語等との比較(1) - Linda
147 * keyでタプルというデータの集合を管理している
148 * in/outでAliceのput/takeに対応する操作を行う
149
150 * タスクはinで単一のタプルを待つ
151 * MetaComputationがない
152
153 # Aliceと他言語等との比較(1) - Corba
154 * オブジェクト間のRPC
155
156 * DSがない。keyという概念がない。
157 * データの待ち合わせがない
158
159 # Aliceと他言語等との比較(1) - HTTP
160 * get/putで通信を行う
161 * URLがデータベースのkeyとなる
162
163 * MIME形式で送信。複数の表現を持つMeta Computationがない。
164 * セッション管理はクライアント自身がやる
165 * 並列処理できない
166 * get/putをRPC的に扱わない
167
168
169 # TreeVNCとAliceを用いたTreeVNCの比較
170 * TreeVNC
171 通信プロトコルを定義や圧縮を自前で行う
172 通信スレッドを複数作成
173 様々な部分で通信APIを呼び出す
174
175 * Aliceを用いたTreeVNC
176 Aliceと接続する最小限の変更
177 木の構成部分や圧縮形式での通信はMeta Computation
178
179 # TreeVNCとAliceを用いたTreeVNCの比較
180 * TightVNCからのコードの増加量
181 * Aliceを用いれば通常の TreeVNC の 20% の行数で記述できる。
182
183 <table style="border-collapse: collapse;border:1px solid #000000;">
184 <th style="border:1px solid #000000;padding:5px 15px 5px 15px;"></th>
185 <th style="border:1px solid #000000;padding:5px 15px 5px 15px;"> 行数 </th>
186 <th style="border:1px solid #000000;padding:5px 15px 5px 15px;">単語数</th>
187 <tr>
188 <td style="border:1px solid #000000;padding:5px 15px 5px 15px;"> TreeVNC </td>
189 <td style="border:1px solid #000000;padding:5px 15px 5px 15px;">5049</td>
190 <td style="border:1px solid #000000;padding:5px 15px 5px 15px;">14191</td>
191 </tr>
192 <tr>
193 <td style="border:1px solid #000000;padding:5px 15px 5px 15px;"> Aliceを用いたTreeVNC </td>
194 <td style="border:1px solid #000000;padding:5px 15px 5px 15px;">989</td>
195 <td style="border:1px solid #000000;padding:5px 15px 5px 15px;">2355</td>
196 </tr>
197 </table>
198
199 # まとめ
200 * Alice が実用的なアプリケーションを記述するための Meta Computation として、データに多態性を持たせ、指定するDSMによってデータ表現を変える機能を実装した。
201 * これによりユーザが記述する Computation 部分を大きく変えずに自由度の高い通信を行うことが可能になった。
202 * 同様の手法により、暗号形式・JSON 形式など複数のデータ表現を扱えるように拡張できる。
203 * 今後の課題としては、圧縮機能を TreeVNC で用 いることで有効性を測る必要がある。