\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[papersize={210truemm,297truemm},
top=3truecm,bottom=3truecm,left=2truecm,right=2truecm]{geometry}
\usepackage{setspace}
\usepackage[dvipdfm]{graphicx}
\usepackage{listings,jlisting}
\usepackage{picins}
\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 卒業研究発表予稿}
\rhead{}
\cfoot{}

\lstset{%
  frame=single,
  stringstyle={\ttfamily},
  commentstyle={\ttfamily},
  identifierstyle={\ttfamily}, 
  keywordstyle={\ttfamily},
  basicstyle={\ttfamily},
  breaklines=true,
  xleftmargin=0zw,
  xrightmargin=0zw,
  framerule=.2pt,
  columns=[l]{fullflexible},
  numbers=left,
  stepnumber=1,
  numberstyle={\scriptsize},
  numbersep=1em,
  language={Java},
  tabsize=4,
  lineskip=-0.5zw,
  morecomment={[s][]{/**}{*/}},
}


\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{11mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\begin{document}
\title{分散ネットフレームワーク Aliceにおける例題の作成}
\author{学籍番号 095732B 氏名 杉本優{}{} 指導教員 : 河野真治}
\date{}
\maketitle
\thispagestyle{fancy}


\section{研究背景と目的}
インターネット上でのサービスには信頼性とスケーラビリティの両方が要求される。
本研究室ではデータをData Segment 、タスクをCode Segmentという単位に分割して記述する分散ネットフレームワークAlice\cite{1}の開発を行なっている。
AliceはJavaで実装されており、
% ユーザーがAliceを利用するためにはCode Segmentというclassを継承するだけでよい。
% 記述が大変である    こういう口語的なものは論文では使わない
ノード間のData Segmentの送受信APIが提供されている。
% のでユーザーが記述をする必要はない。
また、Blade また PCクラスタ上で分散プログラムのシュミレーションするために、オーバレイネットワークを自動的に構成する
TopologyManagerという機能が搭載されている。
さらに近年のメニーコアのマシンが主流になっている背景からSEDA Architecture\cite{4}を採用しており、マルチコア上 でのスループットの向上を期待している。
% というトポロジーの作成をサポートする機能が含まれているためユーザーはトポロジー完成後の記述を行うだけで良い。
% しかし、提供されているAPIが適当なものであるか、必要な機能が備わっているかどうかは、ソースコード上では確認できず、実際にプログラミングを行うことでしか見えてこない部分である。

本研究はAliceを用いてプログラムを作成することで、Aliceが抱える問題点、APIの見直しを行った。
まず、分散プログラムを書くためのAPIがちゃんとそろっているかどうかを例題を作成することにより確認した。
スケーラビリティがあるかどうかを調べるためには、Blade 上でのシュミレーションを行うことが必要である。
実際にシュミレーションを行い、応答時間の測定を行った。
% そして、Aliceの改良を行い、
% 誰でも簡単に
% 分散プログラムを書けるようなフレームワークを作成するのが目的である。

\section{Alice}
Aliceを使う際に必要なData SegmentとCode Segmentについて説明を行う。
\subsection{DataSegment}
AliceではData Segmentをデータベースとして利用しており、Key Value Storeで実装されている。
従来のKey Value StoreのようにKey と Valueが一対になっているのではなく、Key毎にキューを持っていてデータを管理している。
そのキューに対してData Segment API を用いることでData Segmentにデータを追加、削除を適宜行うことができる。


\begin{itemize}
\item \verb+void put(String key, Value val)+
\item \verb+void update(String key, Value val)+
\item \verb+void peek(Receiver receiver, String key)+
\item \verb+void take(Receiver receiver, String key)+
\end{itemize}



\verb+put+ はデータを追加するための API である。
% キューというのが何か説明する
\verb+update+ はデータを置き換えるための API である。 キューの先頭を置き換える特急メッセージのように動作する。
\verb+peek+ はデータを調べるためのAPIである。目的のData Segment がなければ、Code Segment の待ち合わせ (Blocking) が起きる。
\verb+take+ もデータを読み込むための API である。読み込まれたデータは Key Value Store のキューから取り除かれる

\subsection{CodeSegment}
CodeSegmentはタスクを分割したものであり、Code SegmentはInput Data SegmentとOutput Data Segmentを持つ。CodeSegmentに依存するData Segmentを記述することにより、(図 \ref{fig:dsandcs})のように実行される順番が一意に決まる。Code SegmentはInput Data Segmentが揃い次第Code Segment Managerに送られ順次実行されていく。またCode SegmentにInput Data Segmentがない場合はexecuteにより実行させる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=65mm]{pic/dsandcs2.pdf}
\caption{DataSegment と CodeSegment の依存関係で一意に決まる実行順序}
\label{fig:dsandcs}
\end{center}
\end{figure}



\section{水族館ゲーム}
% 魚の位置が共有されている
% 複数のディスプレイに異なる視点で表示される
% 魚とディスプレイが増えてもサービスを維持できることを確認するため
% このままではスケールしない
Aliceを用いて水族館ゲームの作成を行った。水族館ゲームとは複数の魚の情報をゲームに参加するClinet全体で共有し、複数のディスプレイに異なる視点で表示されるものである。トポロジーはツリー状に構成されている。


