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 ALU Data memory rd rs rt 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 Outlin e 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 ME WB S S B D Data Mem A EX ME Exec DE EX Reg File IR Inst Mem PC Next PC IF DE Reg File New Representation Regs more explicit M 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 ME WB S S B D Data Mem A EX ME Exec DE EX Reg File IR Inst Mem PC Next PC IF DE Reg File New Representation Regs more explicit M 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 WB Ctrl Reg File 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 S A SX M Mem S A S B M D CS 61C L19 Pipelining II 11 Reg File Equal Mem S B Data Mem Reg File R rd M IR Inst Mem R rt S PC Next PC R rd S If Cond PC PC SX Mem Access S A or ZX Exec 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 ALUOp ALUOp RegDst MemWr Branch MemtoReg RegWr CS 61C L19 Pipelining II 12 RegDst MemWr Branch MemtoReg RegWr MemWr Branch MemtoReg RegWr Wr Mem Wr Register ExtOp ALUSrc Mem Ex Mem Register ExtOp ALUSrc ID Ex Register IF ID Register Main Control 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 n B 10 PC Next PC D CS 61C L19 Pipelining II 14 M S Data Mem A Mem Access im WB Ctrl Mem Ctrl Exec rs rt Reg File IR n Reg File n Decode Inst Mem Start n Fetch 10 IF 10 lw r1 36 r2 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 r13 r14 15 A Carle Summer 2005 UCB B 14 PC Next PC D CS 61C L19 Pipelining II 15 M S Reg File A WB Ctrl Data Mem im Mem Access rt n Mem Ctrl Exec 2 Reg File IR n Decode lw r1 36 r2 Inst Mem Fetch 14 Decode 10n ID 10 IF 14 lw r1 36 r2 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 r13 r14 15 A Carle Summer 2005 UCB 20 PC Next PC Data Mem D CS 61C L19 Pipelining II 16 M S Mem Access B WB Ctrl Mem Ctrl Exec r2 2 n Reg File lw r1 Decode rt 36 IR Reg File addI r2 r2 3 Inst Mem Fetch 20 Decode 14 n Exec 10 EX 10 ID 14 lw IF 20 sub r3 r4 r5 24 beq r6 r7 100 30 ori r8 r9 17 34 add r10 r11 r12 r1 36 r2 addI r2 r2 3 100 and r13 r14 15 A Carle Summer 2005 UCB 24 PC Next PC CS 61C L19 Pipelining II 17 Data Mem D Reg File M Mem Access B WB Ctrl Mem Ctrl r2 36 r2 Exec 4 lw r1 addI r2 r2 3 Decode 5 3 IR Reg File sub r3 r4 r5 Inst Mem Fetch 24 Decode 20 Exec n 14 Mem 10 M 10 EX 14 lw 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 addI r2 r2 3 100 and r13 r14 15 A Carle Summer 2005 UCB Note Delayed Branch always execute ori after beq CS 61C L19 Pipelining II 18 WB Ctrl Reg File M r2 36 r2 3 30 PC Next PC D Data Mem r5 Mem Access 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 Summer 2005 …
View Full Document
Unlocking...