# Technology-Driven, Highly-Scalable Dragonfly Topology Source: [[John Kim]]・[[William J. Dally]]・[[Steve Scott]]・[[Dennis Abts]] / ISCA 2008 / [PDF](https://static.googleusercontent.com/media/research.google.com/ja//pubs/archive/34926.pdf) ## 概要 本論文は **Dragonfly トポロジ**を提案した先駆的論文である。ルータのラジックス増加と能動光ケーブル(active optical cable)の普及という技術動向を出発点に、「ルータのグループを仮想ルータとして扱う階層ネットワーク」を設計することで、ネットワーク直径・コスト・レイテンシを同時に削減できることを示した。本論文が示した 3 段階の階層(ルータ・グループ・システム)と間接適応ルーティングの改良手法は、後の大規模 HPC ネットワーク設計に大きな影響を与えた。 ## 背景と動機 インターコネクトネットワークのコストはチャネル(ケーブル)が支配する。特にキャビネット間のグローバルケーブルとその光トランシーバが主要コスト要因である。ピン帯域幅の増大はハイラジックスルータの採用を後押しし、Cray BlackWidow はラジックス 64 ルータを用いた折り畳み Clos を採用した初期実装例である。一方、能動光ケーブル(Intel Connect Cable、Luxtera Blazar)の登場で 10m 超の距離でも光伝送が電気伝送より経済的になった。Dragonfly はこの技術変化を積極的に活かすトポロジである。 ## トポロジ設計 ### 階層構造 Dragonfly は 3 層の階層を持つ。 - **ルータ層**: 各ルータはラジックス $k = p + a + h - 1$。$p$ 個の端末チャネル・$a-1$ 個のローカルチャネル(同一グループ内接続)・$h$ 個のグローバルチャネル(他グループへの接続)を持つ。 - **グループ層**: $a$ 台のルータが イントラグループネットワークで完全接続される仮想ルータ。グループの実効ラジックスは $k' = a(p+h)$。 - **システム層**: 最大 $g = ah + 1$ 個のグループが相互接続される。端末数は $N = ap(ah+1)$。 最大サイズの Dragonfly では各グループ対は正確に 1 本のグローバル接続を持つ。 ### 設計パラメータのバランス 負荷分散トラフィック上でチャネル負荷を均衡させるには $a = 2p = 2h$ の関係が望ましい。各パケットのルートでローカルチャネル 2 本・グローバルチャネル 1 本・端末チャネル 1 本の比率が維持される。コスト上の理由からグローバルチャネルを過剰投資せず、ローカル・端末チャネルを過剰投資する設計 ($a \ge 2h, \; 2p \ge 2h$) が推奨される。 ### スケーラビリティ ラジックス 64 ルータを用いた場合、Dragonfly はネットワーク直径 3 ホップで 256K ノード超に到達する。グループサイズを増やすことで拡張できるため、フラット化バタフライが追加次元を要するのと対照的にスケーリングが容易である。 ### グループ内ネットワークの変形 グループ内イントラネットワークとして、1D フラット化バタフライ(完全グラフ)の代わりに多次元フラット化バタフライを用いることで実効ラジックスをさらに引き上げられる。3D フラット化バタフライで $p=2$ の場合は単純な 3D 立方体と等価となり、同じルータで到達可能なノード数が拡大する。 ## ルーティングアルゴリズム ### 最小ルーティング(MIN) 送信元グループ $G_s$ から宛先グループ $G_d$ へ 3 段階で転送: (1) $G_s$ 内でグローバルチャネルを持つルータへ転送 → (2) グローバルチャネルでジャンプ → (3) $G_d$ 内で宛先ルータへ転送。均一ランダムトラフィックではスループットが高いが、逆張りトラフィックパターンでは特定のグローバルチャネルに負荷集中する。 ### Valiant 法(VAL) 各パケットをまず無作為に選んだ中間グループ $G_i$ を経由させる非最小ルーティング。最悪ケーストラフィックを約 50% のスループットまで均衡化できるが、均一ランダムトラフィックではグローバルチャネルの負荷が 2 倍になりスループットが半減する。 ### UGAL (Universal Globally-Adaptive Load-balanced) MIN と VAL をパケット単位で切り替え、キュー長と経由ホップ数の積で遅延を推定し小さい経路を選ぶ。 - **UGAL-G**: グループ内全グローバルチャネルのキュー情報を使う理想的実装。実装困難だが性能目標値。 - **UGAL-L**: 現在のルータのローカルキュー情報のみで判断。間接性の問題(後述)を持つ。 ### 間接適応ルーティングの課題と解決 Dragonfly における適応ルーティングの難点は、均衡させるべきグローバルチャネルが現在のルータと異なるルータに接続されている点にある(間接性)。 **問題 1: 限定スループット** — UGAL-L は最小経路・非最小経路が同一出力ポートを共有するとき、個別に VC を使い分けられずにキュー占有率の比較が機能しない。解決策として **UGAL-LVC** を提案: 同一出力ポートを共有するときのみ最小経路用 VC と非最小経路用 VC を分離して判断する **UGAL-LVCH** でスループット問題を解消。 **問題 2: 中間負荷での高遅延** — 最小経路パケットがグローバルキュー情報を間接的にのみ感知するため、バッファが満杯になるまで輻輳を検知できない。クレジット往復レイテンシ $t_{crt}$ を計測し、通常時の往復時間 $t_{crt0}$ からの偏差 $t_d(O) = t_{crt}(O) - t_{crt0}$ だけ上流へのクレジット返信を遅延させることでバックプレッシャーを強化する **UGAL-LCR** を提案。バッファサイズ 16・256 いずれでも UGAL-L に比べて最大 35%(16 バッファ)・20 倍以上(256 バッファ)の遅延改善を達成した。 仮想チャネル(VC)の割り当ては最小経路に VC2 本・非最小経路に VC3 本を用い、ルーティングデッドロックを防ぐ。 ## コスト比較 コストモデルは「チャネル本数 × 単価(距離関数)」に基づく。能動光ケーブルは 10m 超で電気ケーブルより安価で、固定費用は高いが距離あたりコストが低い。Dragonfly は 16K ノード以上で: - フラット化バタフライ比: **約 20% のコスト削減** - 折り畳み Clos 比: **約 52% のコスト削減** - 3D トーラス比: 1K ノードで約 62% 削減(光ケーブルが不要な低コストリンクを使うトーラスとの差は規模拡大で縮小するが、8K 超で再び拡大) 64K ノードでの Dragonfly とフラット化バタフライの比較では、Dragonfly はグローバルケーブル本数が半分で済み(ルータポートの 25% をグローバルに割り当て vs フラット化バタフライの 50%)、グループサイズを増やすことで追加次元なしにスケールできる。 ## 評価設定 - シミュレータ: サイクル精度・入力キューイングルータ・ウォームアップ後の定常状態測定 - 基準構成: 1K ノード($p = h = 4$、$a = 8$) - トラフィックパターン: 均一ランダム(UR)・最悪ケース(WC、各ノードが Gi+1 のランダムノードへ送信) - バッファサイズ: 16・256 フリット ## 関連研究との位置づけ - SOENet はサブネットワーク構造で光技術を活用するが、中間ルータが存在し直径・コストが大きい。Dragonfly は全ルータが端末に直接接続されフラット。 - 従来の階層ネットワーク(ツリー構造)は帯域ボトルネックがある。Dragonfly はラジックスを増やしつつ直径を削減する。 - UGAL の間接問題に対し Singh (2005) はチャネルキューを使う手法を提案したが、Dragonfly の間接性ではこれが使えないため、クレジット往復レイテンシを使う本論文の手法が必要となった。 ## 結論 Dragonfly トポロジはグループを仮想ルータとして用いることで実効ラジックスを大きく高め、最大 1 グローバルホップという低直径を実現する。能動光ケーブルの経済特性(高固定費・低距離あたりコスト)と Dragonfly の「グローバルリンク本数削減・リンク長増加」という特性が良く適合する。また UGAL-LCR により間接適応ルーティングの課題を克服し、理想実装に近い性能を実証した。 ## 関連 - 概念: [[Dragonflyトポロジ]] / [[Fat-Tree]] / [[マルチプレーンClosトポロジ]] / [[ネットワークトポロジ]] - エンティティ: [[John Kim]] / [[William J. Dally]] / [[Steve Scott]] / [[Dennis Abts]] / [[Northwestern University]] / [[Stanford University]] / [[Cray Inc.]] / [[Google]] - 関連 MOC: [[structures/分散深層学習 - MOC]] ## 出典 - PDF: https://static.googleusercontent.com/media/research.google.com/ja//pubs/archive/34926.pdf - DOI: 10.1109/ISCA.2008.19 - 掲載: International Symposium on Computer Architecture (ISCA) 2008, pp. 77-88