Papers/2015/nozomi-prosym: paper-last/prosym.tex comparison

comparison paper-last/prosym.tex @ 4:a1f6921de16c

add mesureresult

author	Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
date	Sun, 29 Nov 2015 18:15:15 +0900
parents
children	50de9b120af4

comparison

equal deleted inserted replaced

-:9994b9edfaff
+:a1f6921de16c
+% withpage: ページ番号をつける (著者確認用)
+% english: 英語原稿用フォーマット
+\documentclass[techrep, ,dvipdfmx]{ipsjprosym}
+%\documentclass[withpage,english]{ipsjprosym}
+\usepackage[dvipdfmx,hiresbb]{graphicx}
+\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,%キャプションの位置
+moredelim=**[s][\color{red}]{\"compressed}{\"},
+}
+\renewcommand{\lstlistingname}{Code}
+\input{dummy.tex} %% Font
+\begin{document}
+% Title, Author %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\title{分散フレームワークAliceのPC画面配信システムへの応用}
+\author{照屋 のぞみ}{Nozomi Teruya}{琉球大学工学部情報工学科}[dpop@cr.ie.u-ryukyu.ac.jp]
+\author{河野 真治}{Shinji Kono}{琉球大学工学部情報工学科}[kono@ie.u-ryukyu.ac.jp]
+\begin{abstract}
+当研究室ではデータを Data Segment、タスクを Code Segment という単位で分割して記述する手法を提唱しており、
+それに基づく並列分散フレームワークAliceを開発している。
+Aliceが分散プログラムを記述する能力を有することは水族館の例題等において確認された。
+しかし、実用的な分散アプリケーションを構築するには圧縮形式で通信を行う機能等が必要であることが分かった。
+本研究では、 実用的なアプリケーションである画面共有システムTreeVNCをAliceで実装するにあたり必要となった圧縮機能等をMeta Computationとして実装した。
+データの多態性の実現により、扱うデータの形式を元のコードを大きく変更することなく指定することができ、ノード間通信における自由度の向上を図った。
+\end{abstract}
+\begin{jkeyword}
+並列分散フレームワーク
+\end{jkeyword}
+\maketitle
+% Body %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{研究背景と目的}
+当研究室ではデータをData Segment、タスクをCode Segmentという単位で記述する分散フレームワークAliceの開発を行っている。
+Aliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。
+ここで言う信頼性とは、定められた環境下で安定して仕様に従った動作を行うことを指す。
+Aliceでは、処理をComputationとMeta Computationに階層化し、コアな仕様と複雑な例外処理に分離する。
+そして分散環境の構築に必要な処理をMeta Computationとして提供する。
+プログラマはコアな仕様の変更を抑えつつプログラムの挙動変更ができるため、信頼性の高い分散アプリケーションの記述が可能となる。
+先行研究 \cite{senkokenkyu} の水族館の例題等において、Aliceが分散プログラムを記述する能力を有することは確認された。
+しかし、実用的な分散アプリケーションを作成するためには、動的トポロジーを管理・構成する機能や通信時にData Segmentを圧縮形式で扱う機能が必要な場合がある。
+本研究では、Alice上に実用的な分散アプリケーションの例題である画面共有システムTreeVNC \cite{treeVNC} を構築する。
+構築するにあたり必要となった圧縮などの機能を、AliceのMeta Computationとして実装する。
+そして Alice を使用していないTreeVNCとの比較を行うことでMeta Computationの役割と有効性を示す。
+\section{分散フレームワークAlice}
+\subsection{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}
+\end{center}
+\caption{CodeSegmentの依存関係 }
+\label{fig:CS}
+\end{figure}
+実際にはAliceはJavaで実装されており、DSはJavaObjectでCSはRunnableThreadである。プログラマーがCSを記述する際は、CodeSegmentクラスを継承し、DSを操作するAPIを使用する。
+\subsection{DataSegmentManager}
+DSは数値や文字列などの基本的なデータの集まりを指し、Aliceが内部にもつデータベースによって管理されている。このデータベースをAliceではDS Manager（以下DSM）と呼ぶ。
+DSには対になるString型のkeyが存在し、このkeyを指定してDSの保存・取得を行う。
+一つのkeyに対して複数のDSを登録することもでき、その場合DSはqueueに保存されFIFOで取り出される。
+DSMにはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。
+Remote DSMは他ノードのLocal DSMに対応するproxyであり、接続しているノードの数だけ存在する（図 \ref{fig:RemoteDSM} ）。
+他ノードのLocal DSMに書き込みたい場合はRemote DSMに対して書き込めば良い。
+Remote DSMを立ち上げるには、DataSegment.classが提供するconnectメソッドを用いる。
+接続したいノードのipアドレスとport番号、そして任意のManager名を指定することで立ちあげられる。その後はManager名を指定してData Segment APIを用いてDSのやり取りを行う。
+\begin{figure}[h]
+\begin{center}
+\includegraphics[width=70mm]{images/remote_datasegment.pdf}
+\end{center}
+\caption{Remote DSMは他のノードのLocal DSMのproxy }
+\label{fig:RemoteDSM}
+\end{figure}
+\newpage
+\subsection{Data Segment API}
+DSの保存・取得にはAliceが提供するAPIを用いる。
+putとupdateはOutput DS APIと呼ばれ、DSをDSMに保存する際に用いる。
+peekとtakeはInput DS APIと呼ばれ、DSをDSMから取得する際に使用する。
+\begin{itemize}
+\item {\ttfamily void put(String managerKey, String key, Object val)}
+\end{itemize}
+DSをDSMに追加するためのAPIである。第一引数はLocalDSMかRemoteDSMかといったManager名を指定する。そして第二引数で指定されたkeyに対応するDSとして第三引数の値を追加する。
+\begin{itemize}
+\item {\ttfamily void update(String managerKey, String key,  Object val)}
+\end{itemize}
+updateもDSをDSMに追加するためのAPIである。putとの違いは、queueの先頭のDSを削除してからDSを追加することである。そのためAPI実行前後でqueueの中にあるDSの個数は変わらない。
+\begin{itemize}
+\item {\ttfamily void take(String managerKey, String key)}
+\end{itemize}
+takeはDSを読み込むためのAPIである。読み込まれたDSは削除される。要求したDSが存在しなければ、CSの待ち合わせ （Blocking）が起こる。putやupdateによりDSに更新があった場合、takeが直ちに実行される。
+\begin{itemize}
+\item {\ttfamily void peek(String managerKey, String key)}
+\end{itemize}
+peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。
+\subsection{Data Segmentの表現}
+DSの表現にはMessagePack for Java \cite{MessagePack} を利用している。
+\begin{itemize}
+\item {\ttfamily DSは一般的なJavaのクラスオブジェクト}
+\item {\ttfamily MessagePackを用いて変換したbyte[]で表現されたバイナリオブジェクト}
+\end{itemize}
+の２種類があり、LocalDSMにputされた場合は一般的なJavaのクラスオブジェクトとして追加される。
+RemoteDSMにputされた場合は通信時にbyteArrayに変換されたバイナリオブジェクトが追加される。
+\subsection{Code Segmentの記述方法}
+CSをユーザーが記述する際にはCodeSegment.classを継承して記述する(ソースコード \ref{src:StartCodeSegment} , \ref{src:CodeSegment})。
+継承することによりCode Segmentで使用するData Segment APIを利用する事ができる。
+\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メソッドを呼ぶことで実行を開始させることができる。
+ソースコード \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}を実行することができる。
+TestCodeSegmentはこの"cnt"というkeyに対して依存関係があり、8行目でputが行われるとTestCodeSegmentは実行される。
+\ref{src:CodeSegment}は、0から9までインクリメントする例題である。
+2行目で取得されたDSが格納される受け皿を作る。Input DS APIがもつcreateメソッドを使うことで作成できる。
+\begin{itemize}
+\item {\ttfamily Receiver create(CommandType type)}
+\end{itemize}
+引数にはCommandTypeが取られ、指定できるCommandTypeは{\tt PEEK}または{\tt TAKE}である。
+Input DS API はCSの{\tt ids}というフィールドを用いてアクセスする。
+Output DSは、{\tt ods}が提供するput/updateメソッドをそのまま呼べばよかったが、Input DSの場合{\tt ids}にpeek/takeメソッドはなく、create/setKeyメソッド内でCommandTypeを指定して実行する。
+4行目から6行目はコンストラクタである。コンストラクタはオブジェクト指向のプログラミング言語で新たなオブジェクトを生成する際に呼び出されて内容の初期化を行う関数である。
+TestCodeSegmentのコンストラクタが呼ばれた際には、
+\begin{enumerate}
+\item CSが持つフィールド変数 {\tt Receiver input}に{\tt ids.create(CommandType.TAKE)}が行われ、{\tt input}が初期化される。
+\item 5行目にあるTestCodeSegmentのコンストラクタのTAKEが実行される。
+\end{enumerate}
+5行目はInput DS APIがもつsetKeyメソッドによりLocal DSMからDSを取得している。
+\begin{itemize}
+\item \verb+void setKey(String managerKey, String key)+
+\end{itemize}
+setKeyメソッドはpeek/takeの実行を行う。どのDSMのどのkeyに対してpeekまたはtakeコマンドを実行させるかを指定できる。コマンドの結果がレスポンスとして届き次第CSは実行される。
+runメソッドの内容としては
+\begin{enumerate}
+\item 10行目で取得されたDSをInteger型に変換してcountに代入する。
+\item 12行目でcountをインクリメントする。
+\item 16行目で次に実行されるCSが作られる。（この時点で次のCSはInput DSの待ち状態に入る）
+\item 17行目でcountをLocal DSMにputする。Input DSが揃い待ち状態が解決されたため、次のCSが実行される。
+\item 13行目が終了条件であり、countの値が10になれば終了する。
+\end{enumerate}
+となっている。
+\section{Meta Computation}
+Aliceでは、計算の本質的な処理をComputation、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。
+AliceのComputationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理と捉えられる。
+それに対して、AliceのMeta Computation は、Remoteノードとの通信時のトポロジーの構成や切断・再接続の処理と言える。
+つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。
+Aliceの機能を追加するということはプログラマ側が使うMeta Computationを追加すると言い換えられる。
+AliceではMeta Computationとして分散環境の構築等の機能を提供するため、プログラマーはCSを記述する際にトポロジー構成や切断、再接続という状況を予め想定した処理にする必要はない。
+プログラマーは目的の処理だけ記述し、切断や再接続が起こった場合の処理をMeta Computationとして指定する。
+このようにプログラムすることで、通常処理と例外処理を分離することができるため、仕様の変更を抑えたシンプルなプログラムを記述できる。
+現在Aliceには、動的・静的トポロジーの管理構成機能、ノードとの接続状態確認機能、切断・再接続時の処理を指定できる機能などのMeta Computationが用意されている。
+\section{AliceVNC}
+AliceのMeta Computationが実用的なアプリケーションの記述において有用であることを確認する。
+そのために、TreeVNCをAliceを用いて実装したAliceVNCの作成を行った。
+TreeVNCとは、当研究室で開発を行っている授業向け画面共有システムである。
+オープンソースのVNCであるTightVNC \cite{tightVNC} をもとに作られている。
+授業でVNCを使う場合、１つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう。
+この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである（図 \ref{fig:TreeVNC} ）。
+TreeVNCは通信処理部分の記述が大変複雑になっている。しかし、Aliceで記述すれば本質的な処理とそれを支える通信処理部分で分離できる。
+そのため、TightVNCからの修正も少なく、見通しの良い記述で構成可能と期待される。
+\begin{figure}[h]
+\begin{center}
+\includegraphics[width=80mm]{images/TreeVNC.pdf}
+\end{center}
+\caption{AliceVNC の構造}
+\label{fig:TreeVNC}
+\end{figure}
+\newpage
+\section{Aliceの新機能}
+実用的なアプリケーションであるTreeVNCをAlice上で実装することで、Aliceに必要な機能を洗い出した。
+\subsection{転送機能}
+Input DSをRecieverに取得したあと、プログラマーはRecieverから値を任意の型で取り出し、値を操作した後putメソッドで再度別クラスに変換されOutput DSとして出力する。
+しかし、Input DSとして取得したデータをそのまま子ノードにOutput DSとして出力する場合、一度Recieverから取り出し再変換する操作は無駄である。
+そこで、Input DSとして受け取ったDSをそのままOutput DSとして転送する機能をput/updateとは別にflipメソッドをData Segment APIに実装した。
+Input DSであるReceiverを展開せずにflipメソッドに引数として渡すことで、展開のオーバーヘッドをなくしている。
+TreeVNCでは親ノードから受け取った画面データをそのまま子ノードに配信するため、Meta Computationとして転送機能が有用である。
+\subsection{Data Segmentの表現の追加（圧縮機能）}
+TreeVNCでは画面配信の際、データを圧縮してノード間通信を行っている。
+そのため、AliceVNCにも圧縮されたデータ形式を扱える機能が必要だと考えた。
+しかし、ただデータを圧縮する機構を追加すればいいわけではない。
+AliceVNCでは、ノードは受け取った画面データを描画すると同時に、子ノードのRemote DSMに送信する。
+ノードはDSを受信するとそれを一度解凍して画面を表示し、再圧縮して子ノードに送信する。
+しかし、受け取ったデータを自分の子ノードに対して送信する際には、解凍する必要はない。
+圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる。
+そこで、１つのData Segmentに対し複数の表現を持たせることで、必要に応じた形式でDSを扱うことを可能にした。
+DSを扱うReceiveData.classに、次の3種類の表現を同時に持つことができる。
+\begin{enumerate}
+\item 一般的なJavaのクラスオブジェクト
+\item MessagePack for Javaでシリアライズ化されたバイナリオブジェクト
+\item 2を圧縮したバイナリオブジェクト
+\end{enumerate}
+ソースコード \ref{src:ReceiveData} はReceiveData.classが持つ表現であり、{\tt val}に(1) 一般的なJavaのクラスオブジェクト の表現でデータ本体が保存される。
+{\tt messagePack}には(2) シリアライズ化されたバイナリオブジェクトが保存され、通常のRemoteDSMへの通信にこの表現が扱われる。
+そして、{\tt zMessagePack}には(3) 圧縮されたバイナリオブジェクトが保存される。
+\begin{table}[html]
+\lstinputlisting[label=src:ReceiveData, caption=データを表現するクラス]{source/ReceiveData.java}
+\end{table}
+\newpage
+また、圧縮状態を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerを追加した。
+Compressed DSMの内部では、put/updateが呼ばれた際にReceiveData.classが圧縮表現を持っていればそれを使用し、持っていなければその時点で圧縮表現を作ってput/updateを行う。
+ソースコード \ref{src:before} はRemoteからDSをtakeしインクリメントしてLocalにputすることを10回繰り返す例題である。
+これをDSを圧縮形式で行いたい場合、ソースコード \ref{src:after} のように指定するDSM名の先頭に"compressed"をつければCompressed DSM内部の圧縮Meta Computationが走りDSを圧縮状態で扱うようになる。
+これによりユーザは指定するDSMを変えるだけで、他の計算部分を変えずに圧縮表現を持つDSを扱うことができる。
+ノードは圧縮されたDSを受け取った後、そのまま子ノードにflipメソッドで転送すれば圧縮状態のまま送信されるので、送信の際の再圧縮がなくなる。
+画面表示の際はReceiveData.class内の{\tt asClass()}(ソースコード\ref {src:asClass} )を使うことで適切な形式でデータを取得できる。
+{\tt asClass()}はDSを目的の型にcastするメソッドであり、ReceiveData.classが圧縮表現だけを持っている場合はこのメソッド内で解凍してcastを行っている。
+これによりDSの表現を必要になったときに作成できる。
+\newpage
+\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}
+\begin{table}[html]
+\lstinputlisting[label=src:asClass, caption=asClassの処理]{source/asClass.java}
+\end{table}
+\subsection{Aliceの通信プロトコルの変更}
+2.4 Data Segmentの表現 で述べたように、Remoteからputされたデータは必ずシリアライズ化されておりbyteArrayで表現される。
+しかし、TreeVNCのようにもとからbyteArrayの画像データをputする場合、MessagePackでシリアライズされたものかの判別が付かない。
+また、データの表現に圧縮したbyteArrayを追加したため、RemoteからputされたbyteArrayが圧縮されているのかそうでないのかを判断する必要がある。
+そこで、Aliceの通信におけるヘッダにあたるCommandMessage.class(ソースコード \ref{src:CommandMessage} )にシリアライズ状態表すフラグと、圧縮状態を表すフラグを追加した。
+\begin{table}[html]
+\lstinputlisting[label=src:CommandMessage, caption=CommandMessage]{source/CommandMessage.java}
+\end{table}
+\newpage
+\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
+serialized&データ本体のシリアライズ状態を示す\\
+\hline
+compressed&データ本体の圧縮状態を示す\\
+\hline
+dataSize&圧縮前のデータサイズを表す\\
+\hline
+\end{tabular}
+\end{center}
+\end{table}
+これによってputされたDSMはフラグに応じた適切な形式でReceiveData.class内にDSを格納できる。
+また、CommandMessage.classに圧縮前のデータサイズも追加したことで、適切な解凍が可能になった。
+\section{評価と考察}
+TreeVNCをAlice上で構築するために必要な機能をAliceのMeta Computationとして実装した。
+それにより、AliceVNCが簡潔な記述でTreeVNCと同等の性能を出せれば、実用的な分散アプリケーションの実装においてAliceのMeta Computationは有用であるといえる。
+そこで、TreeVNCとAliceVNCの性能評価としてメッセージ伝達速度の比較を、コードの評価としてコード量とその複雑度の比較を行った。
+また、AliceのMeta Computationの価値を明確にするため、他言語・フレームワークとの比較を行った。
+\subsection{メッセージ伝達速度の比較}
+TreeVNC/AliceVNCにおいて、配信する画像データは構成した木を伝ってノードに伝搬され、接続する人数が増える毎に木の段数は増えていく。
+そこで、木の段数ごとにメッセージの到達にどれぐらい時間がかかっているかを計測した。
+\textbf{実験環境}
+講義内で学生に協力してもらい、最大17名の接続がある中でTreeVNC、AliceVNC(圧縮・転送機能あり)、AliceVNC(圧縮・転送機能なし)の木の段数1~3の測定を行った。
+\textbf{実験内容}
+ルートノードから画面データを子ノードに伝搬する際に、計測用のヘッダをつけたパケットトを子ノードに送信する。
+各子ノードはパケットを受け取り自身のViewerに画面データを表示すると同時に、計測用ヘッダ部分のみのDSを作成し、親ノードに送り返す（図 \ref{fig:mesure}） 。
+計測用DSは木を伝ってルートノードまで送り返され、ルートノードは受け取った計測用DSから到達時間を計算する。
+\begin{figure}[h]
+\begin{center}
+\includegraphics[width=70mm]{images/delay.pdf}
+\end{center}
+\caption{各ノードごとに到達時間を測定}
+\label{fig:mesure}
+\end{figure}
+計測用のヘッダは以下の要素で構成されている。
+\begin{table}[htbp]
+\caption{計測用ヘッダの変数名の説明}
+\label{tb:variable}
+\begin{center}
+\begin{tabular} {|l|l|}
+\hline
+変数名&説明\\
+\hline
+time&ルートノードがパケットを送信した時刻\\
+\hline
+depth&木の段数。初期値=1。\\
+\hline
+dataSize&送信時の形式に変換済みの画面データのサイズ\\
+\hline
+\end{tabular}
+\end{center}
+\end{table}
+timeにはパケットの送信時刻を、dataSizeには画面データのサイズを付けて送信する。
+今回、TreeVNCとAliceVNC(圧縮・転送機能あり)では圧縮形式の画面データのサイズを、AliceVNC(圧縮・転送機能なし)ではMessegePack形式でのサイズをdataSizeにセットする。
+depthは各ノードに到達するごとにインクリメントされる。
+計算方法をソースコード \ref{src:mesurement}に示す。
+到達時間は、計測用DSを受け取った時刻とDSのtime（送信した時刻）の差をとる。
+この到達時間は画面データがノードまで到達した時間と計測DSをルートまで送り返す時間を含めているが、送り返す時間は誤差として考える。
+また、depthは各ノードに到達するごとにインクリメントされるため、送り返す際もインクリメントされる。そのため、木の段数を計算するにはdepthを1/2した値となる。
+\begin{table}[html]
+\lstinputlisting[label=src:Mesurement, caption=到達時間・木の段数の計測方法]{source/mesurement.java}
+\end{table}
+\textbf{実験結果}
+木の段数ごとに散布図を示す（図\ref{fig:TreeVNC_delay} ~ \ref{fig:AliceVNC_notcompress_delay}）。
+X軸が画面データのサイズ(byte)、Y軸が計算した到達時間(ms)である。
+実験時間の都合上、AliceVNC（圧縮・転送機能あり）の計測時間が他より短くなってしまったためプロットされた点の数が少なくなっている。
+また、それぞれ3段目の図で処理に10秒以上かかっている点の集合が見られるが、これは今回の実験において3段目にPCのスペック上処理が遅いノードが1台あったためである。そのため比較においてこの点集合は無視する。
+どの図も同様の傾向があり、画面データのサイズが小さいうちは処理時間も5ms程度だが、50000byte以上から比例して処理時間も遅くなっている。このことからAliceVNCはTreeVNCと同等の処理・同等の性能があることがわかる。
+また、AliceVNCを圧縮機能の有無でデータサイズ比較すると、圧縮機能のないAliceVNCはデータサイズがほとんど1000byte以上なのに対し、圧縮機能のあるAliceVNCではTreeVNC同様10byte程度のサイズに抑えることに成功している。
+さらに転送機能の有無で比較した場合、転送機能がないAliceVNCでは木の段数に関係なく1000ms近く到達に時間がかかってしまっているが、転送機能のあるAliceVNCではデータサイズが大きくなっても100ms程度に抑えられている。
+このことから、圧縮・転送のMeta Computationは分散通信において有用であると言える。
+\newpage
+\begin{figure}[h]
+\begin{center}
+\includegraphics[width=70mm]{images/TreeVNC_depth1.pdf}
+\includegraphics[width=70mm]{images/TreeVNC_depth2.pdf}
+\includegraphics[width=70mm]{images/TreeVNC_depth3.pdf}
+\end{center}
+\caption{TreeVNCの測定結果}
+\label{fig:TreeVNC_delay}
+\end{figure}
+\newpage
+\begin{figure}[h]
+\begin{center}
+\includegraphics[width=70mm]{images/AliceVNC_notcompress_depth1.pdf}
+\includegraphics[width=70mm]{images/AliceVNC_notcompress_depth2.pdf}
+\includegraphics[width=70mm]{images/AliceVNC_notcompress_depth3.pdf}
+\end{center}
+\caption{AliceVNC(圧縮・転送機能なし)の測定結果}
+\label{fig:AliceVNC_notcompress_delay}
+\end{figure}
+\newpage
+\begin{figure}[h]
+\begin{center}
+\includegraphics[width=70mm]{images/AliceVNC_compress_depth1.pdf}
+\includegraphics[width=70mm]{images/AliceVNC_compress_depth2.pdf}
+\includegraphics[width=70mm]{images/AliceVNC_compress_depth3.pdf}
+\end{center}
+\caption{AliceVNC(圧縮・転送機能あり)の測定結果}
+\label{fig:AliceVNC_compress_delay}
+\end{figure}
+\newpage
+\subsection{コードの比較}
+\textbf{コード量}
+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}
+\textbf{コードの複雑度}
+コード量の比較で述べたように、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は全てプログラマが記述したコードであり、通信処理や画面データの読み込みなどの記述が入り組んで書かれている。
+しかし、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と同等の性能を持つ分散アプリケーションの記述ができ、かつコードの修正量・複雑度共に低く抑える能力を有することがわかった。
+\subsection{他言語・フレームワークとの比較}
+\textbf{Erlang}
+\textbf{Akka}
+\textbf{?}
+\section{まとめ}
+並列分散フレームワークAliceの計算モデルと実装について説明を行い、Aliceにおけるプログラミング手法を述べた。
+Aliceが実用的なアプリケーションを記述するために必要なMeta Computationとして、データの多態性を実現し、指定するDSMの切り替えで扱うデータ表現を変えるようにした。
+これにより、必要に応じた形式を扱うことができ、ユーザが記述するComputation部分を大きく変えずに自由度の高い通信を行うことが可能になった。
+同様の手法を用いれば、圧縮形式以外にも暗号形式・JSON形式などの複数のデータ表現をユーザに扱いやすい形で拡張することができる。
+Aliceに圧縮等のMeta Computationを追加したことで、AliceVNCではシンプルな記述でTreeVNCと同等の性能を提供できると期待される。
+今後の課題としては、圧縮機能をAliceVNCで用いることでMeta Computationの有効性を測る必要がある。
+また、AliceのMeta ComputationにProxy機能を実装することで、TreeVNCでは実装が困難であったNAT越えの機能を提供できると期待される。
+\nocite{*}
+\bibliographystyle{ipsjunsrt}
+\bibliography{prosym}
+\end{document}

Mercurial > hg > Papers > 2015 > nozomi-prosym

comparison paper-last/prosym.tex @ 4:a1f6921de16c