Mercurial > hg > Papers > 2015 > nozomi-sigos

comparison presen/sigOS/sample.markdown @ 18:20c9082b212d

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