Mercurial > hg > Papers > 2015 > nozomi-sigos
comparison paper/sigos.tex @ 1:e13be99f69b6
can't view graphix correct place
author | Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 05 May 2015 16:37:38 +0900 |
parents | 0127effb8fcd |
children | 74e97b9a4caf |
comparison
equal
deleted
inserted
replaced
0:0127effb8fcd | 1:e13be99f69b6 |
---|---|
1 \documentclass[techrep]{ipsjpapers} | 1 \documentclass[techrep, ,dvipdfmx]{ipsjpapers} |
2 \usepackage[dvipdfm]{graphicx} | 2 \usepackage[dvipdfmx]{color} |
3 \usepackage[dvipdfmx]{graphicx} | |
3 \usepackage{url} | 4 \usepackage{url} |
4 \usepackage{listings} | 5 \usepackage{listings} |
5 \usepackage{mediabb} | 6 \usepackage{mediabb} |
6 \lstset{% | 7 \lstset{% |
7 language={C++},%使用言語 | 8 language={C++},%使用言語 |
97 DSはAliceが内部にもつデータベースによって管理されている。DSに対応する一意のkeyが設定されており、そのkeyを用いてデータベースを操作する。 | 98 DSはAliceが内部にもつデータベースによって管理されている。DSに対応する一意のkeyが設定されており、そのkeyを用いてデータベースを操作する。 |
98 | 99 |
99 CSは実行に必要なDSが揃うと実行されるという性質を持ち、入力されたDSに応じた結果が出力される。 | 100 CSは実行に必要なDSが揃うと実行されるという性質を持ち、入力されたDSに応じた結果が出力される。 |
100 CSを実行するために必要な入力DSはInputDS、CSが計算を行った後に出力されるDSはOutput DSと呼ばれる。データの依存関係にないCSは並列実行が可能であるため、並列度を上げるためにはCSの処理内容を細かく分割して依存するデータを少なくするのが望ましい。 | 101 CSを実行するために必要な入力DSはInputDS、CSが計算を行った後に出力されるDSはOutput DSと呼ばれる。データの依存関係にないCSは並列実行が可能であるため、並列度を上げるためにはCSの処理内容を細かく分割して依存するデータを少なくするのが望ましい。 |
101 | 102 |
102 \subsection{ComputationとMeta Computation} | |
103 AliceのComputationは、keyで指し示されるDSを待ち合わせてCSを実行させると定義できる。 | |
104 それに対して、AliceのMeta Computationは、AliceのComputationを支えているComputationのプログラミングと定義できる。 | |
105 | |
106 例えば、トポロジーを指定するAPIはMeta Computationである。Aliceが動作するためにはトポロジーを決める必要がある。つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。トポロジーが決定するとそのトポロジーを構成する計算が行われる。トポロジーを指定するAPIはその構成の計算をプログラミングして変更するものである。 | |
107 他にも再接続の動作を決めるAPIや切断時の動作を決めるAPIはMeta Computationである。 | |
108 | |
109 これらのMeta ComputationがAliceのComputationに影響することはない。プログラマーはCSを記述する際にトポロジーや切断、再接続という状況を予め想定した処理にする必要はない。プログラマーは目的の処理だけ記述する。そして、切断や再接続が起こった場合の処理を記述しMeta Computationで指定する。 | |
110 このようにプログラムすることで、通常処理と例外処理を分離することができるため、シンプルなプログラムを記述できる。 | |
111 | |
112 \subsection{Data Segment} | 103 \subsection{Data Segment} |
113 複数のスレッドから1つのデータに変更を行うためには、データの不整合を防ぐためのlockが必要になる。複数の関係のない要素を1つのデータオブジェクトで表現した場合、全ての操作でlockが必要になる。このlockがスケラビリティーを低下させる。つまりデータのサイズも並列計算には重要である。 | 104 複数のスレッドから1つのデータに変更を行うためには、データの不整合を防ぐためのlockが必要になる。複数の関係のない要素を1つのデータオブジェクトで表現した場合、全ての操作でlockが必要になる。このlockがスケラビリティーを低下させる。つまりデータのサイズも並列計算には重要である。 |
114 | 105 |
115 Aliceはデータを細かく分割して記述する。その細かく分割されたデータをDSと呼ぶ。 | 106 Aliceはデータを細かく分割して記述する。その細かく分割されたデータをDSと呼ぶ。 |
116 実際には特定のオブジェクトにマッピングされ、マッピングされたクラスを通してアクセスされる。 | 107 実際には特定のオブジェクトにマッピングされ、マッピングされたクラスを通してアクセスされる。 |
119 DSは実際にはqueueに保存される。queueには対になるkeyが存在し、keyの数だけqueueが存在する。 | 110 DSは実際にはqueueに保存される。queueには対になるkeyが存在し、keyの数だけqueueが存在する。 |
120 この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 この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に書き込まれる。 |
121 | 112 |
122 \begin{figure}[htbp] | 113 \begin{figure}[htbp] |
123 \begin{center} | 114 \begin{center} |
124 \includegraphics[width=60mm]{images/remote_datasegment.pdf} | 115 \includegraphics[scale=0.3]{images/remote_datasegment.pdf} |
125 \end{center} | 116 \end{center} |
126 \caption{Remote DSMは他のノードのLocal DSMのproxy } | 117 \caption{Remote DSMは他のノードのLocal DSMのproxy } |
127 \label{fig:RemoteDSM} | 118 \label{fig:RemoteDSM} |
128 \end{figure} | 119 \end{figure} |
129 | 120 |
130 \subsection{Data Segment API} | 121 \subsection{Data Segment API} |
131 以下のData Segment APIを用いてデータベースにアクセスする。 | 122 以下のData Segment APIを用いてデータベースにアクセスする。 |
132 putとupdateはDSを追加する際に、peekとtakeはDSを取得する際に使用する。 | 123 putとupdateはDSを追加する際に、peekとtakeはDSを取得する際に使用する。 |
133 | 124 |
134 \begin{itemize} | 125 \begin{itemize} |
135 \item {\ttfamily void put(String key, Object val)} | 126 \item {\ttfamily void put(String managerKey, String key, \\ Object val)} |
136 \end{itemize} | 127 \end{itemize} |
137 DSをqueueに追加するためのAPIである。第一引数に対応するqueueに対してDSを追加している。 | 128 DSをqueueに追加するためのAPIである。第一引数で指定したDSMの中の、第二引数に対応するqueueに対してDSを追加している。 |
138 \begin{itemize} | 129 \begin{itemize} |
139 \item {\ttfamily void update(String key, Object val)} | 130 \item {\ttfamily void update(String managerKey, String key, \\ Object val)} |
140 \end{itemize} | 131 \end{itemize} |
141 updateもqueueに追加するためのAPIである。putとの違いは、先頭のDSを削除してからDSを追加することである。そのためAPI実行前後でqueueの中にあるDSの個数は変わらない。 | 132 updateもqueueに追加するためのAPIである。putとの違いは、先頭のDSを削除してからDSを追加することである。そのためAPI実行前後でqueueの中にあるDSの個数は変わらない。 |
142 | 133 |
143 \begin{itemize} | 134 \begin{itemize} |
144 \item {\ttfamily void take(String key)} | 135 \item {\ttfamily void take(String managerKey, String key)} |
145 \end{itemize} | 136 \end{itemize} |
146 takeはDSを読み込むためのAPIである。読み込まれたDSは削除される。要求したDSが存在しなければ、CSの待ち合わせ (Blocking)が起こる。putやupdateによりDSに更新があった場合、takeが直ちに実行される。 | 137 takeはDSを読み込むためのAPIである。読み込まれたDSは削除される。要求したDSが存在しなければ、CSの待ち合わせ (Blocking)が起こる。putやupdateによりDSに更新があった場合、takeが直ちに実行される。 |
147 | 138 |
148 \begin{itemize} | 139 \begin{itemize} |
149 \item {\ttfamily void peek(String key)} | 140 \item {\ttfamily void peek(String managerKey, String key)} |
150 \end{itemize} | 141 \end{itemize} |
151 peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。 | 142 peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。 |
152 | 143 |
153 | 144 |
154 \section{Code Segment} | 145 \section{Code Segment} |
175 このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 | 166 このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 |
176 | 167 |
177 ソースコード \ref{src:StartCodeSegment}は、5行目で次に実行させたいCS(ソースコード \ref{src:CodeSegment})を作成している。8行目でOutput DSMを通してLocal DSMに対してDSをputしている。 | 168 ソースコード \ref{src:StartCodeSegment}は、5行目で次に実行させたいCS(ソースコード \ref{src:CodeSegment})を作成している。8行目でOutput DSMを通してLocal DSMに対してDSをputしている。 |
178 Output DSMはCSの{\tt ods}というフィールドを用いてアクセスする。 | 169 Output DSMはCSの{\tt ods}というフィールドを用いてアクセスする。 |
179 Output DSMは{\tt put}と{\tt update}を実行することができる。 | 170 Output DSMは{\tt put}と{\tt update}を実行することができる。 |
180 \begin{itemize} | |
181 \item \verb+void put(String managerKey, String key, Object val)+ | |
182 \item \verb+void update(String managerKey, String key, Object val)+ | |
183 \end{itemize} | |
184 TestCodeSegmentはこの"cnt"というkeyに対して依存関係があり、8行目でupdateが行われるとTestCodeSegmentは実行される。 | 171 TestCodeSegmentはこの"cnt"というkeyに対して依存関係があり、8行目でupdateが行われるとTestCodeSegmentは実行される。 |
185 | 172 |
186 ソースコード\ref{src:CodeSegment}は、0から10までインクリメントする例題である。 | 173 ソースコード\ref{src:CodeSegment}は、0から10までインクリメントする例題である。 |
187 2行目で取得されたDSが格納される受け皿を作る。Input DSMがもつcreateメソッド使うことで作成できる。 | 174 2行目で取得されたDSが格納される受け皿を作る。Input DSMがもつcreateメソッド使うことで作成できる。 |
188 \begin{itemize} | 175 \begin{itemize} |
211 runメソッドの内容としては10行目で取得されたDSをInteger型に変換してcountに代入している。 | 198 runメソッドの内容としては10行目で取得されたDSをInteger型に変換してcountに代入している。 |
212 16行目で もう一度TestCodeSegmentのCSが作られる。 | 199 16行目で もう一度TestCodeSegmentのCSが作られる。 |
213 17行目でcountの値をインクリメントしてLocal DSMに値を追加する。 | 200 17行目でcountの値をインクリメントしてLocal DSMに値を追加する。 |
214 13行目が終了条件であり、countの値が10になれば終了する。 | 201 13行目が終了条件であり、countの値が10になれば終了する。 |
215 | 202 |
203 \subsection{ComputationとMeta Computation} | |
204 AliceのComputationは、keyで指し示されるDSを待ち合わせてCSを実行させると定義できる。 | |
205 それに対して、AliceのMeta Computationは、AliceのComputationを支えているComputationのプログラミングと定義できる。 | |
206 | |
207 例えば、トポロジーを指定するAPIはMeta Computationである。Aliceが動作するためにはトポロジーを決める必要がある。つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。トポロジーが決定するとそのトポロジーを構成する計算が行われる。トポロジーを指定するAPIはその構成の計算をプログラミングして変更するものである。 | |
208 他にも再接続の動作を決めるAPIや切断時の動作を決めるAPIはMeta Computationである。 | |
209 | |
210 これらのMeta ComputationがAliceのComputationに影響することはない。プログラマーはCSを記述する際にトポロジーや切断、再接続という状況を予め想定した処理にする必要はない。プログラマーは目的の処理だけ記述する。そして、切断や再接続が起こった場合の処理を記述しMeta Computationで指定する。 | |
211 このようにプログラムすることで、通常処理と例外処理を分離することができるため、シンプルなプログラムを記述できる。 | |
212 | |
213 | |
216 \section{Meta Data Segment} | 214 \section{Meta Data Segment} |
217 DSは、アプリケーションに管理されているデータのことである。アプリケーションを構成するCSによってその値は変更される。 | 215 DSは、アプリケーションに管理されているデータのことである。アプリケーションを構成するCSによってその値は変更される。 |
218 それに対してMeta DSは、分散フレームワークAliceが管理しているデータである。Aliceを構成するCSによってのみ、その値は変更される。一部のMeta DSはアプリケーションに利用することができる。 | 216 それに対してMeta DSは、分散フレームワークAliceが管理しているデータである。Aliceを構成するCSによってのみ、その値は変更される。一部のMeta DSはアプリケーションに利用することができる。 |
219 | 217 |
220 例えば、"start"というkeyでは、ノードがStart CSを実行可能かどうかの状態を表す。他にも"\_CLIST"というkeyでは、利用可能なRemote DSの一覧が管理されている。ユーザーはこの一覧にある名前を指定することで、動的にDSの伝搬などを行うことができる。 | 218 例えば、"start"というkeyでは、ノードがStart CSを実行可能かどうかの状態を表す。他にも"\_CLIST"というkeyでは、利用可能なRemote DSの一覧が管理されている。ユーザーはこの一覧にある名前を指定することで、動的にDSの伝搬などを行うことができる。 |
227 \section{Meta Code Segment} | 225 \section{Meta Code Segment} |
228 CSはアプリケーションを動作させるために必要なタスクであり、ユーザーによって定義される。 | 226 CSはアプリケーションを動作させるために必要なタスクであり、ユーザーによって定義される。 |
229 それに対してMeta CSはAliceを構成するタスクである。つまりMeta CSの群はAliceのComputationと言い換えることができる。一部のみユーザーが定義をすることができ、Aliceの挙動を変更することができる。 | 227 それに対してMeta CSはAliceを構成するタスクである。つまりMeta CSの群はAliceのComputationと言い換えることができる。一部のみユーザーが定義をすることができ、Aliceの挙動を変更することができる。 |
230 | 228 |
231 | 229 |
232 \input{chapter2} | 230 |
231 | |
232 \section{AliceVNC} | |
233 AliceVNCは、当研究室で開発を行っているTreeVNCをAliceを用いて実装された、授業向け画面共有システムである。 | |
234 Aliceが実用的なアプリケーションを記述する能力をもつことを確認するために作成した。 | |
235 | |
236 授業でVNCを使う場合、1つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう(図\ref{fig:vnc})。この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである(図\ref{fig:treestructure})。TreeVNCは、TightVNCのソースコードを利用して開発されている。 | |
237 | |
238 \begin{figure}[htbp] | |
239 \begin{center} | |
240 \includegraphics[width=80mm]{images/vnc.pdf} | |
241 \end{center} | |
242 \caption{VNCの構造 } | |
243 \label{fig:vnc} | |
244 \end{figure} | |
245 | |
246 \begin{figure}[htbp] | |
247 \begin{center} | |
248 \includegraphics[width=120mm]{images/treestructure.pdf} | |
249 \end{center} | |
250 \caption{TreeVNC, AliceVNCの構造 } | |
251 \label{fig:treestructure} | |
252 \end{figure} | |
253 | |
254 | |
255 | |
233 % \input{chapter3} | 256 % \input{chapter3} |
234 % \input{chapter4} | |
235 % \input{chapter5} | 257 % \input{chapter5} |
236 % \input{conclusion} | 258 % \input{conclusion} |
237 | 259 |
238 \nocite{*} | 260 \nocite{*} |
239 %\nocite{opencl} | 261 %\nocite{opencl} |