Mercurial > hg > Papers > 2012 > sugi-prosym

Binary file presen/.DS_Store has changed
--- a/presen/alice-presen.ind	Fri Jan 11 09:58:57 2013 +0900
+++ b/presen/alice-presen.ind	Fri Jan 11 15:15:59 2013 +0900
@@ -11,12 +11,20 @@

 これらの経験から並列分散を統一的に扱えるプログラミングフレームワークを考えたい。

+そこで、
+
+    data segment と code segment で書くというのを考えた
+    Java で実装して評価した
+
 --並列分散フレームワークには何が求められるのか

     並列実行単位の記述
     プロトコルの記述
     実用的な実装
+    高い対障害性
+    Scalability
     実験環境の用意
+    Version up への対応
     多言語対応
     検証や証明への対応

@@ -27,298 +35,186 @@
    in Tuple を取り出す
    out Tuple 書きだす

+in, out で待ち合わせを行う
+
 --Federated Linda の Pros and Cons

+in/out のAPIさえあれば良いので、言語独立 (良)
+
+Tuple のキーが文字列でわかりやすい (良)
+
+切断に強い (良)
+
+記述部分がスパゲティになりやすい (悪)
+
+call back を使うと、さらにダメな記述に (悪)
+
+--Linda の だめな記述の例
+
+    left.in(Up, new PSXCallback() {public void callback(ByteBuffer reply) {
+        if (debug) System.out.println("Up from left at"+nodeId);
+        left.in(Up,this);
+        leftWaiter.add(reply);
+        checkSend(ml);
+    }
+
 --Cerium

 Task 単位で並列実行するツール

+Task を作って scheduler に投入
+
+Task のデータは暗黙に通信される
+
+Open CL 、Spurs Engine などの実装がある
+
 --Cerium の Pros and Cons

+Task は短く単純になる (良)
+
+アセンブラ的なので性能は出やすい (良)
+
+Task の依存関係は自分で管理 (悪)
+
+データ構造は基本的に配列になりやすい (悪)
+
+Task 管理部分が極めて複雑になる (悪)
+
+--Cerium  の だめな記述の例
+
+    {
+        int i = half_num-1;
+
+        if (s->bsort[i]) manager->free_htask(s->bsort[i]);
+        s->bsort[i] = manager->create_task(QUICK_SORT,
+            (memaddr)&s->data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num,
+            (memaddr)&s->data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num);
+        s->bsort[i]->flip();
+        s->bsort[i]->set_cpu(GPU_0);
+        s->bsort[i]->set_param(0,(memaddr)last_half_block_num);
+    }
+
+    for (int i = 0; i < half_num; i++) {
+        s->bsort[i]->wait_for(s->fsort[i]);
+        s->bsort[i]->wait_for(s->fsort[i+1]);
+        s->bsort[i]->no_auto_free();
+        s->bsort[i]->spawn();
+    }
+
+
+--Linda と Cerium の良いとこ取りをしたい
+
+Task 依存は、Tuple の依存で決まる
+
+コードをTaskに分割する
+    Code Segment
+
+データをTupleに分割する
+    Data Segment
+
+Code と Data は双対になるはず
+
 --Data segment と Code Segment

+Code segment には input data segment と output data segment がある
+
+<center><img src="images/reconnection.jpg"></center>
+
 --Java Implmentation : Alice

+data segment は key (strig) でアクセスされる
+
+input data segment は書き込みを待つ
+
+--Local / Remote data segment Manager
+
+Data Segmentを管理するのが、Data Segment Manager 各ノード毎に、Local DS ManagerとRemote DS Managerが存在する。
+
+Local DS Managerはノード固有のKey Value Storeであり、Remote DS Managerは他のノードのLocal DS Managerのproxyである。
+
+<center><img src="images/lrds.png"></center>
+
 --CS/DS API

---Alice Architecture
+input data segment の作成 (PEEKとTAKE)
+    public Receiver ds1 = ids.create(CommandType.TAKE);
+key の設定
+    ds1.setKey("finish");
+output data segment の書き出し (put と update)
+    ods.put("local", "finish", ValueFactory.createNilValue());
+
+これらを用いてデータの送受信を行う。
+
+--Data segment の型
+
+MessagePack を使用すると、そのままオブジェクトを data segment に使える
+
+   import org.msgpack.annotation.Message;
+   @Message
+   public class FishPoint {
+     public float x = 0.0f;
+     public float y = 0.0f;
+     public float z = 0.0f;
+   }
+
+
+--Example

---Sample Application
+    public class SendWidth extends CodeSegment {
+        Receiver width = ids.create(CommandType.PEEK);
+        @Override
+        public void run() {
+            int width = this.width.asInteger();
+            ods.put("parent", "widths", width);
+            System.out.println("send widths: " + width);
+            SendWidth cs = new SendWidth();
+            cs.width.setKey("local", "width", this.width.index);
+        }
+    }
+
+
+--Sample Application 水族館の例題
+
+複数の魚が複数のディスプレイ上を移動する。
+
+魚のうち一匹はクライアントが操作することができる。
+
+トポロジーはツリー状に構成してある。
+<center><img src="images/aquarium.png"></center>
+
+--CS/DS Java 版 Alice
+
+Java で SEDA をしようして実装
+
+MessagePack を使って Marshaling
+
+--SEDA
+
+Thread pool を使ったパイプラインによるサーバ実装
+
+応答よりもスループット重視
+
+<center><img src="images/SEDA.jpg"></center>

 --Experiment

---Ring
-
-
-
-
-
-に置いて、タスクをCode Segment、データをData Segmentという単位に分割して記述する方法を提唱している。</p>
-<p>しかし、前述したプログラムをプログラマーが一から記述していくことは大変である。</p>
-<p>そこで、本研究室の卒業生である赤嶺一樹氏が分散ネットフレームワークAliceのプロトタイプを作成した。</p>
-<p>本研究では実際にAliceを利用して、水族館の例題を作成した。また、Federated Lindaとの性能比較を行った。そして、Aliceの問題点の洗い出し、APIの見直しを行った。</p>
-
---発表内容
-<ul>
-<li>Aliceの紹介
-<li>プログラムの記述方法
-<li>水族館の例題と性能評価
-<li>まとめと課題
-</ul>
-
---Alice
-<ul>
-<p>Alice は本研究室で開発を行なっている分散タスク管理フレームワークである。</p>
-<p>Cell用のOpen CL に似たTask管理用フレームワークCeriumと
-	   Lindaを相互接続した分散フレームワークであるFederated Lindaの開発を通して得られた知見を生かされている。</p>
-<ul>
-
---Cerium
-<ul>
-<p>Ceriumは当研究室で開発を行なっている並列プログラミングフレームワークである。</p>
-<p>CeriumではTaskを小さく分割して並列実行し、データ転送はパイプライン実行により隠される。</p>
-<p>Taskには依存関係がありデータの依存関係がそのままTaskの依存関係になることが多い。</p>
-<p>繰り返し使われるデータの管理が重要であり、実行時にわかるデータ構造間の依存関係がTaskを複雑にしている。</p>
-</ul>
-
---Data Segment API
-<ul>
-<p>Data Segmentは数値や文字などのデータを構造体的に保持するが、分散プログラムにおいてData Segmentの相互参照が問題になってくる。</p>
-<p>AliceではData SegmentにユニークなKeyを持たせ、Key Value Storeとして扱っている。Key毎のキューがあり、Key毎に順に実行される。<br>
-<div align="center">
-<img src="images/dataSegment_key.png">
-</div>
-
-</ul>
-
-
---Data Segment API
-<ul>
-<p>Data Segmentを管理するのが、Data Segment Manager
-	   各ノード毎に、Local DS ManagerとRemote DS Managerが存在する。</p>
-<p>Local DS Managerはノード固有のKey Value Storeであり、Remote DS Managerは他のノードのLocal DS Managerのproxyである。
-	 AliceのTopology Managerが自動的に構成する。</p>
-<div align="center">
-<img src="images/lrds.png" width=500>
-</div>
-</ul>
-
-
---Data Segment API
-<ul>
-	  以下が用意されているData Segment APIである。
-<li>void put(String key, Value val)</li>
-<li>void update(String key, Value val)</li>
-<li>void peek(Receiver receiver, String key)</li>
-<li>void take(Receiver receiver, String key)</li>
-<p>これらを用いてデータの送受信を行う。</p>
-</ul>
-
---Data Segment API - put
-<ul>
-<li>データを追加する</li>
-</ul>
-<div align="center">
-<img src="images/put.png" width=70%>
-</div>
-<ul>
-<p>putを行うとデータがenqueueされる。</p>
-<p>putするたびにKeyが持つindexがincrementされる。</p>
-</ul>
-
---Data Segment API - update
-<ul><li>データを置き換える</li></ul>
-<div align="center">
-<img src="images/update.png" width=70%>
-</div>
-<ul>
-	 putと異なる点は先頭データを削除し、データを追加する。
-</ul>
-
---Data Segment API - peek
-<ul><li>データを取得する</li></ul>
-<div align="center">
-<img src="images/peek.png" width=50%><br>
-</div>
-<ul>
-	 peekはデータを取得しreceiverに渡す。
-</ul>
-
---Data Segment API - peek
-<div align="center">
-<img src="images/peek1.png" width=60%><br>
-</div>
-<ul>
-<p>要求したデータがない場合にはwaitListに登録する。</p>
-	   データがput、updateされる際に要求したデータがあるかどうかを再びチェックする。
-
-</ul>
-
---Data Segment API - take
-<ul><li>データを取得して取得されたデータはdequeueされる</li></ul>
-<div align="center">
-<img src="images/take.png" width=50%><br>
-</div>
-<ul>
-<p>基本的な動作はpeekと同じである。</p>
-<p>peekと異なる点は取得されたデータがdequeueされる。</p>
-</ul>
-
---Data Segmentの実装
-<ul>
-	 Data Segmentのデータ表現はMessagePackを使用。
-</ul>
-<ul><p>JavaにおけるMessagePackのデータ表現</p>
-<li>一般的なJavaのクラスオブジェクト</li>
-<li>MessagePack for JavaのValueオブジェクト</li>
-<li>byte[]で表現されたバイナリ</li>
-</ul>
-<ul>
-<p>Data Segment APIでは</p>
-	 MessagePack for javaのValueオブジェクトを使用</p>
-         MessagePackのバイナリにシリアライズできる型のみで
-         構成されているため自己記述式のデータ形式
-</ul>
-
---Data Segmentの実装
-<ul>
-<p>Valueオブジェクトは通信に関わる際には、シリアライズ、デシリアライズを高速に行うことができる</p>
-<img src="images/FishPoint.png" width=700><br>
-	  ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを記述することが可能
-</ul>
-
---CodeSegment
-<ul>
-<li>Code Segmentはタスクのこと</li>
-<li>ユーザーが記述する際にCode Segment内で使用する<br>Data Segmentの作成を記述</li>
-<li>Input Data SegmentとOutput Data Segmentを作るAPI</li>
-<li>必要なInput Data Segmentが揃った時に実行される</li>
-</ul>
-
---Input Data SegmentとOutput Data Segment
-<ul>
-<li>localかremoteを指定</li>
-<li>Data Segmentに関連付けされているKEYを指定</li>
-</ul>
-
-<ul>
---Data Segmentの例
-<img src="images/SendWidth.png" width=600>
-</ul>
-
---Input Data Segmentの例
-<ul>
-<img src="images/ids.png" width=400><br>
-	 Receiverの作成<br>
-	 PEEK,TAKEのどちらかを選択
-</ul>
-<ul>
-<img src="images/idsSetkey.png" width=600><br>
-	 第1引数 マシン名<br>
-	 第2引数 Data Segmentに関連付けられているKEY<br>
-	 第3引数 index(指定しない場合は先頭データが取得される)<br>
-</ul>
-
---Output Data Segmentの例
-<ul>
-<img src="images/ods.png" width=400><br>
-	  putかupdateのどちらかを選択
-</ul>
-<ul>
-      	  第1引数 マシン名<br>
-	  第2引数 Data Segmentに関連付けるKEY<br>
-	  第3引数 Data Segment<br>
-</ul>
-
---Code Segmentの実行方法
-<ul>
-<img src="images/StartCS.png" width=600><br>
-</ul>
-<ul>
-	  AliceにはCのmainに相当するStart Code SegmentというCode Segmentが存在する。<br>
-	  Start Code SegmentはInput Data Segmentが存在しない。
-</ul>
-
---Code Segmentの実行方法
-<ul>
-<img src="images/execute.png" width=600><br>
-</ul>
-<ul>
-	 このStart Code Segmentをnewし、executeメソッドを呼ぶことでCode Segmentを実行することができる。
-</ul>
-
---Code Segmentの記述方法
-<ul>
-<img src="images/TestCodeSegment.png" width=600><br>
-</ul>
-	ユーザがCode Segmentを記述する際にはCode Segmentを継承する。<br>
-	runの中に実際にさせたい処理を記述する。
-
---Topology Manager
-<ul>
-	  Alice同士の接続トポロジーを管理する。<br>
-	  トポロジーファイルを読み込み、参加を表明したクライアントに接続すべきクライアントのIPアドレスやポート番号、接続名を送る。
-<div align="center">
-<img src="images/topology.png" width=350>
-</div>
-</ul>
-
---Topology Manager
-<ul>
-	  Topology Manager関連の通信は全て、Code Segmentで実装されている。
-</ul>
-
---トポロジーファイル
-<ul>
-<p>トポロジーファイルはDOT Languageと言う言語で記述される。</p>
-	  DOT Languageはプレーンテキストを用いてデータ構造としてのグラフを表現するデータ記述言語の一つ。<br>
-	  DOT Languageのグラフ構造を用いてTopology Node間の接続を表現する。<br>
-</ul>
-
---トポロジーファイルの記述方法
-<ul>
-<img src="images/topologyfile.png">
-<p>dotコマンドを用いて、グラフの画像ファイルを生成することができるのでトポロジーが正しいか確認することができる。</p>
-
-</ul>
-
---トポロジーファイルの確認方法
-<ul>
-<p><strong>dot -T png ring.dot -o ring.png</strong></p>
-<div align="center">
-<img src="images/dot.png">
-</div>
-</ul>
-
---水族館の例題
-<ul>
-<p>複数の魚が複数のディスプレイ上を移動する。</p>
-<p>魚のうち一匹はクライアントが操作することができる。</p>
-<p>トポロジーはツリー状に構成してある。</p>
-</ul>
-<div align="center">
-<img src="images/aquarium.png" width=800>
-</div>
-
-<div align="center">
-<img src="images/commnuication.png" width=600>
-</div>
-
---性能比較 - 実験概要
-<ul>
-	  AliceとFederated Linda で性能比較を行った。<br>
+	  AliceとFederated Linda で性能比較を行った。
 	  Ring型のトポロジーを構成、メッセージが100周する時間を計測。
 	  1周あたりの平均時間を求めた。
-<div align="center">
-<img src="images/ringTest.png">
-</div>
+<center><img src="images/ringTest.png"></center>
+
 	  パケットのサイズは10byte,10Kbyte,100kbtyeで実験
-</ul>
+
+--何故 Ring?
+
+なぜ、不利なベンチマークを取るのか?

---実験環境
-<ul>
-	  ブレードサーバー上の仮想マシンによる仮想クラスタ環境を用いて実験した。<br>
-<p><strong>ブレードサーバー詳細</strong></p>
+SEDA でレスポンスをはかっちゃだめだろう?
+
+SEDA はCPU食い。Core Duo とかで全然ダメ。
+
+なので、Core i7 を用意しました。
+
 <table style="font:Osaka;text-align:right;" border="2" >
 <tr>
 <td>マシン台数</td>
@@ -344,79 +240,34 @@
 <td>132GB</td>
 </tr>
 </table>
-
-</ul>
---実験環境
-<ul>
-<p><strong>仮想クラスタ詳細</strong></p>
-<table style="font:Osaka;text-align:right;" border="2" >
-<tr>
-<td>マシン台数</td>
-<td>48台</td>
-</tr>
-<tr>
-<td>CPU</td>
-<td>Intel(R) Xeon(R) X5650 @ 2.67GHz</td>
-</tr>
-<tr>
-<td>物理コア数</td>
-<td>2</td>
-</tr>
-<tr>
-<td>論理コア数</td>
-<td>4</td>
-</tr><tr>
-<td>CPU キャッシュ</td>
-<td>12MB</td>
-</tr>
-<tr>
-<td>Memory</td>
-<td>8GB</td>
-</tr>
-</table>
-</ul>
+
+
+--実験結果 小さいデータ
+
+<strong>10byte</strong>
+<center><img src="images/ring10B.png"></center>
+
+Single threaded な Federated Linda に負けている
+
+--実験結果 大きなデータ

---実験結果
-<ul>
-<strong>10byte</strong><br>
-<img src="images/ring10B.png" width=650>
-</ul>
-
---実験結果
-<ul>
-<strong>10kbyte</strong><br>
-<img src="images/ring10KB.png" width=650>
-</ul>
-
---実験結果
-<ul>
 <strong>100kbyte</strong>
-<img src="images/ring100KB.png" width=650><br>
+<center><img src="images/ring100KB.png"></center>
 	  データ量が増えると差が縮まっている。これはここの通信の手間の影響が大きことを示している。
-</ul>

---評価と考察
-<ul>
-	  今回の実装はJavaによりCode SegmentとData Segmentに必要なAPIを洗い出すものだった。この実装でも問題をいくつか発見した。<br>
-<p><strong>API</strong></p>
-<li>Class継承したりData Segmentの作成にFactory objectを使うのはJavaを使う際の技術的な問題</li>
-<li>JavaのObject指向な記述が全体を煩雑にしている部分がある</li>
-<li>updateはData Segmentの競合的な更新に使われるべきだと思われる</li>
-</ul>
-
---評価と考察
-<p><strong>SEDA</strong></p>
-<ul>
-<li>Federated Lindaに比べ遅い原因の一つはSEDA architectureのせいと思われる</li>
-<li>SEDAはスループット重視の実装であり、多段パイプラインのせいでレスポンスが遅れてしまう</li>
-
-</ul>
-
---評価と考察
-<ul>
-<li>スレッドプールを使わないほうが、Ringの結果は良い</li>
-<img src="images/notp.png" width=650><br>
-</ul>
+
+--実験結果 スレッドプールなし
+
+スレッドプールを使わないほうが、Ringの結果は良い<
+<center><img src="images/notp.png"></center>
+
+
+--わかりやすい記述になったのか?
+
+Input DS と Output DS の記述が対称にならない
+
+CS/DS の関係を CS 内部に書くのはダメな戦略?
+

 --評価と考察
 <p><strong>MessagePack</strong></p>