# HG changeset patch # User Nozomi Teruya # Date 1430919351 -32400 # Node ID a5958e372cee428749b577a1e71fdcc098224793 # Parent 1dd3a4150e7de43156b0f7146e8bacdfd11b270a add souse code diff -r 1dd3a4150e7d -r a5958e372cee paper/sigos.aux --- a/paper/sigos.aux Wed May 06 21:10:08 2015 +0900 +++ b/paper/sigos.aux Wed May 06 22:35:51 2015 +0900 @@ -12,12 +12,10 @@ \@writefile{lol}{\contentsline {lstlisting}{\numberline {4}flipの使用例}{5}} \newlabel{src:ReceiveData}{{5}{5}} \@writefile{lol}{\contentsline {lstlisting}{\numberline {5}データを表現するクラス}{5}} -\newlabel{src:zput}{{6}{5}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {6}圧縮DSのput}{5}} -\newlabel{src:ztake}{{7}{5}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {7}圧縮DSのtake}{5}} -\newlabel{src:asClass}{{8}{5}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {8}asClassの処理}{5}} +\newlabel{src:before}{{6}{5}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {6}通常のDSを扱うCSの例}{5}} +\newlabel{src:after}{{7}{5}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {7}圧縮したDSを扱うCSの例}{5}} \citation{*} \bibstyle{ipsjunsrt} \bibdata{sigos} @@ -26,6 +24,8 @@ \bibcite{Alice3}{3} \bibcite{Alice4}{4} \bibcite{Erlang}{5} +\newlabel{src:asClass}{{8}{6}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {8}asClassの処理}{6}} \newlabel{src:CommandMessage}{{9}{6}} \@writefile{lol}{\contentsline {lstlisting}{\numberline {9}CommandMessage}{6}} \newlabel{tb:variable}{{1}{6}} diff -r 1dd3a4150e7d -r a5958e372cee paper/sigos.dvi Binary file paper/sigos.dvi has changed diff -r 1dd3a4150e7d -r a5958e372cee paper/sigos.log --- a/paper/sigos.log Wed May 06 21:10:08 2015 +0900 +++ b/paper/sigos.log Wed May 06 22:35:51 2015 +0900 @@ -1,4 +1,4 @@ -This is e-pTeX, Version 3.1415926-p3.4-110825-2.6 (utf8.euc) (TeX Live 2013) (format=platex 2014.4.14) 6 MAY 2015 21:09 +This is e-pTeX, Version 3.1415926-p3.4-110825-2.6 (utf8.euc) (TeX Live 2013) (format=platex 2014.4.14) 6 MAY 2015 22:26 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -240,7 +240,7 @@ File: images/treestructure.pdf Graphic file (type pdf) (./source/flip.java) (./source/Sort.java) [4] (./source/ReceiveData.java) -(./source/compress_put.java) (./source/compress_take.java) +(./source/beforeCompress.java) (./source/afterCompress.java) [5] (./source/asClass.java LaTeX Font Info: Try loading font information for OML+cmr on input line 1. @@ -249,20 +249,20 @@ ) LaTeX Font Info: Font shape `OML/cmr/m/n' in size <8> not available (Font) Font shape `OML/cmm/m/it' tried instead on input line 1. -) [5] +) (./source/CommandMessage.java) -Overfull \hbox (17.32811pt too wide) in paragraph at lines 351--374 +Overfull \hbox (17.32811pt too wide) in paragraph at lines 350--373 [] [] (./sigos.bbl) [6] (./sigos.aux) ) Here is how much of TeX's memory you used: - 3051 strings out of 494008 - 41499 string characters out of 6154472 - 224979 words of memory out of 5000000 - 6466 multiletter control sequences out of 15000+600000 + 3054 strings out of 494008 + 41554 string characters out of 6154472 + 268979 words of memory out of 5000000 + 6469 multiletter control sequences out of 15000+600000 17796 words of font info for 69 fonts, out of 8000000 for 9000 745 hyphenation exceptions out of 8191 33i,12n,58p,606b,1467s stack positions out of 5000i,500n,10000p,200000b,80000s -Output written on sigos.dvi (6 pages, 53384 bytes). +Output written on sigos.dvi (6 pages, 57268 bytes). diff -r 1dd3a4150e7d -r a5958e372cee paper/sigos.pdf Binary file paper/sigos.pdf has changed diff -r 1dd3a4150e7d -r a5958e372cee paper/sigos.tex --- a/paper/sigos.tex Wed May 06 21:10:08 2015 +0900 +++ b/paper/sigos.tex Wed May 06 22:35:51 2015 +0900 @@ -98,21 +98,22 @@ \section{分散フレームワーク Alice の概要} -\subsection*{「Data SegmentとCode Segment」} +\subsection*{[Data SegmentとCode Segment]} AliceはデータをData Segment、（以下DS）タスクをとCode Segment（以下CS）という単位に分割してプログラミングを行う。 DSはAliceが内部にもつデータベースによって管理されている。DSに対応する一意のkeyが設定されており、そのkeyを用いてデータベースを操作する。 CSは実行に必要なDSが揃うと実行されるという性質を持ち、入力されたDSに応じた結果が出力される。 CSを実行するために必要な入力DSはInputDS、CSが計算を行った後に出力されるDSはOutput DSと呼ばれる。データの依存関係にないCSは並列実行が可能であるため、並列度を上げるためにはCSの処理内容を細かく分割して依存するデータを少なくするのが望ましい。 -\subsection*{「Data Segment」} +\subsection*{[Data Segment]} + 複数のスレッドから１つのデータに変更を行うためには、データの不整合を防ぐためのlockが必要になる。複数の関係のない要素を１つのデータオブジェクトで表現した場合、全ての操作でlockが必要になる。このlockがスケラビリティーを低下させる。つまりデータのサイズも並列計算には重要である。 -Aliceはデータを細かく分割して記述する。その細かく分割されたデータをDSと呼ぶ。 -実際には特定のオブジェクトにマッピングされ、マッピングされたクラスを通してアクセスされる。 +Aliceはデータを分割して記述する。その分割されたデータをDSと呼ぶ。 +Javaの実装ではMPでは特定のオブジェクトにマッピングされ、マッピングされたクラスを通してアクセスされる。 -\subsection*{「Data Segment Manager」} +\subsection*{[Data Segment Manager]} DSは実際にはqueueに保存される。queueには対になるkeyが存在し、keyの数だけqueueが存在する。 このkeyを指定してDSの保存、取得を行う。queueの集合体はデータベースとして捉えられる。このデータベースをAliceではDS Manager（以下DSM）と呼ぶ。DSMにはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。Remote DSMは他のノードのLocal DSMのproxyであり、接続しているノードの数だけ存在する。（図\ref{fig:RemoteDSM}）Remote DSMに対して書き込むと対応するノードのLocal DSMに書き込まれる。 @@ -124,7 +125,7 @@ \label{fig:RemoteDSM} \end{figure} -\subsection*{「Data Segment API」} +\subsection*{[Data Segment API]} 以下のData Segment APIを用いてデータベースにアクセスする。 putとupdateはDSを追加する際に、peekとtakeはDSを取得する際に使用する。 @@ -148,7 +149,7 @@ peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。 -\subsection*{「Data Segmentの表現」} +\subsection*{[Data Segmentの表現]} DSの表現にはMessagePack for Javaを利用している。 \begin{itemize} \item {\ttfamily DSは一般的なJavaのクラスオブジェクト} @@ -157,7 +158,7 @@ の２種類があり、LocalDSMにputされた場合は一般的なJavaのクラスオブジェクトとしてenQueueされる。 RemoteDSMにputされた場合は通信時にbyteArrayに変換されたバイナリオブジェクトがenQueueされる。 -\subsection*{「Code Segment」} +\subsection*{[Code Segment]} Alice上で実行されるタスクの単位がCSである。ユーザーはCSを組み合わせることでプログラミングを行う。CSをユーザーが記述する際に、内部で使用するDSの作成を記述する。 Input DS と Output DSはCSに用意されているAPIを用いて作成する。 @@ -167,7 +168,7 @@ Inputの場合はsetKeyを呼ぶ際、Outputの場合はput(またはupdate)の際にノードとkeyの指定を行っている。 しかし、どの時点でノードとkeyの指定を行えばよいか、どのようなAPIを用意するべきかは、議論の余地がある。 -\subsection*{「Code Segmentの記述方法」} +\subsection*{[Code Segmentの記述方法]} CSをユーザーが記述する際にはCSを継承して記述する(ソースコード \ref{src:StartCodeSegment} ,\ref{src:CodeSegment})。 継承することによりCode Segmentで使用するAPIを利用する事ができる。 @@ -215,29 +216,29 @@ 17行目でcountの値をインクリメントしてLocal DSMに値を追加する。 13行目が終了条件であり、countの値が10になれば終了する。 -\subsection*{「ComputationとMeta Computation」} +\subsection*{[ComputationとMeta Computation]} AliceのComputationは、keyで指し示されるDSを待ち合わせてCSを実行させると定義できる。 それに対して、AliceのMeta Computationは、AliceのComputationを支えているComputationのプログラミングと定義できる。 例えば、トポロジーを指定するAPIはMeta Computationである。Aliceが動作するためにはトポロジーを決める必要がある。つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。トポロジーが決定するとそのトポロジーを構成する計算が行われる。トポロジーを指定するAPIはその構成の計算をプログラミングして変更するものである。 他にも再接続の動作を決めるAPIや切断時の動作を決めるAPIはMeta Computationである。 -これらのMeta ComputationがAliceのComputationに影響することはない。プログラマーはCSを記述する際にトポロジーや切断、再接続という状況を予め想定した処理にする必要はない。プログラマーは目的の処理だけ記述する。そして、切断や再接続が起こった場合の処理を記述しMeta Computationで指定する。 +プログラマーはCSを記述する際にトポロジーや切断、再接続という状況を予め想定した処理にする必要はない。プログラマーは目的の処理だけ記述する。そして、切断や再接続が起こった場合の処理を記述しMeta Computationで指定する。 このようにプログラムすることで、通常処理と例外処理を分離することができるため、シンプルなプログラムを記述できる。 -\subsection*{「Meta Data Segment」} +\subsection*{[Meta Data Segment]} DSは、アプリケーションに管理されているデータのことである。アプリケーションを構成するCSによってその値は変更される。 それに対してMeta DSは、分散フレームワークAliceが管理しているデータである。Aliceを構成するCSによってのみ、その値は変更される。一部のMeta DSはアプリケーションに利用することができる。 -例えば、"start"というkeyでは、ノードがStart CSを実行可能かどうかの状態を表す。他にも"\_CLIST"というkeyでは、利用可能なRemote DSの一覧が管理されている。ユーザーはこの一覧にある名前を指定することで、動的にDSの伝搬などを行うことができる。 +例えば、"start"というkeyをもつMeta DSは、ノードがStart CSを実行可能かどうかの状態を表す。他にも"\_CLIST"というkeyでは、利用可能なRemote DSの一覧が管理されている。ユーザーはこの一覧にある名前を指定することで、動的にDSの伝搬などを行うことができる。 また、Input DSに付随しているものもある。Input DSはCS内部でReceiverという入れ物に格納される。ユーザーは、Receiverに対して操作することでDSを入手できる。 このReceiverには、fromというフィールドがあり、このDSを誰がputしたという情報が入っている。この情報をデータの伝搬する際に利用することで、DSをputしたノードに送り返すことを防ぐことができる。 Meta DSはDS同様にDS APIを用いて取得できる。 -\subsection*{「Meta Code Segment」} +\subsection*{[Meta Code Segment]} CSはアプリケーションを動作させるために必要なタスクであり、ユーザーによって定義される。 それに対してMeta CSはAliceを構成するタスクである。つまりMeta CSの群はAliceのComputationと言い換えることができる。一部のみユーザーが定義をすることができ、Aliceの挙動を変更することができる。 @@ -272,12 +273,12 @@ \section{Aliceの新機能} 実用的なアプリケーションであるTreeVNCをAlice上で実装することで、Aliceに必要な機能を洗い出した。 -\subsection*{「flip機能」} +\subsection*{[flip機能]} Data Segment APIのput、updateを呼ぶとOutput Data Segmentが毎回新しく作成され、出力するデータのコピーが行われる。しかし、Input Data Segmentとして取得したデータをそのまま子ノードにOutput Data Segmentとして出力する場合、コピーを行なうのは無駄である。 そこで、Input Data SegmentとOutput Data Segmentを交換する機能をflip機能として実装した。 ソースコード\ref{src:exampleFlip}のようにInput Data SegmentであるReceiverをコピーせずにflipメソッドに引数として渡すことで、コピーのオーバーヘッドをなくしている。 -TreeVNCでは親ノードから受け取った画面データをそのまま子ノードに配信するため、Meta Computationとしてflip機能が使えることは有用である。 +TreeVNCでは親ノードから受け取った画面データをそのまま子ノードに配信するため、Meta Computationとしてflip機能が有用である。 \begin{table}[html] \lstinputlisting[label=src:flipAlice, caption=Aliceにおけるflip]{source/flip.java} \end{table} @@ -286,7 +287,7 @@ \lstinputlisting[label=src:exampleFlip,caption=flipの使用例]{source/Sort.java} \end{table} -\subsection*{「Data Segmentの表現の追加（圧縮機能）」} +\subsection*{[Data Segmentの表現の追加（圧縮機能）]} TreeVNCでは画面配信の際、データを圧縮してノード間通信を行っている。 そのため、AliceVNCにも圧縮されたデータ形式を扱える機能が必要だと考えた。 しかし、ただデータを圧縮する機構を追加すればいいわけではない。 @@ -311,32 +312,31 @@ \end{table} また、圧縮状態を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerの追加した。Compressed DSMの内部では、put/updateが呼ばれた際にReceiveData.classが圧縮表現を持っていればそれを使用し、持っていなければその時点で圧縮表現を作ってput/updateを行う。 -ユーザが圧縮形式での通信を行いたい場合、ソースコード\ref{src:zput}、\ref{src:ztake}のように指定するDSM名の先頭に"compressed"をつけることでCompressed DSM内部の圧縮Meta Computationが走りDSを圧縮状態で扱うようになる。 +ソースコード\ref{src:before}はRemoteからDSをtakeしインクリメントしてLocalにputすることを10回繰り返す例題である。これをDSを圧縮形式で行いたい場合、ソースコード\ref{src:after}のように指定するDSM名の先頭に"compressed"をつければCompressed DSM内部の圧縮Meta Computationが走りDSを圧縮状態で扱うようになる。 \begin{table}[html] -\lstinputlisting[label=src:zput, caption=圧縮DSのput]{source/compress_put.java} +\lstinputlisting[label=src:before, caption=通常のDSを扱うCSの例]{source/beforeCompress.java} \end{table} \begin{table}[html] -\lstinputlisting[label=src:ztake,caption=圧縮DSのtake]{source/compress_take.java} +\lstinputlisting[label=src:after,caption=圧縮したDSを扱うCSの例]{source/afterCompress.java} \end{table} これによりユーザは指定するDSMを変えるだけで、他の計算部分を変えずに圧縮表現を持つDSを扱うことができる。ノードは圧縮されたDSを受け取った後、そのまま子ノードにflipすれば圧縮状態のまま送信されるので、送信の際の再圧縮がなくなる。 -画面表示の際は{\tt asClass()}(ソースコード\ref {src:asClass} )を使うことで適切な形式でデータを取得できる。 +画面表示の際はReceiveData.class内の{\tt asClass()}(ソースコード\ref {src:asClass} )を使うことで適切な形式でデータを取得できる。 {\tt asClass()}はDSを目的の型にcastするメソッドであり、ReceiveData.classが圧縮表現だけを持っている場合はこのメソッド内で解凍してcastを行っている。 -これによりDSの表現を必要になったときにその場で作成できる。 +これによりDSの表現を必要になったときに作成できる。 \begin{table}[html] \lstinputlisting[label=src:asClass, caption=asClassの処理]{source/asClass.java} \end{table} -\subsection*{「パケットの再設計」} -2章「Data Segmentの表現」で述べたように、Remoteからputされたデータは必ずシリアライズ化されておりbyteArrayで表現される。 -しかし、データの表現に圧縮形式を追加したことで、RemoteからでもputされたbyteArrayが圧縮されているのかそうでないのかが判断できなくなった。 +\subsection*{[Aliceの通信プロトコルの変更]} +2章 [Data Segmentの表現]で述べたように、Remoteからputされたデータは必ずシリアライズ化されておりbyteArrayで表現される。 +しかし、データの表現に圧縮したbyteArrayを追加したため、RemoteからputされたbyteArrayが圧縮されているのかそうでないのかを判断する必要がある。 -そこで、データの状態を表すフラグをヘッダに含めてパケットを構成するように変更した。 -Aliceの通信におけるヘッダにあたるCommandMessage.class(ソースコード\ref {src:CommandMessage})にシリアライズ状態表すフラグと、圧縮状態を表すフラグを追加した。 +そこで、Aliceの通信におけるヘッダにあたるCommandMessage.class(ソースコード\ref {src:CommandMessage})にシリアライズ状態表すフラグと、圧縮状態を表すフラグを追加した。 これによってputされたDSMはフラグに応じた適切な形式でReceiveData.class内にDSを格納できる。 また、CommandMessage.classに圧縮前のデータサイズも追加したことで、適切な解凍が可能になった。 @@ -376,9 +376,9 @@ \section{まとめ} -本研究では、まずはじめに並列分散フレームワークAliceの計算モデルと実装について説明を行い、Aliceにおけるプログラミング手法を述べた。 +並列分散フレームワークAliceの計算モデルと実装について説明を行い、Aliceにおけるプログラミング手法を述べた。 -次に、Aliceが実用的なアプリケーションを記述するために必要なMeta Computationとして、データの多態性を実現し、指定するDSMの切り替えで扱うデータ表現を変えるようにした。 +Aliceが実用的なアプリケーションを記述するために必要なMeta Computationとして、データの多態性を実現し、指定するDSMの切り替えで扱うデータ表現を変えるようにした。 これにより、必要に応じた形式を扱うことができ、ユーザが記述するComputation部分を大きく変えずに自由度の高い通信を行うことが可能になった。 同様の手法を用いれば、圧縮形式以外にも暗号形式・JSON形式などの複数のデータ表現をユーザに扱いやすい形で拡張することができる。