予測ルータ

予測機構を持った低遅延オンチップ
ルータアーキテクチャ
松谷宏紀
大)
鯉渕道紘
天野英晴
(慶
(NII)
(慶
Network-on-Chip (NoC)
• タイルアーキテクチャ
– Tilera Tile64 (64コア)
– Intel 80-core (80コア)
Core
On-chip router
タイル数は増える傾向にある
• 通信遅延
– SRC から DST へパケット
が届くまでのサイクル数
例) 要求を出して, パケットが届くまでに
1000-cycleかかったら使い物にならない
例えば, 1ホップ = 3サイクルとすると,
16-core mesh なら最大 21サイクル
64-core mesh なら最大 45サイクル
16-core Tile architecture
Network-on-Chip (NoC)
• タイルアーキテクチャ
– Tilera Tile64 (64コア)
– Intel 80-core (80コア)
Core
On-chip router
タイル数は増える傾向にある
• 通信遅延
– SRC から DST へパケット
が届くまでのサイクル数
遅延を減らす2つのアプローチ
• トポロジを工夫する
– 例: Mesh  Torus
• ルータを工夫する
– 例: 3サイクル  1サイクル
16-core Tile architecture
発表の流れ
• Network-on-Chip (NoC)
• ルータアーキテクチャ
– 通常のルータ, 低遅延ルータ
– 予測ルータ [吉永,SACSIS’07]
• 予測ルータアーキテクチャ
– データパス構造
– バッファ管理, Stop 機構
– Kill 機構
• 評価
– 面積, 消費エネルギー
– 通信遅延
オンチップルータ: ハードウェア構成
• 5入力5出力の WH ルータ, データ(フリット)幅は 64-bit
1ポート当り n個の入力バッファ (この図では 2系統) を持つ  仮想チャネルn本
ARBITER
X+
FIFO
X+
X-
FIFO
X-
Y+
FIFO
Y+
Y-
FIFO
Y5x5 XBAR
CORE
FIFO
(※) 配置配線後のゲート数は 33 [kgates] 前後
CORE
[松谷,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
DATA 2
ST
ST
ST
ST
DATA 3
1
2
3
4
5
RCが終わらないと
VSAを実行できない
6
ST
ST
7
8
9
ST
10
11
12
ヘッダがルータ(a)に注入され,
データ3がルータ(c)を通過するまで12サイクル
ELAPSED
TIME [CYCLE]
Look-aheadルータ: 3段パイプライン
• 衝突しなければ 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
ST
DATA 2
ST
ST
ST
ST
ST
DATA 3
1
2
3
4
5
6
ST
ST
7
8
9
ST
10
11
12
ルータ(b)の出力ポートはルータ(a)が決め,
ルータ(c)の出力ポートはルータ(b)が…
ELAPSED TIME
[CYCLE]
一般的な低遅延ルータ: 2段パイプライン
別アプローチ 1 –
virtual channels
•• 衝突しなければ
2 Express
cycle でヘッダがルータを通過
[Kumar,ISCA’07]
非隣接ルータ間に仮想的なバイパス経路
–– NRC
+ VSA (Next routing computation / switch
allocation)
隣接間通信が多いと効果が薄い
–– ST
(Switch traversal)
• 別アプローチ
2 – Preferred path
NRC と VSA に依存性がないので並列実行できる  2サイクル転送
– XYルーティングを想定し, パケットが直進すると予測
W. Dally, “Principles
[Michelogiannakis,NOCS’07]
– クロスバを迂回する低遅延なパス
@Router A @Router B @Router C
HEAD
NRC
ST
VSA
NRC
ST
VSA
and Practices of
Interconnection
Networks” (2004)
NRC
ST
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]  動作周波数悪化
予測ルータ: Yet another 1-cycle router
[吉永,SACSIS’07]
[鯉渕,SACSIS’08]
• 予測による1サイクル転送
– どの出力ポートが使われるか予測する (RC をプレ実行)
– 予測した出力ポートでクロスバ調停を済ます (SA をプレ実行)
– 予測が正しければ ST だけ (1サイクル転送)
予測アルゴリズム: 直前ポートを使う, 直進すると予測, 履歴を使うなど
@ROUTER A
@ROUTER B
@ROUTER C
HEAD RC VSA ST
RC VSA ST
RC VSA ST
DATA 1
ST
ST
予測が当たれば, ST
RC と SA は省略
DATA 2
DATA 3
1
2
3
4
5
ST
ST
ST
6
ST
ST
7
8
9
ST
10
11
12
1ステージに処理を詰込まない;予測が70%当たれば1.6サイクル転送
ELAPSED TIME [CYCLE]
予測機構付きルータ: これまでの成果
• 予測を用いた低遅延ネットワークの提案
[吉永,SACSIS’07]
– 並列計算機ネットワーク向けにスループット評価
– 予測アルゴリズムの比較
• NoC における予測ルーティング
[鯉渕,SACSIS’08]
– 予測ルーティングを NoC に応用
– 予測成功率の解析, スループット評価
上記の論文は,予測ルータアーキテクチャの詳細をカバーしていない
• 本発表では,予測ルータアーキテクチャを検討
–
–
–
–
データパス構造
バッファ管理
Stop 機構
Kill 機構
2つのデータパス(予測用とバックアップ用)
2つのデータパスでバッファを共有  面積抑える
片方のデータパスを早期に止める  電力抑える
予測失敗時の無効フリットの伝播を止める
発表の流れ
• Network-on-Chip (NoC)
• ルータアーキテクチャ
– 通常のルータ, 低遅延ルータ
– 予測ルータ [吉永,SACSIS’07]
• 予測ルータアーキテクチャ
– データパス構造
– バッファ管理, Stop 機構
– Kill 機構
• 評価
– 面積, 消費エネルギー
– 通信遅延
ルータの構成: 通常ルータ vs. 予測ルータ
• 通常のルータ
Arbiter
FIFO
• 予測ルータ
Predictor
(直前ポート予測)
Arbiter
FIFO
Predictor
FIFO
5x5 XBAR
FIFO
5x5 XBAR
• 予測器
– チャネル毎に持つ
– 直前ポート予測(LP)など
• 事前アービトレーション
– 予測に基づき, 事前にクロ
スバを割り当てる
データパス構造: 通常ルータ vs. 予測ルータ
• 通常のルータ
Arbiter
FIFO
• 予測ルータ
Predictor
(直前ポート予測)
Arbiter
FIFO
Predictor
FIFO
5x5 XBAR
5x5 XBAR
FIFO
Backup datapath
3-stage pipeline
RC VSA ST
RC VSA ST
各チャネルのデータパス構造
ST
Prediction datapath
データパスを2重化; 予測が当たると1サイクル転送,
外れは3サイクル
データパス構造: Stop 機構による省電力化
• Stop 機構無し
– 2つのデータパスが常に
データ転送
– 電力オーバヘッド (大)
Backup datapath
RC VSA ST
ST
Prediction datapath
予測が成功… 両データパスが動作
予測が失敗… 両データパスが動作
予測の成否はRC(1サイクル目)で判明
• Stop 機構有り
データパス構造: Stop 機構による省電力化
• Stop 機構無し
– 2つのデータパスが常に
データ転送
– 電力オーバヘッド (大)
Backup datapath
• Stop 機構有り
– RC(1サイクル目)で片方
のデータパスを停止
– 電力オーバヘッド (小)
予測成功
Backup datapath
RC VSA ST
RC VSA ST
ST
ST
Prediction datapath
Prediction datapath
予測が成功… 両データパスが動作
予測が失敗… 両データパスが動作
予測が成功… Backup path を停止
予測が失敗… Prediction path を停止
予測の成否はRC(1サイクル目)で判明
予測の成否はRC(1サイクル目)で判明
データパス構造: Stop 機構による省電力化
• Stop 機構無し
– 2つのデータパスが常に
データ転送
– 電力オーバヘッド (大)
Backup datapath
• Stop 機構有り
– RC(1サイクル目)で片方
のデータパスを停止
– 電力オーバヘッド (小)
予測失敗
Backup datapath
RC VSA ST
RC VSA ST
ST
ST
Prediction datapath
Prediction datapath
予測が成功… 両データパスが動作
予測が失敗… 両データパスが動作
予測が成功… Backup path を停止
予測が失敗… Prediction path を停止
予測の成否はRC(1サイクル目)で判明
予測の成否はRC(1サイクル目)で判明
評価では,通常ルータ,予測ルータ(stop有/無)の転送エネルギー比較
バッファ管理: 独立バッファ vs. 共有バッファ
• 独立バッファ方式
– 2つのデータパスが独立し
たバッファを持つ
– 面積オーバヘッド (大)
Backup datapath
• 共有バッファ方式
– 2つのデータパスが同じ
バッファを共有する
– 面積オーバヘッド (小)
Backup datapath
RC VSA ST
RC VSA ST
ST
ST
Prediction datapath
Prediction datapath
バッファの書き潰しが起きるのでは?
次スライドでは,データパス間のデータ書潰しが発生しないことを確認
バッファ管理:共有バッファで書潰しは起きない
Backup
Prediction
RC
Backupデータパスは cycle-1 で停止
h
d
1 h
d d
2 1 h
d d d
3 2 1 h
ST
ST
ST
ST
cycle-1
cycle-2
cycle-3
予測成功時の2つのデータパスの動作
cycle-4
バッファ管理:共有バッファで書潰しは起きない
Backup
Prediction
RC
Backupデータパスは cycle-1 で停止
h
d
1 h
d d
2 1 h
d d d
3 2 1 h
ST
ST
ST
ST
cycle-1
cycle-2
cycle-3
cycle-4
予測成功時の2つのデータパスの動作
Backup
RC
h
Prediction
ST
cycle-1
SA
d
1 h
ST
d d
2 1 h
ST
d d d
3 2 1 h
Predictionデータパスは cycle-1 で停止
cycle-2
cycle-3
cycle-4
予測失敗時の2つのデータパスの動作
評価では,通常ルータ,予測ルータ(バッファ独立/共有)の面積を比較
予測失敗時の動作: 無効フリットとは?
• 予測失敗時の流れ
• 予測失敗の例
Backup
B
RC
SA
RC
Stop!!
Prediction ST
A
ST
C
1
無効フリット発生
2
3
4
• 1サイクル目
Router A にパケットが来た
次ホップとして Router C を予測したが
実際には Router B だった…
– RC で予測失敗が判明
– Stop 信号を有効化
– 間違った宛先に1-flit 伝播
• 2サイクル目
– Stop 信号により
prediction datapath 停止
予測失敗時: 無効フリットの Kill 機構
• Kill機構の動作 (予測失敗
• 予測失敗時の流れ
時)
– 予測失敗を検出したら,
– 隣接ルータのチャネルに
Kill 信号を送る
Backup
RC
SA
ST
RC
Stop & Kill !!
Prediction ST
無効フリット発生
データ信号(64-bit)
1
A
C
kill 信号 (1-bit)
Router C には,無効フリットと
Kill 信号が同時に伝播
 Kill信号と同時に来たフリットは廃棄
2
3
4
• 1サイクル目
– RC で予測失敗が判明
– Stop / Kill 信号を有効化
– 間違った宛先に1-flit 伝播
• 2サイクル目
– prediction datapath 停止
– 無効フリットを廃棄
予測失敗時: 無効フリットの Kill 機構
• Kill機構の動作 (予測失敗
時)
– 予測失敗を検出したら,
– 隣接ルータのチャネルに
Kill 信号を送る
• Kill 信号の引き回し
– すべての隣接ルータの
チャネルへ1-bit 信号
– チャネルごとに3本の Kill
信号を出力
データ信号(64-bit)
0
1
2
kill 信号 (1-bit)
3
4
5
Router C には,無効フリットと
Kill 信号が同時に伝播
6
7
8
A
C
 Kill信号と同時に来たフリットは廃棄
Router 4西ポートからのKill信号
発表の流れ
• Network-on-Chip (NoC)
• ルータアーキテクチャ
– 通常のルータ, 低遅延ルータ
– 予測ルータ [吉永,SACSIS’07]
• 予測ルータアーキテクチャ
– データパス構造
– バッファ管理, Stop 機構
– Kill 機構
• 評価
– 面積, 消費エネルギー
– 通信遅延
評価項目と比較対象
• ハードウェア量
– オリジナルルータ
– 予測ルータ(バッファ独立)
– 予測ルータ(バッファ共有)
Predictor
Arbiter
FIFO
• 消費エネルギー
– オリジナルルータ
– 予測ルータ(Stop機構無
し)
– 予測ルータ(Stop機構有
り)
Predictor
FIFO
5x5 XBAR
評価に用いた予測ルータ
• データ幅は 64-bit
• 5入力5出力ワームホール方式
• 通信遅延
– オリジナルルータ
• 予測アルゴリズムは LP
• 仮想チャネル数は 1 と 2 の場合
面積評価: ルータのゲート数を比較
• 予測ルータ(バッファ独
立)Backup datapath
• 予測ルータ(バッファ共
有) Backup datapath
RC VSA ST
RC VSA ST
ST
ST
Prediction datapath
Prediction datapath
面積評価のフロー
1.
オリジナルルータ, 予測ルータ(独立), 予測ルータ(共有) を Verilog-HDLで実装
2.
各種ルータを ASPLA 90nm ライブラリで合成 (Design Compiler)
3.
各種ルータのゲート数をカウント
面積評価: ルータのゲート数を比較
• 予測ルータ(バッファ独
立)Backup datapath
• 予測ルータ(バッファ共
有) Backup datapath
RC VSA ST
RC VSA ST
ST
ST
Prediction datapath
Prediction datapath
仮想チャネル数1
仮想チャネル数2
+53.1%
+21.9%
+57.2%
+23.4%
オリジナルバッファ共有バッファ独立
オリジナルバッファ共有バッファ独立
バッファ共有方式によって,
面積の増分を
21.9%～23.4%増に低減
電力評価: フリット転送エネルギーを比較
• 予測ルータ(Stop機構無)
• 予測ルータ(Stop機構有)
Stop!!
Backup datapath
RC VSA ST
RC VSA ST
ST
ST
Prediction datapath
Prediction datapath
電力評価のフロー
1.
オリジナルルータ, 予測ルータ(stop有), 予測ルータ(stop無) をVerilog-HDLで実装
2.
各種ルータを ASPLA 90nm で合成, 配置配線 (Design Compiler / Astro)
3.
配置配線ルータにパケット負荷を与えるシミュレーションを実行 (NC-Verilog)
4.
SAIF, SDF, SPEF を読み込んで消費電力を見積もる (Power Compiler)
電力評価: フリット転送エネルギーを比較
• 予測ルータ(Stop機構無)
• 予測ルータ(Stop機構有)
Stop!!
Backup datapath
RC VSA ST
RC VSA ST
ST
ST
Prediction datapath
仮想チャネル数1
Prediction datapath
仮想チャネル数2
+26.8%
+10.0%
+26.2%
+8.8%
オリジナル
Stop有 Stop無リンク0.7mm
オリジナル Stop有 Stop無リンク0.7mm
Stop機構によって,
転送エネルギー増分を
8.8%～10.0%増に低減
遅延評価: 無負荷時の通信レイテンシ
• 比較対象
– オリジナルルータ
(Conv)
100%的中
– 予測ルータ(ideal) 直進予測
– 予測ルータ(SS) 直前予測
– 予測ルータ(LP)
• 無負荷時の遅延モデル
PktSize  hd
L

LinkBW
Tlink (d  1)  (Tr  Ta  Ts )d
Tr …ルーティング遅延
Ts …スイッチ遅延
Ta …アービトレーション遅延 Tlink …リンク遅延
h
…ヘッダサイズ
d
…ホップ数
Tr  0,Ta  0,Ts  1
予測失敗時 Tr  1,Ta  1,Ts  1
予測成功時
予測成功率は [鯉渕,SACSIS’08]
の値を使用
遅延評価: 無負荷時の通信レイテンシ
– オリジナルルータ
(Conv)
100%的中
– 予測ルータ(ideal) 直進予測
– 予測ルータ(SS) 直前予測
– 予測ルータ(LP)
[nsec]
• 比較対象
• 評価パラメータ
トポロジ
ルーティング
パケット長
トラフィック
動作周波数
k-ary 2-cube (k=3…17)
次元順 (XY routing)
16-flit
ユニフォームランダム
通常ルータ: 470.0MHz
予測ルータ: 464.8MHz
ノード数 vs. 通信レイテンシ
予測によって, 通信遅延は 64コアで14.2%減, 289コアで23.7%減
まとめ: 予測ルータアーキテクチャ
• 予測機構を持つ低遅延ルータ
[吉永,SACSIS’07]
– 予測にもとづき RC と SA ステージをプレ実行
– 予測が当たれば ST ステージだけ (1サイクル転送)
これまで予測ルータのアーキテクチャの詳細はカバーしてない
• 本発表では,予測ルータのアーキテクチャを検討
– バッファ共有方式
– Stop 機構
– Kill 機構 (今回は未実装)
Stop!!
RC VSA ST
• 評価結果
– 通信遅延を 14.2%～23.7% 削減
– 面積オーバヘッドは 23.4%
– エネルギーオーバヘッドは10.0%
ST
実装のさらなる改善, 他の低遅延ルータとの定量的な比較が必要
ご清聴ありがとうございました

Download Report