# HG changeset patch # User sugi # Date 1421999028 -32400 # Node ID 675939a7f983f4cc95c2ed36a71d2598cbe67fca # Parent 8e0b26d962cc8d2012fd6d522a29d023d51db536 change experiment picture diff -r 8e0b26d962cc -r 675939a7f983 paper/chapter1.tex --- a/paper/chapter1.tex Sun Jan 18 00:23:22 2015 +0900 +++ b/paper/chapter1.tex Fri Jan 23 16:43:48 2015 +0900 @@ -1,145 +1,21 @@ \chapter{分散フレームワーク Alice の概要} \label{chapter:chapter1} -Aliceは、本研究室で開発を行っている分散タスク管理フレームワークである。Cell用のOpen CLに似たTask管理フレームワークCeriumとLindaを相互に接続した分散フレームワークであるFederated Lindaの開発を通して得られた知見が生かされている。 - -Ceriumでは、Taskを小さく分割して並列実行し、データ転送はパイプライン実行により隠される。Task間に依存関係があるが、実際にはデータの依存関係がそのままTaskの依存関係になることが多い。繰り返し使われるデータ構造の管理が重要であり、実行時にわかるデータ構造間の依存関係がTaskを複雑にしている。 - -Federated Lindaでは、Lindaサーバ内部にMeta Engineと呼ばれるLindaのタプル(データ構造)をやり取りする部分を作成した。Meta Engineでは、タプルのやり取りによって起動するcall backを使うが、call backによる記述が分散してしまい、可読性を落としてしまう。また、複数のタプルの待ち合わせが重要だが、その待ち合わせはsingle threadedなMeta Engine内部の状態に依存する。 - -これらが示しているのは、並列分散実行はコードの並列実行だけでなく、データの単位が重要だということである。そこで、AliceはData SegmentとCode Segmentという単位でデータと処理を細かく分割し、それぞれの依存関係を記述して分散プログラムを作成する。 - -Data SegmentはCode Segmentと分離されたデータ構造であり、オブジェクトではない。オブジェクト指向プログラミングが状態を複雑に持ち、並列実行や分散実行に向かないことは徐々に理解されてきている。一方で、状態自体は有限状態遷移機械(Finite State Machine/FSM)で記述するのが自然である。Code Segmentは状態遷移記述そのものであり、その状態遷移はData Segmentの到着によってトリガーされる。 - -カプセル化されたデータをプロセスがやり取りするのは、DFD(Data Flow Diagram)の古典的な手法であり、それ自体は新しくはない。むしろ、メインフレーム上でのソフトウェア開発に良く使われてきた手法である。Alice では、それを再実装する。 - -AliceはCode SegmentとData SegmentをJavaとMessage Packで実装したフレームワークである。Topology Managerを持ち、Blade上での -分散プログラムの実験を容易に行うことができる。また、SEDA Architectureを採用しており、マルチコア上でのスループットの向上を期待している。 - -\section{Data Segment} -Data Segmentはデータを細かく分割したものであり、数値や文字列などのデータを構造的に保持する。AliceはData Segmentをデータベースとして扱っている。Data Segmentには必ず対になるKeyが存在する。つまりKey Value Storeとして考える事ができる。 - -Aliceのデータベースは通常のKVSとは異なっている点がある。通常のKVSはプログラミング言語の連想配列やMapと同様に 「Key（キー）」と「Value（値）」がペアとなっている。そのため1つのKeyに対して値は1つである。しかし、Aliceの場合は「Key」と「Queue」がペアとなっているため、Keyに対して複数回putできる。従って取得できるValueも複数存在できる。Key毎の追加と取得はLindaに準じた設計になっている。 -Data SegmentはData Segment Manager（以下DSM）によって管理されている。ノード毎にLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のKVSとなっている。従ってRemote DSMを指定するKeyはノード内部でuniqueなものである。Remote DSMは他のノードのLocal DSMのproxyと考えられる。つまりRemote DSMは複数存在し、それぞれに対応するノードは異なる。 - -\begin{figure}[htbp] -\begin{center} -\includegraphics{images/remote_datasegment.pdf} -\end{center} -\caption{Remote DSMは他のノードのLocal DSMのproxy } -\label{fig:RemoteDSM} -\end{figure} +\section{Aliceの計算モデル} +\subsection{Data SegmentとCode Segment} +\subsection{computationとmeta computation} -KVSへのアクセスはqueueによって、ノード内部で逐次化される。それ以外は、すべてJavaのThread Poolにより並列実行される。 + \subsection{Data Segment API} -以下が用意されているData Segment APIである。これらを用いてデータの送受信を行う。 -\begin{itemize} -\item \verb+void put(String key, Value val)+ -\item \verb+void update(String key, Value val)+ -\item \verb+void peek(Receiver receiver, String key)+ -\item \verb+void take(Receiver receiver, String key)+ -\end{itemize} - \subsection{Data Segment の表現} -Data Segmentの表現にはMessage Packを利用している。Message Packに関してJavaにおけるデータ表現は以下の3種類があり、制限を伴うが互いに変換可能である。 -\begin{itemize} -\item {\ttfamily 一般的なJavaのクラスオブジェクト} -\item {\ttfamily MessagePack for JavaのValueオブジェクト} -\item {\ttfamily byte[]で表現されたbinary} -\end{itemize} -Data Segment APIの内部においてデータは、一般的なJavaのクラスオブジェクトまたはbyteArrayで表現されたbinaryで表現されている。 -Localからデータがputされた場合は一般的なJavaのクラスオブジェクトの状態でenqueueされる。RemoteからデータがputされるとbyteArrayで表現されたbinaryの状態でenqueueされる。 - -ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを表現することができる。 -この場合、クラス宣言時に@Messageというアノテーションをつける必要がある。もちろん、MessagePackで扱うことのできるデータのみをフィールドに入れなければならない。 - -Remoteに対してputできるデータは、@MessageをもつクラスオブジェクトかMessage Packで扱える型に限られる。 - -\section{Code Segment} -Code SegmentとはAlice上で実行されるタスクの単位である。ユーザーはCode Segmentを組み合わせることでプログラミングを行う。Code Segmentをユーザーが記述する際に、内部で使用するData Segmentの作成を記述する。入力時のData SegmentをInput Data Segment、出力時をOutput Data Segmentと呼ぶ。(図 \ref{fig:dsandcs}) - -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=100mm]{images/dsandcs.pdf} -\end{center} -\caption{Code SegmentはInput Data Segment とOutput Data Segmentが存在する} -\label{fig:dsandcs} -\end{figure} - -Input Data Segment と Output Data SegmentはCode Segmentに用意されているAPIを用いて作成する。 -Input Data Segmentは、LocalかRemoteか、またkeyを指定する必要がある。Code Segmentは、記述したInput Data Segmentが全て揃うとThread poolに送られ、実行される。 - -Out Data SegmentもLocalかRemoteか、またkeyを指定する必要がある。 - -Input Data SegmentとOutput Data SegmentによってCode Segmentの間の依存関係が自動的に記述される。(図 \ref{fig:dsandcs2}) - -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=110mm]{images/dsandcs2.pdf} -\end{center} -\caption{Input Data Segment とOut put Data SegmentがCode Segment間の依存関係を自動的に記述する} -\label{fig:dsandcs2} -\end{figure} -現在、Inputの場合はsetKeyを呼ぶ際、Outputはput(またはupdate)の際にノードとkeyの指定を行っている。 -しかし、どの時点でノードとkeyの指定を行えばよいか、どのようなAPIを用意するべきかは、議論の余地がある。 - -\subsection{Code Segmentの実行方法} -Alice には、Start Code Segment (ソースコード \ref{src:StartCodeSegment})というC の main に相当するような最初に実行される Code Segment がある。 -\begin{table}[html] -\lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java} -\end{table} - -Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。 -このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 - -\subsection{Code Segmentの記述方法} -Code Segmentをユーザーが記述する際にはCode Segmentを継承して記述する(ソースコード \ref{src:CodeSegment})。 -Code SegmentはInput/Output Data Segment Managerを利用することができる。 - -Input DSM はCode Segmentの{\tt ids}というフィールドを用いてアクセスする。 - -\begin{table}[html] -\lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java} -\end{table} - -\begin{itemize} -\item {\ttfamily Receiver create(CommandType type)} -\end{itemize} -createでコマンドが実行された際に取得されるData Segmentが格納される受け皿を作る。引数にはCommandTypeが取られ、指定できるCommandTypeは{\tt PEEK}または{\tt TAKE}である。 -\begin{itemize} -\item \verb+void setKey(String managerKey, String key)+ -\end{itemize} -setKeyメソッドにより、どこのData Segmentのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定することができる。 -コマンドの結果がレスポンスとして届き次第Code Segmentは実行される。 - -Output DSMはCode Segmentの{\tt ods}というフィールドを用いてアクセスする。 -Output DSMは{\tt put}または{\tt update}を実行することができる。 -\begin{itemize} -\item \verb+void put(String managerKey, String key, Object val)+ -\item \verb+void update(String managerKey, String key, Object val)+ -\end{itemize} - - -\section{Meta Data Segment} -Meta Data SegmentはData Segmentの一種である。Data Segmentは、ユーザーがput（またはupdate）したデータを管理するData Baseであるのに対して、Meta Data Segmentは、分散フレームワークAliceがputしたデータを管理するData Baseである。管理されているデータは、主にTopology Nodeの状態を表すメタデータである。ユーザーがメタデータを扱うこともできる。 - -例えば、"start"というkeyにはTopology NodeがStart Code Segmentを実行することができる状態を表す。他にも"\_CLIST"というkeyでは、利用可能なRemote Data Segmentの名前のリストが保存されている。ユーザーはリストをpeekし、putする際にリストにある名前を指定することで、動的にデータの伝搬などを行うことができる。 - -また、Input Data Segmentに付随しているものもある。Input Data SegmentはCode Segment内部でReceiverという入れ物に格納される。ユーザーは、Receiverに対して操作することでData Segmentを入手できる。 -このReceiverには、fromというフィールドがあり、このデータを誰がputしたという情報が入っている。この情報をデータの伝搬する際に利用することで、データをputしたノードに送り返すことを防ぐことができる。 - -現在のAliceでは、メタデータはデータと同じ領域にputされているため、データと同じAPIを用いて取得できる。 - -\section{Meta Code Segment} -Meta Code SegmentはAliceを構成するCode Segmentである。 - - - -Alice自身が全てCode Segmentで記述されているため、AliceをMeta Code Segmentのかたまりと考える事ができる。 - - -\section{Topology Manager} +\section{Aliceの実装} +\subsection{Code Segment} +\subsubsection{Code Segmentの実行方法} +\subsubsection{Code Segmentの記述方法} +\subsection{Meta Data Segment} +\subsection{Meta Code Segment} +\subsection{Topology Manager} Aliceは複数のノードで構成され、相互に接続される。通信するノードはURLにより直接指定するのではなくTopology Managerで管理する。 Topology Managerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきTopology NodeのIPアドレス、ポート番号、接続名を送りトポロジーファイルに記述されたとおりにトポロジーを作成する。(図\ref{fig:topologymanager}) @@ -155,7 +31,7 @@ トポロジーファイルはグラフ構造を表現するデータ記述する言語の一種であるDOT Languageと呼ばれる言語で記述する。また、dotコマンドを用いてトポロジーファイルを可視化することができる。 -\subsection{Topology Managerの参加表明処理} +\subsubsection{Topology Managerの参加表明処理} Topology Managerへの参加表明は、Topology Node起動時にコマンドライン引数からTopology ManagerのIPアドレスとポート番号を指定すればよい。 指定されたTopology Managerに接続を行うと、Topology Manager側のキー"hosts"に、自分自身のIPアドレスとポート番号をputする。 @@ -170,6 +46,7 @@ \label{fig:topologymanagerandnode} \end{figure} -\section{Aliceによるプログラミング手法} + +\subsection{Aliceによるプログラミング手法} AliceはCode SegmentとData Segmentによってプログラミングを行なう。Code Segmentから別にCode SegmentへData Segmentを引き渡す際、コンストラクタは使わない。Code SegmentがLocal / Remote Data Segmentに対してputを行い、別のCode SegmentがLocal / Remote Data Segmentに対してpeekを行うことで引き渡される。つまり、Code Segmentは実行前後にData Segmentへ通信が行われるのである。この通信の順序がCode Segmentの実行順序を決定している。 すなわち、Aliceによるプログラミングとは通信の管理を行うことであり、プロトコルを設計することと捉える事ができる。 diff -r 8e0b26d962cc -r 675939a7f983 paper/chapter3.tex --- a/paper/chapter3.tex Sun Jan 18 00:23:22 2015 +0900 +++ b/paper/chapter3.tex Fri Jan 23 16:43:48 2015 +0900 @@ -75,13 +75,13 @@ heartbeatは、Node AからNode Bに一方向に送られる訳ではなく、Node BからNode Aにも送られている。 \section{切断時の処理} -DataBaseではデータ更新の際にトランザクション処理に障害が起こった場合、DataBase側でトランザクション処理開始前に戻すロールバックという処理が行われる。 +MMORPGでは、試合の最中にサーバーからユーザーが切断された場合、自動的にユーザーが操作するキャラクターをゲーム開始時の位置に戻すという処理が実行される。 同様にTreeVNCでは切断を検知した場合、LostParentというメッセージがトップノードに対して送信される。 以上の例のように、アプリケーションはノードの切断に対する処理を用意したい場合がある。 しかし、Aliceを用いたアプリケーションの場合、アプリケーション側で検知するのは難しい。 切断自体は、Remote Data Segmentに対してwriteまたはreadを行った際に出るExceptionにより判断することができる。 -だが、I/O の処理はCode Segmentを実行するThreadで行われない。専用のI/O Threadによって行われるため、Code Segment内でExceptionを捕まえられず、例外として処理することができない。 +だが、I/O の処理はCode Segmentを実行するThreadで行われない。専用のI/O Threadによって行われるため、Code Segment内でExceptionを捕まえられず、例外処理を行なうことができない。 そこで、Aliceが切断を検知した際に、任意のCode Segmentを実行できる機能 (ClosedEventManager)を追加した。 ユーザはClosedEventManagerにCode Segmentを登録することで、切断時の処理として実行するCode Segmentを指定できる。 @@ -106,7 +106,6 @@ 図 \ref{fig:TopologyFIx}、 \ref{fig:TopologyFIx2}、\ref{fig:TopologyFIx3}はTopologyの再構成をコラボレーションダイアグラムで表したものである。 -%コラボレーションダイアグラム図の挿入 \begin{figure}[htbp] \begin{center} \includegraphics[width=120mm]{images/TopologyFIx.pdf} @@ -147,6 +146,13 @@ \end{enumerate} \section{再接続の処理} +MMORPGでは、試合の最中に障害などによりサーバーから離脱したユーザーが、試合が終わるまでに再びサーバーに接続してきた場合に、再びその試合に参加できるような再接続の処理が用意されている。 + +分散にアプリケーションでは、MMORPGの例のように再接続してきたノードに対して通常の処理とは別の処理を行わせたい場合がある。そこで、Aliceに再接続してきたノードに、任意のCode Segmentを実行できる機能を追加した。ユーザーはconfigにCode Segmentを継承したClassを登録することで、再接続時に実行されるCode Segmentを指定することができる。 + +\begin{table}[htbp] +\lstinputlisting[label=src:StartAquarium, caption=再接続に実行するCode Segmentの登録方法]{source/StartAquariumFX.java} +\end{table} \section{Multicast Data Segment} TreeVNCには、Multicastを利用して起動しているTreeVNCのRoot Nodeの情報の一覧にして表示する接続先自動検索システムという機能がある。この機能によりTreeVNCの起動の際にIPアドレスを入力する手間を省くことができる。 diff -r 8e0b26d962cc -r 675939a7f983 paper/chapter5.tex --- a/paper/chapter5.tex Sun Jan 18 00:23:22 2015 +0900 +++ b/paper/chapter5.tex Fri Jan 23 16:43:48 2015 +0900 @@ -12,11 +12,9 @@ \begin{center} \begin{tabular} {|l|l|} \hline - {\bf CPU}&Intel(R) Xeon(R) X5650 @2.67GHz\\ + {\bf CPU}&Intel Xeon E5-1650 v2 @3.50GHz\\ \hline - {\bf 物理コア数}&12\\ - \hline - {\bf 論理コア数}&24\\ + {\bf 物理コア数}&6\\ \hline {\bf CPU キャッシュ}&12MB\\ \hline @@ -26,7 +24,7 @@ \end{center} \end{table} \subsection{実験結果} -100万の要素をもつ配列のSortにかかる時間を計測する。同時に走るCode Segmentが物理コア数と同じになるように、分割数は10個で行った。 +100万の要素をもつ配列のSortにかかる時間を計測する。同時に走るCode Segmentが物理コア数と同じになるように、分割数は4個で行った。 \begin{table}[html] \caption{bitonic sortの結果} @@ -36,7 +34,7 @@ \hline & 改善前 & 改善後 \\ \hline - 実行時間 (ms)& 232.7 & 131.0 \\ + 実行時間 (ms)& 164.8 & 112.1 \\ \hline \end{tabular} \end{center} @@ -74,7 +72,7 @@ \begin{figure}[htbp] \begin{center} - \includegraphics[width=110mm]{images/topologyring.pdf} + \includegraphics[width=120mm]{images/topologyring.pdf} \end{center} \caption{100周にかかる時間を計測し、1周あたりの平均時間を求める} \label{fig:topologyring} @@ -131,16 +129,25 @@ \subsection{実験結果} \subsubsection{改善効果とFederated Lindaとの比較} -データのサイズは4KBで実験を行った。 +データのサイズは10Bと100KBで実験を行った。10Bの結果は図\ref{fig:compare_10B}、100KBの結果は図\ref{fig:compare_100KB}である。 \begin{figure}[htbp] \begin{center} - \includegraphics[width=140mm]{images/compare.pdf} + \includegraphics[width=140mm]{images/compare_10B.pdf} \end{center} - \caption{4096 bytes のデータを 100 周させたときの 1 周にかかる平均時間} - \label{fig:compare} + \caption{10 bytes のデータを 100 周させたときの 1 周にかかる平均時間} + \label{fig:compare_10B} + + \begin{center} + \includegraphics[width=140mm]{images/compare_100KB.pdf} + \end{center} + \caption{100 Kbytes のデータを 100 周させたときの 1 周にかかる平均時間} + \label{fig:compare_100KB} \end{figure} -改善によって24\% ほど実行速度を改善することができた。また、改善後とFederated Lindaの比較では45台の場合、0.8ms 程、Aliceが遅い。 +10Bと100KBの両方の結果でAliceに行った改善の効果を確認することができる。 +45台を使用した実験では10Bの小さいパットの場合では17％、100KBの大きいパケットの場合では12％程度高速化することができた。 +Federated Lindaと改善後の比較では、10Bの場合でAliceのほうが20％程遅い。しかし、100KBの場合ほとんど差がないことがわかる。 +\newpage \subsubsection{no-tcp-delay有無の比較} TCPはデフォルトで、Nagleアルゴリズムを使用している。Nagleアルゴリズムは、小さいパケットを集めてまとめて送信することで、送信するパケット数を減らし効率性をあげるアルゴリズムである。このアルゴリズムにより、実験結果に影響があるか調査した。 @@ -155,6 +162,34 @@ 図\ref{fig:TcpNoDelay}からTCP\_NODELAYにおける影響はないことがわかる。 \section{考察} +今回の結果から、Aliceは先行研究であるFederated Lindaと同等の性能を持つことが確認できた。 +また、並列性能の改善と分散性能の改善の両方に効果があることを確認できた。 +両方に共通して行った改善として、複数のSEDAのステージをまとめて1つのステージにしたことがあげられる。 +SEDAが実行結果に大きく影響を与えていることが分かる。 + +10Bの実験でFederated Lindaに及ばない理由としてもSEDAが原因と考えられる。 +リングの実験は並列処理を行なう部分がないシーケンシャルな実験であるため、全ての処理は直列的に実行される。SEDAによるThreadの切り替えが発生する分Aliceの実行速度は遅くなる。 +100KBの実験ではData Segmentの送受信にかかる時間に比べ、Threadの切り替えの時間が無視できる程度小さいため、Federated Lindaと同じグラフとなる。 + +AliceがFederated Lindaに対して優位な点は、マルチコアによる並列実行である。従って、複数のCode Segmentが同時に走る実験では、小さなパケットの場合でもFederated Lindaに勝つことができると予想される。 \section{TreeVNCとのCodeの比較} +TreeVNCとAliceVNCのソースコードに対してwcを行い、TightVNCからどの程度コードが増加しているかを調べた。（表\ref {tb:diffwordCount}） +\begin{table}[htbp] +\begin{center} +\begin{tabular} {|l|r|r|} + \hline + {\bf }&行数&単語数\\ + \hline + {\bf TreeVNC}&5049&14191\\ + \hline + {\bf AliceVNC}&989&2355\\ + \hline +\end{tabular} +\end{center} +\caption{コードの増加量} +\label{tb:diffwordCount} +\end{table} + +AliceVNCはTreeVNCの20\%の行数で記述できることがわかる。コード量が少なければ管理する手間が少ないためプログラマー負担を減らすことができる。つまり、Aliceを使うことでプログラマーの負担を20\%減らせる。 \ No newline at end of file diff -r 8e0b26d962cc -r 675939a7f983 paper/images/compare.pdf Binary file paper/images/compare.pdf has changed diff -r 8e0b26d962cc -r 675939a7f983 paper/images/compareTcpDelay.pdf Binary file paper/images/compareTcpDelay.pdf has changed diff -r 8e0b26d962cc -r 675939a7f983 paper/images/compare_100KB.pdf Binary file paper/images/compare_100KB.pdf has changed diff -r 8e0b26d962cc -r 675939a7f983 paper/images/compare_10B.pdf Binary file paper/images/compare_10B.pdf has changed diff -r 8e0b26d962cc -r 675939a7f983 paper/master_paper.tex --- a/paper/master_paper.tex Sun Jan 18 00:23:22 2015 +0900 +++ b/paper/master_paper.tex Fri Jan 23 16:43:48 2015 +0900 @@ -27,7 +27,7 @@ \end{minipage}} \markleftfoot{% 左下に挿入 \begin{minipage}{.8\textwidth} - 分散ネットワークフレームワーク Alice の設計と実装 + 分散フレームワーク Alice 上の meta computation と応用 \end{minipage}} \newcommand\figref[1]{図 \ref{fig:#1}} diff -r 8e0b26d962cc -r 675939a7f983 paper/source/StartAquariumFX.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/source/StartAquariumFX.java Fri Jan 23 16:43:48 2015 +0900 @@ -0,0 +1,8 @@ +public class StartAquariumFX { + public static void main(String args[]){ + AquariumConfig conf = new AquariumConfig(args); + conf.register(MoveBeforePosition.class); + StartCodeSegment cs = new StartCodeSegment(); + new TopologyNode(conf, cs); + } +} \ No newline at end of file