Mercurial > hg > Papers > 2013 > sugi-sigos

--- a/alice.tex	Thu Apr 25 04:31:15 2013 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,158 +0,0 @@
-\section{分散ネットフレームワークAlice}
-Alice\cite{kono11g}は、本研究室で開発を行なっている分散管理フレームワークである。Cell用の並列フレームワークCerium\cite{kono09b} \cite{cerium-sourceforge}に似たタスク管理機構を持つ。Data Semgnetの通信ではLinda\cite{linda} を相互接続した分散フレームワークであるFederated Linda\cite{kono05b}\cite{kono10d}に似た構造をもつ。
-
-まず、Aliceを使用するに必要なData Segment、Code Segmentについて説明を行う。
-\subsection{Data Segment API}
-Data Segmentは数値や文字列などのデータを構造体的に保持する。AliceはData Segmentをデータベース的に扱う。しかし、Aliceは通常のデータベースとは異なりKey毎にキューがある。キューにData Segmentをput した順番に取得することができる。これはLindaに準じた設計となっている。
-
-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.0}{\includegraphics{images/remote_datasegment.pdf}}
-\end{center}
-\caption{Remote DSMは他のノードの Local DSMのproxy}
-\label{fig:proxy}
-\end{figure}
-以下が用意されている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+ はデータを追加するための API である。Key Value Storeのキューに追加される。 (図 \ref{fig:put})
-
-\begin{figure}[htbl]
-\begin{center}
-\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}[htbl]
-\begin{center}
-\scalebox{1.1}{\includegraphics{images/update.pdf}}
-\end{center}
-\caption{updateはキューの先頭を書き換える}
-\label{fig:update}
-\end{figure}
-
-\subsubsection{peek}
-peek はデータを取得する。(図 \ref{fig:peek})
-\begin{figure}[html]
-\begin{center}
-\scalebox{1.0}{\includegraphics{images/peek.pdf}}
-\end{center}
-\caption{peekはデータを取得する}
-\label{fig:peek}
-\end{figure}
-
-
-Data Segmentが無ければCode Segmentの待ち合わせが起きる。(図 \ref{fig:no_peek})
-
-\begin{figure}[htbl]
-\begin{center}
-\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}[htbl]
-\begin{center}
-\scalebox{1.1}{\includegraphics{images/take.pdf}}
-\end{center}
-\caption{take はデータを読み込む}
-\label{fig:take}
-\end{figure}
-
-\subsection{Code Segment}
-
-Code Segmentはタスクのことである。Code Segmentをユーザーが記述するときにCode Segment内で使用するData Segmentの作成を記述する。Code SegmentにはInput Data SegmentとOutput Data Segmentを作るAPIが存在する。
-
-
-Input Data SegmentはRemoteかLocalを指定する必要がある。さらに、どのData Segmentを取るかをキーで指定する。
-実際にsetKeyのメソッドを呼んだ時に指定する。
-Code Segmentがactiveになるためには、Input Data Segmentが全て揃う必要がある。
-
-
-Output Data SegmentもRemoteかLocalを指定する。Input と同様にどのキーに対してData Segmentを追加するか指定する。
-実際にはputまたはupdateメソッドを呼ぶタイミングでおこなう。
-
-これらのInput/OutputがCode Segment間の依存関係を自動的に記述することになる。
-
-\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}[html]
-\lstinputlisting[label=fig:TestLocalAlice, caption=Start Code Segmentを実行させる方法]{source/TestLocalAlice.java}
-\end{table}
-
-\subsubsection{Code Segmentの記述方法}
-Code Segmentをユーザーが記述する際にはCode Segmentを継承して記述する。(ソースコード \ref{fig:CodeSegment})そのCodeSegmentはInputDataSegmentManagerとOutputDataSegmentManagerを利用することができる。
-
-InputDataSegmentManagerはCode Segmentの{\tt ids}というフィールドを用いてアクセスする。
-
-
-
-\begin{table}[html]
-\lstinputlisting[label=fig:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java}
-\end{table}
-
-\begin{itemize}
-\item {\ttfamily Receiver create(CommandType type)}
-\end{itemize}
-createでコマンドが実行された際に取得されるData Segmentが格納される受け皿を作る。引数にはCommandTypeが取られ、指定できるCommandTypeは{\tt PEEK}または{\tt TAKE}である。
-\begin{itemize}
-\item {\ttfamily void setKey(String managerKey, String key)}
-\end{itemize}
-setKeyメソッドにより、どこのData Segmentのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定することができる。
-コマンドの結果がレスポンスとして届き次第Code Segmentは実行される。
-
-OutputDataSegmentManagerはCode Segmentの{\tt ods}というフィールドを用いてアクセスする。
-OutPutDataSegmentManagerは{\tt put}または{\tt update}を実行することができる。
-\begin{itemize}
-\item {\ttfamily void put(String managerKey, String key, \\ Value val)}
-\item {\ttfamily void update(String managerKey, String key, Value val)}
-\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
--- a/bibliography.tex	Thu Apr 25 04:31:15 2013 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,39 +0,0 @@
-
-\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.
-
-\bibitem{kono13h}
-{多賀野海人, 小林佑亮, 宮國渡, 河野真治 (琉球大).} Code Segment と Data Segment によるプログラミング手法. 情報処理学会プログラミング・シンポジウム, January 2013.
-\end{thebibliography}
--- a/compare.tex	Thu Apr 25 04:31:15 2013 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,88 +0,0 @@
-\section{実験}
-
-\subsection{実験環境}
-SEDAがコア数の少ないマシーンではうまく動作しないことを考慮して、メニコア環境で実験を行った。
-
-
-\begin{table}[htbp]
-\caption{実行環境の詳細}
-\label{tb:MacPro}
-\begin{center}
-\begin{tabular} {|l|l|}
-  \hline
-  {\bf CPU}&Intel(R) Xeon(R) X5650 @2.67GHz\\
-  \hline
-  {\bf 物理コア数}&12\\
-  \hline
-  {\bf 論理コア数}&24\\
-  \hline
-  {\bf CPU キャッシュ}&12MB\\
-  \hline
-  {\bf Memory}&16GB\\
-  \hline
-\end{tabular}
-\end{center}
-\end{table}
-
-
-\subsection{実験概要}
-今回それぞれの改善案の効果を調査するために以下の3つの実験を行った。
-\subsubsection{SEDAの有無}
-LocalからData Segmentを取得するCode Segmentを10000回実行される時間を計測する。
-SEDAを使用した場合と、しない場合の2つの比較を行い、その効果を測定する。
-
-\begin{table}[html]
-\caption{SEDAの有無の比較}
-\label{tb:result1}
-\begin{center}
-\begin{tabular}{|l|l|l|}
-\hline
- SEDA& あり & なし \\
- \hline
- 実行時間 (ms)& 27.72 & 7.53 \\
-\hline
-\end{tabular}
-\end{center}
-\end{table}
-SEDAを使わずにコマンドを処理する方が約3.7倍差が見られた。(表\ref{tb:result1})
-\subsubsection{flipの効果の測定}
-Local にData Segmentを10000回追加するのにかかる時間を計測する。
-flipコマンドを使用して追加する場合と、putコマンドを使用して追加する場合の2つの比較を行う。
-
-\begin{table}[html]
-\caption{flipの結果}
-\label{tb:result2}
-\begin{center}
-\begin{tabular}{|l|l|l|}
-\hline
-Command & flip & put \\
- \hline
- 実行時間 (ms)& 61.12 & 65.24 \\
-\hline
-\end{tabular}
-\end{center}
-\end{table}
-
-flipを使う方が若干ではあるが速度改善が見られる。(表\ref{tb:result2})
-
-\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
- & 改善前 & 改善後 \\
- \hline
- 実行時間 (ms)& 199.38 & 184.64 \\
-\hline
-\end{tabular}
-\end{center}
-\end{table}
-
-
-\subsection{考察}
-実験の結果より今回の改善により、約10\%程Aliceの速度改善を行うことができた。(表\ref{tb:result3})この差のほとんどがSEDAによるものと推測される。
-LinkedBlockingQueueを使ったSEDAの実装は、コストが高くレスポンスを求めるには不向きであることがわかった。
\ No newline at end of file
--- a/improvement.tex	Thu Apr 25 04:31:15 2013 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,33 +0,0 @@
-\section{改善案}
-\subsection{Message Pack}
-AliceではData SegmentをValue型という、Message Packが提供している型で保存している。
-Value というクラスは動的に型付けされたオブジェクトを表現することができるため、RubyやPythonのような動的型付けの言語のオブジェクトと同様の扱いをすることができる。
-分散プログラムのアプリケーションはサーバとクライアントのVersionが同じとは限らない。サーバ側が更新され、扱うData Segmentが変更された場合であっても、旧Versionとの互換性が要求される。
-Aliceは、この問題をMessage PackのValue型を用いることで互換性をもたせようとしている。
-しかし、Versionの問題が起こらないLocalの場合、Data SegmentをValue型に変換し、また任意の型に戻すという操作を行う必要はなく、この操作は単なるオーバーヘッドにしかならない。
-
-従って、Data Segmentの送信先がRemoteであるならばValue型に変換を行い、Localであるならば変換しないという具合に改善をすれば、LocalにおけるMessage Packのオーバーヘッドを減らすことができる。
-
-
-\subsection{SEDA Architecture }
-Localにおいてはput や peek に沿ったCommand を作成するステージ(Code Segmentが実行されているスレッド)、受け取ったCommandを処理するステージ、Code SegmentにData Segmentをセットするステージの三段のパイプラインで構成されている。これを全て同一のステージにまとめ、Localの環境下においてSEDAを使用せずに処理を行うように変更する。
-\subsection{Data Segmentの再構成}
-Data Segmentの更新におけるオーバーヘッドを減らす方法としてCeriumでも良好な結果を得ているflipを提案する。
-CeriumにおけるflipはInput Data SegmentとOutput Data SegmentをswapさせるAPIである。(ソースコード \ref{fig:flip})
-
-\begin{table}[html]
-\lstinputlisting[label=fig:flip, caption=Ceriumにおけるflip]{source/Cerium_flip.cc}
-\end{table}
-{\tt readbuf}がInput Data Segment、{\tt writebuf}がOutput Data Segmentである。
-Output がinput の書き換えならばswapを行い、2つの領域を入れ替えることで無駄なmemcopyを防ぐことができる。
-
-
-AliceにおいてもCeriumと同様にflipを実装することで、無駄なデータのコピーを防ぐ。(ソースコード\ref{fig:flipAlice})
-\begin{table}[html]
-\lstinputlisting[label=fig:flipAlice, caption=Aliceにおけるflip]{source/OutputDataSegment.java}
-\lstinputlisting[label=fig:use,caption=flipの使用例]{source/Sort.java}
-\end{table}
-
-CeriumにおいてOutput Data SegmentはTaskが実行された段階ですでに用意されているため、flipしてから書き込む。
-しかし、Aliceではputまたはupdateを呼んだ段階で作られるため、ソースコード\ref{fig:use}のようにInput Data SegmentであるReceiverをflipメソッドに引数として渡すことで、
-無駄なコピーを減らす
--- a/introduction.tex	Thu Apr 25 04:31:15 2013 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,7 +0,0 @@
-\section{研究背景と目的}
-本研究室では、データをData Segment、タスクをCode Segmentという単位に分割して記述する分散ネットフレームワークAliceの開発を行なっている。Aliceはノード間のData Segmentの送受信APIが提供されている。メニーコアのマシンが主流になっている背景からSEDA Architectureを採用しており、マルチコア上でのスループットの向上を期待している。
-
-
-以前、Aliceが分散フレームワークとしての記述能力を確認するために、水族館の例題\cite{kono13h}の作成を行った。その結果より、Aliceには分散プログラムを記述するのに必要なAPIが備わっていることが確認できている。また、並列環境に対応していることを確認するため、bitonic sortを作成した。しかし、Data Segmentの更新のオーバーヘッドにより、期待した効果を得られなかった。
-
-本研究ではData Segmentの更新オーバーヘッドを解決する手段として新しくAPIを提案し、効果の測定を行う。
\ No newline at end of file
--- a/presen/index.html	Thu Apr 25 04:31:15 2013 +0900
+++ b/presen/index.html	Thu Apr 25 13:10:43 2013 +0900
@@ -108,6 +108,25 @@

   <slide>
     <hgroup>
