Mercurial > hg > Papers > 2012 > sugi-prosym

comparison Paper/sugi-prosym.tex @ 0:58c6244a184d

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