Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

日本語での需要ないかもですし、超一部の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}$
sakurano
OSS原理主義者ではないものの、プリファーOSSな人です。 (OSSだけというのは)なんとなく心強い。一部の人だけ使ってたでしょ?みんな使うようになったらいいと思ってた。クローズドソースがいないと安心!
ricos
FEMによる構造解析、機械学習の専門家集団。計算資源のクラウド提供もしています。
https://www.ricos.co.jp/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした