Mercurial > hg > Papers > 2016 > nozomi-thesis
diff presen/sample.markdown @ 10:90aaf305aed6 default tip
add presen
author | Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 18 Feb 2016 09:06:13 +0900 |
parents | b2869724949d |
children |
line wrap: on
line diff
--- a/presen/sample.markdown Wed Feb 17 20:35:54 2016 +0900 +++ b/presen/sample.markdown Thu Feb 18 09:06:13 2016 +0900 @@ -1,29 +1,28 @@ -title: 分散フレームワークAliceのPC画面配信システムへの応用 -author: 照屋のぞみ 河野真治 -profile:琉球大学 工学部 情報工学科 +title: 分散フレームワークAliceのMeta Data Segment +author: 照屋のぞみ +profile:琉球大学 工学部 情報工学科 河野研 # 研究目的(1/3) -* 当研究室が開発している並列分散フレームワークAliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。 -* ここで言う信頼性とは定められた環境下で安定して仕様に従った動作を行うことを指す。 -* Aliceでは当研究室が提案しているデータを Data Segment、タスクを Code Segment という単位で分割して記述するプログラミング手法を採用している。 +* 当研究室が開発している並列分散フレームワークAliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する +* ここで言う信頼性とは定められた環境下で安定して仕様に従った動作を行うことを指す +* Aliceでは当研究室が提案しているデータを Data Segment、タスクを Code Segment という単位で分割して記述するプログラミング手法を採用している # 研究目的(2/3) -* Aliceでは、処理をComputationとMetaComputationに階層化し、コアな仕様と複雑な例外処理に分離する。 +* Aliceでは、ComputationとMetaComputationに階層化し、コアな仕様と複雑な例外処理に分離する。 * 分散環境構築などの複雑な処理はAliceがMeta Computationとして提供する -* 仕様を大きく変更することなくプログラムの挙動が変えられる -* 変更前の信頼性を保ったまま拡張可能にする +* コードの変更を抑え、変更前の信頼性を保ったまま拡張可能にする # 研究目的(3/3) -* 本研究では、 Alice上に実用的な分散アプリケーションが制作できることを示すために画面配信システムTreeVNCを構築する。 -* 構築するにあたり必要となった圧縮機能をAliceのMeta Computationとして実装した。 -* もとのTreeVNCとの比較を行うことでMetaComputationの役割と有効性を示す。 +* 本研究では、Alice上に実用的な分散アプリケーションが制作できることを示すために画面配信システムTreeVNCを構築する +* 構築するにあたり必要となった圧縮機能をAliceのMeta Computationとして実装した +* もとのTreeVNCとの比較を行うことでMeta Computationの役割と有効性を示す # Data Segment と Code Segment * Aliceではデータを **Data Segment(DS)** 、タスクを **Code Segment(CS)** という単位に分割して依存関係を記述することでプログラミングを行う。 * CSはInput DS(入力されるDS)とOutput DS(出力されるDS)を持つ。 -* CSはkeyで指定されたDSが揃うと実行されるという性質を持つ。 -![opt](./images/dsandcs.svg){:width="60%"} +* CSはkeyで指定されたDSが全て揃うと実行されるという性質を持つ。 +![opt](./images/dsandcs.svg){:width="50%"} # CodeSegmentの依存関係 * データの依存関係にないCSは並列実行される @@ -31,38 +30,18 @@ * DSはCSに専有されるためロックの記述を必要としない ![opt](./images/dsandcs2.svg){:width="60%"} -# Data Segment と CodeSegment -* AliceはJavaで実装されており、DSはJava-Object、CSはRunnableに相当する -* ユーザーが記述する際には CodeSegment.class を継承することでDSを操作するためのAPIを利用して依存関係を記述することができる。 -* DSはAliceが内部にもつデータベース(DS Manager)により管理されており、CSはDSに対応する一意のkeyを使ってDSを操作する。 - # Data Segment Manager -* DS の集合体であるデータベースを Alice では **DS Manager(DSM)** と呼ぶ。 +* DS の集合体であるデータベースを **DS Manager(DSM)** と呼ぶ。 + * Local DSM … 各ノード固有のデータベース。 + * Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在する。 * DSM 内の DS には対になる String型のkey が存在し、 DSM 名と key を指定しすることで DS の保存、取得を行う。 -* keyに対して複数のDSを保存する際はFIFO的に処理される -![opt](./images/KeyDS.svg){:width="50%"} - -# Data Segment Manager -* Local DSM … 各ノード固有のデータベース。 -* Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在する。 ![opt](./images/remote_datasegment.svg){:width="50%"} -# Data Segment API -* DS の追加 - * put(String managerKey, String key, Object val) - * update(String managerKey, String key, Object val) ※先頭DSを削除してからput - * flip(String managerKey, String key, Receiver receiver) ※ゼロコピー転送用 -* DS の取得 - * take(String managerKey, String key) - * peek(String managerKey, String key) ※DSMから削除されない - -* take/peekは実際にはcreate()とsetKey()によって行われる -* create()でDSの受け皿を作っておき、setKey()にkeyをセットすることで Input DS を指定する # Computation と Meta Computation * Aliceでは、計算の本質的な処理をComputatin、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。 -* Alice のComputationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理。 -* 分散トポロジーの構成、通信の切断・再接続時の処理やデータの表現形式の選択など、Computationを支えている処理。 +* 分散トポロジーの構成、通信の切断・再接続時の処理などはMeta ComputationとしてAliceが提供 +* プログラマは目的の処理だけ記述し通信部分などはMeta Computationを指定することでシンプルな記述を実現 # Computation と Meta Computation * DS/CSの接続の間にMeta Computationが実行されている @@ -70,14 +49,10 @@ * Meta ComputationはCS の処理を支えるMeta CSとMeta CSに管理されるMeta DSに分けられる ![opt](./pictures/MetaCSDS.svg){:width="70%"} -# Computation と Meta Computation -* 分散環境構築などの複雑な処理をAliceがMeta Computationとして提供する -* プログラマは目的の処理だけ記述し通信部分などはMeta Computationを指定する -# TreeVNC -* Aliceを用いて実装する実用的な分散プログラムの例題 -* 当研究室で開発したノードを木構造に配置して負荷分散を行う授業向け画面共有システム -* TightVNCがもとになっている +# TreeVNCへの応用 +* AliceのMeta Computationの有効性を示すため実用的な例題であるTreeVNCを実装する +* TightVNCをもとにした木構造画面配信システム * 画面処理や分散処理が混在する複雑なTreeVNCも、Aliceを用いればTightVNCからの変更が少ない見通しの良い記述で構成可能 # TreeVNCで必要な機能 @@ -92,33 +67,30 @@ # Meta Computationの追加 * TreeVNCの数MByteの画面差分データを配信し続けるためデータを圧縮している * 画面データを圧縮して送る → 解凍して画面表示 → 再圧縮して子ノードへ転送 -* 再圧縮オーバーヘッドなしにゼロコピー転送する機能が必要 +* 圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮 するオーバーヘッドを無くすことができる * 圧縮のMeta Computationと転送のMeta Computationを追加した # 圧縮表現(Meta DS)の追加 * DSを複数作るのではなく、1つのDSに対しMeta DSとして以下の表現を同時に持たせる <table style="border:none;"> -<tr><td> +<tr><td width="550px"> 1. 一般的なJavaのオブジェクト<br> - LocalDSMにputしたときの形式 <br> -2. MessagePackでシリアライズ化されたバイナリオブジェクト <br> - RemoteDSMにputしたときの形式 <br> -3. 2をさらに圧縮したバイナリオブジェクト <br> - 今回追加した形式 <br> + LocalDSMにputしたときの形式 <br> +<br> +2. シリアライズ化されたバイナリオブジェクト <br> + RemoteDSMにputしたときの形式 <br> +<br> +3. 2を圧縮したバイナリオブジェクト <br> + 今回追加した形式 <br> </td> -<td> -<img src="./pictures/compressDS.svg" width="90%"> +<td width="500px"> +<img src="./pictures/compressDS.svg" width="100%"> </td> </tr> </table> -# MessagePackとは -* Sadayuki Furuhashiが開発したシリアライズのための機能をまとめたオープンソースライブラリ。 -* シリアライズ/デシリアライズを高速に行うことができ、整数、浮動小数点数、Boolean、文字列、配列、連想配列、nilをバイト列にシリアライズできる。 -* JSONのようにプログラミング言語に依存しないデータの表現形式として使用できる。 - # 圧縮表現を扱うDSMとAPIの追加 * Local と Remote それぞれに圧縮表現を扱う Compressed DSM を追加 @@ -130,33 +102,9 @@ ``` # 圧縮表現がオンデマンドに作られる -* NodeAでNodeBのcompressed RemoteDSM に対してDSをput -![opt](./pictures/flow1.svg){:width="80%"} - -# 圧縮表現がオンデマンドに作られる -* DS が圧縮表現を持っていなければCompressed DSM内部で圧縮表現を生成してput -![opt](./pictures/flow2.svg){:width="80%"} - -# 圧縮表現がオンデマンドに作られる -* RemoteDSMがAliceの送信パケットをNodeBのLocalDSMに送る -![opt](./pictures/flow3.svg){:width="80%"} - -# 圧縮表現がオンデマンドに作られる -* NodeBのLocalDSMでは圧縮表現のみのDSとして保存する -![opt](./pictures/flow4.svg){:width="80%"} - -# 圧縮表現がオンデマンドに作られる -* setKey()でtake/peekで呼ばれたらReceiverにDSが渡される -![opt](./pictures/flow5.svg){:width="80%"} - -# 圧縮表現がオンデマンドに作られる -* castメソッドである **asClass()** が解凍・デシリアライズされた表現を作って渡す -![opt](./pictures/flow6.svg){:width="80%"} - -# 圧縮表現がオンデマンドに作られる * DS はオブジェクト表現と圧縮表現を同時にもつため、TreeVNCでは受け取った画面データを解凍した後、転送のためにコピーや再圧縮をすることはない。 * 複数表現は必要最低限にしか作られない。 -* 一つのKeyに対し様々な表現のDSが対応するが、asClass()によってユーザーは送られてくるDSの表現を気にせず扱える。 +* 一つのKeyに対し様々な表現のDSが対応するが、キャストメソッドであるasClass()によってユーザーは送られてくるDSの表現を気にせず任意の型で取り出せる。 # Meta Computationの評価 TreeVNCとAliceVNCを比較した @@ -168,11 +116,6 @@ コード量・コード複雑度を比較 シンプルな記述で仕様の変更が抑えられているか -# 性能比較 - 実験内容 -* 木の段数ごとにメッセージの到達にどれぐらい時間がかかっているかを計測 -* 講義内で学生に協力してもらい、最大 17 名の接続があった -![](./pictures/delay.svg){:width="50%"}![](./pictures/delay2.svg){:width="50%"} - # 性能比較 - 実験結果 * 3段目の計測結果 * 同じ傾向から同等の処理性能があることがわかった @@ -221,7 +164,6 @@ # コード複雑度比較 * 循環的複雑度を用いる コード内の線形独立な経路の数。if や forが多いほど複雑度が高い。 -* 計測にはIntelliJのプラグイン「MetricsReloaded」を使用 <table style="border-collapse: collapse;border:1px solid #000000;"> <th style="border:1px solid #000000;padding:5px 15px 5px 15px;"></th> @@ -252,9 +194,13 @@ # まとめ -* Alice が実用的なアプリケーションを記述するための Meta Computation として、Meta Data Segmentに複数の表現のデータを同時に持たせることで圧縮機能を実装した。 -* TreeVNCをAlice上で実装し比較を行った結果、シンプルな記述でTreeVNCの基本機能を実現でき、同等の性能を出すことに成功した。 -* AliceのMeta Computationが信頼性の高い実 用的な分散アプリケーションの構築に有用であることが確認された。 +* Alice が実用的なアプリケーションを記述するための Meta Computation として、Meta Data Segmentに複数の表現のデータを同時に持たせることで圧縮機能を実装した。同様の手法を用いれば暗号表現などへの対応もでき自由度の高い通信を行うことが可能になる。 +* TreeVNCをAlice上で実装し比較を行った結果、変更量の少ないシンプルな記述でTreeVNCの基本機能を実現でき、同等の性能を出すことに成功した。 +* AliceのMeta Computationが拡張性・信頼性の高い実用的な分散アプリケーションの構築に有用であることが確認された。 + +# 今後の課題 +* TreeVNCでは拡張が困難であった別ネットワーク間の通信もTopology Manager を用いれば容易に拡張できると考えられる +![opt](./pictures/overNAT.svg){:width="60%"} # 今後の課題 * APIの再設計 @@ -264,176 +210,8 @@ * セキュリティをサポートしていない * 圧縮と同様の手法で暗号形式のデータ表現を扱えるように拡張可能 -# 今後の課題 -* TreeVNCでは拡張が困難であった別ネットワーク間の通信もTopology Manager を用いれば容易に拡張できると考えられる -![opt](./pictures/overNAT.svg){:width="60%"} - -# Dynamic Topology Manager -![](./pictures/tree1.svg){:width="33%"}![](./pictures/tree2.svg){:width="33%"}![](./pictures/tree3.svg){:width="33%"} -# CodeSegment の 例 -* RemoteDSM から DSをtakeし、LocalDSM に put を10回繰り返す -![opt](./pictures/remoteTest.svg){:width="70%"} - -# CodeSegment の 例 -* RemoteDSM から DSをtakeし、LocalDSM に put を10回繰り返す -* CSはInputDSを持たないStartCSからはじまる -![opt](./pictures/remoteTest2.svg){:width="70%"} - -# StartCodeSegmentの例 -```java -public class RemoteStartCodeSegment extends CodeSegment { - - @Override - public void run() { - RemoteIncrement cs = new RemoteIncrement();//CSを生成 - ods.put("local", "num", 0); - } - -} -``` - -# StartCodeSegmentの例 -```java -public class RemoteStartCodeSegment extends CodeSegment { - - @Override - public void run() { - RemoteIncrement cs = new RemoteIncrement(); - ods.put("local", "num", 0);//DSをLocalDSMにput - } - -} -``` - -# CodeSegment の 例 -```java -public class RemoteIncrement extends CodeSegment { - - public Receiver num = ids.create(CommandType.TAKE);//DSの受け皿を作る - - public RemoteIncrement(){ - num.setKey("remote", "num"); - } - - @Override - public void run() { - int n = num.asClass(Integer.class); - if (n == 10) System.exit(0); - RemoteIncrement cs = new RemoteIncrement(); - ods.put("local", "num", ++n); - } - -} -``` - -# CodeSegment の 例 -```java -public class RemoteIncrement extends CodeSegment { - - public Receiver num = ids.create(CommandType.TAKE); - - public RemoteIncrement(){ - num.setKey("remote", "num");//CSにInputDSをセット。待ち合わせが発生。 - } - - @Override - public void run() { - int n = num.asClass(Integer.class); - if (n == 10) System.exit(0); - RemoteIncrement cs = new RemoteIncrement(); - ods.put("local", "num", ++n); - } - -} -``` - -# CodeSegment の 例 -```java -public class RemoteIncrement extends CodeSegment { - - public Receiver num = ids.create(CommandType.TAKE); - - public RemoteIncrement(){ - num.setKey("remote", "num"); - } - - @Override - public void run() { - int n = num.asClass(Integer.class);//InputDSをキャストして取得 - if (n == 10) System.exit(0); - RemoteIncrement cs = new RemoteIncrement(); - ods.put("local", "num", ++n); - } - -} -``` - -# CodeSegment の 例 -```java -public class RemoteIncrement extends CodeSegment { - - public Receiver num = ids.create(CommandType.TAKE); - - public RemoteIncrement(){ - num.setKey("remote", "num"); - } - - @Override - public void run() { - int n = num.asClass(Integer.class); - if (n == 10) System.exit(0);//num=10なら終了 - RemoteIncrement cs = new RemoteIncrement(); - ods.put("local", "num", ++n); - } - -} - -``` - - -# CodeSegment の 例 -```java -public class RemoteIncrement extends CodeSegment { - - public Receiver num = ids.create(CommandType.TAKE); - - public RemoteIncrement(){ - num.setKey("remote", "num"); - } - - @Override - public void run() { - int n = num.asClass(Integer.class); - if (n == 10) System.exit(0); - RemoteIncrement cs = new RemoteIncrement();//次のCSを生成 - ods.put("local", "num", ++n); - } - -} -``` - -# CodeSegment の 例 -```java -public class RemoteIncrement extends CodeSegment { - - public Receiver num = ids.create(CommandType.TAKE); - - public RemoteIncrement(){ - num.setKey("remote", "num"); - } - - @Override - public void run() { - int n = num.asClass(Integer.class); - if (n == 10) System.exit(0); - RemoteIncrement cs = new RemoteIncrement(); - ods.put("local", "num", ++n);//インクリメントしたDSをput - } - -} -``` <style type="text/css">