|
6
|
1 \documentclass[private]{ipsjpapers}
|
|
|
2 \usepackage{listings}
|
|
|
3 % 巻数，号数などの設定
|
|
|
4 %\setcounter{巻数}{41}
|
|
|
5 %\setcounter{号数}{6}
|
|
|
6 %\setcounter{volpageoffset}{1234}
|
|
|
7 %\受付{12}{2}{4}
|
|
|
8 %\採録{12}{5}{11}
|
|
|
9
|
|
|
10 % ユーザが定義したマクロなど．
|
|
|
11 \makeatletter
|
|
|
12 \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
|
|
|
13 \def\<{\(\langle\)}
|
|
|
14 \def\>{\(\rangle\)}
|
|
|
15 %\def\|{\verb|}
|
|
|
16 \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
|
|
|
17 \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
|
|
|
18 \def\LATEX{\iLATEX\Large}
|
|
|
19 \def\LATEx{\iLATEX\normalsize}
|
|
|
20 \def\LATex{\iLATEX\small}
|
|
|
21 \def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
|
|
|
22 T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
|
|
|
23 \def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
|
|
|
24 \def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
|
|
|
25 \def\Quote{\list{}{}\item[]}
|
|
|
26 \let\endQuote\endlist
|
|
|
27 \def\TT{\if@LaTeX@e\tt\fi}
|
|
|
28 \def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
|
|
|
29 $\backslash$#1\fi}
|
|
|
30
|
|
|
31 %\checklines % 行送りを確認する時に使用
|
|
|
32 \begin{document}%{
|
|
|
33 % 和文表題
|
|
|
34 \title[Code Segment と Data Segment によるプログラミング手法]%
|
|
|
35 {Code Segment と Data Segment によるプログラミング手法 }
|
|
|
36 % 英文表題
|
|
|
37 \etitle{How to Programming with Code Segment and Data Segment}
|
|
|
38 % 所属ラベルの定義
|
|
|
39 \affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}
|
|
|
40 % 和文著者名
|
|
|
41 \author{河野 真治\affiref{URYUKYU}\member{19841765}\and
|
|
|
42 杉本 優\affiref{URYUKYU}\nomember}
|
|
|
43
|
|
|
44
|
|
|
45 % 英文著者名
|
|
|
46 \eauthor{Shinji Kono\affiref{URYUKYU}\and
|
|
|
47 Yu Sugimoto\affiref{URYUKYU}}
|
|
|
48
|
|
|
49
|
|
|
50 % 連絡先（投稿時に必要．製版用では無視される．）
|
|
|
51 \contact{杉本 優\\
|
|
|
52 〒903-0213 沖縄県中頭郡西原町字千原1番地\\
|
|
|
53 琉球大学 情報工学科\\
|
|
|
54 TEL: (098)895-8723\qquad FAX: (098)895-8727\\
|
|
|
55 email: sugi@cr.ie.u-ryukyu.ac.jp}
|
|
|
56
|
|
|
57 % 和文概要
|
|
|
58 \begin{abstract}
|
|
|
59 本研究室では分散プログラミングにおいて、データをData Segment、タスクをCode Segmentという単位に分割して記述する方法を提唱している。
|
|
|
60 しかし、前述した方法をプログラマーが一から記述することは大変である。そこで、本研究室で分散ネットフレームワーク Alice を作成した。本論文では実際にAliceを用いてCode Segment と Data Segment によるプログラミング手法の例を示す。
|
|
|
61 \end{abstract}
|
|
|
62 % 英文概要
|
|
|
63 \begin{eabstract}
|
|
|
64 \end{eabstract}
|
|
|
65
|
|
|
66 % 表題などの出力
|
|
|
67 \maketitle
|
|
|
68
|
|
|
69 % }{
|
|
|
70
|
|
|
71 % 本文はここから始まる
|
|
|
72 \section{歴史的経緯}
|
|
|
73 本研究室では、並列タスク管理フレームワークCeriumの管理を行なっているが、その設計と実装を行うにあたり、並列プログラミングと分散プログラミング
|
|
|
74 は本質的には同じことを行なっていることが分かった。特にヘテロジーニアスマルチコアであり、ローカルストアをそれぞれのコアが持っているというCell の特異な環境は、分散プログラミング環境と告示している。それらを踏まえて、Ceriumのタスク管理手法を分散に応用できないかと考えた。
|
|
|
75
|
|
|
76
|
|
|
77 Ceriumに置いても、タスクとそれの入出力データの取り扱いは難しい課題である。データを操作するAPIを考えて、タスクを自然に記述し、効率良く実行する方法を考えてきた。そこで考えられた手法が、データをDataSegment、タスクをCodeSegmentという単位に分割して記述する方法である。
|
|
|
78 % }{
|
|
|
79
|
|
|
80 \section{分散ネットフレームワークAlice}\label{sec:ITEM}
|
|
|
81 \subsection{Aliceとは}
|
|
|
82 Aliceは本研究室の卒業生である赤嶺一樹氏が、本研究室で開発を行なっている並列タスク管理フレームワーク Cerium と先行研究である Federated Linda の開発を通して得られた知見を生かされている。
|
|
|
83 Federated Linda の設計はシングルスレッドで行われている。しかし、近年ではマルチコアのマシンが主流となっている。将来的にはメニーコアのマシンが主流になってくると考えられるそのような背景を踏まえてAliceはマルチスレッド向けに設計されている。
|
|
|
84
|
|
|
85 AliceはData SegmentとCode Segmentという単位でデータと処理を細かく分割し、それぞれの依存関係を記述して分散プログラムを作成する。また、他のマシンとの接続トポロジーの構成の機能も有しているのでユーザーはトポロジー構成後の処理を記述するだけでよい。
|
|
|
86 % }{
|
|
|
87 \subsection{Data Segment}
|
|
|
88 AliceではData Semgnetをデータベースとして利用している。KeyValueStoreで実装されており、キーごとにリストを持っている。Data Segment APIを用いることで、リストにデータを追加、削除を適宜行うことができる。
|
|
|
89
|
|
|
90 \subsubsection{Data Segment Manager}
|
|
|
91 大量のData Segmentを管理するのがData Segment Managerである。Data Segment Managerは文字列のキーでData Segmentを整理する。各キーごとにキュー構造を持っている。それらをData Segment APIを用いて操作する。
|
|
|
92 データの読み出し("peek" または "take")時に、希望のデータがなかった場合、ブロッキングを行う機能を持つ。
|
|
|
93 しかし、ブロッキングといってもそこで同期するわけではない。
|
|
|
94 非同期でデータを通信する。
|
|
|
95 そのため、 "peek" と "take" は他の API とは違い、レスポンスが発生する。
|
|
|
96 \subsubsection{Data Segment API}
|
|
|
97 表番号)が用意されているData Segment APIである。これらを用いてデータの送受信を行う。
|
|
|
98 \begin{itemize}
|
|
|
99 \item {\ttfamily void put(String key, Value val)}
|
|
|
100 \item {\ttfamily void update(String key, Value val)}
|
|
|
101 \item {\ttfamily void peek(Receiver receiver, String key, int id)}
|
|
|
102 \item {\ttfamily void take(Receiver receiver, String key, int id)}
|
|
|
103 \end{itemize}
|
|
|
104
|
|
|
105 \subsubsection*{"put"}
|
|
|
106 "put" はデータを追加するための API である。
|
|
|
107
|
|
|
108 "put" は受け取ったデータ val を Data Segment 内のキューに対してエンキューする。
|
|
|
109 この時、キーごとに重複しない連番の ID を受け取った順に振る。
|
|
|
110
|
|
|
111 %(図 \ref{fig:put})
|
|
|
112 \subsubsection*{"update"}
|
|
|
113 "update" はデータを置き換えるための API である。
|
|
|
114
|
|
|
115 "update" はキューの先頭にあるデータをひとつだけ削除する。
|
|
|
116 その後は "put" と同じく、 受け取ったデータ val を Data Segment 内のキューに対してエンキューする。
|
|
|
117 この時、キーごとに重複しない連番の ID を受け取った順に振る。
|
|
|
118 %(図 \ref{fig:update})
|
|
|
119 \subsubsection*{"peek"}
|
|
|
120 "peek" はデータを読み込むための API である。
|
|
|
121
|
|
|
122 "peek" は前回読み込んだデータの id を引数で指定する。省略した場合は、 0 が id として渡される。
|
|
|
123 id よりも値の大きい id のデータがキューに含まれていれば、そのデータを receiver に返す。
|
|
|
124 もし id 以下のデータしか無いならば、データの更新が前回の "peek" 発行時から更新が無いものと考え、リストに格納されて保留される。
|
|
|
125 %(図 \ref{fig:peek})
|
|
|
126
|
|
|
127 "take" や "update" によりデータの更新があれば、 "peek" が直ちに実行される。
|
|
|
128 \subsubsection*{"take"}
|
|
|
129 "take" もデータを読み込むための API である。
|
|
|
130 基本的な id に関する部分は "peek" と同じである。
|
|
|
131
|
|
|
132 "peek" との決定的な違いは、読み込まれたデータは Data Segment 内のキューから取り除かれるということである。
|
|
|
133 %(図 \ref{fig:take})
|
|
|
134
|
|
|
135 %after
|
|
|
136 \lstset{
|
|
|
137 language={java},
|
|
|
138 basicstyle={\small},
|
|
|
139 identifierstyle={\small},
|
|
|
140 commentstyle={\small\itshape},
|
|
|
141 keywordstyle={\small\bfseries},
|
|
|
142 ndkeywordstyle={\small},
|
|
|
143 stringstyle={\small\ttfamily},
|
|
|
144 frame={tb},
|
|
|
145 breaklines=true,
|
|
|
146 columns=[l]{fullflexible},
|
|
|
147 numbers=left,
|
|
|
148 xrightmargin=0zw,
|
|
|
149 xleftmargin=3zw,
|
|
|
150 numberstyle={\scriptsize},
|
|
|
151 stepnumber=1,
|
|
|
152 numbersep=1zw,
|
|
|
153 lineskip=-0.5ex
|
|
|
154 }
|
|
|
155
|
|
|
156
|
|
|
157
|
|
|
158 \subsection{Code Segment}
|
|
|
159 Code Segmentはタスクのことである。Code Segmentをユーザーが記述するときに、Code Segment 内で使用するData Segment を記述し、依存関係を作る。依存関係により、実行される順番が一意に決まる。実際に使用するData Segment はCode Segmentの入出力に相当する。それぞれ、Input Data Segment、Output Data Segmentとする。
|
|
|
160 \subsubsection{Code Segmentの実行方法}
|
|
|
161 Code Semgnetを実行するためにはStart Code SegmentというCode Segmentを実行させる必要がある。
|
|
|
162 Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。
|
|
|
163 \begin{table}[tb]
|
|
|
164 \lstinputlisting[label=StartCodeSegment, caption=StartCodeSegment]{source/StartCodeSegment.java}
|
|
|
165 \end{table}
|
|
|
166
|
|
|
167 \subsubsection{Code Segmentの記述方法}
|
|
|
168 Code Segmentをユーザーが記述する際にはCodeSegmentを継承して記述する。そのCodeSegmentはInputDataSegmentManagerとOutputDataSegmentManagerを利用することができる。
|
|
|
169 \subsubsection*{InputDataSegmentManager}
|
|
|
170 InputDataSegmentManagerはCode Segmentのidsというフィールドを用いてアクセスする。
|
|
|
171 \begin{itemize}
|
|
|
172 \item {\ttfamily Receiver create(CommandType type)}
|
|
|
173 \end{itemize}
|
|
|
174 createでコマンドが実行された際に取得されるData Segmentが格納される受け皿を作る。引数にはCommandTypeが取られ、指定できるCommandTypeはPEEKまたはTAKEである。
|
|
|
175 \begin{itemize}
|
|
|
176 \item {\ttfamily void setKey(String managerKey, String key, int id)}
|
|
|
177 \end{itemize}
|
|
|
178 setKeyメソッドにより、どこのData Segmentのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定することができる。
|
|
|
179 コマンドの結果がレスポンスとして届き次第Code Segmentは実行される。
|
|
|
180 \subsubsection*{OutputDataSegmentManager}
|
|
|
181 OutputDataSegmentManagerはCode Segmentのodsというフィールドを用いてアクセスする。
|
|
|
182 OutPutDataSegmentManagerは"put"または"update"を実行することができる。
|
|
|
183 \begin{itemize}
|
|
|
184 \item {\ttfamily void put(String managerKey, String key, \\ Value val)}
|
|
|
185 \item {\ttfamily void update(String managerKey, String key, Value val)}
|
|
|
186 \end{itemize}
|
|
|
187
|
|
|
188 \subsection{Topology Manager}
|
|
|
189 TopologyManagerはAlice同士の接続トポロジーを管理する。TopologyManager関連の通信処理はCode Segmentで実装してある。
|
|
|
190 TopologyManagerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきクライアントのIPアドレスやポート番号、接続名を送り、トポロジーファイルに記述された通りにトポロジーを作成する。
|
|
|
191
|
|
|
192 \subsection{Topology Managerの設定ファイル}
|
|
|
193 Topology Managerはトポロジーファイルを読み込むが、トポロジーファイル自体はDOT Languageという言語で記述される。
|
|
|
194 DOT Languageとはプレーンテキストを用いて、データ構造としてのグラフを表現するための、データ記述言語の一種である。このDOT Languageのグラフを利用して、クライアント間の接続を表現する。DOT Languageファイルはdotコマンドを用いて、グラフの画像ファイルを出力することができるので、記述したトポロジーが正しいことを可視化して確認することができる。
|
|
|
195
|
|
|
196 クライアント間の接続にはlabelを用いて名前が割り振られており、この接続名を用いてユーザーはData Segment Managerにアクセスすることができる。
|
|
|
197 前述したReceiver にsetKeyを行う際、odsでputまたはupdateする際の引数のmanagerKeyがこれにあたる。
|
|
|
198
|
|
|
199 \subsection{Topology Managerの使用方法}
|
|
|
200 Topology Nodeを起動する際にコマンドライン引数としてTopology ManagerのIPアドレスとポート番号を指定をする。
|
|
|
201 そしてmain関数内でTopologyNodeをnewを行えば良い。
|
|
|
202 TopologyNodeの第一引数は Alice デーモンの設定オブジェクト、第二引数はStart Code Segmentである。
|
|
|
203 ここで指定した、Start Code Segmentがトポロジーが完成した後実行される。
|
|
|
204
|
|
|
205 % }{
|
|
|
206 \section{ゲームの例題}\label{sec:Enum}\label{sec:item}
|
|
|
207 \subsection{水族館}
|
|
|
208 今回作成した例題は水族館である。複数のクライアントのディスプレイを複数の魚が移動していくものである。魚は画面の端まで移動すると自分の画面上からは消え、別のクライアントの画面の端から魚が出てくる。また、魚のうち一匹はクライアントが直接操作することができる。トポロジーはTopologyManagerによりツリー状に構成してある。
|
|
|
209 \subsection{データの伝搬}
|
|
|
210
|
|
|
211 \begin{enumerate}
|
|
|
212 \item ユーザーが魚を操作するまたはCode Segmentにより魚の座標が更新される。
|
|
|
213 \item 画面に表示させるためのSetLocation (Code Segment)が実行され実際に魚のオブジェクトにセットされ画面に反映される。
|
|
|
214 \item Update(Code Segment)にFishPosition(魚の座標データ)が渡される。
|
|
|
215 \item Updateにlist(送信者リスト)が渡される。
|
|
|
216 \item Updateが実行され、listを元にデータが送信される。ただし、この時にFishPositionには送信元情報が付加されているので、送信元には送信されない。
|
|
|
217 \item 各clientで2 - 4が実行される。
|
|
|
218 \end{enumerate}
|
|
|
219
|
|
|
220 \section{評価}
|
|
|
221
|
|
|
222
|
|
|
223 \section{まとめと今後の課題}
|
|
|
224
|
|
|
225
|
|
|
226 \end{document}
|
