松谷 宏紀 (慶大) 鯉渕 道紘 (ＮＩＩ) 天野 英晴 (慶大) クロスバ接続による 3次元 Network-on-Chip 向け 多層型トポロジ 松谷 宏紀 (慶大) 鯉渕 道紘 (ＮＩＩ) 天野 英晴 (慶大)

発表の流れ Network-on-Chip (NoC) XNoTs 予備評価 既存の 2次元 / 3次元トポロジ 既存の問題点 新しい3次元トポロジ 定義, 適用例 ルーティングアルゴリズム 予備評価 スループット 面積, 消費エネルギー

Network-on-Chip (NoC) タイルアーキテクチャ MIT RAW Texas U. TRIPS Intel 80-tile NoC NoC のトポロジ メッシュ, トーラス ツリー型 性能, 面積, 消費電力に影響を与える 計算タイル(プロセッサ等) ＋ オンチップ・ルータ [Taylor, Micro’02] [Buger, Computer’04] [Vangal, ISSCC’07] パケット転送(タイル間通信) タイルアーキテクチャの実装例 (VDEC/ASPLA/京大 90nm 使用)

既存の 2次元トポロジ: Mesh & Torus 2-D Mesh 2-D Torus メッシュの2倍の帯域 [Dally, DAC’01] RAW [Taylor, Micro’02] Intel’s 80-tile [Vangal, ISSCC’07] ルータ 計算コア

既存の 2次元トポロジ: Fat Tree Fat Tree (p, q, c) p: 上位リンクの数 q: 下位リンクの数 SPIN [Andriahantenaina, DATE’03] p: 上位リンクの数 q: 下位リンクの数 c: コアのポート数 Fat Tree (p, q, c) SCORE [Caspi, FPL’00] ACM [Furtek, FPL’04] Fat Tree (2,4,1) Fat Tree (2,4,2) ルータ 計算コア

NoC の3次元化: メリット 2次元トポロジ 3次元化 移動距離が長い リンクで電力を消費 ウェハ(ダイ)の積層 マイクロバンプ 貫通ビア リンク1-hop ≒ 72 [pJ / packet] ルータ1-hop≒ 66 [pJ / packet] 移動距離が長い [Banerjee, NOCS’07] ホップ数,移動距離は短いほうが良い タイルアーキテクチャ例 [Ezaki, ISSCC’04] [Burns, ISSCC’01]

既存の 3次元トポロジ: 3D-Mesh [Addo-Quaye, SoC’05] [Vasilis,SoC’06] Tier-3 Tier-2 Tier-1 Tier-0 2D-Mesh (8x8=64) 3D-Mesh (4x4x4=64) Average hop count: 5.33 Channel bisection: 16 Number of routers: 64 Node degree: 5 Average hop count: 4.00 Channel bisection: 32 Number of routers: 64 Node degree: 7

異なる形状の平面トポロジをどう繋ぐか? どうルーティングするか? 3次元 NoC: 問題点 Tier 毎に異なる回路構成 Tier 毎に異なるトポロジ Processor array Fat Tree (2,4,1) Tier-2 Accelerator Ring Tier-1 Cache memory 2D-Mesh Tier-0 異なる形状の平面トポロジをどう繋ぐか? どうルーティングするか?

発表の流れ Network-on-Chip (NoC) XNoTs 予備評価 既存の 2次元 / 3次元トポロジ 既存の問題点 新しい3次元トポロジ 定義, 適用例 ルーティングアルゴリズム 予備評価 スループット 面積, 消費エネルギー

各ルータと各コアには, 垂直方向の接続用に 1-port を用意 XNoTs: 新しい3次元トポロジ NoT: Network-on-Tier 各 tier に実装される 平面ネットワーク XNoTs: Xbar NoTs クロスバで接続されたNoTs 最下層の NoT は全コアへの接続性を保障する 各ルータと各コアには, 垂直方向の接続用に 1-port を用意 NoT NoT メッシュベースの NoT ルータ 計算コア NoT

