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

-author: 河野 真治, 杉本 優

-abstract:

本研究室では分散プログラミングにおいて、データをData Segment、タスクをCode Segmentという単位に分割して記述する方法を提唱している。
しかし、前述した方法をプログラマーが一から記述することは大変である。そこで、本研究室で分散ネットフレームワーク Alice を作成した。本論文では実際にAliceを用>いてCode Segment と Data Segment によるプログラミング手法の例を示す。

-abstract-e:

We suggest that programmers develop a distributed program with splitting data as Data Segment and processing as Code Segment.
But it is difficult for programmers to develop on that way from scratch. So We developed distributed network framework 'Alice'.
We show example how to programming with Code Segment and Data Segment on this paper.




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

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

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

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

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

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

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

--Data Segment API

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

Data Segmentを管理するのがData Segment Managerである。ノード毎に local DS manager と remote DS manager がある。local 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}


{\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}

\{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}


{\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 に移される。

{\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}

DataSegment 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=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 にならない。

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

\begin{verbatim}
public class SendWidth extends CodeSegment {
    
    Receiver width = ids.create(CommandType.PEEK);

    @Override
    public void run() {
        int width = this.width.asInteger();
        ods.put("parent", "widths", width);
        
        System.out.println("send widths: " + width);
        
        SendWidth cs = new SendWidth();
        cs.width.setKey("local", "width", this.width.index);
    }
}
\end{verbatim}

{\tt ids,ods} により、Input/Ouput を選択して Data Segment を作成する。Output には put 時にキーを指定する。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=TestLocalAlice, caption=Start Code Segmentを実行させる方法]{source/TestLocalAlice.java}
\end{table}

--Code Segmentの記述方法

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

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

\begin{table}[tb]
\lstinputlisting[label=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{}という言語で記述される。
DOT Languageとはプレーンテキストを用いて、データ構造としてのグラフを表現するための、データ記述言語の一種である。このDOT Languageのグラフを利用して、クライアント間の接続を表現する。DOT Languageファイルはdotコマンドを用いて、グラフの画像ファイルを出力することができるので、記述したトポロジーが正しいことを可視化して確認することができる。

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

\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:take}
\end{figure}


---Topology Managerの使用方法

Topology 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}

--評価


--まとめと今後の課題