計算機アーキテクチャ特論 後半第２回 アウトオブオーダー実行 Out-of-Order Execution

Transcription

1 計算機アーキテクチャ特論 後半第 6 回 NoC Network on Chip 講師加藤真平 本資料は授業用です 無断で転載することを禁じます

2 前回の理解度クイズ 問 1 NVIDIA GPU におけるグリッド ブロック スレッドの関係を簡潔に述べよ 答え GPUアーキテクチャの差異を吸収する抽象概念グリッド : 複数のブロックの集合ブロック : 複数のスレッドの集合スレッド : 実行の最小単位

3 前回の理解度クイズ 問 2 NVIDIA GPU におけるワープの役割を簡潔に述べよ 答え マルチスレッディングにおけるスレッドのグループ 32 個のスレッドをひとまとめにしたものをワープと呼ぶ ワープ単位で実行するスレッドを切り替えることで 1 つ 1 つのスレッドを切り替える場合に比べてオーバヘッドを削減できる

4 前回の理解度クイズ 問 3 NVIDIA GPU の実行手順が正しくなるように以下を並べ替えよ 1 GPU 上で計算 2 CPU から GPU にプログラムコードをコピー 3 GPU から CPU に計算結果をコピー 4 CPU から GPU に入力データをコピー 5 GPU コンテキストの生成答え または

5 前回の理解度クイズ 問 4 NVIDIA GPU を制御するうえで GPU コマンド送信に使用する Indirect Buffer の役割を簡潔に述べよ 答え Indirect Buffer は 64 ビットのパケットを格納しており 各パケットは実際の GPU コマンドが格納されているメモリ領域のオフセットとサイズに関する情報を持っている GPU はこの Indirect Buffer を読むことで GPU コマンドが格納されている場所からそのサイズ分 DMA 転送を行うことができるようになる

6 今日の講義 Network on Chip (NoC) 理解度クイズ

7 メニーコア NVIDIA/GPU INTEL/MIC L1 L1 L1 L1 L1 L1 L1 L2 Cache X86 Vec L1 Cache X86 Vec L1 Cache X86 Vec L1 Cache L2 Cache L2 Cache L2 Cache Interprocessor Network Memory & I/O Interface Video Memory CPU Main Memory CPU Main Memory

8 Many Integrated Core (MIC)

9 TILE64

10 Network on Chip PE PE PE PE PE PE Router PE PE PE PE

11 ここからは慶應義塾大学 松谷宏紀先生から借用のスライド

12 はじめに : マルチコア化への流れ 半導体技術の進歩 複数の計算コアを集積可 消費電力の増加 PPE SPE SPE SPE Ring buses SPE 動作周波数の向上は頭打ち SPE SPE SPE SPE マルチコア化 コア数を増やす (2~80 コア ) 動作周波数は低く抑える 並列化でスループットを稼ぐ マルチコアの例 STI Cell BE Sun T1(Niagara) [Pham, ISSCC 05] [Kongetira, micro 05] Cell BE (PPE 1 個, SPE 8 個 ) Core Core Core Core Core Crossbar SW Core Core Core L2 $ L2 $ L2 $ L2 $ Sun T1( コア 8 個, 各コア 4 スレッド )

13 コアの接続方式 : バス vs. ネットワーク オンチップバス ARM AMBA IBM CoreConnect パケットの構造 Core Core Core Core Network-on-Chip (NoC) ネットワーク状に接続 Router パケットスイッチング Core [Dally,DAC 01] [Benini,Computer 02] 占有 On-chip bus Dst シンプル, 面積が小さい Body flits Header flit コア数が増えるとボトルネック オンチップバスに代わる結合網として Network-on-Chip(NoC) が注目 2-D mesh network

14 Network-on-Chips の応用 MEM PE Array PE Array Network-on-Chip 80 tiles MEM router FP MAC FP MAC PE Array MIPS core Single tile MuCCRA [ 天野, ASSCC 07] Intel 80-core chip [Vangal,ISSCC 07] オンチップバスの置換え コア数を増やして電圧低減 科学技術演算向け 小規模 System-on-Chip 組込マルチメディア処理 ハイパフォーマンス系 面積コストの削減 高スループット化, 低遅延化消費電力の削減

15 Network-on-Chip の研究分野 いろいろなアプローチ ソフトウェアレベル アーキテクチャレベル 回路レベル ネットワークアーキテクチャ Software Level Architecture Level Circuit Level Device Level Input ports OS, task scheduling Topology, routing, router architecture 3D IC, power gating Output ports Tree FIFO FIFO Crossbar Deadlock-free routing Mesh (Grid) ルーティング, フロー制御 ネットワークトポロジ ルータアーキテクチャ

