Mercurial > hg > Papers > 2015 > sugi-master

comparison paper/chapter1.tex @ 17:675939a7f983

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
change experiment picture
author sugi
date Fri, 23 Jan 2015 16:43:48 +0900
parents 930eae4e8aeb
children d2eeb833c75e
comparison
equal deleted inserted replaced
16:8e0b26d962cc 17:675939a7f983
1 \chapter{分散フレームワーク Alice の概要} \label{chapter:chapter1} 1 \chapter{分散フレームワーク Alice の概要} \label{chapter:chapter1}
2 Aliceは、本研究室で開発を行っている分散タスク管理フレームワークである。Cell用のOpen CLに似たTask管理フレームワークCeriumとLindaを相互に接続した分散フレームワークであるFederated Lindaの開発を通して得られた知見が生かされている。
3 2
4 Ceriumでは、Taskを小さく分割して並列実行し、データ転送はパイプライン実行により隠される。Task間に依存関係があるが、実際にはデータの依存関係がそのままTaskの依存関係になることが多い。繰り返し使われるデータ構造の管理が重要であり、実行時にわかるデータ構造間の依存関係がTaskを複雑にしている。 3 \section{Aliceの計算モデル}
5 4 \subsection{Data SegmentとCode Segment}
6 Federated Lindaでは、Lindaサーバ内部にMeta Engineと呼ばれるLindaのタプル(データ構造)をやり取りする部分を作成した。Meta Engineでは、タプルのやり取りによって起動するcall backを使うが、call backによる記述が分散してしまい、可読性を落としてしまう。また、複数のタプルの待ち合わせが重要だが、その待ち合わせはsingle threadedなMeta Engine内部の状態に依存する。 5 \subsection{computationとmeta computation}
7
8 これらが示しているのは、並列分散実行はコードの並列実行だけでなく、データの単位が重要だということである。そこで、AliceはData SegmentとCode Segmentという単位でデータと処理を細かく分割し、それぞれの依存関係を記述して分散プログラムを作成する。
9
10 Data SegmentはCode Segmentと分離されたデータ構造であり、オブジェクトではない。オブジェクト指向プログラミングが状態を複雑に持ち、並列実行や分散実行に向かないことは徐々に理解されてきている。一方で、状態自体は有限状態遷移機械(Finite State Machine/FSM)で記述するのが自然である。Code Segmentは状態遷移記述そのものであり、その状態遷移はData Segmentの到着によってトリガーされる。
11
12 カプセル化されたデータをプロセスがやり取りするのは、DFD(Data Flow Diagram)の古典的な手法であり、それ自体は新しくはない。むしろ、メインフレーム上でのソフトウェア開発に良く使われてきた手法である。Alice では、それを再実装する。
13
14 AliceはCode SegmentとData SegmentをJavaとMessage Packで実装したフレームワークである。Topology Managerを持ち、Blade上での
15 分散プログラムの実験を容易に行うことができる。また、SEDA Architectureを採用しており、マルチコア上でのスループットの向上を期待している。
16
17 \section{Data Segment}
18 Data Segmentはデータを細かく分割したものであり、数値や文字列などのデータを構造的に保持する。AliceはData Segmentをデータベースとして扱っている。Data Segmentには必ず対になるKeyが存在する。つまりKey Value Storeとして考える事ができる。
19
20 Aliceのデータベースは通常のKVSとは異なっている点がある。通常のKVSはプログラミング言語の連想配列やMapと同様に 「Key（キー）」と「Value（値）」がペアとなっている。そのため1つのKeyに対して値は1つである。しかし、Aliceの場合は「Key」と「Queue」がペアとなっているため、Keyに対して複数回putできる。従って取得できるValueも複数存在できる。Key毎の追加と取得はLindaに準じた設計になっている。
21
22 Data SegmentはData Segment Manager（以下DSM）によって管理されている。ノード毎にLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のKVSとなっている。従ってRemote DSMを指定するKeyはノード内部でuniqueなものである。Remote DSMは他のノードのLocal DSMのproxyと考えられる。つまりRemote DSMは複数存在し、それぞれに対応するノードは異なる。
23
24 \begin{figure}[htbp]
25 \begin{center}
26 \includegraphics{images/remote_datasegment.pdf}
27 \end{center}
28 \caption{Remote DSMは他のノードのLocal DSMのproxy }
29 \label{fig:RemoteDSM}
30 \end{figure}
31
32 KVSへのアクセスはqueueによって、ノード内部で逐次化される。それ以外は、すべてJavaのThread Poolにより並列実行される。
33 \subsection{Data Segment API}
34 以下が用意されているData Segment APIである。これらを用いてデータの送受信を行う。
35 \begin{itemize}
36 \item \verb+void put(String key, Value val)+
37 \item \verb+void update(String key, Value val)+
38 \item \verb+void peek(Receiver receiver, String key)+
39 \item \verb+void take(Receiver receiver, String key)+
40 \end{itemize}
41 6
42 7
8 \subsection{Data Segment API}
9
43 \subsection{Data Segment の表現} 10 \subsection{Data Segment の表現}
44 Data Segmentの表現にはMessage Packを利用している。Message Packに関してJavaにおけるデータ表現は以下の3種類があり、制限を伴うが互いに変換可能である。
45 \begin{itemize}
46 \item {\ttfamily 一般的なJavaのクラスオブジェクト}
47 \item {\ttfamily MessagePack for JavaのValueオブジェクト}
48 \item {\ttfamily byte[]で表現されたbinary}
49 \end{itemize}
50 11
51 Data Segment APIの内部においてデータは、一般的なJavaのクラスオブジェクトまたはbyteArrayで表現されたbinaryで表現されている。 12 \section{Aliceの実装}
52 Localからデータがputされた場合は一般的なJavaのクラスオブジェクトの状態でenqueueされる。RemoteからデータがputされるとbyteArrayで表現されたbinaryの状態でenqueueされる。 13 \subsection{Code Segment}
53 14 \subsubsection{Code Segmentの実行方法}
54 ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを表現することができる。 15 \subsubsection{Code Segmentの記述方法}
55 この場合、クラス宣言時に@Messageというアノテーションをつける必要がある。もちろん、MessagePackで扱うことのできるデータのみをフィールドに入れなければならない。 16 \subsection{Meta Data Segment}
56 17 \subsection{Meta Code Segment}
57 Remoteに対してputできるデータは、@MessageをもつクラスオブジェクトかMessage Packで扱える型に限られる。 18 \subsection{Topology Manager}
58
59 \section{Code Segment}
60 Code SegmentとはAlice上で実行されるタスクの単位である。ユーザーはCode Segmentを組み合わせることでプログラミングを行う。Code Segmentをユーザーが記述する際に、内部で使用するData Segmentの作成を記述する。入力時のData SegmentをInput Data Segment、出力時をOutput Data Segmentと呼ぶ。(図 \ref{fig:dsandcs})
61
62 \begin{figure}[htbp]
63 \begin{center}
64 \includegraphics[width=100mm]{images/dsandcs.pdf}
65 \end{center}
66 \caption{Code SegmentはInput Data Segment とOutput Data Segmentが存在する}
67 \label{fig:dsandcs}
68 \end{figure}
69
70 Input Data Segment と Output Data SegmentはCode Segmentに用意されているAPIを用いて作成する。
71 Input Data Segmentは、LocalかRemoteか、またkeyを指定する必要がある。Code Segmentは、記述したInput Data Segmentが全て揃うとThread poolに送られ、実行される。
72
73 Out Data SegmentもLocalかRemoteか、またkeyを指定する必要がある。
74
75 Input Data SegmentとOutput Data SegmentによってCode Segmentの間の依存関係が自動的に記述される。(図 \ref{fig:dsandcs2})
76
77 \begin{figure}[htbp]
78 \begin{center}
79 \includegraphics[width=110mm]{images/dsandcs2.pdf}
80 \end{center}
81 \caption{Input Data Segment とOut put Data SegmentがCode Segment間の依存関係を自動的に記述する}
82 \label{fig:dsandcs2}
83 \end{figure}
84 現在、Inputの場合はsetKeyを呼ぶ際、Outputはput(またはupdate)の際にノードとkeyの指定を行っている。
85 しかし、どの時点でノードとkeyの指定を行えばよいか、どのようなAPIを用意するべきかは、議論の余地がある。
86
87 \subsection{Code Segmentの実行方法}
88 Alice には、Start Code Segment (ソースコード \ref{src:StartCodeSegment})というC の main に相当するような最初に実行される Code Segment がある。
89 \begin{table}[html]
90 \lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java}
91 \end{table}
92
93 Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。
94 このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。
95
96 \subsection{Code Segmentの記述方法}
97 Code Segmentをユーザーが記述する際にはCode Segmentを継承して記述する(ソースコード \ref{src:CodeSegment})。
98 Code SegmentはInput/Output Data Segment Managerを利用することができる。
99
100 Input DSM はCode Segmentの{\tt ids}というフィールドを用いてアクセスする。
101
102 \begin{table}[html]
103 \lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java}
104 \end{table}
105
106 \begin{itemize}
107 \item {\ttfamily Receiver create(CommandType type)}
108 \end{itemize}
109 createでコマンドが実行された際に取得されるData Segmentが格納される受け皿を作る。引数にはCommandTypeが取られ、指定できるCommandTypeは{\tt PEEK}または{\tt TAKE}である。
110 \begin{itemize}
111 \item \verb+void setKey(String managerKey, String key)+
112 \end{itemize}
113 setKeyメソッドにより、どこのData Segmentのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定することができる。
114 コマンドの結果がレスポンスとして届き次第Code Segmentは実行される。
115
116 Output DSMはCode Segmentの{\tt ods}というフィールドを用いてアクセスする。
117 Output DSMは{\tt put}または{\tt update}を実行することができる。
118 \begin{itemize}
119 \item \verb+void put(String managerKey, String key, Object val)+
120 \item \verb+void update(String managerKey, String key, Object val)+
121 \end{itemize}
122
123
124 \section{Meta Data Segment}
125 Meta Data SegmentはData Segmentの一種である。Data Segmentは、ユーザーがput（またはupdate）したデータを管理するData Baseであるのに対して、Meta Data Segmentは、分散フレームワークAliceがputしたデータを管理するData Baseである。管理されているデータは、主にTopology Nodeの状態を表すメタデータである。ユーザーがメタデータを扱うこともできる。
126
127 例えば、"start"というkeyにはTopology NodeがStart Code Segmentを実行することができる状態を表す。他にも"\_CLIST"というkeyでは、利用可能なRemote Data Segmentの名前のリストが保存されている。ユーザーはリストをpeekし、putする際にリストにある名前を指定することで、動的にデータの伝搬などを行うことができる。
128
129 また、Input Data Segmentに付随しているものもある。Input Data SegmentはCode Segment内部でReceiverという入れ物に格納される。ユーザーは、Receiverに対して操作することでData Segmentを入手できる。
130 このReceiverには、fromというフィールドがあり、このデータを誰がputしたという情報が入っている。この情報をデータの伝搬する際に利用することで、データをputしたノードに送り返すことを防ぐことができる。
131
132 現在のAliceでは、メタデータはデータと同じ領域にputされているため、データと同じAPIを用いて取得できる。
133
134 \section{Meta Code Segment}
135 Meta Code SegmentはAliceを構成するCode Segmentである。
136
137
138
139 Alice自身が全てCode Segmentで記述されているため、AliceをMeta Code Segmentのかたまりと考える事ができる。
140
141
142 \section{Topology Manager}
143 Aliceは複数のノードで構成され、相互に接続される。通信するノードはURLにより直接指定するのではなくTopology Managerで管理する。 19 Aliceは複数のノードで構成され、相互に接続される。通信するノードはURLにより直接指定するのではなくTopology Managerで管理する。
144 Topology Managerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきTopology NodeのIPアドレス、ポート番号、接続名を送りトポロジーファイルに記述されたとおりにトポロジーを作成する。(図\ref{fig:topologymanager}) 20 Topology Managerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきTopology NodeのIPアドレス、ポート番号、接続名を送りトポロジーファイルに記述されたとおりにトポロジーを作成する。(図\ref{fig:topologymanager})
145 21
146 \begin{figure}[htbp] 22 \begin{figure}[htbp]
147 \begin{center} 23 \begin{center}
153 29
154 Code Segment内部でRemote DSMにアクセスする場合はToplogyManagerによって指定されたノード内部だけで有効なlabel(文字列)を使う。これにより特定のURLがCode Segment内部に記述されることを防いでいる。 30 Code Segment内部でRemote DSMにアクセスする場合はToplogyManagerによって指定されたノード内部だけで有効なlabel(文字列)を使う。これにより特定のURLがCode Segment内部に記述されることを防いでいる。
155 31
156 トポロジーファイルはグラフ構造を表現するデータ記述する言語の一種であるDOT Languageと呼ばれる言語で記述する。また、dotコマンドを用いてトポロジーファイルを可視化することができる。 32 トポロジーファイルはグラフ構造を表現するデータ記述する言語の一種であるDOT Languageと呼ばれる言語で記述する。また、dotコマンドを用いてトポロジーファイルを可視化することができる。
157 33
158 \subsection{Topology Managerの参加表明処理} 34 \subsubsection{Topology Managerの参加表明処理}
159 Topology Managerへの参加表明は、Topology Node起動時にコマンドライン引数からTopology ManagerのIPアドレスとポート番号を指定すればよい。 35 Topology Managerへの参加表明は、Topology Node起動時にコマンドライン引数からTopology ManagerのIPアドレスとポート番号を指定すればよい。
160 指定されたTopology Managerに接続を行うと、Topology Manager側のキー"hosts"に、自分自身のIPアドレスとポート番号をputする。 36 指定されたTopology Managerに接続を行うと、Topology Manager側のキー"hosts"に、自分自身のIPアドレスとポート番号をputする。
161 37
162 参加表明を受け取ったTopology Managerは、抽象名を参加表明したTopology Nodeのキー"host"にputする。 38 参加表明を受け取ったTopology Managerは、抽象名を参加表明したTopology Nodeのキー"host"にputする。
163 その後、Topology Manager上のTopology Node名のキーに、接続すべきTopology Nodeの情報(IP アドレス、ポート番号等)を全てputする。Topology Nodeは、その情報を1つずつTakeし接続処理を行う。全ての接続処理が終わるとTopology ManagerからTopology Nodeに対してStart Code Segmentの実行命令が出され、アプリケーションが開始される。 39 その後、Topology Manager上のTopology Node名のキーに、接続すべきTopology Nodeの情報(IP アドレス、ポート番号等)を全てputする。Topology Nodeは、その情報を1つずつTakeし接続処理を行う。全ての接続処理が終わるとTopology ManagerからTopology Nodeに対してStart Code Segmentの実行命令が出され、アプリケーションが開始される。
168 \end{center} 44 \end{center}
169 \caption{Topology ManagerとTopology Node間の通信} 45 \caption{Topology ManagerとTopology Node間の通信}
170 \label{fig:topologymanagerandnode} 46 \label{fig:topologymanagerandnode}
171 \end{figure} 47 \end{figure}
172 48
173 \section{Aliceによるプログラミング手法} 49
50 \subsection{Aliceによるプログラミング手法}
174 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の実行順序を決定している。 51 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の実行順序を決定している。
175 すなわち、Aliceによるプログラミングとは通信の管理を行うことであり、プロトコルを設計することと捉える事ができる。 52 すなわち、Aliceによるプログラミングとは通信の管理を行うことであり、プロトコルを設計することと捉える事ができる。