低遅延オンチップネットワークのための予測ルータの評価 松谷 宏紀 (慶大) 鯉渕 道紘 (NII) 天野 英晴 (慶大) 吉永　　努 (電通大) 予測ルータの設計・実装 [松谷,5月ICD/ARC研] 今回の発表では, 複数の予測アルゴリズムを装備, トラフィックに応じて切換え 実タイルアーキテクチャを想定した 4つのcase studyで評価

はじめに: Network-on-Chip (NoC) について メニーコア・アーキテクチャ 多数のコア (プロセッサ, キャッシュ) チップ内のパケット転送ネットワーク [Dally, DAC’01] router router router FP MAC MEM 80 tiles FP MAC router router router router Single tile router router router Intel 80-core chip [Vangal,ISSCC’07] パケット転送ネットワーク メニーコア・アーキテクチャの例 メニーコアの結合網 (NoC) 部分

最近の Network-on-Chip 一覧 システム名 トポロジ ルーティング スイッチング フロー制御 MIT RAW 2-D mesh (32bit) XY DOR WH, no VC Credit UPMC SPIN Fat Tree (32bit) Up*/down* QuickSilver ACM H-Tree (32bit) 1-flit, no VC UMass Amherst aSOC 2-D mesh Shortest-path Pipelined CS, no VC Timeslot Sun T1 Crossbar (128bit) - Handshake Cell BE EIB Ring (128bit) TRIPS (operand) 2-D mesh (109bit) YX DOR On/off TRIPS (on-chip) 2-D mesh (128bit) WH, 4 VCs Intel SCC 2-D torus (32bit) XY,YX DOR, odd-even TM Stall/go Intel 80-core NoC Source routing WH, 2 lanes TILE64 iMesh コアの数はますます増加 (例: 64コア, 80コア, …) 通信遅延の影響が増大 宛先まで何ホップもかかる オンチップルータのパイプライン構造を工夫して通信遅延を削減しよう

発表の流れ: 予測ルータによる低遅延通信 既存のオンチップルータ 予測ルータ 評価項目 Case study Speculative ルータ Look-ahead ルータ Bypassing ルータ 予測ルータ アーキテクチャ, 予測アルゴリズムいろいろ 評価項目 予測ヒット率, ハードウェア量, 消費エネルギー Case study [1] 2次元メッシュ (細粒度 ALU ネットワーク) [2] 2次元メッシュ (粗粒度 CMP ネットワーク) [3] Fat tree ネットワーク [4] Spidergon ネットワーク

オンチップルータ: ハードウェア構成 5入力5出力の WH ルータ, データ(フリット)幅は 64-bit ARBITER X+ X+ FIFO X- X- FIFO Y+ Y+ FIFO Y- Y- FIFO 5x5 XBAR CORE CORE FIFO 入力パケットは,バッファリング&経路計算され,適切な出力チャネルから出力される

Speculative ルータ: VA/SA を並列実行 衝突しなければ 3 cycle でヘッダがルータを通過 RC (Routing computation) VSA (Virtual channel / switch allocation) ST (Switch traversal) 例) ルータ(a) からルータ(c) にパケットを転送 VA と SA を投機的に並列実行 @ROUTER A @ROUTER B @ROUTER C HEAD RC VSA ST RC VSA ST RC VSA ST DATA 1 SA ST SA ST SA ST DATA 2 SA ST SA ST SA ST DATA 3 SA ST SA ST SA ST 1 2 3 4 5 6 7 8 9 10 11 12 ヘッダがルータ(a)に注入され, データ3がルータ(c)を通過するまで12サイクル ELAPSED TIME [CYCLE]

Look-ahead ルータ: RC/VA を同時実行 衝突しなければ 3 cycle でヘッダがルータを通過 NRC (Next routing computation) VSA (Virtual channel / switch allocation) ST (Switch traversal) NRCが終わらなくても VSAを実行できる NRC: 次ルータのRCを実行 (自ルータのRCは手前のルータに任せる) @ROUTER A @ROUTER B @ROUTER C HEAD NRC VSA ST NRC VSA ST NRC VSA ST DATA 1 SA ST SA ST SA ST DATA 2 SA ST SA ST SA ST DATA 3 SA ST SA ST SA ST 1 2 3 4 5 6 7 8 9 10 11 12 ルータ(b)の出力ポートはルータ(a)が決め, ルータ(c)の出力ポートはルータ(b)が… ELAPSED TIME [CYCLE]

