-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 がある
--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

--評価と考察

Key

--評価と考察

Java

--評価と考察

拡張性

--まとめと課題