Mercurial > hg > Papers > 2011 > kazz-jssst

view presen/index.html @ 18:21c68d67d7a5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
presen finish
author kazz <kazz@cr.ie.u-ryukyu.ac.jp>
date Tue, 27 Sep 2011 15:27:47 +0900
parents 1ad07d67472f
children
line wrap: on
line source

<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<title>DataSegment API を用いた分散フレームワークの設計</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="copyright" content="Copyright &#169; 2010 Kazuki AKAMINE" />
<meta name="font-size-adjustment" content="-1" />
<link rel="stylesheet" href="./res/w3c-blue2.css"
 type="text/css" media="screen, projection, print" />
<script src="./res/slidy.js" type="text/javascript">
</script>
</head>
<body>
<!-- this defines the slide background -->

<div class="background">
  <div class="header">
  <!-- sized and colored via CSS -->
  </div>
  <!-- hidden style graphics to ensure they are saved with other content -->
  <img class="hidden" src="./res/bullet.png" alt="" />
  <img class="hidden" src="./res/fold.bmp" alt="" />
  <img class="hidden" src="./res/unfold.bmp" alt="" />
  <img class="hidden" src="./res/fold-dim.bmp" alt="" />
  <img class="hidden" src="./res/nofold-dim.bmp" alt="" />
  <img class="hidden" src="./res/unfold-dim.bmp" alt="" />
  <img class="hidden" src="./res/bullet-fold.gif" alt="" />
  <img class="hidden" src="./res/bullet-unfold.gif" alt="" />
  <img class="hidden" src="./res/bullet-fold-dim.gif" alt="" />
  <img class="hidden" src="./res/bullet-nofold-dim.gif" alt="" />
  <img class="hidden" src="./res/bullet-unfold-dim.gif" alt="" />

  <div class="footer">
  <!-- modify the following text as appropriate -->
  Presentation Name<br />
  Event, Location, Month Year
  </div>
</div>

<div class="slide cover">
<div class="header">
<div class="block">
<h1>DataSegment API を用いた分散フレームワークの設計</h1>
<div class="name">琉球大学理工学研究科 情報工学専攻 並列信頼研 M2 赤嶺一樹</div>
</div>
</div>
</div>

<div class="slide">
<h1>研究目的</h1>
<p class="subhead">スケーラブルな分散プログラミングモデルの提案</p>
<ul>
  <li>ブロードバンド環境やモバイル端末の普及により、ネットワーク上におけるサービスの巨大化は必至である</li>
  <li>スケーラビリティ(サービスの大きさが増えてもリソースの追加のみでサービスの質を維持できること)を備えたプログラムを作成するためには、いろいろなプロトコルを提案し、実装し、検証していく必要がある</li>
  <li>提案したプロトコルを<strong>シンプルに</strong>実験できるフレームワークが求められている</li>
</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>
  <li>このフレームワークを設計するにあたって、 Federated Linda の実装から得られた見地が非常に役立った。</li>
  <li>まず、 Federated Linda について紹介する。</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">Federated Linda とは</p>
<div style="float: left; width: 55%;">
<ul>
  <li>本研究室では、分散フレームワーク Federated Linda の開発を行なってきた。</li>
  <li>当初、並列言語 Linda を用いてアクセスできる Tuplespace を実装し、ネットワークゲームの通信ライブラリとして使用して来た。</li>
  <li>それでは、クライアントが増えれば増えるほど通信がサーバー側に一極集中するため、スケールアウトできないという問題が発生した。</li>
</ul>
</div>
<img src="img/game.png" style="display: block; margin-right: 5%; width: 40%; float: right;" />
</div>

<div class="slide">
<h1>Federated Linda</h1>
<p class="subhead">Linda とは</p>
<div style="float: left; margin-left: 2em; width: 59%;">
<p>
Linda は、以下のAPIを用いてタプルスペース上のデータの更新を行う。
</p>
<table>
  <tr>
    <th>in(id)</th>
    <td>データをタプルから取り出す<br>タプルにデータは残らない</td>
  </tr>
  <tr>
    <th>rd(id)</th>
    <td>データをタプルから取り出す<br>タプルにデータが残る</td>
  </tr>
  <tr>
    <th>out(id,data)</th>
    <td>データをタプルへ書き込む</td>
  </tr>