Look-ahead ルータ: RC/VA を同時実行 衝突しなければ 2 cycle でヘッダがルータを通過 NRC + VSA (Next routing computation / switch allocation) ST (Switch traversal) NRC と VSA に依存性がないので並列実行できる  2サイクル転送 W. Dally, “Principles and Practices of Interconnection Networks” (2004) @Router A @Router B @Router C NRC NRC NRC HEAD ST ST ST VSA VSA VSA DATA 1 DATA 2 DATA 3 1 2 3 4 5 6 7 8 9 1-cycleルータもあるが,1ステージに詰込み過ぎ  動作周波数悪化 ヘッダがルータ(a)に注入され, データ3がルータ(c)を通過するまで9サイクル ELAPSED TIME [CYCLE]

Bypassingルータ: 一部ステージをスキップ バイパス方法1 – 頻繁に使うパスを低遅延化 Express VC: 非隣接ルータ間に仮想的なバイパス経路 Dynamic Fast Path: SA パケットを先行させる 隣接間通信が多いと効果が薄い [Kumar,ISCA’07] [Park, HOTI’07] 頻繁に使う経路の低遅延化 (4ホップのとき) 3-cycle 1-cycle 1-cycle 1-cycle 3-cycle SRC DST 頻繁に使う経路の低遅延化 (2ホップのとき) 3-cycle 1-cycle 3-cycle SRC DST

Bypassingルータ: 一部ステージをスキップ バイパス方法1 – 頻繁に使うパスを低遅延化 Express VC: 非隣接ルータ間に仮想的なバイパス経路 Dynamic Fast Path: SA パケットを先行させる 隣接間通信が多いと効果が薄い [Kumar,ISCA’07] [Park, HOTI’07] バイパス方法 2 – 次元順ルーティングの規則性を利用 Mad Postman: 上から来たら下, 右から来たら左へ即転送 転送後に RC と VSA を行い, 間違っていたらリカバリ 隣接間通信が多いと効果が薄い [Izu, PDP’94] バイパス方法 3 – ユーザ指定の特定パスを低遅延化 Preferred Path:クロスバを経由しない高速パス DBP: リング状に張った高速パス どのパスを高速化するかをユーザが指定しないといけない [Michelogiannakis, [鯉渕, NOCS’08] NOCS’07] どれが良いかはケースバイケース予測アルゴリズムは1個では不足

発表の流れ: 予測ルータによる低遅延通信 既存のオンチップルータ 予測ルータ 評価項目 Case study Speculative ルータ Look-ahead ルータ Bypassing ルータ 予測ルータ アーキテクチャ, 予測アルゴリズムいろいろ 評価項目 予測ヒット率, ハードウェア量, 消費エネルギー Case study [1] 2次元メッシュ (細粒度 ALU ネットワーク) [2] 2次元メッシュ (粗粒度 CMP ネットワーク) [3] Fat tree ネットワーク [4] Spidergon ネットワーク

1ステージに処理を詰込まない;予測が70%当たれば1.6サイクル転送 予測ルータ: 予測に基づいた低遅延ルータ [吉永,情処論’08] 予測による1サイクル転送 どの出力ポートが使われるか予測する (RC をプレ実行) 予測した出力ポートでクロスバ調停を済ます (SA をプレ実行) [鯉渕,情処論’08] 予測が当たれば RC と VSA をスキップ (1サイクル転送) @ROUTER A @ROUTER B @ROUTER C HEAD RC VSA ST RC VSA ST RC VSA ST DATA 1 ST ST ST DATA 2 ST ST ST DATA 3 ST ST ST 1 2 3 4 5 6 7 8 9 10 11 12 1ステージに処理を詰込まない;予測が70%当たれば1.6サイクル転送 ELAPSED TIME [CYCLE]

