自動取得したネットワークの構成情報に基づく
MPI集合通信アルゴリズムの改良
電子情報工学科
近山・田浦研究室
吉富 翔太
背景

Gridコンピューティングの発展




MPIを用いた大規模な計算
計算処理の高速化
計算処理中の通信時間をなるべく減らす工夫
特にGrid環境での集合通信の性能向上が不可欠

複数のノード間でデータ通信を行う


Broadcast データを全体に分配する
Gather
データを全体から集約する
etc
背景

Grid環境を考慮したMPIのライブラリと集合通信



WAN,LANのような遅延の大きく異なるネットワークでは異なる
アルゴリズムを用いる
リンクのバンド幅を最大限利用するように通信するノード数を制
御する
問題点


WANやLANなどの線引きをネットワークの設定に頼っている
→ 事前に手動で設定する必要あり
ノードとスイッチの接続関係のような,ネットワークトポロジーを
考慮しないものが多い
本研究の目的

自動的に取得したネットワークの構成情報を利用した集
合通信モデルの設計

ネットワークの構造に基づく効率の良い集合通信の実現




遅延の大きいノード間の通信回数を抑制
スイッチ間やクラスタ間の一本のリンク介して,同時に多数の
ノードが多量の通信することを避ける.
自動で線引き
ユーザ側は使用するネットワーク構造に関する知識や,
設定を必要としない.
発表の流れ





背景と目的
関連研究
提案手法
実験と評価
まとめ
関連研究
Grid環境に適応した集合通信に対するアプローチ

MagPIe [Kielmann et al. 1999]



遅延の大きいリンクでの通信を極力減ら
す
WANとLANで異なる集合通信のアルゴ
リズム
クラスタ 間
は1ノードの
み通信
高バンド幅ネットワークでの集合通信
[松田 et al. 2006]


WANとLANで異なる集合通信のアルゴ
リズム
一度に複数のノードがクラスタをまたい
で通信することで,クラスタ間リンクのバ
ンド幅を最大限利用する
クラスタ 間で
複数ノードが
まとめて通信
関連研究
トポロジー情報を短時間で取得するためのアプローチ
高速なトポロジー推定法 [白井 et al. 2007]


1.
2.
取得できるもの
計算ノード及びスイッチがどのようにつながりあい,
階層構造を成しているかというネットワークのトポロジー
任意のノードとノードの間のリンクの遅延
提案する集合通信モデルの概要

集合通信実行前にネットワークの情報を自動取得
(高速なトポロジー推定の方法による)


任意のノード間の遅延
ノードとノードの接続関係

ネットワークの情報を元に最適な集合通信のアルゴ
リズムを選択・実行する

全ての集合通信は,基本的な集合通信のアルゴリズ
ムの組み合わせにより実現する
提案する集合通信モデルの概要
実装する集合通信

7種類の集合通信について
モデルを設計





Broadcast
Scatter
Gather
Reduce



Allgather
Allreduce
Alltoall
(ex) Broadcast



1対全通信
1つのノードが他の全ノード
に対してデータを送信する
全体全通信


(ex) Allreduce
全てのノードが自身を除く全
ノードからのデータを受信し,
そのデータに演算を行う.
提案する集合通信モデルの概要
基本的な集合通信のアルゴリズム

基本的な集合通信の
アルゴリズム









Binomial tree
Flat tree
Ring
Recursive Doubling
Recursive Halving
Binary Blocks
Bruck
Van de Geijn algorithm
Rabenseifner algorithm
• ネットワーク環境
• 通信されるデータサイ
ズ
により適するアルゴリズムが異なる
×
ネットワーク情報
の手動設定
自動取得した
ネットワーク情報
ネットワークや通信の条件に応じて
• 適切なアルゴリズムを選択
• 複数のアルゴリズムを複合
単一のアルゴリズムのみを使用する
よりも高いパフォーマンスを実現
一対全通信を行う集合通信

Broadcast




Binomial tree
Flat tree
Van de Geijn
(Scatter + Allgather)
Scatter



Reduce


Gather



Binomial tree
Flat tree
Binomial tree
Flat tree

Binomial tree
Flat tree
Rabenseifner
(Reduce_Scatter+Gather)
基本アルゴリズムの組み合わせにより集合通信を実現
一対全通信を行う集合通信
例:Broadcastのツリー構築
既にデータ受信済みのノードの集合
20 50
10
40 60 20
経過見積時間
構築されるツリー構造
root
10 30
30 2010
70
80 20
60
90
60
通信見積時間
経過見積時間
データを受信していないノードの集合
このツリーに沿ってデータを通信
一対全通信を行う集合通信
例:Broadcastのツリー構築


対照的な例
ノード間通信時間が通信の
オーバーヘッドと大きく違わ
ない場合
root
深さを持ったツリー
Binomial tree

通信のオーバーヘッドよりも通信
時間が非常に大きい場合
root
平坦なツリー
Flat tree
全体全通信を行う集合通信

