# HG changeset patch # User sugi # Date 1364809481 -32400 # Node ID 7482647c66ec40bda4b3f378041830a87a448546 # Parent ddd5a624bb7a0a128219ccb800c851f5c797f120 minor change diff -r ddd5a624bb7a -r 7482647c66ec compare.tex --- a/compare.tex Mon Apr 01 01:52:11 2013 +0900 +++ b/compare.tex Mon Apr 01 18:44:41 2013 +0900 @@ -1,13 +1,90 @@ \section{実験} -\subsection{実験概要1} -SEDAの比較 -\subsection{実験概要2} -flipとputの比較 -\subsection{実験概要3} -bitonic sortの実験 \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{実験1} +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の結果} +\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倍差が見られた。 -\subsection{考察} \ No newline at end of file +\begin{table}[htbp] +\caption{実験2の結果} +\label{tb:result1} +\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を使う方が若干ではあるが速度改善が見られる。 + +\begin{table}[htbp] +\caption{実験3の結果} +\label{tb:result1} +\begin{center} +\begin{tabular}{|l|l|l|} +\hline + & 改善前 & 改善後 \\ + \hline + 実行時間 (ms)& 199.38 & 184.64 \\ +\hline +\end{tabular} +\end{center} +\end{table} + +\subsection{考察} +実験の結果より今回の改善により、約10\%程Aliceの速度改善を行うことができた。この差のほとんどがSEDAから来ていると推測される。 +LinkedBlockingQueueを使ったSEDAの実装は、コストが高くレスポンスを求めるには不向きであることがわかった。 \ No newline at end of file diff -r ddd5a624bb7a -r 7482647c66ec conclusion.tex --- a/conclusion.tex Mon Apr 01 01:52:11 2013 +0900 +++ b/conclusion.tex Mon Apr 01 18:44:41 2013 +0900 @@ -1,1 +1,7 @@ -\section{まとめ} \ No newline at end of file +\section{まとめ} +今回の改善はAliceのLocalにおける並列処理の速度を向上させるためのものであった。その結果約10％程処理速を改善することができた。 +しかし、まだまだ十分な速度であるとは言いがたい。別の実験からCode Segment生成からの実行されるまでに、オーバーヘッドがあるとの実験結果が出ている。 +Code Segment側のオーバーヘッドを取り除くことで、更なる速度改善が見込まれる。 +LocalにおいてはSEDAは使用しないが、RemoteにData Segmentの更新する際にはまだSEDAを使用している。今回の実験によりRemoteにおいてもSEDAを使用しないことでレスポンスの向上が見込まれるので、実験を行い確認したい。Remoteの処理速度としては少なくともシングルスレッドのFederated Lindaと同等の速度を目指している。 + +また、Aliceが抱える問題はAPIのシンタックス的な問題や拡張性の問題、永続性の問題などが現在判明している。これらの問題を解決し、Aliceが信頼性とスケーラビリティーを持つように改良を行なっていく必要がある。 \ No newline at end of file diff -r ddd5a624bb7a -r 7482647c66ec improvement.tex --- a/improvement.tex Mon Apr 01 01:52:11 2013 +0900 +++ b/improvement.tex Mon Apr 01 18:44:41 2013 +0900 @@ -8,23 +8,20 @@ Value というクラスは動的に型付けされたオブジェクトを表現することができるため、RubyやPythonのような動的型付けの言語のオブジェクトと同様の扱いをすることができる。 分散プログラムのアプリケーションはサーバとクライアントのVersionが同じとは限らない。サーバ側が更新され、扱うData Segmentが変更された場合であっても、旧Versionとの互換性が要求される。 Aliceは、この問題をMessage PackのValue型を用いることで互換性をもたせようとしている。 -しかし、Versionの問題が起こらないLocalの場合、Data SegmentをValue型に変換し、また任意の型に戻すという操作を行う必要はなく、この操作はは単なるオーバーヘッドにしかならない。 +しかし、Versionの問題が起こらないLocalの場合、Data SegmentをValue型に変換し、また任意の型に戻すという操作を行う必要はなく、この操作は単なるオーバーヘッドにしかならない。 -以上のことからData Segmentの送信先がRemoteの場合に限りValue型に変換を行われるように設計をすれば良い。内部ではObject型として保存する。この場合、Code Segment内でData Segmentを処理をする際にキャストを行う必要があるが、asClassメソッドでキャストを行うようにすることで、RemoteとLocalの記述を同じにすることができる。 -そのため、プログラマーはData Segmentとして送られてくるオブジェクトの型を気にすることなくプログラムを記述できる。 +従って、Data Segmentの送信先がRemoteであるならばValue型に変換を行い、Localであるならば変換しないという具合に改善をすれば、LocalにおけるMessage Packのオーバーヘッドを減らすことができる。 + \subsection{SEDA Archtecture } -Localにおいてはput や peek に沿ったCommand を作成するステージ(Code Segmentが実行されているスレッド)、受け取ったCommandを処理するステージ、Code SegmentにData Segmentをセットするステージの三段のパイプラインで構成されている。最後のCode SegmentにData Segmentをセットするステージはpeekとtakeの時のみ実行される。 -今回、二段目と三段目を一つにまとめることによってステージを減らすことによりオーバーヘッドを減らす。 - +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である。 +CeriumにおけるflipはInput Data SegmentとOutput Data SegmentをswapさせるAPIである。(ソースコード \ref{fig:flip}) \begin{table}[tb] -\lstinputlisting[label=fig:CodeSegment, caption=Ceriumにおけるflipの例]{source/Cerium_flip.cc} +\lstinputlisting[label=fig:flip, caption=Ceriumにおけるflip]{source/Cerium_flip.cc} \end{table} - -AliceにおいてもCeriumと同様にflipを実装する。 -AliceにおけるflipはInput Data SegmentコピーしてOutput Data Segmentを作成するのではなく、Input Data SegmentそのものをOutput DSMに渡すことでData Segmentの無駄なコピーを防ぐ。 - +{\tt readbuf}がInput Data Segment、{\tt writebuf}がOutput Data Segmentである。 +Output がinput の書き換えならばswapを行い、2つの領域を入れ替えることで無駄なmemcopyを防ぐことができる。 +AliceにおいてもCeriumと同様にflipを実装することで、無駄なデータのコピーを防ぐ。 diff -r ddd5a624bb7a -r 7482647c66ec problem.tex --- a/problem.tex Mon Apr 01 01:52:11 2013 +0900 +++ b/problem.tex Mon Apr 01 18:44:41 2013 +0900 @@ -4,15 +4,16 @@ 特に実行速度の問題では分散環境をテストする例題として作成されたRingの例題(トポロジーを円状に構成し、メッセージが1周する時間を計測する)ではシングルスレッドで実装されているFederated Lindaに実行速度で及ばない。また、並列環境をテストする例題として作成したbitonic sortの例題も期待した結果を得ることができなかった。そこで、実行速度の改善を行うために、オーバーヘッドになっている原因の洗い出しを行った。その結果以下のような原因が見つかっている。 {\bf HashMapの多用　} -AliceではData Segment Managerのマネージャーキーによる探索、Data Segmentのキーによる探索などHashMapを多用している。この検索かかる時間が多少ではあるが、オーバーヘッドになっているものと考えられる。 +AliceではData Segment Managerのマネージャーキーによる探索、Data Segmentのキーによる探索などHashMapを多用している。この探索を行う際に排他制御を行うためかかる時間が多少ではあるが、オーバーヘッドになっていると予想される。 {\bf Message Packの convert / unconvert　} -現在の実装ではputまたはupdateを呼ぶとMessage PackによりValue型へと変換が行われている。また、Code Segment内でValue型から変換元の型への変換が行われる。 +現在の実装ではputまたはupdateを呼ぶとMessage PackによりValue型へと変換が行われている。また、peek,takeで取得したData Segmentに対してCode Segment内でValue型から変換元の型への変換を行う必要がある。 この作業もオーバーヘッドになる。また、配列の要素数が増えると変換に時間が多くかかるので、この作業はできるだけ避けたい。 {\bf SEDA Architecture　} -Federated Lindaに比べて、通信のレスポンスが遅い原因にはSEDA Architectureが挙げられる。SEDA とはマルチコアスレッドを用いて大量の接続を管理し、受け取ったデータを処理ごとに分けられたステージと呼ばれるスレッドに投げ、処理が終わると次のステージにデータを伝搬させて行く処理方式である。しかし、SEDAはスループット重視の実装であり、レスポンス重視ではない。逆に多段のパイプラインのせいでレスポンスは遅れてしまう。また、非力なマシーンではSEDAの効果を得られず、スレッドを切り替える等の時間もオーバーヘッドになってしまう。 +Federated Lindaに比べて、通信のレスポンスが遅い原因にはSEDA Architectureが挙げられる。SEDA とはマルチコアスレッドを用いて大量の接続を管理し、受け取ったデータを処理ごとに分けられたステージと呼ばれるスレッドに投げ、処理が終わると次のステージにデータを伝搬させて行く処理方式である。しかし、SEDAはスループット重視の実装であり、レスポンス重視ではない。逆に多段のパイプラインのせいでレスポンスは遅れてしまう。また、データを次のステージへ伝搬させていく際にLinkedBlockingQueueを使用しているがenqueue時、dequeue時にロックを掛けるのでオーバーヘッドの原因と思われる。LinkedBlockingQueueは片方向の連結リストをベースとしたQueue実装である。enqueue / dequeueの操作時の排他制御にはそれぞれ別々のロックオブジェクトが使用されている。そのため、enqueueとdequeueが重なってもロック解除待ちは発生しないが、そのかわりに連結リストのNodeオブジェクトの生成操作などが発生してしまうため、enqueue操作の処理コストが高い。 +さらに、非力なマシーンではSEDAの効果を得られず、スレッドを切り替えが頻繁に起こりオーバーヘッドになってしまう。 {\bf Data Segmentの再構成　} 取得されたData Segmentに変更を行いKey Value Storeへ追加する際に、Output Data Segmentが毎回新しく作成される。そして、変更された値のコピーが行われる。 diff -r ddd5a624bb7a -r 7482647c66ec sigos.tex --- a/sigos.tex Mon Apr 01 01:52:11 2013 +0900 +++ b/sigos.tex Mon Apr 01 18:44:41 2013 +0900 @@ -46,7 +46,8 @@ % 英文概要 \begin{eabstract} -Alice is an distributed programming frame Alice, which uses Data Segment and Code Segment as programming units. We checked that Alice has an ability to write distributed program. +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. \end{eabstract} % 表題などの出力 \maketitle