\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvips]{graphicx}
\usepackage{fancyhdr,picins}
\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.eps}}琉球大学主催 工学部情報工学科 卒業研究発表会}
\rhead{}
\cfoot{}

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

\begin{document}
\title{分散プログラムにおけるデバッグツールの設計と実装}
\author{035713J 小野雅俊 {}{} 指導教員 : 河野真治}
\date{}
\maketitle
\thispagestyle{fancy}

\section{スケーラビリティをデバッグする}
分散アプリケーションが多数開発されている近年、
ノードやネットワークの動的な変化、故障、性能の多様性を考慮した
フレームワークが必要である。
分散環境ではスケーラビリティを確保すること重要である。ここでの
スケーラビリティとはノードの規模の増大にも関わらず、
アプリケーションの性能を維持できることを指す。
分散アルゴリズムの作成には、論理的なプログラムの正しさだけでなく、
スケーラビリティのデバッグを可能にする必要がある。
つまり、デバッガ自体をスケーラブルに作る必要がある。
そのため、分散
フレームワークとして本研究室が提案しているFederated Lindaに、
スケーラビリティなデバッグを行う為のメタな通信を行うプロトコルエンジン
を設計し実装した。

分散プログラムの
デバッグを行う際には通信は必須であるが、その通信によって
本来の通信に影響を及ぼす恐れがある。
ここでは、スケーラビリティには若干問題があるが、
本来の通信に影響を与えないように、一つのトークンをリング上に
流す方法を提案\cite{aa,bb}している。本論文ではPCクラスタ上で実際の通信を行ない、100台程度の
分散プログラムでの評価を行なった。

\section{Federated Linda}
Federated Lindaとは、複数のタプル空間を相互に
結ぶプロトコルエンジンによって
接続する分散プログラミングモデルである。
Lindaと同じAPIを持つが、
Lindaが一つのタプル空間を共有するのに対し、
Federated Lindaは複数のタプル空間を個別に持つ。
クライアントのアクセス数に対応して、
タプルスペースの数を増やし処理を分散させる事により、スケーラビリティを保つ。

\subsection{Federated Linda Protocol}
Federated Lindaは以下の様にして通信を行う。

\begin{itemize}
\item public PSXLinda open(String \_host,int \_port)

Linda Serverに対し、接続を行う。引数はホスト名とポート番号をとる。返り値はタプルスペースの番号となる。

\item public PSXReply in(int id)

タプルスペース番号より引数で指定したidのタプルの受け取りを要求する。
受け取りは、返値のPSXReplyをチェックすることにより非同期に行なう。
in では待ち合わせは行なわれない。Call back 形式でタプルを受け取る
ことも出来る。

\item public PSXReply out(int id, ByteBuffer data)

引数で指定したidでByteBuffer内のデータを送信する。

\item public int sync(long mtimeout) 

接続しているLinda Serverとタプルの送受信のポーリングを行う。

\end{itemize}


\section{Protocol Engine}
Protocol Engineとはタプルスペースを介してデータをやり取りするEngineである。
二つのサーバー間でやり取りを行う場合、以下のようなプログラムとなる。

例）ポートを変えた、二つのLocal Linda Server間のデータをやり取りする場合

\begin{verbatim}
FederatedLinda fdl;
PSXLinda getpsx;
PSXLinda sendpsx;
PSXReply in;
ByteBuffer data = ByteBuffer.allocate(10);

//通信を初期化する
fdl = FederatedLinda.init();
//データを取ってくるホストと受け渡すホストとの接続開始
getpsx = fdl.open(localhost,10000);
sendpsx = fdl.open(localhost,10001);
//取ってくるホストからinを指定してデータを取得
in = getpsx.in(10)
data = in.getData();
//受け渡すホストに対しデータとidを指定して同期
sendpsx.out(10,data);
fdl.sync();
\end{verbatim}

\section{Meta Protocol Engine}
デバッグ用の通信はLinda Server内部に直接アクセス出来なければ
ならない。これをLinda Server内のMeta Protocol Engine に
よって実現する(図\ref{mpe})。
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.3]{img/3.eps}
\caption{Meta Protocol Engine}
\label{mpe}
\end{center}
\end{figure}

Meta Engine は、
通常のFederatedLindaと同様のin/out APIを持つ。
Meta Engine では、\verb+sync()+が、属するLinda Server
自体のポーリングを行なう。\verb+sync()+の間は、
通信は行なわれず タプル空間は変化しない。
Meta Engine は安全にタプル空間にアクセス出来る。
Meta Engine のプログラムは、
Linda Serverのメインループで指定することが出来、
Server 毎に独自の動作をさせることが可能である。

3台のLinda Server間でMeta Engineがデータをやり取りする場合
のUMLシーケンス図は
図\ref{ringthree}のようになる。
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.2]{img/meta_ring_three.eps}
\caption{3台間の通信}
\label{ringthree}
\end{center}
\end{figure}

\section{測定}
本稿では
分散通信に影響を最低限にするために、Ringで性能を評価する。
Ring では通信パケットは一つのみであり、デバッグ対象への
影響が小さい。しかし、スナップショットや一時停止などの
デバッグ操作をするためには、全ノードを周回する必要がある。
これはo(n)であり、十分にスケーラビリティがあるとは言えない。
しかし、もっとも影響が少ない方法なので、どの程度まで使える
かを測定することには意味がある。

ここでは、通信パケットの大きさを変えて、
3〜100までの台数でデータが1周(図\ref{metaring})する時間、
および1000周(図\ref{metaring1000})した時に掛かった時間を測定する。
前者では接続の手間を含む通信時間、後者では通信のみの時間を
計ることが出来る。

実験は、
琉球大学
情報工学科のクラスタ上(Core Duo 2GHz,メモリ1GB)で、
クラスタジョブ管理システム
Torqueを用いて行なった。
ネットワークはAlaxalA Gigabit Ethernet Switchで構成されている。
クラスタ自体は180台あるが、
安定して動作する100台までを使用して測定を行なった。

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.3]{img/metaring1.eps}
\caption{接続を含む一周の時間}
\label{metaring}
\end{center}
\end{figure}
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.3]{img/metaring1.eps}
\caption{千周の平均周回時間}
\label{metaring1000}
\end{center}
\end{figure}

X軸が台数、Y軸がミリ秒、ラインの色が通信するデータサイズを表す。
両図から見てわかる通り、データの量にはあまり依存する事はなくほぼ同じラインを形作っている。
データを1周のみした場合は1サイクルあたり約14000ms、一台あたり約140ms掛かっている計算になり、
それに対し1000周した際に掛かった時間は、1サイクルおよそ60ms、一台につき約0.6msとなっている。
これより、一度、接続してしまえば、
Meta Engine での通信は実際に100台程度のデバッグに使用するのに十分な性能を
持っていることが確認出来た。

\section{まとめと課題}
本稿ではデバッグを行う為に通常通信とは他に、Metaで通信するMeta Protocol Engineを実装し評価した。
今回は、スナップショットなどの実際のデバッグ機能を実装することは出来なかった。
通信の実験においても、
同クラスタ上で別のRing通信や他のMetaLinda通信等があった場合の干渉の程度
などを測定する必要があると考えられる。

\thispagestyle{fancy}
\begin{thebibliography}{9}
\bibitem {aa}上里献一, 河野真治 SuciライブラリのスナップショットAPIを利用した並列デバッグツールの設計
\bibitem {bb}渕田 良彦, 河野 真治 分散プログラミングモデルFederated Lindaと分散デバッグ
\end{thebibliography}
\end{document}