\documentclass[techrep, ,dvipdfmx]{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage[dvipdfmx]{color}
\usepackage{url}
\usepackage{listings}
\lstset{%
  language={C++},%使用言語
  basicstyle={\small},%書体
  commentstyle={\small\itshape},%コメントの書体
  keywordstyle={\small\bfseries},%キーワードの書体
  %identifierstyle={\small},%
  %ndkeywordstyle={\small},%
  stringstyle={\small},%文字列の書体
  frame={trlb},%外枠
  breaklines=true,%改行
  columns=[l]{fullflexible},%
  xrightmargin=0zw,%
  xleftmargin=3zw,%
  %numbers=none,%行番号の表示
  %numberstyle={\scriptsize},%行番号の書体
  %numbersep=1zw,%
  %stepnumber=1,
  lineskip=-0.5ex,%
  captionpos=b,%キャプションの位置
}
\renewcommand{\lstlistingname}{Code}
\input{dummy.tex} %% Font 

% ユーザが定義したマクロなど．
\makeatletter

\begin{document}

% 和文表題
\title{分散フレームワークAliceの圧縮機能}
% 英文表題
\etitle{}

% 所属ラベルの定義
\affilabel{1}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}
\affilabel{2}{琉球大学大学院理工学研究科情報工学専攻 \\Interdisciplinary Information Engineering, Graduate School of Engineering and Science, University of the Ryukyus.}
\affilabel{3}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}

% 和文著者名
\author{
  照屋 のぞみ\affiref{1}\and
  杉本 優\affiref{2}\and
  河野 真治\affiref{3}
}

% 英文著者名
\eauthor{
  Nozomi TERUYA\affiref{1}\and
  Yu SUGIMOTO\affiref{2}\and
  Shinji KONO\affiref{3}
}

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{照屋 のぞみ\\
        〒903-0213 沖縄県西原町千原1番地\\
	琉球大学工学部情報工学科\\
        TEL: (098)895-2221\qquad FAX: (098)895-8727\\
        email: kokubo@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
  当研究室ではデータをData Segment、タスクをCode Segmentという単位で分割して記述する手法を提唱しており、そのプロトタイプとして並列分散フレームワークAliceを開発している。
　本研究ではAliceに実用的なアプリケーションを作成するために必要な動的なトポロジーを管理する機能とAliceの制御を行えるメタ計算を追加した。また、通信時におけるData Segmentの多態性を実現するため、Data SegmentをObject型、MessagePackを使ったByteArray型、圧縮されたByteArray型の３つの形式で表現できるメタ計算の設計と実装、性能評価を行った。


\end{abstract}

% 英文概要　仮
\begin{eabstract}
   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 .
In this paper, we add functions which control dynamic topology and Alice computation. And we show Alice has an ability to write useful application.
Furthermore we improve Alice performance. So Alice works 12% faster and has same performance as Federated Linda.
\end{eabstract}

% 表題などの出力
\maketitle

% 本文はここから始まる

\section{研究背景と目的}
当研究室ではデータをData Segment、タスクをCode Segmentという単位で分割して記述する並列分散フレームワークAliceの開発を行っている。Aliceでは分散環境の構築に必要な処理をMeta Computationとして提供することで、スケーラブルな分散プログラムを信頼性高く記述できる環境を実現している。

Alice が分散プログラムを記述する能力を有することは確認された。だが、実用的な分散プログラムを作成するためには、ノードの切断・再接続時に対応した処理を行いたい場合や圧縮されたデータ形式で通信を行いたい場合がある。

本研究では、 Alice の Computation の 制御を行う Meta Computation を実装した。プログラムに Alice の制御を行うメタプログラムを記述することにより切断や再接続の状況に応じた処理を元のコードを変更することなく指定することができる。また、圧縮機能を持ったDataSegmentManagerを追加することによりData Segmentの多態性を実現した。 
そして、 TreeVNC と TreeVNC を Alice を用いて実装した AliceVNC の比較をコードの観点から評価を行った。


\section{分散フレームワーク Alice の概要}
\subsection{Data SegmentとCode Segment}
AliceはデータをData Segment、（以下DS）タスクをとCode Segment（以下CS）という単位に分割してプログラミングを行う。
DSはAliceが内部にもつデータベースによって管理されている。DSに対応する一意のkeyが設定されており、そのkeyを用いてデータベースを操作する。

CSは実行に必要なDSが揃うと実行されるという性質を持ち、入力されたDSに応じた結果が出力される。
CSを実行するために必要な入力DSはInputDS、CSが計算を行った後に出力されるDSはOutput DSと呼ばれる。データの依存関係にないCSは並列実行が可能であるため、並列度を上げるためにはCSの処理内容を細かく分割して依存するデータを少なくするのが望ましい。

\subsection{Data Segment}
複数のスレッドから１つのデータに変更を行うためには、データの不整合を防ぐためのlockが必要になる。複数の関係のない要素を１つのデータオブジェクトで表現した場合、全ての操作でlockが必要になる。このlockがスケラビリティーを低下させる。つまりデータのサイズも並列計算には重要である。

Aliceはデータを細かく分割して記述する。その細かく分割されたデータをDSと呼ぶ。
実際には特定のオブジェクトにマッピングされ、マッピングされたクラスを通してアクセスされる。

\subsection{Data Segment Manager}
DSは実際にはqueueに保存される。queueには対になるkeyが存在し、keyの数だけqueueが存在する。
この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に書き込まれる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.3]{images/remote_datasegment.pdf}
\end{center}
\caption{Remote DSMは他のノードのLocal DSMのproxy }
\label{fig:RemoteDSM}
\end{figure}

