Mercurial > hg > Papers > 2011 > kazz-jssst

<?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>
</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>Protocol Engine の複雑化</li>
</ul>
</div>
</div>


<div class="slide">
<h1>Federated Linda を用いた設計</h1>
<p class="subhead">スケーラブルな分散プログラミングモデルの設計</p>
<ul>
  <li>複数のサーバーを接続することで負荷を分散する</li>
  <li>情報を取捨しながら伝搬する</li>
  <ul>
    <li>すべてのデータをレプリケーションする必要はない</li>
    <li>サーバーがクライアントの必要な情報とは何かを把握する</li>
  </ul>
</ul>
</div>


<div class="slide">
<h1>Meta Engine を用いた設計例</h1>
<p class="subhead">ツリー型トポロジーを用いた負荷分散</p>
<div style="display: block; float: left; width: 60%;">
<ul>
  <li>ツリー型トポロジーを用いて、負荷を分散する</li>
  <li>末端にクライアントを接続する</li>
  <li>末端のノードは、クライアントから受け取った座標情報をクライアントが必要か判断する</li>
  <ul>
    <li>必要ならば、その Linda サーバーのみで通信は完結</li>
    <li>必要でないなら、親に判断を委ねるため、親に伝搬</li>
  </ul>
  <li>伝搬された上位ノードは、子のノードが必要か判断し、子に伝搬するか、親に伝搬するかを決定する</li>
  <li><strong>データを必要としているマシンのみにデータを伝搬する</strong></li>
</ul>
</div>
<img src="./img/treetopology.png" style="display: block; width: 37%; margin: auto; float: right; margin-right: 3%; margin-top: 5%;"/>
</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>
</div>
</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>
</div>
<img src="./img/apiinout.png" style="display: block; width: 37%; margin: auto; float: right; margin-right: 3%; margin-top: 5%;"/>
</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>
</div>
<img src="./img/apiupdate.png" style="display: block; width: 37%; margin: auto; float: right; margin-right: 3%; margin-top: 5%;"/>
</div>

<div class="slide">
<h1>評価</h1>
<p class="subhead">update API の検証</p>
<div style="display: block; float: left; width: 60%;">
<ul>
  <li>update と in/out の双方を用いた場合で比較を行った</li>
  <li>それぞれの API で N 回の更新を行う処理を2台のマシンを用いて計測</li>
  <li><strong>update と in/out のどちらを用いても、処理速度に影響は見られない</strong></li>
  <li>大量のマシンを使ってアクセスを集中すると差が出たかもしれない。</li>
</ul>
</div>
<img src="./img/apigraph.png" style="display: block; width: 37%; margin: auto; float: right; margin-right: 3%; margin-top: 5%;"/>
</div>

<div class="slide">
<h1>評価</h1>
<p class="subhead">TCP No Delay の検証</p>
<div style="display: block; float: left; width: 60%;">
<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>
</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>
</ul>
</div>


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

</body>
</html>
author	kazz <kazz@cr.ie.u-ryukyu.ac.jp>
date	Mon, 26 Sep 2011 19:37:54 +0900
parents
children	1ad07d67472f