コンピュータ工学基礎 パイプラインハザード テキスト9章 115~124 コンピュータ工学基礎 パイプラインハザード テキスト9章　115~124 情報工学科 天野英晴

パイプラインハザードとは？ パイプラインがうまく流れなくなる危険、障害のこと パイプラインストール 構造ハザード データハザード 資源が競合して片方のステージしか使えない場合に生じる データハザード データの依存性により生じる 先に進んだ命令の結果を後の命令が利用するため、その結果がレジスタに書かれるまで、読むことができない コントロールハザード 分岐命令が原因で、次に実行する命令の確定ができない パイプラインストール ハザードが原因による性能の低下 パイプライン処理は理想的に動くとCPIが1 ストールによりCPIが大きくなってしまう

IF EX WB ID ir ‘１’ A areg S Y ＋ creg B breg ext dreg PC ext0 データ メモリ rwe rwe_id rwe_ex opcode 15:11 decorder st_op st_op_id ld_op ld_op_id funct 3:0 funct 2:0 00 01 10 com_id THB ADD rd 10:8 ir rd_id rd_ex ‘１’ A rwe_ex areg S Y ＋ creg 1 00 B rs 7:5 breg ext 01 dreg PC imm 7:0 10 ext0 alu_bsel daddr ddataout ddatain データ メモリ 命令メモリ st_op_id we

IF EX WB ID 命令/データの 共有メモリを使う 場合 ir ‘１’ A areg S Y ＋ creg B breg ext rwe rwe_id rwe_ex opcode 15:11 decorder st_op st_op_id ld_op ld_op_id funct 3:0 命令/データの 共有メモリを使う 場合 funct 2:0 00 01 10 com_id THB ADD rd 10:8 ir rd_id rd_ex ‘１’ A rwe_ex areg S Y ＋ creg 1 00 B rs 7:5 breg ext 01 dreg PC imm 7:0 10 ext0 alu_bsel dataout datain 命令/ データ メモリ addr st_op_id we

メモリの共通化による構造ハザード LD命令 1クロック分終了が遅れる 命令１ 命令2 IF時にメモリが使えない 命令3 ID EX WB LD命令 IF ID EX WB 1クロック分終了が遅れる 命令１ IF ID EX WB Bubble 命令2　IF時にメモリが使えない IF ID EX WB 命令3 LD命令の次の次の命令フェッチを1クロック遅らせる。 ストール付きCPI＝理想のCPI＋ストールの確率×ストールのダメージ 　　　　　　　　　　　　　　　1　　　＋　0.25×1 　　　　　　　　　　　　　（LD/ST命令が合わせて25％とする）

構造ハザード 資源の複製により解決可能 コストと性能のトレードオフを考えて決める メモリの共有化→コスト減を取るか？ CPI　１→1.25の性能低下を取るか？

データハザード 直前の命令の結果がレジスタファイルに書き込まれないうちに、後続の命令が読み出しを行ってしまう 一つ前、さらに一つ前まで問題に データの依存性により生じるハザード 一つ前、さらに一つ前まで問題に 複数命令を時間的に重ねて実行する場合には常に問題になる Read After Write (RAW)ハザードと呼ばれる Write After Read(WAR)はPOCOでは生じない Write After Write(WAW)は通常あまり問題にならない 回避手法 →　NOPを入れて命令の間隔を保持する →　フォワーディング（Forwarding) 最新のデータを横流しにする 条件：１．後続の命令とレジスタ番号が一致　２．結果を書き込む命令

ADDI r0,#1 LDI r0,#0 LD r1, (r0) IF EX WB ID ir ‘１’ A areg S Y ＋ r0 rwe rwe_id rwe_ex opcode 15:11 decorder st_op st_op_id ld_op ld_op_id funct 3:0 funct 2:0 00 01 10 com_id THB ADD rd 10:8 ir rd_id rd_ex ‘１’ A rwe_ex areg S Y ＋ r0 creg 1 00 B rs 7:5 breg ext 01 dreg PC imm 7:0 10 ext0 alu_bsel daddr ddataout ddatain データ メモリ 命令メモリ st_op_id we