+      <h2>並列性能の例題 - Bitonic Sort</h2>
+    </hgroup>
+    <article>
+      <ul>
+	<table>
+	  <tr width="100%">
+	  <td width="60%"><Div Align="center"><image src="images/bitonicsort.png" width="100%"></Div></td><td width="40%"><ul>
+		<li>配列を分割してSortする</li>
+		<li>Sortされた配列をさらに分割する</li>
+		<li>分割された配列の下半分と上半分に対してSortする</li>
+	  </ul></td>
+	  </tr>
+	</table>
+      </ul>
+    </article>
+  </slide>
+
+  <slide>
+    <hgroup>
       <h2>実行速度の問題</h2>
     </hgroup>
     <article>
@@ -144,7 +163,7 @@
       <ul>
       <code><pre>
 while(ture){
-　Command cmd = linkedBlockingQueue.take()
+  Command cmd = linkedBlockingQueue.take();
   Command result = runCommand(cmd);
   nextLinkedBlockingQueue.put(result);
 }
@@ -228,31 +247,13 @@

   <slide>
     <hgroup>
-      <h2>実験概要</h2>
+      <h2>実験1の概要と結果</h2>
     </hgroup>
     <article>
-      <p>今回行った改善による効果を調べるために3つの実験を行った。<br>
-      実験はSEDAの効果が出るようにメニコアのマシンで行った</p>
       <ul>
 	<li>SEDAの有無</li>
 	<p>Data Segmentを取得するCode Segmentが10000回実行されるまでの時間を測定</p>
