Mercurial > hg > Papers > 2008 > fuchita-master

comparison handout/handout.tex @ 0:420c2d37b2bf

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial revision
author fuchita
date Tue, 12 Feb 2008 17:18:57 +0900
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:420c2d37b2bf
1 %これはちょっとマジで書きかけたものです．
2 %気にしないで，使ってください．
3 %minru
4
5 \documentclass[twocolumn, a4j, twoside]{jarticle}
6 \usepackage{master_proc}
7 \usepackage[dvips]{graphicx}
8
9 % dvipdfm を使って PDF ファイルに日本語の栞をつける
10 % \usepackage[dvipdfm]{color}
11 % \usepackage[dvipdfm,bookmarks=true,bookmarksnumbered=true,%
12 % bookmarkstype=toc]{hyperref}
13
14 \jtitle{分散プログラミングモデル : Federated Linda} %和文タイトル
15 \etitle{Distributed Programming Model : Federated Linda} %英文タイトル
16 \author{安村 恭一} %著者名
17 \studentid{048545E} %学籍番号
18 \teacher{河野 真治} %指導教官
19
20 \begin{document}
21 \maketitle
22 \section{はじめに}
23 比較的ネットワーク的に遠いコンピュータを取り扱う分散プログラムはスケーラ
24 ブルに書くことが難しいとされている。一方、遂次プログラムなどは構造型やオ
25 ブジェクト指向などにより、難しさが緩和されており、自然に逐次プログラムを
26 書くことができる。これまでの分散フレームワークやツール群は、逐次プログラ
27 ミングモデルの延長だったりスケーラブルに書くには複雑で理解しづらいもので
28 あり、真の分散プログラミングモデルとはいえない。分散プログラムには自然に
29 スケーラブルな分散プログラムを書くことができる真の分散プログラミングモデ
30 ルが必要である。
31
32 本研究の目的は、スケーラブルな分散プログラムを自然に記述できる、真の分散
33 プログラミングモデルを提供することである。本論文では、本研究室で開発した
34 非同期型 Linda の拡張を用いて、分散プログラミングモデル Federated Linda
35 を提案する。
36
37 \section{分散プログラム}
38
39 分散プログラムが難しいのは、それをスケーラブルにすることが難しいからであ
40 る。実際、Internet 上でも、集中サーバ構成が通常であり、きちんとスケール
41 する分散アプリケーションは珍しい。しかし、DNSのように大規模の対象のサー
42 ビスもあることから、きちんと分散アプリケーションを作ることができればイン
43 ターネットのような大規模な対象のサービスも実現可能といえる。
44
45 自然な分散プログラミングを目指すためには、以下のようなことが要請される。
46 {\small
47 \begin{verbatim}
48 ・ 実際の通信のモデルが理解しやすい
49 ・ Basic のように会話的に開発できる
50 ・ 基本オペレーションが少なく、明解である
51 ・ 分散環境での運用が容易
52 ・ インターネット環境で自動的に相互接続する
53 \end{verbatim}
54 }
55 自然に書いて、スケールする分散プログラムになることが目標である。そのため
56 には分散アルゴリズム自体を内蔵するようなプログラミングモデルが望ましい。
57
58 \subsection{Linda}
59
60 本論文で提供するFederated Lindaのベースとなった分散システムLinda につい
61 て説明する。Linda はタプルというIDで番号づけられたデータの塊を
62 \tt{in,read,out}などのオペレーションを用いて、共有されたタプル空間に出し
63 入れすることで分散プログラムを行う(図\ref{originallinda}参照)。Linda の
64 利点として通信モデルが理解しやすいことが挙げられる。また、接続切断に強い
65 モデルである。しかし、集中型になりやすいモデルである。
66
67 \begin{figure}[hbp]
68 \begin{center}
69 \includegraphics[width=3cm]{fig/original-linda.eps}
70 \caption{Linda Server}
71 \label{originallinda}
72 \end{center}
73 \end{figure}
74
75 \subsection{分散プログラムの要素}
76
77 分散プログラムには三つの要素で構成される。Protocol Engine,Local access
78 to protocol, Link configuration である。
79 Protocol Engine はプロトコルを定義している要素である。Local Access to
80 protocolは直接通信にアクセスするAPIである。Link Configurationは論理的な
81 接続を規定・接続を行う。これらの要素を分離してサポートすることで、プログ
82 ラムの開発・テストで、それぞれに集中することができる。また、各要素毎に切
83 り換えを行うことができるので、ポータビリティ性の向上が期待できる。
84
85 \section{Federated Linda の提案}
86 Federated Linda は、複数のタプルスペースを相互に接続することにより分散プ
87 ログラムを実現する。一つのタプルスペースには少数の接続があることが期待さ
88 れており、多数のタプルスペースが接続により分散アプリケーションを実現する
89 (図\ref{connection-of-tspace}参照)。インターネットのパケット転送のように、
90 タプルと呼ばれるIDとデータが組になったものが、タプルスペース間を転送され
91 ていく。
92
93 Federated Lindaは分散プログラムの要素毎に以下のモデルを提供する。Local
94 Accessは、in,read,outを用いたタプルを出し入れする通信モデルであり、通信
95 は非同期に行われる。Protocol Engineは分散アルゴリズムを内蔵するエージェン
96 トを記述するモデル。エージェントはタプルをリレー転送する
97 Link ConfigurationはXMLでトポロジを定義して、それを基に接続を行うモジュー
98 ルを提供する。
99 \begin{figure}[htp]
100 \begin{center}
101 \includegraphics[width=3.5cm]{fig/FederatedLinda.eps}
102 \caption{タプルスペースの相互接続}
103 \label{connection-of-tspace}
104 \end{center}
105 \end{figure}
106
107 \section{プログラミング例}
108 Linda Server は C 言語で記述している。タプルスペースはメモリ上のキューと
109 して実装されている。タプルIDは16bit整数値、データは任意の文字列である。
110 Protocol Engine, クライアントプログラムはC, Perl, Python, Ruby で記述可能
111 である。以下にPython で記述したマルチキャストを行うプログラム例を載せる。
112 \begin{verbatim}
113 while (1) : # メインループ
114 rep=ConnectRep.reply()
115 if (rep): # 新規の接続処理
116 ConnectRep = self.linda.In(TUPLE_ID_CONNECT)
117 # 新規接続者を登録
118 self.tuplespaces.append(getTuplespace(rep))
119 rep=MultiCastRep.reply()
120 if (rep): # マルチキャスト
121 MultiCastRep=self.linda.In(TUPLE_ID_MULTICAST)
122 # 全タプルスペースへデータを送信
123 for t in self.tuplespaces :
124 t.Out(TUPLE_ID_RECV, rep)
125 self.flinda.sync()
126 \end{verbatim}
127 \section{Federated Lindaを用いたプログラミング}
128 Federated Linda を用いたプログラム例としてディスタンスベクタ型ルーティン
129 グプロトコルをPythonで実装した。宛先情報は``ホスト名:ポート番号''の文字
130 列として表す。Linda Serverとルーティングエージェントをセットで１ノードと
131 してルーティングを行う。今回接続を行ってからルーティングテーブルが安定す
132 るまでの時間を計測した(図\ref{exetime})。トポロジは二分木とメッシュを使
133 用した。また、トポロジを構築するXMLを用いて、ノード間の接続を行った。こ
134 の結果より、ディスタンスベクタ型ルーティングプロトコルでは二分木よりメッ
135 シュの方が遥かに時間がかかることが容易に確認できた。
136
137 \begin{figure}[htp]
138 \begin{center}
139 \includegraphics[width=7cm]{fig/exetime.eps}
140 \caption{テーブルが安定するまでの時間}
141 \label{exetime}
142 \end{center}
143 \end{figure}
144
145 \section{比較}
146 JXTAはノードの発見とグループの自己組織化は提供するが、分散アプリケーションをど
147 う書くかは示してくれない。Federated Linda はタプルの出し入れという通信モ
148 デルと分散プログラム毎にプログラミングモデルを提供している。
149
150 CORBAはネットワークを意識しないオブジェクト呼び出しができるが、それゆえ
151 通信が起こるタイミングが把握しづらくなりやすい。Federated Lindaはsyncと
152 いう関数でしか通信は起きないので通信発生は明確である。
153
154 OverlayWeaverは分散アルゴリズムをJavaでしか記述できない。Federated Linda
155 は好きなスクリプト言語で記述可能である。また、通信モデルも理解しやすい。
156
157 \section{考察}
158 タプルの出し入れという通信モデルは直感的に分かりやすく、簡潔に書ける。ま
159 た、分散プログラムを要素毎に分離して提供するので、開発しやすくなっている。
160 Federated Linda の記述の容易さはそれらの理由によるものであると考えられる。
161 タプルの出し入れという通信モデルにより、タプル転送を行う。この通信モデル
162 はインターネットのパケット転送と酷似しており、Federated Linda を用いてイ
163 ンターネットの分散プログラムが記述できる。また、分散プログラムの要素を分
164 離して提供しているので、それらの切り替えが容易に行うことができる。
165
166 \section{まとめと課題}
167 スケーラブルな分散プログラミングモデルとしてFederated Lindaを提案し、実
168 装した。またそれらを用いたルーティングプログラムを作成した。他の分散プロ
169 グラムツールとの比較を行い、考察を行った。今後の課題として、Federated
170 Lindaを用いてより多くの分散プログラムを実装することが重要だと思われる。
171 {\small
172 \begin{thebibliography}{9}
173 \bibitem{globalid}河野 真治,仲宗根 雅臣,
174 同期型タプル通信を用いたマルチユーザ Playstation ゲームシステム,
175 卒業論文, 1998
176
177 \bibitem{globalid}安村 恭一，河野 真治,
178 大域IDを持たない連邦型タプルスペース Federated Linda,
179 第99回 情報処理学会 システムソフトウェアとオペレーティング・システム研究発表会, 2005.
180
181 \bibitem{dinamicrouting}安村 恭一，河野 真治,
182 ,動的ルーティングによりタプル配信を行なう分散タプルスペース Federated Linda,
183 日本ソフトウェア科学会第22回大会, 2005.
184 \end{thebibliography}
185 }
186 % \bibitem{argentina} 中西 学，永田 裕志，猪木 寛至
187 % ``アルゼンチンバックブリーカーの効果的担ぎ方,''
188 % 新日技報 Vol.99 No.38 pp.7--11，新日本技術向上学会，1999．
189 % \bibitem{friendly-power} 中西 学，キン肉 卓，正義超人，
190 % ``友情パワーにおける潜在能力の引出し方,''
191 % 第12回 火事場のクソ力と友情パワーシンポジウム資料，
192 % 悪行超人討伐学会主催, 2000．
193 %\begin{table}[b]
194 % \begin{tabular}{cc}
195 % \parbox[c]{.14\textwidth}{\center%
196 % \epsfile{file=author.eps,scale=0.65}\\
197 % \begin{center}\vspace*{-4mm}{著者近影}\end{center}}&
198 % \parbox[c]{.28\textwidth}{\scriptsize
199 %著者略歴：
200 %高校時代よりアマレスで活躍し、全日本選手権３連覇を達成。専修大学を卒業
201 %後、'91年4月に「闘魂クラブ」に入団。'92年のバルセロナ五輪に出場後、同年
202 %8月に新日本プロレス入門。ＳＧタッグIIで藤波のパートナーに抜擢を受け、
203 %同年10月13日、東大阪市立中央体育館におけるＳ・ノートン、Ｓ・Ｓ・マシン
204 %組戦でデビュー。'95年3月の第6回ＹＬ杯に優勝し、同年6月に米国武者修行
205 %へ出発。同年7月よりＷＣＷマットに参戦し、クロサワの名で活躍。'96年9月に
206 %凱旋し、'97年５月、小島と組み第31代IWGPタッグ王座に君臨。'98年12月、
207 %IWGPヘビー級王座に初挑戦。'99年8月、Ｇ1クライマックス初優勝に輝き、８・
208 %28神宮で永田と組み第39代IWGPタッグ王座に就く。今年3月格闘集団「G-EGGS」
209 %の一員となる。
210 %}
211 % \end{tabular}
212 %\end{table}
213
214 \end{document}