# HG changeset patch # User Nozomi Teruya # Date 1446125001 -32400 # Node ID 044cd3cfabc5d5dad3f457c5514063d1eb45b92d # Parent 4f6ec742600707f61fdbdb65143b6337d6e0c03f last fix diff -r 4f6ec7426007 -r 044cd3cfabc5 Makefile --- a/Makefile Thu Oct 29 17:33:24 2015 +0900 +++ b/Makefile Thu Oct 29 22:23:21 2015 +0900 @@ -4,7 +4,7 @@ LATEX=platex BIBTEX=pbibtex -DVIPDF=dvipdfmx +DVIPDF=dvipdfmx -p a4 #You need setting "-l" option if You think You get a landscape PDF #DVIPDF_OPT=-l diff -r 4f6ec7426007 -r 044cd3cfabc5 midterm.pdf Binary file midterm.pdf has changed diff -r 4f6ec7426007 -r 044cd3cfabc5 midterm.tex --- a/midterm.tex Thu Oct 29 17:33:24 2015 +0900 +++ b/midterm.tex Thu Oct 29 22:23:21 2015 +0900 @@ -24,21 +24,19 @@ \maketitle \thispagestyle{fancy} -\section{研究目的} -当研究室ではデータをData Segment、タスクをCode Segmentという単位で分割して記述する分散フレームワークAliceの開発を行っている。Aliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。 - ここで言う信頼性とは定められた環境下で安定して仕様に従った動作を行うことを指す。 - Aliceでは、処理をComputationとMetaComputationに階層化し、コアな仕様と複雑な例外処理に分離する。 +\section{Meta Computationによる分散プログラミングの信頼性向上} +当研究室ではデータをData Segment、タスクをCode Segmentという単位で記述する分散フレームワークAliceの開発を行っている。Aliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。 + ここで言う信頼性とは、定められた環境下で安定して仕様に従った動作を行うことを指す。 + Aliceでは、処理をComputationとMeta Computationに階層化し、コアな仕様と複雑な例外処理に分離する。 仕様の変更を抑えながらプログラムの挙動を変えさせることにより分散アプリケーションの信頼性向上をめざす。 -本研究では、 Alice上に実用的なアプリケーションである画面共有システムTreeVNC\cite{1}を構築する。構築するにあたり必要となった転送・圧縮などの機能を AliceのMeta Computation として実装する。そしてAliceを使用していないTreeVNCとの比較を行うことでMetaComputationの役割と有効性を示す。 +本研究では、 Alice上に実用的なアプリケーションである画面共有システムTreeVNC\cite{1}を構築する。構築するにあたり必要となった圧縮などの機能を AliceのMeta Computation として実装する。そしてAliceを使用していないTreeVNCとの比較を行うことでMetaComputationの役割と有効性を示す。 \section{分散フレームワーク Alice の概要} -AliceはデータをData Segment（以下DS）、タスクをとCode Segment（以下CS）という単位に分割してプログラミングを行う。 -DSはAliceが内部にもつデータベースによって管理されている。DSに対応する一意のkeyが設定されており、そのkeyを用いてデータベースを操作する。 +AliceではCode Segment（以下CS）とData Segment（以下DS）の依存関係を記述することでプログラミングを行う。 -CSは実行に必要なDSが揃うと実行されるという性質を持ち、入力されたDSに応じた結果が出力される。 -CSを実行するために必要な入力DSはInputDS、CSが計算を行った後に出力されるDSはOutput DSと呼ばれる。データの依存関係にないCSは並列実行が可能である。（図\ref{fig:CS}） -実際にはAliceはJavaで実装されており、DSはJavaObjectでCSはRannableThreadである。 +CSは実行に必要なDSが全て揃うと実行される。CSを実行するために必要な入力DSはInputDS、CSが計算を行った後に出力されるDSはOutput DSと呼ばれる。データの依存関係にないCSは並列実行が可能である。（図\ref{fig:CS}） +CSの実行においてDSが他のCSから変更を受けることはない。そのためAliceではデータが他から変更され整合性がとれなくなることはない。 \begin{figure}[htbp] \begin{center} @@ -48,15 +46,13 @@ \label{fig:CS} \end{figure} -\subsection*{[Data Segment]} -Aliceはデータを分割して記述する。その分割されたデータをDSと呼ぶ。 -実際には整数や文字列などの基本的なデータの集まりのことを指し、Aliceの場合はJavaオブジェクトに対応する。 -CSの実行においてDSが他のCSから変更を受けることはない。そのためAliceではデータが他から変更され整合性がとれなくなることはない。 +DSはAliceが内部にもつデータベースによって管理されている。DSの保存・取得にはAliceが提供するAPIを用いる。 +DSを管理するデータベースをAliceではDS Manager（以下DSM）と呼ぶ。 +DSには対になるString型のkeyが存在し、このkeyを指定してDSの保存・取得を行う。 +一つのkeyに対して複数のDSを登録することもでき、その場合DSはqueueに保存されFIFOで取り出される。 -\subsection*{[Data Segment Manager]} -DSは実際にはqueueに保存される。queueには対になるkeyが存在し、keyの数だけqueueが存在する。 -このkeyを指定してDSの保存、取得を行う。queueの集合体はデータベースとして捉えられる。このデータベースをAliceではDS Manager（以下DSM）と呼ぶ。DSMにはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。Remote DSMは他のノードのLocal DSMのproxyであり、接続しているノードの数だけ存在する。（図\ref{fig:RemoteDSM}）Remote DSMに対して書き込むと対応するノードのLocal DSMに書き込まれる。 +DSMにはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。他ノードのLocal DSMに書き込みたい場合はRemote DSMに対して書き込む。Remote DSMは他ノードのLocal DSMに対応するproxyであり、接続しているノードの数だけ存在する。（図\ref{fig:RemoteDSM}） \begin{figure}[htbp] \begin{center} @@ -66,34 +62,49 @@ \label{fig:RemoteDSM} \end{figure} -\subsection*{[ComputationとMeta Computation]} + +実際にはAliceはJavaで実装されており、DSはJavaObjectでCSはRannableThreadである。プログラマーがCSを記述する際は、CodeSegmentクラスを継承し、DSを操作するAPIを使用する。 + + +\section{AliceのMeta Computation} Aliceでは、計算の本質的な処理をComputation、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。 Alice の Computationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理と捉えられる。 それに対して、Alice の Meta Computation は、Remoteノードとの通信時のトポロジーの構成や切断・再接続の処理と言える。つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。 -プログラマーはCSを記述する際にトポロジーや切断、再接続という状況を予め想定した処理にする必要はない。プログラマーは目的の処理だけ記述する。そして、切断や再接続が起こった場合の処理を記述しMeta Computationで指定する。このようにプログラムすることで、通常処理と例外処理を分離することができるため、シンプルなプログラムを記述できる。 +プログラマーはCSを記述する際にトポロジーや切断、再接続という状況を予め想定した処理にする必要はない。プログラマーは目的の処理だけ記述する。そして、切断や再接続が起こった場合の処理をMeta Computationで指定する。このようにプログラムすることで、通常処理と例外処理を分離することができるため、シンプルなプログラムを記述できる。 Aliceの機能を追加するということは Meta Computation を追加すると言い換えられる。 \section{AliceVNC} AliceのMeta Computationが実用的なアプリケーションの記述において有用であることを確認する。 そのために、TreeVNCをAliceを用いて実装したAliceVNCの作成を行った。 + TreeVNCとは、当研究室開発を行っている授業向け画面共有システムである。 授業でVNCを使う場合、１つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう。 -この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである。 +この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである。（図\ref{fig:TreeVNC}） + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=50mm]{images/treestructure.pdf} +\end{center} +\caption{TreeVNC, AliceVNC の構造} +\label{fig:TreeVNC} +\end{figure} + TreeVNCは通信処理部分の記述が大変複雑である。しかし、Aliceで記述すれば本質的な処理とそれを支える通信処理部分で分離できるため、シンプルな記述で構成可能と期待される。 \section{Alice に追加したMetaComputation(圧縮機能)} AliceVNCで使用するAliceのMetaComputationの一つが圧縮機能である。 TreeVNCでは画面配信の際、データを圧縮してノード間通信を行っている。 そのため、AliceVNCにも圧縮されたデータ形式を扱える機能が必要だと考えた。 + +\newpage しかし、ただデータを圧縮する機構を追加すればいいわけではない。 - AliceVNCでは、ノードは受け取った画面データを描画すると同時に、子ノードのRemote DSMに送信する。 ノードはDSを受信するとそれを一度解凍して画面を表示し、再圧縮して子ノードに送信する。 しかし、受け取ったデータを自分の子ノードに対して送信する際には、解凍する必要はない。 圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる。 -そこで、１つのData Segmentに対し複数の表現を持たせることで、必要に応じた形式でDSを扱うことを可能にした。 +そこで、１つのDSに対し複数の表現を持たせることで、必要に応じた形式でDSを扱うことを可能にした。 DSを扱うクラスに、次の3種類の表現を同時に持つことができる。 \begin{enumerate} @@ -103,21 +114,18 @@ \end{enumerate} 1はLocalDSMにDSを保存する場合に用いる。また、圧縮せずにRemoteDSMにDSを保存する場合は2のMessagePack形式で送られる。そしてLocal, Remote に対しDSを圧縮して保存する場合は3を用いる。 -さらに、圧縮状態を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerの追加した。Compressed DSMの内部では、DSが呼ばれた際に圧縮表現を持っていればそれを使用し、持っていなければその時点で圧縮表現を作って操作を行う。 +圧縮状態を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed DSMの追加した。Compressed DSMの内部では、DSが呼ばれた際に圧縮表現を持っていればそれを使用し、持っていなければその時点で圧縮表現を作って操作を行う。 これによりユーザは指定するDSMを変えるだけで、他の計算部分を変えずに圧縮表現を持つDSを扱うことができる。ノードは圧縮されたDSを受け取った後、そのまま子ノードに転送すれば圧縮状態のまま送信されるので、送信の際の再圧縮がなくなる。 \section{まとめ} -並列分散フレームワークAliceの計算モデルと実装について説明を行い、Aliceにおけるプログラミング手法を述べた。 - Aliceが実用的なアプリケーションを記述するために必要なMeta Computationとして、データの多態性を実現し、指定するDSMの切り替えで扱うデータ表現を変えるようにした。 これにより、必要に応じた形式を扱うことができ、ユーザが記述するComputation部分を大きく変えずに自由度の高い通信を行うことが可能になった。 -同様の手法を用いれば、圧縮形式以外にも暗号形式・JSON形式などの複数のデータ表現をユーザに扱いやすい形で拡張することができる。 今後の課題としては、AliceVNCとTreeVNCを比較することにより実装したMeta Computationの有効性を示す必要がある。 また、TreeVNCでは複雑な記述になってしまったNAT越えの機能を提供できると期待される。 - +\newpage \begin{thebibliography}{9} \bibitem{1}