</table>
</div>
<img src="./img/linda_server.png" style="display: block; width: 27%; margin-right: 10%; float: right;"/>
</div>

<div class="slide">
<h1>Federated Linda</h1>
<p class="subhead">Federated Linda とは</p>
<div style="display: block; float: left; width: 60%;">
<p>
タプルスペースを複数個つなげて、タプルの伝搬を基にデータを共有するモデルである。
</p>
<ul>
  <li>タプルスペース間には データの伝搬などを管理する Protocol Engine と呼ばれるプログラムが存在</li>
  <li>しかしタプルスペースと Protocol Engine は別プロセスであるため、同一サーバー上であってもソケットによる接続が必要だった。
</li>
</ul>
</div>
<img src="./img/prefedlinda.png" style="display: block; width: 37%; margin: auto; float: right; margin-right: 3%; margin-top: 2%;"/>
</div>

<div class="slide">
<h1>Federated Linda</h1>
<p class="subhead">Meta Engine とは</p>
<div style="display: block; float: left; width: 60%;">
<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%;"/>
</div>

<div class="slide">
<h1>Federated Linda の問題点</h1>
<p class="subhead">分散アプリケーションの3大構成要素</p>
<div style="display: block; float: left; width: 90%;">
<ul>
  <li><strong>Configuration</strong></li>
  <ul>
    <li>各ノードの接続やルーティングを行う</li>
  </ul>
  <li><strong>Protocol Engine</strong></li>
  <ul>
    <li>Database へアクセスし、他のノードにデータを伝搬する</li>
  </ul>
  <li><strong>Database</strong></li>
  <ul>
    <li>通信した内容や計算結果などの各種データの保存領域</li>
  </ul>
</ul>
<ul>
  <li>しかし、 Federated Linda では Configuration も Protocol Engine 内で記述する必要があった。</li>
  <li><strong>Protocol Engine の複雑化を招いていた</strong></li>
</ul>
</div>
</div>

<div class="slide">
<h1>Federated Linda の問題点</h1>
<p class="subhead">Protocol Engine の実行方法</p>
<ul>
  <li><strong>Polling based</strong></li>
  <ul>
    <li>メインループで定期的に Protocol Engine を実行し、 Tuplespace からデータを取得し、確認する。 </li>
    <li>通信が発生する度、記述した Tuple へのアクセスが発生する</li>
  </ul>
  <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>DataSegment API を用いた新設計</h1>
<p class="subhead">DataSegment の型</p>
<ul>
  <li>Federated Linda では、 Tuple の型は単なる byte[] であり、内部のデータ構造を自分で決める必要があった。</li>
  <ul>
    <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>DataSegment API を用いた新設計</h1>
<p class="subhead">DataSegment の表現</p>
<div style="float: left; width: 55%;">
<ul>
  <li>DataSegment はデータ型と ID で表現される。</li>
  <li>データ型は MessagePack で表現できる構造体の名前</li>
  <li>ID は <strong>GeoAddress</strong> と <strong>LocalAddress</strong> の2つの部分に分けて表現される。</li>
</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 の表現 - 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>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>

<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>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/remoteds.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>TaskManager に CodeSegment を登録する。</li>
  <li>TaskManager は必要な InputDataSegment が揃った CodeSegment を Executor に投げる。</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">競合的な DataSegment の書き出し</p>
<ul>
  <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>

<div class="slide">
<h1>まとめと今後の課題</h1>
<ul>
  <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>


<!-- <div class="slide"> -->
<!-- <h1>ご清聴ありがとうございました</h1> -->
<!-- <img src="./img/nadeko.png" style="display: block; width: 80%; margin: auto"/> -->
<!-- </div> -->

</body>
</html>