1ステージに処理を詰込まない;予測が70%当たれば1.6サイクル転送 予測ルータ: 予測に基づいた低遅延ルータ [吉永,情処論’08] 予測による1サイクル転送 どの出力ポートが使われるか予測する (RC をプレ実行) 予測した出力ポートでクロスバ調停を済ます (SA をプレ実行) [鯉渕,情処論’08] 予測が当たれば RC と VSA をスキップ (1サイクル転送) MISS @ROUTER B @ROUTER C HEAD RC VSA ST RC VSA ST RC VSA ST DATA 1 ST ST ST DATA 2 ST ST ST DATA 3 ST ST ST 1 2 3 4 5 6 7 8 9 10 11 12 1ステージに処理を詰込まない;予測が70%当たれば1.6サイクル転送 ELAPSED TIME [CYCLE]

1ステージに処理を詰込まない;予測が70%当たれば1.6サイクル転送 予測ルータ: 予測に基づいた低遅延ルータ [吉永,情処論’08] 予測による1サイクル転送 どの出力ポートが使われるか予測する (RC をプレ実行) 予測した出力ポートでクロスバ調停を済ます (SA をプレ実行) [鯉渕,情処論’08] 予測が当たれば RC と VSA をスキップ (1サイクル転送) MISS HIT @ROUTER C HEAD RC VSA ST ST RC VSA ST DATA 1 ST ST ST DATA 2 ST ST ST DATA 3 ST ST ST 1 2 3 4 5 6 7 8 9 10 11 12 1ステージに処理を詰込まない;予測が70%当たれば1.6サイクル転送 ELAPSED TIME [CYCLE]

1ステージに処理を詰込まない;予測が70%当たれば1.6サイクル転送 予測ルータ: 予測に基づいた低遅延ルータ [吉永,情処論’08] 予測による1サイクル転送 どの出力ポートが使われるか予測する (RC をプレ実行) 予測した出力ポートでクロスバ調停を済ます (SA をプレ実行) [鯉渕,情処論’08] 予測が当たれば RC と VSA をスキップ (1サイクル転送) MISS HIT HIT HEAD RC VSA ST ST ST DATA 1 ST ST ST DATA 2 ST ST ST DATA 3 ST ST ST 1 2 3 4 5 6 7 8 9 10 11 12 1ステージに処理を詰込まない;予測が70%当たれば1.6サイクル転送 ELAPSED TIME [CYCLE]

予測ルータ: いろいろな予測アルゴリズム 出力ポート予測による1サイクル転送 ヒット率が低遅延化の鍵 予測アルゴリズムを複数装備 [吉永,情処論’08] 出力ポート予測による1サイクル転送 ヒット率が低遅延化の鍵 予測アルゴリズムを複数装備 トラフィックやルーティングに 　応じて1サイクルで切り替え可 Random Static Straight パケットが直進すると予測 Custom 予測ポートをユーザが指定 Latest Port 前回と同じポートを予測 Finite Context Method 頻繁に出現する n個のコン テキストパターンで予測 Sampled Pattern Match 履歴テーブルによるパター ンマッチング 1種類では適用範囲が狭い MISS HIT HIT RC VSA ST ST ST ST ST ST ST ST ST ST ST ST 1 2 3 4 5 6 7 8

予測ルータ: ハードウェア構成 [松谷,HPCA’09] チャネルごとに数種類の予測器; 1サイクルで切替え可 Predictors A B C ARBITER X+ X+ FIFO X- X- Y+ Y+ Y- Y- CORE 5x5 XBAR CORE

予測ルータ: 予測ヒット時の動作 [松谷,HPCA’09] チャネルごとに数種類の予測器; 1サイクルで切替え可 Predictors A B C ARBITER Correct X+ X+ FIFO 予めクロスバを予約 X- X- Y+ Y+ Y- Y- CORE 5x5 XBAR CORE 予測がヒットすれば, 予約しておいたポートを使って 1サイクル転送

予測ルータ: 予測ミス時の動作 [松谷,HPCA’09] チャネルごとに数種類の予測器; 1サイクルで切替え可 KILL Predictors A B C ARBITER X+ X+ Dead flit FIFO Correct X- X- Y+ Y+ Y- Y- CORE 5x5 XBAR CORE 間違って転送されたフリット (dead flit) は出力チャネルで kill される 伝播しない

