BSP モデルにおけ る最適プロセッサ 台数の推移

BSP モデルにおけ る最適プロセッサ 台数の推移

2007 年 2 月 16 日 02-1-47-015

吉田　鉄哉

01/16/22 2

本研究の内容

BSP

モデル上でのソーティングアルゴリズム



パラメタ（通信時間、同期時間）が変化した際 の最適プロセッサ台数を求める。

検証方法



シミュレートプログラムの測定値



理論値

本研究の背景



並列計算処理の需要



並列アルゴリズムの必要性



並列計算モデルの必要性

01/16/22 4

BSP(Bulk-Synchronous Parallel) モデル



分散メモリ型



プロセッサ間

対

通信



バリア同期による同期

ネットワーク

プロセッサ メモリ

プロセッサ メモリ

プロセッサ メモリ

BSP モデルのパラメ タ

 p

: プロセッサ数

 L

: バリア同期時間

 g

: 通信コスト



内部計算に 1 時間



プロセッサ全体での同期に

時間



1 メッセージの送受信命令に

時

01/16/22 6

バリア同期

L

BSP アルゴリズムの 実行



粗粒度同期式：スーパーステップごとに同期



非一様コスト：通信は内部計算の

倍の時間

内部計算 通信

1 g

P _０ P _１ P _２

スーパーステップ

バイトニックソートアルゴリ ズム

 並列計算機上でマージソートを行うアルゴリズ ム

　　　　　図：マージソートの概念図

01/16/22 8

バイトニックソートアルゴ リズム



バイトニックソートの概念図

バイトニックソートアルゴ リズムの計算式

 T^I:

内部計算時間

 T^C:

通信時間

 T^S:

同期時間

 T^I=(nlogn+log²p)/p

 T =(gn/p) log p

最適プロセッサ台数

gn/p<L p<nlogn/L

gn/p>L p<gn/L

01/16/22 10

シミュレートプログラムにお

ける最適プロセッサ台数

シミュレートプログラムの測

定値

01/16/22 12

シミュレートプログラムの測

定値

最適なプロセッサ台数

　　 g=1 のとき、最適プロセッサ台数は以下のように なる

L p

0~27 256 台 28~57 128 台 57~110 64 台

01/16/22 14

同期時間と実行時間の関係

シミュレータと理論値の比較

01/16/22 16

実行時間の比較

実行時間の比較

01/16/22 18

実行時間の比較

考察

の値が大きい場合で以下の場合はシミュ レータの実行結果のほうが遅い

 ( 1<p ≤ 4)

の場合

 (p8,n16)

以外の

の場合

　それ以外の場合で

が大きい場合は

の場

01/16/22 20

結論および今後の課題



現行のシミュレータプログラムからの最適 プロセッサの割り出しが可能であるため、

本研究で求めたプロセッサ台数を用いるこ とにより効率よくソーティングを行える。



シミュレータと理論値の実行結果の値にず

れがあるためこのずれを解消できるシミュ

レータを作ることが今後の課題。