BSPモデル上でのMSTを作る 並列アルゴリズム

Similar presentations


Presentation on theme: "BSPモデル上でのMSTを作る 並列アルゴリズム"— Presentation transcript:

1 BSPモデル上でのMSTを作る 並列アルゴリズム
情報理論工学研究室 北脇真斗

2 あらまし 並列計算機モデル MST問題 Sollinのアルゴリズム 本研究で提案するアルゴリズム 結果 結論

3 並列計算モデル P1 P2 Pn BSP PRAM (Bulk-Synchronous Parallel)
(Parallel Random Access Machine)  ネットワーク 共有メモリ P1 P2 Pn P1 P2 Pn メモリ メモリ メモリ

4 PRAM上のアルゴリズムの実行 1 2 3 4 5 P1 P2 P3 P4 演算命令 メモリアクセス命令 入出力命令 同期

5 BSP上のアルゴリズムの実行 P0 P1 P2 スーパーステップ L 内部計算 通信 1 g

6 PRAMとBSPの比較 PRAM BSP 同期 1命令ごと スーパーステップごと 同期時間 1 通信時間

7 MST(Minimum Spanning Tree)
V4 V6 V2 V5 V3 V1 V4 V5 V3 V6 V1 V2

8 Sollinのアルゴリズム (1). 最小値演算 V4 V6 V2 V5 V3 V1

9 Sollinのアルゴリズム (2). ポインタジャンプ V4 V4 V5 V3 V5 V3 V6 V1 V2 V6 V1 V2

10 Sollinのアルゴリズム (3). 情報を根に集める V4 V1 V2 V3 V5 V6
データを送信したプロセッサは以降の処理の対象から外れる

11 本研究で提案するアルゴリズム (3-1).親が子に 通信相手を教える V4 V1 V2 V3 V5 V6

12 本研究で提案するアルゴリズム (3-2).教えられた相手と通信 V4 V5 V1 V6 V2 V3
データを送信したプロセッサは以降の処理の対象から外れる V4 V2 V1 各グループの親以外が残っている場合(3-1)へ

13 結果 各アルゴリズムの計算量 Sollin :O(n2 g + L log n) 時間 n プロセッサ

14 結果 シミュレートプログラムによって計測した内部計算時間

15 結果 シミュレートプログラムによって計測した通信時間

16 結果 シミュレートプログラムによって計測した同期時間

17 結論 提案した並列アルゴリズム O( ng + L log2 n) 時間 n プロセッサ BSPモデル上でMST問題を解く
通信時間が大きい環境でも高速 プロセッサ間で2分木構造による負荷分散 O( ng + L log2 n) 時間 n プロセッサ


Download ppt "BSPモデル上でのMSTを作る 並列アルゴリズム"

Similar presentations


Ads by Google