予測機構を持つルータを用いた低遅延チップ内ネットワークに関する研究 鯉渕 道紘 (国情研/総研大/JST) 吉永　　努 　(電通大) 村上　弘和　（電通大） 松谷 宏紀 (慶大) 天野 英晴 (慶大)

発表の流れ チップ内ネットワーク（Network-on-Chip: NoC) ルータにおけるパケット処理 通常のルータ, 低遅延ルータ 予測ルータ 予測ルータを用いたチップ内ネットワークの性能解析 予測成功率 無負荷状態のネットワーク遅延 総合評価 面積, 消費エネルギー スループットと遅延 [吉永,SACSIS’07]

チップ内ネットワーク(Network-on-Chip:NoC) レギュラーアーキテクチャ Tilera Tile64 (64コア) Texas U. TRIPS Intel 80コア NoC タイルアーキテクチャ (P2P）イレギュラー アーキテクチャ 16-Core Tile Architecture On-chip router Core [Buger, Computer’04] [Vangal, ISSCC’07] タイルアーキテクチャの実装例 (*) 京大/VDEC/ASPLA 90nm CMOS 使用 3

バスからパケットネットワークへ バス構造の限界 コア数の増加 配線遅延の増加 Packet Network Generation

NoCとは？ チップ内ネットワーク＝ Network-on-Chip (NoC) = On-Chip Network(OCN)= On-Chip Interconnection Network(OCIN) 広義 チップ内のモジュール間ネットワークすべて 古典的バス： 単位時間あたり１データ転送, poor performance scalability 専用配線 全対全通信. poor area scalability パケットネットワーク 複数データ転送： high scalability 狭義 スイッチ（ルータ）ベースのパケットネットワーク

古典的な並列計算機のインターコネクトと同じNWアーキテクチャ 既存のNoC Topology; 　Data width Switching; VCs Flow control Routing algorithm MIT Raw (dynamic network) 2-D mesh; 32-bit wormhole; no VC credit based XY DOR UPMC/LIP6 SPIN Micro Network Fat Tree; 32-bit up*/down* routing UMass Amherst aSOC arch 2-D mesh PCS; no VC timeslot based shortest-path Sun UltraSparc T1 (CPX bus) crossbar; 128-bit N/A handshaking Sony, Toshiba, IBM Cell BE EIB ring; 128-bit UT Austin TRIPS (operand NW) 2-D mesh; 109-bit N/A †; no VC on/off YX DOR UT Austin TRIPS (OCN) 2-D mesh; 128-bit wormhole; 4VCs Intel SCC architecture 2-D torus; 32-bit wormhole; no VC stall/go XY,YX DOR; odd-even TM Intel Teraflops NoC wormhole; 2lane source routing ( e.g. DOR) Tilera TILE64 iMesh (dynamic NW) wormhole; no VC 古典的な並列計算機のインターコネクトと同じNWアーキテクチャ トポロジ：2-Dグリッド構造　ルーティング：次元順ルーティング スイッチング技術：ワームホール方式

NoCの課題 これまでの成功は、Off-chipネットワークアーキテクチャの転用による 並列計算機のネットワーク（Blue Gene/L等) トポロジ、ルーティング、フロー制御、ルータアーキテクチャ ロスレス高バンド幅ルータ これでは解決しきれない課題が顕著に、、、 [Dally’s Report,06] 遅延の削減 バスに比べると大きい。 オンチップメモリへのアクセス 高機能ルータによる遅延が主な原因 電力 プロセッサコアは省電力化、ネットワークも必要 詳細は本セッション内の松谷の発表にて CADの互換性

通信遅延 SRC から DST へ パケットが届くまでのサイクル数 Core On-chip router 例) 要求を出して, パケットが届くまでに1000-cycleかかったら使い物にならない 例えば, 1ホップ = 3サイクルとすると, 16-core mesh なら最大 21サイクル 64-core mesh なら最大 45サイクル 16-core Tile architecture

通信遅延の削減 通信遅延 トポロジを工夫する ルータを工夫する SRC から DST へ パケットが届くまでの サイクル数 例: Mesh  Torus ルータを工夫する パケット処理 例: 3サイクル 1サイクル Core On-chip router 遅延を減らす2つのアプローチ 16-core Tile architecture

発表の流れ チップ内ネットワーク（Network-on-Chip: NoC) ルータにおけるパケット処理 通常のルータ, 低遅延ルータ 予測ルータ 予測ルータを用いたチップ内ネットワークの性能解析 予測成功率 無負荷状態のネットワーク遅延 総合評価 面積, 消費エネルギー スループットと遅延 [吉永,SACSIS’07]