16 NoC のトポロジ : Mesh & Torus 2-D Mesh RAW [Taylor, ISCA 04] Intel s 80-core [Vangal, ISSCC 07] 2-D Torus [Dally, DAC 01] メッシュの 2 倍の帯域 ルータ 計算コア

17 NoC のトポロジ : Fat Tree Fat Tree (p, q, c) p: 上位リンクの数 q: 下位リンクの数 c: コアのポート数 SPIN [Andriahantenaina,DATE 03] SCORE [Caspi, FPL 00] ACM [Furtek, FPL 04] Fat Tree (2,4,1) Fat Tree (2,4,2) ルータ 計算コア

18 NoC のトポロジ : その他 (1) Spidergon リング + 対角線上に追加リンク Node degree 3; コスト効率が良い [Coppola, ISSOC 04] [Bononi, DATE 06] ルータ Spidergon (2-D layout) 計算コア

19 NoC のトポロジ : その他 (2) WK-recursive (d,k) d-node の完全グラフ 再帰的に k 回結合 Mesh-of-Tree メッシュ状にコアを並べる 縦 / 横方向にツリーで結合 [Vecchia, FCGS 88] [Rahmati, WK-recursive (4,2) ルータ 計算コア Mesh-of-Tree [Leighton, Math System

20 最近のオンチップネットワーク システム名トポロジルーティングスイッチングフロー制御 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 Shortest-path Pipelined CS, no VC Timeslot Sun T1 Crossbar (128bit) - - Handshake Cell BE EIB Ring (128bit) Shortest-path Pipelined CS, no VC TRIPS (operand) TRIPS (on-chip) 2-D mesh (109bit) ネットワークトポロジのまとめ 2-D mesh (128bit) Intel SCC 2-D torus (32bt) XY,YX DOR, 実際は 2-D mesh が良く使われる odd-even TM Credit YX DOR 1-flit, no VC On/off YX DOR WH, 4 VCs Credit 考慮すべきは, スループット, ルータ面積, 配線量, 配線遅延 NoC では配線は豊富に使えるが, ルータ面積は小さくしたい WH, no VC レイアウトが容易, かつ, パケットルーティングも単純 Stall/go Intel Teraflops 2-D mesh (32bit) Source WH, 2 lanes On/off

21 On-Chip Network Architecture いろいろなアプローチ ソフトウェアレベル アーキテクチャレベル 回路レベル ネットワークアーキテクチャ Software Level Architecture Level Circuit Level Device Level Input ports OS, task scheduling Topology, routing, router architecture 3D IC, power gating Output ports Tree FIFO Deadlock-free routing ルーティング, フロー制御 Mesh (Grid) ネットワークトポロジ FIFO Crossbar ルータアーキテクチャ

22 ルーティング : 固定型ルーティング 固定型ルーティング Source-destination 間の経路は 1 つに固定 ランダム型ルーティング Source-destination 間に複数の経路 ランダムに 1 つを選択 適応型ルーティング Source-destination 間に複数の経路 混雑に応じて 1 つを選択 X 方向 例 ) 次元順ルーティング Y 方向

23 ルーティング : 次元順ルーティング ( トーラス ) 次元順ルーティング X 方向 Y 方向 仮想チャネルが必要 2 次元トーラス ルータ 計算コア

24 ルーティング : 次元順ルーティング ( トーラス ) 次元順ルーティング X 方向 Y 方向 仮想チャネルが必要 循環依存 ( サイクル ) が発生 デッドロック バッファを多重化 ( 仮想チャネル ) 2 次元トーラス ルータ 循環依存を断ち切る デッドロックフリー 計算コア

25 ルーティング : 適応型ルーティング 固定型ルーティング Source-destination 間の経路は 1 つに固定 ランダム型ルーティング Source-destination 間に複数の経路 ランダムに 1 つを選択 適応型ルーティング Source-destination 間に複数の経路 混雑に応じて 1 つを選択 例 ) West-first, Negative-first, North-last, Odd-even, Opt-y, DP

26 ルーティング : West-first routing 固定型ルーティング Source-destination 間の経路は 1 つに固定 ランダム型ルーティング Source-destination 間に複数の経路 ランダムに 1 つを選択 適応型ルーティング Source-destination 間に複数の経路 混雑に応じて 1 つを選択 NW West-first の禁止ターン SW

27 ルーティング : North-last routing 固定型ルーティング Source-destination 間の経路は 1 つに固定 ランダム型ルーティング Source-destination 間に複数の経路 ランダムに 1 つを選択 適応型ルーティング Source-destination 間に複数の経路 混雑に応じて 1 つを選択 NW NE North-last の禁止ターン

