Mercurial > hg > Papers > 2015 > nozomi-sigos
comparison presen/sigOS/sample.markdown @ 18:20c9082b212d
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 形式など複数のデータ表現を扱えるように拡張できる。 |