# HG changeset patch # User sugi # Date 1360744382 -32400 # Node ID 3b3b014765a26d3f902d400bd310de7eafed0fc8 # Parent c874088754a4220e56c4a856958026bb54b2f029 minor change diff -r c874088754a4 -r 3b3b014765a2 paper/chapter2.tex --- a/paper/chapter2.tex Fri Feb 08 19:12:52 2013 +0900 +++ b/paper/chapter2.tex Wed Feb 13 17:33:02 2013 +0900 @@ -2,9 +2,23 @@ \label{chap:concept} \section{Alice} -AliceはJavaを用いて作成された分散ネットフレームワークである。本研究室で開発を行なっている並列タスク用管理フレームワークであるCeriumと先行研究であるFederated Lindaの開発を通して得られた知見を生かして本研究室卒業生である赤嶺一樹氏が設計、実装を行った。 -近年のマルチコアのマシンが主流になっている背景からSEDAアーキテクチャが採用されている。SEDAアーキテクチャとは、処理ごとに分けられているステージと呼ばれるものが複数存在し、ステージでデータが処理され次第、次のステージにデータを伝搬していく処理方式である。これによってマルチコアを生かし、パイプライン的に効率よく処理することがが可能となっている。 -また、本研究室が提唱している「CodeSegmentとDataSegmentという単位でプログラムを作成する」というプログラミング手法でプログラムを作成する。 +Aliceは、本研究室で開発を行なっている分散タスク管理フレームワークである。 +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との性能評価も行う。 \section{Data Segment API} Data Segmentは、データ細かく分割したものであり、数値や文字列などのデータを構造体的に保持す @@ -15,7 +29,16 @@ Aliceのデータベースは通常のKVSと若干異なっている点がある。通常のKVSはプログラミング言語の連想配列やMapと同様に「Key(キー)」と「Value(値)」がペアとなってる。そのためKeyに対して取得できるValueは当然1つである。しかし、Aliceの場合は「Key」と「Value」と「Index」がセットとなっているため、Keyに対して保存できる値が複数ある。そのため取得できるValueも複数存在する。 key毎の追加と取得は、Lindaに準じた設計になっている。 -Data SegmentはData Segment Manager(以下DSM)によって管理されている。ノード毎にLocal DSMとRDSMが存在する。Local DSMは、各ノード固有のKey Value Storeとなっている。従って、Keyはノード内部でuniqueなものである。Remote DSMは他のノードのLocal DSMのproxyである。AliceのトポロジーマネージャーがRemote DSMを自動的に構築する。つまりRemote DSMは複数存在し、それぞれに対応するノードが異なる。 +Data SegmentはData Segment Manager(以下DSM)によって管理されている。ノード毎にLocal DSMとRDSMが存在する。Local DSMは、各ノード固有のKey Value Storeとなっている。従って、Keyはノード内部でuniqueなものである。Remote DSMは他のノードのLocal DSMのproxyである。(図 \ref{fig:RemoteDSM}) AliceのトポロジーマネージャーがRemote DSMを自動的に構築する。つまりRemote DSMは複数存在し、それぞれに対応するノードが異なる。 + +\begin{figure}[htbp] +\begin{center} +\includegraphics{fig/remote_datasegment.pdf} +\end{center} +\caption{Remote DSM は他の ノードの Local DSM の proxy } +\label{fig:RemoteDSM} +\end{figure} + KVSへのアクセスはキューによって、ノード内部で逐次化される。それ以外は、すべてJavaのThread Poolによって並列実行される。Code Segmentが実行される際には、Data Segmentが揃っているのでBlockingが起こることはない。逆にBlockingが必要な場合は、Code Segmentを分割する必要がある。 @@ -29,17 +52,60 @@ \end{itemize} \subsection{put} -putはデータを追加するためのAPIである。putは受けとったvalをキーに毎重複しない連番のIDを受け取った順に振る。Lindaのout()に相当する。 +putはデータを追加するためのAPIである。putは受けとったvalをキーに毎重複しない連番のIDを受け取った順に振る。Lindaのout()に相当する。(図 \ref{fig:put}) + +\begin{figure}[htbp] +\begin{center} +\includegraphics{fig/put.pdf} +\end{center} +\caption{putはデータを追加する} +\label{fig:put} +\end{figure} + \subsection{update} -updateはデータを置き換える特急メッセージのように動作する。 putと同様に受けとったvalをキーに毎重複しない連番のIDを受け取った順に振る。Lindaのupdate()に相当する。 +updateはデータを置き換える特急メッセージのように動作する。 putと同様に受けとったvalをキーに毎重複しない連番のIDを受け取った順に振る。Lindaのupdate()に相当する。(図 \ref{fig:update}) + +\begin{figure}[htbp] +\begin{center} +\includegraphics{fig/update.pdf} +\end{center} +\caption{updateはキューの先頭を書き換える} +\label{fig:update} +\end{figure} + \subsection{peek} -peekはデータを調べるAPIである。要求したData Segmentが存在しなければ、Code Segmentの待ち合わせ(Blocking)が起こる。 +peekはデータを調べるAPIである。(図 \ref{fig:peek}) + +要求したData Segmentが存在しなければ、Code Segmentの待ち合わせ(Blocking)が起こる。(図 \ref{fig:no_peek}) -putやupdateによりData Segmentに更新があった場合、peekが直ちに実行される。目的のData Segmentを取得できた場合、Data Segmentを作成したCode Segmentがactive queueに移される。 +\begin{figure}[htbp] +\begin{center} +\includegraphics{fig/peek.pdf} +\end{center} +\caption{peekはデータを調べる} +\label{fig:peek} +\end{figure} + +putやupdateによりData Segmentに更新があった場合、peekが直ちに実行される。目的のData Segmentを取得できた場合、Data Segmentを作成したCode Segmentがactive queueに移される。Lindaのrd()に相当する。 -Lindaのrd()に相当する。 +\begin{figure}[htbp] +\begin{center} +\includegraphics{fig/peek1.pdf} +\end{center} +\caption{希望のデータが無いときは保留する} +\label{fig:no_peek} +\end{figure} + \subsection{take} -takeもデータを読み込むためのAPIである。読み込まれたデータをKVSから取り除かれる。Lindaのin() に相当する。 +takeもデータを読み込むためのAPIである。読み込まれたデータをKVSから取り除かれる。Lindaのin() に相当する。(図 \ref{fig:take}) + +\begin{figure}[htbp] +\begin{center} +\includegraphics{fig/take.pdf} +\end{center} +\caption{take はデータを読み込む} +\label{fig:take} +\end{figure} \section{Data Segmentの実装} Data Segmentのデータの表現にはMessagePackを利用している。 @@ -55,16 +121,12 @@ MessagePackはJavaのように静的に型付けされたオブジェクトではなく、自己記述なデータ形式である。MessagePack for JavaのValueオブジェクトはMessagePackのバイナリに シリアライズできる型のみで構成されたJavaのオブジェクトである。そのため、Valueも自己記述式のデータ形式になっている。 - Valueオブジェクトは通信に関わるときには、シリアライズ・デシリアライズを高速に行うことができる。 また、ユーザーはメソッドを用いてオブジェクト内部のデータを閲覧、編集することができる。 - ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを表現することができる。 この場合、クラス宣言時に@Messageというアノテーションをつける必要がある。もちろん、MessagePackで扱うことのできるデータのみをフィールドに入れなければならない。 - - \section{Code Segment} Code Segmentはタスクのことである。Code Segmentをユーザーが記述するときに、Code Segmentの作成を記述する。Code Segment内で使用するData Segmentの作成を記述する。Code Segmentには、Input Data SegmentとOutput Data Segmentを作るAPIが存在する。 @@ -72,17 +134,33 @@ Out Data Segmentで作成されたData Segmentに対してもremoteかlocalか、keyを指定する必要がある。 -Input Data Segment とOut put Data SegmentがCode Segment間の依存関係を自動的に記述することになる。 +Input Data Segment とOut put Data SegmentがCode Segment間の依存関係を自動的に記述することになる。(図\ref{fig:dsandcs2}) +\begin{figure}[htbp] +\begin{center} +\includegraphics{fig/dsandcs2.pdf} +\end{center} +\caption{Input Data Segment とOut put Data SegmentがCode Segment間の依存関係を自動的に記述する} +\label{fig:dsandcs2} +\end{figure} + idsとods によりInput/Outputを選択してData Segmentを作成する。Outputにはput時(update時)にremoteかlocalか、keyを指定する。Inputの場合にはsetKeyする際にremoteかlocal、keyを指定する。 今現在はInputはsetKeyをする際に、Outputはputの際にノードとkeyを指定しているが、どの時点でノードとkeyを指定するのか、どのようなAPIを用意するべきかは、まだ議論の余地がある。 \section{Code Segmentの実行方法} -Aliceには、Start Code SegmentというCのmainに相当するような最初に実行されるCode Segmentがある。Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 +Aliceには、Start Code SegmentというCのmainに相当するような最初に実行されるCode Segmentがある。Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。(ソースコード \ref{fig:StartCodeSegment}) \section{Code Segmentの記述方法} -Code Segmentをユーザーが記述する際にはCode Segmentを継承して記述する。そのCode SegmentはInput DSMとOutput DSMを利用することができる。 +Code Segmentをユーザーが記述する際にはCode Segmentを継承して記述する。(ソースコード \ref{fig:CodeSegment})そのCode SegmentはInput DSMとOutput DSMを利用することができる。 + +\begin{table}[htbp] +\lstinputlisting[label=fig:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java} +\end{table} + +\begin{table}[htbp] +\lstinputlisting[label=fig:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java} +\end{table} Input DSMはCode Segmentのidsというフィールドを用いてアクセスする。 @@ -112,10 +190,17 @@ \section{Topology Manager} Aliceは複数のノードで構成され、相互に接続される。通信するノードは、URLにより直接指定するのではなく、TopologyManagerで管理する。 -TopologyManagerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきTopology NodeのIPアドレス、ポート番号、接続名を送りトポロジーファイルに記述されたとおりにトポロジーを作成する。 +TopologyManagerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきTopology NodeのIPアドレス、ポート番号、接続名を送りトポロジーファイルに記述されたとおりにトポロジーを作成する。(図\ref{fig:topologymanager}) Code Segment内部でRemote DSMにアクセスする場合はToplogyManagerによって指定されたノード内部だけで有効なlabel(文字列)を使う。これにより特定のURLがCode Segment内部に記述されることを防いでいる。 +\begin{figure}[htbp] +\begin{center} +\includegraphics{fig/topologymanager.pdf} +\end{center} +\caption{Topology Manager はトポロジーファイルの記述に従ってトポロジーを生成する} +\label{fig:topologymanager} +\end{figure} \subsection{Topology Manager の設定ファイルの記述方法} Topology Managerが読み込むトポロジーファイルはDOT Languageと呼ばれる言語で記述する。 @@ -125,7 +210,23 @@ テキストのみではユーザーが望む形のトポロジーかどうかを判断しにくい。ノードの数が少なければ、可能であるがノードの数が増加するに連れて困難になるが、dotコマンドを用いることでその問題を解決することができる。 dotコマンドでトポロジーファイルを画像として出力することができるので、記述したトポロジーが正しいことを可視化して判断することができる。 -クライアント間の接続にはlabelを用いて名前が割り振られている。この接続名を指定することでユーザーは他のノードのDSMにアクセスすることができる。ReceiverにsetKeyを行う際、odsでput、updateする際のmanagerKeyがlabelである。 +クライアント間の接続にはlabelを用いて名前が割り振られている。この接続名を指定することでユーザーは他のノードのDSMにアクセスすることができる。ReceiverにsetKeyを行う際、odsでput、updateする際のmanagerKeyがlabelである。(図\ref{fig:ring}) AliceのNodeを起動する際にコマンドライン引数としてTopology ManagerのIPアドレスとポート番号を指定する。main関数内でTopologyNodeのnewを行い、その際に引数として渡すだけでよい。TopologyNodeの第一引数はAliceのdeamonの設定オブジェクト、第二引数はStart Code Segmentである。このStart Code Segmentがトポロジーが完成した後に実行される。 + +\begin{table}[htbp] +\lstinputlisting[label=ring, caption=3台でリングを組んだ時の例]{source/ring.dot} +\end{table} + +\begin{figure}[htbp] +\begin{itemize} +\item {\ttfamily dot -T png ring.dot -o ring.png} +\end{itemize} + +\begin{center} +\includegraphics{fig/ring.pdf} +\end{center} +\caption{dotコマンドで作成された3台で構成されたリングのグラフ} +\label{fig:ring} +\end{figure} diff -r c874088754a4 -r 3b3b014765a2 paper/chapter3.tex --- a/paper/chapter3.tex Fri Feb 08 19:12:52 2013 +0900 +++ b/paper/chapter3.tex Wed Feb 13 17:33:02 2013 +0900 @@ -2,29 +2,55 @@ \label{chap:poordirection} AliceのAPIを見直すためには実際にAliceを用いて例題を作成するのが、適切である。この章では実際にAliceを用いて作成された例題を示す。 \section{水族館ゲーム} -Aliceは分散ネットフレームワークである。従って例題を作成するにあたってネットワークを介した例題が適切であると思われる。そこで過去にFedarated Lindaでも作成された水族館ゲームをAliceで実装した。 +Aliceは分散ネットフレームワークである。従って例題を作成するにあたってネットワークを介した例題が適切であると思われる。そこで過去にFedarated Lindaでも作成された水族館ゲームをAliceで実装した。また、Java3D版(図\ref{fig:Java3D})とは別に、新しくJava7に組み込まれたJavaFx(図\ref{fig:JavaFx})を使い水族館ゲームのJavaFx版を作成した。 水族館ゲームとは複数のclientのディスプレイを並べて使用する。アプリケーションを実行するとウインドウが表示され、複数の魚がウインドウの中を泳ぎ始める。魚は画面の端まで移動すると自分の画面上からは消え、隣のプレイヤーの画面の端から出てくる。魚のうち1匹はプレイヤーが操作することができる。トポロジーはAliceのTopologyManagerによってツリー状に構成されている。 +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=160mm]{fig/for_3D.pdf} +\end{center} +\caption{java3D版 水族館ゲーム} +\label{fig:Java3D} +\end{figure} + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=160mm]{fig/for_FX.pdf} +\end{center} +\caption{javaFX版 水族館ゲーム} +\label{fig:JavaFx} +\end{figure} + \subsection{処理の流れ} +図\ref{fig:NodeToClient}はデータの流れをコラボレーションダイアグラムで示したものである。 \begin{enumerate} \item ユーザーが魚を操作する。または、PositionController(Code Segment)により魚の座標のData SegmentであるfishPositionが更新される。 \item fishPositionが魚のオブジェクトに座標をセットするためのCode Segment であるSetLocationにreplyされる。SetLocationが実行され画面に反映される。 -\item 他のノードに更新されたfishPositionを送信するためのCode SegmenであるUpdateにfishPositionがreplyされる。 +\item 他のノードに更新されたfishPositionを送信するためのCode SegmentであるUpdateにfishPositionがreplyされる。 \item Updateに自分と接続されているノード一覧のData Segmentであるlistがreplyされる。 \item Updateはlistを参照して、fishPositionを送信する。また、fishPositionには送信元の情報が付加されているので、送信元に対してfishPositionを送り返すことはない。 \item 各clientで2 - 4 が実行され、fishPositionが全体で共有される。 +\end{enumerate} -\end{enumerate} +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=150mm]{fig/NodeToClient.pdf} +\end{center} +\caption{データの伝搬の様子} +\label{fig:NodeToClient} +\end{figure} \section{バイトニックソート} Aliceはマルチコアが現在に主流になっているという背景を踏まえて設計されている。従って並列処理に対するテストを行った。並列処理に対する例題としてバイトニックソートを実装した。 + \subsection{処理の流れ} 指定された数の乱数を生成し、Sortを行う例題である。 +また、図\ref{fig:bitonicSort}はSortされるまでの流れをコラボレーションダイアグラムで示したものである。 \begin{enumerate} \item SetTask (Code Segment)が乱数列を分割してarray1にputする。 \item replyされたDataSegmentをSort (Code Segment)で昇順に整列させる。 @@ -39,6 +65,43 @@ \item 6 - 10 を繰り返し行うことで全体がSortされる。 \end{enumerate} -\section{例題を通しての知見} -\subsection{Aliceのバグ} +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=150mm]{fig/bitonicSort.pdf} +\end{center} +\caption{Sortの様子} +\label{fig:bitonicSort} +\end{figure} + +\section{Aliceのバグ} +データを静的な型に変換する際にMessagePackの使い方が誤っていたため、PermGen Errorを引き起こしていた。 + + +peekまたはtakeで取得したData SegmentはValueオブジェクトであるため、そのままでは使うことができない。 +そのため Data Segmentの型を変換する必要がある。それを提供するAPIにasClass()というものがある。 +このAPIはユーザーが一般的なクラスを IDLのように用いてデータを表現した場合に使用し、引数として変換したいClassを指定する。(ソースコード \ref{fig:use_asClass}) + + +asClass内部のconvert(ソースコード \ref{fig:PermGenError})で実際に目的の型に変換するが、この際Message Pack のオブジェクトは渡されたClassに対してClass定義を行う。 +Class定義の情報はPermanent領域に保存される。 +同一オブジェクトであれば、一度定義を行えば次回以降変換する際に再び定義することはない。 +しかし、型変換を行うたびにMessagePackのオブジェクトをnewしていた。そのため型変換を行うたびにClassを定義を行なっていたため +Parmanent領域が減っていき、枯渇した際にエラーを引き起こしていた。現在はMessagePackのオブジェクトをSingletonパターンで記述しているためこのエラーは起きない。 + +\begin{table}[htbp] +\lstinputlisting[label=fig:use_asClass, caption=asClassの使用例]{source/AsClass.java} +\lstinputlisting[label=fig:PermGenError, caption=PermGen Errorを引き起こす]{source/PermGenError.java} +\end{table} + \subsection{注意すべき記述} +Aliceを記述する際に注意すべき記述がある。(ソースコード \ref{fig:NullPointerException}) + +Code Segmentを作成する際、コンストラクタ内でData Segmentを指定するsetKeyメソッドを呼ぶ。 +この際、setKey以降に処理を記述すると、その記述した処理が実行されない可能性がある。 + +Code Segmentは内部で必要なData Segmentの数の数えている。 +Data Segmentが取得されるたびにこの値がデクリメントされていき、0になった時にThread Poolへ送られる仕組みとなっている。 +値が0であるかを確認するのは別スレッドであるため、setKey以降に処理を記述すると、その処理が途中であってもThread Poolへ送られてしまい、nullpointerexception等のエラーが起こる可能性がある。記述自体は一般的なjavaの記述であるため一見してわかるものではない。また、データの取得にかかる時間次第で、エラーが出たり、出なかったりするので非常に厄介である。 +\begin{table}[htbp] +\lstinputlisting[label=fig:NullPointerException, caption=実行するとNullPointerExceptionを起こす]{source/NullPointerException.java} +\end{table} \ No newline at end of file diff -r c874088754a4 -r 3b3b014765a2 paper/chapter5.tex --- a/paper/chapter5.tex Fri Feb 08 19:12:52 2013 +0900 +++ b/paper/chapter5.tex Wed Feb 13 17:33:02 2013 +0900 @@ -1,3 +1,5 @@ -\chapter{まとめ} +\chapter{まとめと今後の課題} \label{chap:poordirection} + + diff -r c874088754a4 -r 3b3b014765a2 paper/thesis.tex --- a/paper/thesis.tex Fri Feb 08 19:12:52 2013 +0900 +++ b/paper/thesis.tex Wed Feb 13 17:33:02 2013 +0900 @@ -1,5 +1,7 @@ \documentclass[a4j,12pt]{jreport} -\usepackage[dvips]{graphicx} +\usepackage[dvipdfm]{graphicx} +%\usepackage[dvips]{graphicx} +\usepackage{listings,jlisting} \usepackage{mythesis} \usepackage{multirow} \usepackage{here} @@ -29,6 +31,28 @@ \pagenumbering{roman} \setcounter{page}{0} +\lstset{% + frame=single, + stringstyle={\ttfamily}, + commentstyle={\ttfamily}, + identifierstyle={\ttfamily}, + keywordstyle={\ttfamily}, + basicstyle={\ttfamily}, + breaklines=true, + xleftmargin=0zw, + xrightmargin=0zw, + framerule=.2pt, + columns=[l]{fullflexible}, + numbers=left, + stepnumber=1, + numberstyle={\scriptsize}, + numbersep=1em, + language={Java}, + tabsize=4, + lineskip=-0.5zw, + morecomment={[s][]{/**}{*/}}, +} + \tableofcontents % 目次 \listoffigures % 図目次 \listoftables % 表目次