BSPモデルを用いた 最小スパニング木 情報論理工学研究室 ０２－１－４７－１３４ 小林洋亮
本研究の目的 BSP（Bulk Synchronous Parallel)モデルを用いて最小スパニング木問題を解く並列アルゴリズムを提案する。
並列処理の必要性 高速処理や大規模データ処理が必要 逐次処理による計算が限界に近づきつつある コンピュータ素子価格とサイズが下がっている 並列コンピュータが作りやすい
並列計算モデル 並列アルゴリズムの設計・解析 並列計算モデル上で行う 代表的な並列計算モデル ＰＲＡＭモデル ＢＳＰモデル
PRAM（Parallel Random Access)モデル 共有記憶装置を持っている 通信や同期を考慮していない ＰＲＡＭの実現は困難
BSP(Bulk-Synchronous Parallel)モデル 局所メモリを持つ複数のプロセッサ プロセッサ間の1対１メッセージ通信を行う完全結合網 プロセッサ間の同期を実現するための同期機構
BSPモデルの特性 p：プロセッサ数 g：通信命令 L(>=g)：バリア同期 各プロセッサはプロセッサ番号を持っている 送信命令または受信命令の実行に必要な時間 L(>=g)：バリア同期 同期に必要な時間
最小スパニング木(Minimum Spaning Tree:MST)問題
ＭＳＴ問題に対する既知の結果と本研究の結果 Prim Sollin 本研究
BSPモデル上でのMSTアルゴリズム A 1 6 5 B C 4 2 3 7 D E F 手続きfind_parent, pointer_jump, data_collect, remake_graph
find_parent A B C D E F
pointer_jump A B C D E F
Sollinのアルゴリズムのdata_collect 情報を根に集める 送信命令 A B C D E F
本研究で提案するアルゴリズムのdata_collect 親 ・・・・・・・・ 親 ・・・ 親 ・・・・・・・・ 親 親 ・・・・・・・・
remake_graph A,B,C,F⇒S1 D,E⇒S2 4 C 4 E D find_parent,pointer_jump,data_collect,remake_graphを頂点が １つになるまで繰り返す。
最小スパニング木(MST)
結果 Prim Sollin 本研究
結論 BSPモデル上で頂点の重み付き連結無向グラフＧ に対してnプロセッサを用いて 時間で最小スパニング木問題を解く データの負荷分散を行うことにより、通信時間を減らすことができる より大きいプロセッサ数を用いて速い最小スパニング問題を解くBSPモデル上の並列アルゴリズム設計が今後の課題である。
ご清聴ありがとうございました