オンチップトーラス網における

オンチップトーラス網における
仮想チャネルフリールーティング
松谷宏紀 (慶大)
鯉渕道紘 (NII)
天野英晴 (慶大)
Network-on-Chip (NoC)
• タイルアーキテクチャ
– 演算要素, ルータ
– パケット転送
タイル(RISC, DSP, RAM, I/O)
○ 利点
• 配線遅延
– グローバル配線
– 固定長, 隣接タイル間
• 各タイルごとの標準I/F
0
1
2
– モジュラリティ
3
4
5
× 欠点
6
7
8
• オーバヘッド
e.g., RAW [Taylor, IEEE Micro’02]
大規模化するSoCにおいて,
aSoC [Liang, IEEE TVLSI’04] 短TATを実現する設計法として注目
NoCの例～Viterbi Decoder on 4x4 NoC～
(0)
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
SISO Viterbi Decoder のタイルマッピング例
• 設計フロー
–
–
–
–
シミュレーション
通信パターン解析
マッピング
ルーティング
NoCの例～Viterbi Decoder on 4x4 NoC～
(0)
(2)
(3)
FIFO 0
FIFO 1
(4)
(1)
Make
Path
Metric
(5)
(6)
(7)
FIFO 2
FIFO 3
DELTA
(8)
(9)
Trace
Back 0
(11)
Trace
Back 1
(12)
Trace
Back 2
(13)
Trace
Back 3
(14)
Soft Out
Trace
Back 1
Soft Out
Trace
Back 2
Soft Out
Trace
Back 3
Add
Compare
Select
(10)
Soft Out
Trace
Back 0
(15)
SISO Viterbi Decoder のタイルマッピング例
• 設計フロー
–
–
–
–
シミュレーション
通信パターン解析
マッピング
ルーティング
NoCの例～Viterbi Decoder on 4x4 NoC～
(0)
(2)
(3)
FIFO 0
FIFO 1
(4)
(1)
Make
Path
Metric
(5)
(6)
(7)
FIFO 2
FIFO 3
DELTA
(8)
(9)
Trace
Back 0
(11)
Trace
Back 1
(12)
Trace
Back 2
(13)
Trace
Back 3
(14)
Soft Out
Trace
Back 1
Soft Out
Trace
Back 2
Soft Out
Trace
Back 3
Add
Compare
Select
(10)
• 設計フロー
–
–
–
–
シミュレーション
通信パターン解析
マッピング
ルーティング
Soft Out
Trace
Back 0
(15)
SISO Viterbi Decoder のタイルマッピング例
(ルータ面積)
(ルータ + コア面積)
≒ 34%
NoCにおいてはルータの面積を極力小さくする必要がある
2Dトーラス
v.s 2Dメッシュ
サイクルが
形成
○ トーラスの利点
• 高性能・低遅延
– メッシュの2倍の帯域
– 平均ホップ数 (小)
× トーラスの欠点
• 高コスト
– 総ワイヤ長が2倍
– 消費電力 15%増
[Dally, DAC’01]
× トーラスではデッドロック回避のために仮想チャネル機構が必要
仮想チャネルの実装コスト
Buf
Buf
Input Ports
Crossbar
Output Ports
仮想チャネルの実装コスト
Buf
Buf
仮想チャネルごとに
バッファとコントローラ
[Chien, TPDS’98]
Buf
Buf
Input Ports
Crossbar
Output Ports
仮想チャネル割り当てのアービトレーション
データパスの複雑化, パイプライン段の増加
仮想チャネルフリー化  トーラスによる高性能 & シンプルなルータ
既存の仮想チャネルフリー技術
Bubble Flow Control
Eject-and-Reinjection
[Flich, TPDS’02]
[Puente, ICPP’99]
• パケットの注入制限
– サイクルができないよう
– パケットの注入を制限
• 中継ノードでの再注入
– 中継ノードの前後で
– サイクルを断ち切る
中継ノード
Bubble
×欠点
– パケットを溜め込む
– バッファ量 (多)
×欠点
Eject
Reinject
– 再注入の遅延
– NoCでは遅延の影響 (大)
NoC向けに, 通信パターンを解析した上で利用できる軽量な方法を
提案～NoC向け仮想チャネルフリー技術～
• 次元順ルーティング
– 最短経路のみ
– 仮想チャネル機構
NoCでは正味使われる
通信を特定可能
• 非最短経路を導入
– 進行方向を一部反転
– 代替経路の数を増やす
• 増えた代替経路の中から…
– 仮想チャネルフリー経路集合
– 効率的に探索
Wrap-aroundチャネルをす
べての通信が使わない場合
通信パターンはメッシュと等価
仮想チャネルフリーな経
路集合は常に存在
デッドロックフリー経路集合の探索
• 最適な経路集合
– 仮想チャネルフリー
＠トーラス
– 平均ホップ数最短
C=1
n1n2
C=11
C=5
C=8
n1n6
Stop!
• 全数探索
– 9～64ノード
– 平均ホップ数計算
– デッドロック検出
• 枝刈りによる高速化
C=10
C=8
C=10
C=12
n4n10
Stop!
C=12
C=10
C=13
n9n10
– 分枝限定法
デッドロックフリー, かつ, 平均ホップ数が最小な経路集合を探索
デッドロック検出アルゴリズム
ある経路集合
が与えられる
4  5  6  10  14
7451
567
11  10  9  5  1
674
・・・・・・・
通信パターン
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
デッドロック検出アルゴリズム
ある経路集合
が与えられる
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
4  5  6  10  14
7451
Y+
Deadlock を検出 !!
別の経路集合を探索
0
1
2
3
0
1
2
3
4
5
6
7
4
5
6
7
8
9
10 11
8
9
10
11
Deadlock!
12 13 14 15
567
12 13 14 15
11  10  9  5  1
0
1
2
3
0
1
2
3
4
5
6
7
4
5
6
7
8
9
10 11
8
9
10
11
674
Y-
X+
X-
・・・・・・・
12 13 14 15
通信パターン
12 13 14 15
16ノードビットマップ (X+, X-, Y+, Y-
デッドロック検出アルゴリズム
次の経路集合
を評価
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
4  7  6  2  14
7651
Y+
Deadlock を検出 !!
別の経路集合を探索
0
1
2
3
0
1
2
3
4
5
6
7
4
5
6
7
8
9
10 11
8
9
10
11
547
12 13 14 15
12 13 14 15
11  8  9  13  1
0
1
2
3
0
1
2
3
4
5
6
7
4
5
6
7
8
9
10 11
8
9
10
11
654
Y-
X+
X-
・・・・・・・
12 13 14 15
12 13 14 15
仮想チャネルフリー,
かつ, 平均ホップ数が最小な経路集合を発見
通信パターン
16ノードビットマップ (X+, X-, Y+, Y-
デッドロックフリー経路集合の探索
• 最適な経路集合
– 仮想チャネルフリー
＠トーラス
– 平均ホップ数最短
C=1
n1n2
C=11
C=5
C=8
n1n6
Stop!
• 全数探索
– 9～64ノード
– 平均ホップ数計算
– デッドロック検出
• 枝刈りによる高速化
– 分枝限定法
C=10
C=8
C=10
C=12
n4n10
Stop!
C=12
C=10
C=13
n9n10
最適な経路集合
デッドロックフリー, かつ, 平均ホップ数が最小な経路集合を探索
評価項目
1. ルータの面積評価
2. 仮想チャネルフリールーティングの性能
3. 探索時間
面積評価～仮想チャネル省略による面積削減～
• ルータ面積を比較
– DOR + v1
– DOR + v2
– DOR + v1 + N
• 実装環境
– Verilog-HDL
– Design Compiler
– 0.35um Library
仮想チャネルフリールーティング用
Buf
Buf
Buf
Buf
Input Ports
Crossbar
Output Ports
面積評価～仮想チャネル省略による面積削減～
No VC
提案ルータ
2 VCs
仮想チャネルルータの 50.7% の面積 (バッファ量削減, パイプライン段数削減)
性能評価
～シミュレーション環境～
• スループットを比較
– Mesh + v1
– Torus + v2
– Torus + v1 + N
0
1
2
3
4
5
6
7
8
9
10
11
12
13
仮想チャネルフリールーティング
• 通信パターン
–
–
–
–
–
–
Viterbi (16)
BT (9, 16, 36, 64)
SP (9, 16, 36, 64)
CG (16, 32, 64)
MG (16, 32, 64)
IS (16, 32, 64)
Router
14
15
Core
パケットサイズ
16 flit (1 flit ヘッダ)
バッファサイズ
1 flit 分
パケット転送方式
Wormhole方式
パケット転送時間
3 cycle / 1 hop
性能評価～仮想チャネル無しで性能はでるか～
• Viterbi (16)
– ストリーム処理
• BT (36), SP(36)
– 隣接間通信が多い
Viterbi (16-node)
• スループットを比較
– Mesh+v1
– Torus+v2
– Torus+v1+N
BTトラフィック (36-node)
性能評価～仮想チャネル無しで性能はでるか～
• CG(32), MG(32)
– BT より平均ホップ数(大)
• IS (32)
– All-to-All 通信を含む
• スループットを比較
– Mesh+v1
– Torus+v2
– Torus+v1+N
CGトラフィック (32-node)
ISトラフィック (32-node)
18種中11種で
Torus+v2 並の性能. IS(all-to-all)では
Mesh+v1 並
経路集合の探索時間
トレース
Viterbi(16
)
時間(秒)
0.005
トレース
CG(16)
時間(秒)
0.011
BT(9)
0.014
CG(32)
0.196
BT(16)
0.030
CG(64)
0.298
BT(36)
4.798
MG(16)
0.011
BT(64)
1.018
MG(32)
5.354
SP(9)
0.015
MG(64)
0.427
SP(16)
0.011
IS(16)
0.865
SP(36)
5.404
IS(32)
19.901
SP(64)4 2.6GHz
0.130
IS(64)
3600.000
※Pentium
※カッコ内の数字はノード数を表す
IS(all-to-all)を除き, 経路の探索時間は無視できるほど小さい
まとめ
• 本研究の目的
– トーラスによる高性能
– 仮想チャネル不要なシンプルなルータ
NoCでは通信パターンが既知
• 仮想チャネルフリールーティング
– 次元順ルーティングに非最短経路を導入
– デッドロックフリー経路集合を全数探索
• スループット
– 18種中11種のトレースで, 仮想チャネルルータ並の性能
• ルータ面積
– 仮想チャネルルータの約半分 (バッファ量削減, パイプライン段数削減)
動的トラフィック (例：制御パケット, 同期)
• 中継ノードでの再注入
[Flich, TPDS’02]
– 中継ノードの前後で
– サイクルを断ち切る
中継ノード
Eject
Reinject
• 再注入の遅延
– 動的トラフィックの量が少なければ影響は小さい
Head-of-Line (HoL) Blocking
• 仮想チャネルの効能
– デッドロックフリー
– HoL Blocking の緩和
影響は小さいと考えられる
• HoL blocking 緩和効果が小さい理由
– ネットワークが小規模
– 固定型ルーティングでは, 仮想チャネル切り替えは
限定的 (主に適応型ルーティングで影響が出る)
提案～NoC向け仮想チャネルフリー技術～
• 次元順ルーティング
– 最短経路のみ
– 仮想チャネル機構
NoCでは正味使われる
通信を特定可能
• 非最短経路を導入
– 進行方向を一部反転
– 代替経路の数を増やす
• 増えた代替経路の中から…
– 仮想チャネルフリー経路集合
– 効率的に探索
Wrap-aroundチャネルをす
べての通信が使わない場合
通信パターンはメッシュと等価
仮想チャネルフリーな経
路集合は常に存在
Network-on-Chip (NoC)
• 通信パターンに合わせたルーティング
• 組込みシステム設計
– Cレベル設計
– シミュレーション
(2)
(1)
(2)
(3)
(4)
(2)
アプリケーションのタスクフロー
(1)
(2)
(2)
(2)
(4)
(3)
NoCの物理タイル

Download Report