# HG changeset patch # User sugi # Date 1422511014 -32400 # Node ID 6b470aab9a41eafd8fe39cb00350ba9c773d4d3b # Parent d2eeb833c75e1a6ca3a46edef91c58099ec03196 modify chapter1 diff -r d2eeb833c75e -r 6b470aab9a41 paper/abstract.tex --- a/paper/abstract.tex Tue Jan 27 20:38:25 2015 +0900 +++ b/paper/abstract.tex Thu Jan 29 14:56:54 2015 +0900 @@ -1,2 +1,3 @@ \begin{abstract} + \end{abstract} diff -r d2eeb833c75e -r 6b470aab9a41 paper/chapter1.org.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/chapter1.org.tex Thu Jan 29 14:56:54 2015 +0900 @@ -0,0 +1,214 @@ +\chapter{分散フレームワーク Alice の概要} \label{chapter:chapter1} +Aliceは、本研究室で開発を行っている分散タスク管理フレームワークである。Cell用のOpen CLに似たTask管理フレームワークCeriumとLindaを相互に接続した分散フレームワークであるFederated Lindaの開発を通して得られた知見が生かされている。 + +Ceriumでは、Taskを小さく分割して並列実行し、データ転送はパイプライン実行により隠される。Task間に依存関係があるが、実際にはデータの依存関係がそのままTaskの依存関係になることが多い。繰り返し使われるデータ構造の管理が重要であり、実行時にわかるデータ構造間の依存関係がTaskを複雑にしている。 + +Federated Lindaでは、Lindaサーバ内部にMeta Engineと呼ばれるLindaのタプル(データ構造)をやり取りする部分を作成した。Meta Engineでは、タプルのやり取りによって起動するcall backを使うが、call backによる記述が分散してしまい、可読性を落としてしまう。また、複数のタプルの待ち合わせが重要だが、その待ち合わせはsingle threadedなMeta Engine内部の状態に依存する。 + +これらが示しているのは、並列分散実行はコードの並列実行だけでなく、データの単位が重要だということである。そこで、AliceはData SegmentとCode 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で実装したフレームワークである。Topology Managerを持ち、Blade上での +分散プログラムの実験を容易に行うことができる。また、SEDA Architectureを採用しており、マルチコア上でのスループットの向上を期待している。 + +\section{Data Segment} +Data Segmentはデータを細かく分割したものであり、数値や文字列などのデータを構造的に保持する。AliceはData Segmentをデータベースとして扱っている。Data Segmentには必ず対になるKeyが存在する。つまりKey Value Storeとして考える事ができる。 + +Aliceのデータベースは通常のKVSとは異なっている点がある。通常のKVSはプログラミング言語の連想配列やMapと同様に 「Key（キー）」と「Value（値）」がペアとなっている。そのため1つのKeyに対して値は1つである。しかし、Aliceの場合は「Key」と「Queue」がペアとなっているため、Keyに対して複数回putできる。従って取得できるValueも複数存在できる。Key毎の追加と取得はLindaに準じた設計になっている。 + +Data SegmentはData Segment Manager（以下DSM）によって管理されている。ノード毎にLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のKVSとなっている。従ってRemote DSMを指定するKeyはノード内部でuniqueなものである。Remote DSMは他のノードのLocal DSMのproxyと考えられる。つまりRemote DSMは複数存在し、それぞれに対応するノードは異なる。 + +\begin{figure}[htbp] +\begin{center} +\includegraphics{images/remote_datasegment.pdf} +\end{center} +\caption{Remote DSMは他のノードのLocal DSMのproxy } +\label{fig:RemoteDSM} +\end{figure} + +KVSへのアクセスはqueueによって、ノード内部で逐次化される。それ以外は、すべてJavaのThread Poolにより並列実行される。 +\subsection{Data Segment API} +以下が用意されているData Segment APIである。これらを用いてデータの送受信を行う。 +\begin{itemize} +\item \verb+void put(String key, Value val)+ +\item \verb+void update(String key, Value val)+ +\item \verb+void peek(Receiver receiver, String key)+ +\item \verb+void take(Receiver receiver, String key)+ +\end{itemize} +\subsubsection{put} +putはデータをQueueに追加するためのAPIである。Lindaのout()に相当する。(図 \ref{fig:put}) +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=100mm]{images/put.pdf} +\end{center} +\caption{queueにデータを追加する} +\label{fig:put} +\end{figure} + +\subsubsection{update} +updateはデータを置き換える特急メッセージのように動作する。Lindaのupdate()に相当する。(図 \ref{fig:update}) +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=100mm]{images/update.pdf} +\end{center} +\caption{update"は先頭データを取り除き、queueにデータを追加する} +\label{fig:update} +\end{figure} + +\subsubsection{peek} +peekはデータを読み込むAPIである。読み込まれたデータはQueueに残る。要求したデータが存在しなければ、Code Segmentの待ち合わせ （Blocking）が起こる。putやupdateによりデータに更新があった場合、peekが直ちに実行される。Lindaのread()に相当する。(図 \ref{fig:peek}) + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=90mm]{images/peek.pdf} +\end{center} +\caption{peekはデータをreceiverに読み込む。希望のデータがない場合は保留する} +\label{fig:peek} +\end{figure} + +\subsubsection{take} +takeもデータを読み込むためのAPIである。peekとの違いは読み込まれたデータはQueueから削除される。Lindaのin()に相当する。(図 \ref{fig:take}) +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=70mm]{images/take.pdf} +\end{center} +\caption{"take" はデータを receiver に読み込む。その際、読み込んだデータは削除される} +\label{fig:take} +\end{figure} + +\subsection{Data Segment の表現} +Data Segmentの表現にはMessage Packを利用している。Message Packに関してJavaにおけるデータ表現は以下の3種類があり、制限を伴うが互いに変換可能である。 +\begin{itemize} +\item {\ttfamily 一般的なJavaのクラスオブジェクト} +\item {\ttfamily MessagePack for JavaのValueオブジェクト} +\item {\ttfamily byte[]で表現されたbinary} +\end{itemize} + +Data Segment APIの内部においてデータは、一般的なJavaのクラスオブジェクトまたはbyteArrayで表現されたbinaryで表現されている。 +Localからデータがputされた場合は一般的なJavaのクラスオブジェクトの状態でenqueueされる。RemoteからデータがputされるとbyteArrayで表現されたbinaryの状態でenqueueされる。 + +ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを表現することができる。 +この場合、クラス宣言時に@Messageというアノテーションをつける必要がある。もちろん、MessagePackで扱うことのできるデータのみをフィールドに入れなければならない。 + +Remoteに対してputできるデータは、@MessageをもつクラスオブジェクトかMessage Packで扱える型に限られる。 + +\section{Code Segment} +Code SegmentとはAlice上で実行されるタスクの単位である。ユーザーはCode Segmentを組み合わせることでプログラミングを行う。Code Segmentをユーザーが記述する際に、内部で使用するData Segmentの作成を記述する。入力時のData SegmentをInput Data Segment、出力時をOutput Data Segmentと呼ぶ。(図 \ref{fig:dsandcs}) + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=100mm]{images/dsandcs.pdf} +\end{center} +\caption{Code SegmentはInput Data Segment とOutput Data Segmentが存在する} +\label{fig:dsandcs} +\end{figure} + +Input Data Segment と Output Data SegmentはCode Segmentに用意されているAPIを用いて作成する。 +Input Data Segmentは、LocalかRemoteか、またkeyを指定する必要がある。Code Segmentは、記述したInput Data Segmentが全て揃うとThread poolに送られ、実行される。 + +Out Data SegmentもLocalかRemoteか、またkeyを指定する必要がある。 + +Input Data SegmentとOutput Data SegmentによってCode Segmentの間の依存関係が自動的に記述される。(図 \ref{fig:dsandcs2}) + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=110mm]{images/dsandcs2.pdf} +\end{center} +\caption{Input Data Segment とOut put Data SegmentがCode Segment間の依存関係を自動的に記述する} +\label{fig:dsandcs2} +\end{figure} +現在、Inputの場合はsetKeyを呼ぶ際、Outputはput(またはupdate)の際にノードとkeyの指定を行っている。 +しかし、どの時点でノードとkeyの指定を行えばよいか、どのようなAPIを用意するべきかは、議論の余地がある。 + +\subsection{Code Segmentの実行方法} +Alice には、Start Code Segment (ソースコード \ref{src:StartCodeSegment})というC の main に相当するような最初に実行される Code Segment がある。 +\begin{table}[html] +\lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java} +\end{table} + +Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。 +このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 + +\subsection{Code Segmentの記述方法} +Code Segmentをユーザーが記述する際にはCode Segmentを継承して記述する(ソースコード \ref{src:CodeSegment})。 +Code SegmentはInput/Output Data Segment Managerを利用することができる。 + +Input DSM はCode Segmentの{\tt ids}というフィールドを用いてアクセスする。 + +\begin{table}[html] +\lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java} +\end{table} + +\begin{itemize} +\item {\ttfamily Receiver create(CommandType type)} +\end{itemize} +createでコマンドが実行された際に取得されるData Segmentが格納される受け皿を作る。引数にはCommandTypeが取られ、指定できるCommandTypeは{\tt PEEK}または{\tt TAKE}である。 +\begin{itemize} +\item \verb+void setKey(String managerKey, String key)+ +\end{itemize} +setKeyメソッドにより、どこのData Segmentのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定することができる。 +コマンドの結果がレスポンスとして届き次第Code Segmentは実行される。 + +Output DSMはCode Segmentの{\tt ods}というフィールドを用いてアクセスする。 +Output DSMは{\tt put}または{\tt update}を実行することができる。 +\begin{itemize} +\item \verb+void put(String managerKey, String key, Object val)+ +\item \verb+void update(String managerKey, String key, Object val)+ +\end{itemize} + + +\section{Meta Data Segment} +Meta Data SegmentはData Segmentの一種である。Data Segmentは、ユーザーがput（またはupdate）したデータを管理するData Baseであるのに対して、Meta Data Segmentは、分散フレームワークAliceがputしたデータを管理するData Baseである。管理されているデータは、主にTopology Nodeの状態を表すメタデータである。ユーザーがメタデータを扱うこともできる。 + +例えば、"start"というkeyにはTopology NodeがStart Code Segmentを実行することができる状態を表す。他にも"\_CLIST"というkeyでは、利用可能なRemote Data Segmentの名前のリストが保存されている。ユーザーはリストをpeekし、putする際にリストにある名前を指定することで、動的にデータの伝搬などを行うことができる。 + +また、Input Data Segmentに付随しているものもある。Input Data SegmentはCode Segment内部でReceiverという入れ物に格納される。ユーザーは、Receiverに対して操作することでData Segmentを入手できる。 +このReceiverには、fromというフィールドがあり、このデータを誰がputしたという情報が入っている。この情報をデータの伝搬する際に利用することで、データをputしたノードに送り返すことを防ぐことができる。 + +現在のAliceでは、メタデータはデータと同じ領域にputされているため、データと同じAPIを用いて取得できる。 + +\section{Meta Code Segment} +Meta Code SegmentはAliceを構成するCode Segmentである。 + + + +Alice自身が全てCode Segmentで記述されているため、AliceをMeta Code Segmentのかたまりと考える事ができる。 + + +\section{Topology Manager} +Aliceは複数のノードで構成され、相互に接続される。通信するノードはURLにより直接指定するのではなくTopology Managerで管理する。 +Topology Managerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきTopology NodeのIPアドレス、ポート番号、接続名を送りトポロジーファイルに記述されたとおりにトポロジーを作成する。(図\ref{fig:topologymanager}) + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=70mm]{images/topologymanager.pdf} +\end{center} +\caption{Topology Manager はトポロジーファイルの記述に従ってトポロジーを生成する} +\label{fig:topologymanager} +\end{figure} + +Code Segment内部でRemote DSMにアクセスする場合はToplogyManagerによって指定されたノード内部だけで有効なlabel(文字列)を使う。これにより特定のURLがCode Segment内部に記述されることを防いでいる。 + +トポロジーファイルはグラフ構造を表現するデータ記述する言語の一種であるDOT Languageと呼ばれる言語で記述する。また、dotコマンドを用いてトポロジーファイルを可視化することができる。 + +\subsection{Topology Managerの参加表明処理} +Topology Managerへの参加表明は、Topology Node起動時にコマンドライン引数からTopology ManagerのIPアドレスとポート番号を指定すればよい。 +指定されたTopology Managerに接続を行うと、Topology Manager側のキー"hosts"に、自分自身のIPアドレスとポート番号をputする。 + +参加表明を受け取ったTopology Managerは、抽象名を参加表明したTopology Nodeのキー"host"にputする。 +その後、Topology Manager上のTopology Node名のキーに、接続すべきTopology Nodeの情報(IP アドレス、ポート番号等)を全てputする。Topology Nodeは、その情報を1つずつTakeし接続処理を行う。全ての接続処理が終わるとTopology ManagerからTopology Nodeに対してStart Code Segmentの実行命令が出され、アプリケーションが開始される。 + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=120mm]{images/topologymanagerandnode.pdf} +\end{center} +\caption{Topology ManagerとTopology Node間の通信} +\label{fig:topologymanagerandnode} +\end{figure} + +\section{Aliceによるプログラミング手法} +AliceはCode SegmentとData Segmentによってプログラミングを行なう。Code Segmentから別にCode SegmentへData Segmentを引き渡す際、コンストラクタは使わない。Code SegmentがLocal / Remote Data Segmentに対してputを行い、別のCode SegmentがLocal / Remote Data Segmentに対してpeekを行うことで引き渡される。つまり、Code Segmentは実行前後にData Segmentへ通信が行われるのである。この通信の順序がCode Segmentの実行順序を決定している。 +すなわち、Aliceによるプログラミングとは通信の管理を行うことであり、プロトコルを設計することと捉える事ができる。 diff -r d2eeb833c75e -r 6b470aab9a41 paper/chapter1.tex --- a/paper/chapter1.tex Tue Jan 27 20:38:25 2015 +0900 +++ b/paper/chapter1.tex Thu Jan 29 14:56:54 2015 +0900 @@ -33,11 +33,13 @@ \end{figure} \subsection{ComputationとMeta Computation} -Aliceのcomputationは\ref{subsection:computation}で示したように、keyで指し示されるData Segmentを待ち合わせてCode Segmentを実行させるというものである。アプリケーションを作成するためにはアルゴリズムをAliceのComputationで表現する必要がある。しかし、アプリケーションを作成するためにはAliceのComputationで表現するだけでは足りない。 +Aliceのcomputationは\ref{subsection:computation}で示したように、keyで指し示されるData Segmentを待ち合わせてCode Segmentを実行させるというものである。アプリケーションを作成するためにはアルゴリズムをAliceのComputationで表現する必要がある。 + +また、アプリケーションでAliceのComputationを設定するComputationを利用することができる。このComputationをMeta Computationと呼ぶ。 -例えば、AliceはData SegmentをDatabaseにMemory上に書き出してるが、書き出す際にMemoryが不足していた場合どうするのかといったメモリ管理の問題がある。これはアプリケーションに直接関係しているわけではないが、Aliceを動作させるために必要なcomputationである。このcomputationを設定することのできるcomputationがmeta computationである。 +例えば、Topology ManagerのMeta Computationを利用することで、2分木を３分木にするというトポロジーの変更を行うことができる。他にも再接続のMeta Computationを利用することで、切断されたノードが再びアプリケーションに参加してきた時のみ、以前の計算から再開させることができる。 -今回Aliceにmeta computationを追加した。Aliceでmeta computationを表現するので、当然Code SegmentとData Segmentで表現される +こういったMeta Computationを用いることで元のプログラムを変更することなしに動作を変更する事ができる。 \section{Aliceの実装} @@ -85,7 +87,6 @@ しかし、どの時点でノードとkeyの指定を行えばよいか、どのようなAPIを用意するべきかは、議論の余地がある。 - \subsubsection{Code Segmentの実行方法} Alice には、Start Code Segment (ソースコード \ref{src:StartCodeSegment})というC の main に相当するような最初に実行される Code Segment がある。 \begin{table}[html] @@ -161,5 +162,5 @@ \section{Aliceによるプログラミング手法} -AliceはCode SegmentとData Segmentによってプログラミングを行なう。Code Segmentから別にCode SegmentへData Segmentを引き渡す際、コンストラクタは使わない。Code SegmentがLocal / Remote Data Segmentに対してputを行い、別のCode SegmentがLocal / Remote Data Segmentに対してpeekを行うことで引き渡される。つまり、Code Segmentは実行前後にData Segmentへ通信が行われるのである。この通信の順序がCode Segmentの実行順序を決定している。 +AliceはCode SegmentとData Segmentによってプログラミングを行う。Code Segmentから別にCode SegmentへData Segmentを引き渡す際、コンストラクタは使わない。Code SegmentがLocal / Remote Data Segmentに対してputを行い、別のCode SegmentがLocal / Remote Data Segmentに対してpeekを行うことで引き渡される。つまり、Code Segmentは実行前後にデータベースへ通信が行われるのである。この通信の順序がCode Segmentの実行順序を決定している。 すなわち、Aliceによるプログラミングとは通信の管理を行うことであり、プロトコルを設計することと捉える事ができる。 diff -r d2eeb833c75e -r 6b470aab9a41 paper/chapter5.tex --- a/paper/chapter5.tex Tue Jan 27 20:38:25 2015 +0900 +++ b/paper/chapter5.tex Thu Jan 29 14:56:54 2015 +0900 @@ -4,7 +4,7 @@ \section{並列環境の改善効果の測定} 第\ref{section:conçurrent}章 の分散環境における改善効果をbitonic sortによる実験によって測定を行なう。 -\subsection{実験環境} +\subsubsection{実験環境} コア数が少ないマシンでは、同時に走るCode Segmentが少ないことから、メニコア環境で実験を行った。 \begin{table}[htbp] \caption{実行環境の詳細} @@ -23,7 +23,7 @@ \end{tabular} \end{center} \end{table} -\subsection{実験結果} +\subsubsection{実験結果} 100万の要素をもつ配列のSortにかかる時間を計測する。同時に走るCode Segmentが物理コア数と同じになるように、分割数は4個で行った。 \begin{table}[html] @@ -80,7 +80,7 @@ 実験では、トポロジーの構築時間は実験に含めてはいない。 -\subsection{実験環境} +\subsubsection{実験環境} ブレードサーバー(表 \ref{tb:blade})上の仮想マシン(表 \ref{tb:virtual})による仮想クラスタ環境を用いて実験を行った。 \begin{table}[htbp] @@ -127,7 +127,7 @@ \end{center} \end{table} -\subsection{実験結果} +\subsubsection{実験結果} \subsubsection{改善効果とFederated Lindaとの比較} データのサイズは10Bと100KBで実験を行った。10Bの結果は図\ref{fig:compare_10B}、100KBの結果は図\ref{fig:compare_100KB}である。 \begin{figure}[htbp] diff -r d2eeb833c75e -r 6b470aab9a41 paper/conclusion.tex --- a/paper/conclusion.tex Tue Jan 27 20:38:25 2015 +0900 +++ b/paper/conclusion.tex Thu Jan 29 14:56:54 2015 +0900 @@ -2,6 +2,8 @@ \section{まとめ} 今回の研究では、さまざまなアプリケーションの作成を行い、Aliceの性能的問題や不足機能を洗い出した。 + + 性能的な問題に対しては、並列と分散の両方の観点から改善を行った。その結果、実行速度を最大24\%改善した。 不足機能に関しては、洗いだした機能を実装することで、当研究室で開発しているTreeVNCをAlice上で実装できるまでになった。 diff -r d2eeb833c75e -r 6b470aab9a41 paper/introduciton.tex --- a/paper/introduciton.tex Tue Jan 27 20:38:25 2015 +0900 +++ b/paper/introduciton.tex Thu Jan 29 14:56:54 2015 +0900 @@ -8,6 +8,9 @@ そこで本研究室ではデータをData Segment、タスクをCode Segmentという単位で分割して記述する並列分散フレームワークAliceの開発を行っている。AliceはJavaで実装され、ノード間の通信のためのAPIが提供されている。また、オーバーレイネットワークを自動的に構成するTopology Managerという機能を持つため、分散プログラムのシュミレーションを行うことができる。 -本研究では、Aliceに実用的なアプリケーションを開発するために必要なmeta 機能を実 -Aliceの実行速度の問題の解決、および実用的な分散プログラムの記述に必要な機能の洗い出し実装を行う。また、実行速度の改善効果および、TreeVNCとTreeVNCをAliceを用いて実装したAliceVNCの比較をコードの観点から評価を行う。 +Aliceが分散プログラムを記述する能力を有することは確認された。だが、実用的な分散プログラムを作成するためには動的なトポロジー、つまりノードの切断や再接続に対応しなければならない。また、プログラムによっては切断や再接続等の状態に対応した処理を行いたい場合がある。 + +本研究では、Aliceに動的なトポロジーを管理構成する機能とAliceのComputationの制御を行うMeta Computationを実装した。 +プログラムにAliceの制御を行うメタプログラムを記述することにより切断や再接続の状況に応じた処理を元のコードを変更することなく再接続、切断時の処理を指定することができる。また、Aliceの実行速度の改善を並列処理と分散処理の両方の観点から行い、その改効果を計測した。さらにTreeVNCとTreeVNCをAliceを用いて実装したAliceVNCの比較をコードの観点から評価を行った。 + \section{論文の構成} diff -r d2eeb833c75e -r 6b470aab9a41 paper/judge.tex --- a/paper/judge.tex Tue Jan 27 20:38:25 2015 +0900 +++ b/paper/judge.tex Thu Jan 29 14:56:54 2015 +0900 @@ -22,7 +22,7 @@ \vspace{1cm} \underline{\hspace{6cm}印}\\ -（副\hspace{1em}査）\hspace{1em}山田 孝治 氏 +（副\hspace{1em}査）\hspace{1em}和田 知久 氏 \end{minipage} \end{flushright}