inst eecs berkeley edu cs61c su05 CS61C Machine Structures Lecture 19 Pipelining II 2005 07 21 Andy Carle CS 61C L19 Pipelining II 1 A Carle Summer 2005 UCB 4 1 Instruction Fetch rs rt ALU Data memory rd registers PC instruction memory Review Datapath for MIPS imm 5 Write 2 Decode 3 Execute 4 Memory Back Register Read Use datapath figure to represent pipeline IFtch Dcd Exec Mem WB CS 61C L19 Pipelining II 2 Reg ALU I D Reg A Carle Summer 2005 UCB Review Problems for Computers Limits to pipelining Hazards prevent next instruction from executing during its designated clock cycle Structural hazards HW cannot support this combination of instructions single person to fold and put clothes away Control hazards Pipelining of branches other instructions stall the pipeline until the hazard bubbles in the pipeline Data hazards Instruction depends on result of prior instruction still in the pipeline missing sock CS 61C L19 Pipelining II 3 A Carle Summer 2005 UCB Review C f Branch Delay vs Load Delay Load Delay occurs only if necessary dependent instructions Branch Delay always happens part of the ISA Why not have Branch Delay interlocked Answer Interlocks only work if you can detect hazard ahead of time By the time we detect a branch we already need its value hence no interlock is possible CS 61C L19 Pipelining II 4 A Carle Summer 2005 UCB FYI Historical Trivia First MIPS design did not interlock and stall on load use data hazard Real reason for name behind MIPS Microprocessor without Interlocked Pipeline Stages Word Play on acronym for Millions of Instructions Per Second also called MIPS Load Use Wrong Answer CS 61C L19 Pipelining II 5 A Carle Summer 2005 UCB Outline Pipeline Control Forwarding Control Hazard Control CS 61C L19 Pipelining II 6 A Carle Summer 2005 UCB Piped Proc So Far CS 61C L19 Pipelining II 7 A Carle Summer 2005 UCB New Representation Regs more explicit ME WB S S Data Mem B Reg File A EX ME Exec DE EX Reg File IR Inst Mem PC Next PC IF DE M D IF DE Ir Instruction DE EX A BusA out of Reg EX ME S AluOut EX ME D Bus B pass through for sw ME WB S ALuOut pass through ME WB M Mem Result from lw CS 61C L19 Pipelining II 8 A Carle Summer 2005 UCB New Representation Regs more explicit ME WB S S Data Mem B Reg File A EX ME Exec DE EX Reg File IR Inst Mem PC Next PC IF DE M D What s Missing CS 61C L19 Pipelining II 9 A Carle Summer 2005 UCB Pipelined Processor almost for slides Idea Parallel Piped Control M Data Mem D Mem Access S B Equal Reg File WB Ctrl IRwb Mem Ctrl IRmem Ex Ctrl IRex A Exec Dcd Ctrl IR Reg File PC Next PC Inst Mem Valid CS 61C L19 Pipelining II 10 A Carle Summer 2005 UCB Pipelined Control IR Mem PC PC PC 4 A R rs B R rt S A SX M Mem S Mem S B If Cond PC PC SX S M D CS 61C L19 Pipelining II 11 Mem Access B Data Mem A Reg File Equal R rd M IR Inst Mem PC R rt S Next PC R rd S S A SX Exec S A or ZX Reg File S A B A Carle Summer 2005 UCB Data Stationary Control The Main Control generates the control signals during Reg Dec Control signals for Exec ExtOp ALUSrc are used 1 cycle later Control signals for Mem MemWr Branch are used 2 cycles later Control signals for Wr MemtoReg MemWr are used 3 cycles later Reg Dec MemW r Branch MemtoReg RegWr CS 61C L19 Pipelining II 12 RegDst MemW r Branch MemtoReg RegWr MemW rBranch MemtoReg RegWr Wr Mem Wr Register RegDst ExtOp ALUSrc ALUOp Mem Ex Mem Register Main Control ID Ex Register IF ID Register ExtOp ALUSrc ALUOp Exec MemtoReg RegWr A Carle Summer 2005 UCB Let s Try it Out 10 lw 14 addI r2 r2 3 20 sub r3 r4 r5 24 beq r6 r7 100 28 ori r8 r9 17 32 add r10 r11 r12 100 and r13 r14 15 CS 61C L19 Pipelining II 13 r1 36 r2 A Carle Summer 2005 UCB Start Fetch 10 n B 10 D PC M S Data Mem A Mem Access im Exec rs rt Next PC WB Ctrl Mem Ctrl Reg File IR n Reg File n Decode Inst Mem n IF 10 lw 14 addI r2 r2 3 20 sub r3 r4 r5 24 beq r6 r7 100 30 ori r8 r9 17 34 add r10 r11 r12 100 and CS 61C L19 Pipelining II 14 r1 36 r2 r13 r14 15 A Carle Summer 2005 UCB n WB Ctrl B PC 14 D Next PC M S Data Mem A Reg File im Mem Access rt Exec 2 n Mem Ctrl Reg File IR n Decode lw r1 36 r2 Inst Mem Fetch 14 Decode 10 ID 10 lw IF 14 addI r2 r2 3 r1 36 r2 20 sub r3 r4 r5 24 beq r6 r7 100 30 ori r8 r9 17 34 add r10 r11 r12 100 and CS 61C L19 Pipelining II 15 r13 r14 15 A Carle Summer 2005 UCB n PC 20 D Data Mem B Next PC Reg File WB Ctrl M S Mem Access r2 2 n Mem Ctrl Exec 36 lw r1 rt Reg File IR Decode addI r2 r2 3 Inst Mem Fetch 20 Decode 14 Exec 10 EX 10 lw ID 14 addI r2 r2 3 IF 20 sub r3 r4 r5 24 beq r6 r7 100 30 ori r8 r9 17 34 add r10 r11 r12 r1 36 r2 100 and CS 61C L19 Pipelining II 16 r13 r14 15 A Carle Summer 2005 UCB 24 PC Next PC D Mem Access Reg File M Data Mem lw r1 B WB Ctrl Mem Ctrl r2 36 Exec 3 r2 4 n addI r2 r2 3 5 Reg File IR Decode sub r3 r4 r5 Inst Mem Fetch 24 Decode 20 Exec 14 Mem 10 M 10 lw EX 14 addI r2 r2 3 ID 20 sub r3 r4 r5 IF 24 beq r6 r7 100 30 ori r8 r9 17 34 add r10 r11 r12 r1 36 r2 100 and CS 61C L19 Pipelining II 17 r13 r14 15 A Carle Summer 2005 UCB Note Delayed Branch always execute ori after beq CS 61C L19 Pipelining II 18 Reg File WB Ctrl M r2 36 30 PC Next PC D Data Mem r5 Mem Access r2 3 r4 lw r1 addI r2 sub r3 Mem Ctrl 7 Exec 6 Reg File IR Decode beq r6 r7 100 Inst Mem Fetch 30 Dcd 24 Ex 20 Mem 14 WB 10 WB 10 M 14 lw r1 36 r2 addI r2 r2 3 EX 20 ID 24 sub r3 r4 r5 beq r6 r7 100 IF 30 ori r8 r9 17 add r10 r11 r12 34 100 and r13 r14 15 A Carle …
View Full Document
Unlocking...