\subsection{Data Segment API}
以下のData Segment APIを用いてデータベースにアクセスする。
putとupdateはDSを追加する際に、peekとtakeはDSを取得する際に使用する。

\begin{itemize}
\item {\ttfamily void put(String managerKey, String key, \\ Object val)}
\end{itemize}
DSをqueueに追加するためのAPIである。第一引数で指定したDSMの中の、第二引数に対応するqueueに対してDSを追加している。
\begin{itemize}
\item {\ttfamily void update(String managerKey, String key, \\ Object val)}
\end{itemize}
updateもqueueに追加するためのAPIである。putとの違いは、先頭のDSを削除してからDSを追加することである。そのためAPI実行前後でqueueの中にあるDSの個数は変わらない。

\begin{itemize}
\item {\ttfamily void take(String managerKey, String key)}
\end{itemize}
takeはDSを読み込むためのAPIである。読み込まれたDSは削除される。要求したDSが存在しなければ、CSの待ち合わせ （Blocking）が起こる。putやupdateによりDSに更新があった場合、takeが直ちに実行される。

\begin{itemize}
\item {\ttfamily void peek(String managerKey, String key)}
\end{itemize}
peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。


\section{Code Segment}
Alice上で実行されるタスクの単位がCSである。ユーザーはCSを組み合わせることでプログラミングを行う。CSをユーザーが記述する際に、内部で使用するDSの作成を記述する。

Input DS と Output DSはCSに用意されているAPIを用いて作成する。
Input DSは、LocalかRemoteか、またkeyを指定する必要がある。CSは、記述したInput DSが全て揃うとThread poolに送られ、実行される。

Output DSもLocalかRemoteか、またkeyを指定する必要がある。
Inputの場合はsetKeyを呼ぶ際、Outputの場合はput(またはupdate)の際にノードとkeyの指定を行っている。
しかし、どの時点でノードとkeyの指定を行えばよいか、どのようなAPIを用意するべきかは、議論の余地がある。

\section{Code Segmentの記述方法}
CSをユーザーが記述する際にはCSを継承して記述する(ソースコード \ref{src:StartCodeSegment} ,\ref{src:CodeSegment})。
継承することによりCode Segmentで使用するAPIを利用する事ができる。

\begin{table}[html]
\lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java}
\lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java}
\end{table}

Alice には、Start CS (ソースコード \ref{src:StartCodeSegment})というC の main に相当するような最初に実行される CS がある。
Start CSはどのDSにも依存しない。つまりInput DSを持たない。
このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。

ソースコード \ref{src:StartCodeSegment}は、5行目で次に実行させたいCS（ソースコード \ref{src:CodeSegment}）を作成している。8行目でOutput DSMを通してLocal DSMに対してDSをputしている。
Output DSMはCSの{\tt ods}というフィールドを用いてアクセスする。
Output DSMは{\tt put}と{\tt update}を実行することができる。
TestCodeSegmentはこの"cnt"というkeyに対して依存関係があり、8行目でupdateが行われるとTestCodeSegmentは実行される。

ソースコード\ref{src:CodeSegment}は、0から10までインクリメントする例題である。
2行目で取得されたDSが格納される受け皿を作る。Input DSMがもつcreateメソッド使うことで作成できる。
\begin{itemize}
\item {\ttfamily Receiver create(CommandType type)}
\end{itemize}

引数にはCommandTypeが取られ、指定できるCommandTypeは{\tt PEEK}または{\tt TAKE}である。
Input DSM はCSの{\tt ids}というフィールドを用いてアクセスする。

4行目から6行目はコンストラクタである。コンストラクタはオブジェクト指向のプログラミング言語で新たなオブジェクトを生成する際に呼び出されて内容の初期化を行う関数である。