典型的なオンチップルータ 5入力5出力の WH ルータ 1ポート当り n個の入力バッファ (この図では 2系統) を持つ  仮想チャネルn本 ARBITER X+ X+ FIFO X- X- FIFO Y+ Y+ FIFO Y- Y- FIFO 5x5 XBAR CORE CORE FIFO [松谷,NOCS’08]

通常のルータ: 3段パイプライン 衝突しなければ 3 cycle でヘッダがルータを通過 RC (Routing computation) VSA (Virtual channel / switch allocation) ST (Switch traversal) 順番に実行 @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 ヘッダがルータ(a)に注入され, データ3がルータ(c)を通過するまで12サイクル ELAPSED TIME [CYCLE]

一般的な低遅延ルータ: 2段パイプライン 別アプローチ 1 – Express virtual channels 非隣接ルータ間に仮想的なバイパス経路 隣接間通信が多いと効果が薄い 別アプローチ 2 – Preferred path XYルーティングを想定し, パケットが直進すると予測 クロスバを迂回する低遅延なパス [Kumar,ISCA’07] [Michelogiannakis,NOCS’07] 衝突しなければ 2 cycle でヘッダがルータを通過 RC (Routing computation) VSA + ST (Switch allocation/ Switch traversal) NRC と VSA に依存性がないので並列実行できる  2サイクル転送 W. Dally, “Principles and Practices of Interconnection Networks” (2004) @Router A @Router B @Router C VSA VSA VSA HEAD RC RC RC ST ST ST 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]

予測ルータ: Yet another 1-cycle router [吉永,SACSIS’07] 予測による1サイクル転送 どの出力ポートが使われるか予測する (RC をプレ実行) 予測した出力ポートでクロスバ調停を済ます (SA をプレ実行) 予測が正しければ ST だけ (1サイクル転送) [松谷,ARC’08] 予測アルゴリズム: 直前ポートを使う, 直進すると予測, 履歴を使うなど @ROUTER A @ROUTER B @ROUTER C HEAD RC VSA ST RC VSA ST RC VSA ST DATA 1 ST ST ST DATA 2 予測が当たれば, RC と SA は省略 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]

予測機構付きルータ: これまでの成果 予測を用いた低遅延ネットワークの提案 予測機構付きルータアーキテクチャの提案と設計 並列計算機ネットワーク向けにスループット評価 予測アルゴリズムの比較 予測機構付きルータアーキテクチャの提案と設計 予測ミス時の処理 データパス構造 本研究では,予測ルータを用いたNoCを提案、評価 予測成功率の解析 １００%成功した理想場合との比較 コア数が増加した場合は？ パケット転送遅延の最小理論値 スループット、HW量、エネルギー [吉永,SACSIS’07] [松谷,ARC’08]

発表の流れ チップ内ネットワーク（Network-on-Chip: NoC) ルータにおけるパケット処理 通常のルータ, 低遅延ルータ 予測ルータ 予測ルータを用いたチップ内ネットワークの性能解析 予測成功率 無負荷状態のネットワーク遅延 総合評価 面積, 消費エネルギー スループットと遅延 [吉永,SACSIS’07]

既存のNoC トポロジ：2-Dグリッド構造 ルーティング：次元順ルーティング スイッチング技術：ワームホール方式 Topology; 　Data width Switching; VCs Flow control Routing algorithm MIT Raw (dynamic network) 2-D mesh; 32-bit wormhole; no VC credit based XY DOR UPMC/LIP6 SPIN Micro Network Fat Tree; 32-bit up*/down* routing UMass Amherst aSOC arch 2-D mesh PCS; no VC timeslot based shortest-path Sun UltraSparc T1 (CPX bus) crossbar; 128-bit N/A handshaking Sony, Toshiba, IBM Cell BE EIB ring; 128-bit UT Austin TRIPS (operand NW) 2-D mesh; 109-bit N/A †; no VC on/off YX DOR UT Austin TRIPS (OCN) 2-D mesh; 128-bit wormhole; 4VCs Intel SCC architecture 2-D torus; 32-bit wormhole; no VC stall/go XY,YX DOR; odd-even TM Intel Teraflops NoC wormhole; 2lane source routing ( e.g. DOR) Tilera TILE64 iMesh (dynamic NW) wormhole; no VC トポロジ：2-Dグリッド構造　　ルーティング：次元順ルーティング スイッチング技術：ワームホール方式

