view Paper/alice.ind @ 31:32b555e8fb6f

minor change
author e095732 <e095732@ie.u-ryukyu.ac.jp>
date Fri, 21 Dec 2012 15:32:46 +0900
parents dc453f4c4acf
children
line wrap: on
line source

-title: Code Segment と Data Segment によるプログラミング手法

-author: 河野 真治, 杉本 優

-abstract:

データをData Segment、タスクをCode Segmentという単位に分割して記述する
分散ネットフレームワーク Alice を作成した。Alice によるプログラミング例を示すと共に、
本研究室で従来使ってきた Federated Linda との比較も示し、Java による実装について考察する。

-abstract-e:

We have developed an distributed programming frame Alice, which uses Data Segment and Code Segment as programming units.
We show programming examples and comparisons with our old framework, Federated Linda. We show some consideration about
our Java implementation.




--分散ネットフレームワークAlice

Alice\cite{kono11g}は、本研究室で開発を行なっている並列タスク管理フレームワーク である。
Cell 用の Open CL に似た Task 管理フレームワークCerium\cite{kono09b,cerium-sourceforge} と、Linda\cite{linda} を相互接続した分散フレームワークである Federated Linda\cite{kono05b} の開発を通して得られた知見を生かされている。

Cerium では、Taskを小さく分割して並列実行し、データ転送はパイプライン実行により隠される。Taskには依存関係があり、その記述は煩雑になるが、実際にはデータの依存関係がそのまま Task の依存関係になることが多い。繰り返し使われるデータ構造の管理が重要であり、実行時にわかるデータ構造間の依存関係が Task を複雑にしている。

Federated Linda では、Linda サーバ内部に Meta Engine と呼ばれる Linda のタプル(データ構造)をやり取りする部分を作成した\cite{kono10d}。Meta Engine では、タプルのやり取りによって起動する call back を使うが、call back による記述が分散してしまい、可読性を落としてしまう。また、複数のタプルの待ち合わせが重要だが、その待ち合わせは single threaded な Meta Engine 内部の状態に依存する。

これらが示しているのは、並列分散実行はコードの並列実行だけでなく、データの単位が重要だということである。そこで、 AliceはData SegmentとCode Segmentという単位でデータと処理を細かく分割し、それぞれの依存関係を記述して分散プログラムを作成する。Code Segment は Continuation based C の実行単位\cite{kono00a,cbc-sourceforge} であり、その双対が Data 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 で実装したフレームワークである。トポロジーマネージャーを持ち、Blade 上での
分散プログラムの実験を容易に行うことができる。また、SEDA Architecture \cite{SEDA2001} を採用しており、マルチコア上でのスループットの向上を期待している。

本論文では、Code Segment と Data Segment の Alice のAPIと、その設計方針を示し、それによって実装された水族館プログラムを示す。また、これまでの Federated 
Linda との性能評価も行う。

% また、他のマシンとの接続トポロジーの構成の機能も有しているのでユーザーはトポロジー構成後の処理を記述するだけでよい。また、AliceはJavaで実装されている。

--Data Segment API

Data Segment は数値や文字列などのデータを構造体的に保持するが、Data Segment の相互参照が問題になる。
AliceではData Segmentをデータベースとして扱い、Data Segment は必ずキーを持つ。つまり、Data Segment を Key Value Store として考えることができる。
通常のデータベースでは隠れているが、Key 毎のキューがあり、Key 毎に順に実行される。key 毎の追加と取得は、Linda に準じた設計になっている。

Data Segmentを管理するのがData Segment Managerである。ノード毎に local DS manager と remote DS manager がある。local DS manager は、ノードに固有の
key Value Store と考えることができる。したがって Key はノード内部で unique な文字列である。

remote DS manager は他のノードのlocal DS manager の proxy である。Alice のトポロジーマネージャーが remote DS manager を自動的に構成する。つまり、remote DS manager は複数あって、それぞれ対応するノードが異なる。