28 ルーティング : Negative-first routing 固定型ルーティング Source-destination 間の経路は 1 つに固定 ランダム型ルーティング Source-destination 間に複数の経路 ランダムに 1 つを選択 適応型ルーティング Source-destination 間に複数の経路 混雑に応じて 1 つを選択 NW ES Negative-first の禁止ターン

29 ルーティング : Odd-even turn-model 固定型ルーティング Source-destination 間の経路は 1 つに固定 ランダム型ルーティング Source-destination 間に複数の経路 ランダムに 1 つを選択 偶数列か奇数列かによって禁止ターン違う ES EN Odd-even ( 偶数列 ) の禁止ターン 適応型ルーティング Source-destination 間に複数の経路 混雑に応じて 1 つを選択 NW SW Odd-even ( 奇数列 ) の禁止ターン

30 ルーティング : Opt-y routing (1/3) 固定型ルーティング Source-destination 間の経路は 1 つに固定 ランダム型ルーティング Source-destination 間に複数の経路 ランダムに 1 つを選択 適応型ルーティング Source-destination 間に複数の経路 混雑に応じて 1 つを選択 Fully adaptive routing 仮想チャネル (VC) を用い, 任意のターンを許可 NS 方向に VC 2 本 WN SW WS NW NS 方向に仮想チャネル 0 を使う場合 ( ) 点線のターンは これ以上 West 方向に進まないとき のみ許可

31 ルーティング : Opt-y routing (2/3) 固定型ルーティング Source-destination 間の経路は 1 つに固定 ランダム型ルーティング Source-destination 間に複数の経路 ランダムに 1 つを選択 適応型ルーティング Source-destination 間に複数の経路 混雑に応じて 1 つを選択 Fully adaptive routing 仮想チャネル (VC) を用い, 任意のターンを許可 NS 方向に VC 2 本 NS 方向に仮想チャネル 1 を使う場合 ( ) 点線のターンは これ以上 West 方向に進まないとき のみ許可

32 ルーティング : Opt-y routing (3/3) 固定型ルーティング Source-destination 間の経路は 1 つに固定 ランダム型ルーティング Source-destination 間に複数の経路 ランダムに 1 つを選択 適応型ルーティング Source-destination 間に複数の経路 混雑に応じて 1 つを選択 Fully adaptive routing 仮想チャネル (VC) を用い, 任意のターンを許可 NS 方向に VC 2 本 N1 N0 N0 N1 S1 S0 S0 S1 NS 方向の仮想チャネル番号切替え ( ) 点線のターンは これ以上 West 方向に進まないとき のみ許可

33 最近のオンチップネットワーク システム名トポロジルーティングスイッチングフロー制御 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 Shortest-path Pipelined CS, no VC Timeslot Sun T1 Crossbar (128bit) - - Handshake Cell BE EIB Ring (128bit) Shortest-path Pipelined CS, no VC TRIPS (operand) TRIPS (on-chip) 2-D mesh (109bit) パケットルーティングのまとめ 2-D mesh (128bit) Intel SCC 2-D torus (32bt) XY,YX DOR, Credit YX DOR 1-flit, no VC On/off YX DOR WH, 4 VCs Credit NoC では単純な固定型ルーティングが多く使われている 非最短経路は消費電力 ( 回路のスイッチング ) の増加を招く WH, no VC ルーティングはトポロジによって odd-even ( TM ある程度 ) 決まる Mesh/torus なら次元順ルーティング Stall/go Intel Teraflops 2-D mesh (32bit) Source WH, 2 lanes On/off

34 パケットスイッチング : 3 種類の方法 Store-and-forward (SAF) パケット単位で転送 大きなバッファ T = D (Lh + Lb) Wormhole (WH) フリット単位で転送 小さなバッファ T = D Lh + Lb Virtual-cut through フリット単位で転送 大きなバッファ T= 転送時間, D= ホップ数 Lh= ヘッダ長, Lb= ボディ長 R1 R2 R3 R1 R2 R3 ホップ数 3, パケット長 10-flit で, 1-flit 転送に 1-clock かかるとき, 転送時間の合計は? SAF の場合 WH の場合 3 * (1 + 10) = 33 clock 3 * = 13 clock

35 仮想チャネル (VC) 機構 VC の利点 先詰まりの防止 (1 車線と 2 車線の道路の例 ) 前方で右折したいが先が詰まってて進めない ( 怒 ) この帯域が無駄になっている 右折レーンを有効活用

36 仮想チャネル (VC) 機構 VC の利点 先詰まりの防止 (1 車線と 2 車線の道路の例 ) この帯域が無駄になっている VC の実装 1 物理ポートの時分割多重 [Dally,TPDS 92] Packet (a) Packet (b) VC#0 VC#1 パケット (a) は先が詰まって進めないので, 先にパケット (b) がクロスバを通過

