Edited at

n段Fat Treeネットワークには、何台入る?何台のスイッチが必要?

日本語での需要ないかもですし、超一部のSIerにしか興味ある人はいないかも。


背景

HPCでは、ノード(ここではコンピュータ1台とします)間の通信速度を確保しないと、大規模になればなるほど所要のパフォーマンスが出せません。

スーパーコンピュータともなれば、どの計算機間にも同等の通信帯域が求められます。

InfiniBandでは、36ポートのスイッチが標準的に使われます。

36台間であれば、1台のスイッチを用意するだけで、同等の帯域がすべてのノード間で確保できます。

これ以上のノードを相互接続するにはどうしたらよいでしょうか。

ツリーネットワークであれば、遠いノード間では、集約される分、帯域が確保されなくなります。

そこで考えられたのがFatTreeネットワークです。

上に行くほど太くして相互接続して、上流と下流を同等の帯域を確保する方法です。

(ここでは、そのスイッチにつながるノードを下流、別のスイッチにつながるものを上流と呼びます。)


InfiniBand

低レイテンシ、広帯域なインターコネクトです。(雑)


1段ファットツリー

一般化するために、ツリーでもないが、一応1から考えておきましょう。

36ポートが標準と書きましたが、一般化して$p$とおきます。以下は明らかです。


  • スイッチのポート数 $p$

  • 収容可能ノード数 $N_1 = p$

  • 必要スイッチ数 $S_1 = 1$

  • 必要ケーブル数 $C_1 = p$

  • 最大収容時ノード数 $N_1^{max} = p$

  • 最大収容時スイッチ台数 $S_1^{max} = 1$

  • 最大収容時ケーブル数 $C_1^{max} = p $

  • 最大収容時効率 $E_1 = N_1/S_1 = p$

$p$
$N_1^{max}$
$S_1^{max}$
$C_1^{max}$
$E_1^{max}$

36
36
1
36
36


2段ファットツリー


  • 上段スイッチ(=1段ファットツリー)の数 $T_1$
    とします。

二段ファットツリーでは、2段スイッチは1段スイッチの半分だけの数を用意します。

その間をケーブル接続する必要があるので、自然数であるべきです。

$\frac{p}{2T_1} \in \mathbb{N}$

そのため、場合によっては、36ポート全部活かせないこともありえます。

収容可能なノード数は、1段スイッチの下流数、2段スイッチの下流数と同じとなります。1段スイッチは2段スイッチの半分の個数であるため、$pT_1$となります。


  • 収容可能ノード数 $N_2 = pT_1$

また、1段スイッチの数が$T_1$で、2段スイッチは$2T_1$となりますので、必要なスイッチ数は、$3T_1$となります。


  • 必要スイッチ数 $S_2 = 3T_1$

さらに、ケーブルは上流・下流それぞれにノード数の2倍必要なので、$2N_2$必要となります。


  • 必要ケーブル数 $C_2 = 2pT_1$

たくさんノードを、少ないスイッチで実現できればよいわけです。全体で1台のスイッチあたりに、何台つなげるかを収容効率と考えることができそうです。


  • 収容効率 $E_2 = N_2/S_2 = p/3$

ポート数$p$
上段スイッチ$T_1$
ノード数$N_2$
スイッチ数$S_2$
ケーブル数$C_2$
効率$E_2$

36
1
36
3
72
12.0

36
2
72
6
144
12.0

36
3
108
9
216
12.0

32
4
128
12
256
10.7

30
5
150
15
300
10.0

36
6
216
18
432
12.0

32
8
256
24
512
10.7

36
9
324
27
648
12.0

36
18
648
54
1296
12.0

※$T_1=1$のときは、1段で良いので合理的には$T_1\geq2$となる。


  • 最大収容時ノード数、$N_2^{max} = \frac{1}{2} p^2$

  • 最大収容時スイッチ台数、$S_2^{max} = \frac{3}{2} p$

  • 最大収容時ケーブル数、$C_2^{max} = p^2$

  • 最大収容時効率、$E_2^{max} = \frac{p}{3}$


3段ファットツリー

2段ファットツリーを上流スイッチとみなします。


  • スイッチのポート数 $p$

  • 2段FTの上段スイッチの数 $T_1$

  • 2段FT数 $T_2$

2段FTの上段スイッチに対して、$N_2=pT_1$であり、その数が$T_2$あるので


  • 収容可能ノード数 $N_3 = pT_1T_2$

となり、1つの2段FT数で、$S_2=3T_1$であり、2段FTが$T_2$あるので、$3T_1T_2$。さらに、もう一段ある分が$2/3$倍にあたるので、


  • 必要スイッチ数 $S_3 = 5T_1T_2$

となり、1つの2段FT数で、$C_2=2pT_1$であり、2段FTが$T_2$あるので、$2pT_1T_2$。さらに、もう一段ある分で$pT_1T_2$分必要なので、


  • 必要ケーブル数 $C_3 = 3pT_1T_2$

となります。

ポート数$p$
二段FTの上段$T_1$
二段FT数$T_2$
ノード数$N_3$
スイッチ数$S_3$
ケーブル数$C_3$
効率$E_3$

36
18
2
1296
180
3888
7.2

36
18
18
11664
1620
34992
7.2

$T_1$,$T_2$は$p/2$が最大なので、以下のようになります。

- 最大収容時ノード数、$N_3^{max} = \frac{1}{4} p^3$

- 最大収容時スイッチ台数、$S_3^{max} = \frac{5}{4}p^2$

- 最大収容時ケーブル数、$C_3^{max} = \frac{3}{4}p^3$


n段ファットツリー

$n-1$段ファットツリーを上流スイッチとみなすことで、多段を考えることができます。

3段のときにおける、2段スイッチの上段スイッチ数(=$T_1$)、2段FT数(=$T_2$)のように考えることで、

総乗で書くことができそうです。

$\forall T \leq \frac{p}{2} \cap \forall \frac{T}{2p} \in \mathbb{N}$


  • スイッチのポート数 $p$

  • 収容可能ノード数 $N_n = p\prod_{1}^{n-1}{T_k}$

  • 必要スイッチ数 $S_n = (2n-1)\prod_{1}^{n-1}{T_k}$

  • 必要ケーブル数 $C_n = np\prod_{1}^{n-1}{T_k}$

$\forall T \leq \frac{p}{2}$であることから、


  • 最大収容時ノード数 $N_{n}^{max} = \frac{1}{2^{n-1}} p^n$

  • 最大収容時スイッチ台数 $S_{n}^{max} = \frac{2n-1}{2^{n-1}}p^{n-1}$

  • 最大収容時ケーブル数 $C_{n}^{max} = \frac{n}{2^{n-1}}p^n$

  • 最大収容時利用効率 $E_{n}^{max} = \frac{p}{2n-1}$

となる。

36ポートスイッチ利用したとき、それぞれの段数での最大収容数であるとき、以下の表の通りとなる。

段数$n$
ポート数$p$
ノード数$N_n$
スイッチ数$S_n$
ケーブル数$C_n$
効率$E_n$

1
36
36
1
36
$\frac{36}{1}$

2
36
648
54
1296
$\frac{36}{3}$

3
36
11664
1620
34992
$\frac{36}{5}$

4
36
209952
40824
839808
$\frac{36}{7}$

5
36
3779316
944784
18895680
$\frac{36}{9}$

6
36
68024448
20785248
408146688
$\frac{36}{11}$

7
36
1224440064
442158912
8571080448
$\frac{36}{13}$