Key Value Store へのアクセスはキューによって、ノード内部で逐次化される。それ以外は、すべて Java の Thread pool により並列実行される。
Code Segment が実行される時には、Data Segment はすべて手元に揃っているので、Blocking が起きることはない。逆に、Blocking が必要な場合は、
Code Segment を分割する必要がある。

以下が用意されているData Segment APIである。これらを用いてデータの送受信を行う。
\begin{itemize}
\item {\ttfamily void put(String key, Value val)}
\item {\ttfamily void update(String key, Value val)}
\item {\ttfamily void peek(Receiver receiver, String key}
\item {\ttfamily void take(Receiver receiver, String key)}
\end{itemize}


---put

{\tt put} はデータを追加するための API である。Key Value Store のキューに追加される。
(図 \ref{fig:put})


\begin{figure}[tb]
%\begin{center}
\scalebox{0.6}{\includegraphics{images/put.pdf}}
%\end{center}
\caption{putはデータを追加する}
\label{fig:put}
\end{figure}

---update

{\tt update} はデータを置き換えるための API である。キューの先頭を置き換える特急メッセージのように動作する。
(図 \ref{fig:update})


\begin{figure}[tb]
\begin{center}
\scalebox{0.6}{\includegraphics{images/update.pdf}}
\end{center}
\caption{updateはキューの先頭を書き換える}
\label{fig:update}
\end{figure}

---peek

{\tt peek はデータを調べる}

\begin{figure}[tb]
\begin{center}
\scalebox{0.6}{\includegraphics{images/peek.pdf}}
\end{center}
\caption{peekはデータを調べる}
\label{fig:peek}
\end{figure}

最新のData Segment がなければ、Code Segmentの待ち合わせ(Blocking)が起きる。
(図 \ref{fig:no_peek})

\begin{figure}[tb]
\begin{center}
\scalebox{0.6}{\includegraphics{images/peek1.pdf}}
\end{center}
\caption{希望のデータが無いときは保留する}
\label{fig:no_peek}
\end{figure}

{\tt put} や {\tt update} によりData Segment の更新があれば、 {\tt peek} が直ちに実行される。つまり、
Data Segment を作成した Code Segment が active queue に移される。

---take

{\tt take} もデータを読み込むための API である。
読み込まれたデータは Key Value Storeのキューから取り除かれる。これは、Linda の in() に相当する。
(図 \ref{fig:take})
必要な待ち合わせが行われる。

\begin{figure}[tp]
\begin{center}
\scalebox{0.6}{\includegraphics{images/take.pdf}}
\end{center}
\caption{take はデータを読み込む}
\label{fig:take}
\end{figure}

--Data Segmentの実装

Data Segmentのデータの表現にはMessagePackを利用している。
MessagePackに関してJavaにおけるデータ表現は以下の3段階あり、これらのデータ表現は制限を伴うが互いに変換可能である。

\begin{itemize}
\item {\ttfamily 一般的なJavaのクラスオブジェクト}
\item {\ttfamily MessagePack for JavaのValueオブジェクト}
\item {\ttfamily byte[]で表現されたバイナリ}
\end{itemize}

Data Segment APIでは、このMessagePack for JavaのValueオブジェクトを用いてデータが表現されている。
MessagePackはJavaのように静的に型付けされたオブジェクトではなく、自己記述なデータ形式である。MessagePack for JavaのValueオブジェクトはMessagePackのバイナリにシリアライズできる型のみで構成されたJavaのオブジェクトである。そのため、Valueも自己記述式のデータ形式になっている。


Valueオブジェクトは通信に関わるときには、シリアライズ・デシリアライズを高速に行うことができる。
また、ユーザーはメソッドを用いてオブジェクト内部のデータを閲覧、編集することができる。


ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを表現することができる。
この場合、クラス宣言時に@Messageというアノテーションをつける必要がある。(ソースコード \ref{fig:MessagePackTest})もちろん、MessagePackで扱うことのできるデータのみをフィールドに入れなければならない。
\begin{table}[htbp]
\lstinputlisting[label=fig:MessagePackTest, caption=一般的なクラスをIDLのように使用]{source/MessagePackTest.java}
\end{table}

--Code Segment

Code Segmentはタスクのことである。Code Segmentをユーザーが記述するときに、Code Segment 内で使用するData Segment の作成を記述する。
Code Segment には、Input Data Segment と Output Data Segment を作る API が存在する。

Input Data Segment で作成された Data segment は、remote か local かと、key を指定する必要がある。Input Data Segment がすべて揃わないと
Code Segment は active にならない。

Output Data Segment で作成された Data segment にも、remote か local かと、key を指定する必要がある。Input/Output が Code Segment 間の
依存関係を自動的に記述することになる。

\begin{table}[tb]
\lstinputlisting[label=fig:SendWidth, caption=Data Segment の例]{source/SendWidth.java}
\end{table}

{\tt ids,ods} により、Input/Output を選択して Data Segment を作成する。Output には put 時にキーを指定する(図\ref{fig:SendWidth})。Input は setKey を使ってキーを指定する。
もちろん、{\tt cs.width} のようにアクセスするのは Java 的には正しくない書き方であり避けるべきである。{\tt SendWidth} は Code Segment であり、
Data Segment が揃った時に、 {\tt Runnable} のように実行される。{\tt SendWidth} 内部で setKey する方が Java 的には望ましい。

どの時点でキーとノードを指定するか、どのようなAPIを用意するべきかは、まだ、議論の余地がある。

--Code Segmentの実行方法

Alice には、
Start Code Segment (ソースコード \ref{fig:StartCodeSegment})というC の main に相当するような最初に実行される Code Segment がある。
Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。
このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。(ソースコード \ref{fig:TestLocalAlice})


\begin{table}[tb]
\lstinputlisting[label=fig:TestLocalAlice, caption=Start Code Segmentを実行させる方法]{source/TestLocalAlice.java}
\end{table}

--Code Segmentの記述方法

Code Segmentをユーザーが記述する際にはCode Segmentを継承して記述する。(ソースコード \ref{fig:CodeSegment})そのCodeSegmentはInputDataSegmentManagerとOutputDataSegmentManagerを利用することができる。

\begin{table}[tb]
\lstinputlisting[label=fig:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java}
\end{table}

\begin{table}[tb]
\lstinputlisting[label=fig:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java}
\end{table}

InputDataSegmentManagerはCode Segmentの{\tt ids}というフィールドを用いてアクセスする。
\begin{itemize}
\item {\ttfamily Receiver create(CommandType type)}
\end{itemize}
createでコマンドが実行された際に取得されるData Segmentが格納される受け皿を作る。引数にはCommandTypeが取られ、指定できるCommandTypeは{\tt PEEK}または{\tt TAKE}である。
\begin{itemize}
\item {\ttfamily void setKey(String managerKey, String key)}
\end{itemize}
setKeyメソッドにより、どこのData Segmentのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定することができる。
コマンドの結果がレスポンスとして届き次第Code Segmentは実行される。


OutputDataSegmentManagerはCode Segmentの{\tt ods}というフィールドを用いてアクセスする。
OutPutDataSegmentManagerは{\tt put}または{\tt update}を実行することができる。
\begin{itemize}
\item {\ttfamily void put(String managerKey, String key, \\ Value val)}
\item {\ttfamily void update(String managerKey, String key, Value val)}
\end{itemize}

--Topology Manager

Alice は複数のノードで構成され、相互に接続される。通信するノードは、URLなどにより直接指定するのではなく、
TopologyManagerによって管理される。

TopologyManager関連の通信処理はCode Segmentで実装してある。
TopologyManagerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきクライアントのIPアドレスやポート番号、接続名を送り、トポロジーファイルに記述された通りにトポロジーを作成する。

Code Segment 内部で remote DS manager にアクセスする場合は、Topology Manager によって指定されたノード内部だけで有効なlabel(文字列)を使う。これにより、
特定のURLが Code Segment 内部に記述されることを防いでいる。

---Topology Managerの設定ファイル

Topology Managerはトポロジーファイルを読み込むが、トポロジーファイル自体はDOT Language\cite{graphviz}という言語で記述される。
DOT Languageとはプレーンテキストを用いて、データ構造としてのグラフを表現するための、データ記述言語の一種である。このDOT Languageのグラフを利用して、クライアント間の接続を表現する。DOT Languageファイルはdotコマンドを用いて、グラフの画像ファイルを出力することができるので、記述したトポロジーが正しいことを可視化して確認することができる。

クライアント間の接続にはlabelを用いて名前が割り振られており、この接続名を用いてユーザーはData Segment Managerにアクセスすることができる。
前述したReceiver にsetKeyを行う際、odsでputまたはupdateする際の引数のmanagerKeyがこれにあたる (図\ref{fig:ring})。

\begin{table}[tb]
\lstinputlisting[label=ring, caption=3台でリングを組んだ時の例]{source/ring.dot}
\end{table}



\begin{figure}[tb]
\begin{itemize}
\item {\ttfamily dot -T png ring.dot -o ring.png}
\end{itemize}

\begin{center}
\scalebox{0.6}{\includegraphics{images/ring.pdf}}
\end{center}
\caption{dotコマンドで作成された3台で構成されたリングのグラフ}
\label{fig:ring}
\end{figure}


Alice の Nodeを起動する際にコマンドライン引数としてTopology ManagerのIPアドレスとポート番号を指定をする。
そしてmain関数内でTopologyNodeをnewを行えば良い。
TopologyNodeの第一引数は Alice デーモンの設定オブジェクト、第二引数はStart Code Segmentである。
ここで指定した、Start Code Segmentがトポロジーが完成した後実行される。


--水族館の例題

今回作成した例題は水族館である。複数のクライアントのディスプレイを複数の魚が移動していくものである。魚は画面の端まで移動すると自分の画面上からは消え、別のクライアントの画面の端から魚が出てくる。また、魚のうち一匹はクライアントが直接操作することができる。トポロジーはTopologyManagerによりツリー状に構成してある。

\begin{enumerate}
\item ユーザーが魚を操作するまたはCode Segmentにより魚の座標が更新される。
\item 画面に表示させるためのSetLocation (Code Segment)が実行され実際に魚のオブジェクトにセットされ画面に反映される。
\item Update(Code Segment)にFishPosition(魚の座標データ)が渡される。
\item Updateにlist(送信者リスト)が渡される。
\item Updateが実行され、listを元にデータが送信される。ただし、この時にFishPositionには送信元情報が付加されているので、送信元には送信されない。
\item 各clientで2 - 4が実行される。
\end{enumerate}

--実験

Ring 上のトポロジーを構築して、100周回時間を測定してみた。
マシン48台,CPU Intel(R) Xeon(R) X5650 @ 2.67GHz, 仮想コア数4,CPU キャッシュ12MB。Blade 上の仮想マシン上での測定となっている。
従来のFederated Lindaよいも若干遅い結果になっている。一部の異常なデータがあるが、データ量が増えると差は縮まっている。これは、コピーの影響よりも、個々の通信の手間の影響が大きいことを示している。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=70mm]{./images/ring10B.pdf}
\end{center}
\caption{10 bytes のデータを100周させたときの1周にかかる平均時間}
\label{fig:ring10B}
\end{figure}

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=70mm]{./images/ring10KB.pdf}
\end{center}
\caption{10 Kbytes のデータを100周させたときの1周にかかる平均時間}
\label{fig:ring10KB}
\end{figure}

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=70mm]{./images/ring100KB.pdf}
\end{center}
\caption{100 Kbytes のデータを100周させたときの1周にかかる平均時間}
\label{fig:ring100KB}
\end{figure}