-	<li>flipとputの比較</li>
-	<p>既存のAPIの<em>put</em>と新しく追加したAPIである<em>flip</em>を使用して10000回、Data Segmentを追加されるまでの時間を測定</p>
-	<li>Bitonic Sortによる比較</li>
-	<p>今回行った改善でBitonic Sortがどの程度速度が改善されたか測定する。<br>
-	  要素は100万個、10個に分割して実験した</p>
-      </ul>
-    </article>
-  </slide>

-
-  <slide>
-    <hgroup>
-      <h2>実験結果</h2>
-    </hgroup>
-    <article>
-      <p>実験結果は100回行った平均</p>
-      <ul>
       <table>
         <tr width="100%">
           <th width="50%">SEDA</th><th width="25%">あり</th><th width="25%">なし</th>
@@ -261,8 +262,20 @@
           <td>実行時間(ms)</td><td>27.72</td><td>7.53</td>
         </tr>
       </table>
+      <p>SEDAが無いほうが約4倍程度早い</p>
       </ul>
+    </article>
+  </slide>
+
+  <slide>
+    <hgroup>
+      <h2>実験2の概要と結果</h2>
+    </hgroup>
+    <article>
       <ul>
+	<li>flipとputの比較</li>
+	<p>既存のAPIのputと新しいAPIであるflipを使用して、
+	  Data Segmentが10000回追加されるまでの時間を測定</p>
       <table>
         <tr width="100%">
           <th width="50%">API</th><th width="25%">flip</th><th width="25%">put</th>
