gnuplot_plot

# HG changeset patch # User Nozomi Teruya # Date 1455122075 -32400 # Node ID f148e6addeaf7677d1dad9fe541486916ae8243b # Parent a97aa059242f177a064eaaf484bcea13c6060899 add ring result diff -r a97aa059242f -r f148e6addeaf paper/images/AliceVNC_compress_depth3.pdf Binary file paper/images/AliceVNC_compress_depth3.pdf has changed diff -r a97aa059242f -r f148e6addeaf paper/images/AliceVNC_compress_depth3.svg --- a/paper/images/AliceVNC_compress_depth3.svg Fri Feb 05 21:00:41 2016 +0900 +++ b/paper/images/AliceVNC_compress_depth3.svg Thu Feb 11 01:34:35 2016 +0900 @@ -34,935 +34,937 @@ - + 1 - + 10 - + 100 - + 1000 - + 10000 - + + 100000 + + + 1e+06 + + 10 - + 100 - + 1000 - + 10000 - + 100000 - + 1e+06 - 1e+07 - + time(ms) - + size(byte) - + node depth3 gnuplot_plot_1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - + diff -r a97aa059242f -r f148e6addeaf paper/images/AliceVNC_compress_depth3.xbb --- a/paper/images/AliceVNC_compress_depth3.xbb Fri Feb 05 21:00:41 2016 +0900 +++ b/paper/images/AliceVNC_compress_depth3.xbb Thu Feb 11 01:34:35 2016 +0900 @@ -2,7 +2,7 @@ %%Creator: extractbb 20130405 %%BoundingBox: 0 0 600 480 %%HiResBoundingBox: 0.000000 0.000000 600.000000 480.000000 -%%PDFVersion: 1.3 +%%PDFVersion: 1.4 %%Pages: 1 -%%CreationDate: Sun Nov 29 13:53:46 2015 +%%CreationDate: Tue Feb 9 19:38:03 2016 diff -r a97aa059242f -r f148e6addeaf paper/main.tex --- a/paper/main.tex Fri Feb 05 21:00:41 2016 +0900 +++ b/paper/main.tex Thu Feb 11 01:34:35 2016 +0900 @@ -1,12 +1,35 @@ \documentclass[a4j,12pt]{jreport} -\usepackage[dvips]{graphicx} +\usepackage[dvipdfmx,hiresbb]{graphicx} \usepackage{mythesis} \usepackage{multirow} +\usepackage{listings} +\usepackage{url} +\lstset{% + language={Java},%使用言語 + basicstyle={\small},%書体 + commentstyle={\small\itshape},%コメントの書体 + keywordstyle={\small\bfseries},%キーワードの書体 + %identifierstyle={\small},% + %ndkeywordstyle={\small},% + stringstyle={\small},%文字列の書体 + frame={trlb},%外枠 + breaklines=true,%改行 + columns=[l]{fullflexible},% + xrightmargin=0zw,% + xleftmargin=3zw,% + numbers=left,%行番号の表示 + numberstyle={\scriptsize},%行番号の書体 + numbersep=1zw,% + stepnumber=1, + lineskip=-0.5ex,% + captionpos=b,%キャプションの位置 +} +\renewcommand{\lstlistingname}{Code} \usepackage{here} \setlength{\itemsep}{-1zh} \title{分散フレームワークAliceのMeta Data Segment} \icon{ - \includegraphics[width=80mm,bb=0 0 595 842]{fig/ryukyu.pdf} + \includegraphics[width=50mm,bb=0 0 595 842]{fig/ryukyu.pdf} } \year{平成27年度卒業論文} \belongto{琉球大学工学部情報工学科} @@ -27,12 +50,11 @@ \maketitle \baselineskip 17pt plus 1pt minus 1pt -\pagenumbering{roman} \setcounter{page}{0} \tableofcontents % 目次 -\listoffigures % 図目次 -\listoftables % 表目次 +%\listoffigures % 図目次 +%\listoftables % 表目次 %以下のように、章ごとに個別の tex ファイルを作成して、 % main.tex をコンパイルして確認する。 @@ -40,6 +62,7 @@ % はじめに \chapter{序論} +\pagenumbering{arabic} \section{研究背景と目的} 近年、スマートフォンやタブレット端末の普及率が増加している。それに伴いインターネット利用者数も増加しており、ネットワーク上のサービスの利用者の増加は必至である。 @@ -66,13 +89,15 @@ \chapter{分散フレームワークAliceの概要} \section{Code Segment と Data Segment} AliceではCode Segment（以下CS）とData Segment（以下DS）の依存関係を記述することでプログラミングを行う。 + CSは実行に必要なDSが全て揃うと実行される。CSを実行するために必要な入力されるDSのことをInputDS、CSが計算を行った後に出力されるDSのことをOutput DSと呼ぶ。 + データの依存関係にないCSは並列実行が可能である（図 \ref{fig:CS} ）。 CSの実行においてDSが他のCSから変更を受けることはない。そのためAliceではデータが他から変更され整合性がとれなくなることはない。 \begin{figure}[htbp] \begin{center} - \includegraphics[width=70mm]{images/dsandcs2.pdf} + \includegraphics{images/dsandcs2.pdf} \end{center} \caption{CodeSegmentの依存関係 } \label{fig:CS} @@ -89,24 +114,29 @@ \section{Data Segment Manager} DS Manager（以下DSM）にはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。 + Remote DSMは他ノードのLocal DSMに対応するproxyであり、接続しているノードの数だけ存在する（図 \ref{fig:Remote DSM} ）。他ノードのLocal DSMに書き込みたい場合はRemote DSMに対して書き込めば良い。 Remote DSMを立ち上げるには、DataSegmentクラスが提供するconnectメソッドを用いる。 -接続したいノードのipアドレスとport番号、そして任意のManager名を指定することで立ちあげられる。その後はManager名を指定してData Segment APIを用いてDSのやり取りを行うため、プログラマはManager名さえ意識すればLocalへの操作もRemoteへの操作も同じ様に扱える。 +接続したいノードのipアドレスとport番号、そして任意のManager名を指定することで立ちあげられる。 +その後はManager名を指定してData Segment APIを用いてDSのやり取りを行うため、プログラマはManager名さえ意識すればLocalへの操作もRemoteへの操作も同じ様に扱える。 \begin{figure}[h] \begin{center} - \includegraphics[width=70mm]{images/remote_datasegment.pdf} + \includegraphics[width=150mm]{images/remote_datasegment.pdf} \end{center} \caption{Remote DSMは他のノードのLocal DSMのproxy } \label{fig:Remote DSM} \end{figure} +\newpage \section{Data Segment API} DSの保存・取得にはAliceが提供するAPIを用いる。 + putとupdate、flipはOutput DS APIと呼ばれ、DSをDSMに保存する際に用いる。 + peekとtakeはInput DS APIと呼ばれ、DSをDSMから取得する際に使用する。 \begin{itemize} @@ -122,7 +152,7 @@ \begin{itemize} \item{\ttfamily void update(String managerKey, String key, Receiver val)} \end{itemize} -flipはDSの転送用のAPIである。取得したDSに対して何もせずに別のKeyに対し保存を行いたい場合、flipを使うことで無駄なコピーなくDSの保存ができる。 +flipはDSの転送用のAPIである。取得したDSに対して何もせずに別のKeyに対し保存を行いたい場合、一旦値を取り出すのは無駄である。flipを使うことで無駄なコピーなくDSの保存ができる。 \begin{itemize} \item {\ttfamily void take(String managerKey, String key)} @@ -134,32 +164,34 @@ \end{itemize} peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。 - +\newpage \section{Code Segmentの記述方法} CSをユーザーが記述する際にはCodeSegmentクラスを継承して記述する(ソースコード \ref{src:StartCodeSegment} , \ref{src:CodeSegment})。 + 継承することによりCode Segmentで使用するData Segment APIを利用する事ができる。 +Alice には、Start CS (ソースコード \ref{src:StartCodeSegment} )というC の main に相当するような最初に実行される CS がある。 +Start CSはどのDSにも依存しない。つまりInput DSを持たない。 +このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 + \begin{table}[html] \lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java} \lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java} \end{table} -Alice には、Start CS (ソースコード \ref{src:StartCodeSegment} )というC の main に相当するような最初に実行される CS がある。 -Start CSはどのDSにも依存しない。つまりInput DSを持たない。 -このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 +\newpage -ソースコード \ref{src:StartCodeSegment} は、5行目で次に実行させたいCS（ソースコード \ref{src:CodeSegment} ）を作成している。8行目でOutput DS APIを通してLocal DSMに対してDSをputして -いる。 +ソースコード \ref{src:StartCodeSegment} は、5行目で次に実行させたいCS（ソースコード \ref{src:CodeSegment} ）を作成している。 +8行目でOutput DS APIを通してLocal DSMに対してDSをputしている。 Output DS APIはCSの{\tt ods}というフィールドを用いてアクセスする。 -{\tt ods}は{\tt put}と{\tt update}を実行することができる。 +{\tt ods}は{\tt put}と{\tt update}と{\tt flip}を実行することができる。 TestCodeSegmentはこの"cnt"というkeyに対して依存関係があり、8行目でputが行われるとTestCodeSegmentは実行される。 CSのInput DSは、CSの作成時に指定する必要がある。指定はCommandType(PEEKかTAKE)、DSM名、そしてkey よって行われる。 Input DS API はCSの{\tt ids}というフィールドを用いてアクセスする。 -Output DSは、{\tt ods}が提供するput/updateメソッドをそのまま呼べばよかったが、Input DSの場合{\tt ids}にpeek/takeメソッドはなく、create/setKeyメソッド内でCommandTypeを指定して実行す -る。 +Output DSは、{\tt ods}が提供するput/update/flipメソッドをそのまま呼べばよかったが、Input DSの場合{\tt ids}にpeek/takeメソッドはなく、create/setKeyメソッド内でCommandTypeを指定して実行する。ソースコード\ref{src:CodeSegment}は、0から9までインクリメントする例題である。 2行目では、Input DS APIがもつcreateメソッドでInput DSを格納する受け皿(Receiver)を作っている。 @@ -196,6 +228,7 @@ \chapter{AliceのMeta Computation} \section{Computetion と Meta Computation} Aliceでは、計算の本質的な処理をComputation、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。 + AliceのComputationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理と捉えられる。それに対して、AliceのMeta Computation は、Remoteノードとの通信時のトポロジーの構成や切断・再接続の処理と言える。つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。 @@ -206,19 +239,19 @@ このようにプログラムすることで、通常処理と例外処理を分離することができるため、仕様の変更を抑えたシンプルなプログラムを記述できる。 \subsection{Meta Code Segment と Meta Data Segment} -AliceのMeta ComputationもCS/DSにより実現される。 -Meta Computationは、CSの処理を支えるMeta CSと、Meta CSに管理されるMeta DSに分けられる。 +AliceのMeta ComputationもCS/DSにより実現され、CSの処理を支えるMeta CSと、Meta CSに管理されるMeta DSに分けられる。図\ref{fig:metaCS}は、AliceのMeta CS/Meta DSの接続関係の例である。プログラマ側はCSとDSの依存関係を記述するが、その裏ではMeta CSやMeta DSが間に接続されて処理を行っている。 \begin{figure}[h] \begin{center} - \includegraphics[width=70mm]{images/metaCS.pdf} + \includegraphics[width=120mm]{images/MetaCSDS.pdf} \end{center} \caption{CS/DSの間にMetaCS/MetaDSが接続される} \label{fig:metaCS} \end{figure} +\newpage \section{Aliceが持つMeta Computation} Aliceでは分散環境構築のためにさまざまなMeta Computationが用意されている。 @@ -239,7 +272,7 @@ そのため、Topology NodeはTopology ManagerのIPアドレスさえ知っていれば自分の接続すべきノードのデータを受け取り、ノード間での正しい接続を実現できる。 \begin{figure}[h] \begin{center} -\includegraphics[width=60mm]{images/topologymanager.pdf} +\includegraphics{images/topologymanager.pdf} \end{center} \caption{Topology Managerが記述に従いトポロジーを構成} \label{fig:topologymanager} @@ -283,31 +316,460 @@ % AliceVNC \chapter{AliceのTreeVNCへの応用} \section{TreeVNC} -\section{AliceVNCで用いるMeta Computation} +AliceのMeta Computationが実用的なアプリケーションの記述において有用であることを確認する。 +そのために、TreeVNCをAliceを用いて実装したAliceVNCの作成を行った。 + +TreeVNCとは、当研究室で開発を行っている授業向け画面共有システムである。 +オープンソースのVNCであるTightVNC \cite{tightVNC} をもとに作られている。 +授業でVNCを使う場合、１つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう(図 \ref{fig:vncstructure})。 +この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである(図 \ref{fig:treestructure})。 +\begin{figure}[htbp] +\begin{tabular}{cc} +\begin{minipage}{0.5\hsize} +\begin{center} +\includegraphics[width=80mm]{images/vnc.pdf} +\caption{通常のVNCの構造} +\label{fig:vncstructure} +\end{center} +\end{minipage} +\begin{minipage}{0.5\hsize} +\begin{center} +\includegraphics[width=80mm]{images/treestructure.pdf} +\caption{TreeVNCの構造} +\label{fig:treestructure} +\end{center} +\end{minipage} +\end{tabular} +\end{figure} + + + +図 \ref{fig:TreeVNC}はAliceVNCを実現するための構成である。leftとrightのRemote DSMを用意し子ノードと接続することで木構造を実現する。 + +\begin{figure}[h] + \begin{center} + \includegraphics[width=120mm]{images/TreeVNC.pdf} + \end{center} + \caption{AliceVNC の構造} + \label{fig:TreeVNC} +\end{figure} + +TreeVNCは通信処理部分や画面データの処理部分が１つのコード内で記述され、大変複雑になっている。 +しかし、Aliceで記述すればMeta Computationにより本質的な処理とそれを支える通信処理部分で分離できる。 +TreeVNCでは3章で述べた動的なトポロジーの構成、切断ノードの発見、再接続・トポロジーの再構成といった通信処理のMeta Computationが活用できる。 +そのため、TightVNCからの修正の少ない、見通しの良い記述で構成可能と期待される。 + +\newpage + \section{圧縮のMeta Computationの追加} +TreeVNCでは画面配信の際、データを圧縮してノード間通信を行っている。 +そのため、AliceVNCにも圧縮されたデータ形式を扱える機能が必要だと考えた。 +しかし、ただデータを圧縮する機構を追加すればいいわけではない。 + +AliceVNCでは、ノードは受け取った画面データを描画すると同時に、子ノードのRemote DSMに送信する。 +ノードはDSを受信するとそれを一度解凍して画面を表示し、再圧縮して子ノードに送信する。 +しかし、受け取ったデータを自分の子ノードに対して送信する際には、解凍する必要はない。 +圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる。 + +そこで、DSを複数作るのではなく１つのDS内で複数の表現を持たせ、必要に応じた形式でDSを扱うことを可能にした。 +Meta DSに相当するReceiveData.classに、次の3種類の表現を同時に持つことができるようにしたことで、データの多態性を実現した。 + +\begin{enumerate} + \item 一般的なJavaのクラスオブジェクト + \item MessagePack for Java\cite{MessagePack}でシリアライズ化されたバイナリオブジェクト + \item 2を圧縮したバイナリオブジェクト +\end{enumerate} + +Local DSMにputされた場合は、(1)の一般的なJavaクラスオブジェクトとして追加される。 +Remote DSMにputされた場合は、通信時に(2)のbyteArrayに変換されたバイナリオブジェクトに変換されたDSが追加される。 +この2つの形式は従来のAliceが持っていた表現である。 +今回、Remote DSMに圧縮形式での通信を行いたいため、(3)の圧縮表現を追加した。 + +ソースコード \ref{src:ReceiveData1} は変更前のReceiveData.classである。 +変更前はDSの表現は１つでフラグによって、Local DSM にputする(1)の形式とRemote DSMにputする(2)の形式を判別していた。 +しかしこの実装では圧縮形式と非圧縮形式を同時に持つことができないため、AliceVNCでは解凍・再圧縮が必要になってしまう。 + +変更後の実装ではソースコード \ref{src:ReceiveData1} のようになっている。 +{\tt val}に(1) 一般的なJavaのクラスオブジェクトの表現でデータ本体が保存される。 +{\tt messagePack}には(2) シリアライズ化されたバイナリオブジェクトが保存される。 +そして、{\tt zMessagePack}には(3) 圧縮されたバイナリオブジェクトが保存される。 +このようにDSが複数の表現を同時に保持することで、DSが圧縮表現を持っている場合に再圧縮する必要がなくなる。 +プログラマ側がから見れば1つのDSであり直接これら３つの表現を操作することはないため、これらはAliceのMeta Data Segmentと言える。 + +\begin{table}[html] +\lstinputlisting[label=src:ReceiveData1, caption=変更前のデータ表現]{source/beforeReceiveData.java} +\end{table} + +\begin{table}[html] +\lstinputlisting[label=src:ReceiveData2, caption=変更後のデータ表現]{source/ReceiveData.java} +\end{table} + + +また、圧縮表現を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerを追加した。 +Compressed DSMの内部では、put/updateが呼ばれた際にReceiveData.classが圧縮表現を持っていればそれを使用し、持っていなければその時点で圧縮表現を作ってput/updateを行う。 +Local Compressed DSM は表現の判別や変換を行うだけで、操作する対象は Local DSM と同じDSを指すため、DSの管理が別々になるわけではない。 + + +ソースコード \ref{src:before} はRemote DSMに対しInt型のデータをputする記述である。 +この通信を圧縮形式のDSで行いたい場合、ソースコード \ref{src:after} のように指定するDSM名の先頭に"compressed"をつければCompressed DSM内部の圧縮Meta Computationが走り圧縮形式に変換さ +れたDSとなって通信が行われる。 + +\begin{table}[html] +\lstinputlisting[label=src:before, caption=通常のDSを扱うCSの例]{source/beforeCompress.java} +\end{table} + +\begin{table}[html] +\lstinputlisting[label=src:after,caption=圧縮したDSを扱うCSの例]{source/afterCompress.java} +\end{table} + +これによりユーザは指定するDSMを変えるだけで、他の計算部分を変えずに圧縮表現をDS内で持つことができる。 +ノードは圧縮されたDSを受け取った後、そのまま子ノードにflipメソッドで転送すれば圧縮状態のまま送信されるので、送信の際の再圧縮がなくなる。 + + +画面表示の際はReceiveData.class内のasClassメソッドを使うことで適切な形式でデータを取得できる。 +asClassメソッドはDSを目的の型にcastするためのメソッドである。 +AliceVNCで圧縮形式を指定してDSを送信すると、それを受け取るDSMは圧縮形式のみを持ったDSとして保存する。 +そしてasClassメソッドが呼ばれて初めて、メソッド内で解凍してcastが行われDSが複数の表現を同時に持つようになる。 +これによりDSの表現を必要になったときに作成できるため、プログラマはどんな形式でDSを受け取ってもDSを編集可能な形式として扱うことができる。 +また、複数表現は必要なときにしか作成されないため、メモリ使用量も必要最低限に抑えることができる。 + +\section{Aliceの通信プロトコルの変更} +4.2で述べたように、Remoteからputされたデータは必ずシリアライズ化されておりbyteArrayで表現される。 +しかし、データの表現に圧縮したbyteArrayを追加したため、RemoteからputされたbyteArrayが圧縮されているのかそうでないのかを判別がつかなくなった。 + +そこで、Aliceの通信におけるヘッダにあたるCommandMessage.class(ソースコード\ref {src:CommandMessage} \ref{fig:variable})に圧縮状態を表すフラグを追加した。 +これによってputされたDSMはフラグに応じた適切な形式でReceiveData.class内にDSを格納できる。 +また、CommandMessage.classに圧縮前のデータサイズも追加したことで、適切な解凍が可能になった。 + +\begin{table}[html] +\lstinputlisting[label=src:CommandMessage, caption=CommandMessage]{source/CommandMessage.java} +\end{table} + + +\begin{table}[htbp] +\caption{CommandMessageの変数名の説明} +\label{tb:variable} +\begin{center} +\begin{tabular} {|l|l|} + \hline + 変数名&説明\\ + \hline + type&CommandType {\tt PEEK, PUT}などを表す\\ + \hline + seq&\shortstack{Data Segmentの待ち合わせを行っている\\Code Segmentを表すunique number }\\ + \hline + key&どのKeyに対して操作を行うか指定する\\ + \hline + + quickFlag&SEDAを挟まずCommandを処理を行うかを示す\\ + \hline + + compressed&データ本体の圧縮状態を示す\\ + \hline + + dataSize&圧縮前のデータサイズを表す\\ + \hline + +\end{tabular} +\end{center} +\end{table} + +\newpage + \section{Topology Managerの複数対応} % 実験 \chapter{評価と考察} -\section{性能比較} -\section{コード量比較} -\section{コードの複雑度比較} +\section{圧縮のMeta Computationの評価} +圧縮のMeta Computationが正しく機能しているかを確認するために通信時間の計測を行った。 +2台のPC間でお互いにデータを100回転送し合う。圧縮を指定したコードとしていないコードで5回計測した。 + +結果が表\ref{tb:compressmesure}である。 +データサイズから見ても圧縮に成功していることがわかる。 +通信においても、所要時間が1/3以下に抑えられていることから圧縮が効果的に作用している。 +TreeVNCと同等の性能をだすために有用なMeta Computationが実装できたと言える。 + +\begin{table}[htbp] +\caption{圧縮機能の測定結果} +\label{tb:compressmesure} +\begin{center} +\begin{tabular} {|l|l|l|} + \hline + 　 &圧縮なし&圧縮あり\\ + \hline + データサイズ&300KB&91KB\\ + \hline + 平均通信時間&6014ms&1764ms\\ + \hline +\end{tabular} +\end{center} +\end{table} + + + +\section{TreeVNCとAliceVNCの比較} +TreeVNCをAlice上で構築するために必要な機能をAliceのMeta Computationとして実装した。 +これにより、AliceVNCが簡潔な記述でTreeVNCと同等の性能を出せれば、実用的な分散アプリケーションの実装においてAliceのMeta Computationは有用であるといえる。 +そこで、TreeVNCとAliceVNCの性能評価としてメッセージ伝達速度の比較を、コードの評価としてコード量とその複雑度の比較を行った。 + +\subsection{メッセージ伝達速度の比較} +TreeVNC/AliceVNCにおいて、配信する画像データは構成した木を伝ってノードに伝搬され、接続する人数が増える毎に木の段数は増えていく。 +そこで、木の段数ごとにメッセージの到達にどれぐらい時間がかかっているかを計測した。 + +講義内で学生に協力してもらい、最大17名の接続がある中でTreeVNC、AliceVNCの木の段数1〜3の測定を行った。 + +　 + +\textbf{実験内容} + +ルートノードから画面データを子ノードに伝搬する際に、計測用のヘッダをつけたパケットを子ノードに送信する。 +各子ノードはパケットを受け取り自身のViewerに画面データを表示すると同時に、計測用ヘッダ部分のみのDSを作成し、親ノードに送り返す。 +計測用DSは木を伝ってルートノードまで送り返され、ルートノードは受け取った計測用DSから到達時間を計算する。 + +計測用のヘッダは以下の要素で構成されている。 +\begin{table}[htbp] +\caption{計測用ヘッダの変数名の説明} +\label{tb:mesure} +\begin{center} +\begin{tabular} {|l|l|} + \hline + 変数名&説明\\ + \hline + time&ルートノードがパケットを送信した時刻\\ + \hline + depth&木の段数。初期値=1。\\ + \hline + dataSize&送信時の形式に変換済みの画面データのサイズ\\ + \hline +\end{tabular} +\end{center} +\end{table} + +timeにはパケットの送信時刻を、dataSizeには圧縮された画面データのサイズを付けて送信する。 +depthは各ノードに到達するごとにインクリメントされる。 + +到達時間の計算方法は、計測用DSを受け取った時刻とDSのtime（送信した時刻）の差をとる。 +この到達時間は画面データがノードまで到達した時間と計測DSをルートまで送り返す時間を含めているが、送り返す時間は誤差として考える。 +また、depthは各ノードに到達するごとにインクリメントされるため、送り返す際もインクリメントされる。そのため、木の段数を計算するにはdepthを1/2した値となる。 + +　 + +\textbf{実験結果} + +3段目の測定結果の散布図を示す（図\ref{fig:TreeVNC_delay} 〜 \ref{fig:AliceVNC_compress_delay}）。 +X軸が画面データのサイズ(byte)、Y軸が計算した到達時間(ms)である。 +実験時間の都合上、AliceVNCの計測時間が他より短くなってしまったためプロットされた点の数が少なくなっている。 +また、それぞれの図で処理に10000ms以上かかっている点の集合が見られるが、これは今回の実験において3段目にPCのスペック上処理が遅いノードが1台あったためである。 +そのため比較においてこの点集合は無視する。 + +どの図も同様の傾向があり、画面データのサイズが小さいうちは処理時間も5ms程度だが、50000byte以上から比例して処理時間も遅くなっている。 +このことからAliceVNCはTreeVNCと同等の処理性能があることがわかる。 + +\begin{figure}[h] + \begin{center} + \includegraphics[width=100mm]{images/TreeVNC_depth3.pdf} + \end{center} + \caption{TreeVNCの測定結果} + \label{fig:TreeVNC_delay} +\end{figure} + +\begin{figure}[h] + \begin{center} + \includegraphics[width=100mm]{images/AliceVNC_compress_depth3.pdf} + \end{center} + \caption{AliceVNC(圧縮・転送機能あり)の測定結果} + \label{fig:AliceVNC_compress_delay} +\end{figure} +\newpage + + +\subsection{コード量比較} + +TreeVNCとAliceVNCのコード量を比較した表が表\ref{tb:code}である。 +TightVNCを含むコード全体にwcを行い、行数と単語数を比較した。 +また、hg diffでTightVNCからの変更行数を調べ変更量を比較した。 + +表からわかるように、Aliceを用いればコードの行数が25\%削減できる。 +また、TreeVNCではTightVNCに大幅に修正を加えながら作成したため仕様の変更が多かった。 +しかし、AliceVNCではTightVNCにほとんど修正を加えることなくトポロジー構成等のAliceのMeta Computationを使うために新しいクラスを作成したのみであった。 +そのためTreeVNCに比べ75\%も仕様の変更が抑えられている。 +\begin{table}[htbp] +\caption{コード量の比較} +\label{tb:code} +\begin{center} +\begin{tabular} {|l|l|l|l|} + \hline + &行数&単語数&変更行数\\ + \hline + TreeVNC&19502&73646&7351\\%11369+8133=19502,47010+26636,2094+5257 + \hline + AliceVNC&14647&59217&1129\\%689+7094+6864=14647,23035+34610+1572,689+395+45 + \hline + 減少率(\%)&25&20&75\\ + \hline +\end{tabular} +\end{center} +\end{table} + + + +\subsection{コードの複雑度比較} +コード量の比較で述べたように、TreeVNCはTightVNCからの変更が多い。 +その理由の一つがトポロジーの構成や通信処理がコアな仕様と分離できておらず、 +そのためTreeVNCは大変複雑な記述になってしまっている。 + +そこでTreeVNCとAliceVNCにおいてコードの複雑度を比較した。 +今回、複雑度の指標としてThomas McCabeが提案した循環的複雑度\cite{complaxy}を用いた。 +循環的複雑度とはコード内の線形独立な経路の数であり、if文やfor文が多ければ複雑度も高くなりバグ混入率も高まる。 +一般的に、循環的複雑度が10以下であればバグ混入率の少ない非常に良いコードとされる。 +計測にはIntelliJのCodeMetrics計測プラグインであるMetricsReloadedを使用した。 + +表\ref{tb:complex}はTightVNC、TreeVNC、AliceVNCにおける循環的複雑度の比較である。 +プロジェクト全体でのクラスの複雑度の平均値と最高値をとった。 +平均値・最高値ともにAliceVNCのほうが複雑度が低いことから、Aliceではシンプルな記述が可能だということがわかる。 + +TreeVNCで最高値を出したTreeRFBProto.classは全てプログラマが記述したコードであり、データの待ち合わせのためのタイマー処理や通信処理、画面データの圧縮処理などの複数のスレッド処理が集中した複雑なコードになっている。 +これをAliceで記述した場合、データの待ち合わせはCSが行うためプログラマがデータの不整合を気にする必要はなく、また通信処理や圧縮処理もMeta Computationが提供するためコードが複雑になることはない。 + +AliceVNCで複雑度の最高値を出したSwingViewerWindow.classはTightVNCで最高値を出したクラスと同じであり、コード量の比較でも示したようにAliceVNCで変更を加えた点がほとんどない。つまりこの複雑度は元来TightVNCが持っている複雑度と言える。 + + +\begin{table}[htbp] +\caption{複雑度の比較} +\label{tb:complex} +\begin{center} +\begin{tabular} {|l|l|l|} + \hline + &平均値&最高値\\ + \hline + TightVNC&13.63&97\\ + \hline + TreeVNC&15.33&141\\ + \hline + AliceVNC&10.95&99\\%(4.12+13.64)/2 (4.12+9.16+19.59)/3 + \hline +\end{tabular} +\end{center} +\end{table} + +AliceVNCとTreeVNCの性能比較・コード比較から、AliceVNCはTreeVNCと同等の性能を持つ分散アプリケーションの記述ができ、かつコードの修正量・複雑度共に低く抑える能力を有することがわかった +。 + + + \section{他言語等との比較} +Aliceが採用しているCS/DSのプログラミングモデルやMeta Computationの特性を明確にするため、他言語・フレームワークとの類似点・相違点を比較した。 + \subsection{Erlang} + +並列指向プログラミング言語Erlang\cite{Erlang}は、プロセスと呼ばれるid付きの独立したタスクに対して、データをメッセージでやりとりする。 +タスクをプロセスという細かい単位に分割して並列に動かす点や、メモリロックの仕組みを必要としない点はAliceと同様である。 + +しかしErlangでは分散環境の構築等はすべてプログラマ自身が記述しなければならない。 +Aliceでは分散環境の構築はTopology ManagerなどのMeta Computationが行うためプログラマはトポロジーを指定するだけで良い。 +また、Erlangでは複数のデータの待ち合わせのための再帰処理も自分で書かないといけない。 +一方、Aliceのプログラミング手法はCSが必要なデータが全て揃うまで待ち合わせを行うためその必要はない。 + + \subsection{Akka} +Akka\cite{Akka}はScala・Java向けの並列分散処理フレームワークである。 +アクターモデルを採用しており、アクターと呼ばれるアドレスを持ったタスクに、データをメッセージでやりとりする点がErlangと似ている。 +AkkaもErlangもプロセス/アクターに直接データをやりとりする。データには名前がないため、メッセージを受け取ったあとにその内容を確認した上で次にどう振る舞うかを判断する。 +一方Aliceでは、DSをCSに直接やりとりはせず、keyを指定してDSMにputする。 +また、DSをtakeするときもkeyを指定して取り出すためどんなデータが入っているかを確認する必要がなく、扱い易い。 + +Akkaの特徴として、メッセージを送りたいプロセスのアドレスを知っていればアクターがどのマシン上にあるかを意識せずにプログラミングできるという点がある。 +逆にAliceはどのRemote DSMに対してやり取りをするかを考慮するが、CSがOutputしたDSを次にどのCSに渡すかを意識する必要がない。この点はアクターモデルとCS/DSモデルのパラダイムの違いと言え +る。 + +一方AliceとAkkaは提供されるAPIという点で類似している。AkkaのメッセージAPIでは、メッセージを送るtellメソッドと、メッセージを送って返信を待つaskメソッドが用意されている。これはAliceのDataSegment APIのput/takeメソッドに対応している。 + +また、Akkaのもう一つの特徴として、アクターで親子関係を構成できる点がある。 +分散通信部分を子アクターに分離し、親アクターは子アクターのExceptionが発生した時に再起動や終了といった処理を指定できる。 +さらにRouterという子アクターへのメッセージの流れを制御するアクターや、Dispatcherというアクターへのスレッドの割当を管理する機能をAkkaが提供している。 +このように処理を階層化し複雑な処理をフレームワーク側が提供する仕組みはAliceのMeta Computationと共通している。 +相違点としては、AliceのMeta DSのようにデータの多態性を実現する機能はAkkaにはない。 + +\subsection{MPICH?} + + % 今後の課題 \chapter{結論} \section{まとめ} +並列分散フレームワークAliceでは、スケーラブルかつ信頼性の高いプログラムを記述する環境を実現するため、CS/DSの計算モデルとMeta Computationによる実装の階層化を採用している。 +Aliceが実用的な分散アプリケーションを記述するために必要なMeta Computationとして、多態性を持つデータを扱う機能や無駄なコピーなくデータを転送する機能を実装した。 +そしてMeta Computationを用いて分散アプリケーションTreeVNCをAlice上で実装し性能評価を行った。 +その結果、TreeVNCで使用される基本機能はAliceでも実現でき、同等の性能を出すことができるということが分かった。 +またコードの観点からTreeVNCとAliceVNCを比較した結果、Aliceが仕様の変更を抑えたシンプルな記述を実現し、信頼性の高い実用的な分散アプリケーションを構築するに有用であることが確認された +。 + \section{今後の課題} +\subsection{AliceVNCのNAT超え通信の実装} +今後の課題としては、TreeVNCで実装が困難であったNATを超えたノード間通信をAliceVNCで実現し、その性能とコード修正量を比較することが挙げられる。 +図\ref{fig:overNAT}は２つの違うプライベートネットワークを超えた接続の設計例である。 + +\begin{figure}[h] + \begin{center} + \includegraphics[width=75mm]{images/overNAT.pdf} + \end{center} + \caption{複数のTopology ManagerでNAT超えを実現} + \label{fig:overNAT} +\end{figure} + +各ネットワークごとにTopoogy Managerを立ち上げることでネットワークを超えたノード間接続を実現する。 +プライベートネットワークのTopoogy Managerは今までどおりネットワーク内に木を構築・管理する。 +他のネットワークにあるノードBがノードAに接続したい場合は、グローバルアドレスを持ったTopology Managerに参加表明をすればノードAの情報が提供され、ノードAの子ノードとして接続される。 +つまり、Topology Managerを複数用意するだけで、Topology Manager自体の「参加表明のあったノードで木を構成する」という仕様は全く変更しないで良い。 +TreeVNCでは500行以上の変更が必要とされたが、Aliceでは複数のTopology Managerに接続するためのconfigファイルを変更するだけなので、AliceVNCの仕様の変更を抑えられると期待される。 +この機能も実現できれば、AliceのMeta Computationが拡張性の高い環境を提供できると言える。 + +\subsection{セキュリティのサポート} +現在のAliceはネットワーク通信においてセキュリティをサポートしていない。 +しかし、圧縮機能と同様に、暗号化形式を扱うMeta Computationを追加すれば、プログラマが記述するComputation部分を大きく変えずに自由度の高い通信を行うことができると期待できる。 + +\subsection{APIの再設計} +2.4で示したように、DSを取得するときのAPIはpeek/takeが直接扱えず、create/setKeyを組み合わせてプログラミングしなければならない。 +この設計だとプログラマにとってわかりづらく、コンストラクタ内でtakeを行いたい場合はsetKeyを必ず最後に呼ばなければならないといった注意点がある。 +put/update/flipと同様に、peek/takeをそのまま呼べるように再設計する必要がある。 + +\subsection{データの永続性の確保} +現在のAliceは、On memoryであるためプロセスの終了とともにData Segmentは全て失われてしまう。 + +この問題を解決するためには、Data Segmentを他のKey Value Store等のシステムに保存し、永続性を確保する昼用がある。 +また、当研究室で開発しているJungle Database\cite{Jungle}のようにLogファイルとして出力することでも解決ができる。 + +\subsection{DSの型情報のマネジメント} +Aliceでは型情報がないので、peek/takeする際にどんな型のデータが入っているのかがわからない。 +takeしたDSの型を確認したい場合には、そのDSをputしている部分を確認しなくてはならない。 +そのため、型情報をサポートする機能が必要である。 + +\subsection{Java以外での実装} +Alice に Garbage Collection は必要ない。Alice では、すべての Data Segment は Key Value に格納され、実行時の Data Segment は Code Segment が active な時のみにメモリ上にある。 +この最大値を見積ることは、Active Task の量を見積もれば良い。したがって、Alice にはGarbage Collection は必要ない。 +一方で、Key Value Store 上のデータは決して Garbage Collection の対象にならない。 +しかし、それは Garbage Collector には負荷をかけてしまう。 +つまり、Alice 自体は Java で実装するのには向いていない。 % 参考文献 -\chapter{参考文献} \input{bibliography.tex} % 謝辞 \chapter{謝辞} -\input{thanks.tex} +\hspace{1zw}本研究の遂行，また本論文の作成にあたり、御多忙にも関わらず終始懇切なる御指導と御教授を賜わりましたhoge助教授に深く感謝したします。 + +また、本研究の遂行及び本論文の作成にあたり、日頃より終始懇切なる御教授と御指導を賜わりましたhoge教授に心より深く感謝致します。 + +数々の貴重な御助言と細かな御配慮を戴いたhoge研究室のhoge氏に深く感謝致します。 + +また一年間共に研究を行い、暖かな気遣いと励ましをもって支えてくれたhoge研究室のhoge君、hoge君、hogeさん並びにhoge研究室のhoge、hoge君、hoge君、hoge君、hoge君に感謝致します。 + +最後に、有意義な時間を共に過ごした情報工学科の学友、並びに物心両面で支えてくれた両親に深く感謝致します。 + +\begin{flushright} + 2010年 3月 \\ hoge +\end{flushright} + % 付録 %\input{appendix.tex} diff -r a97aa059242f -r f148e6addeaf paper/source/CommandMessage.java --- a/paper/source/CommandMessage.java Fri Feb 05 21:00:41 2016 +0900 +++ b/paper/source/CommandMessage.java Thu Feb 11 01:34:35 2016 +0900 @@ -3,7 +3,6 @@ public int seq; public String key; public boolean quickFlag = false; - public boolean serialized = false; public boolean compressed = false; public int dataSize = 0; } diff -r a97aa059242f -r f148e6addeaf paper/source/ReceiveData.java --- a/paper/source/ReceiveData.java Fri Feb 05 21:00:41 2016 +0900 +++ b/paper/source/ReceiveData.java Thu Feb 11 01:34:35 2016 +0900 @@ -2,4 +2,6 @@ private Object val = null; private byte[] messagePack = null; private byte[] zMessagePack = null; + + ... }