|
0
|
1 \chapter{分散フレームワーク Alice の概要} \label{chapter:chapter1}
|
|
22
|
2 この章では、Aliceの計算モデルを説明した後、実際にどのように実装されているかを説明する。
|
|
20
|
3 \section{Data SegmentとCode Segment}\label{subsection:computation}
|
|
25
|
4 AliceはデータをData Segment、（以下DS）タスクをとCode Segment（以下CS）という単位に分割してプログラミングを行う。
|
|
|
5 DSはAliceが内部にもつデータベースによって管理されている。DSに対応する一意のkeyが設定されており、そのkeyを用いてデータベースを操作する。
|
|
18
|
6
|
|
25
|
7 CSは実行に必要なDSが揃うと実行されるという性質を持つ。そして入力されたDSに応じた結果が出力される。
|
|
27
|
8 入力されるDSはInput DS、出力されるDSはOutput DSと呼ばれる(図 \ref{fig:dsandcs})。Input DSはそのCSを実行するために必要なデータであり、Output DSはCSが計算を行った後に出力されるデータである。
|
|
18
|
9
|
|
|
10
|
|
|
11 \begin{figure}[htbp]
|
|
|
12 \begin{center}
|
|
|
13 \includegraphics[width=100mm]{images/dsandcs.pdf}
|
|
|
14 \end{center}
|
|
25
|
15 \caption{CSはInput DS とOutput DSをもつ}
|
|
18
|
16 \label{fig:dsandcs}
|
|
|
17 \end{figure}
|
|
|
18
|
|
27
|
19 CSに依存するデータであると出力されるデータを記述することにより、CSが実行される順番が決定される(図 \ref{fig:dsandcs2})。データの依存関係にないCSは並列実行が可能であるため、並列度を上げるためにはCSの処理内容を細かく分割して依存するデータを少なくするのが望ましい。
|
|
18
|
20
|
|
|
21
|
|
|
22 \begin{figure}[htbp]
|
|
|
23 \begin{center}
|
|
|
24 \includegraphics[width=110mm]{images/dsandcs2.pdf}
|
|
|
25 \end{center}
|
|
25
|
26 \caption{Input DS とOut put DSがCS間の依存関係を自動的に記述する}
|
|
18
|
27 \label{fig:dsandcs2}
|
|
|
28 \end{figure}
|
|
|
29
|
|
20
|
30 \section{ComputationとMeta Computation}
|
|
28
|
31 AliceのComputationは、keyで指し示されるDSを待ち合わせてCSを実行させると定義できる。
|
|
|
32 それに対して、AliceのMeta Computationは、AliceのComputationを支えているComputationのプログラミングと定義できる。
|
|
19
|
33
|
|
28
|
34 例えば、トポロジーを指定するAPIはMeta Computationである。Aliceが動作するためにはトポロジーを決める必要がある。つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。トポロジーが決定するとそのトポロジーを構成する計算が行われる。トポロジーを指定するAPIはその構成の計算をプログラミングして変更するものである。
|
|
|
35 他にも再接続の動作を決めるAPIや切断時の動作を決めるAPIはMeta Computationである。
|
|
|
36
|
|
|
37 これらのMeta ComputationがAliceのComputationに影響することはない。プログラマーはCSを記述する際にトポロジーや切断、再接続という状況を予め想定した処理にする必要はない。プログラマーは目的の処理だけ記述する。そして、切断や再接続が起こった場合の処理を記述しMeta Computationで指定する。
|
|
|
38 このようにプログラムすることで、通常処理と例外処理を分離することができるため、シンプルなプログラムを記述できる。
|
|
18
|
39
|
|
25
|
40 \section{Data Segment}
|
|
|
41 複数のスレッドから１つのデータに変更を行うためには、データの不整合を防ぐためのlockが必要になる。
|
|
|
42 複数の関係のない要素を１つのデータオブジェクトで表現した場合、全ての操作でlockが必要になる。
|
|
|
43 このlockがスケラビリティーを低下させる。つまりデータのサイズも並列計算には重要である。
|
|
|
44
|
|
|
45 Aliceはデータを細かく分割して記述する。その細かく分割されたデータをDSと呼ぶ。
|
|
26
|
46 実際には特定のオブジェクトにマッピングされ、マッピングされたクラスを通してアクセスされる。
|
|
25
|
47
|
|
26
|
48 \section{Data Segment Manager}
|
|
|
49 DSは実際にはqueueに保存される。queueには対になるkeyが存在し、keyの数だけqueueが存在する。
|
|
|
50 このkeyを指定してDSの保存、取得を行う。
|
|
|
51 queueの集合体はデータベースとして捉えられる。
|
|
25
|
52 このデータベースをAliceではDS Manager（以下DSM）と呼ぶ。
|
|
26
|
53 DSMにはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。
|
|
|
54 Remote DSMは他のノードのLocal DSMであり、接続しているノードの数だけ存在する。（図\ref{fig:RemoteDSM}）
|
|
|
55 Remote DSMにも対になるkeyが存在し、そのkeyを指定して利用する。
|
|
|
56 Local DSMへのアクセスはノード内部で逐次化される。
|
|
18
|
57
|
|
|
58 \begin{figure}[htbp]
|
|
|
59 \begin{center}
|
|
26
|
60 \includegraphics[width=100mm]{images/remote_datasegment.pdf}
|
|
18
|
61 \end{center}
|
|
26
|
62 \caption{Remote DSMは他のノードのLocal DSMのproxy }
|
|
18
|
63 \label{fig:RemoteDSM}
|
|
|
64 \end{figure}
|
|
|
65
|
|
25
|
66
|
|
|
67 \section{Data Segment API}
|
|
|
68 以下のData Segment APIを用いてデータベースにアクセスする。
|
|
|
69 \begin{itemize}
|
|
|
70 \item \verb+void put(String key, Object val)+
|
|
|
71 \item \verb+void update(String key, Object val)+
|
|
|
72 \item \verb+void peek(String key)+
|
|
|
73 \item \verb+void take(String key)+
|
|
|
74 \end{itemize}
|
|
|
75 putとupdateはDSを追加する際に、peekとtakeはDSを取得する際に使用する。
|
|
|
76
|
|
|
77 \subsubsection{put}
|
|
26
|
78 DSをqueueに追加するためのAPIである。第一引数に対応するqueueに対してDSを追加している。
|
|
25
|
79 \subsubsection{update}
|
|
26
|
80 updateもqueueに追加するためのAPIである。putとの違いは、先頭のDSを削除してからDSを追加することである。そのためAPI実行前後でqueueの中にあるDSの個数は変わらない。
|
|
25
|
81
|
|
|
82 \subsubsection{take}
|
|
26
|
83 takeはDSを読み込むためのAPIである。読み込まれたDSは削除される。要求したDSが存在しなければ、CSの待ち合わせ （Blocking）が起こる。putやupdateによりDSに更新があった場合、takeが直ちに実行される。
|
|
25
|
84
|
|
|
85 \subsubsection{peek}
|
|
26
|
86 peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。
|
|
25
|
87
|
|
|
88 DSの表現にはMessage Packを利用している。Message Packに関してJavaにおけるデータ表現は以下の3種類があり、制限を伴うが互いに変換可能である。
|
|
18
|
89 \begin{itemize}
|
|
|
90 \item {\ttfamily 一般的なJavaのクラスオブジェクト}
|
|
|
91 \item {\ttfamily MessagePack for JavaのValueオブジェクト}
|
|
|
92 \item {\ttfamily byte[]で表現されたbinary}
|
|
|
93 \end{itemize}
|
|
|
94
|
|
25
|
95 DS APIの内部においてデータは、一般的なJavaのクラスオブジェクトまたはbyteArrayで表現されたbinaryで表現されている。
|
|
23
|
96 Localからデータがputされた場合は一般的なJavaのクラスオブジェクトの状態でenQueueされる。RemoteからデータがputされるとbyteArrayで表現されたbinaryの状態でenQueueされる。
|
|
18
|
97
|
|
|
98 ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを表現することができる。
|
|
|
99 この場合、クラス宣言時に@Messageというアノテーションをつける必要がある。もちろん、MessagePackで扱うことのできるデータのみをフィールドに入れなければならない。
|
|
|
100
|
|
|
101 Remoteに対してputできるデータは、@MessageをもつクラスオブジェクトかMessage Packで扱える型に限られる。
|
|
17
|
102
|
|
25
|
103 \section{Code Segment}
|
|
|
104 Alice上で実行されるタスクの単位がCSである。ユーザーはCSを組み合わせることでプログラミングを行う。CSをユーザーが記述する際に、内部で使用するDSの作成を記述する。
|
|
23
|
105
|
|
25
|
106 Input DS と Output DSはCSに用意されているAPIを用いて作成する。
|
|
|
107 Input DSは、LocalかRemoteか、またkeyを指定する必要がある。CSは、記述したInput DSが全て揃うとThread poolに送られ、実行される。
|
|
23
|
108
|
|
25
|
109 Output DSもLocalかRemoteか、またkeyを指定する必要がある。
|
|
18
|
110 Inputの場合はsetKeyを呼ぶ際、Outputの場合はput(またはupdate)の際にノードとkeyの指定を行っている。
|
|
|
111 しかし、どの時点でノードとkeyの指定を行えばよいか、どのようなAPIを用意するべきかは、議論の余地がある。
|
|
|
112
|
|
26
|
113 \section{Code Segmentの記述方法}
|
|
|
114 CSをユーザーが記述する際にはCSを継承して記述する(ソースコード \ref{src:StartCodeSegment} ,\ref{src:CodeSegment})。
|
|
|
115 継承することによりCode Segmentで使用するAPIを利用する事ができる。
|
|
18
|
116
|
|
|
117 \begin{table}[html]
|
|
|
118 \lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java}
|
|
26
|
119 \lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java}
|
|
18
|
120 \end{table}
|
|
|
121
|
|
26
|
122 Alice には、Start CS (ソースコード \ref{src:StartCodeSegment})というC の main に相当するような最初に実行される CS がある。
|
|
25
|
123 Start CSはどのDSにも依存しない。つまりInput DSを持たない。
|
|
|
124 このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。
|
|
18
|
125
|
|
26
|
126 ソースコード \ref{src:StartCodeSegment}は、5行目で次に実行させたいCS（ソースコード \ref{src:CodeSegment}）を作成している。8行目でOutput DSMを通してLocal DSMに対してDSをputしている。
|
|
25
|
127 Output DSMはCSの{\tt ods}というフィールドを用いてアクセスする。
|
|
26
|
128 Output DSMは{\tt put}と{\tt update}を実行することができる。
|
|
18
|
129 \begin{itemize}
|
|
|
130 \item \verb+void put(String managerKey, String key, Object val)+
|
|
|
131 \item \verb+void update(String managerKey, String key, Object val)+
|
|
|
132 \end{itemize}
|
|
26
|
133 TestCodeSegmentはこの"cnt"というkeyに対して依存関係があり、8行目でupdateが行われるとTestCodeSegmentは実行される。
|
|
18
|
134
|
|
26
|
135 ソースコード\ref{src:CodeSegment}は、0から10までインクリメントする例題である。
|
|
|
136 2行目で取得されたDSが格納される受け皿を作る。Input DSMがもつcreateメソッド使うことで作成できる。
|
|
|
137 \begin{itemize}
|
|
|
138 \item {\ttfamily Receiver create(CommandType type)}
|
|
|
139 \end{itemize}
|
|
|
140
|
|
|
141 引数にはCommandTypeが取られ、指定できるCommandTypeは{\tt PEEK}または{\tt TAKE}である。
|
|
|
142 Input DSM はCSの{\tt ids}というフィールドを用いてアクセスする。
|
|
|
143
|
|
|
144 4行目から6行目はコンストラクタである。コンストラクタはオブジェクト指向のプログラミング言語で新たなオブジェクトを生成する際に呼び出されて内容の初期化を行う関数である。
|
|
|
145
|
|
|
146 TestCodeSegmentのコンストラクタが呼ばれた際には、
|
|
|
147 \begin{enumerate}
|
|
|
148 \item TestCodeSegmentが持つフィールド変数Receiver input1の定義が行われる。
|
|
|
149 \item 次にCSのコンストラクタが呼ばれ、CSが持つフィールド変数の定義と初期化が行われる。
|
|
|
150 \item {\tt ids.create(CommandType.TAKE)}が行われ、input1の初期化が行われる。
|
|
|
151 \item 最後にTestCodeSegmentのコンストラクタの5行目が実行される。
|
|
|
152 \end{enumerate}
|
|
|
153
|
|
|
154 5行目はInput DSMがもつsetKeyメソッドによりLocal DSMからDSを取得している。
|
|
|
155 \begin{itemize}
|
|
|
156 \item \verb+void setKey(String managerKey, String key)+
|
|
|
157 \end{itemize}
|
|
|
158 setKeyメソッドにより、どのDSMのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定できる。コマンドの結果がレスポンスとして届き次第CSは実行される。
|
|
|
159
|
|
|
160 runメソッドの内容としては10行目で取得されたDSをInteger型に変換してcountに代入している。
|
|
|
161 16行目で もう一度TestCodeSegmentのCSが作られる。
|
|
|
162 17行目でcountの値をインクリメントしてLocal DSMに値を追加する。
|
|
|
163 13行目が終了条件であり、countの値が10になれば終了する。
|
|
22
|
164
|
|
25
|
165 \section{Meta Data Segment}
|
|
|
166 DSは、アプリケーションに管理されているデータのことである。アプリケーションを構成するCSによってその値は変更される。
|
|
|
167 それに対してMeta DSは、分散フレームワークAliceが管理しているデータである。Aliceを構成するCSによってのみ、その値は変更される。一部のMeta DSはアプリケーションに利用することができる。
|
|
22
|
168
|
|
25
|
169 例えば、"start"というkeyでは、ノードがStart CSを実行可能かどうかの状態を表す。他にも"\_CLIST"というkeyでは、利用可能なRemote DSの一覧が管理されている。ユーザーはこの一覧にある名前を指定することで、動的にDSの伝搬などを行うことができる。
|
|
22
|
170
|
|
25
|
171 また、Input DSに付随しているものもある。Input DSはCS内部でReceiverという入れ物に格納される。ユーザーは、Receiverに対して操作することでDSを入手できる。
|
|
|
172 このReceiverには、fromというフィールドがあり、このDSを誰がputしたという情報が入っている。この情報をデータの伝搬する際に利用することで、DSをputしたノードに送り返すことを防ぐことができる。
|
|
18
|
173
|
|
25
|
174 Meta DSはDS同様にDS APIを用いて取得できる。
|
|
22
|
175
|
|
25
|
176 \section{Meta Code Segment}
|
|
|
177 CSはアプリケーションを動作させるために必要なタスクであり、ユーザーによって定義される。
|
|
|
178 それに対してMeta CSはAliceを構成するタスクである。つまりMeta CSの群はAliceのComputationと言い換えることができる。一部のみユーザーが定義をすることができ、Aliceの挙動を変更することができる。
|
|
|
179
|
|
|
180 \section{Topology Manager}
|
|
26
|
181 Aliceにおけるノードの管理は全てTopology Managerで管理される。Topology Managerの詳細は付録で示す。
|
