BSP モデルを用いた 最小スパニング木

BSP モデルを用いた 最小スパニング木

情報論理工学研究室

０２－１－４７－１３４

小林洋亮

本研究の目的

BSP （ Bulk Synchronous Parallel) モデルを

用いて最小スパニング木問題を解く並列ア

ルゴリズムを提案する。

並列処理の必要性

 高速処理や大規模データ処理が必要

 逐次処理による計算が限界に近づきつ つある

 コンピュータ素子価格とサイズが下が っている

並列コンピュータが作りやすい

 並列アルゴリズムの設計・解析



並列計算モデル上で行う

 代表的な並列計算モデル



ＰＲＡＭモデル



ＢＳＰモデル

並列計算モデル

PRAM （ Parallel Random Access) モデル



共有記憶装置を持 っている



通信や同期を考慮 していない

ＰＲＡＭの実現は困

難

BSP(Bulk-Synchronous Parallel) モデル



局所メモリを持つ 複数のプロセッサ



プロセッサ間の 1 対１メッセージ通 信を行う完全結合 網



プロセッサ間の同

期を実現するため

の同期機構

BSP モデルの特性



p ：プロセッサ数

各プロセッサはプロセッ サ番号を持っている



g ：通信命令

送信命令または受信命令 の実行に必要な時間



L(>=g) ：バリア同 期

同期に必要な時間

最小スパニング木 (Minimum S

paning Tree:MST) 問題

ＭＳＴ問題に対する既知の結果 と本研究の結果

Prim Sollin 本研究

BSP モデル上での MST アル ゴリズム

B C

D E F

1

2 3

4 5

6

7

手続き find_parent, pointer_jump, data_collect, re

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

S

S

A,B,C,F S ⇒ ¹ D,E S ⇒ ²

find_parent,pointer_jump,data_collect,remake_graph を頂点が

A B

C

D E

F

4

最小スパニング木 (MST)

結果

Prim Sollin 本研究

結論

BSP モデル上で頂点の重み付き連結無向グラフＧ に対して n プロセッサを用いて

時間で最小スパニング木問題を解く



データの負荷分散を行うことにより、通信時 間を減らすことができる



より大きいプロセッサ数を用いて速い最小ス パニング問題を解く BSP モデル上の並列アル ゴリズム設計が今後の課題である。

) log

log

( ng n L

n

O 

ご清聴ありがとうございま

した