1. sakurano

    No comment

    sakurano
Changes in body
Source | HTML | Preview

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

背景

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

InfiniBandでは、36ポートのスイッチが標準的に使われます。
36台間であれば、1台のスイッチを用意するだけで、同等の帯域がすべてのノード間で確保できます。
これ以上のノードを相互接続するにはどうしたらよいでしょうか。

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

上に行くほど太くして相互接続して、上流と下流を同等の帯域を確保する方法です。
(ここでは、そのスイッチにつながるノードを下流、別のスイッチにつながるものを上流と呼びます。)

InfiniBand

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

1段ファットツリー

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

36ポートが標準と書きましたが、一般化して

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

とします。

以下は、自明です。

  • 収容可能ノード数 $N_1 = p$
  • 必要スイッチ数 $S_1 = 1$
  • 必要ケーブル数 $C_1 = p$

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

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

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

ポート数$p$ $N_1^{max}$ $S_1^{max}$ $C_1^{max}$
36 36 1 36

2段ファットツリー

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

二段ファットツリーでは、2段スイッチは1段スイッチの半分だけの数を用意します。
その間をケーブル接続する必要があるので、自然数であるべきです。

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

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

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

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

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

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

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

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

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

  • 収容効率 $E_2 = N_2/S_2 = p/3$
ポート数$p$ 上段スイッチ$n_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

※n=1のときは、1段で良いので合理的最小はn=2となる。

  • 最大収容時ノード数、$N_2^{max} = \frac{1}{2} p^2$
  • 最大収容時スイッチ台数、$S_2^{max} = \frac{3}{2} p$
  • 最大収容時ケーブル数、$C_2^{max} = p^2$
ポート数$p$ $N_2^{max}$ $S_2^{max}$ $C_2^{max}$
36 648 54 1296

3段ファットツリー

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

  • スイッチのポート数 $p$
  • 2段FTの上段スイッチの数 $n_1$
  • 2段FT数 $n_2$

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

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

1つの2段FT数で、$S_2=3n_1$であり、2段FTが$n_2$あるので、$3n_1n_2$。さらに、もう一段ある分が$2/3$倍にあたるので、

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

1つの2段FT数で、$C_2=2pn_1$であり、2段FTが$n_2$あるので、$2pn_1n_2$。さらに、もう一段ある分で$pn_1n_2$分必要なので、

  • 必要ケーブル数 $C_3 = 3pn_1n_2$
ポート数$p$ 二段FTの上段$n_1$ 二段FT数$n_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

$m$,$n$は$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$)のように階層的に考えることで、

$T_n \leq p/2 , T_n \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}$

$T_k$は、それぞれ$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}$