各ルータと各コアには, 垂直方向の接続用に 1-port を用意 XNoTs: 新しい3次元トポロジ NoT: Network-on-Tier 各 tier に実装される 平面ネットワーク XNoTs: Xbar NoTs クロスバで接続されたNoTs 最下層の NoT は全コアへの接続性を保障する 各ルータと各コアには, 垂直方向の接続用に 1-port を用意 メッシュベースの NoT 垂直方向は, クロスバで接続 メッシュベースの XNoTs ルータ 計算コア

XNoTs: トポロジの柔軟性 (1/2) 2D-Mesh を積層 Ring を積層 Fat Treeを積層

XNoTs: トポロジの柔軟性 (1/2) 2D-Mesh を積層 Ring を積層 Fat Treeを積層 真横から見た図 垂直方向は, クロスバで接続 真横から見た図

XNoTs: トポロジの柔軟性 (2/2) 異なるトポロジの組合せ 最下層の NoT のみ,全コアへの接続性が必要 Fat Tree (2,4,1) Ring 2D-Mesh

XNoTs: トポロジの柔軟性 (2/2) 異なるトポロジの組合せ 最下層の NoT のみ,全コアへの接続性が必要 X-custom 垂直方向は, クロスバで接続 X-custom 真横から見た図

XNoTs: トポロジの柔軟性 (2/2) 異なるトポロジの組合せ 最下層の NoT のみ,全コアへの接続性が必要 X-custom Tier-0 を経由することで宛先に到達 接続性が無い!! X-custom 真横から見た図 X-custom

XNoTs: トポロジの柔軟性 (2/2) 異なるトポロジの組合せ 最下層の NoT のみ,全コアへの接続性が必要 X-custom Tier-0 を経由することで宛先に到達 X-custom 真横から見た図 X-custom

XNoTs: 垂直クロスバの分散配置 垂直クロスバスイッチ クロスバの分散配置 各段のルータ,コアを接続 MUX, BUF から構成 各グループを各 tier に 分散配置 多数の tier 間リンク 真横から見た図 Tier-2 [Dally, DAC’01] Tier-1 Tier-0

XNoTs: デッドロックフリー・ルーティング Tier 内の通信 Tier 内では, 既存のデッドロックフリー・ルーティングを使用 Tier-0 はすべてのコアへの到達性を保障 Tier 間の通信 下位 tier から上位 tier への移動は禁止 ただし, 1ホップ目とラストホップは除く (X方向, Y方向) DEADLOCK-FREE (Z方向) NG! OK! 例) 次元順ルーティング X-Mesh (XNoTs) 真上から見た図 真横から見た図

XNoTs: 経路選択ポリシ (ランダム) XNoTs ルーティング 経路選択ポリシ 複数の tier が利用可能  複数の代替経路が利用可能 経路選択ポリシ ルーティング時にどの tier を使うか? ランダムに選択  負荷分散に優れる [鯉渕, ParaComp’05] 5-hop 5-hop 5-hop X-Mesh (XNoTs) 真上から見た図 真横から見た図

放熱に優れる tier-0 を優先して使用する XNoTs: 経路選択ポリシ2 (放熱対策) 3次元IC の放熱対策 放熱用の貫通ビアを空ける Heat-sink 底辺の Tier ボードが heat-sink となるため放熱効果に優れる 代替経路が利用できるときは底辺の tier を使ってルーティング [Cong, ASPDAC’06] ボード (heat-sink) 3次元 IC 放熱に優れる tier-0 を優先して使用する XNoTs (真横から見た図)

XNoTs: 経路選択ポリシ3 (FIFO性の保障) 制御パケット FIFO 性が必要 In-order 転送 データパケット 広帯域 Out-of-order 転送 固定型ルーティング 適応型ルーティング Duato’s Protocol (適応型) 制御パケットは tier-0 を使う Duato’s Protocol (適応型) 次元順ルーティング(固定型) XNoTs (真横から見た図)