LD r3,(r0) ADDI r0,#1 LD r１,(r0) LDI r0,#0 IF EX WB ID ir 古いデータ ‘１’ A rwe rwe_id rwe_ex opcode 15:11 decorder st_op st_op_id ld_op ld_op_id funct 3:0 funct 2:0 00 01 10 com_id THB ADD rd 10:8 ir rd_id rd_ex 古いデータ ‘１’ A rwe_ex areg S r0=0 Y ＋ creg 1 00 B rs 7:5 breg ext 01 dreg PC imm 7:0 古いデータ 10 ext0 alu_bsel 次のクロックの立上り で格納 daddr ddataout ddatain データ メモリ 命令メモリ st_op_id we

LD r１,(r0) NOP NOP LDI r0,#0 IF EX WB ID NOPを入れて 命令の間隔を確保 ir ‘１’ A rwe rwe_id rwe_ex opcode 15:11 decorder st_op st_op_id NOPを入れて 命令の間隔を確保 ld_op ld_op_id funct 3:0 funct 2:0 00 01 10 com_id THB ADD rd 10:8 ir rd_id rd_ex ‘１’ A rwe_ex areg S r0=0 Y ＋ creg 1 00 B rs 7:5 breg ext 01 dreg PC imm 7:0 10 ext0 alu_bsel 次のクロックの立上り でデータを格納 daddr ddataout ddatain データ メモリ 命令メモリ st_op_id we

NOPを入れる方法 NOPを2つ入れて命令間隔を確保 ハザード付きCPI＝ 理想のCPI＋ストールの確率×ストールのダメージ 　1　+　後続の命令が利用する確率×２＝ 　1+　0.8×２くらいはあるか？？ 　2.6は悪化のしすぎ

LD r3,(r0) ADDI r0,#1 LD r１,(r0) LDI r0,#0 IF EX WB ID レジスタファイルの rwe rwe_id rwe_ex opcode 15:11 decorder st_op st_op_id ld_op ld_op_id funct 3:0 レジスタファイルの フォワーディング funct 2:0 00 01 10 com_id THB ADD rd 10:8 ir rd_id rd_ex 新しいデータ ‘１’ A rwe_ex areg S r0=0 Y ＋ creg 1 00 B rs 7:5 breg ext 01 dreg PC imm 7:0 10 ext0 alu_bsel 読み出しレジスタ 番号＝書き込み レジスタ番号 daddr ddataout ddatain データ メモリ 命令メモリ st_op_id we

演習1 レジスタファイルにフォワーディングを付けたことで、NOPを一つ入れればデータハザードを回避できる。 後続の命令が前の命令の結果を利用する可能性：0.8 とすると、CPIはどのようになるか？

ADDI r0,#1 LDI r0,#0 LD r1, (r0) IF EX WB ID EXステージの フォワーディング 案その1 ir rwe rwe_id rwe_ex opcode 15:11 decorder st_op st_op_id EXステージの フォワーディング 案その1 ld_op ld_op_id funct 3:0 funct 2:0 00 01 10 com_id THB ADD rd 10:8 ir rd_id rd_ex ‘１’ A rwe_ex 1 areg S 古いr0 Y ＋ creg 1 00 B rs 7:5 ext 1 01 breg dreg PC imm 7:0 10 ext0 最新の値と入れ替える 1 alu_bsel r0 daddr ddataout ddatain データ メモリ 命令メモリ st_op_id we

LD r1, (r0) LD r3,(r0) ADDI r0,#1 LDI r0,#0 IF EX WB ID EXステージの rwe rwe_id rwe_ex opcode 15:11 decorder st_op st_op_id EXステージの フォワーディング 案その1 ld_op ld_op_id funct 3:0 funct 2:0 00 01 10 com_id THB ADD rd 10:8 ir rd_id rd_ex ‘１’ A rwe_ex 1 areg S Y ＋ creg 1 00 B rs 7:5 ext 1 01 breg dreg PC imm 7:0 10 1 ext0 alu_bsel r0 daddr ddataout ddatain データ メモリ 命令メモリ st_op_id we

