Papers/2015/nozomi-sigos: paper/sigos.tex comparison

comparison paper/sigos.tex @ 5:4a7fa91ef60a

not fix English Abstract

author	Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
date	Wed, 06 May 2015 05:23:37 +0900
parents	683044bd29ed
children	1702e6278518

comparison

equal deleted inserted replaced

-:683044bd29ed
+:4a7fa91ef60a
 email: kokubo@cr.ie.u-ryukyu.ac.jp}
 % 和文概要
 \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 .
+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 functions which control dynamic topology and Alice computation. And we show Alice has an ability to write useful application.
+　In this paper, we add Alice computation of compress. HOGE
-Furthermore we improve Alice performance. So Alice works 12% faster and has same performance as Federated Linda.
+for DataSegment polymerism.
 \end{eabstract}
 % 表題などの出力
 \maketitle
 % 本文はここから始まる
 \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 の概要}
 \subsection{Data SegmentとCode Segment}
 AliceはデータをData Segment、（以下DS）タスクをとCode Segment（以下CS）という単位に分割してプログラミングを行う。
 複数のスレッドから１つのデータに変更を行うためには、データの不整合を防ぐためのlockが必要になる。複数の関係のない要素を１つのデータオブジェクトで表現した場合、全ての操作でlockが必要になる。このlockがスケラビリティーを低下させる。つまりデータのサイズも並列計算には重要である。
 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}
 \end{figure}
 \begin{itemize}
 \item {\ttfamily void peek(String managerKey, String key)}
 \end{itemize}
 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の作成を記述する。
 Input DS と Output DSはCSに用意されているAPIを用いて作成する。
 \section{AliceVNC}
-AliceVNCは、当研究室で開発を行っているTreeVNCをAliceを用いて実装された、授業向け画面共有システムである。
+当研究室では授業向け画面共有システムTreeVNCの開発を行っている。
-Aliceが実用的なアプリケーションを記述する能力をもつことを確認するために作成した。
+授業で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}
 \end{figure}
 \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}
 \end{figure}
-% \input{chapter3}
-% \input{chapter5}
+\section{Aliceの新機能}
-% \input{conclusion}
+実用的なアプリケーションである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}
 %\nocite{opencl:ref}
 %\nocite{opencl:applied}

Mercurial > hg > Papers > 2015 > nozomi-sigos

comparison paper/sigos.tex @ 5:4a7fa91ef60a