Mercurial > hg > Papers > 2016 > nozomi-thesis
annotate paper/main.tex @ 10:90aaf305aed6 default tip
add presen
| author | Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 18 Feb 2016 09:06:13 +0900 |
| parents | ef17e4dc6216 |
| children |
| rev | line source |
|---|---|
| 0 | 1 \documentclass[a4j,12pt]{jreport} |
| 4 | 2 \usepackage[dvipdfmx,hiresbb]{graphicx} |
| 0 | 3 \usepackage{mythesis} |
| 4 \usepackage{multirow} | |
| 4 | 5 \usepackage{listings} |
| 6 \usepackage{url} | |
| 7 \lstset{% | |
| 8 language={Java},%使用言語 | |
| 9 basicstyle={\small},%書体 | |
| 10 commentstyle={\small\itshape},%コメントの書体 | |
| 11 keywordstyle={\small\bfseries},%キーワードの書体 | |
| 12 %identifierstyle={\small},% | |
| 13 %ndkeywordstyle={\small},% | |
| 14 stringstyle={\small},%文字列の書体 | |
| 15 frame={trlb},%外枠 | |
| 16 breaklines=true,%改行 | |
| 17 columns=[l]{fullflexible},% | |
| 18 xrightmargin=0zw,% | |
| 19 xleftmargin=3zw,% | |
| 20 numbers=left,%行番号の表示 | |
| 21 numberstyle={\scriptsize},%行番号の書体 | |
| 22 numbersep=1zw,% | |
| 23 stepnumber=1, | |
| 24 lineskip=-0.5ex,% | |
| 25 captionpos=b,%キャプションの位置 | |
| 26 } | |
| 27 \renewcommand{\lstlistingname}{Code} | |
| 0 | 28 \usepackage{here} |
| 29 \setlength{\itemsep}{-1zh} | |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
30 \title{分散フレームワークAliceのMeta Data Segment} |
| 0 | 31 \icon{ |
| 4 | 32 \includegraphics[width=50mm,bb=0 0 595 842]{fig/ryukyu.pdf} |
| 0 | 33 } |
| 2 | 34 \year{平成27年度 卒業論文} |
| 0 | 35 \belongto{琉球大学工学部情報工学科} |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
36 \author{e125769 照屋 のぞみ \\ 指導教員 {河野 真治} } |
| 0 | 37 %% |
| 38 %% プリアンブルに記述 | |
| 39 %% Figure 環境中で Table 環境の見出しを表示・カウンタの操作に必要 | |
| 40 %% | |
| 41 \makeatletter | |
| 42 \newcommand{\figcaption}[1]{\def\@captype{figure}\caption{#1}} | |
| 43 \newcommand{\tblcaption}[1]{\def\@captype{table}\caption{#1}} | |
| 44 \makeatother | |
| 45 \setlength\abovecaptionskip{0pt} | |
| 46 | |
| 47 \begin{document} | |
| 48 | |
| 49 % タイトル | |
| 50 \maketitle | |
| 51 \baselineskip 17pt plus 1pt minus 1pt | |
| 52 | |
| 53 \setcounter{page}{0} | |
| 54 | |
| 55 \tableofcontents % 目次 | |
| 4 | 56 %\listoffigures % 図目次 |
| 57 %\listoftables % 表目次 | |
| 0 | 58 |
| 59 %以下のように、章ごとに個別の tex ファイルを作成して、 | |
| 60 % main.tex をコンパイルして確認する。 | |
| 61 %章分けは個人で違うので下のフォーマットを参考にして下さい。 | |
| 62 | |
| 63 % はじめに | |
| 8 | 64 \chapter{Meta Computation による分散プ ログラミングの信頼性向上} |
| 4 | 65 \pagenumbering{arabic} |
| 8 | 66 スマートフォンやタブレット端末の普及率が増加している。 |
| 67 それに伴いインターネット利用者数も増加しており、ネットワーク上のサービスには、信頼性とスケーラビリティーが要求される。 | |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
68 ここでいう信頼性とは、定められた環境下で安定して仕様に従った動作を行うことをさす。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
69 またスケーラビリティーとは、サービスの利用者が増大した場合、メモリ等のリソースを追加するだけでサービスを維持できる性能をさす。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
70 しかし、これらをもつ分散プログラムをユーザーが一から記述することは容易ではない。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
71 |
| 8 | 72 これらの問題の解決のために、データをData Segment、タスクをCode Segmentという単位で記述するプログラミング手法を導入した分散フレームワークAlice\cite{senkokenkyu}\cite{senkokenkyu2} の開発を実現した。 |
| 73 Data Segmentは整数や文字列や構造体などの基本的なデータの集まりである。 | |
| 74 Code Segmentは入力となるData Segmentが全て揃ったら処理を開始し計算結果のData Segmentを出力するタスクである。 | |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
75 |
| 8 | 76 さらにAliceでは、計算の本質的な処理をComputation、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。 |
| 77 分散アプリケーションにおいて、分散環境の構築や通信処理部分はMeta Computationと言える。 | |
| 78 それらの処理をAliceがMeta Computationとして提供することで、プログラマは目的の処理の記述だけで分散処理が実現できる。 | |
| 79 また、Meta Computationを指定するだけでComputationを大きく変更せずにプログラムの細かな挙動が変えられるため、変更前の信頼性を破壊せずに拡張ができる。 | |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
80 |
| 8 | 81 本研究では、Alice上に実用的な分散アプリケーションの例題である画面共有システムTreeVNC \cite{treeVNC} を構築した。 |
| 82 構築するにあたって、配信される画面データはAliceのData Segementに対応するため、AliceのMeta Data Segmentとして圧縮機能が必要となった。 | |
| 83 これらの機能はTreeVNCではad-hocに実装されているが、AliceではこれをMeta Computationとして実装した。 | |
| 84 そして、性能・コード量の観点からTreeVNCとの比較を行い、Aliceの実用性を示すと共にAliceのMeta Computationの役割と有効性の評価を行った。 | |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
85 |
| 0 | 86 |
| 87 % 基礎概念 | |
| 2 | 88 \chapter{分散フレームワークAliceの概要} |
| 89 \section{Code Segment と Data Segment} | |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
90 AliceではCode Segment（以下CS）とData Segment（以下DS）の依存関係を記述することでプログラミングを行う。 |
| 4 | 91 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
92 CSは実行に必要なDSが全て揃うと実行される。CSを実行するために必要な入力されるDSのことをInputDS、CSが計算を行った後に出力されるDSのことをOutput DSと呼ぶ。 |
| 4 | 93 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
94 データの依存関係にないCSは並列実行が可能である（図 \ref{fig:CS} ）。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
95 CSの実行においてDSが他のCSから変更を受けることはない。そのためAliceではデータが他から変更され整合性がとれなくなることはない。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
96 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
97 \begin{figure}[htbp] |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
98 \begin{center} |
| 4 | 99 \includegraphics{images/dsandcs2.pdf} |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
100 \end{center} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
101 \caption{CodeSegmentの依存関係 } |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
102 \label{fig:CS} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
103 \end{figure} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
104 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
105 AliceはJavaで実装されており、DSはJava Objectに相当する。CSはRunnableなObject(void run()を持つObject)に相当する。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
106 プログラマがCSを記述する際は、CodeSegmentクラスを継承する。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
107 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
108 DSは数値や文字列などの基本的なデータの集まりを指し、Aliceが内部にもつデータベースによって管理されている。このデータベースをAliceではDS Managerと呼ぶ。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
109 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
110 CSは複数のDS Managerを持っている。DSには対になるString型のkeyが存在し、それぞれのManagerにkeyを指定してDSにアクセスする。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
111 一つのkeyに対して複数のDSをputするとFIFO的に処理される。なのでData Segment Managerは通常のデータベースとは異なる。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
112 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
113 |
| 2 | 114 \section{Data Segment Manager} |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
115 DS Manager（以下DSM）にはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。 |
| 4 | 116 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
117 Remote DSMは他ノードのLocal DSMに対応するproxyであり、接続しているノードの数だけ存在する（図 \ref{fig:Remote DSM} ）。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
118 他ノードのLocal DSMに書き込みたい場合はRemote DSMに対して書き込めば良い。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
119 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
120 Remote DSMを立ち上げるには、DataSegmentクラスが提供するconnectメソッドを用いる。 |
| 4 | 121 接続したいノードのipアドレスとport番号、そして任意のManager名を指定することで立ちあげられる。 |
| 122 その後はManager名を指定してData Segment APIを用いてDSのやり取りを行うため、プログラマはManager名さえ意識すればLocalへの操作もRemoteへの操作も同じ様に扱える。 | |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
123 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
124 \begin{figure}[h] |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
125 \begin{center} |
| 4 | 126 \includegraphics[width=150mm]{images/remote_datasegment.pdf} |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
127 \end{center} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
128 \caption{Remote DSMは他のノードのLocal DSMのproxy } |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
129 \label{fig:Remote DSM} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
130 \end{figure} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
131 |
| 4 | 132 \newpage |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
133 |
| 2 | 134 \section{Data Segment API} |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
135 DSの保存・取得にはAliceが提供するAPIを用いる。 |
| 4 | 136 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
137 putとupdate、flipはOutput DS APIと呼ばれ、DSをDSMに保存する際に用いる。 |
| 4 | 138 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
139 peekとtakeはInput DS APIと呼ばれ、DSをDSMから取得する際に使用する。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
140 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
141 \begin{itemize} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
142 \item {\ttfamily void put(String managerKey, String key, Object val)} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
143 \end{itemize} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
144 DSをDSMに追加するためのAPIである。第一引数はLocal DSMかRemote DSMかといったManager名を指定する。そして第二引数で指定されたkeyに対応するDSとして第三引数の値を追加する。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
145 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
146 \begin{itemize} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
147 \item {\ttfamily void update(String managerKey, String key, Object val)} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
148 \end{itemize} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
149 updateもDSをDSMに追加するためのAPIである。putとの違いは、queueの先頭のDSを削除してからDSを追加することである。そのためAPI実行前後でqueueの中にあるDSの個数は変わらない。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
150 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
151 \begin{itemize} |
| 6 | 152 \item{\ttfamily void flip(String managerKey, String key, Receiver val)} |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
153 \end{itemize} |
| 6 | 154 flipはDSの転送用のAPIである。取得したDSに対して何もせずに別のKeyに対し保存を行いたい場合、一旦値を取り出すのは無駄である。flipはDSを受け取った形式のまま転送するため無駄なコピーなくDSの保存ができる。 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
155 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
156 \begin{itemize} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
157 \item {\ttfamily void take(String managerKey, String key)} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
158 \end{itemize} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
159 takeはDSを読み込むためのAPIである。読み込まれたDSは削除される。要求したDSが存在しなければ、CSの待ち合わせ （Blocking）が起こる。putやupdateによりDSに更新があった場合、takeが直ちに実行される。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
160 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
161 \begin{itemize} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
162 \item {\ttfamily void peek(String managerKey, String key)} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
163 \end{itemize} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
164 peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
165 |
| 4 | 166 \newpage |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
167 |
| 2 | 168 \section{Code Segmentの記述方法} |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
169 CSをユーザーが記述する際にはCodeSegmentクラスを継承して記述する(ソースコード \ref{src:StartCodeSegment} , \ref{src:CodeSegment})。 |
| 4 | 170 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
171 継承することによりCode Segmentで使用するData Segment APIを利用する事ができる。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
172 |
| 4 | 173 Alice には、Start CS (ソースコード \ref{src:StartCodeSegment} )というC の main に相当するような最初に実行される CS がある。 |
| 174 Start CSはどのDSにも依存しない。つまりInput DSを持たない。 | |
| 175 このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 | |
| 176 | |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
177 \begin{table}[html] |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
178 \lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
179 \lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
180 \end{table} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
181 |
| 4 | 182 \newpage |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
183 |
| 4 | 184 ソースコード \ref{src:StartCodeSegment} は、5行目で次に実行させたいCS（ソースコード \ref{src:CodeSegment} ）を作成している。 |
| 185 8行目でOutput DS APIを通してLocal DSMに対してDSをputしている。 | |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
186 Output DS APIはCSの{\tt ods}というフィールドを用いてアクセスする。 |
| 4 | 187 {\tt ods}は{\tt put}と{\tt update}と{\tt flip}を実行することができる。 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
188 TestCodeSegmentはこの"cnt"というkeyに対して依存関係があり、8行目でputが行われるとTestCodeSegmentは実行される。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
189 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
190 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
191 CSのInput DSは、CSの作成時に指定する必要がある。指定はCommandType(PEEKかTAKE)、DSM名、そしてkey よって行われる。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
192 Input DS API はCSの{\tt ids}というフィールドを用いてアクセスする。 |
| 4 | 193 Output DSは、{\tt ods}が提供するput/update/flipメソッドをそのまま呼べばよかったが、Input DSの場合{\tt ids}にpeek/takeメソッドはなく、create/setKeyメソッド内でCommandTypeを指定して実行する。 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
194 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
195 ソースコード\ref{src:CodeSegment}は、0から9までインクリメントする例題である。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
196 2行目では、Input DS APIがもつcreateメソッドでInput DSを格納する受け皿(Receiver)を作っている。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
197 引数には{\tt PEEK}または{\tt TAKE}を指定する。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
198 \begin{itemize} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
199 \item {\ttfamily Receiver create(CommandType type)} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
200 \end{itemize} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
201 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
202 4行目から6行目はコンストラクタである。コンストラクタはオブジェクト指向のプログラミング言語で新たなオブジェクトを生成する際に呼び出されて内容の初期化を行う関数である。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
203 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
204 % TestCodeSegmentのコンストラクタが呼ばれた際には、 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
205 % \begin{enumerate} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
206 % \item CSが持つフィールド変数 {\tt Receiver input}に{\tt ids.create(CommandType.TAKE)}が行われ、{\tt input}が初期化される。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
207 % \item 5行目にあるTestCodeSegmentのコンストラクタのTAKEが実行される。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
208 % \end{enumerate} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
209 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
210 5行目は、2行目のcreateで作られたReceiverが提供するsetKeyメソッドを用いてLocal DSMからDSを取得している。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
211 \begin{itemize} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
212 \item \verb+void setKey(String managerKey, String key)+ |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
213 \end{itemize} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
214 setKeyメソッドはpeek/takeの実行を行う。どのDSMのどのkeyに対してpeekまたはtakeコマンドを実行させるかを指定できる。コマンドの結果がレスポンスとして届き次第CSは実行される。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
215 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
216 実行されるrunメソッドの内容は |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
217 \begin{enumerate} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
218 \item 10行目で取得されたDSをInteger型に変換してcountに代入する。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
219 \item 12行目でcountをインクリメントする。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
220 \item 16行目で次に実行されるCSが作られる。（この時点で次のCSはInput DSの待ち状態に入る） |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
221 \item 17行目でcountをLocal DSMにputする。Input DSが揃い待ち状態が解決されたため、次のCSが実行される。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
222 \item 13行目が終了条件であり、countの値が10になれば終了する。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
223 \end{enumerate} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
224 となっている。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
225 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
226 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
227 \chapter{AliceのMeta Computation} |
| 2 | 228 \section{Computetion と Meta Computation} |
| 8 | 229 Aliceでは、処理をComputationとMeta Computationに階層化し、コアな仕様と複雑な例外処理に分離する。 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
230 AliceのComputationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理と捉えられる。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
231 それに対して、AliceのMeta Computation は、Remoteノードとの通信時のトポロジーの構成や切断・再接続の処理と言える。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
232 つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
233 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
234 Aliceの機能を追加するということはプログラマ側が使うMeta Computationを追加すると言い換えられる。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
235 AliceではMeta Computationとして分散環境の構築等の機能を提供するため、プログラマはCSを記述する際にトポロジー構成や切断、再接続という状況を予め想定した処理にする必要はない。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
236 プログラマは目的の処理だけ記述し、切断や再接続が起こった場合の処理をMeta Computationとして指定する。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
237 このようにプログラムすることで、通常処理と例外処理を分離することができるため、仕様の変更を抑えたシンプルなプログラムを記述できる。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
238 |
| 5 | 239 現在Aliceには、トポロジーの構成・管理機能、ノードの生存確認機能、ノードの切断・再接続時の処理管理機能などのMeta Computationが用意されている。 |
| 240 | |
| 241 \newpage | |
| 242 | |
| 6 | 243 \section{Meta Code Segment と Meta Data Segment} |
| 5 | 244 Alice提供するMeta ComputationもCS/DSにより実現される。 |
| 245 CSの処理を支える処理をMeta CS、Meta CSに管理されるMeta DSとして考える。 | |
| 246 | |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
247 図\ref{fig:metaCS}は、AliceのMeta CS/Meta DSの接続関係の例である。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
248 プログラマ側はCSとDSの依存関係を記述するが、その裏ではMeta CSやMeta DSが間に接続されて処理を行っている。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
249 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
250 \begin{figure}[h] |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
251 \begin{center} |
| 4 | 252 \includegraphics[width=120mm]{images/MetaCSDS.pdf} |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
253 \end{center} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
254 \caption{CS/DSの間にMetaCS/MetaDSが接続される} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
255 \label{fig:metaCS} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
256 \end{figure} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
257 |
| 5 | 258 Meta DSは基本的にAliceを構成するCSによってのみ管理され、プログラマは認識できない。 |
| 259 しかし一部のMeta DSはプログラマがアプリケーションに利用することもできる。 | |
| 260 例えば、トポロジー管理のMeta Computationなどで使われる"\_CLIST"というMeta DSには、利用可能なRemote DSMの情報が管理されている。 | |
| 261 プログラマはこのMeta DSを取得しRemote DSM名を指定することで、動的にDSの伝搬などを行うことができる。 | |
| 262 | |
| 263 | |
| 4 | 264 \newpage |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
265 |
| 6 | 266 \section{Topology Manager} |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
267 Aliceでは、ノード間の接続管理やトポロジーの構成管理を、Topology ManagerというMeta Computationが提供している。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
268 プログラマはトポロジーファイルを用意し、Topology Managerに読み込ませるだけでトポロジーを構成することができる。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
269 トポロジーファイルはDOT Language\cite{dot}という言語で記述される。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
270 DOT Languageとは、プレーンテキストを用いてデータ構造としてのグラフを表現するためのデータ記述言語の一つである。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
271 ソースコード\ref{src:topologyfile}は3台のノードでリングトポロジーを組むときのトポロジーファイルの例である。 |
| 5 | 272 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
273 \begin{table}[html] |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
274 \lstinputlisting[label=src:topologyfile, caption=トポロジーファイルの例]{source/TopologyFile.dot} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
275 \end{table} |
| 5 | 276 DOT Languageファイルはdotコマンドを用いてグラフの画像ファイルを生成することができる。そのため、記述したトポロジーが正しいか可視化することが可能である。 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
277 |
| 5 | 278 \newpage |
| 279 | |
| 6 | 280 Topology Managerはトポロジーファイルを読み込み、参加を表明したクライアント（以下、Topology Node）に接続するべきクライアントのIPアドレスやポート番号、接続名を送る（図\ref{fig:topologymanager}）。 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
281 また、トポロジーファイルでlavelとして指定した名前はRemote DSMの名前としてTopology Nodeに渡される。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
282 そのため、Topology NodeはTopology ManagerのIPアドレスさえ知っていれば自分の接続すべきノードのデータを受け取り、ノード間での正しい接続を実現できる。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
283 \begin{figure}[h] |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
284 \begin{center} |
| 4 | 285 \includegraphics{images/topologymanager.pdf} |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
286 \end{center} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
287 \caption{Topology Managerが記述に従いトポロジーを構成} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
288 \label{fig:topologymanager} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
289 \end{figure} |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
290 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
291 また、実際の分散アプリケーションでは参加するノードの数が予め決まっているとは限らない。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
292 そのためTopology Managerは動的トポロジーにも対応している。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
293 トポロジーの種類を選択してTopology Managerを立ち上げれば、あとは新しいTopology Nodeが参加表明するたびに、Topology ManagerからTopology Nodeに対して接続すべきTopology Nodeの情報がput |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
294 され接続処理が順次行われる。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
295 そしてTopology Managerが持つトポロジー情報が更新される。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
296 現在Topology Managerでは動的なトポロジータイプとして二分木に対応している。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
297 |
| 5 | 298 \newpage |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
299 |
| 6 | 300 \section{Keep Alice} |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
301 ノード間通信はRemote DSMに対してputやtakeを行うことでのみ発生する。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
302 アプリケーション次第では長時間通信が行われない可能性があり、その間にノード間接続が切れた場合、次の通信が行われるまで切断を発見することができない。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
303 また、接続状態ではあるが応答に時間がかかる場合もある。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
304 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
305 これらの問題を検知するために、KeepAliveという定期的にheart beatを送信し生存確認を行うMeta Computationがある。この機能もCS/DSを用いて実装されている。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
306 一定時間内にノードからの応答がない場合、KeepAliveにより、そのノードのRemote DSMが切断される。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
307 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
308 また、トポロジーからノードが切断された際にトポロジーを再構成する機能もTopology Managerに用意した。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
309 例えばツリートポロジーでノードが切断された場合、そのノードの子ノードは全体のトポロジーから分断されてしまう。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
310 ノードは切断を検知するとただちにTopology Managerに再接続すべきノード情報を要求し、木を構成し直す。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
311 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
312 |
| 6 | 313 \section{切断・再接続時の処理} |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
314 MMORPGでは、試合の最中にサーバーからユーザーが切断された場合、自動的にユーザーが操作するキャラクターをゲームの開始時の位置に戻すという処理が実行される。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
315 同様に、Aliceを用いたアプリケーションでもノードの切断時に対する処理を用意したい場合がある。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
316 そこで、Aliceが切断を検知した際に任意のCSを実行できる機能(ClosedEventManager)を追加した。 |
| 5 | 317 プログラマは切断の際に実行したいCSを書き、ClosedEventManagerに登録しておけば良い。 |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
318 また、再接続してきたノードに対し通常の処理とは別の処理を行わせたい場合がある。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
319 そのため、切断時と同様に再接続してきたノードに任意のCSを実行できるMeta Computationも用意した。 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
320 |
|
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
321 |
| 2 | 322 % AliceVNC |
|
3
a97aa059242f
add images & sources
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
323 \chapter{AliceのTreeVNCへの応用} |
| 5 | 324 AliceのMeta Computationが実用的なアプリケーションの記述において有用であることを確認する。 |
| 325 そのために、TreeVNCをAliceを用いて実装したAliceVNCの作成を行った\cite{sigOS}。 | |
| 326 | |
| 2 | 327 \section{TreeVNC} |
| 4 | 328 TreeVNCとは、当研究室で開発を行っている授業向け画面共有システムである。 |
| 329 オープンソースのVNCであるTightVNC \cite{tightVNC} をもとに作られている。 | |
| 330 授業でVNCを使う場合、１つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう(図 \ref{fig:vncstructure})。 | |
| 331 この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである(図 \ref{fig:treestructure})。 | |
| 332 \begin{figure}[htbp] | |
| 333 \begin{tabular}{cc} | |
| 334 \begin{minipage}{0.5\hsize} | |
| 335 \begin{center} | |
| 336 \includegraphics[width=80mm]{images/vnc.pdf} | |
| 337 \caption{通常のVNCの構造} | |
| 338 \label{fig:vncstructure} | |
| 339 \end{center} | |
| 340 \end{minipage} | |
| 341 \begin{minipage}{0.5\hsize} | |
| 342 \begin{center} | |
| 343 \includegraphics[width=80mm]{images/treestructure.pdf} | |
| 344 \caption{TreeVNCの構造} | |
| 345 \label{fig:treestructure} | |
| 346 \end{center} | |
| 347 \end{minipage} | |
| 348 \end{tabular} | |
| 349 \end{figure} | |
| 350 | |
| 5 | 351 \newpage |
| 4 | 352 |
| 5 | 353 \section{AliceVNC} |
| 4 | 354 図 \ref{fig:TreeVNC}はAliceVNCを実現するための構成である。leftとrightのRemote DSMを用意し子ノードと接続することで木構造を実現する。 |
| 355 | |
| 356 \begin{figure}[h] | |
| 357 \begin{center} | |
| 8 | 358 \includegraphics[width=120mm]{images/AliceVNCstracture.pdf} |
| 4 | 359 \end{center} |
| 360 \caption{AliceVNC の構造} | |
| 361 \label{fig:TreeVNC} | |
| 362 \end{figure} | |
| 363 | |
| 364 TreeVNCは通信処理部分や画面データの処理部分が１つのコード内で記述され、大変複雑になっている。 | |
| 365 しかし、Aliceで記述すればMeta Computationにより本質的な処理とそれを支える通信処理部分で分離できる。 | |
| 366 TreeVNCでは3章で述べた動的なトポロジーの構成、切断ノードの発見、再接続・トポロジーの再構成といった通信処理のMeta Computationが活用できる。 | |
| 367 そのため、TightVNCからの修正の少ない、見通しの良い記述で構成可能と期待される。 | |
| 368 | |
| 369 \newpage | |
| 370 | |
| 5 | 371 \chapter{圧縮のMeta Computationの追加} |
| 372 \section{圧縮のMeta Data Segment} | |
| 8 | 373 TreeVNCは画面変更の差分を木構造にそって配信する際、差分は数MByteに達するため圧縮を行っている。 |
| 4 | 374 そのため、AliceVNCにも圧縮されたデータ形式を扱える機能が必要だと考えた。 |
| 375 しかし、ただデータを圧縮する機構を追加すればいいわけではない。 | |
| 376 | |
| 377 AliceVNCでは、ノードは受け取った画面データを描画すると同時に、子ノードのRemote DSMに送信する。 | |
| 378 ノードはDSを受信するとそれを一度解凍して画面を表示し、再圧縮して子ノードに送信する。 | |
| 379 しかし、受け取ったデータを自分の子ノードに対して送信する際には、解凍する必要はない。 | |
| 380 圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる。 | |
| 381 | |
| 382 そこで、DSを複数作るのではなく１つのDS内で複数の表現を持たせ、必要に応じた形式でDSを扱うことを可能にした。 | |
| 383 Meta DSに相当するReceiveData.classに、次の3種類の表現を同時に持つことができるようにしたことで、データの多態性を実現した。 | |
| 384 | |
| 385 \begin{enumerate} | |
| 386 \item 一般的なJavaのクラスオブジェクト | |
| 387 \item MessagePack for Java\cite{MessagePack}でシリアライズ化されたバイナリオブジェクト | |
| 388 \item 2を圧縮したバイナリオブジェクト | |
| 389 \end{enumerate} | |
| 390 | |
| 391 Local DSMにputされた場合は、(1)の一般的なJavaクラスオブジェクトとして追加される。 | |
| 392 Remote DSMにputされた場合は、通信時に(2)のbyteArrayに変換されたバイナリオブジェクトに変換されたDSが追加される。 | |
| 393 この2つの形式は従来のAliceが持っていた表現である。 | |
| 394 今回、Remote DSMに圧縮形式での通信を行いたいため、(3)の圧縮表現を追加した。 | |
| 395 | |
| 5 | 396 \newpage |
| 397 | |
| 4 | 398 ソースコード \ref{src:ReceiveData1} は変更前のReceiveData.classである。 |
| 399 変更前はDSの表現は１つでフラグによって、Local DSM にputする(1)の形式とRemote DSMにputする(2)の形式を判別していた。 | |
| 400 しかしこの実装では圧縮形式と非圧縮形式を同時に持つことができないため、AliceVNCでは解凍・再圧縮が必要になってしまう。 | |
| 401 | |
| 402 変更後の実装ではソースコード \ref{src:ReceiveData1} のようになっている。 | |
| 403 {\tt val}に(1) 一般的なJavaのクラスオブジェクト の表現でデータ本体が保存される。 | |
| 404 {\tt messagePack}には(2) シリアライズ化されたバイナリオブジェクトが保存される。 | |
| 405 そして、{\tt zMessagePack}には(3) 圧縮されたバイナリオブジェクトが保存される。 | |
| 406 このようにDSが複数の表現を同時に保持することで、DSが圧縮表現を持っている場合に再圧縮する必要がなくなる。 | |
| 407 プログラマ側がから見れば1つのDSであり直接これら３つの表現を操作することはないため、これらはAliceのMeta Data Segmentと言える。 | |
| 408 | |
| 409 \begin{table}[html] | |
| 410 \lstinputlisting[label=src:ReceiveData1, caption=変更前のデータ表現]{source/beforeReceiveData.java} | |
| 411 \end{table} | |
| 412 | |
| 413 \begin{table}[html] | |
| 414 \lstinputlisting[label=src:ReceiveData2, caption=変更後のデータ表現]{source/ReceiveData.java} | |
| 415 \end{table} | |
| 416 | |
| 417 | |
| 5 | 418 \newpage |
| 419 | |
| 420 \section{圧縮のMeta Code Segment} | |
| 421 圧縮表現を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerを追加した。 | |
| 4 | 422 Compressed DSMの内部では、put/updateが呼ばれた際にReceiveData.classが圧縮表現を持っていればそれを使用し、持っていなければその時点で圧縮表現を作ってput/updateを行う。 |
| 423 Local Compressed DSM は表現の判別や変換を行うだけで、操作する対象は Local DSM と同じDSを指すため、DSの管理が別々になるわけではない。 | |
| 424 | |
| 425 | |
| 426 ソースコード \ref{src:before} はRemote DSMに対しInt型のデータをputする記述である。 | |
| 427 この通信を圧縮形式のDSで行いたい場合、ソースコード \ref{src:after} のように指定するDSM名の先頭に"compressed"をつければCompressed DSM内部の圧縮Meta Computationが走り圧縮形式に変換さ | |
| 428 れたDSとなって通信が行われる。 | |
| 429 | |
| 430 \begin{table}[html] | |
| 431 \lstinputlisting[label=src:before, caption=通常のDSを扱うCSの例]{source/beforeCompress.java} | |
| 432 \end{table} | |
| 433 | |
| 434 \begin{table}[html] | |
| 435 \lstinputlisting[label=src:after,caption=圧縮したDSを扱うCSの例]{source/afterCompress.java} | |
| 436 \end{table} | |
| 437 | |
| 5 | 438 この機能は先述のMeta Data Segmentを扱うMeta Code Segmentと言える。 |
| 4 | 439 これによりユーザは指定するDSMを変えるだけで、他の計算部分を変えずに圧縮表現をDS内で持つことができる。 |
| 440 ノードは圧縮されたDSを受け取った後、そのまま子ノードにflipメソッドで転送すれば圧縮状態のまま送信されるので、送信の際の再圧縮がなくなる。 | |
| 441 | |
| 442 | |
| 443 画面表示の際はReceiveData.class内のasClassメソッドを使うことで適切な形式でデータを取得できる。 | |
| 444 asClassメソッドはDSを目的の型にcastするためのメソッドである。 | |
| 445 AliceVNCで圧縮形式を指定してDSを送信すると、それを受け取るDSMは圧縮形式のみを持ったDSとして保存する。 | |
| 446 そしてasClassメソッドが呼ばれて初めて、メソッド内で解凍してcastが行われDSが複数の表現を同時に持つようになる。 | |
| 447 これによりDSの表現を必要になったときに作成できるため、プログラマはどんな形式でDSを受け取ってもDSを編集可能な形式として扱うことができる。 | |
| 448 また、複数表現は必要なときにしか作成されないため、メモリ使用量も必要最低限に抑えることができる。 | |
| 449 | |
| 5 | 450 \newpage |
| 451 | |
| 4 | 452 \section{Aliceの通信プロトコルの変更} |
| 453 4.2で述べたように、Remoteからputされたデータは必ずシリアライズ化されておりbyteArrayで表現される。 | |
| 454 しかし、データの表現に圧縮したbyteArrayを追加したため、RemoteからputされたbyteArrayが圧縮されているのかそうでないのかを判別がつかなくなった。 | |
| 455 | |
| 5 | 456 そこで、Aliceの通信におけるヘッダにあたるCommandMessage.class(ソースコード\ref {src:CommandMessage} 表 \ref{tb:variable})に圧縮状態を表すフラグを追加した。 |
| 4 | 457 これによってputされたDSMはフラグに応じた適切な形式でReceiveData.class内にDSを格納できる。 |
| 458 また、CommandMessage.classに圧縮前のデータサイズも追加したことで、適切な解凍が可能になった。 | |
| 459 | |
| 460 \begin{table}[html] | |
| 461 \lstinputlisting[label=src:CommandMessage, caption=CommandMessage]{source/CommandMessage.java} | |
| 462 \end{table} | |
| 463 | |
| 464 | |
| 465 \begin{table}[htbp] | |
| 466 \caption{CommandMessageの変数名の説明} | |
| 467 \label{tb:variable} | |
| 468 \begin{center} | |
| 469 \begin{tabular} {|l|l|} | |
| 470 \hline | |
| 471 変数名&説明\\ | |
| 472 \hline | |
| 473 type&CommandType {\tt PEEK, PUT}などを表す\\ | |
| 474 \hline | |
| 475 seq&\shortstack{Data Segmentの待ち合わせを行っている\\Code Segmentを表すunique number }\\ | |
| 476 \hline | |
| 477 key&どのKeyに対して操作を行うか指定する\\ | |
| 478 \hline | |
| 479 | |
| 480 quickFlag&SEDAを挟まずCommandを処理を行うかを示す\\ | |
| 481 \hline | |
| 482 | |
| 483 compressed&データ本体の圧縮状態を示す\\ | |
| 484 \hline | |
| 485 | |
| 486 dataSize&圧縮前のデータサイズを表す\\ | |
| 487 \hline | |
| 488 | |
| 489 \end{tabular} | |
| 490 \end{center} | |
| 491 \end{table} | |
| 492 | |
| 493 \newpage | |
| 494 | |
| 6 | 495 \chapter{DSとMetaDSのKeyの領域分け} |
| 496 DSとMeta DSは同じData Segment Managerで管理されており、同じAPIを利用してアクセスされる。 | |
| 497 そのため誰でもMeta DSの変更が可能になってしまっている。 | |
| 498 プログラマが定義しようとしたKeyが偶然AliceのMeta DSのKeyと衝突してしまった場合、ユーザーが意図した動作にならずエラーとなる状況は充分にありえる。 | |
| 499 しかもMeta DSはプログラマ側からは認識できないため衝突の認識やエラーの解決がしづらくなっている。 | |
| 500 このような事態を避けるためにも、DSの領域分けが必要である。 | |
| 501 | |
| 502 いままではLocalDataSegmentManager.classは1つだけだったが、もう1つ追加してMeta Local DSMとして登録した(ソースコード \ref{src:DSManagers})。 | |
| 503 これでmanagerKey="local"ならばLocal DSMに、managerKey="metaLocal"ならばMeta Local DSMに対して操作できる。 | |
| 504 | |
| 505 \begin{table}[html] | |
| 506 \lstinputlisting[label=src:DSManagers, caption=LocalDSMの追加]{source/DataSegmentManagers.java} | |
| 507 \end{table} | |
| 508 | |
| 509 \newpage | |
| 510 | |
| 511 CodeSegment.classを継承したMetaCodeSegment.classを追加した(ソースコード \ref{src:MetaCS})。 | |
| 512 MetaCodeSegmentは、idsとodsに対してCSかMeta CSかのフラグをセットする。 | |
| 513 これを継承したクラスはDS Managerを指定せずにAPIを呼び出すと自動的にMetaDSMに対して操作したことになる。 | |
| 514 | |
| 515 \begin{table}[html] | |
| 516 \lstinputlisting[label=src:MetaCS , caption=MetaCodeSegment.class]{source/MetaCodeSegment.java} | |
| 517 \end{table} | |
| 518 | |
| 519 AliceのMeta CSは今までCS同様CodeSegment.classを継承して作られていたが、 | |
| 520 継承元をMetaCodeSegment.classに変更する(ソースコード \ref{src:extendMeta} 1行目)だけでそれ以外は変更せずにDSの領域分けができる。 | |
| 521 | |
| 522 \begin{table}[html] | |
| 523 \lstinputlisting[label=src:extendMeta ,caption=MetaCodeSegmentを継承]{source/BeforTopologyManager.java} | |
| 524 \end{table} | |
| 525 | |
| 526 | |
|
7
5fa2e97fe3c6
rename abstract to prepaper
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
6
diff
changeset
|
527 managerKey="metaLocal"を指定すれば通常のCSからもMeta DSの操作ができるが、Meta DSにtakeをした場合、そのDSをInputDSとして指定しているMeta CSが想定どおりに動作しないことが考えられる。 |
| 6 | 528 そのため、takeを行っても内部でpeekしか行わないようにした。 |
|
7
5fa2e97fe3c6
rename abstract to prepaper
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
6
diff
changeset
|
529 これにより通常のCSがtakeでDSを取得してもDSが削除されることはないため、Meta Computationに干渉することはない。 |
| 6 | 530 |
| 531 | |
| 532 | |
| 533 | |
| 534 \newpage | |
| 535 | |
| 0 | 536 |
| 537 % 実験 | |
| 2 | 538 \chapter{評価と考察} |
| 4 | 539 \section{圧縮のMeta Computationの評価} |
| 540 圧縮のMeta Computationが正しく機能しているかを確認するために通信時間の計測を行った。 | |
| 541 2台のPC間でお互いにデータを100回転送し合う。圧縮を指定したコードとしていないコードで5回計測した。 | |
| 542 | |
| 543 結果が表\ref{tb:compressmesure}である。 | |
| 544 データサイズから見ても圧縮に成功していることがわかる。 | |
| 545 通信においても、所要時間が1/3以下に抑えられていることから圧縮が効果的に作用している。 | |
| 546 TreeVNCと同等の性能をだすために有用なMeta Computationが実装できたと言える。 | |
| 547 | |
| 548 \begin{table}[htbp] | |
| 549 \caption{圧縮機能の測定結果} | |
| 550 \label{tb:compressmesure} | |
| 551 \begin{center} | |
| 552 \begin{tabular} {|l|l|l|} | |
| 553 \hline | |
| 554 &圧縮なし&圧縮あり\\ | |
| 555 \hline | |
| 556 データサイズ&300KB&91KB\\ | |
| 557 \hline | |
| 558 平均通信時間&6014ms&1764ms\\ | |
| 559 \hline | |
| 560 \end{tabular} | |
| 561 \end{center} | |
| 562 \end{table} | |
| 563 | |
| 564 | |
| 6 | 565 \section{TreeVNCとAliceVNCのメッセージ伝達速度の比較} |
| 4 | 566 TreeVNCをAlice上で構築するために必要な機能をAliceのMeta Computationとして実装した。 |
| 567 これにより、AliceVNCが簡潔な記述でTreeVNCと同等の性能を出せれば、実用的な分散アプリケーションの実装においてAliceのMeta Computationは有用であるといえる。 | |
| 5 | 568 そこで、TreeVNCとAliceVNCの性能評価としてメッセージ伝達速度の比較を、コードの評価としてコード量とその複雑度の比較を行った\cite{prosym}。 |
| 4 | 569 |
| 570 | |
| 6 | 571 まず、木の段数ごとにメッセージの到達にどれぐらい時間がかかっているかを計測した。 |
| 4 | 572 講義内で学生に協力してもらい、最大17名の接続がある中でTreeVNC、AliceVNCの木の段数1〜3の測定を行った。 |
| 573 | |
| 574 | |
| 575 | |
| 576 \textbf{実験内容} | |
| 577 | |
| 578 ルートノードから画面データを子ノードに伝搬する際に、計測用のヘッダをつけたパケットを子ノードに送信する。 | |
| 579 各子ノードはパケットを受け取り自身のViewerに画面データを表示すると同時に、計測用ヘッダ部分のみのDSを作成し、親ノードに送り返す。 | |
| 580 計測用DSは木を伝ってルートノードまで送り返され、ルートノードは受け取った計測用DSから到達時間を計算する。 | |
| 581 | |
| 582 計測用のヘッダは以下の要素で構成されている。 | |
| 583 \begin{table}[htbp] | |
| 584 \caption{計測用ヘッダの変数名の説明} | |
| 585 \label{tb:mesure} | |
| 586 \begin{center} | |
| 587 \begin{tabular} {|l|l|} | |
| 588 \hline | |
| 589 変数名&説明\\ | |
| 590 \hline | |
| 591 time&ルートノードがパケットを送信した時刻\\ | |
| 592 \hline | |
| 593 depth&木の段数。初期値=1。\\ | |
| 594 \hline | |
| 595 dataSize&送信時の形式に変換済みの画面データのサイズ\\ | |
| 596 \hline | |
| 597 \end{tabular} | |
| 598 \end{center} | |
| 599 \end{table} | |
| 600 | |
| 601 timeにはパケットの送信時刻を、dataSizeには圧縮された画面データのサイズを付けて送信する。 | |
| 602 depthは各ノードに到達するごとにインクリメントされる。 | |
| 603 | |
| 604 到達時間の計算方法は、計測用DSを受け取った時刻とDSのtime（送信した時刻）の差をとる。 | |
| 605 この到達時間は画面データがノードまで到達した時間と計測DSをルートまで送り返す時間を含めているが、送り返す時間は誤差として考える。 | |
| 606 また、depthは各ノードに到達するごとにインクリメントされるため、送り返す際もインクリメントされる。そのため、木の段数を計算するにはdepthを1/2した値となる。 | |
| 607 | |
| 5 | 608 |
| 4 | 609 |
| 610 \textbf{実験結果} | |
| 611 | |
| 5 | 612 |
| 4 | 613 3段目の測定結果の散布図を示す（図\ref{fig:TreeVNC_delay} 〜 \ref{fig:AliceVNC_compress_delay}）。 |
| 614 X軸が画面データのサイズ(byte)、Y軸が計算した到達時間(ms)である。 | |
| 615 実験時間の都合上、AliceVNCの計測時間が他より短くなってしまったためプロットされた点の数が少なくなっている。 | |
| 616 また、それぞれの図で処理に10000ms以上かかっている点の集合が見られるが、これは今回の実験において3段目にPCのスペック上処理が遅いノードが1台あったためである。 | |
| 617 そのため比較においてこの点集合は無視する。 | |
| 618 | |
| 6 | 619 図から同様の傾向があり、画面データのサイズが小さいうちは処理時間も5ms程度だが、50000byte以上から比例して処理時間も遅くなっている。 |
| 620 このことからAliceはTreeVNCと同等の処理性能を持つアプリケーションを実装するに十分な能力があることがわかる。 | |
| 4 | 621 |
| 5 | 622 |
| 623 \begin{figure}[htbp] | |
| 4 | 624 \begin{center} |
| 625 \includegraphics[width=100mm]{images/TreeVNC_depth3.pdf} | |
| 626 \end{center} | |
| 627 \caption{TreeVNCの測定結果} | |
| 628 \label{fig:TreeVNC_delay} | |
| 5 | 629 |
| 4 | 630 \begin{center} |
| 631 \includegraphics[width=100mm]{images/AliceVNC_compress_depth3.pdf} | |
| 632 \end{center} | |
| 633 \caption{AliceVNC(圧縮・転送機能あり)の測定結果} | |
| 634 \label{fig:AliceVNC_compress_delay} | |
| 635 \end{figure} | |
| 636 | |
| 5 | 637 \newpage |
| 4 | 638 |
| 6 | 639 \section{TreeVNCとAliceVNCのコード量比較} |
| 4 | 640 |
| 641 TreeVNCとAliceVNCのコード量を比較した表が表\ref{tb:code}である。 | |
| 642 TightVNCを含むコード全体にwcを行い、行数と単語数を比較した。 | |
| 643 また、hg diffでTightVNCからの変更行数を調べ変更量を比較した。 | |
| 644 | |
| 645 表からわかるように、Aliceを用いればコードの行数が25\%削減できる。 | |
| 646 また、TreeVNCではTightVNCに大幅に修正を加えながら作成したため仕様の変更が多かった。 | |
| 647 しかし、AliceVNCではTightVNCにほとんど修正を加えることなくトポロジー構成等のAliceのMeta Computationを使うために新しいクラスを作成したのみであった。 | |
| 648 そのためTreeVNCに比べ75\%も仕様の変更が抑えられている。 | |
| 649 \begin{table}[htbp] | |
| 650 \label{tb:code} | |
| 651 \begin{center} | |
| 652 \begin{tabular} {|l|l|l|l|} | |
| 653 \hline | |
| 654 &行数&単語数&変更行数\\ | |
| 655 \hline | |
| 656 TreeVNC&19502&73646&7351\\%11369+8133=19502,47010+26636,2094+5257 | |
| 657 \hline | |
| 658 AliceVNC&14647&59217&1129\\%689+7094+6864=14647,23035+34610+1572,689+395+45 | |
| 659 \hline | |
| 660 減少率(\%)&25&20&75\\ | |
| 661 \hline | |
| 662 \end{tabular} | |
| 663 \end{center} | |
| 664 \end{table} | |
| 665 | |
| 666 | |
| 6 | 667 \section{TreeVNCとAliceVNCのコードの複雑度比較} |
| 4 | 668 コード量の比較で述べたように、TreeVNCはTightVNCからの変更が多い。 |
| 669 その理由の一つがトポロジーの構成や通信処理がコアな仕様と分離できておらず、 | |
| 670 そのためTreeVNCは大変複雑な記述になってしまっている。 | |
| 671 | |
| 672 そこでTreeVNCとAliceVNCにおいてコードの複雑度を比較した。 | |
| 673 今回、複雑度の指標としてThomas McCabeが提案した循環的複雑度\cite{complaxy}を用いた。 | |
| 674 循環的複雑度とはコード内の線形独立な経路の数であり、if文やfor文が多ければ複雑度も高くなりバグ混入率も高まる。 | |
| 675 一般的に、循環的複雑度が10以下であればバグ混入率の少ない非常に良いコードとされる。 | |
| 676 計測にはIntelliJのCodeMetrics計測プラグインであるMetricsReloadedを使用した。 | |
| 677 | |
| 5 | 678 \newpage |
| 4 | 679 |
| 5 | 680 表\ref{tb:complex}はTightVNC、TreeVNC、AliceVNCにおける循環的複雑度の比較である。 |
| 4 | 681 |
| 682 \begin{table}[htbp] | |
| 683 \caption{複雑度の比較} | |
| 684 \label{tb:complex} | |
| 685 \begin{center} | |
| 686 \begin{tabular} {|l|l|l|} | |
| 687 \hline | |
| 688 &平均値&最高値\\ | |
| 689 \hline | |
| 690 TightVNC&13.63&97\\ | |
| 691 \hline | |
| 692 TreeVNC&15.33&141\\ | |
| 693 \hline | |
| 694 AliceVNC&10.95&99\\%(4.12+13.64)/2 (4.12+9.16+19.59)/3 | |
| 695 \hline | |
| 696 \end{tabular} | |
| 697 \end{center} | |
| 698 \end{table} | |
| 699 | |
| 5 | 700 プロジェクト全体でのクラスの複雑度の平均値と最高値をとった。 |
| 701 平均値・最高値ともにAliceVNCのほうが複雑度が低いことから、Aliceではシンプルな記述が可能だということがわかる。 | |
| 702 | |
| 703 TreeVNCで最高値を出したTreeRFBProto.classは全てプログラマが記述したコードであり、データの待ち合わせのためのタイマー処理や通信処理、画面データの圧縮処理などの複数のスレッド処理が集中した複雑なコードになっている。 | |
| 704 これをAliceで記述した場合、データの待ち合わせはCSが行うためプログラマがデータの不整合を気にする必要はなく、また通信処理や圧縮処理もMeta Computationが提供するためコードが複雑になることはない。 | |
| 705 | |
| 706 AliceVNCで複雑度の最高値を出したSwingViewerWindow.classはTightVNCで最高値を出したクラスと同じであり、コード量の比較でも示したようにAliceVNCで変更を加えた点がほとんどない。つまりこの複雑度は元来TightVNCが持っている複雑度と言える。 | |
| 707 | |
| 4 | 708 AliceVNCとTreeVNCの性能比較・コード比較から、AliceVNCはTreeVNCと同等の性能を持つ分散アプリケーションの記述ができ、かつコードの修正量・複雑度共に低く抑える能力を有することがわかった |
| 709 。 | |
| 710 | |
| 5 | 711 \newpage |
| 4 | 712 |
| 6 | 713 \chapter{他言語等との比較} |
| 4 | 714 |
| 6 | 715 \section{MPICH} |
| 716 メッセージパッシング方式の標準規格であるMPIのC++/FORTRANの実装系がMPICHである。 | |
| 717 メッセージパッシングとは、並列分散処理におけるプロセス間通信の一形態で、分散メモリ同士の書き込みをメールのようにメッセージの送受信で行う方式である。 | |
| 4 | 718 |
| 6 | 719 プロセスごとにランクというidが付与され、プロセスはコミュニケーターという通信単位でグループ化できる。 |
| 720 コミュニケーターとランクをそれを指定してメッセージを送受信する。 | |
| 721 APIはSender/Receiverメソッドが用意されており、宛先情報、データの種類・サイズ、そしてプログラマがメッセージに対し任意に命名できるタグを指定して送受信を行う。 | |
| 722 Sender/ReceiverはAliceのput/takeに対応しており、コミュニケーターはDSM名、タグはKeyに対応している点が類似している。 | |
|
7
5fa2e97fe3c6
rename abstract to prepaper
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
6
diff
changeset
|
723 しかし、Sender/Receiverは同期型と非同期型の2種類あり、プログラマはそれらを組み合わせて同期を意識しながらプログラミングしなければならない。 |
|
5fa2e97fe3c6
rename abstract to prepaper
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
6
diff
changeset
|
724 一方、AliceではDSの待ち合わせ処理をCSが自動で行うためそのような負担が少ない。 |
| 6 | 725 |
|
7
5fa2e97fe3c6
rename abstract to prepaper
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
6
diff
changeset
|
726 また、MPICHはAliceのMeta Computationに対応するものはない。そのため分散環境の構築やデータの圧縮は全てプログラマ側が記述しなければならない。 |
| 6 | 727 一方、Aliceでは分散環境の構築はTopology ManagerなどのMeta Computationが行うためプログラマはトポロジーを指定するだけで良い。 |
| 728 | |
| 729 \section{Erlang} | |
| 730 アクターモデルの並列指向プログラミング言語Erlang\cite{Erlang}は、プロセスと呼ばれるid付きの独立したタスクに対して、idを指定してデータをメッセージでやりとりする。 | |
| 4 | 731 タスクをプロセスという細かい単位に分割して並列に動かす点や、メモリロックの仕組みを必要としない点はAliceと同様である。 |
| 732 | |
| 6 | 733 Erlangもプロセス/アクターに直接データをやりとりする。MPICHにはメッセージにタグが付けられたが、Erlangにはデータには名前がない。 |
| 734 そのため、メッセージを受け取ったあとにその内容を確認した上で次にどう振る舞うかを判断する記述が必要となる。 | |
| 4 | 735 一方Aliceでは、DSをCSに直接やりとりはせず、keyを指定してDSMにputする。 |
| 736 また、DSをtakeするときもkeyを指定して取り出すためどんなデータが入っているかを確認する必要がなく、扱い易い。 | |
| 737 | |
| 6 | 738 そして、Erlangでは静的な複数のデータの待ち合わせのための再帰処理も自分で書かなければならない。 |
| 739 一方、Aliceのプログラミング手法はCSが必要なデータが全て揃うまで待ち合わせを行うためその必要はない。 | |
| 740 | |
| 741 また、MPICH同様ErlangにもMeta Computationに対応する部分がないため、分散環境の構築等はすべてプログラマ自身が記述しなければならない。 | |
| 742 | |
| 743 \section{Akka} | |
| 744 | |
| 745 Akka\cite{Akka}はScala・Java向けの並列分散処理フレームワークである。 | |
| 746 アクターモデルを採用しており、アクターと呼ばれるアドレスを持ったタスクに、データをメッセージでやりとりする点がErlangと似ている。 | |
| 4 | 747 |
| 6 | 748 Akkaの特徴として、メッセージを送りたいプロセスのアドレスを知っていればアクターがどのマシン上にあるかを意識せずにプログラミングできるという点がある。 |
| 749 逆にAliceはどのRemote DSMに対してやり取りをするかを考慮するが、CSがOutputしたDSを次にどのCSに渡すかを意識する必要がない。 | |
| 750 この点はアクターモデルとCS/DSモデルのパラダイムの違いと言える。 | |
| 751 一方AliceとAkkaは提供されるAPIという点で類似している。 | |
| 4 | 752 |
| 6 | 753 また、AkkaのメッセージAPIでは、メッセージを送るtellメソッドと、メッセージを送って返信を待つaskメソッドが用意されている。 |
| 754 これはAliceのDataSegment APIのput/takeメソッドに対応している。 | |
| 755 | |
| 756 Akkaのもう一つの特徴として、アクターで親子関係を構成できる点がある。 | |
| 4 | 757 分散通信部分を子アクターに分離し、親アクターは子アクターのExceptionが発生した時に再起動や終了といった処理を指定できる。 |
| 758 さらにRouterという子アクターへのメッセージの流れを制御するアクターや、Dispatcherというアクターへのスレッドの割当を管理する機能をAkkaが提供している。 | |
| 759 このように処理を階層化し複雑な処理をフレームワーク側が提供する仕組みはAliceのMeta Computationと共通している。 | |
| 6 | 760 相違点としては、AliceのMeta DSのようにデータを分離し多態性を実現する機能はAkkaにはない。 |
| 761 例えば、データを圧縮して通信した場合は、用意されているcompress/uncompressメソッドを使い圧縮・伸長のコードをプログラマが挟まなければならない。 | |
| 762 そのためコードを圧縮通信に変更したいときはメッセージの送信側と受信側を両方書き換えが必要になり、どちらか一方を書き忘れるとエラーとなる。 | |
| 763 一方Aliceでは送信側がDSM名に"compress"をつけるだけで他を変更しなくとも圧縮通信に切り替えられるので、コードの変更量が抑えられ、変更前の信頼性が保存される。 | |
| 4 | 764 |
| 765 | |
| 0 | 766 % 今後の課題 |
| 6 | 767 \chapter{まとめ} |
| 768 並列分散フレームワークAliceでは、スケーラブルかつ信頼性の高いプログラムを記述する環境を実現するため、CS / DSの計算モデルとMeta Computationによる実装の階層化を採用している。 | |
| 769 Meta ComputationはMeta CS / Meta DS に分けられ、それらが通常の処理の間に挟まれることでプログラマ側の記述するComputationの変更を抑えた挙動変更を可能にする。 | |
| 770 | |
| 771 Aliceが実用的な分散アプリケーションを記述するために必要なMeta Computationとして、Meta DSに複数の形式を同時に持たせ、DSMを切り替えることで多態性を持つデータを扱う機能を実装した。 | |
| 772 これにより、必要に応じた形式を扱うことができ、ユーザが記述するComputation部分を大きく変えずに自由度の高い通信を行うことが可能になった。 | |
| 773 同様の手法を用いれば、圧縮形式以外にも暗号形式・JSON 形式などの複数のデータ表現をユーザに扱いやすい形で拡張することができる。 | |
| 774 | |
| 775 また、Data Segment のKeyの管理領域を分けたことで、DSとMeta DSのKeyの衝突を避け、CS / DSのプログラミングスタイルにおける信頼性向上を図った。 | |
| 776 | |
| 4 | 777 そしてMeta Computationを用いて分散アプリケーションTreeVNCをAlice上で実装し性能評価を行った。 |
| 6 | 778 その結果、TreeVNCで使用される基本機能はAliceでも実現でき、同等の性能を出すことに成功した。 |
| 779 また、コードの観点からTreeVNCとAliceVNCを比較した結果、Aliceが仕様の変更を抑えたシンプルな記述を実現できていた。 | |
| 780 このことからAliceのMeta Computationが信頼性・拡張性の高い実用的な分散アプリケーションを構築するに有用であることが確認された。 | |
| 4 | 781 |
| 6 | 782 \chapter{今後の課題} |
| 783 \section{AliceVNCのNAT超え通信の実装} | |
| 4 | 784 今後の課題としては、TreeVNCで実装が困難であったNATを超えたノード間通信をAliceVNCで実現し、その性能とコード修正量を比較することが挙げられる。 |
| 785 図\ref{fig:overNAT}は２つの違うプライベートネットワークを超えた接続の設計例である。 | |
| 786 | |
| 787 \begin{figure}[h] | |
| 788 \begin{center} | |
| 5 | 789 \includegraphics[width=120mm]{images/overNAT.pdf} |
| 4 | 790 \end{center} |
| 791 \caption{複数のTopology ManagerでNAT超えを実現} | |
| 792 \label{fig:overNAT} | |
| 793 \end{figure} | |
| 794 | |
| 795 各ネットワークごとにTopoogy Managerを立ち上げることでネットワークを超えたノード間接続を実現する。 | |
| 796 プライベートネットワークのTopoogy Managerは今までどおりネットワーク内に木を構築・管理する。 | |
| 797 他のネットワークにあるノードBがノードAに接続したい場合は、グローバルアドレスを持ったTopology Managerに参加表明をすればノードAの情報が提供され、ノードAの子ノードとして接続される。 | |
| 798 つまり、Topology Managerを複数用意するだけで、Topology Manager自体の「参加表明のあったノードで木を構成する」という仕様は全く変更しないで良い。 | |
| 799 TreeVNCでは500行以上の変更が必要とされたが、Aliceでは複数のTopology Managerに接続するためのconfigファイルを変更するだけなので、AliceVNCの仕様の変更を抑えられると期待される。 | |
| 800 この機能も実現できれば、AliceのMeta Computationが拡張性の高い環境を提供できると言える。 | |
| 801 | |
| 802 | |
| 6 | 803 \section{APIの再設計} |
| 4 | 804 2.4で示したように、DSを取得するときのAPIはpeek/takeが直接扱えず、create/setKeyを組み合わせてプログラミングしなければならない。 |
| 5 | 805 この設計だとプログラマにとってわかりづらく、コンストラクタ内でtakeを行いたい場合はsetKeyを必ず最後に呼ばなければならない等の注意点がある。 |
| 4 | 806 put/update/flipと同様に、peek/takeをそのまま呼べるように再設計する必要がある。 |
| 807 | |
| 6 | 808 また、動的に複数のDSを取得する場合は、プログラマが末尾再帰処理を書かなければならない。 |
| 809 MPICHのReceiverメソッドは引数でタグと個数を指定することで複数のメッセージの待ち合わせができる。 | |
| 810 複数DSを待ち合わせしたい場面は多いため、個数指定のできるAPIの追加も望ましい。 | |
| 811 | |
| 812 \section{DSの型情報のマネジメント} | |
| 5 | 813 Aliceでは型情報がないので、peek/takeする際にどんな型のデータが入っているのかがわからない。 |
| 814 takeしたDSの型を確認したい場合には、そのDSをputしている部分を確認しなくてはならない。 | |
| 815 そのため、型情報をサポートする機能が必要である。 | |
| 816 | |
| 6 | 817 \section{データの永続性の確保} |
| 4 | 818 現在のAliceは、On memoryであるためプロセスの終了とともにData Segmentは全て失われてしまう。 |
| 819 | |
| 820 この問題を解決するためには、Data Segmentを他のKey Value Store等のシステムに保存し、永続性を確保する昼用がある。 | |
| 821 また、当研究室で開発しているJungle Database\cite{Jungle}のようにLogファイルとして出力することでも解決ができる。 | |
| 822 | |
| 6 | 823 \section{Java以外での実装} |
| 4 | 824 Alice に Garbage Collection は必要ない。Alice では、すべての Data Segment は Key Value に格納され、実行時の Data Segment は Code Segment が active な時のみにメモリ上にある。 |
| 825 この最大値を見積ることは、Active Task の量を見積もれば良い。したがって、Alice にはGarbage Collection は必要ない。 | |
| 826 一方で、Key Value Store 上のデータは決して Garbage Collection の対象にならない。 | |
| 827 しかし、それは Garbage Collector には負荷をかけてしまう。 | |
| 828 つまり、Alice 自体は Java で実装するのには向いていない。 | |
| 0 | 829 |
| 5 | 830 当研究室ではCode Segment/Data Segmentのプログラミング形式で記述する言語CbC |
| 831 | |
| 832 (Continuation based C)\cite{CbC}と、CbCを用いて記述されるGears OS\cite{Gears}の開発を行っている。 | |
| 833 そのため、CbCを用いてGears OSの分散機構の一部としてAliceを再設計することが望ましい。 | |
| 834 | |
| 0 | 835 % 参考文献 |
| 836 \input{bibliography.tex} | |
| 837 | |
| 838 % 謝辞 | |
| 2 | 839 \chapter{謝辞} |
| 10 | 840 \hspace{1zw}本研究の遂行、また本論文の作成にあたり、ご多忙にも関わらず終始懇切なる御指導と御教授を賜わりました河野真治准教授に深く感謝したします。 |
| 4 | 841 |
| 5 | 842 そして、数々の貴重な御助言と技術的指導を戴いた杉本優さん、比嘉健太さん、伊波立樹さん、並びに並列信頼研究室の皆様に感謝いたします。 |
| 4 | 843 |
| 6 | 844 また、東京大学の横山大作教授をはじめ、OS研究会、プログラミング・シンポジウムにおいて多くのフィードバックを頂いた先生方に感謝いたします。 |
| 4 | 845 |
| 5 | 846 本研究を遂行するにあたり参考にさせていただいた先行研究のFederated Linda, Cerium, TreeVNC の設計・実装に関わった全ての先輩方に感謝いたします。 |
| 4 | 847 |
| 5 | 848 最後に、日々の研究生活を支えてくださった米須智子さん、情報工学科の方々、そして家族に心より感謝いたします。 |
| 849 | |
| 4 | 850 |
| 851 \begin{flushright} | |
| 6 | 852 2016年 2月 \\ 照屋のぞみ |
| 4 | 853 \end{flushright} |
| 854 | |
| 0 | 855 |
| 856 % 付録 | |
| 857 %\input{appendix.tex} | |
| 858 | |
| 859 \end{document} |