コンピュータ工学基礎 パイプラインハザード テキスト9章 115~124 情報工学科 天野英晴 パイプラインハザードとは？ • パイプラインがうまく流れなくなる危険、障害のこと – 構造ハザード • 資源が競合して片方のステージしか使えない場合に生じる – データハザード • データの依存性により生じる • 先に進んだ命令の結果を後の命令が利用するため、その結果がレジス タに書かれるまで、読むことができない – コントロールハザード • 分岐命令が原因で、次に実行する命令の確定ができない • パイプラインストール – ハザードが原因による性能の低下 – パイプライン処理は理想的に動くとCPIが1 • ストールによりCPIが大きくなってしまう IF EX ID rwe decorder st_op ld_op funct 3:0 rwe_id opcode 15:11 funct 2:0 rd_id 10 alu_bsel daddr ddataout st_op_id 命令メモリ creg dreg S Y B 01 ext ext0 imm 7:0 PC breg 00 ＋ rd_ex A rwe_ex rs 7:5 com_id areg ‘１’ ADD 00 01 10 ir rwe_ex st_op_id ld_op_id THB rd 10:8 WB we データ メモリ ddatain 0 1 IF EX ID rwe decorder st_op ld_op funct 3:0 rwe_id opcode 15:11 ir ADD rd_id 10 alu_bsel dataout datain addr st_op_id we 命令/ データ メモリ creg dreg S Y B 01 imm 7:0 ext ext0 PC breg 00 ＋ rd_ex A rwe_ex rs 7:5 com_id areg ‘１’ funct 2:0 THB rd 10:8 rwe_ex st_op_id ld_op_id 00 01 10 命令/データの 共有メモリを使う 場合 WB 0 1 メモリの共通化による構造ハザード LD命令 命令１ IF ID IF 命令2 IF時にメモリが 使えない EX ID Bubble WB EX WB IF ID IF 1クロック分終了が遅れる EX ID WB 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 ID rwe decorder st_op ld_op funct 3:0 rwe_id opcode 15:11 funct 2:0 rd_id 10 alu_bsel daddr ddataout 命令メモリ 0 creg dreg S Y B 01 breg 00 imm 7:0 ext ext0 rs 7:5 r0 rd_ex A rwe_ex ＋ PC com_id areg ‘１’ ADD 00 01 10 ir rwe_ex st_op_id ld_op_id THB rd 10:8 WB st_op_id we データ メモリ ddatain 0 1 LD r3,(r0) ADDI r0,#1 IF EX ID rwe decorder st_op ld_op funct 3:0 funct 2:0 rd_id 10 creg dreg S Y B 01 古いデータ alu_bsel 次のクロックの立上り で格納 命令メモリ breg 00 ext ext0 imm 7:0 PC rd_ex A 古いデータ ＋ rs 7:5 com_id areg rwe_ex ADD 00 01 10 ‘１’ rwe_ex st_op_id ld_op_id THB ir WB rwe_id opcode 15:11 rd 10:8 LDI r0,#0 LD r１,(r0) daddr ddataout st_op_id we データ メモリ ddatain r0=0 0 1 NOP LD r１,(r0) IF EX ID rwe decorder st_op ld_op funct 3:0 funct 2:0 rd_id creg dreg S Y 10 alu_bsel 次のクロックの立上り でデータを格納 命令メモリ B 01 ext ext0 imm 7:0 PC breg 00 ＋ rd_ex A rwe_ex rs 7:5 com_id areg ‘１’ ADD 00 01 10 ir rwe_ex st_op_id ld_op_id THB rd 10:8 WB rwe_id opcode 15:11 NOPを入れて 命令の間隔を確保 LDI r0,#0 NOP daddr ddataout st_op_id we データ メモリ ddatain r0=0 0 1 NOPを入れる方法 • NOPを2つ入れて命令間隔を確保 ハザード付きCPI＝ 理想のCPI＋ストールの確率×ストールのダ メージ 1 + 後続の命令が利用する確率×２＝ 1+ 0.8×２くらいはあるか？？ 2.6は悪化のしすぎ LD r3,(r0) ADDI r0,#1 IF EX ID rwe decorder st_op ld_op funct 3:0 funct 2:0 rd_id 新しいデータ creg dreg S Y B 10 命令メモリ 読み出しレジスタ 番号＝書き込み レジスタ番号 01 imm 7:0 PC ext ext0 rs 7:5 breg 00 ＋ rd_ex A rwe_ex com_id areg ‘１’ ADD 00 01 10 ir rwe_ex st_op_id ld_op_id THB rd 10:8 WB rwe_id opcode 15:11 レジスタファイルの フォワーディング LDI r0,#0 LD r１,(r0) alu_bsel daddr ddataout st_op_id we データ メモリ ddatain r0=0 0 1 演習1 • レジスタファイルにフォワーディングを付けた ことで、NOPを一つ入れればデータハザード を回避できる。 – 後続の命令が前の命令の結果を利用する可能 性：0.8 とすると、CPIはどのようになるか？ ADDI r0,#1 LDI r0,#0 LD r1, (r0) IF EX ID rwe decorder st_op ld_op funct 3:0 rwe_id opcode 15:11 funct 2:0 THB ir ADD com_id rd_id 最新の値と入 alu_bsel れ替える daddr ddataout 命令メモリ st_op_id we データ メモリ 0 creg dreg 10 0 1 breg 01 imm 7:0 PC ext ext0 rs 7:5 B 00 ＋ S Y 古いr0 0 1 rd_ex A rwe_ex areg ‘１’ rd 10:8 rwe_ex st_op_id ld_op_id 00 01 10 EXステージの フォワーディング 案その1 WB 0 1 0 1 r0 ddatain LD r3,(r0) ADDI r0,#1 IF LDI r0,#0 EX WB ID rwe decorder st_op ld_op funct 3:0 rwe_id opcode 15:11 funct 2:0 THB ir rd 10:8 ADD com_id rd_id creg dreg S Y B 10 breg 01 ext ext0 imm 7:0 PC 0 1 rd_ex A 00 ＋ areg 0 1 rwe_ex rs 7:5 rwe_ex st_op_id ld_op_id 00 01 10 EXステージの フォワーディング 案その1 ‘１’ LD r1, (r0) 0 1 alu_bsel r0 daddr ddataout 命令メモリ 0 1 st_op_id we データ メモリ ddatain 0 ADDI r0,#1 LDI r0,#0 LD r1, (r0) IF EX ID rwe decorder st_op ld_op funct 3:0 rwe_id opcode 15:11 funct 2:0 THB ir ADD com_id rd_id 0 1 0 creg dreg 10 breg 01 imm 7:0 PC ext ext0 rs 7:5 B 00 ＋ S Y 古いr0 0 1 rd_ex A rwe_ex areg ‘１’ rd 10:8 rwe_ex st_op_id ld_op_id 00 01 10 EXステージの フォワーディング 案その2 WB 0 1 alu_bsel r0 daddr ddataout ここで入れ替え 命令メモリ 0 1 st_op_id we データ メモリ ddatain パイプラインハザードとは？ • パイプラインがうまく流れなくなる危険、障害のこと – 構造ハザード • 資源が競合して片方のステージしか使えない場合に生じる – データハザード • データの依存性により生じる • 先に進んだ命令の結果を後の命令が利用するため、その結果がレジス タに書かれるまで、読むことができない – コントロールハザード • 分岐命令が原因で、次に実行する命令の確定ができない • パイプラインストール – ハザードが原因による性能の低下 – パイプライン処理は理想的に動くとCPIが1 • ストールによりCPIが大きくなってしまう IF EX ID rwe decorder st_op ld_op funct 3:0 rwe_id opcode 15:11 ir ADD com_id rd_id creg dreg 10 0 1 breg 01 imm 7:0 PC ext ext0 rs 7:5 B 00 ＋ S Y 古いr0 0 1 rd_ex A rwe_ex areg ‘１’ funct 2:0 THB rd 10:8 rwe_ex st_op_id ld_op_id 00 01 10 そもそも分岐 命令はサ ポートされて いない WB 0 1 alu_bsel r0 daddr ddataout 命令メモリ 0 1 st_op_id we データ メモリ ddatain ALUで分岐先を計算すると、、、 3クロック分終了が遅れる Branch命令 次の命令 IF ID Bubble EX Bubble WB Bubble IF ID IF EX ID IF WB EX ID Branchの次の命令フェッチを3クロック遅らせる。 ストール付きCPI＝理想のCPI＋ストールの確率×ストールのダメージ 1 ＋ 0.25×3 =1.75 （Branch/JMP/JAL命令を合わせて25％とする） ダメージが大きい！ WB EX WB IFで加算を行う IF EX ID rwe decorder st_op ld_op funct 3:0 rwe_id opcode 15:11 funct 2:0 THB 0 1 ir ADD com_id rd_id 0 1 0 1 alu_bsel r0 判定 daddr ddataout 命令メモリ creg dreg S Y 10 0 1 breg 01 imm 7:0 PC ext ext0 rs 7:5 B 00 ＋ rd_ex A 0 1 rwe_ex areg ‘１’ rd 10:8 rwe_ex st_op_id ld_op_id 00 01 10 ext ‘0’ WB st_op_id we データ メモリ ddatain IFで加算を行う IF EX ID rwe decorder st_op ld_op funct 3:0 rwe_id opcode 15:11 funct 2:0 THB 0 1 ir ADD com_id rd_id alu_bsel r0 クリティカルパスが 伸びる 0 1 0 1 判定 命令メモリ creg dreg S Y 10 0 1 breg 01 imm 7:0 PC ext ext0 rs 7:5 B 00 ＋ rd_ex A 0 1 rwe_ex areg ‘１’ rd 10:8 rwe_ex st_op_id ld_op_id 00 01 10 ext ‘0’ WB daddr ddataout st_op_id we データ メモリ ddatain IFステージで分岐先を計算すると、、、 1クロック分終了が遅れる Branch命令 次の命令 IF ID Bubble EX WB IF ID IF EX WB ID IF EX ID WB EX WB Branchの次の命令フェッチを1クロック遅らせる。 ストール付きCPI＝理想のCPI＋ストールの確率×ストールのダメージ 1 ＋ 0.25×1 = 1.25 （Branch/JMP/JAL命令を合わせて25％とする） これ以上はどうにもならない predict not-taken IF 分岐すれば 1クロック 待たす ID Bubble EX WB IF ID IF 1クロック分終了が遅れる EX ID IF IF 分岐しなければ フェッチした 命令をそのまま 使う ID IF EX ID IF WB EX ID WB EX WB WB EX ID IF WB EX ID WB EX WB ストール付きCPI＝理想のCPI＋ストールの確率×分岐する確率×ストールのダメージ 1 ＋ 0.25×1×0.7 =1.175 （Branch/JMP/JAL命令を合わせて25％とする） 分岐する方が確率が高いため、効果はイマイチ 遅延分岐 • 分岐命令の次の命令（遅延スロット）をパイプ ラインに入れてしまう。 – 遅延スロットの命令は必ず実行される →POCOの場合は遅延スロットは1 – つまり、遅延の効き目が遅い – 有効な命令を入れてやる必要がある → パイプラインスケジューリング パイプラインスケジューリング LDIU r0,#2 LD r1,(r0) LDIU r0,#3 LD r2,(r0) LDIU r3,#0 loop: ADD r3,r1 ADDI r2,#-1 BNZ r2,loop NOP LDIU r0,#0 ST r3,(r0) end: BEZ r2, end NOP 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個のデータ の総和を取る。これをパイプラインスケジュー ルしてストールをなくせ。 loop: LDI r0,#8 LDI r1,#0 ADDI r0,#-1 LD r2,(r0) ADD r1,r2 BNZ r1,loop NOP 高速化の流れ スレッドレベルの 高速化 Simultaneous Multithreading 複数命令の同時発行 （スーパースカラ） 命令レベルの 高速化 RISCの登場 パイプライン化 マルチコア化 パイプラインを細かく （スーパーパイプライン） 周波数の向上 命令の動的スケジュール マルチコア 革命 2003-2004 1980 1990 2000 マルチコア、メニーコア • 動作周波数の向上が限界に達する – 消費電力の増大、発熱の限界 – 半導体プロセスの速度向上が配線遅延により限界に達する • 命令レベル並列処理が限界に達する • メモリのスピードとのギャップが埋まらない → マルチコア、メニーコアの急速な発達 マルチコア革命 2003-2004年 • プログラマが並列化しないと単一プログラムの性能が上 がらない クロック周波数の向上 周波数 Pentium4 3.2GHz 高速プロセッサのクロック周波数 Nehalem 3.3GHz 1GHｚ 年間40％ Alpha21064 150MHz プロセッサの動作周波数は 2003年で限界に達した 消費電力、発熱が限界に 100MHｚ 1992 2000 2008 年 Flynnの分類 • 命令流(Instruction Stream)の数： M(Multiple)/S(Single) • データ流（Data Streaｍ）の数：M/S – SISD • ユニプロセッサ（スーパスカラ、VLIWも入る） – MISD：存在しない（Analog Computer） – SIMD – MIMD 一人の命令で皆同じことをする SIMD 命令メモリ 命令 演算装置 Data memory 半導体チップ内でたくさんの 演算装置を動かすには良い 方法 アクセラレータ（普通のCPU にくっつけて計算能力を加速 する加速装置）の多くは この方式 安くて高いピーク性能が 得られる →パソコン、ゲーム機と 共用 GPGPU：PC用 グラフィックプロセッサ – TSUBAME2.0(Xeon+Tesla,Top500 2010/11 4th ) – 天河一号(Xeon+FireStream,2009/11 5th ) ※()内は開発環境 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 Load/Store Global Memory PBSM PBSM PBSM PBSM GPU (NVIDIA’s GTX580) 128 Cores 128 Cores L2 Cache 128 Cores 128個のコアは SIMD動作をする ４つのグループは 独立動作をする 128 Cores もちろん、このチップを たくさん使う 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) Private FIQ Lines SMP for Embedded MPCore (ARM+Renesas) application … Interrupt Distributor Timer CPU Wdog interface Timer CPU Wdog interface IRQ IRQ Timer CPU Wdog interface IRQ Timer CPU Wdog interface IRQ CPU/VFP CPU/VFP CPU/VFP CPU/VFP L1 Memory L1 Memory L1 Memory L1 Memory Snoop Control Unit (SCU) Private Peripheral Bus Duplicated L1 Tag Private AXI R/W 64bit Bus L2 Cache Coherence Control Bus SUN T1 L2 Cache bank Directory Core Core Core Core Crossbar Switch Core L2 Cache bank Directory Memory L2 Cache bank Directory Core Core Core FPU Single issue six-stage pipeline RISC with 16KB Instruction cache/ 8KB Data cache for L1 L2 Cache bank Directory Total 3MB, 64byte Interleaved SUN Niagara 2 Niagara 2 Multi-Core (Intel’s Nehalem-EX) CPU CPU L3 Cache CPU CPU CPU CPU L3 Cache CPU CPU 8 CPU cores 24MB L3 cache 45nm CMOS 600 mm^2 分散共有メモリ型 Node ０ ０ Node １ １ ２ Ｉｎｔｅｒｃｏｎｎｅｃｔiｏｎ Ｎｅｔｗｏｒｋ Node 2 ３ Node ３ メモリ空間 独立して動けるプロセッサ を複数使う Cell Broadband Engine PS3 PPE L2 C SPE L1 C SXU SXU SXU SXU IBM Roadrunner Common platform for supercomputers and games PXU LS LS LS LS IOIF1 DMA DMA DMA DMA 1.6GHz / 4 X 16B data rings BIF/ MIC SXU SXU SXU SXU IOIF0 LS LS LS LS DMA DMA DMA DMA Supercomputer 「K」 L2 C Memory Core Core Core Core Core Core Core Core Tofu Interconnect 6-D Torus/Mesh Inter Connect Controller SPARC64 VIIIfx Chip 4 nodes/board 96nodes/Lack 24boards/Lack RDMA mechanism NUMA or UMA+NORMA
© Copyright 2024 ExpyDoc