発表の流れ: 予測ルータによる低遅延通信 既存のオンチップルータ 予測ルータ 評価項目 Case study Speculative ルータ Look-ahead ルータ Bypassing ルータ 予測ルータ アーキテクチャ, 予測アルゴリズムいろいろ 評価項目 予測ヒット率, ハードウェア量, 消費エネルギー Case study [1] 2次元メッシュ (細粒度 ALU ネットワーク) [2] 2次元メッシュ (粗粒度 CMP ネットワーク) [3] Fat tree ネットワーク [4] Spidergon ネットワーク

評価項目: ヒット率,通信遅延,HW量,エネルギー How many cycles ? Astro (place and route) FIFO hit NC-Verilog (simulation) FIFO XBAR SAIF SDF miss hit hit Design compiler (synthesis) Power compiler Flit-level net simulation Fujitsu 65nm library 予測ヒット率・通信遅延 HW量 (ゲート数) 消費エネルギー [pJ / bit] 表1: ルータ／ネットワークのパラメータ 表2: 設計パラメータ パケット長 4-flit (1-flit = 64 bit) スイッチング方法 wormhole チャネルバッファ 4-flit / VC 仮想チャネル(VC) 数 1 – 2VCs Cycle / hop (通常) 3 stage Cycle / hop (予測ヒット) 1 stage CMOS プロセス 65nm 供給電圧 1.20V 温度 25C 表3: 設計 CAD ツール Design compiler 2006.06 Astro 2007.03 (※) トポロジ, トラフィックパターンは後述

評価項目: 予測ルータの4つの case study How many cycles ? Astro (place and route) FIFO hit NC-Verilog (simulation) FIFO XBAR SAIF SDF miss hit hit Design compiler (synthesis) Power compiler Flit-level net simulation Fujitsu 65nm library 予測ヒット率・通信遅延 HW量 (ゲート数) 消費エネルギー [pJ / bit] 2-D mesh network Fat tree network 最も一般的なネットワークトポロジ RAW [Taylor,ISCA’04] Intel’s 80-core [Vangal,ISSCC’07] 次元順ルーティング (X 方向  Y 方向) Case study 1 : 細粒度 ALU ネットワーク Case study 2 : 粗粒度 CMP ネットワーク  時間の都合上, まとめて説明します Spidergon network Case study 1 & 2 Case study 3 Case study 4

Case study 2 : 予測ヒット率 @ 8x8 mesh SS: 直進すると予測 LP: 同じポートを使うと予測 FCM: 頻度による予測  1ホップ通信ではヒットせず (LU) 予測ヒット率 [%] 7種類のNAS parallel プログラム 4種類の合成トラフィック

Case study 2 : 予測ヒット率 @ 8x8 mesh SS: 直進すると予測 LP: 同じポートを使うと予測 FCM: 頻度による予測  1ホップ通信ではヒットせず (LU)  繰り返し通信に強い (BT&SP) 予測ヒット率 [%] 7種類のNAS parallel プログラム 4種類の合成トラフィック

Case study 2 : 予測ヒット率 @ 8x8 mesh SS: 直進すると予測 LP: 同じポートを使うと予測 FCM: 頻度による予測  1ホップ通信ではヒットせず (LU)  繰り返し通信に強い (BT&SP)  全体的に高いヒット率 既存の Bypassing ルータでは, 予測アルゴリズムは 1種類に固定 予測ルータでは, 複数のアルゴリズムを装備し, 状況に応じて切り替え可能 幅広いアプリケーションを低遅延化できる [Izu,PDP’94] [Park, HOTI’07] [Kumar,ISCA’07] [Michelogiannakis,NOCS’07] しかし, 良く効くアルゴリズムはトラフィックごとに異なる 予測ヒット率 [%] 7種類のNAS parallel プログラム 4種類の合成トラフィック

Case study 2 : 面積と消費エネルギー ハードウェア量 オリジナルルータ 予測ルータ (SS + LP) 予測ルータ (SS+LP+FCM) 消費エネルギー ハードウェア量 [kilo gates] 予測アルゴリズムの種類と数に応じて6.4% ～ 15.9% の増加

