集団通信アルゴリズムまとめ

	A	B	C	D	E	F	G	H	I
1	処理	アルゴリズム	レイテンシ	帯域	計算	重視	アルゴリズム概要	使い分け (MPICH2)	コメント

2	Allgather	Ring	(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β	（なし）	両方	ワーカー i はステップ k でワーカー i XOR 2^k と持ってるデータを全部交換する。
5		Bruck Algorithm	(lg p) α	((p-1)/p) nβ	（なし）	両方	各ワーカーはステップ k で i-2^k にデータを送り i+2^k からデータを受信する。		concatenation とも呼ばれる。barrier アルゴリズムの dissemination の変種。送受信するデータが常に連続になるように気をつけられている。一番最後に 1 回だけシフトが必要。
6	Broadcast	Binomial Tree	(lg p) α	(lg p) nβ	（なし）	レイテンシ	binomial tree に沿ってデータを送る。	P≧8 かつ 12KB〜：Van de Geijin それ以外：Binomial Tree	MPICH 1
7	Broadcast	Van de Geijin Algorithm	(lg p + p-1)α	2((p-1)/p) nβ	（なし）	帯域	Scatter して Allgather。	P≧8 かつ 12KB〜：Van de Geijin それ以外：Binomial Tree
8	All-to-All	Pairwise Exchange	(p-1) α	nβ	（なし）	帯域	愚直に1対1の通信を p-1 回行う。	〜256B：Bruck 256B〜32KB：Pairwise Exchange (irecv-isend) 〜32KB：Pairwise Exchange (scheduled)	MPICH 1
9	All-to-All	Bruck Algorithm	(lg p) α	(lg p)/2 nβ	（なし）	レイテンシ	ステップ k はサイズ 2^k の行列の転置を行う。
10	Reduce-Scatter	Naive	(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γ	両方	ワーカー i はステップ k でワーカー i XOR p/2^k にサイズ n/2^k のデータを送る。
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	Reduce	Binomial Tree	(lg p) α	(lg p) nβ	(lg p) nγ	レイテンシ	biniomial tree に沿ってデータを送る。	〜2KB：Binomial Tree 2KB〜：Rabenseifner	MPICH 1
16	Reduce	Rabenseifner Algorithm	2(lg p) α	2((p-1)/p) nβ	((p-1)/p) nγ	帯域	Reduce-Scatter して Gather。	〜2KB：Binomial Tree 2KB〜：Rabenseifner
17	Allreduce	Naive	2(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 Algorithm	2(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