Mercurial > hg > Papers > 2012 > sugi-prosym

--- a/Paper/Makefile	Mon Nov 26 17:44:11 2012 +0900
+++ b/Paper/Makefile	Mon Nov 26 18:53:28 2012 +0900
@@ -8,6 +8,38 @@


+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
 PAPER = alice.ind
--- a/Paper/alice.ind	Mon Nov 26 17:44:11 2012 +0900
+++ b/Paper/alice.ind	Mon Nov 26 18:53:28 2012 +0900
@@ -18,21 +18,21 @@

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

-Alice\cite{}は、本研究室で開発を行なっている並列タスク管理フレームワーク である。
-Cell 用の Open CL に似た Task 管理フレームワークCerium\cite{} と、Linda\cite{} を相互接続した分散フレームワークである Federated Linda\cite{} の開発を通して得られた知見を生かされている。
+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{}。Meta Engine では、タプルのやり取りによって起動する call back を使うが、call back による記述が分散してしまい、可読性を落としてしまう。また、複数のタプルの待ち合わせが重要だが、その待ち合わせは single threaded な Meta Engine 内部の状態に依存する。
+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{} であり、その双対が Data Segment である。
+これらが示しているのは、並列分散実行はコードの並列実行だけでなく、データの単位が重要だということである。そこで、 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 で実装したフレームワークである。トポロジーマネージャーを持ち、Bldae 上での
-分散プログラムの実験を容易に行うことができる。また、SEDA Architecture \cite{} を採用しており、マルチコア上でのスループットの向上を期待している。
+分散プログラムの実験を容易に行うことができる。また、SEDA Architecture \cite{SEDA2001} を採用しており、マルチコア上でのスループットの向上を期待している。

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


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

@@ -75,7 +77,9 @@
 \label{fig:put}
 \end{figure}

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


@@ -87,6 +91,7 @@
 \label{fig:update}
 \end{figure}

+---peek

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

@@ -112,6 +117,8 @@
 {\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})
@@ -125,7 +132,7 @@
 \label{fig:take}
 \end{figure}

---Data Segmentの表現
+--Data Segmentの実装

 Data Segmentのデータの表現にはMessagePackを利用している。
 MessagePackに関してJavaにおけるデータ表現は以下の3段階あり、これらのデータ表現は制限を伴うが互いに変換かのである。
@@ -147,7 +154,7 @@
 ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを表現することができる。
 この場合、クラス宣言時に@Messageというアノテーションをつける必要がある。(ソースコード \ref{fig:MessagePackTest})もちろん、MessagePackで扱うことのできるデータのみをフィールドに入れなければならない。
 \begin{table}[htbp]
-\lstinputlisting[label=MessagePackTest, caption=一般的なクラスをIDLのように使用]{source/MessagePackTest.java}
+\lstinputlisting[label=fig:MessagePackTest, caption=一般的なクラスをIDLのように使用]{source/MessagePackTest.java}
 \end{table}

 --Code Segment
@@ -161,25 +168,11 @@
 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);
+\begin{table}[tb]
+\lstinputlisting[label=fig:SendWidth, caption=Data Segment の例]{source/SendWidth.java}
+\end{table}

-    @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 ids,ods} により、Input/Ouput を選択して 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 的には望ましい。

@@ -194,7 +187,7 @@


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

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

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

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

-InputDataSegmentManagerはCode Segmentの\tt ids}というフィールドを用いてアクセスする。
+InputDataSegmentManagerはCode Segmentの{\tt ids}というフィールドを用いてアクセスする。
 \begin{itemize}
 \item {\ttfamily Receiver create(CommandType type)}
 \end{itemize}
@@ -241,11 +234,11 @@

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

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

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

 \begin{table}[tb]
 \lstinputlisting[label=ring, caption=3台でリングを組んだ時の例]{source/ring.dot}
@@ -262,7 +255,7 @@
 \scalebox{0.6}{\includegraphics{images/ring.pdf}}
 \end{center}
 \caption{dotコマンドで作成された3台で構成されたリングのグラフ}
-\label{fig:take}
+\label{fig:ring}
 \end{figure}


@@ -292,27 +285,27 @@
 従来のFederated Lindaよいも若干遅い結果になっている。一部の異常なデータがあるが、データ量が増えると差は縮まっている。これは、コピーの影響よりも、個々の通信の手間の影響が大きいことを示している。00

 \begin{figure}[htbp]
-  \begin{center}
-    \includegraphics[width=110mm]{./images/ring10B.pdf}
-  \end{center}
-  \caption{10 bytes のデータを100周させたときの1周にかかる平均時間}
-  \label{fig:ring10B}
+\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=110mm]{./images/ring10KB.pdf}
-  \end{center}
-  \caption{10 Kbytes のデータを100周させたときの1周にかかる平均時間}
-  \label{fig:ring10KB}
+\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=110mm]{./images/ring100KB.pdf}
-  \end{center}
-  \caption{100 Kbytes のデータを100周させたときの1周にかかる平均時間}
-  \label{fig:ring100KB}
+\begin{center}
+\includegraphics[width=70mm]{./images/ring100KB.pdf}
+\end{center}
+\caption{100 Kbytes のデータを100周させたときの1周にかかる平均時間}
+\label{fig:ring100KB}
 \end{figure}


@@ -323,34 +316,34 @@

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

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

 \begin{figure}[htbp]
-  \begin{center}
-    \includegraphics[width=110mm]{./images/ring_notp_10b.pdf}
-  \end{center}
-  \caption{Code Segment のスレッドプールを使用せずに、 10 bytes のデータを回した時の実験結果}
-  \label{fig:ringnothread}
+\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 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 を
+{\bf Key } 本実装では Data Segment 相互の参照は Key 経由となる。Linda や分散実装では、それは妥当だが、並列実装では、すべての Data Segment を
 Key Value Store
 に格納するのは性能的な問題を引き起こす。一方で、分散記述と並列記述がかけ離れてしまうのも好ましくない。現状は Key Value Store は Java の Concurrent
 Hash map を用いているが、今のベンチマークでは、そこがネックになっているわけではないと思われる。本来は、このKey Value Store は持続性を持つべきだと
 思われるが今回は実装していない。

-\{bf Java }
+{\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 拡張性}
+{\bf 拡張性}
 分散アプリケーションでのプロトコルは常に変更されるものであり、Alice もそれに対応する必要がある。Alice 上で走るプロトコルは、
 Data Segment と Code Segment によって決まる。Key とトポロージーマネージャーをプロトコル毎に別に用意すれば、複数のプロトコルを
 同時に走らせることが可能である。プロトコル間の互換性はいろいろあり得る。Data Segment と Code Segment の結びつきは弱いので、
@@ -360,13 +353,13 @@

 --まとめと今後の課題

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

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

 特に、今回はノード内の並列実行や GPGPU による並列実行などは考慮していないので、将来的には、それを含めた実装をしていきたい。
--- a/Paper/sugi-prosym.tex	Mon Nov 26 17:44:11 2012 +0900
+++ b/Paper/sugi-prosym.tex	Mon Nov 26 18:53:28 2012 +0900
@@ -1,5 +1,6 @@
 \documentclass[private]{ipsjpapers}
 \usepackage{listings}
+\usepackage{url}
 \usepackage[dvipdfm]{graphicx}

 \bibliographystyle{jplain} % for bibliography
@@ -90,6 +91,10 @@
 \input{abstract-e}
 \end{eabstract}

+% 表題などの出力
+\maketitle
+
+
 \input{0}

 \bibliography{ref}