XNoTs: 経路選択ポリシ3 (FIFO性の保障) 制御パケット FIFO 性が必要 In-order 転送 データパケット 広帯域 Out-of-order 転送 固定型ルーティング 適応型ルーティング Duato’s Protocol (適応型) データパケットは tier-0 以外を使う Duato’s Protocol (適応型) 次元順ルーティング(固定型) 固定型と適応型の混載によって, FIFO性を保障しつつ, 高い性能 XNoTs (真横から見た図)

発表の流れ Network-on-Chip (NoC) XNoTs 予備評価 既存の 2次元 / 3次元トポロジ 既存の問題点 新しい3次元トポロジ 定義, 適用例 ルーティングアルゴリズム 予備評価 スループット 面積, 消費エネルギー

上記 5種類の XNoTs トポロジを, 3D-Mesh や 3D-Torus と比較 評価: 比較する3次元トポロジ (64コア) X-Mesh 4x4 の2次元メッシュを4枚積層 X-Torus 4x4 の2次元トーラスを4枚積層 X-FT141 16コアの Fat Tree (1,4,1) を　4枚積層 X-FT241 16コアの Fat Tree (2,4,1) を　4枚積層 X-FT441 16コアの Fat Tree (4,4,1) を　4枚積層 X-Mesh 上記 5種類の XNoTs トポロジを, 3D-Mesh や 3D-Torus と比較 X-FT241

性能評価: シミュレーション環境 グリッド型トポロジ ツリー型トポロジ 経路選択ポリシ 3D-Mesh, X-Mesh, 3D-Torus, X-Torus 次元順ルーティング ツリー型トポロジ X-FT141, X-FT241, X-FT441 Up*/down*ルーティング 経路選択ポリシ ランダム (トーラスのみ仮想チャネル2本) X-Mesh (16コアの4枚重ね) パケットサイズ 16-flit (1-flit header) バッファサイズ 1-flit per channel スイッチング Wormhole switching 通信遅延 3-cycle per 1-hop 通信パターン Uniform random traffic

X-Torus は 3D-Torus と同程度, X-Mesh は 3D-Mesh と同程度 性能評価: シミュレーション結果 X-Torus X-Mesh 3D-Torus 3D-Mesh X-FT441 X-FT241 X-FT141 3D-Torus 3D-Mesh グリッド型XNoTsの性能 ツリー型XNoTsの性能 X-Torus は 3D-Torus と同程度, X-Mesh は 3D-Mesh と同程度

結合網の面積: NoC の合成 ルータと NI の合成 結合網の面積 ルータ回路 貫通ビア 64コア (16コアの4枚重ね) 0.18um CMOS ルータ回路 フリット幅 32-bit Wormhole方式 4段パイプライン 貫通ビア 1～10um角 Tier を貫通する度に 25um / bit を加算 結合網の面積 ルータとNIの面積 貫通ビアの面積 Crossbar Input Ports Buf Arbiter Wormhole ルータ回路 [松谷, SACSIS’06] [Burns, ISSCC’01] [Li, ISCA’06] 2 Tier 間リンクの数をカウントして総面積に加算

結合網の面積: 見積り結果 ルータと NI の合成 ルータ回路 貫通ビア 64コア (16コアの4枚重ね) 0.18um CMOS フリット幅 32-bit Wormhole方式 4段パイプライン 貫通ビア 1～10um角 Tier を貫通する度に 25um / bit を加算 3D-mesh / torus では垂直方向に2-port 必要 [Burns, ISSCC’01] [Li, ISCA’06] 2 ルータとNI + 貫通ビアの面積 [mm ] 2 XNoTs ではルータ (クロスバ)数が増えるが, 垂直リンクは1-portのみ Tier 間リンクの数をカウントして総面積に加算

