集団通信アルゴリズムまとめ
 Share
The version of the browser you are using is no longer supported. Please upgrade to a supported browser.Dismiss

 
View only
 
 
ABCDEFGHIJKLMNOPQRSTUVWXY
1
処理アルゴリズムレイテンシ帯域計算重視アルゴリズム概要使い分け (MPICH2)コメント
2
AllgatherRing(p-1) α((p-1)/p) nβ(なし)帯域ワーカー i は最初のステップは自分のデータを、以降のステップでは前ステップで受信したデータをワーカー i+1 に送る。全 p-1 ステップ。合計 〜80KB:Bruck
〜512KB か 2 べき: Recursive Dobuling
それ以外:Ring
MPICH 1
3
Recursive Doubling(p が 2 べき)(lg p) α((p-1)/p) nβ(なし)両方ワーカー i はステップ k でワーカー i XOR 2^k と持ってるデータを全部交換する。
4
Recursive Doubling(一般)2 floor(lg p) α((p-1)/p) nβ(なし)
5
Bruck Algorithm(lg p) α((p-1)/p) nβ(なし)両方各ワーカーはステップ k で i-2^k にデータを送り i+2^k からデータを受信する。concatenation とも呼ばれる。barrier アルゴリズムの dissemination の変種。送受信するデータが常に連続になるように気をつけられている。一番最後に 1 回だけシフトが必要。
6
BroadcastBinomial Tree(lg p) α(lg p) nβ(なし)レイテンシbinomial tree に沿ってデータを送る。P≧8 かつ 12KB〜:Van de Geijin
それ以外:Binomial Tree
MPICH 1
7
Van de Geijin Algorithm(lg p + p-1)α2((p-1)/p) nβ(なし)帯域Scatter して Allgather。
8
All-to-AllPairwise Exchange(p-1) α(なし)帯域愚直に1対1の通信を p-1 回行う。〜256B:Bruck
256B〜32KB:Pairwise Exchange (irecv-isend)
〜32KB:Pairwise Exchange (scheduled)
MPICH 1
9
Bruck Algorithm(lg p) α(lg p)/2 nβ(なし)レイテンシステップ k はサイズ 2^k の行列の転置を行う。
10
Reduce-ScatterNaive(lg p + p-1)α(lg p + ((p-1)/p) nβ(lg p) nγ存在価値無しReduce して Scatter。〜512B:Recursive Doubling
〜512KB:Recursive Halving
512KB〜:Pairwise Exchange
MPICH 1
11
Recursive Halving(p が 2 べき)(lg p) α((p-1)/p) nβ((p-1)/p) nγ両方ワーカー i はステップ k でワーカー i XOR p/2^k にサイズ n/2^k のデータを送る。
12
Recursive Halving(一般)
(floor(lg p) + 2) α
2 nβ(1 + (p-1)/p) nγ
13
Recursive Doubling(lg p) α(lg p - (p-1)/p) nβ
(lg p - (p-1)/p) nγ
レイテンシワーカー i はステップ k でワーカー i XOR 2^k にサイズ n(1 - 1/2^k) のデータを送る。(こいつには本当に存在価値があるのか?)
14
Pairwise Exchange(p-1) α((p-1)/p) nβ((p-1)/p) nγ帯域愚直に1対1の通信を p-1 回行う。
15
ReduceBinomial Tree(lg p) α(lg p) nβ(lg p) nγレイテンシbiniomial tree に沿ってデータを送る。〜2KB:Binomial Tree
2KB〜:Rabenseifner
MPICH 1
16
Rabenseifner Algorithm2(lg p) α2((p-1)/p) nβ((p-1)/p) nγ帯域Reduce-Scatter して Gather。
17
AllreduceNaive2(lg p) α2(lg p) nβ(lg p) nγ存在価値無しReduce して Bcast。〜2KB:Recursive Doubling
2KB〜:Rabenseifner
MPICH 1
18
Recusrive Doubling(lg p) α(lg p) nβ(lg p) nγレイテンシAllgather の Recursive Doubling と同様。
19
Rabenseifner Algorithm2(lg p) α2((p-1)/p) nβ((p-1)/p) nγ帯域Reduce-Scatter して Allgather。左記のレイテンシは Allgather に Bruck を仮定しているが、MPICH の Allgather は大きなデータを送る時は Ring 。
20
21
22
23
【メモ】
* α はレイテンシ
* β は 1 バイト送るのにかかる時間
* γ は 1 バイトの集約計算にかかる時間
* n はデータサイズ
* lg p は基本的に ceil(lg p) の意味
* 任意の 2 ワーカー間で同じレイテンシ・帯域で通信可能であり、通信同士が影響を与え合わないシンプルなモデルを仮定

【参考文献】
Thakur, Rajeev, Rolf Rabenseifner, and William Gropp. "Optimization of collective communication operations in MPICH." International Journal of High Performance Computing Applications 19.1 (2005): 49-66.

【作成】
iwiwi
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
Loading...
 
 
 
シート1