水族館ゲームを作成した目的は魚とディスプレイが増えてもサービスを維持できることを確認するためである。しかし、現状では魚の数、参加するClinetが増えるとトップノードが処理すべきCode Segmentが増加していくため、スケールしないと思われる。


以前水族館ゲームをJava3Dで作成したが、JavaのVersion が1.7になったのに伴いJavaFXというGUIプラグインが追加されたため、JavaFXで水族館ゲームを書きなおした。(図 \ref{fig:JavaFX})


\begin{figure}[htbp]
\begin{center}
\includegraphics[width=80mm]{pic/for_Fx.pdf}
\caption{JavaFX版 水族館ゲーム}
\label{fig:JavaFX}
\end{center}
\end{figure}


% 以下のようなことを書かないで、Code segment/Data segment が Alice で、どう表現されるかを書く
%\section{注意すべき記述}
%Aliceを記述する際に、注意すべき記述がある。(ソースコード \ref{fig:NullPointerException})
%Code Segmentを作成する際に、コンストラクト内でidsに対してsetKeyを行った後に、処理を記述しても実行されない可能性がある。
%Code Segmentは内部で必要なData Segmentの数を数えている。Data Segmentが取得されるたびにこの値がデクリメントされていき、0になった時にCode Segmentがactiveになる。値が0であるかを確認するのは別スレッドであるため、setKey以降に処理を記述してもThread Poolに送られてしまい、NullPointerException等のエラーが起こる可能性がある。
%
%\begin{table}[htbp]
%\lstinputlisting[label=fig:NullPointerException, caption=実行するとNullPointerExceptionを起こす]{source/NullPointerException.java}
%\end{table}


\section{実験}
トップノードから子ノードに対してデータの送信し、子ノードは受けとったデータをトップノードに送り返す。この作業にかかる時間の測定を行う。台数が増えた際の時間の変化により、スケールするかどうかを評価する。マシン 48 台,CPU Intel(R) Xeon(R) X5650 @ 2.67GHz, 仮想コア数 4,CPU キャッシュ 12MB。Blade 上の仮想マシン上での測定を行った。


\begin{figure}[htbp]
\begin{center}
\includegraphics[width=90mm]{pic/result2.pdf}
\caption{測定結果}
\label{fig:result2}
\end{center}
\end{figure}

\section{考察}
サービスに参加するClientの数が増加するに連れて、時間が増加していく。これはトップノードがData Segmentを子ノードに送信するというCode SegmentがThread Poolに次々に送られてくる。しかし、同時実行可能数はCPUに依存するため、Client数が増えるに従ってThread Poolで実行されるのを待つ時間が増えていくのではないかと思われる。
また、原因の一つにはSEDAがあげられる。SEDAはスループット重視の実装であるので、多段のパイプラインのせいでレスポンスが遅れてしまう。

% 今後の課題ではなくて、今のAPIの評価を行う
\section{APIの評価}
現在、Aliceが提供されているAPIだけで分散プログラムを記述することが可能であったものの、改善したほうがよいAPIがある。


\verb+setKey+ はシンタックス的に問題がある。setKeyを呼部とData Segmentの取得を始める。そして必要なData Segmentが揃った時点でactiveになってしまうため、\verb+setKey+以降に処理を記述しても、その処理が実行される保証がない。コンストラクタ内でsetKeyを呼び出すのではなく、setKeyを行うメソッドを用意するなど工夫する必要がある。


\verb+peek+ でData Segmentを取得、\verb+put+ でData Segmentの追加を行なっているが、この際にMessage Pack\cite{3}でdecode / encodeの操作が行われている。
他のClientに対してデータの送受信するために行う場合はやむを得ないが、local に送受信する際にも行なっている。localに対しての送受信はencode / decode 抜きに処理できるようにするのが望ましい。

\section{今後の課題}
{\bf Key} 本実装ではData Segment相互の参照はKey経由となる。分散実装では妥当であるが、並列実装ではすべてのData SegmentをKVSに格納するのは性能的な問題を引き起こす。一方で、分散記述と並列記述がかけ離れてしまうのも好ましくない。また、本来はKVSは持続性を持つべきだと思われる。持続性をもつことで、トラブルで処理が途中で中断された場合であっても途中から処理を再開可能となる。
\thispagestyle{fancy}
\begin{thebibliography}{9}

\bibitem{1}
赤嶺一樹, 河野真治. 分散ネットワークフレームワーク Alice の 提案と実装 Design and Implementation Distributed network framework Alice 平成23年度 学位論文(修士)
\bibitem{2}
赤嶺一樹, 河野真治. Meta engine を用いた federated linda の実験. 日本ソフトウェア科学会第 27 会大会, Sep 2010.
\bibitem{3}
古橋 貞之,新城靖. 分散システムのためのメッセージ表現手法 に関する研究 システム情報工学研究科修士論文
\bibitem{4}
Matt Welsh, David Culler, and Eric Brewer. Seda: an architecture for well-conditioned, scal- able internet services. SIGOPS Oper. Syst.Rev., Vol.35, No.5, pp. 230-243, 2001.
\end{thebibliography}
\end{document}