ADDI r0,#1 LDI r0,#0 LD r1, (r0) IF EX WB ID EXステージの フォワーディング 案その2 ir rwe rwe_id rwe_ex opcode 15:11 decorder st_op st_op_id EXステージの フォワーディング 案その2 ld_op ld_op_id funct 3:0 funct 2:0 00 01 10 com_id THB ADD rd 10:8 ir rd_id rd_ex ‘１’ 1 A rwe_ex areg S 古いr0 Y ＋ creg 1 00 B 1 rs 7:5 ext 01 breg dreg PC imm 7:0 10 1 ext0 alu_bsel r0 daddr ddataout ddatain ここで入れ替え データ メモリ 命令メモリ st_op_id we

パイプラインハザードとは？ パイプラインがうまく流れなくなる危険、障害のこと パイプラインストール 構造ハザード データハザード 資源が競合して片方のステージしか使えない場合に生じる データハザード データの依存性により生じる 先に進んだ命令の結果を後の命令が利用するため、その結果がレジスタに書かれるまで、読むことができない コントロールハザード 分岐命令が原因で、次に実行する命令の確定ができない パイプラインストール ハザードが原因による性能の低下 パイプライン処理は理想的に動くとCPIが1 ストールによりCPIが大きくなってしまう

IF EX WB ID そもそも分岐命令はサポートされていない ir ‘１’ A areg S 古いr0 Y ＋ creg B ext rwe rwe_id rwe_ex opcode 15:11 decorder st_op st_op_id ld_op ld_op_id そもそも分岐命令はサポートされていない funct 3:0 funct 2:0 00 01 10 com_id THB ADD rd 10:8 ir rd_id rd_ex ‘１’ A rwe_ex 1 areg S 古いr0 Y ＋ creg 1 00 B rs 7:5 ext 1 01 breg dreg PC imm 7:0 10 1 ext0 alu_bsel r0 daddr ddataout ddatain データ メモリ 命令メモリ st_op_id we

ALUで分岐先を計算すると、、、 3クロック分終了が遅れる Branch命令 次の命令 Branchの次の命令フェッチを3クロック遅らせる。 IF ID EX WB Branch命令 IF ID EX WB 次の命令 Bubble Bubble Bubble IF ID EX WB IF ID EX WB Branchの次の命令フェッチを3クロック遅らせる。 ストール付きCPI＝理想のCPI＋ストールの確率×ストールのダメージ 　　　　　　　　　　　　　　　1　　　＋　0.25×3　=1.75 　　　　　　　　　　　　　（Branch/JMP/JAL命令を合わせて25％とする） ダメージが大きい！

IFで加算を行う IF EX WB ID ‘0’ ext 1 ir ‘１’ A areg S Y ＋ creg B ext breg rwe rwe_id rwe_ex opcode 15:11 decorder st_op st_op_id ld_op ld_op_id funct 3:0 ‘0’ funct 2:0 00 01 10 ext com_id THB 1 ADD rd 10:8 ir rd_id rd_ex ‘１’ A rwe_ex 1 areg S Y ＋ creg 1 00 B rs 7:5 ext 1 01 breg dreg PC imm 7:0 10 1 ext0 alu_bsel r0 判定 daddr ddataout ddatain データ メモリ 命令メモリ st_op_id we

IFで加算を行う IF EX WB ID ‘0’ ext 1 ir ‘１’ A areg S Y ＋ creg B ext breg rwe rwe_id rwe_ex opcode 15:11 decorder st_op st_op_id ld_op ld_op_id funct 3:0 ‘0’ funct 2:0 00 01 10 ext com_id THB 1 ADD rd 10:8 ir rd_id rd_ex ‘１’ A rwe_ex 1 areg S Y ＋ creg 1 00 B rs 7:5 ext 1 01 breg dreg PC imm 7:0 10 1 ext0 alu_bsel r0 判定 daddr クリティカルパスが 伸びる ddataout ddatain データ メモリ 命令メモリ st_op_id we

IFステージで分岐先を計算すると、、、 1クロック分終了が遅れる Branch命令 次の命令 ID EX WB Bubble 1クロック分終了が遅れる Branch命令 Branchの次の命令フェッチを1クロック遅らせる。 ストール付きCPI＝理想のCPI＋ストールの確率×ストールのダメージ 　　　　　　　　　　　　　　　1　　　＋　0.25×1　=　1.25 　　　　　　　　　　　　　（Branch/JMP/JAL命令を合わせて25％とする） これ以上はどうにもならない

