Mercurial > hg > Papers > 2015 > nozomi-sigos
annotate paper/sigos.tex @ 4:683044bd29ed
resolve view pdf
author | Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 05 May 2015 17:26:13 +0900 |
parents | f203f5c0d2ca |
children | 4a7fa91ef60a |
rev | line source |
---|---|
1
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1 \documentclass[techrep, ,dvipdfmx]{ipsjpapers} |
2 | 2 \usepackage[dvipdfmx]{graphicx} |
1
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
3 \usepackage[dvipdfmx]{color} |
0 | 4 \usepackage{url} |
5 \usepackage{listings} | |
6 \lstset{% | |
7 language={C++},%使用言語 | |
8 basicstyle={\small},%書体 | |
9 commentstyle={\small\itshape},%コメントの書体 | |
10 keywordstyle={\small\bfseries},%キーワードの書体 | |
11 %identifierstyle={\small},% | |
12 %ndkeywordstyle={\small},% | |
13 stringstyle={\small},%文字列の書体 | |
14 frame={trlb},%外枠 | |
15 breaklines=true,%改行 | |
16 columns=[l]{fullflexible},% | |
17 xrightmargin=0zw,% | |
18 xleftmargin=3zw,% | |
19 %numbers=none,%行番号の表示 | |
20 %numberstyle={\scriptsize},%行番号の書体 | |
21 %numbersep=1zw,% | |
22 %stepnumber=1, | |
23 lineskip=-0.5ex,% | |
24 captionpos=b,%キャプションの位置 | |
25 } | |
26 \renewcommand{\lstlistingname}{Code} | |
27 \input{dummy.tex} %% Font | |
28 | |
29 % ユーザが定義したマクロなど. | |
30 \makeatletter | |
31 | |
32 \begin{document} | |
33 | |
34 % 和文表題 | |
35 \title{分散フレームワークAliceの圧縮機能} | |
36 % 英文表題 | |
37 \etitle{} | |
38 | |
39 % 所属ラベルの定義 | |
40 \affilabel{1}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.} | |
41 \affilabel{2}{琉球大学大学院理工学研究科情報工学専攻 \\Interdisciplinary Information Engineering, Graduate School of Engineering and Science, University of the Ryukyus.} | |
42 \affilabel{3}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.} | |
43 | |
44 % 和文著者名 | |
45 \author{ | |
46 照屋 のぞみ\affiref{1}\and | |
47 杉本 優\affiref{2}\and | |
48 河野 真治\affiref{3} | |
49 } | |
50 | |
51 % 英文著者名 | |
52 \eauthor{ | |
53 Nozomi TERUYA\affiref{1}\and | |
54 Yu SUGIMOTO\affiref{2}\and | |
55 Shinji KONO\affiref{3} | |
56 } | |
57 | |
58 % 連絡先(投稿時に必要.製版用では無視される.) | |
59 \contact{照屋 のぞみ\\ | |
60 〒903-0213 沖縄県西原町千原1番地\\ | |
61 琉球大学工学部情報工学科\\ | |
62 TEL: (098)895-2221\qquad FAX: (098)895-8727\\ | |
63 email: kokubo@cr.ie.u-ryukyu.ac.jp} | |
64 | |
65 % 和文概要 | |
66 \begin{abstract} | |
67 当研究室ではデータをData Segment、タスクをCode Segmentという単位で分割して記述する手法を提唱しており、そのプロトタイプとして並列分散フレームワークAliceを開発している。 | |
68 本研究ではAliceに実用的なアプリケーションを作成するために必要な動的なトポロジーを管理する機能とAliceの制御を行えるメタ計算を追加した。また、通信時におけるData Segmentの多態性を実現するため、Data SegmentをObject型、MessagePackを使ったByteArray型、圧縮されたByteArray型の3つの形式で表現できるメタ計算の設計と実装、性能評価を行った。 | |
69 | |
70 | |
71 \end{abstract} | |
72 | |
73 % 英文概要 仮 | |
74 \begin{eabstract} | |
75 Alice is a prototype framework for distributed programming, which uses Data Segment and Code Segment as programming units. We checked Alice has an ability to write dis- tributed program using aquarium example, distributed database Jungle and share screen system AliceVNC . | |
76 In this paper, we add functions which control dynamic topology and Alice computation. And we show Alice has an ability to write useful application. | |
77 Furthermore we improve Alice performance. So Alice works 12% faster and has same performance as Federated Linda. | |
78 \end{eabstract} | |
79 | |
80 % 表題などの出力 | |
81 \maketitle | |
82 | |
83 % 本文はここから始まる | |
84 | |
85 \section{研究背景と目的} | |
86 当研究室ではデータをData Segment、タスクをCode Segmentという単位で分割して記述する並列分散フレームワークAliceの開発を行っている。Aliceでは分散環境の構築に必要な処理をMeta Computationとして提供することで、スケーラブルな分散プログラムを信頼性高く記述できる環境を実現している。 | |
87 | |
88 Alice が分散プログラムを記述する能力を有することは確認された。だが、実用的な分散プログラムを作成するためには、ノードの切断・再接続時に対応した処理を行いたい場合や圧縮されたデータ形式で通信を行いたい場合がある。 | |
89 | |
90 本研究では、 Alice の Computation の 制御を行う Meta Computation を実装した。プログラムに Alice の制御を行うメタプログラムを記述することにより切断や再接続の状況に応じた処理を元のコードを変更することなく指定することができる。また、圧縮機能を持ったDataSegmentManagerを追加することによりData Segmentの多態性を実現した。 | |
91 そして、 TreeVNC と TreeVNC を Alice を用いて実装した AliceVNC の比較をコードの観点から評価を行った。 | |
92 | |
93 | |
94 \section{分散フレームワーク Alice の概要} | |
95 \subsection{Data SegmentとCode Segment} | |
96 AliceはデータをData Segment、(以下DS)タスクをとCode Segment(以下CS)という単位に分割してプログラミングを行う。 | |
97 DSはAliceが内部にもつデータベースによって管理されている。DSに対応する一意のkeyが設定されており、そのkeyを用いてデータベースを操作する。 | |
98 | |
99 CSは実行に必要なDSが揃うと実行されるという性質を持ち、入力されたDSに応じた結果が出力される。 | |
100 CSを実行するために必要な入力DSはInputDS、CSが計算を行った後に出力されるDSはOutput DSと呼ばれる。データの依存関係にないCSは並列実行が可能であるため、並列度を上げるためにはCSの処理内容を細かく分割して依存するデータを少なくするのが望ましい。 | |
101 | |
102 \subsection{Data Segment} | |
103 複数のスレッドから1つのデータに変更を行うためには、データの不整合を防ぐためのlockが必要になる。複数の関係のない要素を1つのデータオブジェクトで表現した場合、全ての操作でlockが必要になる。このlockがスケラビリティーを低下させる。つまりデータのサイズも並列計算には重要である。 | |
104 | |
105 Aliceはデータを細かく分割して記述する。その細かく分割されたデータをDSと呼ぶ。 | |
106 実際には特定のオブジェクトにマッピングされ、マッピングされたクラスを通してアクセスされる。 | |
107 | |
108 \subsection{Data Segment Manager} | |
109 DSは実際にはqueueに保存される。queueには対になるkeyが存在し、keyの数だけqueueが存在する。 | |
110 このkeyを指定してDSの保存、取得を行う。queueの集合体はデータベースとして捉えられる。このデータベースをAliceではDS Manager(以下DSM)と呼ぶ。DSMにはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。Remote DSMは他のノードのLocal DSMのproxyであり、接続しているノードの数だけ存在する。(図\ref{fig:RemoteDSM})Remote DSMに対して書き込むと対応するノードのLocal DSMに書き込まれる。 | |
111 | |
112 \begin{figure}[htbp] | |
113 \begin{center} | |
4 | 114 \includegraphics[width=80mm]{images/remote_datasegment.pdf} |
0 | 115 \end{center} |
116 \caption{Remote DSMは他のノードのLocal DSMのproxy } | |
117 \label{fig:RemoteDSM} | |
118 \end{figure} | |
119 | |
120 \subsection{Data Segment API} | |
121 以下のData Segment APIを用いてデータベースにアクセスする。 | |
122 putとupdateはDSを追加する際に、peekとtakeはDSを取得する際に使用する。 | |
123 | |
124 \begin{itemize} | |
1
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
125 \item {\ttfamily void put(String managerKey, String key, \\ Object val)} |
0 | 126 \end{itemize} |
1
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
127 DSをqueueに追加するためのAPIである。第一引数で指定したDSMの中の、第二引数に対応するqueueに対してDSを追加している。 |
0 | 128 \begin{itemize} |
1
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
129 \item {\ttfamily void update(String managerKey, String key, \\ Object val)} |
0 | 130 \end{itemize} |
131 updateもqueueに追加するためのAPIである。putとの違いは、先頭のDSを削除してからDSを追加することである。そのためAPI実行前後でqueueの中にあるDSの個数は変わらない。 | |
132 | |
133 \begin{itemize} | |
1
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
134 \item {\ttfamily void take(String managerKey, String key)} |
0 | 135 \end{itemize} |
136 takeはDSを読み込むためのAPIである。読み込まれたDSは削除される。要求したDSが存在しなければ、CSの待ち合わせ (Blocking)が起こる。putやupdateによりDSに更新があった場合、takeが直ちに実行される。 | |
137 | |
138 \begin{itemize} | |
1
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
139 \item {\ttfamily void peek(String managerKey, String key)} |
0 | 140 \end{itemize} |
141 peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。 | |
142 | |
143 | |
144 \section{Code Segment} | |
145 Alice上で実行されるタスクの単位がCSである。ユーザーはCSを組み合わせることでプログラミングを行う。CSをユーザーが記述する際に、内部で使用するDSの作成を記述する。 | |
146 | |
147 Input DS と Output DSはCSに用意されているAPIを用いて作成する。 | |
148 Input DSは、LocalかRemoteか、またkeyを指定する必要がある。CSは、記述したInput DSが全て揃うとThread poolに送られ、実行される。 | |
149 | |
150 Output DSもLocalかRemoteか、またkeyを指定する必要がある。 | |
151 Inputの場合はsetKeyを呼ぶ際、Outputの場合はput(またはupdate)の際にノードとkeyの指定を行っている。 | |
152 しかし、どの時点でノードとkeyの指定を行えばよいか、どのようなAPIを用意するべきかは、議論の余地がある。 | |
153 | |
154 \section{Code Segmentの記述方法} | |
155 CSをユーザーが記述する際にはCSを継承して記述する(ソースコード \ref{src:StartCodeSegment} ,\ref{src:CodeSegment})。 | |
156 継承することによりCode Segmentで使用するAPIを利用する事ができる。 | |
157 | |
158 \begin{table}[html] | |
159 \lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java} | |
160 \lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java} | |
161 \end{table} | |
162 | |
163 Alice には、Start CS (ソースコード \ref{src:StartCodeSegment})というC の main に相当するような最初に実行される CS がある。 | |
164 Start CSはどのDSにも依存しない。つまりInput DSを持たない。 | |
165 このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 | |
166 | |
167 ソースコード \ref{src:StartCodeSegment}は、5行目で次に実行させたいCS(ソースコード \ref{src:CodeSegment})を作成している。8行目でOutput DSMを通してLocal DSMに対してDSをputしている。 | |
168 Output DSMはCSの{\tt ods}というフィールドを用いてアクセスする。 | |
169 Output DSMは{\tt put}と{\tt update}を実行することができる。 | |
170 TestCodeSegmentはこの"cnt"というkeyに対して依存関係があり、8行目でupdateが行われるとTestCodeSegmentは実行される。 | |
171 | |
172 ソースコード\ref{src:CodeSegment}は、0から10までインクリメントする例題である。 | |
173 2行目で取得されたDSが格納される受け皿を作る。Input DSMがもつcreateメソッド使うことで作成できる。 | |
174 \begin{itemize} | |
175 \item {\ttfamily Receiver create(CommandType type)} | |
176 \end{itemize} | |
177 | |
178 引数にはCommandTypeが取られ、指定できるCommandTypeは{\tt PEEK}または{\tt TAKE}である。 | |
179 Input DSM はCSの{\tt ids}というフィールドを用いてアクセスする。 | |
180 | |
181 4行目から6行目はコンストラクタである。コンストラクタはオブジェクト指向のプログラミング言語で新たなオブジェクトを生成する際に呼び出されて内容の初期化を行う関数である。 | |
182 | |
183 TestCodeSegmentのコンストラクタが呼ばれた際には、 | |
184 \begin{enumerate} | |
185 \item TestCodeSegmentが持つフィールド変数Receiver input1の定義が行われる。 | |
186 \item 次にCSのコンストラクタが呼ばれ、CSが持つフィールド変数の定義と初期化が行われる。 | |
187 \item {\tt ids.create(CommandType.TAKE)}が行われ、input1の初期化が行われる。 | |
188 \item 最後にTestCodeSegmentのコンストラクタの5行目が実行される。 | |
189 \end{enumerate} | |
190 | |
191 5行目はInput DSMがもつsetKeyメソッドによりLocal DSMからDSを取得している。 | |
192 \begin{itemize} | |
193 \item \verb+void setKey(String managerKey, String key)+ | |
194 \end{itemize} | |
195 setKeyメソッドにより、どのDSMのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定できる。コマンドの結果がレスポンスとして届き次第CSは実行される。 | |
196 | |
197 runメソッドの内容としては10行目で取得されたDSをInteger型に変換してcountに代入している。 | |
198 16行目で もう一度TestCodeSegmentのCSが作られる。 | |
199 17行目でcountの値をインクリメントしてLocal DSMに値を追加する。 | |
200 13行目が終了条件であり、countの値が10になれば終了する。 | |
201 | |
1
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
202 \subsection{ComputationとMeta Computation} |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
203 AliceのComputationは、keyで指し示されるDSを待ち合わせてCSを実行させると定義できる。 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
204 それに対して、AliceのMeta Computationは、AliceのComputationを支えているComputationのプログラミングと定義できる。 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
205 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
206 例えば、トポロジーを指定するAPIはMeta Computationである。Aliceが動作するためにはトポロジーを決める必要がある。つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。トポロジーが決定するとそのトポロジーを構成する計算が行われる。トポロジーを指定するAPIはその構成の計算をプログラミングして変更するものである。 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
207 他にも再接続の動作を決めるAPIや切断時の動作を決めるAPIはMeta Computationである。 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
208 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
209 これらのMeta ComputationがAliceのComputationに影響することはない。プログラマーはCSを記述する際にトポロジーや切断、再接続という状況を予め想定した処理にする必要はない。プログラマーは目的の処理だけ記述する。そして、切断や再接続が起こった場合の処理を記述しMeta Computationで指定する。 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
210 このようにプログラムすることで、通常処理と例外処理を分離することができるため、シンプルなプログラムを記述できる。 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
211 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
212 |
0 | 213 \section{Meta Data Segment} |
214 DSは、アプリケーションに管理されているデータのことである。アプリケーションを構成するCSによってその値は変更される。 | |
215 それに対してMeta DSは、分散フレームワークAliceが管理しているデータである。Aliceを構成するCSによってのみ、その値は変更される。一部のMeta DSはアプリケーションに利用することができる。 | |
216 | |
217 例えば、"start"というkeyでは、ノードがStart CSを実行可能かどうかの状態を表す。他にも"\_CLIST"というkeyでは、利用可能なRemote DSの一覧が管理されている。ユーザーはこの一覧にある名前を指定することで、動的にDSの伝搬などを行うことができる。 | |
218 | |
219 また、Input DSに付随しているものもある。Input DSはCS内部でReceiverという入れ物に格納される。ユーザーは、Receiverに対して操作することでDSを入手できる。 | |
220 このReceiverには、fromというフィールドがあり、このDSを誰がputしたという情報が入っている。この情報をデータの伝搬する際に利用することで、DSをputしたノードに送り返すことを防ぐことができる。 | |
221 | |
222 Meta DSはDS同様にDS APIを用いて取得できる。 | |
223 | |
224 \section{Meta Code Segment} | |
225 CSはアプリケーションを動作させるために必要なタスクであり、ユーザーによって定義される。 | |
226 それに対してMeta CSはAliceを構成するタスクである。つまりMeta CSの群はAliceのComputationと言い換えることができる。一部のみユーザーが定義をすることができ、Aliceの挙動を変更することができる。 | |
227 | |
228 | |
1
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
229 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
230 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
231 \section{AliceVNC} |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
232 AliceVNCは、当研究室で開発を行っているTreeVNCをAliceを用いて実装された、授業向け画面共有システムである。 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
233 Aliceが実用的なアプリケーションを記述する能力をもつことを確認するために作成した。 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
234 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
235 授業でVNCを使う場合、1つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう(図\ref{fig:vnc})。この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである(図\ref{fig:treestructure})。TreeVNCは、TightVNCのソースコードを利用して開発されている。 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
236 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
237 \begin{figure}[htbp] |
2 | 238 \begin{center} |
4 | 239 \includegraphics[width=80mm]{images/vnc.pdf} |
2 | 240 \end{center} |
241 \caption{VNCの構造 } | |
242 \label{fig:vnc} | |
1
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
243 \end{figure} |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
244 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
245 \begin{figure}[htbp] |
2 | 246 \begin{center} |
4 | 247 \includegraphics[width=80mm]{images/treestructure.pdf} |
2 | 248 \end{center} |
249 \caption{TreeVNC, AliceVNCの構造 } | |
250 \label{fig:treestructure} | |
1
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
251 \end{figure} |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
252 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
253 |
e13be99f69b6
can't view graphix correct place
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
254 |
0 | 255 % \input{chapter3} |
256 % \input{chapter5} | |
257 % \input{conclusion} | |
258 | |
259 \nocite{*} | |
260 %\nocite{opencl} | |
261 %\nocite{opencl:ref} | |
262 %\nocite{opencl:applied} | |
263 %\nocite{yutaka:os} | |
264 %\bibliographystyle{ipsjunsrt} | |
265 %\bibliography{sigos} | |
266 %\bibliography{cerium,book} | |
267 | |
268 | |
269 \end{document} |