|
20
|
1 %これはちょっとマジで書きかけたものです．
|
|
|
2 %気にしないで，使ってください．
|
|
|
3 %minru
|
|
|
4
|
|
|
5 \documentclass[twocolumn, a4j, twoside]{jarticle}
|
|
|
6 \usepackage{master_proc}
|
|
|
7 %\usepackage[dvips]{graphicx}
|
|
|
8 \usepackage[dvipdfm]{graphicx}
|
|
|
9
|
|
|
10 % dvipdfm を使って PDF ファイルに日本語の栞をつける
|
|
|
11 % \usepackage[dvipdfm]{color}
|
|
|
12 % \usepackage[dvipdfm,bookmarks=true,bookmarksnumbered=true,%
|
|
|
13 % bookmarkstype=toc]{hyperref}
|
|
|
14
|
|
|
15 \jtitle{分散プログラミングモデル Federated Linda と 分散デバッグ} %和文タイトル
|
|
|
16 \etitle{Distributed Programming Model : Federated Linda and Distributed debugging}%英文タイトル
|
|
|
17 \author{渕田 良彦} %著者名
|
|
|
18 \studentid{068514D} %学籍番号
|
|
|
19 \teacher{河野 真治} %指導教官
|
|
|
20
|
|
|
21 \begin{document}
|
|
|
22 \maketitle
|
|
|
23 \section{はじめに}
|
|
|
24 並列・分散環境におけるプログラミングは、今後ますますその重要性が高まっていくと考えられる。
|
|
|
25 しかし、分散プログラム開発において、スケーラビリティを確保することは難しい。
|
|
|
26 スケーラビリティとは、参加ノードの数が小規模から大規模に変化しても性能が劣化しない
|
|
|
27 という性能基準のことを示す。
|
|
|
28 %スケーラビリティ等を確保したまま、分散プログラムを正しく記述することやデバッグ
|
|
|
29 %を行う為に、これまで多くの分散プログラミングモデルが開発されてきたが、それらは
|
|
|
30 %遂次プログラミングモデルの延長であったり、アプリケーション開発者が複雑で理解しにくい
|
|
|
31 %記述を熟知しなければならなかった。
|
|
|
32 そこで本研究室では、自然にスケールする分散プログラミン
|
|
|
33 グモデルを提供することを目的として Federated Linda を開発した。
|
|
|
34 Federated Lindaは実験的に分散アルゴリズムを実装し、そのスケーラビリティを測る
|
|
|
35 ことができる分散プログラミングモデルである。
|
|
|
36
|
|
|
37 本研究では、本研究室で開発した分散プログラミングモデル Federated Linda を用いた
|
|
|
38 分散アルゴリズムの記述事例として、Compact Routing の実装を行い、
|
|
|
39 その開発によって得られた知見から本モデルに必要な機能の拡張を提案する。
|
|
|
40 本モデルへの機能拡張としてまず最初の段階で、Federated Linda の実装をC言語から
|
|
|
41 Java言語へと移行した。その上で、分散デバッグ機能について検討を行い、
|
|
|
42 実際に分散デバッグ機能を実装する。
|
|
|
43 実装した分散デバッグ機能の評価として、Federated Linda での
|
|
|
44 分散アルゴリズムにおけるバグの特定を行い、その有用性を示す。
|
|
|
45 \section{Federated Linda}
|
|
|
46 Federated Lindaは本研究室で開発された非同期型Lindaで構築される。
|
|
|
47 非同期型Lindaは、タプルというデータ単位をネットワーク上の「タプル空間」に
|
|
|
48 出し入れする事で通信を行うLindaという通信モデルを用い、その通信を、明確な
|
|
|
49 待ちを行わない非同期的な通信によって行う。しかし、集中型の通信を行う
|
|
|
50 非同期型Lindaはスケーラビリティをもたない。そこで、複数のタプル空間を接続し、
|
|
|
51 ノード間にてタプルを中継させる分散モデルとしてFederated Lindaを提案する。
|
|
|
52 これによって、通信の集中型モデルから脱し、スケーラビリティを得る。
|
|
|
53 また、分散プログラムにおける構成要素を、３つに分離することで、各要素毎に
|
|
|
54 切り替えが可能となり、ポータビリティが向上する。
|
|
|
55
|
|
|
56 ３つに分離されるFederated Lindaの構成要素には以下の３つがある。
|
|
|
57 {\small
|
|
|
58 \begin{verbatim}
|
|
|
59 Local Access Protocol
|
|
|
60 ・'in','read','out'といったLindaのAPI、ユーザープログラ
|
|
|
61 ムからの通信、プロトコルへのアクセス
|
|
|
62 Protocol Engine
|
|
|
63 ・分散アルゴリズムを内包するエージェントプログラム、タプル
|
|
|
64 空間から別ノードのタプル空間へとタプルを転送する
|
|
|
65 Link Configuration
|
|
|
66 ・タプル空間やProtocol Engineの接続をXMLで表し、そのXML
|
|
|
67 に沿ったコネクション確立処理を行う
|
|
|
68 \end{verbatim}
|
|
|
69 }
|
|
|
70 Federated Lindaでは、玩具的に分散アルゴリズムを実装し、実験する事が可能であり、
|
|
|
71 その教育的な利用も考えられる。
|
|
|
72
|
|
|
73 \section{Compact Routingの実装と評価}
|
|
|
74 Federated Lindaにおける分散アルゴリズム、つまりProtocol Engineの実装として
|
|
|
75 Distance Vector Routingの実装が先行研究[1]によって行われた。これは、自ノードから
|
|
|
76 宛先ノードまで、距離が最短のルーティングを行う分散アルゴリズムであるが、ネットワーク
|
|
|
77 が複雑になるほど経路の情報量が増え、スケーラビリティに劣ると考えられた。よって
|
|
|
78 今回、階層型ルーティングを用いた、ルーティングテーブル収束速度や、ネットワーク
|
|
|
79 のスケーラビリティに対して優位な分散アルゴリズムである'Compact Routing'[3]の実装を
|
|
|
80 行った。
|
|
|
81
|
|
|
82 評価としてDistance Vector RoutingとCompact Routingそれぞれにおけるルーティングテーブル構築
|
|
|
83 時間の比較を行い、表\ref{routingtime}に示す結果となった。
|
|
|
84 \vspace{-7mm}
|
|
|
85 \begin{table}[htbp]
|
|
|
86 \begin{center}
|
|
|
87 \caption{ルーティングテーブル構築にかかる時間}
|
|
|
88 \label{routingtime}
|
|
|
89 {\small
|
|
|
90 \begin{tabular}{|c|c|c|}
|
|
|
91 \hline \hline
|
|
|
92 \multicolumn{3}{|c|}{Compact Routing} \\
|
|
|
93 \hline
|
|
|
94 トポロジ & ノード数 & かかった時間(sec)\\
|
|
|
95 \hline
|
|
|
96 Line & 10 & 1.19 \\
|
|
|
97 \hline
|
|
|
98 Tree & 10 & 2.40 \\
|
|
|
99 \hline
|
|
|
100 Line & 20 & 5.18 \\
|
|
|
101 \hline
|
|
|
102 Tree & 20 & 6.95 \\
|
|
|
103 \hline
|
|
|
104 Line & 30 & 7.56 \\
|
|
|
105 \hline
|
|
|
106 Tree & 30 & 26.26 \\
|
|
|
107 \hline \hline
|
|
|
108 \multicolumn{3}{|c|}{Distance Vector Routing} \\
|
|
|
109 \hline
|
|
|
110 トポロジ & ノード数 & かかった時間(sec)\\
|
|
|
111 \hline
|
|
|
112 Line & 10 & 2.66 \\
|
|
|
113 \hline
|
|
|
114 Tree & 10 & 4.54 \\
|
|
|
115 \hline
|
|
|
116 Line & 20 & 89.66 \\
|
|
|
117 \hline
|
|
|
118 Tree & 20 & 29.91 \\
|
|
|
119 \hline
|
|
|
120 Line & 30 & 8634.50 \\
|
|
|
121 \hline
|
|
|
122 Tree & 30 & 127.55 \\
|
|
|
123 \hline
|
|
|
124 \end{tabular}
|
|
|
125 }
|
|
|
126 \end{center}
|
|
|
127 \end{table}
|
|
|
128 \vspace{-8mm}
|
|
|
129
|
|
|
130 比較の結果、Distance Vector Routingではルーティングテーブル構築時間が、ノード
|
|
|
131 数の増加に対して大幅に増加する結果となったのに対し、Compact Routingでは、
|
|
|
132 階層型ルーティングを用い、ノード数の増加に対するルーティングテーブルのサイズや、
|
|
|
133 更新量を抑えることによってルーティングテーブルの構築時間が短くなる事を確認できた。
|
|
|
134 以上の結果より、Compact RoutingはDistance Vector Routingよりもスケーラビリティに
|
|
|
135 優れる分散アルゴリズムであると言える。
|
|
|
136 \vspace{-6mm}
|
|
|
137 \subsection{問題点}
|
|
|
138 今回の評価実験において、Distance Vector RoutingとCompact Routingの両実装を
|
|
|
139 格子状のメッシュ型トポロジにおいて用いた所、何らかのバグが原因と考えられる
|
|
|
140 問題点が明らかとなった。しかし、当時のFederated Lindaにおける開発環境が、多数の
|
|
|
141 ターミナルによって全プロセスを起動するテスト駆動開発であり、それらに対して逐次的
|
|
|
142 デバッグを行うことではバグ要因を特定する事は困難であった。
|
|
|
143
|
|
|
144 よって、Federated Lindaの機能を拡張し、分散プログラム開発に適した'分散デバッグ機能'を
|
|
|
145 実装することを提案し、その機能の検討と実装を行った。
|
|
|
146
|
|
|
147
|
|
|
148 \section{Java言語への移行と分散デバッグ機能の実装}
|
|
|
149 \subsection{Java言語への移行}
|
|
|
150 Federated Lindaへ分散デバッグ機能を実装する為に、これまでのC言語によるLindaサーバーや
|
|
|
151 Linda APIの実装を、Java言語での実装へ移行した。そのことにおける利点を以下に示す。
|
|
|
152 {\small
|
|
|
153 \begin{verbatim}
|
|
|
154 1. Java言語への移行において設計や仕様の見直しを行い、機能拡
|
|
|
155 張を行いやすい実装とする
|
|
|
156 2. オブジェクト指向、自動化されたリファクタリングを用いること
|
|
|
157 による開発の効率化
|
|
|
158 3. マルチプラットホームへの対応
|
|
|
159 4. デュアルスタック化によるIPv4/IPv6の同時接続に対応
|
|
|
160 \end{verbatim}
|
|
|
161 }
|
|
|
162 %\vspace{-3mm}
|
|
|
163 \subsection{分散デバッグ機能の検討}
|
|
|
164 分散環境におけるプログラムのデバッグでは、多くの場合、逐次デバッガ(gdb等)を用いた
|
|
|
165 二分法でデバッグ可能である。しかし、通信の状態が全体に依存する場合では、単体のデバッグ
|
|
|
166 では全体の正しさをデバッグできないという状況が存在する。その状況を示した図を以下に示す。
|
|
|
167 \vspace{-2mm}
|
|
|
168 \begin{figure}[htbp]
|
|
|
169 \begin{center}
|
|
|
170 \includegraphics[width=5.5cm]{fig/nonseqdeb.pdf}
|
|
|
171 \vspace{-5mm}
|
|
|
172 \caption{逐次デバッグが困難な通信の例}
|
|
|
173 \label{nonseqdeb}
|
|
|
174 \end{center}
|
|
|
175 \end{figure}
|
|
|
176 \vspace{-8mm}
|
|
|
177
|
|
|
178 図\ref{nonseqdeb}に示す様に、通信が全体に影響し、その順序に任意性が存在する場合
|
|
|
179 （分散プログラムの非決定性）、逐次型デバッガによるデバッグを用いることは出来ない。
|
|
|
180 よって、全体の通信を止めずにデバッグが行える仕組みが必要であると考える。
|
|
|
181
|
|
|
182 \subsection{通信状態のデバッグ機能}
|
|
|
183 Federated Lindaの分散デバッグ機能として、Java版Lindaサーバーの機能を拡張し、
|
|
|
184 通信状態のデバッグを、全体の通信を止める事無く行う機能を実装した。
|
|
|
185 この機能は以下の２点からなる。
|
|
|
186 \vspace{-3mm}
|
|
|
187 {\small
|
|
|
188 \begin{verbatim}
|
|
|
189 1. Federated Lindaにおける全体の通信を止める事無く、通信状
|
|
|
190 態のログを取得する機能
|
|
|
191 2. 取得したログを用いて通信状態を視覚的に表示し、ステップ実行
|
|
|
192 によって通信の状態を確認できるモニターツール
|
|
|
193 \end{verbatim}
|
|
|
194 }
|
|
|
195 \vspace{-3mm}
|
|
|
196
|
|
|
197 \section{評価}
|
|
|
198 実装した分散デバッグ機能の評価として、以前デバッグが困難であった、格子状メッシュ型トポロジ
|
|
|
199 におけるルーティングアルゴリズムのデバッグを行った。用いた実験は以下の２つである。
|
|
|
200 \vspace{-3mm}
|
|
|
201 {\small
|
|
|
202 \begin{verbatim}
|
|
|
203 ・6ノードの格子状メッシュ型トポロジにおけるDistance Vector
|
|
|
204 Routingのルーティングテーブル構築
|
|
|
205 ・6ノードの格子状メッシュ型トポロジにおけるCompact Routing
|
|
|
206 のルーティングテーブル構築
|
|
|
207 \end{verbatim}
|
|
|
208 }
|
|
|
209 \vspace{-3mm}
|
|
|
210 上記２点のFederated Lindaにおけるルーティングテーブル構築を行い、
|
|
|
211 その通信状態のログを取得した。その取得したログに対して、モニターツールを
|
|
|
212 用いた通信状態の確認よるデバッグを行い、バグ要因の特定を行う。その様子を
|
|
|
213 図\ref{exec1},図\ref{exec2}に示す。
|
|
|
214
|
|
|
215 \begin{figure}[htbp]
|
|
|
216 \begin{tabular}{cc}
|
|
|
217 \begin{minipage}{0.5\hsize}
|
|
|
218 \begin{center}
|
|
|
219 \includegraphics[width=4.25cm]{fig/debug1.pdf}
|
|
|
220 \vspace{-5mm}
|
|
|
221 \caption{トポロジ及び通信イベントの表示}
|
|
|
222 \label{exec1}
|
|
|
223 \end{center}
|
|
|
224 \end{minipage}
|
|
|
225 \begin{minipage}{0.5\hsize}
|
|
|
226 \begin{center}
|
|
|
227 \includegraphics[width=4.25cm]{fig/debug2.pdf}
|
|
|
228 \vspace{-5mm}
|
|
|
229 \caption{実行シーケンスでの転送タプル内容を表示}
|
|
|
230 \label{exec2}
|
|
|
231 \end{center}
|
|
|
232 \end{minipage}
|
|
|
233 \end{tabular}
|
|
|
234 \end{figure}
|
|
|
235
|
|
|
236 \subsection{バグ要因の発見}
|
|
|
237 通信状態ログのモニターツールを用いてデバッグを行った結果、Link Configuratetionが
|
|
|
238 正常終了していない為に、ルーティングテーブル構築時の通信量が増えているというバグ要因を特定した。
|
|
|
239
|
|
|
240 \newpage
|
|
|
241 このバグは、Distance Vector RoutingとCompact Routingの両実装に見られ、格子状のメッシュ型トポロジに
|
|
|
242 おける問題の原因となっていた。図\ref{bug}にその状況を示す。
|
|
|
243
|
|
|
244 \vspace{-2mm}
|
|
|
245 \begin{figure}[htbp]
|
|
|
246 \begin{center}
|
|
|
247 \includegraphics[width=8.5cm]{fig/bug.pdf}
|
|
|
248 \vspace{-5mm}
|
|
|
249 \caption{別経路からのLink Configuration}
|
|
|
250 \label{bug}
|
|
|
251 \end{center}
|
|
|
252 \end{figure}
|
|
|
253 \vspace{-8mm}
|
|
|
254
|
|
|
255 以上のことより、以前のFederated Linda における開発環境ではデバッグが困難な状況を、
|
|
|
256 通信状態のデバッグ機能を実装することによって解消したと評価する。
|
|
|
257
|
|
|
258 \section{他の分散プログラミングモデルとの比較}
|
|
|
259 Federated Lindaと他の分散プログラミングモデルとの比較を、Overlay Weaver, StarBEDを対象に行う、
|
|
|
260 以下にその結果を示す。
|
|
|
261 \vspace{-2mm}
|
|
|
262 \begin{figure}[htbp]
|
|
|
263 \begin{center}
|
|
|
264 \includegraphics[width=9cm]{fig/table.pdf}
|
|
|
265 \vspace{-5mm}
|
|
|
266 \caption{他の分散プログラミングモデルとの比較}
|
|
|
267 \label{table}
|
|
|
268 \end{center}
|
|
|
269 \end{figure}
|
|
|
270 \vspace{-8mm}
|
|
|
271
|
|
|
272 \section{まとめと今後の課題}
|
|
|
273 本研究では、自然にスケールする分散プログラミングモデルを実現する為、
|
|
|
274 実験的に分散アルゴリズムを実装し、スケーラビリティを測ること
|
|
|
275 ができる分散モデルとしてFederated Lindaを提案した。
|
|
|
276 Federated Lindaにおける分散アルゴリズムの実装としてCompat Routingを実装し、評価した。
|
|
|
277 また、その実装の経験から必要と分かった分散デバッグ機能について検討し、実装と評価を行った。
|
|
|
278 本研究における今後の課題としては、スナップショットを用いた分散デバッグ機能の実装が挙げられる
|
|
|
279
|
|
|
280 {\small
|
|
|
281 \begin{thebibliography}{9}
|
|
|
282 \bibitem{dinamicrouting}安村 恭一, 河野 真治,
|
|
|
283 動的ルーティングによりタプル配信を行なう分散タプルスペース Federated Linda,
|
|
|
284 日本ソフトウェア科学会第22回大会, 2005.
|
|
|
285
|
|
|
286 \bibitem{dinamicrouting_compact}渕田 良彦, 河野 真治,
|
|
|
287 連邦型タプルスペースを使ったコンパクトルーティングの実験,
|
|
|
288 情報処理学会プログラミング研究会, 2007.
|
|
|
289
|
|
|
290 \bibitem{compactrouting}L. J . Cowen,
|
|
|
291 Compact Routing with Minimum Stretch, Proc. SODA’99, pp.255-260 (1999).
|
|
|
292
|
|
|
293 \end{thebibliography}
|
|
|
294 }
|
|
|
295
|
|
|
296 \end{document}
|
