changeset 1:484bf45ca3ee

add new file
author sugi
date Sun, 31 Mar 2013 16:35:18 +0900
parents 88c3fd4f9bb2
children ddd5a624bb7a
files alice.tex bibliography.tex compare.tex conclusion.tex improvement.tex introduction.tex problem.tex sigos.tex
diffstat 8 files changed, 155 insertions(+), 13 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/alice.tex	Sun Mar 31 16:35:18 2013 +0900
@@ -0,0 +1,56 @@
+\section{分散ネットフレームワークAlice}
+Aliceは、本研究室で開発を行なっている分散管理フレームワークである。Cell用ののOpen CLに似たTask管理フレームワークCerium\cite{kono09b} \cite{cerium-sourceforge}とLinda\cite{linda} を相互接続した分散フレームワークであるFederated Lindaの開発を通して得られた知見が生かされている。
+
+まず、Aliceを使用するに必要なData Segment、Code Segmentについて説明を行う。
+\subsection{Data Segment API}
+Data Segmentは数値や文字列などのデータ構造体的に保持するが、Data Segmentの相互参照が問題になる。AliceはData Segmentをデータベース的に扱い、またData Segmentは必ずuniqueなKeyをもつ。つまりKey Value Storeとして考えることができる。Key毎にキューがあり、Key毎に順に実行される。Key毎の追加と取得は、Lindaに準じた設計となっている。
+
+Data Segmentを管理するのがData Segment Manager(以下DSM)である。ノード毎にLocal DSMとRemote DSMが存在する。Local DSMはノード固有のKey Value Storeと考えることができる。Remote DSMは他のノードのLocal DSMのproxyである。AliceのトポロジーマネージャーがRemote DSMを自動的に構成する。
+Key Value Storeへのアクセスはキューによって、ノード内部で逐次化される。それ以外は、すべてJavaのThread poolにより並列実行される。
+
+以下が用意されている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}
+\subsubsection{put}
+\verb+put+ はData Segmentを追加するための API である。Key Value Storeのキューに追加される。 
+
+\subsubsection{update}
+\verb+update+ はData Segmentを更新するためのAPIである。キューの先頭を置き換える。
+\subsubsection{peek}
+peek はData Segmentを取得する。Data Segmentが無ければCode Segmentの待ち合わせが起きる。
+put、updateによりData Segmentの更新があれば、peekが直ちに実行され、待ち合わせを行なっていたCode Segmentがactive queue に移される。
+
+\subsubsection{take}
+takeもData Segmentを取得するためのAPIである。peekとの違いは取得されたData SegmentはKey Value Storeのキューから取り除かれる。
+
+\subsection{Data Segment }
+Data Segmentのデータの表現にはMessage Packを利用している。Message Packに関してJavaにおけるデータ表現は以下の3つあり、これらのデータ表現は制限を伴うが互いに変換可能である。
+\begin{itemize}
+\item {\ttfamily 一般的なJavaのクラスオブジェクト}
+\item {\ttfamily MessagePack for JavaのValueオブジェクト}
+\item {\ttfamily byte[]で表現されたバイナリ}
+\end{itemize}
+
+Data Segmentは、MessagePack for JavaのValueオブジェクトを用いてデータが表現されている。
+MessagePackはJavaのように静的に型付けされたオブジェクトではなく、自己記述なデータ形式である。MessagePack for JavaのValueオブジェクトはMessagePackのバイナリにシリアライズできる型のみで構成されたJavaのオブジェクトである。そのため、Valueも自己記述式のデータ形式になっている。
+
+Valueオブジェクトは通信に関わるときには、シリアライズ・デシリアライズを高速に行うことができる。
+また、ユーザーはメソッドを用いてオブジェクト内部のデータを閲覧、編集することができる。
+
+ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを表現することができる。
+この場合、クラス宣言時に@Messageというアノテーションをつける必要がある。もちろん、MessagePackで扱うことのできるデータのみをフィールドに入れなければならない。
+
+\subsection{Code Segment}
+
+Code Segmentはタスクのことである。Code Segmentをユーザーが記述するときにCode Segment内で使用するData Segmentの作成を記述する。Code SegmentにはInput Data SegmentとOutput Data Segmentを作るAPIが存在する。
+
+
+Input Data Segmentで作成されたData SegmentはRemoteかLocalを指定する必要がある。
+Code Segmentがactiveになるためには、Input Data Segmentが全て揃う必要がある。
+
+
+Output Data Segmentで作成されたData Segmentにも、RemoteかLocalを指定する。
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/bibliography.tex	Sun Mar 31 16:35:18 2013 +0900
@@ -0,0 +1,37 @@
+
+\begin{thebibliography}{10}
+
+\bibitem{linda}
+{Sudhir Ahuja, Nicholas Carriero, and David Gelernter. Linda and friends} IEEE Computer, Aug. 1986.
+
+\bibitem{graphviz}
+{AT\& T Research.}  Graphviz - graph visualization software. \url{http://www.graphviz.org/Documentation.php}.
+
+\bibitem{kono00a}
+{Shinji KONO.}  CbC. \url{http://sourceforge.jp/projects/cbc/}, March 2008
+
+\bibitem{kono09b}
+{Shinji KONO.}  Cerium. \url{http://sourceforge.jp/projects/cerium/}, March 2008
+
+\bibitem{SEDA2001}
+{Matt Welsh, David Culler, and Eric Brewer.} Seda: an architecture for well-conditioned, scalable internet services 
+{\em SIGOPS Oper. Syst. Rev.} Vol.35, No.5, pp. 230-243, 2001.
+
+\bibitem{kono05b}
+{安村恭一, 河野真治.}: 大域 IDを持たない連邦型タプルスペース Federated Linda. 
+情報処理学会 システムソフトウェアとオペレーティング・システム研究会, May 2005.
+\bibitem{kono10d}
+{赤嶺一樹, 河野真治. } Meta Engineを用いたFederated Lindaの実験. 
+日本ソフトウェア科学会第27 回大会 (2010 年度) 論文集, Sep 2010.
+\bibitem{kono11g}
+{赤嶺一樹, 河野真治.}Data Segment API を用いた分散フレームワークの設計. 
+日本ソフトウェ ア科学会第 28 回大会 (2011 年度) 論文集, Sep 2011.
+
+\bibitem{cbc-sourceforge}
+{河野真治, 島袋仁.}: Blender.jp - Blender Japanese Website,
+  \url{http://blender.jp/}. C with Continuationと、そのPlayStationへの応用 . {\em In IPSJ OS, CPSY,} May 2000.
+
+\bibitem{cerium-sourceforge}
+{多賀野海人, 小林佑亮, 宮國渡, 河野真治 (琉球大).} Cell Task Manager Cerium の SPU 内デー タ管理. 情報処理学会システムソフトウェアとオ ペレーティング・システム研究会, April 2009.
+
+\end{thebibliography}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/compare.tex	Sun Mar 31 16:35:18 2013 +0900
@@ -0,0 +1,2 @@
+\section{実験}
+\subsection{実験概要}
\ No newline at end of file
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/conclusion.tex	Sun Mar 31 16:35:18 2013 +0900
@@ -0,0 +1,1 @@
+\section{まとめ}
\ No newline at end of file
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/improvement.tex	Sun Mar 31 16:35:18 2013 +0900
@@ -0,0 +1,29 @@
+\section{改善案}
+\subsection{HashMap}
+HashMapによる探索を排除することはRemoteに対してData Segmentを送受信する際には、マネージャーキーによる探索の操作は削ることは出来ないが、Localにおいては固有のマネージャーキーによる探索は必要ない。改善案としてマネージャーキーを指定しない場合の
+\subsection{Message Pack}
+AliceではData SegmentをValue型という、Message Packが提供している型で保存している。
+Value というクラスは動的に型付けされたオブジェクトを表現することができるため、RubyやPythonのような動的型付けの言語のオブジェクトと同様の扱いをすることができる。
+分散プログラムのアプリケーションはサーバとクライアントのVersionが同じとは限らない。サーバ側が更新され、扱うData Segmentが変更された場合であっても、旧Versionとの互換性が要求される。
+Aliceは、この問題をMessage PackのValue型を用いることで互換性をもたせようとしている。
+
+改善前のAliceではData Segmentをput、updateする段階で、Value型に変換され保存されている。そして、Code Segmentが実行される段階でasClassメソッドに変換したいClassを引数として渡すことで目的の型に戻す。
+しかし、Versionの問題が起こらないLocalの場合、Data SegmentをValue型に変換し、また任意の型に戻すという操作を行う必要はなく、この操作はは単なるオーバーヘッドにしかならない。
+Data Segmentの送信先がRemoteの場合に限りValue型に変換するように変更した。内部ではObject型として保存されているのでCode Segment内で処理をする際にキャストを行う必要があるが、この場合もasClassメソッドにClassを引数として渡すだけでよい。
+そのため、プログラマーはData Segmentとして送られてくるオブジェクトの型を気にすることなくプログラムを記述できる。
+
+\subsection{SEDA Archtecture }
+マルチコアが主流になっている背景からAliceにはSEDA Archtectureを採用しているが、SEDAはスループット重視であり、多段のパイプラインのせいでレスポンスが遅れてしまう。Aliceは現在3段のパイプラインで構成されている。今回SEDAのStageを減らす事により、レスポンスの改善を行った。
+
+\subsection{flip}
+
+Data Segmentの更新におけるオーバーヘッドを減らす方法としてCeriumでも良好な結果を得ているflipを提案する。
+CeriumにおけるflipはInput Data SegmentとOutput Data SegmentをswapさせるAPIである。
+AliceにおいてもCeriumと同様に
+
+Code Segmentはpeek , takeを使いData Segmentを取得する。
+取得したData SegmentはInput Data Segmentと呼ばれCode Segmentの Receiverというフィールドに保存されている。
+そして、Code Segment内でInput Data Segmentに対して処理が行われ、Output Data Segmentとして出力される。
+実際はputまたはupdateメソッドにData Segmentなどを引数として渡すことで行うことができるが、この際に、Data Segmentのコピーが行われる。
+
+flipではInput Data SegmentコピーしてOutput Data Segmentを作成するのではなく、Input Data SegmentそのものをOutput DSMに渡すことでData Segmentの無駄なコピーを防ぐ。
--- a/introduction.tex	Fri Mar 29 03:53:26 2013 +0900
+++ b/introduction.tex	Sun Mar 31 16:35:18 2013 +0900
@@ -1,10 +1,9 @@
-\section{はじめに}
-ブロードバンド環境の普及、タブレット端末およびスマートフォンの普及に伴いインターネット上のサービスに参加するユーザーが増加している。
-そのため、インターネット上のサービスには信頼性とスケーラビリティの両方が要求される。信頼性とは、定められた環境動作下でユーザーが記述した通りの処理を行うことをさす。また、スケーラビリティは、サービスに参加するクライアントの数が増加しても、メモリ等のリソースのみでサービスを維持することをさす。
+\section{研究背景と目的}
+インターネット上のサービスには信頼性とスケーラビリティの両方が要求される。信頼性とは、定められた環境動作下でユーザーが記述した通りの処理を行うことをさす。また、スケーラビリティは、サービスに参加するクライアントの数が増加しても、メモリ等のリソースのみでサービスを維持することをさす。
 
-本研究室では、データをData Segment、タスクをCode Segmentという単位に分割して記述する分散ネットフレームワークAliceの開発を行なっている。Aliceはノード間のData Segmentの送受信APIが提供されている。また、Blade,PCクラスタ上で分散プログラムのシュミレーションをするために、オーバレイネットワークを自動的に構成するTopologyManagerという機能が搭載されている。
+本研究室では、データをData Segment、タスクをCode Segmentという単位に分割して記述する分散ネットフレームワークAliceの開発を行なっている。Aliceはノード間のData Segmentの送受信APIが提供されている。また、Blade,PCクラスタ上で分散プログラムのシュミレーションをするために、オーバレイネットワークを自動的に構成するTopologyManagerという機能が搭載されている。さらにメニーコアのマシンが主流になっている背景からSEDA Archtectureを採用しており、マルチコア上でのスループットの向上を期待している。
  
 
-\subsection{研究の目的}
-Alliceを用いて分散プログラムの例題を作成し、分散フレームワークとしてのAPIが備わっていること、スケーラビリティを持つということが確認できた。
-そこで、次に並列環境にも対応していることを確認するために
\ No newline at end of file
+以前、Aliceが分散フレームワークとしての記述能力を確認するために、水族館の例題の作成を行った。その結果より、Aliceには分散プログラムを記述するのに必要なAPIが備わっていることが確認できている。また、並列環境に対応していることを確認するため、bitonic sortを作成した。しかし、Data Segmentの更新のオーバーヘッドにより、期待した効果を得られなかった。
+
+本研究ではData Segmentの更新オーバーヘッドを解決する手段として新しくAPIを提案し、効果の測定を行う。
\ No newline at end of file
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/problem.tex	Sun Mar 31 16:35:18 2013 +0900
@@ -0,0 +1,19 @@
+\section{現状のAliceの問題点}
+Aliceを用いた例題を通して、様々な問題点が明らかになった。
+APIのシンタックス的問題、永続性の問題、実行速度の問題など解決すべき問題は多々ある。
+特に実行速度の問題では分散環境をテストする例題として作成されたRingの例題(トポロジーを円状に構成し、メッセージが1周する時間を計測する)ではシングルスレッドで実装されているFederated Lindaに実行速度で及ばない。また、並列環境をテストする例題として作成したbitonic sortの例題も期待した結果を得ることができなかった。そこで、実行速度の改善を行うために、オーバーヘッドになっている原因の洗い出しを行った。その結果以下のような原因が見つかっている。
+
+{\bf HashMapの多用 } 
+AliceではData Segment Managerのマネージャーキーによる探索、Data Segmentのキーによる探索などHashMapを多用している。この検索かかる時間が多少ではあるが、オーバーヘッドになっているものと考えられる。
+
+
+{\bf Message Packの convert / unconvert } 
+現在の実装ではputまたはupdateを呼ぶとMessage PackによりValue型へと変換が行われている。また、Code Segment内でValue型から変換元の型への変換が行われる。
+この作業もオーバーヘッドになる。また、配列の要素数が増えると変換に時間が多くかかるので、この作業はできるだけ避けたい。
+
+{\bf SEDA Architecture } 
+Federated Lindaに比べて、通信のレスポンスが遅い原因にはSEDA Architectureが挙げられる。SEDA とはマルチコアスレッドを用いて大量の接続を管理し、受け取ったデータを処理ごとに分けられたステージと呼ばれるスレッドに投げ、処理が終わると次のステージにデータを伝搬させて行く処理方式である。しかし、SEDAはスループット重視の実装であり、レスポンス重視ではない。逆に多段のパイプラインのせいでレスポンスは遅れてしまう。また、非力なマシーンではSEDAの効果を得られず、スレッドを切り替える等の時間もオーバーヘッドになってしまう。
+
+{\bf Data Segmentの再構成 } 
+取得されたData Segmentに変更を行いKey Value Storeへ追加する際に、Output Data Segmentが毎回新しく作成される。そして、変更された値のコピーが行われる。
+このコピーに時間がかかっているのではないかと推測される。この無駄なコピーを無くすことで速度改善ができるのではないかと思われる。
\ No newline at end of file
--- a/sigos.tex	Fri Mar 29 03:53:26 2013 +0900
+++ b/sigos.tex	Sun Mar 31 16:35:18 2013 +0900
@@ -53,11 +53,11 @@
 % 本文はここから始まる
 
 \input{introduction}   % 研究目的
-%\input{d_add}           % d_add
-%\input{model}           % model
-%\input{implmodel}       % implemente Web application
-%\input{compare}
-%\input{conclusion}     % まとめ
+\input{alice}           % Aliceについて
+\input{problem}           % 問題点
+\input{improvement}           % 改善案
+\input{compare} 
+\input{conclusion}     % まとめ
 
 \nocite{kono}
 \nocite{libspe2}
@@ -66,5 +66,4 @@
 
 \input{bibliography}   % 参考文献
 
-
 \end{document}