Case study 2 : 面積と消費エネルギー ハードウェア量 オリジナルルータ 予測ルータ (SS + LP) 予測ルータ (SS+LP+FCM) 消費エネルギー オリジナルルータ 予測ルータ (70%ヒット) 予測ルータ (ヒット時) ハードウェア量 [kilo gates] フリット転送エネルギー [pJ / bit] 予測アルゴリズムの種類と数に応じて6.4% ～ 15.9% の増加 予測が外れるとオーバヘッドが大きい 予測が 70% 当たるなら 9.5% の増加 通信遅延は35.8～48.2%減; 面積は6.4%～16%増; 電力は9.5%増

評価項目: 予測ルータの4つの case study How many cycles ? Astro (place and route) FIFO hit NC-Verilog (simulation) FIFO XBAR SAIF SDF miss hit hit Design compiler (synthesis) Power compiler Flit-level net simulation Fujitsu 65nm library 予測ヒット率・通信遅延 HW量 (ゲート数) 消費エネルギー [pJ / bit] 2-D mesh network Fat tree network Spidergon network H-tree を多重化 ツリー型の NoC SPIN architecture [Andriahantenaina,DATE’03] up*/down* routing Up方向  Down 方向 Case study 1 & 2 Case study 3 Case study 4

Case study 3 : Fat tree ネットワーク Down Up 1. LRU algorithm Up方向に対し,利用頻度の低いポートを予測 2. LRU + LP algorithm Down方向にLPを使用

Case study 3 : Fat tree ネットワーク 通信遅延 @ Uniform オリジナルルータ 予測ルータ (LRU) 予測ルータ (LRU + LP) Down Up 通信遅延 [cycles] 1. LRU algorithm Up方向に対し,利用頻度の低いポートを予測 2. LRU + LP algorithm Down方向にLPを使用 ネットワークサイズ (コア数) 256コアで 30.7% の通信遅延の削減; 面積オーバヘッドは +7.8%

評価項目: 予測ルータの4つの case study How many cycles ? Astro (place and route) FIFO hit NC-Verilog (simulation) FIFO XBAR SAIF SDF miss hit hit Design compiler (synthesis) Power compiler Flit-level net simulation Fujitsu 65nm library 予測ヒット率・通信遅延 HW量 (ゲート数) 消費エネルギー [pJ / bit] 2-D mesh network Fat tree network Spidergon network Case study 1 & 2 Case study 3 Case study 4

Case study 4 : Spidergon ネットワーク Ring + 対角線リンク Node degree は 3 Mesh-like なレイアウト Across first routing 予測ヒット率 @ Uniform [Coppola,ISSOC’04]

Case study 4 : Spidergon ネットワーク Ring + 対角線リンク Node degree は 3 Mesh-like なレイアウト Across first routing 予測ヒット率 @ Uniform SS: 直進予測 LP: 同じポートを予測 FCM: 頻度による予測 [Coppola,ISSOC’04] 予測ヒット率 [%] SS と FCM はほぼ同じヒット率 ネットワークサイズ (コア数) 64コアで 80% の予測ヒット率, 256コアで94% の予測ヒット率を達成

まとめ: NoC における予測ルータの評価 予測ルータ : Yet another low latency router 予測ルータの評価 複数の予測アルゴリズムを装備, 状況に応じて切り替え可 予測ルータの評価 Case study 1 : 2次元メッシュ (細粒度 ALU ネットワーク) Case study 2 : 2次元メッシュ (粗粒度 CMP ネットワーク) Case study 3 : Fat tree ネットワーク Case study 4 : Spidergon ネットワーク 本発表の主張 1. 予測ルータは, 様々なトポロジ・ルーティングに適用可能 2. 予測ルータは, 現実的なオーバヘッドで通信遅延を大幅削減 3. 予測ルータは, 複数の予測アルゴリズムを装備することで, より広範囲なトラフィックパターンに対処可能 面積は6.4～15.9% 増 エネルギーは 9.5% 増 通信遅延は36～48% 減 (Case study 1 & 2 より) 4種類のcase study を通して

Any Questions?

Case study 1 : ルータのクリティカルパス RC: 経路計算 VSA: アービトレーション ST: フリット転送 予測ルータではフリット転送も生じる 通常のルータと比べ, クリティカルパスが 6.2% 増 ステージの遅延 [FO4s] 通常のルータ 予測ルータ (SS)