低遅延オンチップネットワーク のための予測ルータの評価 松谷 宏紀 (慶大) 東大 鯉渕 道紘 (NII) 天野 英晴 (慶大) 吉永 努 (電通大) メニーコア・アーキテクチャの例 • たくさんのコア (プロセッサ, キャッシュバンク) • Network-on-Chip (NoC) で結合 • Large scale CMP の例 [Beckmann, MICRO’04] UltraSPARC L1キャッシュ (I & D) L2キャッシュ (Uni) メニーコア・アーキテクチャの例 • たくさんのコア (プロセッサ, キャッシュバンク) • Network-on-Chip (NoC) で結合 • Large scale CMP の例 [Beckmann, MICRO’04] UltraSPARC L1キャッシュ (I & D) L2キャッシュ (Uni) オンチップルータ メニーコア・アーキテクチャの例 • たくさんのコア (プロセッサ, キャッシュバンク) • Network-on-Chip (NoC) で結合 • Large scale CMP の例 [Beckmann, MICRO’04] UltraSPARC L1キャッシュ (I & D) L2キャッシュ (Uni) オンチップルータ ルータ遅延とアプリの実行時間 • SPLASH-2 ベンチマーク (8-CPU) の実行時間 – 4-cycle ルータ使用時 – 1-cycle ルータ使用時 ルータ遅延がアプリに与える影響は どのくらい? UltraSPARC L1キャッシュ (I & D) L2キャッシュ (Uni) オンチップルータ ルータ遅延とアプリの実行時間 • SPLASH-2 ベンチマーク (8-CPU) の実行時間 アプリケーションの実行時間 (相対値) [%] – 4-cycle ルータ使用時 – 1-cycle ルータ使用時 ルータ遅延がアプリに与える影響は どのくらい? 1サイクル化によって平均20% アプリの実行時間が削減 UltraSPARC L1キャッシュ (I & D) L2キャッシュ (Uni) オンチップルータ メニーコア・アーキテクチャのトレンド システム トポロジ ルーティング スイッチング フロー制御 MIT RAW 2D mesh XY DOR WH, no VC Credit UPMC SPIN Fat Tree Up*/down* WH, no VC Credit QuickSilver ACM H-Tree Up*/down* 1-flit, no VC Credit UMass Amherst aSOC 2D mesh Shortest-path Pipelined CS, no VC Timeslot Sun T1 Crossbar Cell BE EIB Ring -ノード数はますます増加傾向 Handshake (e.g., 64-core, 80-core)Credit Shortest-path Pipelined CS, no VC ホップ数も増加する TRIPS (operand) 2D mesh YX DOR TRIPS (on-chip) 2D mesh Intel SCC 2D torus XY,YX DOR, odd-even TM TILE64 iMesh 2D mesh XY DOR 1-flit, no VC On/off 問題になる WH, no VC Stall/go WH, no VC Credit YX コア間の通信遅延がますます DOR WH, 4 VCs Credit Intel 80-core 2-D mesh Source routing WH, 2 lanes On/off オンチップルータの低遅延化が急務 これまで予測ルータを研究 NoC 本発表の概要: 予測ルータの評価 • これまでの予測ルータの研究 – 予測ルータの提案 (大規模計算機向け) [吉永,情処論’08] [松谷,HPCA’09] – 予測オンチップルータアーキテクチャ 予測オンチップルータの 4 つの case study • 予測ルータの評価 – – – – – 予測ヒット率, ハードウェア量, 消費エネルギー Case study 1: 2-D mesh (細粒度コア) Case study 2: 2-D mesh (粗粒度コア) Case study 3: Fat tree ネットワーク Case study 4: Spidergon ネットワーク 発表の流れ: 予測ルータの評価 • 既存の低遅延ルータアーキテクチャ – Speculative ルータ – Look-ahead ルータ – Bypassing ルータ • 予測ルータ – アーキテクチャと予測アルゴリズム • 予測ルータの評価 – – – – – 予測ヒット率, ハードウェア量, 消費エネルギー Case study 1: 2-D mesh (細粒度コア) Case study 2: 2-D mesh (粗粒度コア) Case study 3: Fat tree ネットワーク Case study 4: Spidergon ネットワーク オンチップルータ: 1) 出力チャネルを 入力チャネル 選択する ハードウェア構成 2) 選択した出力チャネルを 使うためアービトレーション 出力チャネル ARBITER X+ X+ FIFO X- FIFO X- Y+ FIFO Y+ YCORE FIFO FIFO GRANT 3) パケットを出力チャネ Yルへ転送 5x5 CROSSBAR CORE ルーティング計算,アービトレーション,クロスバ上のパケット転送はパイプライン実行 Speculative ルータ: VA/SA を並列実行 • 衝突しなければ 3 cycle でヘッダがルータを通過 – RC (Routing computation) – VSA (Virtual channel / switch allocation) VA と SA を投機的に – ST (Switch traversal) 並列実行 [Peh,HPCA’01] • 例) ルータ(a) からルータ(c) にパケットを転送 @ROUTER A @ROUTER B @ROUTER C HEAD RC VSA ST RC VSA ST RC VSA ST DATA 1 SA ST DATA 2 SA DATA 3 1 2 3 4 SA ST ST SA SA ST 5 6 7 SA ST ST SA SA ST 8 9 10 ST SA ST 11 12 ELAPSED TIME [CYCLE] ヘッダがルータ(a)に注入され, データ3がルータ(c)を通過するまで12サイクル Look-ahead ルータ: RC/VA を同時実行 • 衝突しなければ 3 cycle でヘッダがルータを通過 – NRC (Next routing computation) – VSA (Virtual channel / switch allocation) – ST (Switch traversal) NRCが終わらなくて も VSAを実行可 [Galles,HOTI’96] NRC: 次ルータのRCを実行 (自ルータのRCは手前のルータに任せる) @ROUTER A @ROUTER B @ROUTER C HEAD NRC VSA ST NRC VSA ST NRC VSA ST DATA 1 SA ST DATA 2 SA DATA 3 1 2 3 4 SA ST ST SA SA ST 5 6 7 SA ST ST SA SA ST 8 9 10 ST SA ST 11 12 ELAPSED TIME [CYCLE] ルータ(b)の出力ポートはルータ(a)が決め, ルータ(c)の出力ポートはルータ(b)が… Look-ahead ルータ: RC/VA を同時実行 • 衝突しなければ 2 cycle でヘッダがルータを通過 – NRC + VSA (Next routing computation / switch allocation) – ST (Switch traversal) NRC と VSA に依存性がないので並列実行できる 2サイクル転送 [Galles,HOTI’96] @Router A @Router B @Router C HEAD NRC ST VSA DATA 1 NRC ST VSA ST DATA 2 NRC ST VSA ST ST ST ST ST DATA 3 1 2 3 4 5 ST ST 6 7 ST 8 9 1-cycleルータもあるが,1ステージに詰込み過ぎ ヘッダがルータ(a)に注入され, データ3がルータ(c)を通過するまで9サイクル ELAPSED TIME [CYCLE] 動作周波数悪化 Bypassingルータ: 一部ステージをスキップ • 非隣接ルータ間に仮想的なバイパス経路 – E.g., Express VCs [Kumar, ISCA’07] SRC 3-cycle Bypassed 3-cycle 1-cycle 3-cycle Virtual bypassing paths Bypassed 1-cycle 3-cycle DST 3-cycle Bypassingルータ: 一部ステージをスキップ • 非隣接ルータ間に仮想的なバイパス経路 – E.g., Express VCs [Kumar, ISCA’07] SRC 3-cycle Bypassed 3-cycle 1-cycle 3-cycle Virtual bypassing paths Bypassed 1-cycle 3-cycle DST 3-cycle • 次元順ルーティングの規則性を利用したバイパス – E.g., Mad postman [Izu, PDP’94] • 頻繁に使われるパス上の転送を低遅延化 – E.g., Dynamic fast path [Park, HOTI’07] • ユーザ指定の特定パス上の転送を低遅延化 [Michelogiannakis, NOCS’07] – E.g., Preferred path – E.g., DBP [Koibuchi, NOCS’08] どれが良いかはケースバイケース Bypassingポリシは1個では不足 発表の流れ: 予測ルータの評価 • 既存の低遅延ルータアーキテクチャ – Speculative ルータ – Look-ahead ルータ – Bypassing ルータ • 予測ルータ – アーキテクチャと予測アルゴリズム • 予測ルータの評価 – – – – – 予測ヒット率, ハードウェア量, 消費エネルギー Case study 1: 2-D mesh (細粒度コア) Case study 2: 2-D mesh (粗粒度コア) Case study 3: Fat tree ネットワーク Case study 4: Spidergon ネットワーク 予測ルータ: 予測に基づいた低遅延ルータ [吉永,情処論’08] • 予測による1サイクル転送 – どの出力ポートが使われるか予測する (RC をプレ実行) – 予測した出力ポートでクロスバ調停を済ます (SA をプレ実行) 予測が当たれば RC と VSA をスキップ (1サイクル転送) @ROUTER A @ROUTER B @ROUTER C HEAD RC VSA ST RC VSA ST RC VSA ST DATA 1 ST ST DATA 2 ST ST ST ST DATA 3 1 2 3 4 5 6 ST ST 7 8 9 ST 10 11 12 ELAPSED TIME [CYCLE] 1ステージに処理を詰込まない;予測が70%当たれば1.6サイクル転送 予測ルータ: 予測に基づいた低遅延ルータ [吉永,情処論’08] • 予測による1サイクル転送 – どの出力ポートが使われるか予測する (RC をプレ実行) – 予測した出力ポートでクロスバ調停を済ます (SA をプレ実行) 予測が当たれば RC と VSA をスキップ (1サイクル転送) MISS @ROUTER B @ROUTER C HEAD RC VSA ST RC VSA ST RC VSA ST DATA 1 ST ST DATA 2 ST ST ST ST DATA 3 1 2 3 4 5 6 ST ST 7 8 9 ST 10 11 12 ELAPSED TIME [CYCLE] 1ステージに処理を詰込まない;予測が70%当たれば1.6サイクル転送 予測ルータ: 予測に基づいた低遅延ルータ [吉永,情処論’08] • 予測による1サイクル転送 – どの出力ポートが使われるか予測する (RC をプレ実行) – 予測した出力ポートでクロスバ調停を済ます (SA をプレ実行) 予測が当たれば RC と VSA をスキップ (1サイクル転送) HIT MISS @ROUTER C HEAD RC VSA ST ST RC VSA ST DATA 1 ST ST DATA 2 ST DATA 3 1 2 3 4 5 ST ST ST ST ST 6 7 ST 8 9 10 11 12 ELAPSED TIME [CYCLE] 1ステージに処理を詰込まない;予測が70%当たれば1.6サイクル転送 予測ルータ: 予測に基づいた低遅延ルータ [吉永,情処論’08] • 予測による1サイクル転送 – どの出力ポートが使われるか予測する (RC をプレ実行) – 予測した出力ポートでクロスバ調停を済ます (SA をプレ実行) 予測が当たれば RC と VSA をスキップ (1サイクル転送) HIT HIT MISS HEAD RC VSA ST ST ST DATA 1 ST ST ST DATA 2 ST DATA 3 1 2 3 4 5 ST ST ST ST ST 6 7 8 9 10 11 12 ELAPSED TIME [CYCLE] 1ステージに処理を詰込まない;予測が70%当たれば1.6サイクル転送 予測ルータ: 予測アルゴリズムいろいろ • ヒット率が低遅延化の鍵 1. Random [吉永,情処論’08] 2. Static Straight (SS) 1種類の予測アルゴリズムでは パケットが同一次元上を直進すると予測する 広範囲なアプリケーションを低遅延化できない (次元順ルーティングの規則性を利用) 3. Custom • 予測ルータ 予測する出力チャネルをユーザが事前に指定 – 複数の予測器を各チャネルに装備 4. Latest Port (LP) Predictors 前回のパケット転送で使われた出力チャネルが 再び使われると予測 A 5.B FiniteCContext Method (FCM) [Burtscher, TC’02] 最も頻繁に出現する n個のコンテキストパターン (n = 0,1,2,…) – ベストな予測器をネットワーク環境 6. Sampled Pattern Match (SPM) [Jacquet, TIT’02] ごとに選んで使う 履歴テーブルを用いたパターンマッチング 予測ルータ: 0サイクル目: 1サイクル目: 1サイクル目: 2サイクル目: 予測ヒット時の動作 [松谷,HPCA’09] 出力チャネル X+ が選択され,クロスバが予約される 入力フリットを RC と VSA せずに X+ チャネルへ転送 並行して RC を実行 予測は正しかった! 次の入力フリットも RC と VSA せずに X+ チャネルへ転送 Predictors A X+ B C ARBITER Correct X+ FIFO クロスバが予約される XY+ YCORE 5x5 XBAR XY+ YCORE 予測がヒットすれば,予約しておいたクロスバポートを用いて1サイクル転送 予測ルータ: 予測ミス時の動作 [松谷,HPCA’09] 0サイクル目: 出力チャネル X+ が選択され,クロスバが予約される 1サイクル目: 入力フリットを RC と VSA せずに X+ チャネルへ転送 1サイクル目: 並行して RC を実行 予測が外れた。。。 (X- が正しかった) X+ チャネルへ kill 信号が送られる 2/3サイクル目: Dead flit が消され, そのコピーを正しい出力チャネルへ再送 KILL Predictors A X+ B FIFO C ARBITER Dead flit XY+ YCORE Dead flit のせいで余計 なエネルギーを消費 5x5 XBAR X+ XY+ YCORE 予測が外れたとしても通常どおり3サイクル転送される (ミスペナルティ無し) 発表の流れ: 予測ルータの評価 • 既存の低遅延ルータアーキテクチャ – Speculative ルータ – Look-ahead ルータ – Bypassing ルータ • 予測ルータ – アーキテクチャと予測アルゴリズム • 予測ルータの評価 – – – – – 予測ヒット率, ハードウェア量, 消費エネルギー Case study 1: 2-D mesh (細粒度コア) Case study 2: 2-D mesh (粗粒度コア) Case study 3: Fat tree ネットワーク Case study 4: Spidergon ネットワーク 評価項目: ヒット率,通信遅延,HW量,エネルギー How many cycles ? Astro (place and route) FIFO hit FIFO NC-Verilog (simulation) XBAR SAIF miss hit hit Design compiler (synthesis) Flit-level net simulation Fujitsu 65nm library 予測ヒット率・通信遅延 SDF Power compiler 消費エネルギー [pJ / bit] HW量 (ゲート数) 表2: 設計パラメータ 表1: ルータ/ネットワークのパラメータ 4-flit (1-flit = 64 bit) パケット長 CMOS プロセス 65nm スイッチング方法 wormhole 供給電圧 1.20V チャネルバッファ 4-flit / VC 温度 25C 仮想チャネル(VC) 数 1 – 2VCs Cycle / hop (通常) 3 stage Cycle / hop (予測ヒット) 1 stage (※) トポロジ, トラフィックパターンは後述 表3: 設計 CAD ツール Design compiler 2006.06 Astro 2007.03 評価項目: ヒット率,通信遅延,HW量,エネルギー How many cycles ? Astro (place and route) FIFO hit FIFO NC-Verilog (simulation) XBAR miss hit hit Design compiler (synthesis) Flit-level net simulation Fujitsu 65nm library 予測ヒット率・通信遅延 2-D mesh network HW量 (ゲート数) SAIF SDF Power compiler 消費エネルギー [pJ / bit] Fat tree network Spidergon network • 最も一般的なネットワークトポロジ RAW [Taylor,ISCA’04] Intel’s 80-core [Vangal,ISSCC’07] • 次元順ルーティング (X 方向 Y 方向) • Case study 1 : 細粒度 ALU ネットワーク • Case study 2 : 粗粒度 CMP ネットワーク Case study 1 & 2 Case study 3 Case study 4 時間の都合上, まとめて説明します Case study 1: 無負荷時の通信遅延 • オリジナルルータ • 予測ルータ (SS) • 予測ルータ (100%ヒット) Uniform トラフィック@ 4x4 mesh ~ 16x16 mesh (*) 予測がヒットしたら1サイクル転送, 予測が外れたら3サイクル転送 通信遅延 [cycles] 8x8 mesh では 遅延 35.8% 削減 16x16 mesh では 遅延 48.2% 削減 シミュレーション結果 Network size (k-ary 2-mesh) ネットワークが大きくなるさらに通信遅延が削減 (k=16 で48%減) Case study 2 : 予測ヒット率 @ 8x8 mesh 1ホップ通信ではヒットせず (LU) • SS: 直進すると予測 • LP: 同じポートを使うと予測 • FCM: 頻度による予測 予測ヒット率 [%] (*) 予稿集のほうでは, SS,LP,FCM,Random,Custom,SPM すべて評価 7種類のNAS parallel プログラム 4種類の合成トラフィック Case study 2 : 予測ヒット率 @ 8x8 mesh 1ホップ通信ではヒットせず (LU) • SS: 直進すると予測 • LP: 同じポートを使うと予測 繰り返し通信に強い (BT&SP) • FCM: 頻度による予測 予測ヒット率 [%] (*) 予稿集のほうでは, SS,LP,FCM,Random,Custom,SPM すべて評価 7種類のNAS parallel プログラム 4種類の合成トラフィック Case study 2 : 予測ヒット率 @ 8x8 mesh 1ホップ通信ではヒットせず (LU) • SS: 直進すると予測 • LP: 同じポートを使うと予測 繰り返し通信に強い (BT&SP) 全体的に高いヒット率 • FCM: 頻度による予測 予測ヒット率 [%] (*) 予稿集のほうでは, SS,LP,FCM,Random,Custom,SPM すべて評価 • 既存の Bypassing ルータでは, – Bypassing ポリシ(予測アルゴリズム)は 1種類に固定 [Kumar,ISCA’07] [Park, HOTI’07] [Izu,PDP’94] [Michelogiannakis,NOCS’07] しかし, 良く効くアルゴリズムはトラフィックごとに異なる • 予測ルータでは, – 複数のアルゴリズムを装備し, 状況に応じて切り替え可能 – 幅広いアプリケーションを低遅延化できる 7種類のNAS parallel プログラム 4種類の合成トラフィック Case study 2 : 面積と消費エネルギー • ハードウェア量 • 消費エネルギー HW オーバヘッド – オリジナルルータ が小さい – 予測ルータ (SS + LP) – 予測ルータ (SS+LP+FCM) FCM はヒット率が高いが HW 量が多い 予測ルータを Verilog-HDL で設計 ハードウェア量 [kilo gates] 予測アルゴリズムの種類と数に応じて 6.4% ~ 15.9% の増加 65nm ライブラリで合成 Case study 2 : 面積と消費エネルギー • ハードウェア量 – オリジナルルータ – 予測ルータ (SS + LP) – 予測ルータ (SS+LP+FCM) • 消費エネルギー – オリジナルルータ – 予測ルータ (70%ヒット) – 予測ルータ (ヒット時) このオーバヘッド見積もりは悲観的 1. リンク電力も考慮すると ルータ の電力オーバヘッドの影響 (小) 2. 低遅延化によってアプリが早く終わ る パワーゲーティングによるさら なる電力削減 ハードウェア量 [kilo gates] 予測アルゴリズムの種類と数に応じて 6.4% ~ 15.9% の増加 フリット転送エネルギー [pJ / bit] 予測が外れるとオーバヘッドが大きい 予測が 70% 当たるなら 9.5% の増加 通信遅延は35.8~48.2%減; 面積は6.4%~16%増; 電力は9.5%増 評価項目: 予測ルータの4つの case study How many cycles ? Astro (place and route) FIFO hit FIFO NC-Verilog (simulation) XBAR miss hit hit Design compiler (synthesis) Flit-level net simulation Fujitsu 65nm library SAIF SDF Power compiler 予測ヒット率・通信遅延 HW量 (ゲート数) 消費エネルギー [pJ / bit] 2-D mesh network Fat tree network Spidergon network • H-tree を多重化 • ツリー型の NoC SPIN architecture [Andriahantenaina,DATE’03] • up*/down* routing Case study 1 & 2 Case study 3 Up方向 Down 方向 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 1. LRU algorithm Up方向に対し,利用頻 度の低いポートを予測 2. LRU + LP algorithm 通信遅延 [cycles] Up ネットワークサイズ (コア数) Down方向にLPを使用 256コアで 30.7% の通信遅延の削減; 面積オーバヘッドは +7.8% 評価項目: 予測ルータの4つの case study How many cycles ? Astro (place and route) FIFO hit FIFO NC-Verilog (simulation) XBAR miss hit hit Design compiler (synthesis) Flit-level net simulation Fujitsu 65nm library SAIF SDF Power compiler 予測ヒット率・通信遅延 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 ネットワーク • Spidergon トポロジ – Ring + 対角線リンク [Coppola,ISSOC’04] – Node degree は 3 – Mesh-like なレイアウト – Across first routing • 予測ヒット率 @ Uniform Case study 4 : Spidergon ネットワーク • 予測ヒット率 @ Uniform • Spidergon トポロジ – Ring + 対角線リンク 予測ヒット率 [%] [Coppola,ISSOC’04] – SS: 直進予測 – LP: 同じポートを予測 – FCM: 頻度による予測 SS と FCM はほぼ同じヒット率 – Node degree は 3 – Mesh-like なレイアウト ネットワークサイズ (コア数) – Across routing 64コアで 80% first の予測ヒット率, 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 ネットワーク 面積は6.4~15.9% 増 エネルギーは 9.5% 増 4種類のcase study を通して 通信遅延は36~48% 減 (Case study 1 & 2 より) • 本発表の主張 1. 予測ルータは, 様々なトポロジ・ルーティングに適用可能 2. 予測ルータは, 現実的なオーバヘッドで通信遅延を大幅削減 3. 予測ルータは, 複数の予測アルゴリズムを装備することで, より広範囲なトラフィックパターンに対処可能 ご清聴ありがとうございました Network-on-Chip の低遅延化 • タイルアーキテクチャ – たくさんのコア (プロセッサ, キャッシュバンク) – オンチップネットワークで結合 [Dally, DAC’01] Core Router router router router router router router router router router パケットスイッチ・ネットワーク 16-core tile architecture オンチップルータ チップコストやアプリケーション性能に影響 Case study 1 : ルータのクリティカルパス • RC: 経路計算 • VSA: アービトレーション • ST: フリット転送 予測ルータではフリット転送も 生じる ステージの遅延 [FO4s] 通常のルータと比べ, クリティカルパスが 6.2% 増 通常のルータ 予測ルータ (SS) Case study 2: Hit rate @ 8x8 mesh SS: go straight Efficient for long straight comm. LP: the last one Efficient for short repeated comm. FCM: frequently used pattern All arounder ! Custom: user-specific path Efficient for simple comm. Prediction hit rate [%] • • • • 7 NAS parallel benchmark programs 4 synthesized traffics Prediction router: New modifications • Predictors for each input channel • Kill mechanism to remove dead flits • Two-level arbiter – “Reservation” higher priority – “Tentative reservation” by the pre-execution of VSA Predictors A X+ XY+ YCORE B C KILL signals ARBITER X+ FIFO Currently, the critical path is related to the arbiter 5x5 XBAR XY+ YCORE Prediction router: Predictor selection • Static scheme • Dynamic scheme – A predictor is selected by user per application Predictors A B C Configuration table Application 1 Predictor B Application 2 Predictor A Application 3 Predictor C … Simple … Pre-analysis is needed – A predictor is adaptively selected Predictors A B C Count up if each predictor hits Predictor A 100 Predictor B 80 Predictor C 120 A predictor is selected every n cycles (e.g., n =10,000) Flexible More energy
© Copyright 2025 ExpyDoc