view presen/index.html @ 11:57b1c4692d21

minor change
author sugi
date Wed, 24 Apr 2013 13:34:58 +0900
parents 5c57e35e19b6
children 85b22f56ef00
line wrap: on
line source

<!--
Google IO 2012/2013 HTML5 Slide Template

Authors: Eric Bidelman <ebidel@gmail.com>
         Luke Mahé <lukem@google.com>

URL: https://code.google.com/p/io-2012-slides
-->
<!DOCTYPE html>
<html>
<head>
  <title></title>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="chrome=1">
  <!--<meta name="viewport" content="width=device-width, initial-scale=1.0, minimum-scale=1.0">-->
  <!--<meta name="viewport" content="width=device-width, initial-scale=1.0">-->
  <!--This one seems to work all the time, but really small on ipad-->
  <!--<meta name="viewport" content="initial-scale=0.4">-->
  <meta name="apple-mobile-web-app-capable" content="yes">
  <link rel="stylesheet" media="all" href="theme/css/default.css">
  <link rel="stylesheet" media="only screen and (max-device-width: 480px)" href="theme/css/phone.css">
  <base target="_blank"> <!-- This amazingness opens all links in a new tab. -->
  <script data-main="js/slides" src="js/require-1.0.8.min.js"></script>
</head>
<body style="opacity: 0">

