comparison Paper/sugi-prosym.tex @ 4:88a77b2c92ea

add makefile
author e095732 <e095732@ie.u-ryukyu.ac.jp>
date Sun, 18 Nov 2012 03:32:29 +0900
parents d0a3f3122885
children a48e22ceed00
comparison
equal deleted inserted replaced
3:d0a3f3122885 4:88a77b2c92ea
1 \documentclass[private]{ipsjpapers} 1 \documentclass[private]{ipsjpapers}
2 \usepackage[dvipdfmx]{graphicx} 2 % 巻数,号数などの設定
3 % CȂǂ̐ݒ 3 %\setcounter{巻数}{41}
4 %\setcounter{}{41} 4 %\setcounter{号数}{6}
5 %\setcounter{}{6}
6 %\setcounter{volpageoffset}{1234} 5 %\setcounter{volpageoffset}{1234}
7 %\t{12}{2}{4} 6 %\受付{12}{2}{4}
8 %\̘^{12}{5}{11} 7 %\採録{12}{5}{11}
9 8
10 % [U`}NȂǁD 9 % ユーザが定義したマクロなど.
11 \makeatletter 10 \makeatletter
12 \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY} 11 \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
13 \def\<{\(\langle\)} 12 \def\<{\(\langle\)}
14 \def\>{\(\rangle\)} 13 \def\>{\(\rangle\)}
15 \def\|{\verb|} 14 %\def\|{\verb|}
16 \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline} 15 \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
17 \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\} 16 \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
18 \def\LATEX{\iLATEX\Large} 17 \def\LATEX{\iLATEX\Large}
19 \def\LATEx{\iLATEX\normalsize} 18 \def\LATEx{\iLATEX\normalsize}
20 \def\LATex{\iLATEX\small} 19 \def\LATex{\iLATEX\small}
26 \let\endQuote\endlist 25 \let\endQuote\endlist
27 \def\TT{\if@LaTeX@e\tt\fi} 26 \def\TT{\if@LaTeX@e\tt\fi}
28 \def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else 27 \def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
29 $\backslash$#1\fi} 28 $\backslash$#1\fi}
30 29
31 %\checklines % smF鎞Ɏgp 30 %\checklines % 行送りを確認する時に使用
32 \begin{document}%{ 31 \begin{document}%{
33 % a\ 32 % 和文表題
34 \title[Code Segment Data Segment ɂvO~O@]% 33 \title[Code Segment と Data Segment によるプログラミング手法]%
35 {Code Segment Data Segment ɂvO~O@ } 34 {Code Segment と Data Segment によるプログラミング手法 }
36 % p\ 35 % 英文表題
37 \etitle{How to Programming with Code Segment and Data Segment} 36 \etitle{How to Programming with Code Segment and Data Segment}
38 % x̒` 37 % 所属ラベルの定義
39 \affilabel{URYUKYU}{w\\University of the Ryukyu} 38 \affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}
40 % aҖ 39 % 和文著者名
41 \author{͖ ^\affiref{URYUKYU}\member{19841765}\and 40 \author{河野 真治\affiref{URYUKYU}\member{19841765}\and
42 { D\affiref{URYUKYU}\nomember} 41 杉本 優\affiref{URYUKYU}\nomember}
43 42
44 43
45 % pҖ 44 % 英文著者名
46 \eauthor{Shinji Kono\affiref{URYUKYU}\and 45 \eauthor{Shinji Kono\affiref{URYUKYU}\and
47 Yu Sugimoto\affiref{URYUKYU}} 46 Yu Sugimoto\affiref{URYUKYU}}
48 47
49 48
50 % AieɕKvDŗpł͖Dj 49 % 連絡先(投稿時に必要.製版用では無視される.)
51 \contact{{ D\\ 50 \contact{杉本 優\\
52 903-0213 ꌧS猴1Ԓn\\ 51 〒903-0213 沖縄県中頭郡西原町字千原1番地\\
53 w Hw\\ 52 琉球大学 情報工学科\\
54 TEL: (098)895-8723\qquad FAX: (098)895-8727\\ 53 TEL: (098)895-8723\qquad FAX: (098)895-8727\\
55 email: sugi@cr.ie.u-ryukyu.ac.jp} 54 email: sugi@cr.ie.u-ryukyu.ac.jp}
56 55
57 % aTv 56 % 和文概要
58 \begin{abstract} 57 \begin{abstract}
59 {ł͕UvO~OɂāAf[^Data SegmentA^XNCode SegmentƂPʂɕċLq@񏥂ĂB 58 本研究室では分散プログラミングにおいて、データをData Segment、タスクをCode Segmentという単位に分割して記述する方法を提唱している。
60 AOq@vO}[ꂩLq邱Ƃ͑ςłBŁA{ŕUlbgt[[N Alice 쐬B{_ł͎ۂAlicepCode Segment Data Segment ɂvO~O@̗B 59 しかし、前述した方法をプログラマーが一から記述することは大変である。そこで、本研究室で分散ネットフレームワーク Alice を作成した。本論文では実際にAliceを用いてCode Segment と Data Segment によるプログラミング手法の例を示す。
61 \end{abstract} 60 \end{abstract}
62 % pTv 61 % 英文概要
63 \begin{eabstract} 62 \begin{eabstract}
64 \end{eabstract} 63 \end{eabstract}
65 64
66 % \Ȃǂ̏o 65 % 表題などの出力
67 \maketitle 66 \maketitle
68 67
69 % }{ 68 % }{
70 69
71 % {͂n܂ 70 % 本文はここから始まる
72 \section{jIo} 71 \section{歴史的経緯}
73 {ł́A^XNǗt[[NCerium̊ǗsȂĂ邪A̐݌vƎsɂAvO~OƕUvO~O 72 本研究室では、並列タスク管理フレームワークCeriumの管理を行なっているが、その設計と実装を行うにあたり、並列プログラミングと分散プログラミング
74 ͖{Iɂ͓ƂsȂĂ邱ƂBɃweW[jAX}`RAłA[JXgAꂼ̃RAĂƂCell ̓قȊ‹́AUvO~O‹ƍĂB𓥂܂āACerium̃^XNǗ@𕪎UɉpłȂƍlB 73 は本質的には同じことを行なっていることが分かった。特にヘテロジーニアスマルチコアであり、ローカルストアをそれぞれのコアが持っているというCell の特異な環境は、分散プログラミング環境と告示している。それらを踏まえて、Ceriumのタスク管理手法を分散に応用できないかと考えた。
75 74
76 75
77 CeriumɒuĂA^XNƂ̓o̓f[^̎舵͓ۑłBf[^𑀍삷APIlāA^XNRɋLqAǂs@lĂBōlꂽ@Af[^DataSegmentA^XNCodeSegmentƂPʂɕċLq@łB 76 Ceriumに置いても、タスクとそれの入出力データの取り扱いは難しい課題である。データを操作するAPIを考えて、タスクを自然に記述し、効率良く実行する方法を考えてきた。そこで考えられた手法が、データをDataSegment、タスクをCodeSegmentという単位に分割して記述する方法である。
78 % }{ 77 % }{
79 78
80 \section{Ulbgt[[NAlice}\label{sec:ITEM} 79 \section{分散ネットフレームワークAlice}\label{sec:ITEM}
81 \subsection{AliceƂ} 80 \subsection{Aliceとは}
82 Alice͖{̑ƐłԗA{ŊJsȂĂ^XNǗt[[N Cerium Ɛsł Federated Linda ̊Jʂēꂽm𐶂ĂB 81 Aliceは本研究室の卒業生である赤嶺一樹氏が、本研究室で開発を行なっている並列タスク管理フレームワーク Cerium と先行研究である Federated Linda の開発を通して得られた知見を生かされている。
83 Federated Linda ̐݌v̓VOXbhōsĂBAߔNł̓}`RÃ}V嗬ƂȂĂBIɂ̓j[RÃ}V嗬ɂȂĂƍl邻̂悤Ȕwi𓥂܂Alice̓}`Xbhɐ݌vĂB 82 Federated Linda の設計はシングルスレッドで行われている。しかし、近年ではマルチコアのマシンが主流となっている。将来的にはメニーコアのマシンが主流になってくると考えられるそのような背景を踏まえてAliceはマルチスレッド向けに設計されている。
84 83
85 AliceData SegmentCode SegmentƂPʂŃf[^ƏׂAꂼ̈ˑ֌WLqĕUvO쐬B܂Ã}VƂ̐ڑg|W[̍\̋@\LĂ̂Ń[U[̓g|W[\̏Lq邾ł悢B 84 AliceはData SegmentとCode Segmentという単位でデータと処理を細かく分割し、それぞれの依存関係を記述して分散プログラムを作成する。また、他のマシンとの接続トポロジーの構成の機能も有しているのでユーザーはトポロジー構成後の処理を記述するだけでよい。
86 % }{ 85 % }{
87 \subsection{Data Segment} 86 \subsection{Data Segment}
88 AlicełData Semgnetf[^x[XƂėpĂBKeyValueStoreŎĂAL[ƂɃXgĂBData Segment APIp邱ƂŁAXgɃf[^ljA폜KXsƂłB 87 AliceではData Semgnetをデータベースとして利用している。KeyValueStoreで実装されており、キーごとにリストを持っている。Data Segment APIを用いることで、リストにデータを追加、削除を適宜行うことができる。
89 88
90 \subsubsection{Data Segment Manager} 89 \subsubsection{Data Segment Manager}
91 ʂData SegmentǗ̂Data Segment ManagerłBData Segment Manager͕̃L[Data Segment𐮗BeL[ƂɃL[\ĂBData Segment APIpđ삷B 90 大量のData Segmentを管理するのがData Segment Managerである。Data Segment Managerは文字列のキーでData Segmentを整理する。各キーごとにキュー構造を持っている。それらをData Segment APIを用いて操作する。
92 f[^̓ǂݏo("peek" ܂ "take")ɁA]̃f[^ȂꍇAubLOs@\B 91 データの読み出し("peek" または "take")時に、希望のデータがなかった場合、ブロッキングを行う機能を持つ。
93 AubLOƂĂœ킯ł͂ȂB 92 しかし、ブロッキングといってもそこで同期するわけではない。
94 񓯊Ńf[^ʐMB 93 非同期でデータを通信する。
95 ̂߁A "peek" "take" ͑ API Ƃ͈ႢAX|XB 94 そのため、 "peek" と "take" は他の API とは違い、レスポンスが発生する。
96 \subsubsection{Data Segment API} 95 \subsubsection{Data Segment API}
97 \ԍ)pӂĂData Segment APIłBpăf[^̑MsB 96 表番号)が用意されているData Segment APIである。これらを用いてデータの送受信を行う。
98 \begin{itemize} 97 \begin{itemize}
99 \item {\ttfamily void put(String key, Value val)} 98 \item {\ttfamily void put(String key, Value val)}
100 \item {\ttfamily void update(String key, Value val)} 99 \item {\ttfamily void update(String key, Value val)}
101 \item {\ttfamily void peek(Receiver receiver, String key, int id)} 100 \item {\ttfamily void peek(Receiver receiver, String key, int id)}
102 \item {\ttfamily void take(Receiver receiver, String key, int id)} 101 \item {\ttfamily void take(Receiver receiver, String key, int id)}
103 \end{itemize} 102 \end{itemize}
104 103
105 \subsubsection*{"put"} 104 \subsubsection*{"put"}
106 "put" ̓f[^lj邽߂ API łB 105 "put" はデータを追加するための API である。
107 106
108 "put" ͎󂯎f[^ val Data Segment ̃L[ɑ΂ăGL[B 107 "put" は受け取ったデータ val を Data Segment 内のキューに対してエンキューする。
109 ̎AL[ƂɏdȂAԂ ID 󂯎ɐUB(} \ref{fig:put}) 108 この時、キーごとに重複しない連番の ID を受け取った順に振る。
109
110 %(図 \ref{fig:put})
110 \subsubsection*{"update"} 111 \subsubsection*{"update"}
111 "update" ̓f[^u邽߂ API łB 112 "update" はデータを置き換えるための API である。
112 113
113 "update" ̓L[̐擪ɂf[^ЂƂ‚폜B 114 "update" はキューの先頭にあるデータをひとつだけ削除する。
114 ̌ "put" ƓA 󂯎f[^ val Data Segment ̃L[ɑ΂ăGL[B 115 その後は "put" と同じく、 受け取ったデータ val を Data Segment 内のキューに対してエンキューする。
115 ̎AL[ƂɏdȂAԂ ID 󂯎ɐUB(} \ref{fig:update}) 116 この時、キーごとに重複しない連番の ID を受け取った順に振る。
117 %(図 \ref{fig:update})
116 \subsubsection*{"peek"} 118 \subsubsection*{"peek"}
117 "peek" ̓f[^ǂݍނ߂ API łB 119 "peek" はデータを読み込むための API である。
118 120
119 "peek" ͑Oǂݍ񂾃f[^ id Ŏw肷Bȗꍇ́A 0 id ƂēnB 121 "peek" は前回読み込んだデータの id を引数で指定する。省略した場合は、 0 が id として渡される。
120 id l̑傫 id ̃f[^L[Ɋ܂܂Ă΁Ãf[^ receiver ɕԂB 122 id よりも値の大きい id のデータがキューに含まれていれば、そのデータを receiver に返す。
121 id ȉ̃f[^Ȃ΁Af[^̍XVO "peek" sXV̂ƍlAXgɊi[ĕۗB(} \ref{fig:peek}) 123 もし id 以下のデータしか無いならば、データの更新が前回の "peek" 発行時から更新が無いものと考え、リストに格納されて保留される。
122 124 %(図 \ref{fig:peek})
123 "take" "update" ɂf[^̍XV΁A "peek" ɎsB 125
126 "take" や "update" によりデータの更新があれば、 "peek" が直ちに実行される。
124 \subsubsection*{"take"} 127 \subsubsection*{"take"}
125 "take" f[^ǂݍނ߂ API łB 128 "take" もデータを読み込むための API である。
126 {I id Ɋւ镔 "peek" ƓłB 129 基本的な id に関する部分は "peek" と同じである。
127 130
128 "peek" Ƃ̌IȈႢ́Aǂݍ܂ꂽf[^ Data Segment ̃L[菜ƂƂłB(} \ref{fig:take}) 131 "peek" との決定的な違いは、読み込まれたデータは Data Segment 内のキューから取り除かれるということである。
132 %(図 \ref{fig:take})
129 133
130 134
131 \subsection{Code Segment} 135 \subsection{Code Segment}
132 Code Segment̓^XN̂ƂłBCode Segment[U[LqƂɁACode Segment ŎgpData Segment LqAˑ֌WBˑ֌WɂAs鏇ԂӂɌ܂BۂɎgpData Segment Code Segment̓o͂ɑBꂼAInput Data SegmentAOutput Data SegmentƂB 136 Code Segmentはタスクのことである。Code Segmentをユーザーが記述するときに、Code Segment 内で使用するData Segment を記述し、依存関係を作る。依存関係により、実行される順番が一意に決まる。実際に使用するData Segment はCode Segmentの入出力に相当する。それぞれ、Input Data Segment、Output Data Segmentとする。
133 \subsubsection{Code Segment̎s@} 137 \subsubsection{Code Segmentの実行方法}
134 Code Semgnets邽߂ɂStart Code SegmentƂCode SegmentsKvB 138 Code Semgnetを実行するためにはStart Code SegmentというCode Segmentを実行させる必要がある。
135 Start Code Segment͂ǂData SegmentɂˑȂB‚܂Input Data SegmentȂBCode Segmentmain\bhnewAexecute\bhĂԂƂŎsJn邱ƂłB 139 Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。
136 140
137 141
138 \subsubsection{Code Segment̋Lq@} 142 \subsubsection{Code Segmentの記述方法}
139 Code Segment[U[LqۂɂCodeSegmentpċLqBCodeSegmentInputDataSegmentManagerOutputDataSegmentManager𗘗p邱ƂłB 143 Code Segmentをユーザーが記述する際にはCodeSegmentを継承して記述する。そのCodeSegmentはInputDataSegmentManagerとOutputDataSegmentManagerを利用することができる。
140 \subsubsection*{InputDataSegmentManager} 144 \subsubsection*{InputDataSegmentManager}
141 InputDataSegmentManagerCode SegmentidsƂtB[hpăANZXB 145 InputDataSegmentManagerはCode Segmentのidsというフィールドを用いてアクセスする。
142 \begin{itemize} 146 \begin{itemize}
143 \item {\ttfamily Receiver create(CommandType type)} 147 \item {\ttfamily Receiver create(CommandType type)}
144 \end{itemize} 148 \end{itemize}
145 createŃR}hsꂽۂɎ擾Data Segmenti[󂯎MBɂCommandTypeAwłCommandTypePEEK܂TAKEłB 149 createでコマンドが実行された際に取得されるData Segmentが格納される受け皿を作る。引数にはCommandTypeが取られ、指定できるCommandTypeはPEEKまたはTAKEである。
146 \begin{itemize} 150 \begin{itemize}
147 \item {\ttfamily void setKey(String managerKey, String key, int id)} 151 \item {\ttfamily void setKey(String managerKey, String key, int id)}
148 \end{itemize} 152 \end{itemize}
149 setKey\bhɂAǂData Segment̂keyɑ΂peek܂takeR}hs邩w肷邱ƂłB 153 setKeyメソッドにより、どこのData Segmentのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定することができる。
150 R}ȟʂX|XƂē͂Code Segment͎sB 154 コマンドの結果がレスポンスとして届き次第Code Segmentは実行される。
151 \subsubsection*{OutputDataSegmentManager} 155 \subsubsection*{OutputDataSegmentManager}
152 OutputDataSegmentManagerCode SegmentodsƂtB[hpăANZXB 156 OutputDataSegmentManagerはCode Segmentのodsというフィールドを用いてアクセスする。
153 OutPutDataSegmentManager"put"܂"update"s邱ƂłB 157 OutPutDataSegmentManagerは"put"または"update"を実行することができる。
154 \begin{itemize} 158 \begin{itemize}
155 \item {\ttfamily void put(String managerKey, String key, \\ Value val)} 159 \item {\ttfamily void put(String managerKey, String key, \\ Value val)}
156 \item {\ttfamily void update(String managerKey, String key, Value val)} 160 \item {\ttfamily void update(String managerKey, String key, Value val)}
157 \end{itemize} 161 \end{itemize}
158 162
159 \subsection{Topology Manager} 163 \subsection{Topology Manager}
160 TopologyManagerAlicem̐ڑg|W[ǗBTopologyManager֘A̒ʐMCode SegmentŎĂB 164 TopologyManagerはAlice同士の接続トポロジーを管理する。TopologyManager関連の通信処理はCode Segmentで実装してある。
161 TopologyManager̓g|W[t@Cǂݍ݁AQ\NCAg(ȉATopology Node)ɐڑׂNCAgIPAhX|[gԍAڑ𑗂Ag|W[t@CɋLqꂽʂɃg|W[쐬B 165 TopologyManagerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきクライアントのIPアドレスやポート番号、接続名を送り、トポロジーファイルに記述された通りにトポロジーを作成する。
162 166
163 \subsection{Topology Manager̐ݒt@C} 167 \subsection{Topology Managerの設定ファイル}
164 Topology Manager̓g|W[t@CǂݍނAg|W[t@ĈDOT LanguageƂŋLqB 168 Topology Managerはトポロジーファイルを読み込むが、トポロジーファイル自体はDOT Languageという言語で記述される。
165 DOT LanguageƂ̓v[eLXgpāAf[^\ƂẴOt\邽߂́Af[^Lq̈łBDOT LanguagẽOt𗘗pāANCAgԂ̐ڑ\BDOT Languaget@CdotR}hpāAOt̉摜t@Co͂邱Ƃł̂ŁALqg|W[ƂŽĊmF邱ƂłB 169 DOT Languageとはプレーンテキストを用いて、データ構造としてのグラフを表現するための、データ記述言語の一種である。このDOT Languageのグラフを利用して、クライアント間の接続を表現する。DOT Languageファイルはdotコマンドを用いて、グラフの画像ファイルを出力することができるので、記述したトポロジーが正しいことを可視化して確認することができる。
166 170
167 NCAgԂ̐ڑɂlabelpĖOUĂA̐ڑpă[U[Data Segment ManagerɃANZX邱ƂłB 171 クライアント間の接続にはlabelを用いて名前が割り振られており、この接続名を用いてユーザーはData Segment Managerにアクセスすることができる。
168 OqReceiver setKeysہAodsput܂updateۂ̈managerKeyɂB 172 前述したReceiver にsetKeyを行う際、odsでputまたはupdateする際の引数のmanagerKeyがこれにあたる。
169 173
170 \subsection{Topology Manager̎gp@} 174 \subsection{Topology Managerの使用方法}
171 Topology NodeNۂɃR}hCƂTopology ManagerIPAhXƃ|[gԍwB 175 Topology Nodeを起動する際にコマンドライン引数としてTopology ManagerのIPアドレスとポート番号を指定をする。
172 main֐TopologyNodenewsΗǂB 176 そしてmain関数内でTopologyNodeをnewを行えば良い。
173 TopologyNodȇ Alice f[̐ݒIuWFNgAStart Code SegmentłB 177 TopologyNodeの第一引数は Alice デーモンの設定オブジェクト、第二引数はStart Code Segmentである。
174 Ŏw肵AStart Code Segmentg|W[sB 178 ここで指定した、Start Code Segmentがトポロジーが完成した後実行される。
175 179
176 % }{ 180 % }{
177 \section{Q[̗}\label{sec:Enum}\label{sec:item} 181 \section{ゲームの例題}\label{sec:Enum}\label{sec:item}
178 \subsection{} 182 \subsection{水族館}
179 쐬͐قłB̃NCAg̃fBXvC𕡐̋ړĂ̂łB͉ʂ̒[܂ňړƎ̉ʏォ͏Aʂ̃NCAg̉ʂ̒[狛oĂB܂ÂC̓NCAgڑ삷邱ƂłBg|W[TopologyManagerɂc[ɍ\ĂB 183 今回作成した例題は水族館である。複数のクライアントのディスプレイを複数の魚が移動していくものである。魚は画面の端まで移動すると自分の画面上からは消え、別のクライアントの画面の端から魚が出てくる。また、魚のうち一匹はクライアントが直接操作することができる。トポロジーはTopologyManagerによりツリー状に構成してある。
180 \subsection{f[^̓`} 184 \subsection{データの伝搬}
181 185
182 \begin{enumerate} 186 \begin{enumerate}
183 \item [U[𑀍삷܂Code Segmentɂ苛̍WXVB 187 \item ユーザーが魚を操作するまたはCode Segmentにより魚の座標が更新される。
184 \item ʂɕ\邽߂SetLocation (Code Segment)sۂɋ̃IuWFNgɃZbgʂɔfB 188 \item 画面に表示させるためのSetLocation (Code Segment)が実行され実際に魚のオブジェクトにセットされ画面に反映される。
185 \item Update(Code Segment)FishPosition(̍Wf[^)nB 189 \item Update(Code Segment)にFishPosition(魚の座標データ)が渡される。
186 \item Updatelist(M҃Xg)nB 190 \item Updateにlist(送信者リスト)が渡される。
187 \item UpdatesAlistɃf[^MBA̎FishPositionɂ͑M񂪕tĂ̂ŁAMɂ͑MȂB 191 \item Updateが実行され、listを元にデータが送信される。ただし、この時にFishPositionには送信元情報が付加されているので、送信元には送信されない。
188 \item eclient2 - 4sB 192 \item 各clientで2 - 4が実行される。
189 \end{enumerate} 193 \end{enumerate}
190 194
191 \section{]} 195 \section{評価}
192 196
193 197
194 \section{܂Ƃ߂ƍ̉ۑ} 198 \section{まとめと今後の課題}
195 199
196 200
197 \end{document} 201 \end{document}