--評価と考察

今回の実装は、Java により Code Segment と Data Segment に必要な API を洗い出すためのものであった。この実装でもいくつかの問題が明らかになっている。

{\bf API } Class を継承したり、Input Data segment や Output Data segment の作成に factory object を使うのは Java を使う際の技術的なものであり、Alice のAPI自体は Java に固有である必要はない。むしろ、Java の Object 指向な記述が全体を煩雑にしている部分がある。{\tt update} は、Data Segmentの競合的な更新に使われるべきだと思われる。

{\bf SEDA } Federated Linad に比べて、通信のレスポンスが遅い原因の一つはSEDA architectureのせいだと思われる。SEDA はスループット重視の実装であり、多段のパイプラインのせいでレスポンスは遅れてしまう。実際、スレッドプールを使用しないほうが、Ring の結果は良くなる(図\ref{fig:ringnothread})。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=70mm]{./images/ring_notp_10b.pdf}
\end{center}
\caption{Code Segment のスレッドプールを使用せずに、 10 bytes のデータを回した時の実験結果}
\label{fig:ringnothread}
\end{figure}

レスポンスが要求される部分のスケジューラーを別にするなどの工夫が必要だと思われる。それを記述そのものに入れるのが良いかどうかには議論の余地がある。


{\bf MessagePack } 今回の実装では単純な Message の転送の場合でも MessagePack の decode/encode が必要になる。これは単純に overhead になる。encode/decode 抜きに直接処理できる方が望ましい。また、Data Segment の一部の修正に Data Segment を再構成するのは望ましくない。Cerium では Input Data Segment  と Output Data Segment を swap する API があり、若干状況は複雑になるが良好な結果を得ている。この辺りは、ユーザから見えない最適化として実装する方が望ましいが、なんらかの制御方法も必要だと思われる。