結合網の面積: XNoTs の現実性 NCSU の FFT チップ 3D via density 2-tier X-Mesh 3次元 IC 上に実装 0.18um CMOS 3-tier, 貫通ビア 3D via density 理論上の最大値: 17,500 [vias / mm　] 実用上の最大値: 2,500 [vias / mm　] 2-tier X-Mesh 1-tileに 6本のリンク リンク1本 = 32-bit ルータ1個 = 0.32 [mm　] 密度 = 600 [vias / mm　] 2 [Davis, DToC’05] 2 2 2 [Davis, VMIC’05] 6本のリンク

3-tier以下のXNoTsは現実的, 4-tier は可能(困難), 5-tier は不可能 NCSU の FFT チップ 3次元 IC 上に実装 0.18um CMOS 3-tier, 貫通ビア 3D via density 理論上の最大値: 17,500 [vias / mm　] 実用上の最大値: 2,500 [vias / mm　] 4-tier X-Mesh 1-tileに 18～24本のリンク リンク1本 = 32-bit ルータ1個 = 0.32 [mm　] 密度 = 2,400 [vias / mm　] 2 [Davis, DToC’05] 2 2 2 [Davis, VMIC’05] 18～24本のリンク 3-tier以下のXNoTsは現実的, 4-tier は可能(困難), 5-tier は不可能

まとめ: 3次元トポロジ XNoTs 既存の問題点 XNoTs 今後の課題 異なる形状の平面トポロジをどう繋ぐか? どうルーティングするか？ クロスバによって tier 間を接続 任意の平面トポロジを積層可能 4-tier 以上の XNoTs は実現困難 今後の課題 XNoTs ルーティングの詳細 HW実装寄りの検討 Fat Tree Ring 2D-Mesh [松谷, ICPP’07]

性能評価: Channel bisection ネットワークを二等分したとき, 断面をまたぐリンクの数 N-core × n-tier 1-tier 2-tier 4-tier X-Mesh 8 16 32 X-Torus 64 X-FT141 4 X-FT241 X-FT441 3D-Mesh 3D-Torus X-Torus は 3D-Torus と同程度, X-Mesh は 3D-Mesh と同程度

消費電力: NoC の電力モデル [Wang, DATE’05] フリットエネルギー 1-flit を宛先まで送る 平均何ジュールかかる? シミュレーション環境 6mm角 (4枚重ね) 0.18um CMOS 転送エネルギー 1-bit 転送 @ ルータ ルータ回路のゲートレベル解析 (Power Compiler) 1.13 [pJ / hop] 配線エネルギー 1-bit 転送 @ リンク 配線容量より計算 0.67 [pJ / mm] 6mm [Ho, IEEE’01] 貫通ビアの容量は 4.34fF [Davis,DToC’05]  10um 分の配線容量

消費電力: シミュレーション結果 シミュレーション環境 転送エネルギー 配線エネルギー 6mm角 (4枚重ね) 0.18um CMOS 1-bit 転送 @ ルータ ルータ回路のゲートレベル解析 (Power Compiler) 1.13 [pJ / hop] 配線エネルギー 1-bit 転送 @ リンク 配線容量より計算 0.67 [pJ / mm] ツリー型はデータの移動距離が長い分不利 XNoTs は平均ホップ数が小さいので有利 フリット転送エネルギー [pJ] [Wang, DATE’05] 貫通ビアの容量は 4.34fF [Davis,DToC’05]  10um 分の配線容量

2個の H-Tree によってトーラス構造が形成 既存の 2次元トポロジ: Fat H-Tree Fat H-Tree Red Tree (H-Tree) Black Tree (H-Tree) Fat Tree と Torus の両方の特徴を持つ Fat Tree より面積効率が良い [松谷, IPDPS’07] 2個の H-Tree によってトーラス構造が形成 Fat H-Tree (64-core) [松谷, SACSIS’07] Red ルータ Black ルータ 計算コア