# HG changeset patch
# User Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
# Date 1445843410 -32400
# Node ID 84ace958eee4cb4481b3e6dfb4ddead69bbaa60a
# Parent  7e90dc9afa41b2e66ed5e8276b0296a1f10d50e7
writed

diff -r 7e90dc9afa41 -r 84ace958eee4 midterm.tex
--- a/midterm.tex	Fri Oct 23 17:14:29 2015 +0900
+++ b/midterm.tex	Mon Oct 26 16:10:10 2015 +0900
@@ -1,5 +1,5 @@
 \documentclass[twocolumn,twoside,9.5pt]{jarticle}
-\usepackage[dvips]{graphicx}
+\usepackage[dvipdfmx]{graphicx}
 \usepackage{picins}
 \usepackage{fancyhdr}
 %\pagestyle{fancy}
@@ -18,24 +18,111 @@
 \pagestyle{empty}
 
 \begin{document}
-\title{題名}
-\author{学籍番号 氏名 {}{} 指導教員 : 指導教員名}
+\title{分散フレームワークAliceのPC画面配信システムへの応用}
+\author{学籍番号 125769C 氏名 {照屋}{のぞみ} 指導教員 : 河野真治}
 \date{}
 \maketitle
 \thispagestyle{fancy} 
 
-\section{section1}
+\section{はじめに}
+当研究室ではデータをData Segment、タスクをCode Segmentという単位で分割して記述する並列分散フレームワークAliceの開発を行っている。先行研究\cite{1}の水族館の例題等において、Alice が分散プログラムを記述する能力を有することは確認された。だが、実用的な分散プログラムを作成するためには、受け取ったデータをそのまま転送したい場合や圧縮されたデータ形式で通信を行いたい場合がある。
+
+本研究では、 Alice上に実用的なアプリケーションである画面共有システムTreeVNCを構築する。構築するにあたり必要となった転送・圧縮などの機能を AliceのMeta Computation として実装する。そしてJavaで書かれたTreeVNCとの比較を行うことでMetaComputationの役割と有効性を示す。
+
+\section{分散フレームワーク Alice の概要}
+AliceはデータをData Segment、（以下DS）タスクをとCode Segment（以下CS）という単位に分割してプログラミングを行う。
+DSはAliceが内部にもつデータベースによって管理されている。DSに対応する一意のkeyが設定されており、そのkeyを用いてデータベースを操作する。
+
+CSは実行に必要なDSが揃うと実行されるという性質を持ち、入力されたDSに応じた結果が出力される。
+CSを実行するために必要な入力DSはInputDS、CSが計算を行った後に出力されるDSはOutput DSと呼ばれる。データの依存関係にないCSは並列実行が可能である。
+
+実際にはAliceはJavaで実装されている。
 
-\section{section2}
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=70mm]{images/dsandcs2.pdf}
+\end{center}
+\caption{CodeSegmentの依存関係 }
+\label{fig:RemoteDSM}
+\end{figure}
+
+\subsection*{[Data Segment]}
+Aliceはデータを分割して記述する。その分割されたデータをDSと呼ぶ。
+Javaの実装ではMessagePackで特定のオブジェクトにマッピングされ、マッピングされたクラスを通してアクセスされる。CSの実行においてDSは占有されるため、Aliceではデータが他から変更され整合性がとれなくなることはない。
+
+\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に書き込まれる。
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=70mm]{images/remote_datasegment.pdf}
+\end{center}
+\caption{Remote DSMは他のノードのLocal DSMのproxy }
+\label{fig:RemoteDSM}
+\end{figure}
+
+\subsection*{[ComputationとMeta Computation]}
+Aliceでは、計算の本質的な処理をComputatin、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。
+Alice の Computationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理と捉えられる。
+それに対して、Alice の Meta Computation は、トポロジーの構成や切断・再接続の処理と言える。Aliceが動作するためにはトポロジーを決める必要がある。つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。
 
