BSPモデルにおける 最適プロセッサ台数 の推移 2007年2月16日 02-1-47-015 吉田 鉄哉 情報論理工学研究室 2015/10/1 1 本研究の内容 BSPモデル上でのソーティングアルゴリズム パラメタ（通信時間、同期時間）が変化した際の最 適プロセッサ台数を求める。 検証方法 シミュレートプログラムの測定値 理論値 2015/10/1 2 本研究の背景 2015/10/1 並列計算処理の需要 並列アルゴリズムの必要性 並列計算モデルの必要性 3 BSP(Bulk-Synchronous Parallel)モデル ネットワーク メモリ メモリ プロセッサ プロセッサ メモリ プロセッサ 分散メモリ型 プロセッサ間1対1通信 バリア同期による同期 2015/10/1 4 BSPモデルのパラメタ p : プロセッサ数 L : バリア同期時間 g : 通信コスト 内部計算に1時間 プロセッサ全体での同期にL時間 1メッセージの送受信命令にg時間 2015/10/1 5 BSPアルゴリズムの実行 粗粒度同期式：スーパーステップごとに同期 非一様コスト：通信は内部計算のg倍の時間 バリア同期 P０ P１ P２ スーパーステップ 内部計算 2015/10/1 1 g L 通信 6 バイトニックソートアルゴリズム 2015/10/1 並列計算機上でマージソートを行うアルゴリズム 図：マージソートの概念図 7 バイトニックソートアルゴリズム 2015/10/1 バイトニックソートの概念図 8 バイトニックソートアルゴリズム の計算式 2015/10/1 TI:内部計算時間 TC:通信時間 TS:同期時間 2 TI=(nlogn+log p)/p 2 TC=(gn/p) log p 2 TS=L log p T= TI+ TC+TS 最適プロセッサ台数 gn/p<L p<nlogn/L gn/p>L p<gn/L 9 シミュレートプログラムにおける 最適プロセッサ台数 2015/10/1 10 シミュレートプログラムの測定値 2015/10/1 11 シミュレートプログラムの測定値 2015/10/1 12 最適なプロセッサ台数 g=1のとき、最適プロセッサ台数は以下のようになる L 0~27 28~57 57~110 111~148 148~ 2015/10/1 p 256台 128台 64台 32台 1台 13 同期時間と実行時間の関係 2015/10/1 14 シミュレータと理論値の比較 2015/10/1 15 実行時間の比較 2015/10/1 16 実行時間の比較 2015/10/1 17 実行時間の比較 2015/10/1 18 考察 g,Lの値が大きい場合で以下の場合はシミュレータ の実行結果のほうが遅い ( 1<p ≤ 4)の場合 (p8,n16)以外のp8の場合 それ以外の場合でg,Lが大きい場合はp1の場合を 除きシミュレータの実行結果のほうが速い 2015/10/1 19 結論および今後の課題 2015/10/1 現行のシミュレータプログラムからの最適プロ セッサの割り出しが可能であるため、本研究で 求めたプロセッサ台数を用いることにより効率よ くソーティングを行える。 シミュレータと理論値の実行結果の値にずれが あるためこのずれを解消できるシミュレータを作 ることが今後の課題。 20
© Copyright 2024 ExpyDoc
