# HG changeset patch # User sugi # Date 1364818662 -32400 # Node ID 715578f7608479d5f15267c5b2124d9d4a99067a # Parent 7482647c66ec40bda4b3f378041830a87a448546 fixed diff -r 7482647c66ec -r 715578f76084 alice.tex --- a/alice.tex Mon Apr 01 18:44:41 2013 +0900 +++ b/alice.tex Mon Apr 01 21:17:42 2013 +0900 @@ -1,15 +1,14 @@ \section{分散ネットフレームワークAlice} -Aliceは、本研究室で開発を行なっている分散管理フレームワークである。Cell用ののOpen CLに似たTask管理フレームワークCerium\cite{kono09b} \cite{cerium-sourceforge}とLinda\cite{linda} を相互接続した分散フレームワークであるFederated Lindaの開発を通して得られた知見が生かされている。 +Aliceは、本研究室で開発を行なっている分散管理フレームワークである。Cell用の並列フレームワークCerium\cite{kono09b} \cite{cerium-sourceforge}に似たタスク管理機構を持つ。Data Semgnetの通信ではLinda\cite{linda} を相互接続した分散フレームワークであるFedaradeLinda に似た構造をもつ。 まず、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は数値や文字列などのデータ構造体的に保持する。AliceはData Segmentをデータベース的に扱う。しかし、Data Base的に扱うがAliceではData Baseとは異なりKey毎にキューがある。キューにData Segmentをput した順番に取得することができる。これはLindaに準じた設計となっている。 -Data Segmentを管理するのがData Segment Manager(以下DSM)である。ノード毎にLocal DSMとRemote DSMが存在する。Local DSMはノード固有のKey Value Storeと考えることができる。Remote DSMは他のノードのLocal DSMのproxyである。(図 \ref{fig:proxy})AliceのトポロジーマネージャーがRemote DSMを自動的に構成する。 -Key Value Storeへのアクセスはキューによって、ノード内部で逐次化される。それ以外は、すべてJavaのThread poolにより並列実行される。 +Data Segmentを管理するのがData Segment Manager(以下DSM)である。ノード毎にキーを持ち他のノードにはRemote DSM経由でアクセスすることができる。つまり、Remote DSMは他のノードのLocal DSMのproxyである。(図 \ref{fig:proxy})他のノードに対するアクセスはキューによって、ノード内部で逐次化される。それ以外は、すべてJavaのThread poolにより並列実行される。 \begin{figure}[tb] \begin{center} -\scalebox{1.2}{\includegraphics{images/remote_datasegment.pdf}} +\scalebox{1.0}{\includegraphics{images/remote_datasegment.pdf}} \end{center} \caption{Remote DSMは他のノードの Local DSMのproxy} \label{fig:proxy} @@ -21,81 +20,65 @@ \item \verb+void peek(Receiver receiver, String key)+ \item \verb+void take(Receiver receiver, String key)+ \end{itemize} + \subsubsection{put} \verb+put+ はデータを追加するための API である。Key Value Storeのキューに追加される。 (図 \ref{fig:put}) -\begin{figure}[tb] +\begin{figure}[htbl] \begin{center} -\scalebox{1.2}{\includegraphics{images/put.pdf}} +\scalebox{1.1}{\includegraphics{images/put.pdf}} \end{center} \caption{putはデータを追加する} \label{fig:put} \end{figure} + \subsubsection{update} \verb+update+ はデータを更新するためのAPIである。キューの先頭を置き換える。 (図 \ref{fig:update}) -\begin{figure}[tb] +\begin{figure}[htbl] \begin{center} -\scalebox{1.2}{\includegraphics{images/update.pdf}} +\scalebox{1.1}{\includegraphics{images/update.pdf}} \end{center} \caption{updateはキューの先頭を書き換える} \label{fig:update} \end{figure} \subsubsection{peek} -peek はデータを取得する。(図 \ref{fig:peek})Data Segmentが無ければCode Segmentの待ち合わせが起きる。(図 \ref{fig:no_peek}) -put、updateによりData Segmentの更新があれば、peekが直ちに実行され、待ち合わせを行なっていたCode Segmentがactive queue に移される。 - -\begin{figure}[tb] +peek はデータを取得する。(図 \ref{fig:peek}) +\begin{figure}[html] \begin{center} -\scalebox{1.2}{\includegraphics{images/peek.pdf}} +\scalebox{1.0}{\includegraphics{images/peek.pdf}} \end{center} \caption{peekはデータを取得する} \label{fig:peek} \end{figure} -\begin{figure}[tb] + +Data Segmentが無ければCode Segmentの待ち合わせが起きる。(図 \ref{fig:no_peek}) + +\begin{figure}[htbl] \begin{center} -\scalebox{1.2}{\includegraphics{images/peek1.pdf}} +\scalebox{1.1}{\includegraphics{images/peek1.pdf}} \end{center} \caption{希望のデータが無いときは保留する} \label{fig:no_peek} \end{figure} +put、updateによりData Segmentの更新があれば、peekが直ちに実行され、待ち合わせを行なっていたCode Segmentがactive queue に移される。 + \subsubsection{take} takeもデータを取得するためのAPIである。(図 \ref{fig:take})peekとの違いは取得されたData SegmentはKey Value Storeのキューから取り除かれる。 -\begin{figure}[tp] +\begin{figure}[htbl] \begin{center} -\scalebox{1.2}{\includegraphics{images/take.pdf}} +\scalebox{1.1}{\includegraphics{images/take.pdf}} \end{center} \caption{take はデータを読み込む} \label{fig:take} \end{figure} -\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で扱うことのできるデータのみをフィールドに入れなければならない。 - -\begin{table}[htbp] -\lstinputlisting[label=fig:MessagePackTest, caption=一般的なクラスをIDLのように使用]{source/MessagePackTest.java} -\end{table} - \subsection{Code Segment} Code Segmentはタスクのことである。Code Segmentをユーザーが記述するときにCode Segment内で使用するData Segmentの作成を記述する。Code SegmentにはInput Data SegmentとOutput Data Segmentを作るAPIが存在する。 @@ -113,10 +96,14 @@ \subsubsection{Code Segmentの実行方法} Alice には、Start Code Segment (ソースコード \ref{fig:StartCodeSegment})というC の main に相当するような最初に実行される Code Segment がある。 +\begin{table}[html] +\lstinputlisting[label=fig:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java} +\end{table} + Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。 このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。(ソースコード \ref{fig:TestLocalAlice}) -\begin{table}[tb] +\begin{table}[html] \lstinputlisting[label=fig:TestLocalAlice, caption=Start Code Segmentを実行させる方法]{source/TestLocalAlice.java} \end{table} @@ -125,11 +112,9 @@ InputDataSegmentManagerはCode Segmentの{\tt ids}というフィールドを用いてアクセスする。 -\begin{table}[tb] -\lstinputlisting[label=fig:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java} -\end{table} + -\begin{table}[tb] +\begin{table}[html] \lstinputlisting[label=fig:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java} \end{table} @@ -148,4 +133,26 @@ \begin{itemize} \item {\ttfamily void put(String managerKey, String key, \\ Value val)} \item {\ttfamily void update(String managerKey, String key, Value val)} -\end{itemize} \ No newline at end of file +\end{itemize} + + + +\section{Message Pack } +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で扱うことのできるデータのみをフィールドに入れなければならない。 \ No newline at end of file diff -r 7482647c66ec -r 715578f76084 bibliography.tex --- a/bibliography.tex Mon Apr 01 18:44:41 2013 +0900 +++ b/bibliography.tex Mon Apr 01 21:17:42 2013 +0900 @@ -32,6 +32,8 @@ \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. +{多賀野海人, 小林佑亮, 宮國渡, 河野真治 (琉球大).} Cell Task Manager Cerium の SPU 内データ管理. 情報処理学会システムソフトウェアとオ ペレーティング・システム研究会, April 2009. +\bibitem{kono13h} +{多賀野海人, 小林佑亮, 宮國渡, 河野真治 (琉球大).} Code Segment と Data Segment によるプログラミング手法. 情報処理学会プログラミング・シンポジウム, January 2013. \end{thebibliography} diff -r 7482647c66ec -r 715578f76084 compare.tex --- a/compare.tex Mon Apr 01 18:44:41 2013 +0900 +++ b/compare.tex Mon Apr 01 21:17:42 2013 +0900 @@ -1,7 +1,8 @@ \section{実験} \subsection{実験環境} -今回はSEDAが非力なマシーンでは動作しないことを考慮して、メニコア環境で実験を行った。 +SEDAがコア数の少ないマシーンではうまく動作しないことを考慮して、メニコア環境で実験を行った。 + \begin{table}[htbp] \caption{実行環境の詳細} @@ -26,22 +27,12 @@ \subsection{実験概要} 今回それぞれの改善案の効果を調査するために以下の3つの実験を行った。 -\subsubsection{実験1} +\subsubsection{SEDAの有無} LocalからData Segmentを取得するCode Segmentを10000回実行される時間を計測する。 SEDAを使用した場合と、しない場合の2つの比較を行い、その効果を測定する。 -\subsubsection{実験2} -Local にData Segmentを10000回追加するのにかかる時間を計測する。 -flipコマンドを使用して追加する場合と、putコマンドを使用して追加する場合の2つの比較を行う。 - -\subsubsection{実験3} -bitonic sortにより、100万の要素をもつ配列のSortにかかる時間を計測する。分割数は10個で行った。 -今回改善を行う前と後を比較し今回のどの程度、速度改善が行われたかを調べる。 - - -\subsection{実験結果} -\begin{table}[htbp] -\caption{実験1の結果} +\begin{table}[html] +\caption{SEDAの有無の比較} \label{tb:result1} \begin{center} \begin{tabular}{|l|l|l|} @@ -53,11 +44,14 @@ \end{tabular} \end{center} \end{table} -SEDAを使わずにコマンドを処理する方が約3.7倍差が見られた。 +SEDAを使わずにコマンドを処理する方が約3.7倍差が見られた。(表\ref{tb:result1}) +\subsubsection{flipの効果の測定} +Local にData Segmentを10000回追加するのにかかる時間を計測する。 +flipコマンドを使用して追加する場合と、putコマンドを使用して追加する場合の2つの比較を行う。 -\begin{table}[htbp] -\caption{実験2の結果} -\label{tb:result1} +\begin{table}[html] +\caption{flipの結果} +\label{tb:result2} \begin{center} \begin{tabular}{|l|l|l|} \hline @@ -69,11 +63,14 @@ \end{center} \end{table} -flipを使う方が若干ではあるが速度改善が見られる。 +flipを使う方が若干ではあるが速度改善が見られる。(表\ref{tb:result2}) -\begin{table}[htbp] -\caption{実験3の結果} -\label{tb:result1} +\subsubsection{bitonic sortにおける効果の測定} +bitonic sortにより、100万の要素をもつ配列のSortにかかる時間を計測する。分割数は10個で行った。 + +\begin{table}[html] +\caption{bitonic sortの結果} +\label{tb:result3} \begin{center} \begin{tabular}{|l|l|l|} \hline @@ -85,6 +82,7 @@ \end{center} \end{table} + \subsection{考察} -実験の結果より今回の改善により、約10\%程Aliceの速度改善を行うことができた。この差のほとんどがSEDAから来ていると推測される。 +実験の結果より今回の改善により、約10\%程Aliceの速度改善を行うことができた。(表\ref{tb:result3})この差のほとんどがSEDAによるものと推測される。 LinkedBlockingQueueを使ったSEDAの実装は、コストが高くレスポンスを求めるには不向きであることがわかった。 \ No newline at end of file diff -r 7482647c66ec -r 715578f76084 improvement.tex --- a/improvement.tex Mon Apr 01 18:44:41 2013 +0900 +++ b/improvement.tex Mon Apr 01 21:17:42 2013 +0900 @@ -1,7 +1,5 @@ \section{改善案} -\subsection{HashMap} -HashMapによる探索を排除することは複数のRemote DSMがあるので難しい。しかし、Localに対してはDSMが固有であるので、マネージャーキーによる探索は必要ない。 -従ってLocal 専用の Data Segment APIを提供することによりHashMapによる探索の回数を減らすことができる。 + \subsection{Message Pack} AliceではData SegmentをValue型という、Message Packが提供している型で保存している。 diff -r 7482647c66ec -r 715578f76084 introduction.tex --- a/introduction.tex Mon Apr 01 18:44:41 2013 +0900 +++ b/introduction.tex Mon Apr 01 21:17:42 2013 +0900 @@ -1,9 +1,7 @@ \section{研究背景と目的} -インターネット上のサービスには信頼性とスケーラビリティの両方が要求される。信頼性とは、定められた環境動作下でユーザーが記述した通りの処理を行うことをさす。また、スケーラビリティは、サービスに参加するクライアントの数が増加しても、メモリ等のリソースのみでサービスを維持することをさす。 - -本研究室では、データをData Segment、タスクをCode Segmentという単位に分割して記述する分散ネットフレームワークAliceの開発を行なっている。Aliceはノード間のData Segmentの送受信APIが提供されている。また、Blade,PCクラスタ上で分散プログラムのシュミレーションをするために、オーバレイネットワークを自動的に構成するTopologyManagerという機能が搭載されている。さらにメニーコアのマシンが主流になっている背景からSEDA Archtectureを採用しており、マルチコア上でのスループットの向上を期待している。 +本研究室では、データをData Segment、タスクをCode Segmentという単位に分割して記述する分散ネットフレームワークAliceの開発を行なっている。Aliceはノード間のData Segmentの送受信APIが提供されている。メニーコアのマシンが主流になっている背景からSEDA Archtectureを採用しており、マルチコア上でのスループットの向上を期待している。 -以前、Aliceが分散フレームワークとしての記述能力を確認するために、水族館の例題の作成を行った。その結果より、Aliceには分散プログラムを記述するのに必要なAPIが備わっていることが確認できている。また、並列環境に対応していることを確認するため、bitonic sortを作成した。しかし、Data Segmentの更新のオーバーヘッドにより、期待した効果を得られなかった。 +以前、Aliceが分散フレームワークとしての記述能力を確認するために、水族館の例題\cite{kono13h}の作成を行った。その結果より、Aliceには分散プログラムを記述するのに必要なAPIが備わっていることが確認できている。また、並列環境に対応していることを確認するため、bitonic sortを作成した。しかし、Data Segmentの更新のオーバーヘッドにより、期待した効果を得られなかった。 本研究ではData Segmentの更新オーバーヘッドを解決する手段として新しくAPIを提案し、効果の測定を行う。 \ No newline at end of file diff -r 7482647c66ec -r 715578f76084 problem.tex --- a/problem.tex Mon Apr 01 18:44:41 2013 +0900 +++ b/problem.tex Mon Apr 01 21:17:42 2013 +0900 @@ -12,7 +12,7 @@ この作業もオーバーヘッドになる。また、配列の要素数が増えると変換に時間が多くかかるので、この作業はできるだけ避けたい。 {\bf SEDA Architecture　} -Federated Lindaに比べて、通信のレスポンスが遅い原因にはSEDA Architectureが挙げられる。SEDA とはマルチコアスレッドを用いて大量の接続を管理し、受け取ったデータを処理ごとに分けられたステージと呼ばれるスレッドに投げ、処理が終わると次のステージにデータを伝搬させて行く処理方式である。しかし、SEDAはスループット重視の実装であり、レスポンス重視ではない。逆に多段のパイプラインのせいでレスポンスは遅れてしまう。また、データを次のステージへ伝搬させていく際にLinkedBlockingQueueを使用しているがenqueue時、dequeue時にロックを掛けるのでオーバーヘッドの原因と思われる。LinkedBlockingQueueは片方向の連結リストをベースとしたQueue実装である。enqueue / dequeueの操作時の排他制御にはそれぞれ別々のロックオブジェクトが使用されている。そのため、enqueueとdequeueが重なってもロック解除待ちは発生しないが、そのかわりに連結リストのNodeオブジェクトの生成操作などが発生してしまうため、enqueue操作の処理コストが高い。 +Federated Lindaに比べて、通信のレスポンスが遅い原因にはSEDA Architectureが挙げられる。SEDA とはマルチコアスレッドを用いて大量の接続を管理し、受け取ったデータを処理ごとに分けられたステージと呼ばれるスレッドに投げ、処理が終わると次のステージにデータを伝搬させて行く処理方式である。しかし、SEDAはスループット重視の実装であり、レスポンス重視ではない。逆に多段のパイプラインのせいでレスポンスは遅れてしまう。また、データを次のステージへ伝搬させる際にLinkedBlockingQueueを使用しているがenqueue時、dequeue時にロックを掛けるのでオーバーヘッドの原因と思われる。LinkedBlockingQueueは片方向の連結リストをベースとしたQueue実装である。enqueue / dequeueの操作時の排他制御にはそれぞれ別々のロックオブジェクトが使用されている。そのため、enqueueとdequeueが重なってもロック解除待ちは発生しないが、そのかわりに連結リストのNodeオブジェクトの生成操作などが発生してしまうため、enqueue操作の処理コストが高い。 さらに、非力なマシーンではSEDAの効果を得られず、スレッドを切り替えが頻繁に起こりオーバーヘッドになってしまう。 {\bf Data Segmentの再構成　} diff -r 7482647c66ec -r 715578f76084 sigos.tex --- a/sigos.tex Mon Apr 01 18:44:41 2013 +0900 +++ b/sigos.tex Mon Apr 01 21:17:42 2013 +0900 @@ -46,8 +46,8 @@ % 英文概要 \begin{eabstract} -Alice is an distributed programming frame Alice, which uses Data Segment and Code Segment as programming units. We checked Alice has an ability to write distributed program. -On the other hand, to renew Data Segment has a high cost in concurrent processing. So We propose new API 'flip' to solve the problem and research an effect. +Alice is an distributed programming frame work, which uses Data Segment and Code Segment as programming units. We checked Alice has an ability to write distributed program using aquarium example. +In bitonic sort example refined Data Segment update is slow. So We propose a new API ``flip'' to solve the problem and show its variation. \end{eabstract} % 表題などの出力 \maketitle