-title: CodeSegmentとDataSegmentによるプログラミング手法

--author: 河野 真治, 杉本 優

--並列分散フレームワーク

本研究室では分散プログラミングと並列プログラミングのツールを開発してきた。

    分散プログラミング用のFederated Lidna
    並列プログラミング用のCerium

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

そこで、

    data segment と code segment で書くというのを考えた
    Java で実装して評価した

--並列分散フレームワークには何が求められるのか

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

--Federated Linda 

データの塊である Tuple を使って通信するフレームワーク

   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

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

    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

	  AliceとFederated Linda で性能比較を行った。
	  Ring型のトポロジーを構成、メッセージが100周する時間を計測。
	  1周あたりの平均時間を求めた。
<center><img src="images/ringTest.png"></center>

	  パケットのサイズは10byte,10Kbyte,100kbtyeで実験

--何故 Ring?

なぜ、不利なベンチマークを取るのか?

SEDA でレスポンスをはかっちゃだめだろう?

SEDA はCPU食い。Core Duo とかで全然ダメ。

なので、Core i7 を用意しました。

<table style="font:Osaka;text-align:right;" border="2" >
<tr>
<td>マシン台数</td>
<td>8台</td>
</tr>
<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>132GB</td>
</tr>
</table>


--実験結果 小さいデータ

<strong>10byte</strong>
<center><img src="images/ring10B.png"></center>

Single threaded な Federated Linda に負けている

--実験結果 大きなデータ

<strong>100kbyte</strong>
<center><img src="images/ring100KB.png"></center>
	  データ量が増えると差が縮まっている。これはここの通信の手間の影響が大きことを示している。
      

--実験結果 スレッドプールなし

スレッドプールを使わないほうが、Ringの結果は良い<
<center><img src="images/notp.png"></center>


--わかりやすい記述になったのか?

Input DS と Output DS の記述が対称にならない

CS/DS の関係を CS 内部に書くのはダメな戦略?


--評価と考察
<p><strong>MessagePack</strong></p>
<ul>
<li>今回の実装では単純なMessageの転送時にもMessagePackのdecode/encodeをしているが、overheadになってしまうため、decode/encode抜きに直接操作できるほうが望ましい</li>
<li>Data Segmentの一部の修正をするたびにData Segmentが再構成されているがこれは望ましくない</li>
<li>AliceもCeriumのようにInput Data SegmentとOutput Data SegmentをswapするAPIがあるとよいと思われる</li>
</ul>


--評価と考察
<p><strong>Key</strong></p>
<ul>
<li>分散実装においてはData Segmentの相互参照はKey経由が打倒であるが、並列実装では全てのData SegmentをKey Value Storeに格納するのは、性能的な問題を引き起こす</li>
<li>分散記述と並列記述を分ければ解決するが、2つの記述がかけ離れるのは好ましくない</li>
<li>本来Key Value storeは持続性を持たせる必要がある</li>
</ul>

--評価と考察
<p><strong>Java</strong></p>
<ul>
<li>Data SegmentはCode Segmentがactiveの時のみメモリ上にあり、その最大値はActive Taskの量を見積もればよいのでAliceにGarbage Collectionの機能は必要ない</li>
<li>key Value Store 上のデータは決してGarbage Collectionの対象にはならないが、それがGarbage Collectionに負荷をかける結果となるためAliceとJavaの相性は悪い</li>
</ul>

--評価と考察
<p><strong>拡張性</strong></p>
<ul>
<li>分散アプリケーションのプロトコルは常に変更されるため、Aliceもそれに対応する必要がある</li>
<li>Keyとトポロジーマネージャーをプロトコル毎に別に用意すれば複数のプロトコルを同時に走らせることが可能</li>
<li>Data SegmentとCode Segmentの結びつきは弱いため、Data Segmentに余計な値がある場合、値が足りない場合に適切な値を設定することで古いCode Segmentを変更するとこなしにプロトコルを拡張できる</li>
</ul>

--まとめと課題
<ul>
<p>今回Code SegmentとData Segmentによる並列分散フレームワークのJavaによる実装を示した。実装でしかえられない知見を得ることができた。</p>
<p>今回Javaによる実装を行ったがJavaがAliceの実装に不向きであるということもわかった。</p>
<p>
<li>Code Segment/Data Segmentを見たコンパイラ的アプローチ</li>
<li>実行時最適化</li>
<li>CbCによる実装</li>
	  などが有効、効果的だと思われる。</p>
<p>今回はノード内の並列実行やGPGPUによる並列実行などは考慮していない。将来的にそれを含め実装をしていきたい。</p>
</ul>