@@ -271,8 +284,20 @@
           <td>実行時間(ms)</td><td>61.12</td><td>65.24</td>
         </tr>
       </table>
+      <p>flipを使用するほうが7％改善された</p>
       </ul>
+    </article>
+  </slide>
+
+  <slide>
+    <hgroup>
+      <h2>実験3の概要と結果</h2>
+    </hgroup>
+    <article>
       <ul>
+	<li>Bitonic Sortによる比較</li>
+	<p>今回行った改善でBitonic Sortがどの程度速度が改善されたか測定する。<br>
+	  要素は100万個、10個に分割して実験した</p>
       <table>
         <tr width="100%">
           <th width="50%"></th><th width="25%">改善前</th><th width="25%">改善後</th>
@@ -281,19 +306,32 @@
           <td>実行時間(ms)</td><td>199.38</td><td>184.64</td>
         </tr>
       </table>
-      Bitonic Sortの例題では約10％程度改善された
+      <p>Bitonic sortの例題でも約10％程、改善された</p>
       </ul>
     </article>
   </slide>

   <slide>
     <hgroup>
-      <h2>まとめ</h2>
+      <h2>実験の考察考察</h2>
+    </hgroup>
+    <article>
+      <ul>
+	<li>SEDAの有無で4倍速度に差が出ている。これが示すのはSEDAの実装に問題がある。</li>
+	<li>レスポンスを要求するものに対してはSEDA無し、そうでないものに対してはSEDAで処理させる</li>
+
+	<li>flipにおいても十分効果があった。ただし、ユーザーにflipの判断をさせるのではなく、Alice側で自動的に判断するのが望ましい</li>
+      </ul>
+    </article>
+  </slide>
+
+  <slide>
+    <hgroup>
+      <h2>将来の課題</h2>
     </hgroup>
     <article>
       <ul>
 	<li>今回行った改善により、<FONT color="red">最大4倍程度速度を期待することが出来る</FONT></li>
-	<li>Aliceに要求される速度は、少なくともシングルスレッドで書かれたプログラムと同じ程度</li>
 	<li>分散環境下ではFederated Lindaと同じ速度を目標としている</li>
 	<li>今回の実験からSEDAに問題があることが明らかになったのでRemoteにおいてもSEDAの使用を選択できるようにする</li>
 	<li>また、Aliceが抱える問題は速度だけではない</li>