CodeSegmentとDataSegmentによるプログラミング手法
河野 真治, 杉本 優
並列分散フレームワーク
本研究室では分散プログラミングと並列プログラミングのツールを開発してきた。
分散プログラミング用の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 がある
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である。
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 水族館の例題
複数の魚が複数のディスプレイ上を移動する。
魚のうち一匹はクライアントが操作することができる。
トポロジーはツリー状に構成してある。
CS/DS Java 版 Alice
Java で SEDA をしようして実装
MessagePack を使って Marshaling
SEDA
Thread pool を使ったパイプラインによるサーバ実装
応答よりもスループット重視
Experiment
- AliceとFederated Linda で性能比較を行った。
- Ring型のトポロジーを構成、メッセージが100周する時間を計測。
- 1周あたりの平均時間を求めた。
- パケットのサイズは10byte,10Kbyte,100kbtyeで実験
何故 Ring?
なぜ、不利なベンチマークを取るのか?
SEDA でレスポンスをはかっちゃだめだろう?
SEDA はCPU食い。Core Duo とかで全然ダメ。
なので、Core i7 を用意しました。
マシン台数 |
8台 |
CPU |
Intel(R) Xeon(R) X5650 @ 2.67GHz |
物理コア数 |
12 |
論理コア数 |
24 |
CPU キャッシュ |
12MB |
Memory |
132GB |
実験結果 小さいデータ
10byte
Single threaded な Federated Linda に負けている
実験結果 大きなデータ
100kbyte
- データ量が増えると差が縮まっている。これはここの通信の手間の影響が大きことを示している。
実験結果 スレッドプールなし
スレッドプールを使わないほうが、Ringの結果は良い<
わかりやすい記述になったのか?
Input DS と Output DS の記述が対称にならない
CS/DS の関係を CS 内部に書くのはダメな戦略?
評価と考察
MessagePack
- 今回の実装では単純なMessageの転送時にもMessagePackのdecode/encodeをしているが、overheadになってしまうため、decode/encode抜きに直接操作できるほうが望ましい
- Data Segmentの一部の修正をするたびにData Segmentが再構成されているがこれは望ましくない
- AliceもCeriumのようにInput Data SegmentとOutput Data SegmentをswapするAPIがあるとよいと思われる
評価と考察
Key
- 分散実装においてはData Segmentの相互参照はKey経由が打倒であるが、並列実装では全てのData SegmentをKey Value Storeに格納するのは、性能的な問題を引き起こす
- 分散記述と並列記述を分ければ解決するが、2つの記述がかけ離れるのは好ましくない
- 本来Key Value storeは持続性を持たせる必要がある
評価と考察
Java
- Data SegmentはCode Segmentがactiveの時のみメモリ上にあり、その最大値はActive Taskの量を見積もればよいのでAliceにGarbage Collectionの機能は必要ない
- key Value Store 上のデータは決してGarbage Collectionの対象にはならないが、それがGarbage Collectionに負荷をかける結果となるためAliceとJavaの相性は悪い
評価と考察
拡張性
- 分散アプリケーションのプロトコルは常に変更されるため、Aliceもそれに対応する必要がある
- Keyとトポロジーマネージャーをプロトコル毎に別に用意すれば複数のプロトコルを同時に走らせることが可能
- Data SegmentとCode Segmentの結びつきは弱いため、Data Segmentに余計な値がある場合、値が足りない場合に適切な値を設定することで古いCode Segmentを変更するとこなしにプロトコルを拡張できる
まとめと課題
今回Code SegmentとData Segmentによる並列分散フレームワークのJavaによる実装を示した。実装でしかえられない知見を得ることができた。
今回Javaによる実装を行ったがJavaがAliceの実装に不向きであるということもわかった。
- Code Segment/Data Segmentを見たコンパイラ的アプローチ
- 実行時最適化
- CbCによる実装