Document

低遅延オンチップネットワーク
のための予測ルータの評価
松谷宏紀 (慶大)  東大
鯉渕道紘 (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

Download Report