# HG changeset patch # User sugi # Date 1421387045 -32400 # Node ID 930eae4e8aebfee5dcd070915687cbcf7c3eac67 # Parent b9b3f2241ab474a05a73d1844c7c4ef85f320f89 modify introduction diff -r b9b3f2241ab4 -r 930eae4e8aeb paper/chapter1.tex --- a/paper/chapter1.tex Tue Jan 13 17:10:56 2015 +0900 +++ b/paper/chapter1.tex Fri Jan 16 14:44:05 2015 +0900 @@ -5,7 +5,7 @@ Federated Lindaでは、Lindaサーバ内部にMeta Engineと呼ばれるLindaのタプル(データ構造)をやり取りする部分を作成した。Meta Engineでは、タプルのやり取りによって起動するcall backを使うが、call backによる記述が分散してしまい、可読性を落としてしまう。また、複数のタプルの待ち合わせが重要だが、その待ち合わせはsingle threadedなMeta Engine内部の状態に依存する。 -これらが示しているのは、並列分散実行はコードの並列実行だけでなく、データの単位が重要だということである。そこで、AliceはData SegmentとCode Segmentという単位でデータと処理を細かく分割し、それぞれの依存関係を記述して分散プログラムを作成する。Code SegmentはContinuation based Cの実行単位であり、その双対がData Segmentである。 +これらが示しているのは、並列分散実行はコードの並列実行だけでなく、データの単位が重要だということである。そこで、AliceはData SegmentとCode Segmentという単位でデータと処理を細かく分割し、それぞれの依存関係を記述して分散プログラムを作成する。 Data SegmentはCode Segmentと分離されたデータ構造であり、オブジェクトではない。オブジェクト指向プログラミングが状態を複雑に持ち、並列実行や分散実行に向かないことは徐々に理解されてきている。一方で、状態自体は有限状態遷移機械(Finite State Machine/FSM)で記述するのが自然である。Code Segmentは状態遷移記述そのものであり、その状態遷移はData Segmentの到着によってトリガーされる。 @@ -38,46 +38,7 @@ \item \verb+void peek(Receiver receiver, String key)+ \item \verb+void take(Receiver receiver, String key)+ \end{itemize} -\subsubsection{put} -putはデータをQueueに追加するためのAPIである。Lindaのout()に相当する。(図 \ref{fig:put}) -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=100mm]{images/put.pdf} -\end{center} -\caption{queueにデータを追加する} -\label{fig:put} -\end{figure} -\subsubsection{update} -updateはデータを置き換える特急メッセージのように動作する。Lindaのupdate()に相当する。(図 \ref{fig:update}) -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=100mm]{images/update.pdf} -\end{center} -\caption{update"は先頭データを取り除き、queueにデータを追加する} -\label{fig:update} -\end{figure} - -\subsubsection{peek} -peekはデータを読み込むAPIである。読み込まれたデータはQueueに残る。要求したデータが存在しなければ、Code Segmentの待ち合わせ （Blocking）が起こる。putやupdateによりデータに更新があった場合、peekが直ちに実行される。Lindaのread()に相当する。(図 \ref{fig:peek}) - -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=90mm]{images/peek.pdf} -\end{center} -\caption{peekはデータをreceiverに読み込む。希望のデータがない場合は保留する} -\label{fig:peek} -\end{figure} - -\subsubsection{take} -takeもデータを読み込むためのAPIである。peekとの違いは読み込まれたデータはQueueから削除される。Lindaのin()に相当する。(図 \ref{fig:take}) -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=70mm]{images/take.pdf} -\end{center} -\caption{"take" はデータを receiver に読み込む。その際、読み込んだデータは削除される} -\label{fig:take} -\end{figure} \subsection{Data Segment の表現} Data Segmentの表現にはMessage Packを利用している。Message Packに関してJavaにおけるデータ表現は以下の3種類があり、制限を伴うが互いに変換可能である。 @@ -191,35 +152,8 @@ \end{figure} Code Segment内部でRemote DSMにアクセスする場合はToplogyManagerによって指定されたノード内部だけで有効なlabel(文字列)を使う。これにより特定のURLがCode Segment内部に記述されることを防いでいる。 -\subsection{トポロジーファイルの記述方法} -Topology Managerが読み込むトポロジーファイルは Languageと呼ばれる言語で記述する。 -DOT Languageはプレーンテキストを用いてデータ構造としてのグラフ構造を表現するデータ記述する言語の一種である。 -このDOT Languageを用いてクライアント間の接続を表現する。 - -クライアント間の接続はlabelを用いて名前が割り振られている。この接続名を指定することでユーザーは他のノードのRemote Data Segmentにアクセスすることができる。ReceiverにsetKeyを行う際、odsでput、updateする際のmanagerKeyがlabelである。(ソースコード\ref{src:ring}) - -\begin{table}[htbp] -\lstinputlisting[label=src:ring, caption=3台でリングを組んだ時の例]{source/ring.dot} -\end{table} - -テキストのみではユーザーが望む形のトポロジーかどうかを判断しにくい。ノードの数が少なければ、可能であるがノードの数が増加するに連れて困難になるが、dotコマンドを用いることでその問題を解決することができる。 -dotコマンドでトポロジーファイルを画像として出力することができるので、記述したトポロジーが正しいことを可視化して判断することができる。(図\ref{fig:ring}) - -\begin{figure}[htbp] -\begin{itemize} -\item {\ttfamily dot -T png ring.dot -o ring.png} -\end{itemize} - -\begin{center} -\includegraphics{images/ring.pdf} -\end{center} -\caption{dotコマンドで作成された3台で構成されたリングのグラフ} -\label{fig:ring} -\end{figure} -リングトポロジーの場合、各Topology Nodeは"right"と"left"という2つのkeyでRemote Data Segmentへのアクセスが可能である。 - -また、Topology Nodeへの名前は、Topology Managerへの先着順に"node0"、"node1"、"node2"とトポロジーファイルに記述されている抽象名が割り当てられる。 +トポロジーファイルはグラフ構造を表現するデータ記述する言語の一種であるDOT Languageと呼ばれる言語で記述する。また、dotコマンドを用いてトポロジーファイルを可視化することができる。 \subsection{Topology Managerの参加表明処理} Topology Managerへの参加表明は、Topology Node起動時にコマンドライン引数からTopology ManagerのIPアドレスとポート番号を指定すればよい。 @@ -239,22 +173,3 @@ \section{Aliceによるプログラミング手法} AliceはCode SegmentとData Segmentによってプログラミングを行なう。Code Segmentから別にCode SegmentへData Segmentを引き渡す際、コンストラクタは使わない。Code SegmentがLocal / Remote Data Segmentに対してputを行い、別のCode SegmentがLocal / Remote Data Segmentに対してpeekを行うことで引き渡される。つまり、Code Segmentは実行前後にData Segmentへ通信が行われるのである。この通信の順序がCode Segmentの実行順序を決定している。 すなわち、Aliceによるプログラミングとは通信の管理を行うことであり、プロトコルを設計することと捉える事ができる。 - -\subsection{記述に関する注意点} -\subsubsection{setKey のシンタックス問題} -setKeyメソッドをコンストラクタ等で呼ぶ際、setKeyメソッドを必ず最後に呼ばなければならない。 - -Code Segmentは内部で実行に必要なData Segmentを数えている。Data Segmentの取得に成功するとこの値が、デクリメントされ、0になると必要なData Segmentが全て揃ったことと判断される。全て揃った際にはThread poolへ送られる。 - -setKey移行に処理を記述した場合、その処理が行われない可能性がありThread poolへと送られNullPointerExceptionを引き起こす。 - -\begin{table}[html] -\lstinputlisting[label=src:NullPointerException,caption=NullPointerExceptionになる可能性がある]{source/ShowDataFailed.java} -\end{table} - -ソースコード\ref{src:NullPointerException}は、for文でsetKeyとids.createをcntの回数呼び、動的にData Segmentの取得数を決めようとしている。しかし、setKeyが最初に呼ばれた際に、Data Segmentの取得に成功すると実行可能と判断されてしまう。runの中でinfoの配列の要素だけ中身を表示させようとしてるが、2回目のasClassでNullPointExceptionを引き起こす。今回の場合、コンストラクタ内をソースコード\ref{src:success}のように記述する必要がある。 - -\begin{table}[html] -\lstinputlisting[label=src:success,caption=NullPointerExceptionにならない記述]{source/ShowData.java} -\end{table} -\subsubsection{singleton Code Segment} \ No newline at end of file diff -r b9b3f2241ab4 -r 930eae4e8aeb paper/chapter2.tex --- a/paper/chapter2.tex Tue Jan 13 17:10:56 2015 +0900 +++ b/paper/chapter2.tex Fri Jan 16 14:44:05 2015 +0900 @@ -60,34 +60,6 @@ \end{center} \end{table} -\subsection{表示画面の切り替え} -ゼミなど発表者が多数いる場合、発表者が変わるたびにアプリケーションを立ち上げ直すのは手間である。 -そのため、アプリケーションに切り替えの機能を実装するのが望ましい。そこで、AliceVNCに切り替えの機能を実装した。 - -TreeVNCにも同様に切り替え機能が存在するが、AliceVNCの切り替え機能と挙動が異なる(図\ref{fig:changeTree} \ref{fig:changeAlice})。 - -\begin{figure}[htbp] - \begin{minipage}{0.5\hsize} - \begin{center} - \includegraphics[width=80mm]{images/changeTreeVNC.pdf} - \end{center} - \caption{TreeVNCにおける切り替え} - \label{fig:changeTree} - \end{minipage} - \begin{minipage}{0.4\hsize} - \begin{center} - \includegraphics[width=80mm]{images/changeAliceVNC.pdf} - \end{center} - \caption{AliceVNCにおける切り替え} - \label{fig:changeAlice} - \end{minipage} -\end{figure} - - -%図の変更 -TreeVNCの場合、Root Nodeが常にVNCServerと接続するため、切り替えが行われる際にはRoot Nodeが画面共有のrequestを出したノードと接続を行う。 -AliceVNCの場合、Root Nodeではなく画面共有のrequestを出したノードが自分自身のVNCServerと接続を行う。そのため、AliceVNCは、VNC Serverとノード間にネットワーク遅延が無いという利点がある。 -しかし、図 \ref{fig:changeAlice}のように底辺にいるノードが配信を行った場合、1度Root Nodeまでデータを上げる必要がある。従って、全ノードにデータが行き渡るにはTreeVNCと比べ2倍の時間がかかる。 \section{水族館ゲーム} Aliceで作成された始めての分散アプリケーションである。Aliceに分散アプリケーションを記述する能力があることを確かめるために作成された。 @@ -122,8 +94,13 @@ \end{figure} -\section{木構造をデータベースJungle} +\section{分散データベースJungle} JungleはスケーラビリティのあるCMSの開発を目指して当研究室で開発されている非破壊的木構造データベースである。 +非破壊的にデータを編集を行なうため、過去の全てのデータを参照することができる。また、編集の際にロックが不要であるため、破壊的木構造に比べスケールアウトがし易い。 +Jungleはデータの編集の際にlogが残すため、障害が発生してもlogを読み込ませることにより前回の状態を再現することができる。このlogをハードディスクに書き出すことにより永続性を持たせることも可能である。 + +この木構造データベースを複数接続することにより、可用性と分断耐性をもつ分散データベースJungleとなる。 +Aliceはトポロジーの形成とデータアクセスへの機構を提供している。 \section{bitonic sort} bitnic sortは並列ソートであり、Aliceがマルチコアに対応していることを確認するため実装した。 diff -r b9b3f2241ab4 -r 930eae4e8aeb paper/conclusion.tex --- a/paper/conclusion.tex Tue Jan 13 17:10:56 2015 +0900 +++ b/paper/conclusion.tex Fri Jan 16 14:44:05 2015 +0900 @@ -6,4 +6,23 @@ \subsection{データの永続性の確保} -\subsection{DataSegmentKeyの領域分け} \ No newline at end of file +\subsection{DataSegmentKeyの領域分け} + +\subsection{記述に関する注意点} +\subsubsection{setKey のシンタックス問題} +setKeyメソッドをコンストラクタ等で呼ぶ際、setKeyメソッドを必ず最後に呼ばなければならない。 + +Code Segmentは内部で実行に必要なData Segmentを数えている。Data Segmentの取得に成功するとこの値が、デクリメントされ、0になると必要なData Segmentが全て揃ったことと判断される。全て揃った際にはThread poolへ送られる。 + +setKey移行に処理を記述した場合、その処理が行われない可能性がありThread poolへと送られNullPointerExceptionを引き起こす。 + +\begin{table}[html] +\lstinputlisting[label=src:NullPointerException,caption=NullPointerExceptionになる可能性がある]{source/ShowDataFailed.java} +\end{table} + +ソースコード\ref{src:NullPointerException}は、for文でsetKeyとids.createをcntの回数呼び、動的にData Segmentの取得数を決めようとしている。しかし、setKeyが最初に呼ばれた際に、Data Segmentの取得に成功すると実行可能と判断されてしまう。runの中でinfoの配列の要素だけ中身を表示させようとしてるが、2回目のasClassでNullPointExceptionを引き起こす。今回の場合、コンストラクタ内をソースコード\ref{src:success}のように記述する必要がある。 + +\begin{table}[html] +\lstinputlisting[label=src:success,caption=NullPointerExceptionにならない記述]{source/ShowData.java} +\end{table} +\subsubsection{singleton Code Segment} \ No newline at end of file diff -r b9b3f2241ab4 -r 930eae4e8aeb paper/introduciton.tex --- a/paper/introduciton.tex Tue Jan 13 17:10:56 2015 +0900 +++ b/paper/introduciton.tex Fri Jan 16 14:44:05 2015 +0900 @@ -2,4 +2,11 @@ \pagenumbering{arabic} \section{研究背景と目的} +スマートフォンやタブレット端末の普及率が年々増加している。それに伴いインターネット利用者数も増加しており、ネットワーク上のサービスの利用者の増加は必至である。従って、サービスには、信頼性とスケーラビリティーが要求される。 +ここでいう信頼性は定められた環境下で安定して期待しされた動作を行うことをさす。スケーラビリティーはサービスの利用者が増大した場合、メモリ等のリソースを追加するだけでサービスを維持できる性能をさす。また、CPUが発熱の問題からマルチコアが主流になっているため、プログラムには並列性も求められる。 +しかし、これら全てをもつ分散プログラムをユーザーが一から記述することは容易ではない。 + +そこで本研究室ではデータをData Segment、タスクをCode Segmentという単位で分割して記述する並列分散フレームワークAliceの開発を行っている。AliceはJavaで実装され、ノード間の通信のためのAPIが提供されている。また、オーバーレイネットワークを自動的に構成するTopology Managerという機能を持つため、分散プログラムのシュミレーションを行うことができる。 + +本研究では、Aliceの実行速度の問題の解決、および実用的な分散プログラムの記述に必要な機能の洗い出し実装を行う。また、実行速度の改善効果および、TreeVNCとTreeVNCをAliceを用いて実装したAliceVNCの比較をコードの観点から評価を行う。 \section{論文の構成} diff -r b9b3f2241ab4 -r 930eae4e8aeb paper/master_paper.tex --- a/paper/master_paper.tex Tue Jan 13 17:10:56 2015 +0900 +++ b/paper/master_paper.tex Fri Jan 16 14:44:05 2015 +0900 @@ -8,9 +8,9 @@ \usepackage{url} \input{dummy.tex} %% font -\jtitle{分散フレームワーク Alice の改良と評価} -\etitle{Design and Implementation Distributed network framework Alice} -\year{平成23年度} +\jtitle{分散フレームワーク Alice 上の meta computation と応用} +\etitle{Distributed framework Alice} +\year{平成26年度} \affiliation{\center% \includegraphics[clip,keepaspectratio,width=.15\textwidth] {images/u-ryukyu-Mark.pdf}\\