-\section{section3}
+プログラマーはCSを記述する際にトポロジーや切断、再接続という状況を予め想定した処理にする必要はない。プログラマーは目的の処理だけ記述する。そして、切断や再接続が起こった場合の処理を記述しMeta Computationで指定する。このようにプログラムすることで、通常処理と例外処理を分離することができるため、シンプルなプログラムを記述できる。
+Aliceの機能を追加するということは Meta Computation を追加すると言い換えられる。
+
+\section{AliceVNC}
+当研究室では授業向け画面共有システムTreeVNCの開発を行っている。
+授業でVNCを使う場合、１つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう。
+この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである。
+　Aliceが実用的なアプリケーションを記述する能力をもつことを確認するために、TreeVNCをAliceを用いて実装したAliceVNCの作成を行った。
+
+\section{Alice の新機能}
+実用的なアプリケーションである TreeVNC を Alice 上で実装することで、Alice に必要な機能を洗い出 した。
+\subsection*{[flip機能]}
+Data Segment APIを用いると、Output DSが毎回新しく作成され、出力するデータのコピーが行われる。しかし、Input DSとして取得したデータをそのまま子ノードにOutput Data Segmentとして出力する場合、コピーを行なうのは無駄である。
+そこで、Input DSとOutput DSにそのまま転送する機能をflip機能として実装することで、コピーのオーバーヘッドを減らした。TreeVNCでは親ノードから受け取った画面データをそのまま子ノードに配信するため、Meta Computationとしてflip機能が有用である。
+
+\subsection*{[Data Segmentの表現の追加（圧縮機能）]}
+TreeVNCでは画面配信の際、データを圧縮してノード間通信を行っている。
+そのため、AliceVNCにも圧縮されたデータ形式を扱える機能が必要だと考えた。
+しかし、ただデータを圧縮する機構を追加すればいいわけではない。
 
+AliceVNCでは、ノードは受け取った画面データを描画すると同時に、子ノードのRemote DS Managerに送信する。
+ノードはDSを受信するとそれを一度解凍して画面を表示し、再圧縮して子ノードに送信する。
+しかし、受け取ったデータを自分の子ノードに対して送信する際には、解凍する必要はない。
+圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる。
 
-\section{section4}
+そこで、１つのData Segmentに対し複数の表現を持たせることで、必要に応じた形式でDSを扱うことを可能にした。
+DSを扱うReceiveData.classに、次の3種類の表現を同時に持つことができる。
+
+\begin{enumerate}
+  \item 一般的なJavaのクラスオブジェクト
+  \item MessagePack for Javaでシリアライズ化されたバイナリオブジェクト
+  \item 2を圧縮したバイナリオブジェクト
+\end{enumerate}
+1はLocalDSMにDSを保存する場合に用いる。また、圧縮せずにRemoteDSMにDSを保存する場合は2のMessagePack形式で送られる。そしてLocal, Remote に対しDSを圧縮して保存する場合は3を用いる。
+
+さらに、圧縮状態を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerの追加した。Compressed DSMの内部では、DSが呼ばれた際にReceiveData.classが圧縮表現を持っていればそれを使用し、持っていなければその時点で圧縮表現を作って操作を行う。
+これによりユーザは指定するDSMを変えるだけで、他の計算部分を変えずに圧縮表現を持つDSを扱うことができる。ノードは圧縮されたDSを受け取った後、そのまま子ノードにflipすれば圧縮状態のまま送信されるので、送信の際の再圧縮がなくなる。
+
+しかし、データの表現に圧縮したbyteArrayを追加したため、Remoteから受け取ったbyteArrayのDSが圧縮されているのかそうでないのかを判断する必要がある。
+そこで、Aliceの通信におけるヘッダにあたるCommandMessage.classにシリアライズ状態表すフラグと、圧縮状態を表すフラグを追加した。
+これによってputされたDSMはフラグに応じた適切な形式でReceiveData.class内にDSを格納できる。
+
+\section{今後の課題}
+AliceVNCとTreeVNCを比較することにより実装したMeta Computationの有効性を示す必要がある。
+また、TreeVNCでは実装が困難であったNAT越えの機能を提供できると期待される。
+
 
 \begin{thebibliography}{9}
 
 \bibitem{1}
+{Yu SUGIMOTO and Shinji KONO}: 分散フレームワークAlice上のMeta Computationと応用，琉球大学工学部情報工学科平成26年度学位論文(修士) (2014).
+
+\bibitem{2}
+{Nobuyasu OSHIRO, Yu SUGIMOTO, Shinji KONO and Tatsumi NAGAYAMA}:Data Segment の分散データベースへの応用，日本ソフトウェア科学会 (2013).
+
+
 
 \end{thebibliography}
 \end{document}
\ No newline at end of file