# HG changeset patch
# User kazz <kazz@cr.ie.u-ryukyu.ac.jp>
# Date 1317104867 -32400
# Node ID 21c68d67d7a553335d22ad721a4d040dba84343c
# Parent  1ad07d67472f8b06b4ddc727bb8d40eeccfad7b8
presen finish

diff -r 1ad07d67472f -r 21c68d67d7a5 presen/index.html
--- a/presen/index.html	Mon Sep 26 20:35:05 2011 +0900
+++ b/presen/index.html	Tue Sep 27 15:27:47 2011 +0900
@@ -54,7 +54,7 @@
 <ul>
   <li>ブロードバンド環境やモバイル端末の普及により、ネットワーク上におけるサービスの巨大化は必至である</li>
   <li>スケーラビリティ(サービスの大きさが増えてもリソースの追加のみでサービスの質を維持できること)を備えたプログラムを作成するためには、いろいろなプロトコルを提案し、実装し、検証していく必要がある</li>
-  <li>提案したプロトコルを<strong>玩具的に</strong>実験できるフレームワークが求められている</li>
+  <li>提案したプロトコルを<strong>シンプルに</strong>実験できるフレームワークが求められている</li>
 </div>
 
 <div class="slide">
@@ -132,6 +132,7 @@
 <ul>
   <li>Meta Engine と呼ばれる Protocol Engine の代替となるプログラムを、タプルスペースと同プロセス上に設置</li>
   <li><strong>直接タプルスペースにアクセス可能になった</strong></li>
+  <li>ここまでが先行研究</li>
 </ul>
 </div>
 <img src="./img/metafedlinda.png" style="display: block; width: 37%; margin: auto; float: right; margin-right: 3%; margin-top: 2%;"/>
@@ -166,165 +167,246 @@
 <h1>Federated Linda の問題点</h1>
 <p class="subhead">Protocol Engine の実行方法</p>
 <ul>
-  <li>Polling based</li>
+  <li><strong>Polling based</strong></li>
   <ul>
     <li>メインループで定期的に Protocol Engine を実行し、 Tuplespace からデータを取得し、確認する。 </li>
     <li>通信が発生する度、記述した Tuple へのアクセスが発生する</li>
   </ul>
-  <li>Callback function based</li>
+  <li><strong>Callback function based</strong></li>
   <ul>
     <li>とある Tuple が更新される度にその Tuple に設定された Callback function が実行される。</li>
     <li>その Tuple が更新された時に適切に呼び出される。</li>
     <li>Callback function がツリー状に連鎖されるため、プログラマがツリーを管理する必要がある。</li>
+    <li>コードをシーケンシャルに読めない。</li>
+  </ul>
+</ul>
+</div>
+
+<div class="slide">
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">Geometric Routing</p>
+<ul>
+  <li>分散アプリケーションにおいて Configuration が複雑になるという問題</li>
+  <li>具体的には <strong>Connection</strong> と <strong>Routing</strong></li>
+  <li>接続の自由度が高いと、記述するコード量が増えるため、トポロジーを固定的なものに限定することで簡単化</li>
+  <li>予めトポロジーを構成するロジックを別に用意しておく</li>
+  <ul>
+    <li>Ring</li>
+    <li>Tree</li>
+    <li>Mesh</li>
+    <li>etc...</li>
   </ul>
 </ul>
 </div>
 
-
-
-
-
-
-
-
-
-
+<div class="slide">
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">Geometric Routing - Connection</p>
+<ul>
+  <li>参加するサーバーのリストとトポロジーを参加するサーバー全体に渡す。</li>
+  <li>個々のサーバーは、与えられたトポロジーに基づいて、接続を張る。</li>
+  <li>接続したサーバーには分かりやすい GeoAddress でアクセスできる。</li>
+  <li>ex) Ring Topology の場合、 RING_RIGHT 、 RING_LEFT などのアクセス可能な Address が得られる。</li>
+  <li>ex) Hypercube Topology なら、 HC_0010 、 HC_0110 など。</li>
+</ul>
+</div>
 
