1. sakurano

    No comment

    sakurano
Changes in body
Source | HTML | Preview

日本語での需要ないかも?

背景

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

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

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

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

InfiniBand

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

2段ファットツリー

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

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

としましょう。

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

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

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

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

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

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

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

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

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

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

  • 収容効率 $E_2 = N_2/S_2 = p/3$
ポート数$p$ 上段スイッチ$n$ ノード数$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_{max} = \frac{1}{2} p^2$
  • 最大収容時スイッチ台数、$S_{max} = \frac{3}{2} p$
  • 最大収容時ケーブル数、$C_{max} = p^2$
ポート数$p$ $N_{max}$ $S_{max}$ $C_{max}$
36 648 54 1296

3段ファットツリー

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

  • スイッチのポート数 $p$
  • 2段FTの上段スイッチの数 $m$ ※2台ファットツリーでのnにあたる。
  • 2段FT数 $n$

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

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

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

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

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

  • 必要ケーブル数 $C_3 = 3pmn$
ポート数$p$ 二段FTの上段$m$ 二段FT数$n$ ノード数$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_{max} = \frac{1}{4} p^3$
- 最大収容時スイッチ台数、$S_{max} = \frac{5}{4}p^2$
- 最大収容時ケーブル数、$C_{max} = \frac{3}{4}p^3$

n段ファットツリー

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

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

$a_n \leq p/2 , a_n \in \mathbb{N}$

  • スイッチのポート数 $p$
  • 収容可能ノード数 $N_n = p\prod_{1}^{n-1}{a_k}$
  • 必要スイッチ数 $S_n = (2n-1)\prod_{1}^{n-1}{a_k}$
  • 必要ケーブル数 $C_n = np\prod_{1}^{n-1}{a_k}$

$a_k$は、それぞれ$p/2$が最大なので、
- 最大収容時ノード数、$N_{max} = \frac{1}{2^{n-1}} p^n$
- 最大収容時スイッチ台数、$S_{max} = \frac{2n-1}{2^{n-1}}p^{n-1}$
- 最大収容時ケーブル数、$C_{max} = \frac{n}{2^{n-1}}p^n$
- 最大収容時ポート利用効率、$E_{max} = \frac{1}{2n-1}$

36ポートスイッチを利用したとき、
| 段数$n$ | ポート数$p$ | ノード数$N_n$ | スイッチ数$S_n$ | ケーブル数$C_n$ |効率$E_n$ |
|----:|-----:|----:|---:|---:|---:|---:||-------:|-----------:|-------------:|--------------:|--------------:|--------:|
| 1 | 36 | 36 | 1 | 36 | $\frac{1}{1}$|
| 2 | 36 | 648 | 54 | 1296 | $\frac{1}{3}$|
| 3 | 36 | 11664 | 1620 | 34992 | $\frac{1}{5}$|
| 4 | 36 | 209952 | 40824 | 839808 | $\frac{1}{7}$|
| 5 | 36 | 3779316 | 944784 | 18895680 | $\frac{1}{9}$|
| 6 | 36 | 68024448 | 20785248 | 408146688 | $\frac{1}{11}$|
| 7 | 36 | 1224440064 | 442158912 | 8571080448 | $\frac{1}{13}$|