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