-
-
-
-
-
-
-
-
-
+<div class="slide">
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">DataSegment API を用いた分散フレームワーク</p>
+<div style="float: left; width: 55%;">
+<ul>
+  <li>分散処理を CodeSegment と呼ばれる処理単位で記述し、そこで用いられるデータを DataSegment と呼ばれるデータ単位にまとめる。</li>
+  <li>必要な DataSegment を CodeSegment に記述していくことで、それらに依存関係が生まれ、自明に実行順序が決まる。</li>
+</ul>
+</div>
+<img src="img/csds.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
+</div>
 
 <div class="slide">
-<h1>Federated Linda を用いた設計</h1>
-<p class="subhead">スケーラブルな分散プログラミングモデルの設計</p>
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">DataSegment の型</p>
 <ul>
-  <li>複数のサーバーを接続することで負荷を分散する</li>
-  <li>情報を取捨しながら伝搬する</li>
+  <li>Federated Linda では、 Tuple の型は単なる byte[] であり、内部のデータ構造を自分で決める必要があった。</li>
   <ul>
-    <li>すべてのデータをレプリケーションする必要はない</li>
-    <li>サーバーがクライアントの必要な情報とは何かを把握する</li>
+    <li>バイトオーダー</li>
+    <li>浮動小数点</li>
+    <li>構造体</li>
+  </ul>
+  <li>DataSegment はシリアライズライブラリ MessagePack で扱えるフォーマット(like JSON)で型付けを行う。</li>
+  <li>list や hash のサポート</li>
+  <li>データがシリアライズ可能になるため、リモートへのデータ転送も容易に。</li>
+</ul>
+</div>
+
+<div class="slide">
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">DataSegment の API</p>
+<ul>
+  <li>DataSegment には以下の API が用意されている</li>
+  <ul>
+    <li>create</li>
+    <li>read</li>
+    <li>update</li>
+    <li>delete</li>
   </ul>
 </ul>
 </div>
 
-
-
 <div class="slide">
-<h1>Meta Engine を用いた設計例</h1>
-<p class="subhead">ツリー型トポロジーを用いた負荷分散</p>
-<div style="display: block; float: left; width: 60%;">
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">DataSegment の表現</p>
+<div style="float: left; width: 55%;">
 <ul>
-  <li>ツリー型トポロジーを用いて、負荷を分散する</li>
-  <li>末端にクライアントを接続する</li>
-  <li>末端のノードは、クライアントから受け取った座標情報をクライアントが必要か判断する</li>
-  <ul>
-    <li>必要ならば、その Linda サーバーのみで通信は完結</li>
-    <li>必要でないなら、親に判断を委ねるため、親に伝搬</li>
-  </ul>
-  <li>伝搬された上位ノードは、子のノードが必要か判断し、子に伝搬するか、親に伝搬するかを決定する</li>
-  <li><strong>データを必要としているマシンのみにデータを伝搬する</strong></li>
+  <li>DataSegment はデータ型と ID で表現される。</li>
+  <li>データ型は MessagePack で表現できる構造体の名前</li>
+  <li>ID は <strong>GeoAddress</strong> と <strong>LocalAddress</strong> の2つの部分に分けて表現される。</li>
 </ul>
 </div>
-<img src="./img/treetopology.png" style="display: block; width: 37%; margin: auto; float: right; margin-right: 3%; margin-top: 5%;"/>
+<img src="img/datasegment.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
 </div>
 
 <div class="slide">
-<h1>タプルの伝搬</h1>
-<div class="incremental" style="position: relative;">
-  <div style="position: absolute; left: 10%;">
-    <img src="img/relay1.png" style="display: block; width: 80%;">
-  </div>
-  <div style="position: absolute; left: 10%;">
-    <img src="img/relay2.png" style="display: block; width: 80%;">
-  </div>
-  <div style="position: absolute; left: 10%;">
-    <img src="img/relay3.png" style="display: block; width: 80%;">
-  </div>
-  <div style="position: absolute; left: 10%;">
-    <img src="img/relay4.png" style="display: block; width: 80%;">
-  </div>
-  <div style="position: absolute; left: 10%;">
-    <img src="img/relay5.png" style="display: block; width: 80%;">
-  </div>
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">DataSegment の表現 - GeoAddress</p>
+<div style="float: left; width: 55%;">
+<ul>
+  <li>GeoAddress はトポロジー上のデータの所在を示す。</li>
+  <ul>
+    <li><strong>Persistent</strong></li>
+    <ul>
+      <li>KVS 上にある DataSegment</li>
+    </ul>
+    <li><strong>Remote</strong></li>
+    <ul>
+      <li>他のサーバー上にある DataSegment</li>
+    </ul>
+    <li><strong>Local</strong></li>
+    <ul>
+      <li>自サーバー上にある DataSegment</li>
+    </ul>
+  </ul>
+</ul>
 </div>