TestCodeSegmentのコンストラクタが呼ばれた際には、
\begin{enumerate}
\item TestCodeSegmentが持つフィールド変数Receiver input1の定義が行われる。
\item 次にCSのコンストラクタが呼ばれ、CSが持つフィールド変数の定義と初期化が行われる。
\item {\tt ids.create(CommandType.TAKE)}が行われ、input1の初期化が行われる。
\item 最後にTestCodeSegmentのコンストラクタの5行目が実行される。
\end{enumerate}

5行目はInput DSMがもつsetKeyメソッドによりLocal DSMからDSを取得している。
\begin{itemize}
\item \verb+void setKey(String managerKey, String key)+
\end{itemize}
setKeyメソッドにより、どのDSMのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定できる。コマンドの結果がレスポンスとして届き次第CSは実行される。

runメソッドの内容としては10行目で取得されたDSをInteger型に変換してcountに代入している。
16行目で もう一度TestCodeSegmentのCSが作られる。
17行目でcountの値をインクリメントしてLocal DSMに値を追加する。
13行目が終了条件であり、countの値が10になれば終了する。

\subsection{ComputationとMeta Computation}
AliceのComputationは、keyで指し示されるDSを待ち合わせてCSを実行させると定義できる。
それに対して、AliceのMeta Computationは、AliceのComputationを支えているComputationのプログラミングと定義できる。

例えば、トポロジーを指定するAPIはMeta Computationである。Aliceが動作するためにはトポロジーを決める必要がある。つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。トポロジーが決定するとそのトポロジーを構成する計算が行われる。トポロジーを指定するAPIはその構成の計算をプログラミングして変更するものである。
他にも再接続の動作を決めるAPIや切断時の動作を決めるAPIはMeta Computationである。

これらのMeta ComputationがAliceのComputationに影響することはない。プログラマーはCSを記述する際にトポロジーや切断、再接続という状況を予め想定した処理にする必要はない。プログラマーは目的の処理だけ記述する。そして、切断や再接続が起こった場合の処理を記述しMeta Computationで指定する。
このようにプログラムすることで、通常処理と例外処理を分離することができるため、シンプルなプログラムを記述できる。


\section{Meta Data Segment}
DSは、アプリケーションに管理されているデータのことである。アプリケーションを構成するCSによってその値は変更される。
それに対してMeta DSは、分散フレームワークAliceが管理しているデータである。Aliceを構成するCSによってのみ、その値は変更される。一部のMeta DSはアプリケーションに利用することができる。

例えば、"start"というkeyでは、ノードがStart CSを実行可能かどうかの状態を表す。他にも"\_CLIST"というkeyでは、利用可能なRemote DSの一覧が管理されている。ユーザーはこの一覧にある名前を指定することで、動的にDSの伝搬などを行うことができる。

また、Input DSに付随しているものもある。Input DSはCS内部でReceiverという入れ物に格納される。ユーザーは、Receiverに対して操作することでDSを入手できる。
このReceiverには、fromというフィールドがあり、このDSを誰がputしたという情報が入っている。この情報をデータの伝搬する際に利用することで、DSをputしたノードに送り返すことを防ぐことができる。

Meta DSはDS同様にDS APIを用いて取得できる。

\section{Meta Code Segment}
CSはアプリケーションを動作させるために必要なタスクであり、ユーザーによって定義される。
それに対してMeta CSはAliceを構成するタスクである。つまりMeta CSの群はAliceのComputationと言い換えることができる。一部のみユーザーが定義をすることができ、Aliceの挙動を変更することができる。




\section{AliceVNC}
AliceVNCは、当研究室で開発を行っているTreeVNCをAliceを用いて実装された、授業向け画面共有システムである。
Aliceが実用的なアプリケーションを記述する能力をもつことを確認するために作成した。

授業でVNCを使う場合、１つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう(図\ref{fig:vnc})。この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである(図\ref{fig:treestructure})。TreeVNCは、TightVNCのソースコードを利用して開発されている。

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[width=60mm]{images/vnc.pdf}
    \end{center}
    \caption{VNCの構造 }
    \label{fig:vnc}
\end{figure}

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[height=50mm]{images/treestructure.pdf}
    \end{center}
    \caption{TreeVNC, AliceVNCの構造 }
    \label{fig:treestructure}
\end{figure}



% \input{chapter3}
% \input{chapter5}
% \input{conclusion}

\nocite{*}
%\nocite{opencl}
%\nocite{opencl:ref}
%\nocite{opencl:applied}
%\nocite{yutaka:os}
%\bibliographystyle{ipsjunsrt}
%\bibliography{sigos}
%\bibliography{cerium,book}


\end{document}