# HG changeset patch # User Nozomi Teruya # Date 1455452110 -32400 # Node ID 1f36a64a38684f4f81f312b54ccce9c70672d757 # Parent f148e6addeaf7677d1dad9fe541486916ae8243b fix fig position diff -r f148e6addeaf -r 1f36a64a3868 paper/bibliography.tex --- a/paper/bibliography.tex Thu Feb 11 01:34:35 2016 +0900 +++ b/paper/bibliography.tex Sun Feb 14 21:15:10 2016 +0900 @@ -2,13 +2,57 @@ \def\line{−\hspace*{-.7zw}−} \begin{thebibliography}{99} -%\bibitem{*}内の * は各自わかりやすい名前などをつけて、 -%論文中には \cite{*} のように使用する。 -%これをベースに書き換えた方が楽かも。 -%書籍、論文、URLによって若干書き方が異なる。 -%URLを載せる人は参考にした年月日を最後に記入すること。 + +\bibitem{senkokenkyu} +{Yu SUGIMOTO and Shinji KONO}: Code Segment と Data Segment + によるプログラミング手法，第54回プログラミング・シンポジウム (2013). + +\bibitem{senkokenkyu2} +{Yu SUGIMOTO and Shinji KONO}: + 分散フレームワークAliceのDataSegmentの更新に関する改良，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS) + (2013). + +\bibitem{treeVNC} +{Yu TANINARI, Nobuyasu OSHIRO and Shinji KONO}: + VNCを用いた授業用画面共有システムの設計・開発，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS) + (2012). + +\bibitem{dot} +: Dot Language, \url{http://www.graphviz.org/}. + +\bibitem{tightVNC} +: {TightVNC Software}, \url{http://www.tightvnc.com}. + +\bibitem{MessagePack} +: MessagePack, \url{http://msgpack.org/}. +\bibitem{complaxy} +McCABE, T.~J.: A Complexity Measure, {\em IEEE TRANSACTIONS ON SOFTWARE + ENGINEERING VOL. SE-2, NO.4} (1976). -\bibitem{hoge} -hoge +\bibitem{Erlang} +: Erlang, \url{http://www.erlang.org/}. + +\bibitem{Akka} +Lockney, T. and Tay, R.: Developing an Akka Edge, {\em Bleeding Edge Press} + (2014). + +\bibitem{CbC} +{Kaito TOKUMORI and Shinji KONO} +:Implementing Continuation based language in LLVM and Clang, LOLA 2015 Kyoto (2015). + +\bibitem{Gears} +{Shohey KOKUBO, Tatsuki IHA and Shinji Kono} +:Monad に基づくメタ計算を基本とする Gears OS の設計, 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)(2015). + +\bibitem{MPICH} + +\bibitem{sigOS} +{Yu SUGIMOTO, Nozomi TERUYA and Shinji KONO} +:分散フレームワーク Alice の圧縮機能, 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS) (2015). + +\bibitem{prosym} +{Nozomi TERUYA and Shinji KONO} +:分散フレームワークAliceのPC画面配信システムへの応用, 第57回プログラミング・シンポジウム(2016). + \end{thebibliography} diff -r f148e6addeaf -r 1f36a64a3868 paper/main.tex --- a/paper/main.tex Thu Feb 11 01:34:35 2016 +0900 +++ b/paper/main.tex Sun Feb 14 21:15:10 2016 +0900 @@ -238,8 +238,14 @@ プログラマは目的の処理だけ記述し、切断や再接続が起こった場合の処理をMeta Computationとして指定する。 このようにプログラムすることで、通常処理と例外処理を分離することができるため、仕様の変更を抑えたシンプルなプログラムを記述できる。 +現在Aliceには、トポロジーの構成・管理機能、ノードの生存確認機能、ノードの切断・再接続時の処理管理機能などのMeta Computationが用意されている。 + +\newpage + \subsection{Meta Code Segment と Meta Data Segment} -AliceのMeta ComputationもCS/DSにより実現され、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が間に接続されて処理を行っている。 @@ -251,10 +257,15 @@ \label{fig:metaCS} \end{figure} +Meta DSは基本的にAliceを構成するCSによってのみ管理され、プログラマは認識できない。 +しかし一部のMeta DSはプログラマがアプリケーションに利用することもできる。 +例えば、トポロジー管理のMeta Computationなどで使われる"\_CLIST"というMeta DSには、利用可能なRemote DSMの情報が管理されている。 +プログラマはこのMeta DSを取得しRemote DSM名を指定することで、動的にDSの伝搬などを行うことができる。 + + \newpage \section{Aliceが持つMeta Computation} -Aliceでは分散環境構築のためにさまざまなMeta Computationが用意されている。 \subsection{Topology Manager} Aliceでは、ノード間の接続管理やトポロジーの構成管理を、Topology ManagerというMeta Computationが提供している。 @@ -262,12 +273,16 @@ トポロジーファイルはDOT Language\cite{dot}という言語で記述される。 DOT Languageとは、プレーンテキストを用いてデータ構造としてのグラフを表現するためのデータ記述言語の一つである。 ソースコード\ref{src:topologyfile}は3台のノードでリングトポロジーを組むときのトポロジーファイルの例である。 + \begin{table}[html] \lstinputlisting[label=src:topologyfile, caption=トポロジーファイルの例]{source/TopologyFile.dot} \end{table} -また、DOT Languageファイルはdotコマンドを用いてグラフの画像ファイルを生成することができる。そのため、記述したトポロジーが正しいか可視化することが可能である。 +DOT Languageファイルはdotコマンドを用いてグラフの画像ファイルを生成することができる。そのため、記述したトポロジーが正しいか可視化することが可能である。 Topology Managerはトポロジーファイルを読み込み、参加を表明したクライアント（以下、Topology Node）に接続するべきクライアントのIPアドレスやポート番号、接続名を送る（図\ref{fig:topologymanager}）。 + +\newpage + また、トポロジーファイルでlavelとして指定した名前はRemote DSMの名前としてTopology Nodeに渡される。 そのため、Topology NodeはTopology ManagerのIPアドレスさえ知っていれば自分の接続すべきノードのデータを受け取り、ノード間での正しい接続を実現できる。 \begin{figure}[h] @@ -285,6 +300,7 @@ そしてTopology Managerが持つトポロジー情報が更新される。 現在Topology Managerでは動的なトポロジータイプとして二分木に対応している。 +\newpage \subsection{Keep Alice} ノード間通信はRemote DSMに対してputやtakeを行うことでのみ発生する。 @@ -303,22 +319,17 @@ MMORPGでは、試合の最中にサーバーからユーザーが切断された場合、自動的にユーザーが操作するキャラクターをゲームの開始時の位置に戻すという処理が実行される。 同様に、Aliceを用いたアプリケーションでもノードの切断時に対する処理を用意したい場合がある。 そこで、Aliceが切断を検知した際に任意のCSを実行できる機能(ClosedEventManager)を追加した。 -プログラマは切断の際に実行したいCSを書き、ClosedEventManagerに登録しておけば良い(ソースコード\ref{src:closedEvent})。 -\begin{table}[html] - \lstinputlisting[label=src:closedEvent, caption=切断時に実行されるCSの登録方法]{source/RegisterEvent.java} -\end{table} - +プログラマは切断の際に実行したいCSを書き、ClosedEventManagerに登録しておけば良い。 また、再接続してきたノードに対し通常の処理とは別の処理を行わせたい場合がある。 そのため、切断時と同様に再接続してきたノードに任意のCSを実行できるMeta Computationも用意した。 - % AliceVNC \chapter{AliceのTreeVNCへの応用} +AliceのMeta Computationが実用的なアプリケーションの記述において有用であることを確認する。 +そのために、TreeVNCをAliceを用いて実装したAliceVNCの作成を行った\cite{sigOS}。 + \section{TreeVNC} -AliceのMeta Computationが実用的なアプリケーションの記述において有用であることを確認する。 -そのために、TreeVNCをAliceを用いて実装したAliceVNCの作成を行った。 - TreeVNCとは、当研究室で開発を行っている授業向け画面共有システムである。 オープンソースのVNCであるTightVNC \cite{tightVNC} をもとに作られている。 授業でVNCを使う場合、１つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう(図 \ref{fig:vncstructure})。 @@ -342,8 +353,9 @@ \end{tabular} \end{figure} +\newpage - +\section{AliceVNC} 図 \ref{fig:TreeVNC}はAliceVNCを実現するための構成である。leftとrightのRemote DSMを用意し子ノードと接続することで木構造を実現する。 \begin{figure}[h] @@ -361,7 +373,8 @@ \newpage -\section{圧縮のMeta Computationの追加} +\chapter{圧縮のMeta Computationの追加} +\section{圧縮のMeta Data Segment} TreeVNCでは画面配信の際、データを圧縮してノード間通信を行っている。 そのため、AliceVNCにも圧縮されたデータ形式を扱える機能が必要だと考えた。 しかし、ただデータを圧縮する機構を追加すればいいわけではない。 @@ -385,6 +398,8 @@ この2つの形式は従来のAliceが持っていた表現である。 今回、Remote DSMに圧縮形式での通信を行いたいため、(3)の圧縮表現を追加した。 +\newpage + ソースコード \ref{src:ReceiveData1} は変更前のReceiveData.classである。 変更前はDSの表現は１つでフラグによって、Local DSM にputする(1)の形式とRemote DSMにputする(2)の形式を判別していた。 しかしこの実装では圧縮形式と非圧縮形式を同時に持つことができないため、AliceVNCでは解凍・再圧縮が必要になってしまう。 @@ -405,7 +420,10 @@ \end{table} -また、圧縮表現を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerを追加した。 +\newpage + +\section{圧縮のMeta Code Segment} +圧縮表現を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerを追加した。 Compressed DSMの内部では、put/updateが呼ばれた際にReceiveData.classが圧縮表現を持っていればそれを使用し、持っていなければその時点で圧縮表現を作ってput/updateを行う。 Local Compressed DSM は表現の判別や変換を行うだけで、操作する対象は Local DSM と同じDSを指すため、DSの管理が別々になるわけではない。 @@ -422,6 +440,7 @@ \lstinputlisting[label=src:after,caption=圧縮したDSを扱うCSの例]{source/afterCompress.java} \end{table} +この機能は先述のMeta Data Segmentを扱うMeta Code Segmentと言える。 これによりユーザは指定するDSMを変えるだけで、他の計算部分を変えずに圧縮表現をDS内で持つことができる。 ノードは圧縮されたDSを受け取った後、そのまま子ノードにflipメソッドで転送すれば圧縮状態のまま送信されるので、送信の際の再圧縮がなくなる。 @@ -433,11 +452,13 @@ これによりDSの表現を必要になったときに作成できるため、プログラマはどんな形式でDSを受け取ってもDSを編集可能な形式として扱うことができる。 また、複数表現は必要なときにしか作成されないため、メモリ使用量も必要最低限に抑えることができる。 +\newpage + \section{Aliceの通信プロトコルの変更} 4.2で述べたように、Remoteからputされたデータは必ずシリアライズ化されておりbyteArrayで表現される。 しかし、データの表現に圧縮したbyteArrayを追加したため、RemoteからputされたbyteArrayが圧縮されているのかそうでないのかを判別がつかなくなった。 -そこで、Aliceの通信におけるヘッダにあたるCommandMessage.class(ソースコード\ref {src:CommandMessage} \ref{fig:variable})に圧縮状態を表すフラグを追加した。 +そこで、Aliceの通信におけるヘッダにあたるCommandMessage.class(ソースコード\ref {src:CommandMessage} 表 \ref{tb:variable})に圧縮状態を表すフラグを追加した。 これによってputされたDSMはフラグに応じた適切な形式でReceiveData.class内にDSを格納できる。 また、CommandMessage.classに圧縮前のデータサイズも追加したことで、適切な解凍が可能になった。 @@ -476,7 +497,6 @@ \newpage -\section{Topology Managerの複数対応} % 実験 \chapter{評価と考察} @@ -510,7 +530,7 @@ \section{TreeVNCとAliceVNCの比較} TreeVNCをAlice上で構築するために必要な機能をAliceのMeta Computationとして実装した。 これにより、AliceVNCが簡潔な記述でTreeVNCと同等の性能を出せれば、実用的な分散アプリケーションの実装においてAliceのMeta Computationは有用であるといえる。 -そこで、TreeVNCとAliceVNCの性能評価としてメッセージ伝達速度の比較を、コードの評価としてコード量とその複雑度の比較を行った。 +そこで、TreeVNCとAliceVNCの性能評価としてメッセージ伝達速度の比較を、コードの評価としてコード量とその複雑度の比較を行った\cite{prosym}。 \subsection{メッセージ伝達速度の比較} TreeVNC/AliceVNCにおいて、配信する画像データは構成した木を伝ってノードに伝搬され、接続する人数が増える毎に木の段数は増えていく。 @@ -552,10 +572,11 @@ この到達時間は画面データがノードまで到達した時間と計測DSをルートまで送り返す時間を含めているが、送り返す時間は誤差として考える。 また、depthは各ノードに到達するごとにインクリメントされるため、送り返す際もインクリメントされる。そのため、木の段数を計算するにはdepthを1/2した値となる。 -　 + \textbf{実験結果} + 3段目の測定結果の散布図を示す（図\ref{fig:TreeVNC_delay} 〜 \ref{fig:AliceVNC_compress_delay}）。 X軸が画面データのサイズ(byte)、Y軸が計算した到達時間(ms)である。 実験時間の都合上、AliceVNCの計測時間が他より短くなってしまったためプロットされた点の数が少なくなっている。 @@ -565,23 +586,22 @@ どの図も同様の傾向があり、画面データのサイズが小さいうちは処理時間も5ms程度だが、50000byte以上から比例して処理時間も遅くなっている。 このことからAliceVNCはTreeVNCと同等の処理性能があることがわかる。 -\begin{figure}[h] + +\begin{figure}[htbp] \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 +\newpage　 \subsection{コード量比較} @@ -594,7 +614,6 @@ しかし、AliceVNCではTightVNCにほとんど修正を加えることなくトポロジー構成等のAliceのMeta Computationを使うために新しいクラスを作成したのみであった。 そのためTreeVNCに比べ75\%も仕様の変更が抑えられている。 \begin{table}[htbp] -\caption{コード量の比較} \label{tb:code} \begin{center} \begin{tabular} {|l|l|l|l|} @@ -612,7 +631,6 @@ \end{table} - \subsection{コードの複雑度比較} コード量の比較で述べたように、TreeVNCはTightVNCからの変更が多い。 その理由の一つがトポロジーの構成や通信処理がコアな仕様と分離できておらず、 @@ -624,15 +642,9 @@ 一般的に、循環的複雑度が10以下であればバグ混入率の少ない非常に良いコードとされる。 計測にはIntelliJのCodeMetrics計測プラグインであるMetricsReloadedを使用した。 -表\ref{tb:complex}はTightVNC、TreeVNC、AliceVNCにおける循環的複雑度の比較である。 -プロジェクト全体でのクラスの複雑度の平均値と最高値をとった。 -平均値・最高値ともにAliceVNCのほうが複雑度が低いことから、Aliceではシンプルな記述が可能だということがわかる。 +\newpage -TreeVNCで最高値を出したTreeRFBProto.classは全てプログラマが記述したコードであり、データの待ち合わせのためのタイマー処理や通信処理、画面データの圧縮処理などの複数のスレッド処理が集中した複雑なコードになっている。 -これをAliceで記述した場合、データの待ち合わせはCSが行うためプログラマがデータの不整合を気にする必要はなく、また通信処理や圧縮処理もMeta Computationが提供するためコードが複雑になることはない。 - -AliceVNCで複雑度の最高値を出したSwingViewerWindow.classはTightVNCで最高値を出したクラスと同じであり、コード量の比較でも示したようにAliceVNCで変更を加えた点がほとんどない。つまりこの複雑度は元来TightVNCが持っている複雑度と言える。 - +表\ref{tb:complex}はTightVNC、TreeVNC、AliceVNCにおける循環的複雑度の比較である。 \begin{table}[htbp] \caption{複雑度の比較} @@ -652,10 +664,18 @@ \end{center} \end{table} +プロジェクト全体でのクラスの複雑度の平均値と最高値をとった。 +平均値・最高値ともにAliceVNCのほうが複雑度が低いことから、Aliceではシンプルな記述が可能だということがわかる。 + +TreeVNCで最高値を出したTreeRFBProto.classは全てプログラマが記述したコードであり、データの待ち合わせのためのタイマー処理や通信処理、画面データの圧縮処理などの複数のスレッド処理が集中した複雑なコードになっている。 +これをAliceで記述した場合、データの待ち合わせはCSが行うためプログラマがデータの不整合を気にする必要はなく、また通信処理や圧縮処理もMeta Computationが提供するためコードが複雑になることはない。 + +AliceVNCで複雑度の最高値を出したSwingViewerWindow.classはTightVNCで最高値を出したクラスと同じであり、コード量の比較でも示したようにAliceVNCで変更を加えた点がほとんどない。つまりこの複雑度は元来TightVNCが持っている複雑度と言える。 + AliceVNCとTreeVNCの性能比較・コード比較から、AliceVNCはTreeVNCと同等の性能を持つ分散アプリケーションの記述ができ、かつコードの修正量・複雑度共に低く抑える能力を有することがわかった 。 - +\newpage \section{他言語等との比較} Aliceが採用しているCS/DSのプログラミングモデルやMeta Computationの特性を明確にするため、他言語・フレームワークとの類似点・相違点を比較した。 @@ -711,7 +731,7 @@ \begin{figure}[h] \begin{center} - \includegraphics[width=75mm]{images/overNAT.pdf} + \includegraphics[width=120mm]{images/overNAT.pdf} \end{center} \caption{複数のTopology ManagerでNAT超えを実現} \label{fig:overNAT} @@ -730,20 +750,30 @@ \subsection{APIの再設計} 2.4で示したように、DSを取得するときのAPIはpeek/takeが直接扱えず、create/setKeyを組み合わせてプログラミングしなければならない。 -この設計だとプログラマにとってわかりづらく、コンストラクタ内でtakeを行いたい場合はsetKeyを必ず最後に呼ばなければならないといった注意点がある。 +この設計だとプログラマにとってわかりづらく、コンストラクタ内でtakeを行いたい場合はsetKeyを必ず最後に呼ばなければならない等の注意点がある。 put/update/flipと同様に、peek/takeをそのまま呼べるように再設計する必要がある。 +\subsection{DSの型情報のマネジメント} +Aliceでは型情報がないので、peek/takeする際にどんな型のデータが入っているのかがわからない。 +takeしたDSの型を確認したい場合には、そのDSをputしている部分を確認しなくてはならない。 +そのため、型情報をサポートする機能が必要である。 + +\subsection{DSとMeta DSの領域分け} +現在、DSとMeta DSは同じData Segment Managerで管理されており、同じAPIを利用してアクセスされる。 +そのため誰でもMeta DSの変更が可能になってしまっている。 +プログラマが定義しようとしたKeyが偶然Aliceがもともと持っているMeta DSのKeyと一致してしまった場合、ユーザーが意図した動作にならずエラーとなる状況は充分にありえる。 +しかもMeta DSはプログラマ側からは認識できないためエラーの解決がしづらい。 +このような事態を避けるためにも、DSの領域分けが必要である。 + +また、現在はMeta DSに対してtakeすることもできるため、アクセスしようとしたKeyに対してDSが存在せず、Aliceが機能しなくなる場合も想定される。 +そのため、プログラマ側のCSとMeta CSを区別し、CSからはpeekのみ許可するMeta Computationも必要になってくると考えられる。 + \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 は必要ない。 @@ -751,23 +781,29 @@ しかし、それは Garbage Collector には負荷をかけてしまう。 つまり、Alice 自体は Java で実装するのには向いていない。 +当研究室ではCode Segment/Data Segmentのプログラミング形式で記述する言語CbC + +(Continuation based C)\cite{CbC}と、CbCを用いて記述されるGears OS\cite{Gears}の開発を行っている。 +そのため、CbCを用いてGears OSの分散機構の一部としてAliceを再設計することが望ましい。 + % 参考文献 \input{bibliography.tex} % 謝辞 \chapter{謝辞} -\hspace{1zw}本研究の遂行，また本論文の作成にあたり、御多忙にも関わらず終始懇切なる御指導と御教授を賜わりましたhoge助教授に深く感謝したします。 +\hspace{1zw}本研究の遂行，また本論文の作成にあたり、ご多忙にも関わらず終始懇切なる御指導と御教授を賜わりました河野真治助教授に深く感謝したします。 -また、本研究の遂行及び本論文の作成にあたり、日頃より終始懇切なる御教授と御指導を賜わりましたhoge教授に心より深く感謝致します。 +そして、数々の貴重な御助言と技術的指導を戴いた杉本優さん、比嘉健太さん、伊波立樹さん、並びに並列信頼研究室の皆様に感謝いたします。 -数々の貴重な御助言と細かな御配慮を戴いたhoge研究室のhoge氏に深く感謝致します。 +また、横山大作教授をはじめ、OS研究会、プログラミング・シンポジウムにおいて多くのフィードバックを頂いた先生方に感謝いたします。 -また一年間共に研究を行い、暖かな気遣いと励ましをもって支えてくれたhoge研究室のhoge君、hoge君、hogeさん並びにhoge研究室のhoge、hoge君、hoge君、hoge君、hoge君に感謝致します。 +本研究を遂行するにあたり参考にさせていただいた先行研究のFederated Linda, Cerium, TreeVNC の設計・実装に関わった全ての先輩方に感謝いたします。 -最後に、有意義な時間を共に過ごした情報工学科の学友、並びに物心両面で支えてくれた両親に深く感謝致します。 +最後に、日々の研究生活を支えてくださった米須智子さん、情報工学科の方々、そして家族に心より感謝いたします。 + \begin{flushright} - 2010年 3月 \\ hoge + 2016年 2月 \\ hoge \end{flushright}