+<img src="img/datasegment.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
 </div>
 
+<div class="slide">
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">DataSegment の表現 - LocalAddress</p>
+<div style="float: left; width: 55%;">
+<ul>
+  <li>LocalAddress は、自サーバー上の所在を表すアドレスである。</li>
+</ul>
+</div>
+<img src="img/datasegment.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
+</div>
 
 
 <div class="slide">
-<h1>update API の追加</h1>
-<p class="subhead">in/out による更新</p>
-<div style="display: block; float: left; width: 60%;">
-<p>
-現在の Linda では、タプルのデータを更新するために、 in/out を順に実行する必要がある。
-</p>
-<ol>
-  <li>in によって、データを削除</li>
-  <li>out によって、更新データを送信</li>
-  <li>はじめに実行した in の reply がもどってくる</li>
-</ol>
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">Protocol Engine の代わりに CodeSegment を利用</p>
+<div style="float: left; width: 55%;">
+<ul>
+  <li>Federated Linda における Protocol Engine は、 Callback function で記述し、その接続を管理する機構がなかった。</li>
+  <li>シングルスレッドでつくられているため、 Protocol Engine の並列実行ができなかった。</li>
+</ul>
+</div>
+<img src="img/dsandcs.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
 </div>
-<img src="./img/apiinout.png" style="display: block; width: 37%; margin: auto; float: right; margin-right: 3%; margin-top: 5%;"/>
+
+<div class="slide">
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">Protocol Engine の代わりに CodeSegment を利用</p>
+<div style="float: left; width: 55%;">
+<ul>
+  <li>新設計では、 Protocol Engine に代わり、 CodeSegment という単位で処理を記述する。</li>
+  <li>CodeSegment は InputDataSegment と OutputDataSegment それぞれのリストを持っている。</li>
+  <li>InputDataSegment は CodeSegment が利用するデータ、 OutputDataSegment は CodeSegment が書きだすデータのことである。</li>
+</ul>
+</div>
+<img src="img/dsandcs.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
+</div>
+
+<div class="slide">
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">CodeSegment の利用方法</p>
+<div style="float: left; width: 55%;">
+<ul>
+  <li>InputDataSegment と OutputDataSegment の ID を指定</li>
+  <li>OutputDataSegment の指定された ID が存在しない場合は新しく create を行う。</li>
+  <li>存在する ID だった場合は、 update を行う。</li>
+</ul>
+</div>
+<img src="img/dsandcs.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
 </div>
 
 <div class="slide">
-<h1>update API の追加</h1>
-<p class="subhead">update による更新</p>
-<div style="display: block; float: left; width: 60%;">
-<p>
-本研究では、更新を行うための新しい API である update を作成した。
-</p>
-<ol>
-  <li>update によって、更新データを送信</li>
-  <li>更新前のデータの reply がもどってくる</li>
-</ol>
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">CodeSegment の利用方法</p>
+<div style="float: left; width: 55%;">
+<ul>
+  <li>OutputDataSegment が Remote サーバー上に存在する場合は、 Local のバッファーに書き出し、転送する CodeSegment を呼び出すことで表現できる。</li>
+</ul>
 </div>
-<img src="./img/apiupdate.png" style="display: block; width: 37%; margin: auto; float: right; margin-right: 3%; margin-top: 5%;"/>
+<img src="img/remoteds.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
 </div>
 
 <div class="slide">
-<h1>評価</h1>
-<p class="subhead">update API の検証</p>
-<div style="display: block; float: left; width: 60%;">
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">CodeSegment の利用方法</p>
+<div style="float: left; width: 55%;">
 <ul>
