# HG changeset patch # User Nozomi Teruya # Date 1430857417 -32400 # Node ID 4a7fa91ef60a1a45745d4d3d254685e6e63050f7 # Parent 683044bd29ed6987eb7ce94812cb83d205397a1a not fix English Abstract diff -r 683044bd29ed -r 4a7fa91ef60a paper/chapter3.tex --- a/paper/chapter3.tex Tue May 05 17:26:13 2015 +0900 +++ b/paper/chapter3.tex Wed May 06 05:23:37 2015 +0900 @@ -1,184 +1,107 @@ \section{Aliceの新機能} -水族館の例題によって、Aliceを用いて分散プログラムを記述可能であることを確認した。 -次に実用的なアプリケーションであるTreeVNCをAlice上で実装することで、Aliceに必要な機能を洗い出した。 - -\subsection{Dynamic Topologyへの対応} -第2章で示したように分散フレームワークAliceはTopology Fileを読み込むことでTopologyを構成する。 -つまり、予め参加するノードの台数が決まっている必要がある。また、Topologyに全ノードが参加するまでアプリケーションが起動しない。 - -実際のアプリケーションでは、参加するノードの数は決まっておらず、Topologyを動的に変化させる必要がある。 -そこで、AliceにDynamic Topology Managerを追加した。 - -Dynamic Topologyの場合は、新しくTopology Nodeがアプリケーションに参加するたびにTopology ManagerからTopology Nodeに対して、接続すべきTopology Nodeの情報がputされ接続処理が順次行われる。 -\subsection{Keep Alive} -ノード間の通信は、Remote DSMに対してputやpeekを行うことでのみ発生する。アプリケーション次第では長時間通信が行われない可能性がある。通信が行われない間にRemote DSMとの接続が切れた場合、次の通信が行われるまで切断を発見することができない。また、接続状態ではあるが問題が発生し、応答に時間がかかる場合も考えられる。 - -以上の問題を検知するためにアプリケーションではKeep Aliveという、定期的にheart beatを送り生存確認を行う機能を持つことが望ましい。そこで、Alice自体にKeep Aliveの機能を実装した。 - -一定時間内にノードから応答がない場合、Keep Aliveにより、そのノードのRemote DSMが切断される。 - - -図 \ref{fig:keepAlive}は、keepAliveの処理をコミュニケーションダイアグラムで示したものである。 -keepAliveは、タスクとタスクを実行するTaskExecuterと実行順序を管理するSchedulerによって実装されている。 -タスクの種類には、{\tt PING}、{\tt CLOSE}、{\tt CREATE}があり、TaskExecuterは、タスクの種類に従って処理を行なう。 -{\tt PING}は、指定されたRemote DSMに対してheartbeatを送信する。 -{\tt CLOSE}は、指定されたRemote DSMを削除する。 -{\tt CREATE}は{\tt PING}のタスクを作成し、Schedulerに登録する。 +実用的なアプリケーションであるTreeVNCをAlice上で実装することで、Aliceに必要な機能を洗い出した。 +\subsection{flip機能} +Data Segment APIのput、updateを呼ぶとOutput Data Segmentが毎回新しく作成される。そして出力するデータのコピーが行われる。 +しかし、AliceVNCのようにInput Data Segmentとして取得したデータをそのまま子ノードにOutput Data Segmentとして出力する場合、コピーを行なうのは無駄である。 +　 +そこで、このコピーを無くしData Segmentの更新におけるオーバーヘッドを減らす方法としてflip機能の実装を行った。 +ソースコード\ref{src:exampleFlip}のようにInput Data SegmentであるReceiverをflipメソッドに引数として渡すことで、無駄なコピーを減らす。 +\begin{table}[html] +\lstinputlisting[label=src:flipAlice, caption=Aliceにおけるflip]{source/flip.java} +\end{table} -タスクを作成する際に実行時間の指定をする。Schedulerにタスクを登録すると、Schedulerはタスクの実行時間に従って、タスクを実行順に並び替える。 -\begin{figure}[htbp] -\begin{center} -\includegraphics{images/keepAlive.pdf} -\end{center} -\caption{keepAliveの仕組み} -\label{fig:keepAlive} -\end{figure} - -\subsubsection{処理の流れ} -\begin{enumerate} -\item CreateTask（Code Segment）により{\tt PING}タスクが投入される。\label{enum:putPingTask} -\item TaskExecuterはSchedulerから次に実行すべき{\tt PING}タスクを受け取る。 -\item 指定された時間が訪れるとheartbeatがRemote DSM（Node B）に送信される。\label{enum:send} -\item \ref{enum:send}と同時にheartbeatを送信したRemote DSMとの接続を切断する{\tt CLOSE}タスクが投入される。\label{enum:putCloseTask} -\item \ref{enum:putCloseTask}で投入された{\tt CLOSE}タスクが実行されるまでに、Remote DSM（Node B）からのレスポンスがあった場合、RemoveTask（Code Segment）により{\tt CLOSE}タスクが削除される。 -%\item \ref{enum:putPingTask}に戻る。 -\end{enumerate} - -\ref{enum:putPingTask}で作られる{\tt PING}タスクは、接続しているRemote DSMの数だけ投入される。 -"\_CLSIT"というkeyには、アクセス可能なRemote DSMのkeyの一覧が保存されている。 -CreateTaskは、この一欄により動的にタスクを作成している。 - -以上で説明した処理の流れは、接続状態に問題がない場合である。 -接続状態に問題があり、{\tt CLOSE}タスクの実行されるまでにレスポンスがない場合は、{\tt CLOSE}タスクによりRemote DSMが削除される。 - -heartbeatは、Node AからNode Bに一方向に送られる訳ではなく、Node BからNode Aにも送られている。 - -\section{切断時の処理} -MMORPGでは、試合の最中にサーバーからユーザーが切断された場合、自動的にユーザーが操作するキャラクターをゲーム開始時の位置に戻すという処理が実行される。 -同様にTreeVNCでは切断を検知した場合、LostParentというメッセージがトップノードに対して送信される。 - -以上の例のように、アプリケーションはノードの切断に対する処理を用意したい場合がある。 -しかし、Aliceを用いたアプリケーションの場合、アプリケーション側で検知するのは難しい。 -切断自体は、Remote DSMに対してwriteまたはreadを行った際に出るExceptionにより判断することができる。 -だが、I/O の処理はCode Segmentを実行するThreadで行われない。専用のI/O Threadによって行われるため、Code Segment内でExceptionを捕まえられず、例外処理を行なうことができない。 - -そこで、Aliceが切断を検知した際に、任意のCode Segmentを実行できる機能 (ClosedEventManager)を追加した。 -ユーザはClosedEventManagerにCode Segmentを登録することで、切断時の処理として実行するCode Segmentを指定できる。 -\begin{table}[htbp] -\lstinputlisting[label=src:registerEvent, caption=切断時に実行されるCode Segmentの登録方法]{source/RegisterEvent.java} +\begin{table}[html] +\lstinputlisting[label=src:exampleFlip,caption=flipの使用例]{source/Sort.java} \end{table} -また、切断したRemote DSMの情報を利用したい場合は、Code Segmentをextends する代わりにClosed Event Code Segmentをextendsし、用意されているMethodを使うことで取得可能である(ソースコード \ref{src:CatchClosedEvent})。 - -\begin{table}[htbp] -\lstinputlisting[label=src:CatchClosedEvent, caption=CloseEventCodeSegmentを継承したCodeSegment]{source/CatchClosedEvent.java} -\end{table} -ClosedEventCodeSegmentを継承したCode Segmentに、Input Data Segmentを追加記述する事ができる。 -その際は、もちろんInput Data Segmentが全て揃うまでCode Segmentは実行されない。 - -\subsection{Topologyの再構成} -ノードは永続的にアプリケーションに参加し続ける訳ではない。目的を果たすとアプリケーションから離脱する。 -Topology次第では、アプリケーションに支障をきたす。 -例えば、AliceVNCは木構造であるため、子ノードを持つノードがアプリケーションから離脱した場合、その子ノードに対してデータを送信することができなくなる。 - -この問題を解決するには、アプリケーションからノードが切断するたびにTopologyの再構成を行なう必要がある。そこで、Dynamic Topology Managerに、Topologyの再構成を行う機能を追加した。 - -図 \ref{fig:TopologyFIx}、 \ref{fig:TopologyFIx2}、\ref{fig:TopologyFIx3}はTopologyの再構成をコラボレーションダイアグラムで表したものである。 +\subsection{Data Segmentの表現の追加（圧縮機能）} +TreeVNCでは画面配信の際、データを圧縮してノード間通信を行っている。 +そのため、AliceVNCにも圧縮されたデータ形式を扱える機能が必要だと考えた。 +しかし、ただデータを圧縮する機構を追加すればいいわけではない。 -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=120mm]{images/TopologyFIx.pdf} -\end{center} -\caption{切断ノードの検知} -\label{fig:TopologyFIx} -\end{figure} - -\begin{enumerate} -\item Keep AliveがNode1の切断を検知すると、Node3からTopology Managerに対して切断したノードの情報がputされる。keep Aliveは各ノードで動いているため、実際にはNode0とNode4もTopology Managerに対してNode1の情報をputする。 -\item Topology Managerは最後にアプリケーションに参加したNode6とその親Node2に対して互いを切断するための準備を行わせる、CLOSEMESSAGEをputする。 -\item 切断する準備ができるとお互いに準備完了を知らせるCLOSEREADYをputする。 -\item \label {tb:last}CLOSEREADYを受け取ると切断を行い、Remote DSMが使用不可能になる。 -\end{enumerate} +AliceVNCでは、ノードは受け取った画面データを描画すると同時に、子ノードのRemote DS Managerに送信する。 +ノードはDSを受信するとそれを一度解凍して画面を表示し、再圧縮して子ノードに送信する。 +しかし、受け取ったデータを自分の子ノードに対して送信する際には、解凍する必要はない。 +圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる。 -\begin{figure}[htbp] - \begin{minipage}{0.5\hsize} - \begin{center} - \includegraphics[width=90mm]{images/TopologyFix2.pdf} - \end{center} - \caption{接続すべきノード情報の送信} - \label{fig:TopologyFIx2} - \end{minipage} - \begin{minipage}{0.5\hsize} - \begin{center} - \includegraphics[width=80mm]{images/TopologyFix3.pdf} - \end{center} - \caption{再構成の完了} - \label{fig:TopologyFIx3} - \end{minipage} -\end{figure} +そこで、１つのData Segmentに対し複数の表現を持たせることで、必要に応じた形式でDSを扱うことを可能にした。 +DSを扱うReceiveData.classに、次の3種類の表現を同時に持つことができる。 \begin{enumerate} -\setcounter{enumi}{4} -\item Node1、Node3、Node4に対してNode6の情報を送り、接続を行わせる。 -\item Node6に対して、Node1、Node3、Node4の情報を送り、接続を行わせる。 -\item お互いにRemote DSMの名前を贈り合い、Remote DSMが利用可能になる。 + \item 一般的なJavaのクラスオブジェクト + \item MessagePack for Javaでシリアライズ化されたバイナリオブジェクト + \item 2を圧縮したバイナリオブジェクト \end{enumerate} -\subsection{再接続の処理} -MMORPGでは、試合の最中に障害などによりサーバーから離脱したユーザーが、試合が終わるまでに再びサーバーに接続してきた場合に、再びその試合に参加できるような再接続の処理が用意されている。 +ソースコード\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} -分散にアプリケーションでは、MMORPGの例のように再接続してきたノードに対して通常の処理とは別の処理を行わせたい場合がある。そこで、Aliceに再接続してきたノードに、任意のCode Segmentを実行できる機能を追加した。ユーザーはconfigにCode Segmentを継承したClassを登録することで、再接続時に実行されるCode Segmentを指定することができる。 +また、圧縮状態を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerの追加した。 +put/updateでは、ソースコード\ref{src:zput}のように指定するDSM名の先頭に"compressed"をつけることでDSは自動で圧縮状態も持つようになる。さらに、take/peekもソースコード\ref{src:ztake}のようにsetKeyを実行する際にDSM名の先頭に"compressed"をつけることで圧縮形式でDSを受け取ることができる。 +\begin{table}[html] +\lstinputlisting[label=src:zput, caption=圧縮DSのput]{source/compress_put.java} +\end{table} -\begin{table}[htbp] -\lstinputlisting[label=src:StartAquarium, caption=再接続に実行するCode Segmentの登録方法]{source/StartAquariumFX.java} +\begin{table}[html] +\lstinputlisting[label=src:ztake,caption=圧縮DSのtake]{source/compress_take.java} \end{table} -\subsection{Multicast Data Segment} -TreeVNCには、Multicastを利用して起動しているTreeVNCのRoot Nodeの情報の一覧にして表示する接続先自動検索システムという機能がある。この機能によりTreeVNCの起動の際にIPアドレスを入力する手間を省くことができる。 - -現在のAliceは起動時にTopology ManagerのIPアドレスを入力する必要があり、TreeVNCの接続先自動検索機能が必要と考えられる。 -その機能を実現するためにはMulticastに対応する必要がある。そこで、同じマルチキャストアドレスを持つ端末を１つのData Segmentとして扱うMuticast Data Segmentを追加した。 -Multicast Data Segmentも他のData Segment同様、Data Segment APIを用いて扱う。 +これによりユーザは指定するDSMを変えるだけで、他の計算部分を変えずに圧縮表現を持つDSを扱うことができる。 -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=120mm]{images/multicast.pdf} -\end{center} -\caption{Multicast Data Segment} -\label{fig:multicast} -\end{figure} +ノードは圧縮されたDSを受け取った後、そのまま子ノードにflipすれば圧縮状態のまま送信されるので、送信の際の再圧縮がなくなる。 +また、画面表示の際は{\tt asClass()}(ソースコード\ref {src:asClass})を使うことで適切な形式でデータを取得できる。 +{\tt asClass()}はDSを目的の型にcastするメソッドであり、圧縮されていれば解凍してcastを行っている。 +これにより必要なDSを必要な時にだけ解凍できる。 -図 \ref{fig:multicast}はMulticast Data Segmentを図で表したものである。Node AのMulticast Data Segmentに対してputを行うとnode B、node C、node Dの3つのnodeに対してデータがputされる。同様にTakeを行うと3つのnodeからTakeに対する応答が来る。 +\begin{table}[html] +\lstinputlisting[label=src:asClass, caption=asClassの処理]{source/asClass.java} +\end{table} -Multicast Data SegmentはUDPを用いて実装されている。1つのUDPのパケットで運ぶことのできるデータが、65507bytes（65535bytesからIPヘッダの最低サイズ20bytesとUDPのヘッダのサイズ8bytesを引いた大きさ）である。 -現状、分割して送る処理をMulticast Data Segmentが持たない。従って、Multicast Data Segmentを利用する際には、データのサイズを65507bytes以下にしなければならない。 -\section{Multicast Data Segment Manager} -Multicast Data SegmentもRemote DSM同様Managerを経由して操作を行う。Multicast DSMを作成するとMulticast Data Segmentに対する送受信用のスレッドが作成される。 - -\begin{itemize} -\item {\ttfamily public static MulticastDataSegmentManager \\ -connectMulticast(String connectionKey ,String MCSTADDR, int port, String nis, SocketType type)} -\end{itemize} +\subsection{パケットの再設計} +2.4で述べたように、Remoteからputされたデータは必ずシリアライズ化されておりbyteArrayで表現される。 +しかし、putされたbyteArrayが全てシリアライズ化された状態であるとはいえない。Localからも一般的なJavaのクラスオブジェクトとしてbyteArrayが使用されている場合が存在する。例えば、AliceVNCで使われる画像データはbyteArrayで表現されているが、これはLocalからputされている。 +また、データの表現に圧縮形式を追加したことで、RemoteからでもputされたbyteArrayが圧縮されているのかそうでないのかが判断できなくなった。 -DataSegment classのstaticメソッドである、connectMulticastを呼ぶことでMulticast DSMが作成される。 -第1引数はMulticast DSMへのアクセスするためのkeyを指定できる。第2引数はマルチキャストアドレスを、第3引数はポート番号を、第4引数はネットワークインターフェイスを指定する。第5引数はSocketTypeを指定する。 -SocketTypeには、{\tt Sender}と{\tt Receiver}と{\tt Both}が存在する。{\tt Sender}を指定した場合は、第2引数で指定したマルチキャストアドレスに対して送信処理を行うスレッドを作成する。{\tt Receiver}を指定した場合は、第2引数で指定したマルチキャストアドレスに対して送信されたデータを受信するスレッドを作成する。{\tt Both}は、送受信両方のスレッドを作成する。 - -現在、Multicast Data Segmentは自動では作成されないため、ユーザー自身で作成する必要がある。 +ここからわかることは、データを表現するにはデータ単体をやりとりするだけでは不十分ということである。 +そこで、データとデータの状態を表すヘッダをまとめて1つのオブジェクトとして扱うように変更した。 +Aliceの通信におけるヘッダにあたるCommandMessage.class(ソースコード\ref {src:CommandMessage}にシリアライズ状態表すフラグと、圧縮状態を表すフラグを追加した。 +これによってputされたDSMはフラグに応じた適切な形式でReceiveData.class内にDSを格納できる。 +また、CommandMessage.classに圧縮前のデータサイズも追加したことで、適切な解凍が可能になった。 -ソースコード \ref {src:MulticastStartCodeSegment}と\ref {src:MulticastIncrement}は実際にMulticast Data Segmentを利用した例題である。送信側では送信専用のmulticast DSMを作成し、それに対して数字データを10回putしている。 -受信側では受信専用のmulticast DSMを作成し、送信されたDSを受け取り内容を表示している（ソースコード\ref {src:Receivemessage}）。 - -\begin{table}[htbp] -\lstinputlisting[label=src:MulticastStartCodeSegment, caption=multicast DSの例題の送信側]{source/MulticastStartCodeSegment.java} +\begin{table}[html] +\lstinputlisting[label=src:CommandMessage, caption=変更後のCommandMessage]{source/CommandMessage.java} \end{table} \begin{table}[htbp] -\lstinputlisting[label=src:MulticastIncrement, caption=multicast DSの例題の受信側]{source/MulticastIncrement.java} +\caption{CommandMessageの変数名の説明} +\label{tb:variable} +\begin{center} +\begin{tabular} {|l|l|} + \hline + 変数名&説明\\ + \hline + type&CommandType {\tt PEEK, PUT}などを表す\\ + \hline + seq&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} -\begin{table}[htbp] -\lstinputlisting[label=src:Receivemessage, caption=multicast DSMに対してsetKeyを行う]{source/ReceiveTask.java} -\end{table} -\subsection{圧縮機能} \ No newline at end of file diff -r 683044bd29ed -r 4a7fa91ef60a paper/sigos.aux --- a/paper/sigos.aux Tue May 05 17:26:13 2015 +0900 +++ b/paper/sigos.aux Wed May 06 05:23:37 2015 +0900 @@ -4,7 +4,22 @@ \@writefile{lol}{\contentsline {lstlisting}{\numberline {1}StartCodeSegmentの例}{3}} \newlabel{src:CodeSegment}{{2}{3}} \@writefile{lol}{\contentsline {lstlisting}{\numberline {2}CodeSegmentの例}{3}} -\citation{*} \newlabel{fig:vnc}{{2}{4}} \newlabel{fig:treestructure}{{3}{4}} -\gdef\ipsj@lastpage{4} +\newlabel{src:flipAlice}{{3}{4}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {3}Aliceにおけるflip}{4}} +\newlabel{src:exampleFlip}{{4}{4}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {4}flipの使用例}{4}} +\newlabel{src:ReceiveData}{{5}{5}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {5}データを表現するクラス}{5}} +\newlabel{src:zput}{{6}{5}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {6}圧縮DSのput}{5}} +\newlabel{src:ztake}{{7}{5}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {7}圧縮DSのtake}{5}} +\newlabel{src:asClass}{{8}{5}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {8}asClassの処理}{5}} +\citation{*} +\newlabel{src:CommandMessage}{{9}{6}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {9}変更後のCommandMessage}{6}} +\newlabel{tb:variable}{{1}{6}} +\gdef\ipsj@lastpage{6} diff -r 683044bd29ed -r 4a7fa91ef60a paper/sigos.dvi Binary file paper/sigos.dvi has changed diff -r 683044bd29ed -r 4a7fa91ef60a paper/sigos.log --- a/paper/sigos.log Tue May 05 17:26:13 2015 +0900 +++ b/paper/sigos.log Wed May 06 05:23:37 2015 +0900 @@ -1,4 +1,4 @@ -This is e-pTeX, Version 3.1415926-p3.4-110825-2.6 (utf8.euc) (TeX Live 2013) (format=platex 2014.4.14) 5 MAY 2015 17:15 +This is e-pTeX, Version 3.1415926-p3.4-110825-2.6 (utf8.euc) (TeX Live 2013) (format=platex 2014.4.14) 6 MAY 2015 05:22 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -153,8 +153,7 @@ (/usr/local/texlive/2013/texmf-dist/tex/latex/listings/lstmisc.sty File: lstmisc.sty 2007/02/22 1.4 (Carsten Heinz) ) -(./dummy.tex) -No file sigos.aux. +(./dummy.tex) (./sigos.aux) \openout1 = `sigos.aux'. LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 32. @@ -189,46 +188,34 @@ LaTeX Font Info: External font `cmex10' loaded for size (Font) <7> on input line 81. LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <9> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 95. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 100. LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <9> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 95. -[1 +(Font) Font shape `JY1/gt/m/n' tried instead on input line 100. + [1 ] - -LaTeX Warning: Reference `fig:RemoteDSM' on page 2 undefined on input line 110. - +File: images/remote_datasegment.pdf Graphic file (type pdf) + +LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <7> not available +(Font) Font shape `JT1/gt/m/n' tried instead on input line 122. +LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <7> not available +(Font) Font shape `JY1/gt/m/n' tried instead on input line 122. -File: images/remote_datasegment.pdf Graphic file (type pdf) - -LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <7> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 116. -LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <7> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 116. - -Overfull \hbox (10.66351pt too wide) in paragraph at lines 129--130 +Overfull \hbox (10.66351pt too wide) in paragraph at lines 135--136 []\OT1/cmtt/m/n/9 void update(String managerKey, String key, [] -Overfull \hbox (1.21362pt too wide) in paragraph at lines 134--135 +Overfull \hbox (1.21362pt too wide) in paragraph at lines 140--141 []\OT1/cmtt/m/n/9 void take(String managerKey, String key) [] -Overfull \hbox (1.21362pt too wide) in paragraph at lines 139--140 +Overfull \hbox (1.21362pt too wide) in paragraph at lines 145--146 []\OT1/cmtt/m/n/9 void peek(String managerKey, String key) [] - -LaTeX Warning: Reference `src:StartCodeSegment' on page 2 undefined on input li -ne 155. - - -LaTeX Warning: Reference `src:CodeSegment' on page 2 undefined on input line 15 -5. - (./source/StartCodeSegment.java LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <8> not available (Font) Font shape `JT1/gt/m/n' tried instead on input line 1. @@ -242,61 +229,42 @@ LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <8> not available (Font) Font shape `OMS/cmsy/m/n' tried instead on input line 1. ) -(./source/TestCodeSegment.java) - -LaTeX Warning: Reference `src:StartCodeSegment' on page 2 undefined on input li -ne 163. - - -LaTeX Warning: Reference `src:StartCodeSegment' on page 2 undefined on input li -ne 167. - - -LaTeX Warning: Reference `src:CodeSegment' on page 2 undefined on input line 16 -7. - - -LaTeX Warning: Reference `src:CodeSegment' on page 2 undefined on input line 17 -2. - -[2] -Overfull \hbox (10.66351pt too wide) in paragraph at lines 193--194 +(./source/TestCodeSegment.java) [2] +Overfull \hbox (10.66351pt too wide) in paragraph at lines 207--208 []\OT1/cmtt/m/n/9 void setKey(String managerKey, String key) [] [3] -Overfull \hbox (6.058pt too wide) in paragraph at lines 232--234 -[]\OT1/cmr/m/n/9 AliceVNC \JY1/mc/m/n/9 は 、 当研究室で開発を行 っ ている \OT1 -/cmr/m/n/9 TreeVNC +File: images/vnc.pdf Graphic file (type pdf) + +File: images/treestructure.pdf Graphic file (type pdf) + (./source/flip.java) +(./source/Sort.java) [4] (./source/ReceiveData.java) +(./source/compress_put.java) (./source/compress_take.java) +(./source/asClass.java +LaTeX Font Info: Try loading font information for OML+cmr on input line 1. + +(/usr/local/texlive/2013/texmf-dist/tex/latex/base/omlcmr.fd +File: omlcmr.fd 1999/05/25 v2.5h Standard LaTeX font definitions +) +LaTeX Font Info: Font shape `OML/cmr/m/n' in size <8> not available +(Font) Font shape `OML/cmm/m/it' tried instead on input line 1. +) +(./source/CommandMessage.java) +Overfull \hbox (17.32811pt too wide) in paragraph at lines 351--374 + [] [] - -LaTeX Warning: Reference `fig:vnc' on page 4 undefined on input line 235. - - -LaTeX Warning: Reference `fig:treestructure' on page 4 undefined on input line -235. - -File: images/vnc.pdf Graphic file (type pdf) - -File: images/treestructure.pdf Graphic file (type pdf) - [4 - -] (./sigos.aux) +[5] [6 -LaTeX Warning: There were undefined references. - - -LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right. - - ) +] (./sigos.aux) ) Here is how much of TeX's memory you used: - 2913 strings out of 494008 - 39702 string characters out of 6154472 - 198979 words of memory out of 5000000 - 6358 multiletter control sequences out of 15000+600000 - 17628 words of font info for 68 fonts, out of 8000000 for 9000 + 3044 strings out of 494008 + 41457 string characters out of 6154472 + 215979 words of memory out of 5000000 + 6462 multiletter control sequences out of 15000+600000 + 17796 words of font info for 69 fonts, out of 8000000 for 9000 745 hyphenation exceptions out of 8191 - 33i,11n,58p,431b,1465s stack positions out of 5000i,500n,10000p,200000b,80000s + 33i,12n,58p,431b,1465s stack positions out of 5000i,500n,10000p,200000b,80000s -Output written on sigos.dvi (4 pages, 29660 bytes). +Output written on sigos.dvi (6 pages, 50596 bytes). diff -r 683044bd29ed -r 4a7fa91ef60a paper/sigos.pdf Binary file paper/sigos.pdf has changed diff -r 683044bd29ed -r 4a7fa91ef60a paper/sigos.tex --- a/paper/sigos.tex Tue May 05 17:26:13 2015 +0900 +++ b/paper/sigos.tex Wed May 06 05:23:37 2015 +0900 @@ -65,16 +65,16 @@ % 和文概要 \begin{abstract} 当研究室ではデータをData Segment、タスクをCode Segmentという単位で分割して記述する手法を提唱しており、そのプロトタイプとして並列分散フレームワークAliceを開発している。 -　本研究ではAliceに実用的なアプリケーションを作成するために必要な動的なトポロジーを管理する機能とAliceの制御を行えるメタ計算を追加した。また、通信時におけるData Segmentの多態性を実現するため、Data SegmentをObject型、MessagePackを使ったByteArray型、圧縮されたByteArray型の３つの形式で表現できるメタ計算の設計と実装、性能評価を行った。 +　Aliceが分散プログラムを記述する能力を有することは確認された。しかし、Aliceで実用的なアプリケーションを作成するには、通信時にData Segmentの形式を選択できる機能が必要である。本研究では、Data Segmentの多態性を実現するため、Data SegmentをObject型、MessagePackを使ったByteArray型、圧縮されたByteArray型の３つの形式で表現できるメタ計算の設計と実装を行った。 \end{abstract} % 英文概要　仮 \begin{eabstract} - Alice is a prototype framework for distributed programming, which uses Data Segment and Code Segment as programming units. We checked Alice has an ability to write dis- tributed program using aquarium example, distributed database Jungle and share screen system AliceVNC . -In this paper, we add functions which control dynamic topology and Alice computation. And we show Alice has an ability to write useful application. -Furthermore we improve Alice performance. So Alice works 12% faster and has same performance as Federated Linda. + Alice is a prototype framework for distributed programming, which uses Data Segment and Code Segment as programming units. We checked Alice has an ability to write distributed program by previous research. +　In this paper, we add Alice computation of compress. HOGE +for DataSegment polymerism. \end{eabstract} % 表題などの出力 @@ -83,12 +83,17 @@ % 本文はここから始まる \section{研究背景と目的} -当研究室ではデータをData Segment、タスクをCode Segmentという単位で分割して記述する並列分散フレームワークAliceの開発を行っている。Aliceでは分散環境の構築に必要な処理をMeta Computationとして提供することで、スケーラブルな分散プログラムを信頼性高く記述できる環境を実現している。 +当研究室ではデータをData Segment、タスクをCodeSegmentという単位で分割して記述する並列分散フレームワークAliceの開発を行っている。 +Aliceでは分散環境の構築に必要な処理をMeta Computationとして提供することで、スケーラブルな分散プログラムを信頼性高く記述できる環境を実現している。 + +先行研究にてAlice が分散プログラムを記述する能力を有することは確認された。 +だが、実用的な分散プログラムを作成するためには、受け取ったデータをそのまま転送したい場合や圧縮されたデータ形式で通信を行いたい場合がある。 -Alice が分散プログラムを記述する能力を有することは確認された。だが、実用的な分散プログラムを作成するためには、ノードの切断・再接続時に対応した処理を行いたい場合や圧縮されたデータ形式で通信を行いたい場合がある。 - -本研究では、 Alice の Computation の 制御を行う Meta Computation を実装した。プログラムに Alice の制御を行うメタプログラムを記述することにより切断や再接続の状況に応じた処理を元のコードを変更することなく指定することができる。また、圧縮機能を持ったDataSegmentManagerを追加することによりData Segmentの多態性を実現した。 -そして、 TreeVNC と TreeVNC を Alice を用いて実装した AliceVNC の比較をコードの観点から評価を行った。 +本研究では、 Aliceを用いて画面共有システムAliceVNCを実装するにあたり必要となった +flip機能と圧縮機能を Meta Computation として実装した。 +プログラムに Alice の制御を行うメタプログラムを記述することにより、 +扱うデータの形式を元のコードを大きく変更することなく指定することができる。 +そして、データの多態性を実現し、扱いたいデータの状態に合わせてDataSegmentManagerを切り替えることで、ノード間通信における自由度の向上を図った。 \section{分散フレームワーク Alice の概要} @@ -105,13 +110,14 @@ Aliceはデータを細かく分割して記述する。その細かく分割されたデータをDSと呼ぶ。 実際には特定のオブジェクトにマッピングされ、マッピングされたクラスを通してアクセスされる。 + \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=80mm]{images/remote_datasegment.pdf} +\includegraphics[width=70mm]{images/remote_datasegment.pdf} \end{center} \caption{Remote DSMは他のノードのLocal DSMのproxy } \label{fig:RemoteDSM} @@ -141,6 +147,14 @@ peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。 +DSの表現にはMessagePack for Javaを利用している。 +\begin{itemize} +\item {\ttfamily DSは一般的なJavaのクラスオブジェクト} +\item {\ttfamily MessagePackを用いて変換したbyte[]で表現されたバイナリオブジェクト} +\end{itemize} +の２種類があり、LocalDSMにputされた場合は一般的なJavaのクラスオブジェクトとしてenQueueされる。 +RemoteDSMにputされた場合は通信時にbyteArrayに変換されたバイナリオブジェクトがenQueueされる。 + \section{Code Segment} Alice上で実行されるタスクの単位がCSである。ユーザーはCSを組み合わせることでプログラミングを行う。CSをユーザーが記述する際に、内部で使用するDSの作成を記述する。 @@ -229,14 +243,15 @@ \section{AliceVNC} -AliceVNCは、当研究室で開発を行っているTreeVNCをAliceを用いて実装された、授業向け画面共有システムである。 -Aliceが実用的なアプリケーションを記述する能力をもつことを確認するために作成した。 +当研究室では授業向け画面共有システムTreeVNCの開発を行っている。 +授業でVNCを使う場合、１つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう(図\ref{fig:vnc})。 +この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである(図\ref{fig:treestructure})。 -授業でVNCを使う場合、１つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう(図\ref{fig:vnc})。この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである(図\ref{fig:treestructure})。TreeVNCは、TightVNCのソースコードを利用して開発されている。 +　Aliceが実用的なアプリケーションを記述する能力をもつことを確認するために、TreeVNCをAliceを用いて実装したAliceVNCの作成を行った。 \begin{figure}[htbp] \begin{center} - \includegraphics[width=80mm]{images/vnc.pdf} + \includegraphics[width=60mm]{images/vnc.pdf} \end{center} \caption{VNCの構造 } \label{fig:vnc} @@ -244,7 +259,7 @@ \begin{figure}[htbp] \begin{center} - \includegraphics[width=80mm]{images/treestructure.pdf} + \includegraphics[height=50mm]{images/treestructure.pdf} \end{center} \caption{TreeVNC, AliceVNCの構造 } \label{fig:treestructure} @@ -252,9 +267,123 @@ -% \input{chapter3} -% \input{chapter5} -% \input{conclusion} + +\section{Aliceの新機能} +実用的なアプリケーションであるTreeVNCをAlice上で実装することで、Aliceに必要な機能を洗い出した。 +\subsection{flip機能} +Data Segment APIのput、updateを呼ぶとOutput Data Segmentが毎回新しく作成される。そして出力するデータのコピーが行われる。 +しかし、AliceVNCのようにInput Data Segmentとして取得したデータをそのまま子ノードにOutput Data Segmentとして出力する場合、コピーを行なうのは無駄である。 +　 +そこで、このコピーを無くしData Segmentの更新におけるオーバーヘッドを減らす方法としてflip機能の実装を行った。 +ソースコード\ref{src:exampleFlip}のようにInput Data SegmentであるReceiverをflipメソッドに引数として渡すことで、無駄なコピーを減らす。 +\begin{table}[html] +\lstinputlisting[label=src:flipAlice, caption=Aliceにおけるflip]{source/flip.java} +\end{table} + +\begin{table}[html] +\lstinputlisting[label=src:exampleFlip,caption=flipの使用例]{source/Sort.java} +\end{table} + +\subsection{Data Segmentの表現の追加（圧縮機能）} +TreeVNCでは画面配信の際、データを圧縮してノード間通信を行っている。 +そのため、AliceVNCにも圧縮されたデータ形式を扱える機能が必要だと考えた。 +しかし、ただデータを圧縮する機構を追加すればいいわけではない。 + +AliceVNCでは、ノードは受け取った画面データを描画すると同時に、子ノードのRemote DS Managerに送信する。 +ノードは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} + +また、圧縮状態を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerの追加した。 +put/updateでは、ソースコード\ref{src:zput}のように指定するDSM名の先頭に"compressed"をつけることでDSは自動で圧縮状態も持つようになる。さらに、take/peekもソースコード\ref{src:ztake}のようにsetKeyを実行する際にDSM名の先頭に"compressed"をつけることで圧縮形式でDSを受け取ることができる。 +\begin{table}[html] +\lstinputlisting[label=src:zput, caption=圧縮DSのput]{source/compress_put.java} +\end{table} + +\begin{table}[html] +\lstinputlisting[label=src:ztake,caption=圧縮DSのtake]{source/compress_take.java} +\end{table} + +これによりユーザは指定するDSMを変えるだけで、他の計算部分を変えずに圧縮表現を持つDSを扱うことができる。 + +ノードは圧縮されたDSを受け取った後、そのまま子ノードにflipすれば圧縮状態のまま送信されるので、送信の際の再圧縮がなくなる。 +また、画面表示の際は{\tt asClass()}(ソースコード\ref {src:asClass} )を使うことで適切な形式でデータを取得できる。 +{\tt asClass()}はDSを目的の型にcastするメソッドであり、圧縮されていれば解凍してcastを行っている。 +これにより必要なDSを必要な時にだけ解凍できる。 + +\begin{table}[html] +\lstinputlisting[label=src:asClass, caption=asClassの処理]{source/asClass.java} +\end{table} + +\subsection{パケットの再設計} +2.4で述べたように、Remoteからputされたデータは必ずシリアライズ化されておりbyteArrayで表現される。 +しかし、putされたbyteArrayが全てシリアライズ化された状態であるとはいえない。Localからも一般的なJavaのクラスオブジェクトとしてbyteArrayが使用されている場合が存在する。例えば、AliceVNCで使われる画像データはbyteArrayで表現されているが、これはLocalからputされている。 +また、データの表現に圧縮形式を追加したことで、RemoteからでもputされたbyteArrayが圧縮されているのかそうでないのかが判断できなくなった。 + +ここからわかることは、データを表現するにはデータ単体をやりとりするだけでは不十分ということである。 +そこで、データとデータの状態を表すヘッダをまとめて1つのオブジェクトとして扱うように変更した。 +Aliceの通信におけるヘッダにあたるCommandMessage.class(ソースコード\ref {src:CommandMessage}にシリアライズ状態表すフラグと、圧縮状態を表すフラグを追加した。 +これによって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 + serialized&データ本体のシリアライズ状態を示す\\ + \hline + + compressed&データ本体のシリアライズ状態を示す\\ + \hline + + dataSize&圧縮前のデータサイズを表す\\ + \hline + +\end{tabular} +\end{center} +\end{table} + + + \section{まとめ} +本研究では、まずはじめに並列分散フレームワークAliceの計算モデルと実装について説明を行い、Aliceにおけるプログラミング手法を述べた。 + +次に、Aliceが実用的なアプリケーションを記述するために必要なMeta Computationとして、データの多態性を実現し、指定するDSMの切り替えで扱うデータ表現を変えるようにした。 +これにより、必要に応じた形式を扱うことができ、ユーザが記述するComputation部分を大きく変えずに自由度の高い通信を行うことが可能になった。 +同様の手法を用いれば、圧縮形式以外にも暗号形式・JSON形式などの複数のデータ表現をユーザに扱いやすい形で拡張することができる。 + +今後の課題としては、より実用的なアプリケーションを記述するために、データの永続性の確保等が挙げられる。 +現在のAliceはOn memoryであるためプロセスの終了とともにDS全て失われてしまう。この問題を解決するには、DSを他のKey Value Store等のシステムに保存し、永続性を確保する必要がある。 \nocite{*} %\nocite{opencl} diff -r 683044bd29ed -r 4a7fa91ef60a paper/source/CommandMessage.java --- a/paper/source/CommandMessage.java Tue May 05 17:26:13 2015 +0900 +++ b/paper/source/CommandMessage.java Wed May 06 05:23:37 2015 +0900 @@ -1,9 +1,9 @@ -@Message public class CommandMessage { public int type; public int seq; public String key; public boolean quickFlag = false; public boolean serialized = false; - + public boolean compressed = false; + public int dataSize = 0; } diff -r 683044bd29ed -r 4a7fa91ef60a paper/source/ReceiveData.java --- a/paper/source/ReceiveData.java Tue May 05 17:26:13 2015 +0900 +++ b/paper/source/ReceiveData.java Wed May 06 05:23:37 2015 +0900 @@ -1,6 +1,5 @@ public class ReceiveData { private Object val; - - private boolean serialized = false; - private boolean byteArray = false; -} \ No newline at end of file + private byte[] messagePack; + private byte[] zMessagePack; +} diff -r 683044bd29ed -r 4a7fa91ef60a paper/source/asClass.java --- a/paper/source/asClass.java Tue May 05 17:26:13 2015 +0900 +++ b/paper/source/asClass.java Wed May 06 05:23:37 2015 +0900 @@ -1,13 +1,11 @@ public T asClass(Class clazz) { - if (!byteArray) { + if (val != null) { return (T) val; } - byte[] b = (byte[]) val; - if (serialized) { - return SingletonMessage.getInstance().read(b, clazz); - } else { - return (T) b; + if (zMessagePack != null && messagePack == null) { + messagePack = unzip(zMessagePack, dataSize); } + return packer.read(messagePack, clazz); }