Prediction router

低遅延オンチップネットワークの
ための予測ルータの評価
松谷
宏紀
(慶大)
予測ルータの設計・実装 [松谷,5月ICD/ARC研]
(NII)
今回の発表では, 鯉渕道紘
– 複数の予測アルゴリズムを装備,
トラフィックに応じて切換え
天野英晴 (慶大)
– 実タイルアーキテクチャを想定した 4つのcase studyで評価
吉永努 (電通大)
はじめに: Network-on-Chip (NoC) について
• メニーコア・アーキテクチャ
– 多数のコア (プロセッサ, キャッシュ)
– チップ内のパケット転送ネットワーク
FP
MEM MAC
80 tiles
router
FP
MAC
[Dally, DAC’01]
router
router
router
router
router
router
router
router
router
Single tile
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*
WH, no VC
Credit
QuickSilver ACM
H-Tree (32bit)
Up*/down*
1-flit, no VC
Credit
UMass Amherst
aSOC
2-D mesh
Sun T1
Crossbar (128bit)
Cell BE EIB
Ring (128bit)
Shortest-path Pipelined CS,
no VC
Timeslot
コアの数はますます増加
Handshake
(例: 64コア,
80コア,
Shortest-path
Pipelined
CS, …)Credit
no VC
宛先まで何ホップもかかる
YX DOR
1-flit, no VC
On/off
TRIPS
(operand)
2-D mesh
(109bit)
TRIPS (on-chip)
2-D mesh
(128bit)
YX DOR
WH, 4 VCs
Credit
Intel SCC
2-D torus (32bit)
XY,YX DOR,
odd-even TM
WH, no VC
Stall/go
通信遅延の影響が増大
2-D mesh (32bit)
Intel 80-core
Source
WH, 2 lanes
On/off
オンチップルータのパイプライン構造を工夫して通信遅延を削減しよう
発表の流れ: 予測ルータによる低遅延通信
• 既存のオンチップルータ
– Speculative ルータ
– Look-ahead ルータ
– Bypassing ルータ
• 予測ルータ
– アーキテクチャ, 予測アルゴリズムいろいろ
• 評価項目
– 予測ヒット率, ハードウェア量, 消費エネルギー
• Case study
–
–
–
–
[1] 2次元メッシュ (細粒度 ALU ネットワーク)
[2] 2次元メッシュ (粗粒度 CMP ネットワーク)
[3] Fat tree ネットワーク
[4] Spidergon ネットワーク
オンチップルータ: ハードウェア構成
• 5入力5出力の WH ルータ, データ(フリット)幅は 64-bit
ARBITER
X+
FIFO
X+
X-
FIFO
X-
Y+
FIFO
Y+
Y-
FIFO
Y5x5 XBAR
CORE
FIFO
CORE
入力パケットは,バッファリング&経路計算され,適切な出力チャネルから出力される
Speculative ルータ: VA/SA を並列実行
• 衝突しなければ 3 cycle でヘッダがルータを通過
– RC (Routing computation)
– VSA (Virtual channel / switch allocation)
VA と SA を投機的に
– ST (Switch traversal)
並列実行
• 例) ルータ(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を実行できる
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
ルータ(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サイクル転送
@Router A
@Router B
@Router C
NRC
ST
VSA
NRC
ST
VSA
NRC
ST
VSA
HEAD
W. Dally, “Principles
and Practices of
Interconnection
Networks” (2004)
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: 非隣接ルータ間に仮想的なバイパス経路
[Kumar,ISCA’07]
– Dynamic Fast Path: SA パケットを先行させる
[Park, HOTI’07]
– 隣接間通信が多いと効果が薄い
• 頻繁に使う経路の低遅延化 (4ホップのとき)
3-cycle
1-cycle
1-cycle
1-cycle
SRC
DST
• 頻繁に使う経路の低遅延化 (2ホップのとき)
3-cycle
SRC
3-cycle
1-cycle
3-cycle
DST
Bypassingルータ: 一部ステージをスキップ
• バイパス方法1 – 頻繁に使うパスを低遅延化
– Express VC: 非隣接ルータ間に仮想的なバイパス経路
[Kumar,ISCA’07]
– Dynamic Fast Path: SA パケットを先行させる
[Park, HOTI’07]
– 隣接間通信が多いと効果が薄い
• バイパス方法 2 – 次元順ルーティングの規則性を利用
– Mad Postman: 上から来たら下, 右から来たら左へ即転送
– 転送後に RC と VSA を行い, 間違っていたらリカバリ
[Izu, PDP’94]
– 隣接間通信が多いと効果が薄い
• バイパス方法 3 – ユーザ指定の特定パスを低遅延化
– Preferred Path:クロスバを経由しない高速パス [Michelogiannakis,
NOCS’07]
– DBP: リング状に張った高速パス [鯉渕, NOCS’08]
– どのパスを高速化するかをユーザが指定しないといけない
どれが良いかはケースバイケース予測アルゴリズムは1個では不足
発表の流れ: 予測ルータによる低遅延通信
• 既存のオンチップルータ
– Speculative ルータ
– Look-ahead ルータ
– Bypassing ルータ
• 予測ルータ
– アーキテクチャ, 予測アルゴリズムいろいろ
• 評価項目
– 予測ヒット率, ハードウェア量, 消費エネルギー
• Case study
–
–
–
–
[1] 2次元メッシュ (細粒度 ALU ネットワーク)
[2] 2次元メッシュ (粗粒度 CMP ネットワーク)
[3] Fat tree ネットワーク
[4] Spidergon ネットワーク
予測ルータ: 予測に基づいた低遅延ルータ
[吉永,情処論’08]
[鯉渕,情処論’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]
[鯉渕,情処論’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]
[鯉渕,情処論’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]
[鯉渕,情処論’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サイクル転送
– ヒット率が低遅延化の鍵
[吉永,情処論’08]
1. Random
2. Static Straight
1種類では適用範囲が狭い
パケットが直進すると予測
– 予測アルゴリズムを複数装備 3. Custom
– トラフィックやルーティングに
予測ポートをユーザが指定
応じて1サイクルで切り替え可 4. Latest Port
前回と同じポートを予測
HIT HIT
MISS
5. Finite Context Method
RC VSA ST ST ST
頻繁に出現する n個のコン
ST ST ST
テキストパターンで予測
ST ST ST
6. Sampled Pattern Match
ST ST ST
履歴テーブルによるパター
ンマッチング
1
2
3
4
5
6
7
8
予測ルータ: ハードウェア構成
[松谷,HPCA’09]
• チャネルごとに数種類の予測器; 1サイクルで切替え可
Predictors
A
X+
B
C
ARBITER
X+
FIFO
X-
X-
Y+
Y+
Y-
Y-
CORE
5x5 XBAR
CORE
予測ルータ: 予測ヒット時の動作
[松谷,HPCA’09]
• チャネルごとに数種類の予測器; 1サイクルで切替え可
Predictors
A
X+
B
C
ARBITER
Correct
X+
FIFO
予めクロスバを予約
X-
X-
Y+
Y+
Y-
Y-
CORE
5x5 XBAR
CORE
予測がヒットすれば, 予約しておいたポートを使って 1サイクル転送
予測ルータ: 予測ミス時の動作
[松谷,HPCA’09]
• チャネルごとに数種類の予測器; 1サイクルで切替え可
KILL
Predictors
A
X+
B
FIFO
C
ARBITER
Dead flit
X+
Correct
X-
X-
Y+
Y+
Y-
Y-
CORE
5x5 XBAR
CORE
間違って転送されたフリット (dead flit) は出力チャネルで kill される 伝播しない
発表の流れ: 予測ルータによる低遅延通信
• 既存のオンチップルータ
– 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)
NC-Verilog
(simulation)
SDF
SAIF
FIFO
hit
FIFO
XBAR
miss hit
hit
Design compiler
Flit-level net simulation (synthesis)
Fujitsu 65nm library
予測ヒット率・通信遅延
Power compiler
消費エネルギー [pJ / bit]
HW量 (ゲート数)
表2: 設計パラメータ
表1: ルータ／ネットワークのパラメータ
4-flit (1-flit = 64
パケット長
bit)
CMOS プロセス
65nm
供給電圧
1.20V
スイッチング方法
wormhole
温度
25C
チャネルバッファ
4-flit / VC
仮想チャネル(VC) 数
1 – 2VCs
Cycle / hop (通常)
3 stage
1 stage
Cycle
/ hop (予測ヒット)
(※) トポロジ,
トラフィックパターンは後述
表3: 設計 CAD ツール
Design compiler 2006.06
Astro 2007.03
評価項目: 予測ルータの4つの case study
How many cycles ?
FIFO
hit
FIFO
XBAR
miss hit
hit
Design compiler
Flit-level net simulation (synthesis)
Fujitsu 65nm library
予測ヒット率・通信遅延
2-D mesh network
HW量 (ゲート数)
Astro (place and
route)
NC-Verilog
(simulation)
SDF
SAIF
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 2 : 予測ヒット率 @ 8x8 mesh
予測ヒット率 [%]
 1ホップ通信ではヒットせず (LU)
• SS: 直進すると予測
• LP: 同じポートを使うと予測
• FCM: 頻度による予測
7種類のNAS parallel プログラム
4種類の合成トラフィック
Case study 2 : 予測ヒット率 @ 8x8 mesh
予測ヒット率 [%]
 1ホップ通信ではヒットせず (LU)
• SS: 直進すると予測
• LP: 同じポートを使うと予測  繰り返し通信に強い (BT&SP)
• FCM: 頻度による予測
7種類のNAS parallel プログラム
4種類の合成トラフィック
Case study 2 : 予測ヒット率 @ 8x8 mesh
予測ヒット率 [%]
 1ホップ通信ではヒットせず (LU)
• SS: 直進すると予測
• LP: 同じポートを使うと予測  繰り返し通信に強い (BT&SP)
 全体的に高いヒット率
• FCM: 頻度による予測
• 既存の Bypassing ルータでは,
– 予測アルゴリズムは 1種類に固定
[Kumar,ISCA’07] [Park, HOTI’07] [Izu,PDP’94] [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)
ハードウェア量 [kilo gates]
予測アルゴリズムの種類と数に応じて
6.4% ～ 15.9% の増加
• 消費エネルギー
– オリジナルルータ
– 予測ルータ (70%ヒット)
– 予測ルータ (ヒット時)
フリット転送エネルギー [pJ / bit]
予測が外れるとオーバヘッドが大きい
予測が 70% 当たるなら 9.5% の増加
通信遅延は35.8～48.2%減; 面積は6.4%～16%増; 電力は9.5%増
評価項目: 予測ルータの4つの case study
How many cycles ?
FIFO
hit
FIFO
XBAR
miss hit
hit
Design compiler
Flit-level net simulation (synthesis)
Fujitsu 65nm library
Astro (place and
route)
NC-Verilog
(simulation)
SDF
SAIF
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方向
 study
Down 4方向
Case
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 ?
FIFO
hit
FIFO
XBAR
miss hit
hit
Design compiler
Flit-level net simulation (synthesis)
Fujitsu 65nm library
Astro (place and
route)
NC-Verilog
(simulation)
SDF
SAIF
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. 予測ルータは, 複数の予測アルゴリズムを装備することで,
より広範囲なトラフィックパターンに対処可能
Any Questions?
Case study 1 : ルータのクリティカルパス
• RC: 経路計算
• VSA: アービトレーション
• ST: フリット転送
予測ルータではフリット転送も
生じる
ステージの遅延 [FO4s]
通常のルータと比べ, クリ
ティカルパスが 6.2% 増
通常のルータ
予測ルータ (SS)

Download Report