37 最近のオンチップネットワーク システム名トポロジルーティングスイッチングフロー制御 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 Shortest-path Pipelined CS, no VC Timeslot Sun T1 Crossbar (128bit) - - Handshake Cell BE EIB Ring (128bit) Shortest-path Pipelined CS, no VC TRIPS (operand) TRIPS (on-chip) 2-D mesh (109bit) パケットスイッチングのまとめ 2-D mesh (128bit) NoC では Wormhole 方式が主流 Wormhole 方式 Intel SCC 2-D torus (32bt) XY,YX DOR, Credit YX DOR 1-flit, no VC On/off YX DOR WH, 4 VCs Credit WH, no VC バッファサイズが小さく, 通信遅延が小さい odd-even TM NoC 向き Stall/go ただ, head-of-line blocking の影響を受ける 仮想チャネル Intel Teraflops 2-D mesh (32bit) Source WH, 2 lanes On/off

38 On-Chip Network Architecture いろいろなアプローチ ソフトウェアレベル アーキテクチャレベル 回路レベル ネットワークアーキテクチャ Software Level Architecture Level Circuit Level Device Level Input ports OS, task scheduling Topology, routing, router architecture 3D IC, power gating Output ports Tree FIFO Deadlock-free routing ルーティング, フロー制御 Mesh (Grid) ネットワークトポロジ FIFO Crossbar ルータアーキテクチャ

39 オンチップルータ : ハードウェア構成 5 入力 5 出力の WH ルータ, データ ( フリット ) 幅は 64-bit 1 ポート当り複数の入力バッファ ( この図では 2 系統 ) を持つ 仮想チャネル 2 本 ARBITER X+ FIFO X+ X- FIFO X- Y+ FIFO Y+ Y- CORE FIFO FIFO 5x5 XBAR Y- CORE 配置配線後のゲート数は 15~30 [kgates] で, 全体の 6 割が FIFO

40 オンチップルータ : パイプライン構造 衝突しなければ 3 cycle でヘッダがルータを通過 RC (Routing computation) VSA (Virtual channel / switch allocation) ST (Switch traversal) 例 ) ルータ (a) からルータ (c) C HEAD RC VSA ST RC VSA ST RC VSA ST DATA 1 SA ST SA ST SA ST DATA 2 SA ST SA ST SA ST DATA 3 SA ST SA ST SA ST ヘッダがルータ (a) に注入され ELAPSED, データ3TIME がルータ [CYCLE] (c) を通過するまで12サイクル

41 オンチップルータ : Look-ahead 型ルータ 衝突しなければ 3 cycle でヘッダがルータを通過 NRC (Next routing computation) VSA (Virtual channel / switch allocation) ST (Switch traversal) NRC: 次ルータの RC を実行 ( 自ルータの RC は手前のルータに任せる ) NRC が終わらなくても VSA C HEAD NRC VSA ST NRC VSA ST NRC VSA ST DATA 1 SA ST SA ST SA ST DATA 2 SA ST SA ST SA ST DATA 3 SA ST SA ST SA ST ELAPSED TIME [CYCLE] ルータ (b) の出力ポートはルータ (a) が決め, ルータ (c) の出力ポートはルータ (b) が

42 オンチップルータ : 低遅延ルータ 衝突しなければ 2 cycle でヘッダがルータを通過 NRC + VSA (Next routing computation / switch allocation) ST (Switch traversal) NRC と VSA に依存性がないので並列実行できる 2 サイクル転送 HEAD ROUTER A NRC VSA ST ROUTER B ROUTER C NRC VSA ST NRC VSA ST W. Dally, Principles and Practices of Interconnection Networks (2004) DATA 1 DATA 2 DATA ELAPSED TIME [CYCLE] ヘッダがルータ (a) に注入され, データ 3 がルータ (c) を通過するまで 9 サイクル

43 オンチップルルータ : 消費電力の解析 90nm で配置配線し, 200MHz でシミュレーション ルータアーキテクチャのまとめ ルータの全ポートのうち 5 0 個のポートが使用中, 使われているポートの数 ( スタンバイ時 ) の消費電力 ( 最大帯域の@ 30% 200MHz 負荷 ) 考慮すべきは, 面積 ( バッファ ), パイプライン段数, 消費電力 パイプライン段数を減らす 通信遅延が減る 消費電力の削減が重要 Dynamic Total leakage (55.0%) Buffers leakage (49.4%) 200MHz 動作電圧を下げる 常に漏れ出す ( リーク ) 電流 電力供給自体を止める

44 理解度クイズ 授業アンケート 当日配布