predict not-taken 1クロック分終了が遅れる 分岐すれば 1クロック 待たす 分岐しなければ フェッチした 命令をそのまま IF 分岐すれば 1クロック 待たす ID EX WB Bubble 1クロック分終了が遅れる IF ID EX WB IF ID EX WB 分岐しなければ フェッチした 命令をそのまま 使う IF ID EX WB IF ID EX WB ストール付きCPI＝理想のCPI＋ストールの確率×分岐する確率×ストールのダメージ 　　　　　　　　　　　　　　　1　　　＋　0.25×1×0.7　=1.175 　　　　　　　　　　　　　（Branch/JMP/JAL命令を合わせて25％とする） 分岐する方が確率が高いため、効果はイマイチ

遅延分岐 分岐命令の次の命令（遅延スロット）をパイプラインに入れてしまう。 遅延スロットの命令は必ず実行される つまり、遅延の効き目が遅い →POCOの場合は遅延スロットは1 つまり、遅延の効き目が遅い 有効な命令を入れてやる必要がある →　パイプラインスケジューリング

パイプラインスケジューリング LDIU r0,#2 LDIU r0,#2 LD r1,(r0) LD r1,(r0) LDIU r0,#3 loop: ADD r3,r1 ADDI r2,#-1 BNZ r2,loop NOP LDIU r0,#0 ST r3,(r0) end: BEZ r2, end 　　　LDIU r0,#2 　　　LD r1,(r0) 　　　LDIU r0,#3 　　　LD r2,(r0) 　　　LDIU r3,#0 loop: ADDI r2,#-1 BNZ r2,loop ADD r3,r1 LDIU r0,#0 ST r3,(r0) end: BEZ r2, end NOP

演習2 下のプログラムは0番地から並ぶ8個のデータの総和を取る。これをパイプラインスケジュールしてストールをなくせ。 LDI r0,#8 loop: ADDI r0,#-1 LD r2,(r0) ADD r1,r2 BNZ r1,loop NOP

高速化の流れ スレッドレベルの 高速化 Simultaneous Multithreading マルチコア化 複数命令の同時発行 （スーパースカラ） 命令レベルの 高速化 パイプラインを細かく （スーパーパイプライン） 周波数の向上 RISCの登場 パイプライン化 命令の動的スケジュール マルチコア 革命 2003-2004 1980 1990 2000

マルチコア、メニーコア 動作周波数の向上が限界に達する 命令レベル並列処理が限界に達する メモリのスピードとのギャップが埋まらない 消費電力の増大、発熱の限界 半導体プロセスの速度向上が配線遅延により限界に達する 命令レベル並列処理が限界に達する メモリのスピードとのギャップが埋まらない →　マルチコア、メニーコアの急速な発達 マルチコア革命　2003-2004年 プログラマが並列化しないと単一プログラムの性能が上がらない

プロセッサの動作周波数は2003年で限界に達した クロック周波数の向上 Pentium4 3.2GHz Nehalem 3.3GHz 高速プロセッサのクロック周波数 周波数 1GHｚ 年間40％ プロセッサの動作周波数は2003年で限界に達した 消費電力、発熱が限界に Alpha21064 150MHz 100MHｚ 1992 2008 2000 年

Flynnの分類 命令流(Instruction Stream)の数： M(Multiple)/S(Single) データ流（Data　Streaｍ）の数：M/S SISD ユニプロセッサ（スーパスカラ、VLIWも入る） MISD：存在しない（Analog　Computer） SIMD MIMD

一人の命令で皆同じことをする SIMD 命令メモリ 半導体チップ内でたくさんの 演算装置を動かすには良い 方法 アクセラレータ（普通のCPU にくっつけて計算能力を加速 する加速装置）の多くは この方式 安くて高いピーク性能が 得られる →パソコン、ゲーム機と 　　共用 命令 演算装置 Data memory