{\bf Key } 本実装では Data Segment 相互の参照は Key 経由となる。Linda や分散実装では、それは妥当だが、並列実装では、すべての Data Segment を 
Key Value Store
に格納するのは性能的な問題を引き起こす。一方で、分散記述と並列記述がかけ離れてしまうのも好ましくない。現状は Key Value Store は Java の Concurrent
Hash map を用いているが、今のベンチマークでは、そこがネックになっているわけではないと思われる。本来は、このKey Value Store は持続性を持つべきだと
思われるが今回は実装していない。

{\bf Java }
Ring の実験での異常なデータは、Java の分散プログラミングでは良く現れる。一つは Java のGCの影響だと思われる。Alice では、すべての Data Segment
は Key Value に格納され、実行時の Data Segment は Code Segment が active な時のみにメモリ上にある。この最大値を見積ることは、Active Task の
量を見積もれば良い。したがって、Alice には Garbage Collection は必要ない。一方で、Key Value Store 上のデータは決して Garbage Collection の
対象にならない。しかし、それは Garbage Collector には負荷をかけてしまう。つまり、Alice 自体は Java で実装するのには向いていない。

{\bf 拡張性}
分散アプリケーションでのプロトコルは常に変更されるものであり、Alice もそれに対応する必要がある。Alice 上で走るプロトコルは、
Data Segment と Code Segment によって決まる。Key とトポロージーマネージャーをプロトコル毎に別に用意すれば、複数のプロトコルを
同時に走らせることが可能である。プロトコル間の互換性はいろいろあり得る。Data Segment と Code Segment の結びつきは弱いので、
Data Segment に余計な値がある場合、あるいは、値が足りない場合に適切な値を設定することにより、古い Code Segment を変更せずに
プロトコルを拡張できると考えている。実際、水族館の例題で、2次元と3次元版を両立させることは容易である。


--まとめと今後の課題

今回、Code Segment と Data Segment による並列分散フレームワークの Java による実装を示した。前の設計\cite{kono11g}と異なる部分は、
実装でしか得られない知見である。

Java による実装は、ラピッドプロトタイピングとしては適切であり、例題の記述と基本性能の確認に向いている。一方で、Java が Aliceの
実装に不向きであることもわかってきた。
Code Segment / Data Segment を見たコンパイラ的アプローチ、あるいは実行時最適化などが有効であると思われる。
あるいは、CbC\cite{cbc-sourceforge} による実装が効果的だと考えている。

特に、今回はノード内の並列実行や GPGPU による並列実行などは考慮していないので、将来的には、それを含めた実装をしていきたい。