<slides class="layout-widescreen">

  <slide class="title-slide segue nobackground">
    <!--<aside class="gdbar"><img src="images/google_developers_icon_128.png"></aside>
    The content of this hgroup is replaced programmatically through the slide_config.json. -->
    <hgroup>
      <h1 data-config-title><!-- populated from slide_config.json --></h1>
      <h2 data-config-subtitle><!-- populated from slide_config.json --></h2>
      <p data-config-presenter><!-- populated from slide_config.json --></p>
    </hgroup>
  </slide>

  <slide>
    <hgroup>
      <h2>研究背景</h2>
    </hgroup>
    <article>
      <ul>
        <li>分散プログラムには信頼性とスケーラビリティが必要である</li>
        <li>しかし、両方を兼ね備えたプログラムを作成することは容易ではない</li>
        <li>そこで、当研究室では信頼性とスケーラビリティの両方をもったプログラムの記述をサポートする、分散フレームワークAliceを開発を行なっている</li>
        <li>Aliceはデータとタスクを細かく分割したDataSegment、CodeSegmentでプログラム記述する</li>
        <li>DataSegment、CodeSegmentで記述することにより高い並列処理を行うことができる</li>
        <li>Aliceの並列性能を確認するためbitonic Sortを実装したが、実行速度に問題があったため、
	  本論文では実行速度の改善を試みた</li>
      </ul>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>分散ネットフレームワーク Alice</h2>
    </hgroup>
    <article>
      <ul>
	<li>本研究室で開発を行なっている分散管理フレームワーク</li>
	<li>Data SegmentとCodeSegmentによりプログラムを記述する</li>
	<li>並列フレームワーク Ceriumに似たタスク管理機構と先行研究であるFederated Lindaに似たData Segmentの通信構造をもつ</li>
	<li>メニーコアのマシンが主流である背景からSEDA Architectureが採用している</li>
      </ul>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>Data Segment</h2>
    </hgroup>
    <article>
      <p>Data Segmentは数値や文字列を構造体的に保持する。<br>
	Aliceではデータベース的に扱うが、通常とは異なりKey毎にQueueを持つ<br>
	以下のAPIでデータの送受信を行う</p>
      <ul>
	<li>put</li>
	<li>update</li>
	<li>peek</li>
	<li>take</li>
      </ul>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>put</h2>
    </hgroup>
    <article>
      <ul>
      </ul>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>update</h2>
    </hgroup>
    <article>
      <ul>
      </ul>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>peek</h2>
    </hgroup>
    <article>
      <ul>
      </ul>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>take</h2>
    </hgroup>
    <article>
      <ul>
      </ul>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>Code Segment</h2>
    </hgroup>
    <article>
      <ul>
      <li>AliceではCode Segmentと呼ばれる単位でタスクを生成する</li>
      <li>Code Segmentは依存するData Segmentが全て揃うとActiveになる</li>
      <li>Input/Output Data SegmentがCode Segment間の依存関係を自動的に記述する</li>
      </ul>
    </article>
  </slide>


  <slide>
    <hgroup>
      <h2>実行速度の問題</h2>
    </hgroup>
    <article>
      <p>Aliceは先行研究であるFederated Lindaよりも処理速度が遅い。<br>
	作成した例題によりOverHeadの原因が見つかっている</p>
      <ul>
	<li>Message Packによる型変換</li>
	<li>SEDA Architecture</li>
	<li>Output Data Segmentの作成時のコピー</li>
      </ul>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>Message Pack</h2>
    </hgroup>
    <article>
      <p>シリアライズライブラリの一種。<br>
	シリアライズされたデータにオブジェクトの型情報を併せて埋め込むため、<br>
	IDL(インターフェース定義ファイル)を用意する必要がない。<br>
	異なる言語間でオブジェクトを交換可能<br>
	MessagePack for Java のVersion 0.6からValue型が追加されており、<br>オブジェクトを動的型付け可能</p>
      <ul>
	<li>MessagePackを使用することで他のノードとData Segmentの送受信が高速に行うことができる</li>
        <li>AliceはData SegmentをQueueに追加する際にValue型に変換</li>
        <li>アノテーションをつけることにより既存のData Segmentと互換性を保ったまま拡張することができる</li>
      </ul>
    </article>
  </slide>


  <slide>
    <hgroup>
      <h2>Message Packの問題</h2>
    </hgroup>
    <article>
      <p>分散プログラムにおいて、常にVersionが同じとは限らない。<br>
	旧Versionとの互換性のため、Value型に変換している。<br>
	しかし、追加するタイミングで変換を行うと、外部と通信を行わない<br>
	DataSegmentに対しても型変換を行う</p>
      Sortなどの配列をValue型に変換する場合は要素の数が増えるほど、<br>
      変換する時間が増加する。
      <ul>
      </ul>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>SEDA Architecture</h2>
    </hgroup>
    <article>
      <p>マルチコアを活かすためにAliceではSEDA Architectureを採用している。
	<br>SEDAとはマルチコアスレッドを用いて大量の接続を管理し、<br>
	データを処理毎に分けられたステージと呼ばれるスレッドで処理を行う。</p>
	Aliceでは
      <ul>
	<li>putやtakeなどの要求に沿ったCommandを作成するステージ</li>
	<li>Commandを処理するステージ</li>
	<li>DataSegmentをCodeSegmentにセットするステージ</li>

      </ul>
	の3つのステージで構成されている。
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>SEDAの問題点</h2>
    </hgroup>
    <article>
      <p>SEDAは多段のパイプラインによって構成されるためレスポンスが遅れる。<br>
	スループット重視の実装であるため、レスポンスが要求される<br>
	Sortのようなプログラムに向いていない。<br>
	非力なマシーンでは、スレッドを切り替えが頻繁に起こり、<br>
	レスポンスを下げる要因になる。</p>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>LinkedBlockingQueue</h2>
    </hgroup>
    <article>
      <p>SEDA Architectureを実装するにあたり、LinkedBlockingQueueを使用している。</p>
      特徴として
      <ul>
	<li>LinkedBlockingQueueは片方向の連結リストを使用したQueue</li>
	<li>enqueue/dequeueの操作時は排他制御は別々のlockで管理</li>
	<li>enqueueとdequeueの操作を並列に行うことが可能(スループットに優れている)</li>
      </ul>
      ただし、enqueue時にNodeオブジェクトの生成操作が発生するため、<br>
      enqueue操作の処理コストが特に高い。
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>Output Data Segment作成時のコピー</h2>
    </hgroup>
    <article>
      CodeSegmentはDataSegmentを取得するとActiveになる。<br>
      取得されたDataSegmentはCodeSegmentによって変更され、<br>
      Output Data Segmentとして出力される。<br>
      この際、変更されたDataSegmentをコピーし、新しくDataSegmentを作成する。<br>
      このコピーにかかる時間がオーバーヘッドとなっている。
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>問題に対する改善案</h2>
    </hgroup>
    <article>
      <ul>
	<li>MessagePack</li>
	MessagePackによるValue型に変換が必要なケースは、<br>
	他のノードに対してData Segmentを送信する場合である。<br>
	DataSegmentを追加するタイミングでValue型に変換せず、<br>
	メッセージを送信する前に変換を行えばよい。
	<p></p>
	<li>SEDA Architecture</li>
	Sortのようなにレスポンスが必要なプログラムのために、SEDAのステージ上ではなく、
	直接DataSegmentを取得するAPIを用意する
	<p></p>
      </ul>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>問題に対する改善案</h2>
    </hgroup>
    <article>
      <ul>
	<li>Output Data Segment作成時におけるコピー</li>
	Ceriumでも同様なコピーの問題があり、Input Data SegmentとOutput Data Segmentを
	Swapすることで解決している。Aliceでも同様の方法で解決する。<br>
	Data SegmentはCode Segment内ではReceiverという変数が保持している。<br>
	このReceiverをOutput Data Segmentにすることで無駄なコピーを減らす。
      </ul>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>検証</h2>
    </hgroup>
    
    <article>
     <h3>実験環境</h3>
      <table>
        <tr>
          <td>CPU</td><td>Intel(R) Xeon(R) X5650 @2.67GHz</td>
        </tr>
        <tr>
          <td>物理コア数</td><td>12</td>
        </tr>
        <tr>
          <td>論理コア数</td><td>24</td>
        </tr>
        <tr>
          <td>CPU キャッシュ</td><td>12MB</td>
        </tr>
        <tr>
          <td>Memory</td><td>16GB</td>
        </tr>
      </table>
      <p></p>
      SEDAを活かせるようにメニコア上でテストを行なった。
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>実験概要</h2>
    </hgroup>
    <article>
      <p>今回行った改善による効果を調べるために3つの実験を行った。</p>
      <ul>
	<li>SEDAの有無</li>
	<p>Data Segmentを取得するCode Segmentが10000回実行されるまでの時間を測定</p>
	<li>flipとputの比較</li>
	<p>既存のAPIの<em>put</em>と新しく追加したAPIである<em>flip</em>をつかい10000回、Data Segmentを追加されるまでの時間を測定</p>
	<li>Bitonic Sortによる比較</li>
	<p>今回行った改善(ただし、MessagePackによる改善を除く)
	  Bitonic Sortで100万の要素をSortされるまでの時間を測定する。分割数は10個で行った</p>
      </ul>
    </article>
  </slide>


  <slide>
    <hgroup>
      <h2>実験結果</h2>
    </hgroup>
    <article>
      <p>実験結果は100回行った平均である</p>
      <ul>
      <table>
        <tr>
          <th>SEDA</th><th>あり</th><th>なし</th>
        </tr>
        <tr>
          <td>実行時間(ms)</td><td>27.72</td><td>7.53</td>
        </tr>
      </table>
      </ul>
      <ul>
      <table>
        <tr>
          <th>API</th><th>flip</th><th>put</th>
        </tr>
        <tr>
          <td>実行時間(ms)</td><td>61.12</td><td>65.24</td>
        </tr>
      </table>
      </ul>
      <ul>
      <table>
        <tr>
          <th></th><th>改善前</th><th>改善後</th>
        </tr>
        <tr>
          <td>実行時間(ms)</td><td>199.38</td><td>184.64</td>
        </tr>
      </table>
      Bitonic Sortの例題では約10%程度改善された
      </ul>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>まとめ</h2>
    </hgroup>
    <article>
      <ul>
	<li>今回行った改善により、以前のAliceよりも約10%程度速度が改善した</li>
	<li>しかし、Aliceに要求される速度は、少なくともシングルスレッドで書かれたプログラムと同じ程度</li>
	<li>分散環境下ではFederated Linda以上の速度が求められる</li>
	<li>また、Aliceが抱える問題は速度だけではない</li>
	<li>信頼性の問題や永続性の問題についても改善をしなければならない</li>
      </ul>
    </article>
  </slide>

  <slide>
    <hgroup>
      <h2>Message Packの型変換にかかる時間</h2>
    </hgroup>
    <article>
      <ul>
      </ul>
    </article>
  </slide>
  <slide class="backdrop"></slide>

</slides>

<script>
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-XXXXXXXX-1']);
_gaq.push(['_trackPageview']);

(function() {
  var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
  ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
  var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
</script>

<!--[if IE]>
  <script src="http://ajax.googleapis.com/ajax/libs/chrome-frame/1/CFInstall.min.js"></script>
  <script>CFInstall.check({mode: 'overlay'});</script>
<![endif]-->
</body>
</html>