GPGPU：PC用 グラフィックプロセッサ TSUBAME2.0(Xeon+Tesla,Top500 2010/11 4th ) 天河一号(Xeon+FireStream,2009/11 5th ) 近年、CPUとGPUやCELLといったマルチコアアクセラレータを組み合わせて使うハイブリッドの計算環境が普及しています。 例えばTOP500を見ると、TSUBAMEのNVIDIA GPUはもちろんですが、↑こういったATIのGPUを使ったスパコンも存在します。 またCell B.E.を搭載したアクセラレータもあります。 これらのアクセラレータを使って高い性能が得られるのですが、アクセラレータごとに異なる環境を用いなければなりませんでした。 そこで、Open CLという開発環境が登場しました。 OpenCLは、マルチコアプロセッサ向けの共通プログラミング環境で、Open CLにより、 異なるアーキテクチャでもCライクの同一ソースコードで開発が可能になりました。 ※()内は開発環境 32

Thread Execution Manager GeForce GTX280 240 cores Host Input Assembler Thread Execution Manager Thread Processors Thread Processors Thread Processors Thread Processors Thread Processors … PBSM PBSM PBSM PBSM PBSM PBSM PBSM PBSM PBSM PBSM Load/Store Global Memory

GPU (NVIDIA’s GTX580) L2 Cache 512 GPU cores ( 128 X 4 ) 128個のコアは SIMD動作をする ４つのグループは 独立動作をする もちろん、このチップを たくさん使う 512 GPU cores ( 128 X 4 ) 768 KB L2 cache 40nm CMOS 550 mm^2

MIMD（Multipe-Instruction Streams/ Multiple-Data Streams)の特徴 自分のプログラムで動けるプロセッサ（コア）を多数使う 同期：足並みを揃える データ交信：共通に使うメモリを持つなど 最近のPC用のプロセッサは全部この形を取っている 最近はスマートフォン用のCPUもマルチコア化 集中メモリ型　UMA(Uniform Memory Access Model) 分散メモリ型 NUMA(Non-Uniform Memory Access Model) 共有メモリを持たない型　NORMA(No Remote Memory Access Model)

Interrupt Distributor Snoop Control Unit (SCU) MPCore (ARM+Renesas) Private FIQ Lines SMP for Embedded application … Interrupt Distributor CPU interface Timer Wdog CPU interface Timer Wdog CPU interface Timer Wdog CPU interface Timer Wdog IRQ IRQ IRQ IRQ CPU/VFP CPU/VFP CPU/VFP CPU/VFP L1 Memory L1 Memory L1 Memory L1 Memory ４つのコアを搭載可能、共有データのキャッシングはスヌープで管理する Snoop Control Unit (SCU) Coherence Control Bus Private Peripheral Bus Private AXI R/W 64bit Bus Duplicated L1 Tag L2 Cache

SUN T1 L2 Cache bank Core Core Directory Crossbar Switch Core L2 Cache Memory Core Directory Core L2 Cache bank Core Directory Core FPU L2 Cache bank Core Directory Single issue six-stage pipeline RISC with 16KB Instruction cache/ 8KB Data cache for L1 Total 3MB, 64byte Interleaved

SUN　Niagara 2 Niagara 2

Multi-Core (Intel’s Nehalem-EX) CPU L3 Cache 8 CPU cores 24MB L3 cache 45nm CMOS 600 mm^2

分散共有メモリ型 独立して動けるプロセッサ を複数使う メモリ空間 Node ０ ０ Node １ １ ２ Node 2 ３ Node ３ Ｉｎｔｅｒｃｏｎｎｅｃｔiｏｎ Ｎｅｔｗｏｒｋ Node　2 ３ メモリ空間 Node　３ 独立して動けるプロセッサ を複数使う

Cell Broadband Engine PS3 SXU LS DMA MIC BIF/ IOIF0 PXU L1 C L2 C PPE SPE 1.6GHz / 4 X 16B data rings IBM Roadrunner Common platform for supercomputers and games

Supercomputer 「K」 L2 C Core Core Tofu Interconnect 6-D Torus/Mesh Core Memory L2 C Core Core Tofu Interconnect 　　　　　　6-D Torus/Mesh Core Core Inter Connect Controller Core Core Core Core SPARC64 VIIIfx Chip RDMA mechanism NUMA or UMA+NORMA 4 nodes/board 96nodes/Lack 24boards/Lack