Download presentation
Presentation is loading. Please wait.
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 L 通信時間 g
7
MST(Minimum Spanning Tree)
V4 V6 V2 V5 V3 V1 3 1 5 4 2 7 6 V4 1 5 V5 V3 2 4 3 V6 V1 V2
8
Sollinのアルゴリズム (1). 最小値演算 V4 V6 V2 V5 V3 V1 3 1 5 4 2 7 6
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 プロセッサ
Similar presentations
© 2025 slidesplayer.net Inc.
All rights reserved.