-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.



--歴史的経緯

本研究室では、並列タスク管理フレームワークCeriumの管理を行なっているが、その設計と実装を行うにあたり、並列プログラミングと分散プログラミング
は本質的には同じことを行なっていることが分かった。特にヘテロジーニアスマルチコアであり、ローカルストアをそれぞれのコアが持っているというCell の特異な環境は、分散プログラミング環境と告示している。それらを踏まえて、Ceriumのタスク管理手法を分散に応用できないかと考えた。


Ceriumに置いても、タスクとそれの入出力データの取り扱いは難しい課題である。データを操作するAPIを考えて、タスクを自然に記述し、効率良く実行する方法を考えてきた。そこで考えられた手法が、データをDataSegment、タスクをCodeSegmentという単位に分割して記述する方法である。


--分散ネットフレームワークAlice
\label{sec:ITEM}

Aliceは本研究室の卒業生である赤嶺一樹氏が、本研究室で開発を行なっている並列タスク管理フレームワーク Cerium と先行研究である Federated Linda の開発を通して得られた知見を生かされている。
Federated Linda の設計はシングルスレッドで行われている。しかし、近年ではマルチコアのマシンが主流となっている。将来的にはメニーコアのマシンが主流になってくると考えられるそのような背景を踏まえてAliceはマルチスレッド向けに設計されている。

AliceはData SegmentとCode Segmentという単位でデータと処理を細かく分割し、それぞれの依存関係を記述して分散プログラムを作成する。また、他のマシンとの接続トポロジーの構成の機能も有しているのでユーザーはトポロジー構成後の処理を記述するだけでよい。
また、AliceはJavaで実装されている。

--Data Segment

AliceではData Semgnetをデータベースとして利用している。KeyValueStoreで実装されており、キーごとにリストを持っている。Data Segment APIを用いることで、リストにデータを追加、削除を適宜行うことができる。


--Data Segment Manager

大量のData Segmentを管理するのがData Segment Managerである。
Data Segment Managerは文字列のキーでData Segmentを整理する。また、各キーごとにキュー構造を持っている。それらをData Segment APIを用いて操作する。
データの読み出し("peek" または "take")時に、希望のデータがなかった場合、ブロッキングを行う機能を持つ。
しかし、ブロッキングといってもそこで同期するわけではない。
非同期でデータを通信する。
そのため、データの読み出し時には他の API とは違い、レスポンスが発生する。

--Data Segment API

以下が用意されている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,\\ int id)}
\item {\ttfamily void take(Receiver receiver, String key,\\ int id)}
\end{itemize}

---put

"put" はデータを追加するための API である。
"put" は受け取ったデータ val を Data Segment 内のキューに対してエンキューする。
この時、キーごとに重複しない連番の ID を受け取った順に振る。(図 \ref{fig:put})


\begin{figure}[tb]
%\begin{center}
\scalebox{0.6}{\includegraphics{images/put.pdf}}
%\end{center}
\caption{"put"は重複しないIDを振りながらデデータを追加する}
\label{fig:put}
\end{figure}

---update

"update" はデータを置き換えるための API である。

"update" はキューの先頭にあるデータをひとつだけ削除する。
その後は "put" と同じく、 受け取ったデータ val を Data Segment 内のキューに対してエンキューする。
この時、キーごとに重複しない連番の ID を受け取った順に振る。(図 \ref{fig:update})


\begin{figure}[tb]
\begin{center}
\scalebox{0.6}{\includegraphics{images/update.pdf}}
\end{center}
\caption{"update"は先頭データを取り除き、重複しないIDを振りながらデータを追加する}
\label{fig:update}
\end{figure}

---peek

"peek" はデータを読み込むための API である。

"peek" は前回読み込んだデータの id を引数で指定する。省略した場合は、 0 が id として渡される。
id よりも値の大きい id のデータがキューに含まれていれば、そのデータを receiver に返す。(図 \ref{fig:peek})

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

もし id 以下のデータしか無いならば、データの更新が前回の "peek" 発行時から更新が無いものと考え、リストに格納されて保留される。
(図 \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}

"take" や "update" によりデータの更新があれば、 "peek" が直ちに実行される。

---take

"take" もデータを読み込むための API である。
基本的な id に関する部分は "peek" と同じである。

"peek" との決定的な違いは、読み込まれたデータは Data Segment 内のキューから取り除かれるということである。
(図 \ref{fig:take})


\begin{figure}[tp]
\begin{center}
\scalebox{0.6}{\includegraphics{images/take.pdf}}
\end{center}
\caption{"peek"はデータをreceiverに読み込む。希望のデータが無いときは保留する。}
\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 を記述し、依存関係を作る。依存関係により、実行される順番が一意に決まる。実際に使用するData Segment はCode Segmentの入出力に相当する。それぞれ、Input Data Segment、Output Data Segmentとする。

--Code Segmentの実行方法

Code Semgnetを実行するためにはStart Code Segment (ソースコード \ref{fig:StartCodeSegment})という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

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


---OutputDataSegmentManager

OutputDataSegmentManagerはCode Segmentのodsというフィールドを用いてアクセスする。
OutPutDataSegmentManagerは"put"または"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

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

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

Topology Managerはトポロジーファイルを読み込むが、トポロジーファイル自体はDOT Languageという言語で記述される。
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}

--評価


--まとめと今後の課題