Allgather






Recursive Doubling
Bruck
Flat tree
Ring
Allreduce




Recursive Doubling
Bruck
Flat tree
Ring
Alltoall



Bruck
Flat tree
Ring
基本アルゴリズムの組み合わせにより集合通信を実現
全体全通信を行う集合通信
アルゴリズムの選択

グループ


ノード
同じスイッチに接続されてい
るノードの集合
グループに対するアルゴリズ
ムの選択と実行


スイッチ
それぞれのグループに対して,
ネットワークの情報と通信
データサイズを考慮してもっと
も効率が良いと思われるアル
ゴリズムを選択して実行
グループ間での通信を同様に
アルゴリズムを選択して実行
グループA
グループB
アルゴリズムC
アルゴリズムA
アルゴリズムB
実装と実験

提案手法を7つの集合通信全てについて実装



最適となるものがネットワークの環境により異なる
基本アルゴリズムの組み合わせで集合通信を設計
組み合わせの選択基準として,自動的に取得した
ネットワークトポロジー&遅延の情報を用いる
実験

いくつかの代表的な集合通信について,
ネットワーク環境を変えて実行時間の性能評価
実験:1クラスタ内の性能比較

通信するデータ長は32byteと256KBの2通り
実行ノード数を変化させてBroadcastの実行時間を計測

比較対象



本手法
Binomial tree (hostname)


ホスト名順にBinomial treeを構築してBroadcast
Binomial tree (random)

完全にランダムにrankを割り当て,Binomial treeでBroadcast
実験:1クラスタ内での性能比較
Broadcast
256KB
32byte
400
Random
0.6
0.4
0.2
MagPIe
実行時間(ms)
実行時間(ms)
0.8
300
200
100
OURS
0
0
0
20
40
ノード数
60
80
0
20
40
ノード数
60
80
実験:Grid環境での性能比較



6クラスタ230ノードを用いた集合通信の性能測定
通信されるデータサイズを様々に変化させて実行時間を比較
比較対象


本手法
MagPIe



MC-MPI (Native)


クラスタ間でFlat tree と クラスタ内でBinomial tree の2つの基本アルゴリ
ズムを使用
設定されたホスト名によりノード間の物理的距離が分かっている.
クラスタ間でFlat tree と クラスタ内でBinomial tree を使用
Binary Blocks

基本アルゴリズムの一つ.遅延が均一ならばデータサイズが大きいときの
最適なAllreduceを実現
実験:Grid環境での性能比較
Broadcast
MC-MPI(native)
30
実行時間(ms)
実行時間(ms)
35
25
20
15
OURS
MagPIe
10
5
0
0
1024
2048
3072
4096
データサイズ(byte)
1800
1600
1400
1200
1000
800
600
400
200
0
0
200
400
データサイズ(KB)
本手法:MagPIeとほぼ同じツリー構築
本手法:Scatter+Allgather
→ ネットワーク情報からでもクラスタ
の判別が可能
→ データ量による最適化
600
実験:Grid環境での性能比較
Allreduce
120
100
80
60
40
20
0
実行時間(ms)
Binary Blocks
実行時間(ms)
2000
1600
1200
OURS
MagPIe
0
1000 2000 3000 4000
データサイズ(byte)
本手法:MagPIeとほぼ同じツリー
構築
800
400
0
0
100
200
300
データサイズ(KB)
本手法:アルゴリズムの選択肢として
Binary Blocksも存在
→ Binary Blocks単独よりも効率上昇
実験結果のまとめ

1クラスタ


特にデータ256KBでRandomよりもMagPIeに近い結果
→ 自動取得したネットワーク情報から最適なアルゴリズ
ム選択が行えている
Grid環境


Broadcast, Allreduceともに他手法と同等以上の性能
特にAllreduceで単体の基本アルゴリズムBinary Blocks
よりも高性能
→ 複数の基本アルゴリズムの適切な組み合わせが
行えている
まとめ

ネットワークの構成情報を利用した集合通信の
モデルの設計


ネットワークに関する事前設定が不要
ネットワークの階層構造を考慮し,効率の良い集合通
信を実行
ネットワークに関する手動設定が必要な既存手法と
比べても同等,もしくはそれ以上の高速化が実現でき
た.
今後の課題

NAT,Firewallへの対応


NAT,Firewallの存在する環境でもトポロジーを推定可能
にし,そのような環境適したアルゴリズムの選択を行う
トポロジー取得にかかる時間を含めた高速化

現状ではトポロジーデータの取得から初期化にわた
る前準備に要する時間が0.5~2秒程かかる.ごく少な
い回数の集合通信を行う場合はこのオーバーヘッド
の時間が原因となりかえってアプリケーションの実行
時間が増大してしまう.
ダウンロード

自動取得したネットワークの構成情報に基づくMPI集合通信アルゴリズム