-  <li>update と in/out の双方を用いた場合で比較を行った</li>
-  <li>それぞれの API で N 回の更新を行う処理を2台のマシンを用いて計測</li>
-  <li><strong>update と in/out のどちらを用いても、処理速度に影響は見られない</strong></li>
-  <li>大量のマシンを使ってアクセスを集中すると差が出たかもしれない。</li>
+  <li>TaskManager に CodeSegment を登録する。</li>
+  <li>TaskManager は必要な InputDataSegment が揃った CodeSegment を Executor に投げる。</li>
 </ul>
 </div>
-<img src="./img/apigraph.png" style="display: block; width: 37%; margin: auto; float: right; margin-right: 3%; margin-top: 5%;"/>
+<img src="img/dsandcs.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
 </div>
 
 <div class="slide">
-<h1>評価</h1>
-<p class="subhead">TCP No Delay の検証</p>
-<div style="display: block; float: left; width: 60%;">
+<h1>DataSegment API を用いた新設計</h1>
+<p class="subhead">競合的な DataSegment の書き出し</p>
 <ul>
-  <li><strong>TCP No Delay</strong>: 短いパケットの送信を遅延させる動作の制御フラグ</li>
-  <li>TORQUE を利用して N 台のクラスタ上に Federated Linda でリング型トポロジーを構築</li>
-  <li>100周にかかった時間から、1周にかかる時間を平均して求めた</li>
-  <li>5台から45台まで5台刻みで計測</li>
-  <li><strong>TCP No Delay を用いても通信速度に特に効果は見られなかった。</strong></li>
+  <li>DataSegment の update 方法にはいくつか種類がある。</li>
+  <li><strong>FIFO</strong></li>
+  <ul>
+    <li>実行された順に update する</li>
+  </ul>
+  <li><strong>Priority</strong></li>
+  <ul>
+    <li>優先順位が高いものが update する</li>
+  </ul>
+  <li><strong>Queueing</strong></li>
+  <ul>
+    <li>上書き update せずに書きこみを Queue に格納して順番に取り出す</li>
+  </ul>
 </ul>
 </div>
-<img src="./img/tcpnodelaygraph.png" style="display: block; width: 37%; margin: auto; float: right; margin-right: 3%; margin-top: 5%;"/>
-</div>
 
 <div class="slide">
 <h1>まとめと今後の課題</h1>
 <ul>
-  <li>Meta Engine を用いることによって同一サーバー上のタプルスペースに直接アクセスできるようになり、プログラミングをしやすくなった。</li>
-  <li>update API の追加により、更新処理の記述がシンプルになった</li>
-  <li>ツリー型トポロジーの実装を通して、 Federated Linda の問題点を洗い出したい</li>
-  <li>サーバーの接続処理を毎回書いて、接続を管理するより、ライブラリを作ってまとめたい</li>
-  <li>複数の Federated Linda サーバーをデバッグするのは難しいので、スケーラブルなデバッグ方法を考えていく必要がある</li>
+  <li>本研究では、本研究室で開発しているマルチコア向け並列フレームワーク Cerium の新設計のアイディアを分散フレームワークに応用した。</li>
+  <li>実際に実装して、実験してみないと分からないことが多い。</li>
+  <li><strong>頑張って実装します。</strong></li>
+</ul>
+</div>
+
+<div class="slide">
+<h1>まとめと今後の課題</h1>
+<p class="subhead">実装に用いる言語の使い勝手</p>
+<ul>
+  <li><strong>Java, Scala</strong></li>
+  <ul>
+    <li>Java や Scala には、 java.util.concurrent などの並列処理用のライブラリが充実しているため、実装が比較的容易。</li>
+    <li>Scala は言語レベルで並列処理を記述できる。(Actor を使ったメッセージ交換)</li>
+  </ul>
+  <li><strong>CbC</strong></li>
+  <ul>
+    <li>本研究室で開発している CbC (引数付き goto による継続ベースのC言語拡張)を使えば、 goto で CodeSegment 同士の繋がりを記述できる。</li>
+    <li>しかし、並列処理サポートがまだなため、 TaskManager などの実行カーネルからまずは作らなくてはならない。</li>
+  </ul>
 </ul>
 </div>