Document

メニーコアにおけるタスクの移動を
支援する
On-chip micro mobility プロトコル
松谷宏紀 (慶大)  東大
鯉渕道紘 (ＮＩＩ)
天野英晴 (慶大)
半導体プロセスの進歩により…
• マルチコア・プロセッサ
– バス結合
– E.g., ARM AMBA
PU
PU
PU
Cache
Cache
Cache
×コア数が増えるとバスがボトルネック
半導体プロセスの進歩により…
• マルチコア・プロセッサ
– バス結合
– E.g., ARM AMBA
• メニーコア・プロセッサ
– スイッチ (ルータ) 結合
– Network-on-Chip (NoC)
PU
PU
PU
PU
PU
PU
Cache
Cache
Cache
Cache
Cache
Cache
PU
PU
PU
Cache
Cache
Cache
PU
PU
PU
Cache
Cache
Cache
×コア数が増えるとバスがボトルネック
半導体プロセスの進歩により…
• マルチコア・プロセッサ
– バス結合
– E.g., ARM AMBA
PU
PU
PU
Cache
Cache
Cache
• メニーコア・プロセッサ
– スイッチ (ルータ) 結合
– Network-on-Chip (NoC)
R
R
R
R
R
R
R
R
R
×コア数が増えるとバスがボトルネック
メニーコアの問題点: 負荷の集中
• アプリの実行
– 並列化による負荷分散 (理想)
– 逐次的な処理も多い (現実)
• 負荷の集中
– 局所的な温度上昇
– リーク電力の急増
アプリケーション
(MPEG, AES, …)
Task
(参考) 温度とリーク電力
• OpenSPARC T1
• 1-core SPARC を合成
– 8-core SPARC
– 64-bit
–
–
–
–
キャッシュ無し
Design Comipler
温度 25C, 75C, 125C
200 MHz
Core Core Core Core L2 $
Core
Crossbar SW
L2 $
Core Core Core L2 $ L2 $
Sun T1 (コア8個,各コア4スレッド)
[Kongetira, micro’05]
• プロセスライブラリ
– Nangate 45nm FreePDK
– ASU 45nm PTM ベース
– 温度を変えて再キャラクタ
ライズ
– LibertyNCX & HSPICE
(参考) 温度とリーク電力
• OpenSPARC T1
– 8-core SPARC
– 64-bit
Core Core Core Core L2 $
Core
Crossbar SW
L2 $
Core Core Core L2 $ L2 $
Sun T1 (コア8個,各コア4スレッド)
[Kongetira, micro’05]
Power Consumption [mW]
• 1-core SPARC を合成
– キャッシュ無し
350
– Design Comipler
300
– 25C, 75C, 125C
250
– 200 MHz
200
150
温度が高くなるとリークが増加
• プロセスライブラリ
100
– Nangate 45nm FreePDK
50
– ASU 45nm PTM ベース
0
– 温度を変えてキャラクタラ
25
75
125
イズ Temperature [C]
– LibertyNCX
& HSPICE
Static Dynamic
メニーコアの課題: 負荷の集中
• アプリの実行
– 並列化による負荷分散 (理想)
– 逐次的な処理も多い (現実)
• 負荷の集中
– 局所的な温度上昇
– リーク電力の急増
アプリケーション
(MPEG, AES, …)
Task
メニーコアの課題: 負荷の集中
• アプリの実行
– 並列化による負荷分散 (理想)
– 逐次的な処理も多い (現実)
• 負荷の集中
– 局所的な温度上昇
– リーク電力の急増
• Power density 均一化
– 負荷の分散
– タスクの動的な移動
Task
メニーコアの課題: 負荷の集中
• アプリの実行
– 並列化による負荷分散 (理想)
– 逐次的な処理も多い (現実)
• 負荷の集中
– 局所的な温度上昇
– リーク電力の急増
Task
• Power density 均一化
– 負荷の分散
– タスクの動的な移動
メニーコアの課題: 負荷の集中
• アプリの実行
– 並列化による負荷分散 (理想)
– 逐次的な処理も多い (現実)
• 負荷の集中
– 局所的な温度上昇
– リーク電力の急増
• Power density 均一化
– 負荷の分散
– タスクの動的な移動
Task
メニーコアの課題: 負荷の集中
• アプリの実行
– 並列化による負荷分散 (理想)
– 逐次的な処理も多い (現実)
• 負荷の集中
– 局所的な温度上昇
– リーク電力の急増
Task
• Power density 均一化
– 負荷の分散
– タスクの動的な移動
タスクの移動に伴う問題点
• 着信可能性
• Task
A の移動前
• Task A の移動後
– Task A がどのコアの上で動作していても
A”
– 他のタスクと通信中
– 今まで Task“Task
A と通信して
でアクセス可能
たタスクたちはどうする?
• 移動透過性
– Task A が動的に移動しても通信が途切れない
Task A
???
Task A
NoC におけるタスクマイグレーション  Mobile IP を使ってみては?
Mobile IP とは?
• Mobile IP (Mobile IPv6)
– 移動体通信のための IP protocol の拡張
– RFC 3344 (Mobile IPv4), RFC 3775 (Mobile IPv6)
– 移動するノード (MN) がどのネットワークに接続していても,
同じ IP アドレスで識別, 通信できる
• 用語のまとめ
– Mobile node (MN):
移動するノード
– Corresponding node (CN): MN と通信するノード
– Home agent (HA):
MNが外部にいる際のプロキシ
2001:xxx::11
2001:xxx::/64
2001:ooo::/64
Mobile IP とは?
• Mobile IP (Mobile IPv6)
– 移動体通信のための IP protocol の拡張
– RFC 3344 (Mobile IPv4), RFC 3775 (Mobile IPv6)
– 移動するノード (MN) がどのネットワークに接続していても,
同じ IP アドレスで識別, 通信できる
• 用語のまとめ
– Mobile node (MN):
移動するノード
移動先ネットワーク
(2001:ooo::/64)
においても
– Corresponding
node (CN):
MN と通信するノード
– Home
agent
MNが外部にいる際のプロキシ
もとの
IP (HA):
アドレス (2001:xxx::11)
でアクセス可能
2001:xxx::11
2001:xxx::/64
2001:ooo::/64
発表の流れ: On-Chip Micro Mobility
• メニーコア
– 多数のプロセッサ + スイッチ結合
• タスクの動的な移動
– Power density の均一化
– タスクを別のコアへ移動させる
• On-chip micro mobility プロトコル
– タスクの移動透過性 + 着信可能性
– Mobile IP を単純化
• On-chip micro mobility の設計
– NI としてハードウェア化
– 予備評価
Micro mobility: 利用のシナリオ
• Task A @ Tile 3
• Task A @ Tile 5
– Task B と通信中
– Tile 3 から Tile 5 へ移動
Tile 0
– Micro mobility によって
– Task B との通信を継続
Corresponding
Task
Tile 1
Tile
2 (CT)
Task B
Tile 3
Tile 4
Task A
Task A
Tile 6
Tile 5
Tile 7
Tile 8
Mobile Task (MT)
Mobility によって MT の物理アドレスが変化しても CT は通信を継続
Micro mobility: Mobile Task @ Home
• Home
– 各 MT はどこかのタイル
を “Home” とする
• Home Agent (HA)
– 各 MT の home ルータに
置くプロキシ
• Task A @ Tile 3(home)
– Task B との通信に Micro
mobility を使う必要なし
Tile 0
Tile 1
Tile 2
Tile 4
Tile 5
Task B
• HA の仕事
– MT の現在物理アドレス
(Care-of-Address, CoA)
を管理
– MT 宛てのパケットを
CoA へ転送
Tile 3
Task A
Tile 6
HATile
for 7Task A Tile 8
MT が home にいるとき, Corresponding Task (Task B) と直接通信
Micro mobility: Mobile Task の移動
• タスク移動前
– MT は HA に Binding
Update (BU) を送信
– MT の移動先アドレス
(CoA) を通知
タスクの移動中
(MT 宛てのパケットは HA
がバッファリングする)
• Task A @ Tile 0
– Tile 2 に移動前
– 新しい CoA = Tile 2
Tile 0
Tile 2
Task A
Tile 3
Tile 4
Tile 5
BU (CoA = Tile 2)
Tile 6
HATile
for 7Task A Tile 8
• タスク移動後
– MT は HA に Binding
Ack (BA) を送信
– MT の移動完了を通知
Tile 1
Home Agent (HA) は, Mobile Task (MT) の現在位置 (CoA) を管理
Micro mobility: Mobile Task の移動
• タスク移動前
– MT は HA に Binding
Update (BU) を送信
– MT の移動先アドレス
(CoA) を通知
タスクの移動中
(MT 宛てのパケットは HA
がバッファリングする)
• Task A @ Tile 2
– Tile 2 に移動後
– 移動完了の通知 (BA)
Tile 0
Tile 2
Task A
Tile 3
• タスク移動後
– MT は HA に Binding
Ack (BA) を送信
– MT の移動完了を通知
Tile 1
Tile 4
Tile 5
BA (CoA = Tile 2)
Tile 6
HATile
for 7Task A Tile 8
Home Agent (HA) は, Mobile Task (MT) の現在位置 (CoA) を管理
Micro mobility: 移動後 CT との通信
• CT から MT へ転送
– CT は MT の現在位置を
考えずに
– MT の homeである Tile 3
にパケットを送信
• Task B から A への転送
– 常に Tile 3 宛てに送信
– HA にて CoA 宛てに転送
Tile 0
Tile 1
Tile 2
Task A
• HA による転送
– MT 宛てパケットは Tile 3
に到達
– これを現在の CoA である
Tile 2 へ転送
Tile 3
Tile 6
Tile 4
Tile 5
Tile 7 to Task
TileA 8
Packet
Task B
MT 宛てのパケットは常に HA を経由  スループットのボトルネック!
Micro mobility: Route optimization (RO)
• CT から MT へ転送 (1)
– HA にて中継される
– RO されていない
• CT への BU 送信
– RO されていないパケット
を受信したら
– 送り主 (CT) に CoA 通知
• CT から MT へ転送 (2)
– 直接, MT の CoA に転送
• Task A (MT) において,
– RO されていないパケット
を受信
Tile 0
Tile 1
Tile 2
Task A
Tile 3
Tile 6
Tile 4
Tile 5
Tile 7 to Task
TileA 8
Packet
Task B
Micro mobility: Route optimization (RO)
• CT から MT へ転送 (1)
– HA にて中継される
– RO されていない
• CT への BU 送信
– RO されていないパケット
を受信したら
– 送り主 (CT) に CoA 通知
• CT から MT へ転送 (2)
– 直接, MT の CoA に転送
• Task A (MT) において,
– 送り主 (Task B) に BU を
送信
Tile 0
Tile 1
Tile 2
Task A
Tile 3
Tile 6
Tile 4
Tile 5
7 = TileTile
BUTile
(CoA
2) 8
Task B
Micro mobility: Route optimization (RO)
• CT から MT へ転送 (1)
– HA にて中継される
– RO されていない
• CT への BU 送信
– RO されていないパケット
を受信したら
– 送り主 (CT) に CoA 通知
• CT から MT へ転送 (2)
– 直接, MT の CoA に転送
• Task A (MT) において,
– Task B に BU を送信
– 以後, Task B と直接通信
Tile 0
Tile 1
Tile 2
Task A
Tile 3
Tile 6
Tile 4
Tile 5
Tile 7 to Task
TileA 8
Packet
Task B
Task A がさらに移動する場合は, CT の bindingを消去する必要あり
Micro mobility: Route optimization (RO)
• RO されていない通信
– Task B  Task A
– 必ず HA を経由
Tile 0
Tile 1
Tile 2
• RO された通信
– Task B  Task A
– HA を経由せず直接通信
Tile 0
Tile 1
Task A
Tile 3
Tile 4
Tile 2
Task A
Tile 5
Tile 3
Tile 7 to Task
TileA 8
Packet
Tile 6
Tile 4
Tile 5
Bottleneck!
Tile 6
Task B
Tile 7 to Task
TileA 8
Packet
Task B
Route optimization (RO) することでスループット性能を大幅に改善
Micro mobility: HA 経由の通信 (補足)
• RO されていない通信
– MT 移動後, 最初の通信は必ず HA 経由になる (その後 RO)
– HA 経由の通信により禁止ターンが生じる  デッドロック
Tile 0
Tile 1
Tile 2
Tile 0
Tile 1
Task A
Tile 3 仮想チャネルの切替え
Tile 4
Tile 5
Tile 2
Task A
Tile 3
Tile 4
Tile 5
禁止ターン
Tile 6
Tile 7 to Task
TileA 8
Packet
Task B
Tile 6
Tile(CoA=Tile
7
Tile
BU
2) 8
Task B
CTからHA は VC0, HA から MTは VC1を使用  デッドロックフリー
On-chip network mobility
• 階層構造を持つトポロジ
– Fat Tree
– Fat H-Tree
– Concentrated Mesh
クラスタ構造 (近傍同士はク
ロスバで密に結合)
On-chip network mobility
• 階層構造を持つトポロジ
– Fat Tree
– Fat H-Tree
– Concentrated Mesh
• クラスタ単位のタスク移動
– Micro mobility を拡張
– クラスタ (network) 単位で
タスクが移動
クラスタ構造 (近傍同士はク
ロスバで密に結合)
On-chip network mobility プロトコルについては予稿集をご覧下さい
発表の流れ: On-Chip Micro Mobility
• メニーコア
– 多数のプロセッサ + スイッチ結合
R
R
R
R
R
R
R
R
R
• タスクの動的な移動
– Power density の均一化
– タスクを別のコアへ移動させる
• On-chip micro mobility プロトコル
– タスクの移動透過性 + 着信可能性
– Mobile IP を単純化
• On-chip micro mobility の設計
– NI としてハードウェア化
– 予備評価
Network interface (NI) は, コ
アとルータのインタフェイス
Wormhole ルータの構造
• 5入力5出力の wormhole ルータ; NI 付き
ARBITER
VC0
X+
X+
VC1
X-
X-
Y+
Y+
Y-
Y-
NI
5x5 XBAR
パケット生成
コア (プロセッサ & キャッシュ)
Network interface (NI)
NI
Network interface (NI) の構造
• 5入力5出力の wormhole ルータ; NI 付き
ARBITER
パケット化
(ヘッダ付与)
脱パケット化
(ヘッダ削除)
Network interface (NI)
Core
Core
Micro mobility の設計: CT 側の機能
• 5入力5出力の wormhole ルータ; NI 付き
ARBITER
MT アドレスと実際のアドレス
コアから MT 宛てのパケットを
Binding update list (BUL)
(CoA) の対応付け表
受け取ったら, BC をひいて対
N(log2N + 1)-bit のビットマップ
BU を送った CT のリスト
応する CoA 宛てに変換
Binding cache (BC)
MT の現在アドレス (CoA)
Network interface (NI)
CTがBCを持たないと,
Core MTとの通信はHA経由の非最短経路になる
Core
Micro mobility の設計: MT 側の機能
• 5入力5出力の wormhole ルータ; NI 付き
ARBITER
N-bit のビットマップ
(N はノード数)
BU を送ったCT は 1
Binding update list (BUL)
BU を送った CT のリスト
Binding cache (BC)
MT は移動直前に BUL 内の CT に対して
現在の CoA を無効化 (BU 送信) する
Network interface (NI)
MTがBULを持たないと,移動する度に
HA経由の非最短経路が発生
Core
Core
Micro Mobility の設計: HA 側の機能
• 5入力5出力の wormhole ルータ; NI 付き
ARBITER
受信したパケットが MT 宛て
Binding update list (BUL)
なら,現在の CoA に転送
BU を送った CT のリスト (VC の切替が発生)
Binding cache (BC)
MT の現在アドレス (CoA)
Network interface (NI)
MT 宛てパケットをMTの代わりに受信し,
MTの現在の
Core
CoreCoA へ転送
予備評価: Route optimization の効果
• Task B から Task A
– RO しない経路(HA 経由)
– RO する経路 (直接)
Tile 0
Tile 1
Tile 2
Task A
Tile 3
Tile 6
Tile 4
Tile 7
Task B
Tile 5
Tile 8
• ネットワーク環境
– k x k mesh
– MT の HA が一様に分散
• 平均ホップ数
2k
H
3
– RO しないと 2倍に増加
– 遅延・消費電力が悪化
• スループット  ideal  bC
NH
– RO しないと最悪 1/2 に
予備評価: BC & BUL のハードウェアコスト
• Binding の管理
• ネットワーク環境
– Binding cache (BC)
– Binding update list (BUL)
– 無いと RO できない
• ルータのハードウェア量
– N ノード (k x k mesh)
– 各ノードが通信相手
すべての CoA を管理
• BC のハードウェア量
– バッファサイズが支配的
– (p v 一度に通信する通信相手は少
w d) bit
ない  BC サイズを減らせる
ポート数 p=5, 仮想チャネル数 v=1 •
データ幅 w=64, FIFO深さ d=4
– BC と BUL を持たせると
どれだけ増えるか?
– 通信相手の CoA を保持
– N (log2 N +1) bit
BUL のハードウェア量
– BU 送信済みの CT
– N bit
N=16 のときオーバヘッドは 3.8% 増, N=64 のとき 20.0% 増, …
まとめ: On-Chip Micro Mobility
• メニーコアにおけるタスクの動的な移動
– Power density の均一化
– タスクを別のコアへ移動させる
• On-chip micro mobility プロトコル
– タスクの移動透過性 + 着信可能性
– Mobile IP を単純化
• On-chip micro mobility の設計
– NI としてハードウェア化
– 予備評価
• 今後の課題
– Micro mobility をサポートした NI の実装 (45nm CMOS)
– OpenSPARC T1 を用いた温度とリーク電力の評価
ご清聴ありがとうございました

Download Report