予測ルータ・ネットワークの性能解析 条件 トーラストポロジ（k-ary n-cube)、次元順ルーティング 強い規則性を予測に利用 ランダムトラフィック（注入レートはポアソン分布） 予測が難しいワーストケース 予測アルゴリズム 直前ポート予測（LP)、ランダム予測、直進予測（SS) D D ルータ リンク S S ランダム予測 直進予測(SS)

1次元トーラス（奇数）における経路分布 １つのリンクを通過する経路数 その中で直進する経路数 次元内ルータ数：ｋ 直進予測（SS)の予測成功率

N次元トーラスにおける経路分布（奇数） 2次元平面 2次元トーラス 3次元スタック構造 3次元トーラス i次元入力チャネルにおける予測成功率 2次元平面　　　　　　　　　2次元トーラス 3次元スタック構造　　　　　　3次元トーラス i次元入力チャネルにおける予測成功率 次元内ルータ数： k 次元数： n

ワーストケースのユニフォームトラフィックでも 80%以上の予測成功率を達成 比較対象 直進予測（SS) ランダム予測(Random) 直前予測(LP),SPM 　　　　　予測成功率（％）　　　　　 コア数　　　 ワーストケースのユニフォームトラフィックでも　　　　　　　　80%以上の予測成功率を達成 局所性があればより高い予測成功率を達成

遅延評価: 無負荷時の通信レイテンシ 比較対象 無負荷時の遅延モデル オリジナルルータ (Conv) 予測ルータ(ideal) 予測ルータ(SS) 予測ルータ(LP) 無負荷時の遅延モデル 100%的中 直進予測 直前予測 …ルーティング遅延 …スイッチ遅延 …アービトレーション遅延 …リンク遅延 …ヘッダサイズ …ホップ数 予測成功時 予測失敗時 予測成功率は解析結果を利用

予測によって, 通信遅延は 64コアで14.2%減, 289コアで23.7%減 遅延評価: 無負荷時の通信レイテンシ 比較対象 オリジナルルータ (Conv) 予測ルータ(ideal) 予測ルータ(SS) 予測ルータ(LP) 評価パラメータ 100%的中 直進予測 [nsec] 直前予測 トポロジ k-ary 2-cube (k=3…17) ルーティング 次元順 (XY routing) パケット長 16フリット トラフィック ユニフォームランダム 動作周波数 通常ルータ: 470.0MHz 予測ルータ: 464.8MHz ノード数 vs. 通信レイテンシ 予測によって, 通信遅延は 64コアで14.2%減, 289コアで23.7%減

発表の流れ チップ内ネットワーク（Network-on-Chip: NoC) ルータにおけるパケット処理 通常のルータ, 低遅延ルータ 予測ルータ 予測ルータを用いたチップ内ネットワークの性能解析 予測成功率 無負荷状態のネットワーク遅延 総合評価 面積, 消費エネルギー スループットと遅延 [吉永,SACSIS’07]

スループットと遅延の評価（シミュレーション） 比較対象 オリジナルルータ (Conv) 予測ルータ(SS) 予測ルータ(Random) 予測ルータ(LP) パケットの衝突の影響が新たに含まれる。 飽和前のNWにおける遅延を14%削減 直進予測 直前予測 -14% LU 分解、64コア ランダム、256コア

面積と電力評価[松谷ARC08] 面積、エネルギーは 23.4増、8.8%増 電力評価のフロー オリジナルルータ, 予測ルータ(stop有), 予測ルータ(stop無) をVerilog-HDLで実装 各種ルータを ASPLA 90nm で合成, 配置配線 (Design Compiler / Astro) 配置配線ルータにパケット負荷を与えるシミュレーションを実行 (NC-Verilog) SAIF, SDF, SPEF を読み込んで消費電力を見積もる (Power Compiler) +26.2% +8.8% +57.2% +23.4% オリジナル 予測ルータ1 予測ルータ２ オリジナル 予測ルータ1　２ 面積、エネルギーは 23.4増、8.8%増

まとめ チップ内ネットワーク(Network-on-Chip: NoC) ローカルメモリへのアクセス等の低遅延化が課題 ルータの転送遅延を最小化 予測成功率、ネットワーク遅延 総合評価（シミュレーション） 定常状態のネットワーク遅延を23%減 面積、エネルギーは 23%増、9%増 明瞭なトレードオフはあるが、低遅延NoCを達成する稀な技術 複雑化してルータのパイプライン段数が増加　　 　より効果大 （例：Intel 80-Core NoC: 5-cycle ルータ）