Advanced Computer Org
Advanced Computer Org CS 4290
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 4290 at Georgia Institute of Technology - Main Campus taught by Milos Prvulovic in Fall. Since its upload, it has received 22 views. For similar materials see /class/234170/cs-4290-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Advanced Computer Org
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/02/15
CS 42906290 Appendix A Milos Prvulovic Spring 2004 Pipelining Split instruction s execution into phases Classic vestage pipeline IF Read instruction from memory ID Decode instruction and read operands EX Perform ALU operation MEM Access memory WB Write result to register le As soon as one instruction starts its ID phase start IF for the next instruction Without Pipelining Program code 11 ADD R1 R2 R3 I2 SUB R4 R11 R5 I3 AND R6 R12 R7 I4 OR R8 R13 R9 Decode 11 11 has no I5 XOR R10 R14 R11 read R2 memory and R3 access Cycle 1 RegID Mem U I Read 11 Execute 11 11 Writes from compute result to R1 memory R2R3 Without Pipelining Program code 11 ADD R1 R2 R3 I2 SUB R4 R11 R5 I3 AND R6 R12 R7 I4 OR R8 R13 R9 Decode 12 12 has no 15 XOR R10 R14 R11 read R11 memory and R5 y access Cycle 2 Regan Men 7 Read 12 Execute 12 12 Writes from compute result to R4 memory R1 lRS With Pipelining Program code 11 ADD R1 R2 R3 12 SUB R4 R11 R5 13 AND R6 R12 R7 14 OR R8 R13 R9 15 XOR R10 R14 R11 Cycle 1 9 I Mem r Read 11 r from memory With Pipelining Program code 11 ADD R1 R2 R3 I2 SUB R4 R11 R5 13 AND R6 R12 R7 I4 OR R8 R13 R9 15 XOR R10 R14 R11 DCCOde 11 read R2 and R3 gt 2 c I Mem r Read 12 from memory With Pipelining Program code 11 ADD R1 12 SUB R4 R2 R3 R11 R5 13 AND R6 R12 R7 14 OR R8 R13 R9 15 XOR R10 R14 R11 Cycle 3 Decode 12 read R11 and R5 gt Reg ID Mem lr Read 13 Execute 11 from compute memory R2R3 With Pipelining Program code 11 ADD R1 R2 R3 I2 SUB R4 R11 R5 I3 AND R6 R12 R7 I4 OR R8 R13 R9 15 XOR R10 R14 R11 DeCOde 139 H has no read R12 memory and R7 access CYCICZ 4 RegID Mem I lr Read 14 Execute 12 from compute memory R1 1R5 With Pipelining Program code 11 ADD R1 R2 R3 I2 SUB R4 R11 R5 I3 AND R6 R12 R7 I4 OR R8 R13 R9 Decode I4 12 has 0 I5 XOR R10 R14 R11 read R13 memory and R9 access Cycle 5 Regan Men Read 15 Execute I3 11 Writes from compute result to R1 memory R12ampR7 Speedup with pipelining No pipelining 45ns per cycle Pipelining lOns longest stage lns latch delay U f llns per Cyde Pipeline latches between stages each adds a small delay Speedup of 4 1X both execute l instruction per cycle Not bad at all although we kind of expected 5X Pipeline Hazards Three types of hazards Structural Resource con icts Data Instruction depends on a previous one Control Branch changes ow of the program Structural Hazards Example Memory supports only one read at a time 11 is a load instruction I4 13 12 11 Mem 39 i j Can not fetch 14 in the same cycle 14 Bubble I3 12 11 Dealing with structural hazards Hazard occurs on resource con ict Solution 1 Live With it Good if con ict infrequent Must still detect con ict and insert bubbles to make things work Solution 2 Add more resources In our example have dualported memory or separate instruction and data memory The 3 Kinds of Data Hazard Assume 11 before 12 in program order RAW ReadAfterWrite 11 writes a register 12 reads that register 12 had better get the value that 11 wrote WAR WriteAfterRead 11 reads a register 12 writes to the same register 11 had better read the value before 12 overwrites it WAW WriteAfterWrite 11 writes a register 12 also writes to that register The nal value of the register had better be 12 s Dealing with Data Hazards In our Classical pipeline WAR and WAW are not a problem WAR II is already a lot past its ID stage when 12 gets to its WB stage WAW 11 is past its WB stage just before 12 gets to the WB stage But they will become problems again when we start doing interesting things like RAW Data Hazards Program code I1 ADD R1 R2 R3 I2 SUB R4 R1 r R5 12 would be here and has already I3 AND R6r 1 r R7 read the wrong value from R1 and I4 CR R81 R1 R9 computed the wrong result with it I5 XOR R10 R1 R11 RegID Melquot lt Il Writes result to R1 13 would be here computing the wrong result I4 is here reading the wrong value of R1 Dealing with RAW data hazards Hazard occurs because we need result of previous instruction before it is written to register 0 39 39 ive with i u bles that s a lot 0 Solution 2 Forwarding We have the result after EX stage of 11 Data forwarding Program code 11 computes its result and forwards it back to the ALU inputs for 12 11 ADD R1 R2 R3 12 SUB R4 R1 R5 I3 AND R6 1 R7 Mem IF Reg ID I4 OR R8 R1 R9 15 XOR R10 R1 R11 iHumnesinthefnst half of its WB stage R4 reads registers in Regal the second half of its ID stage When forwarding doesn t work Program code I1 I2 I3 I4 I5 LD R1 100R2 SUB R4 R1 R5 AND R6 1 R7 11 gets the value from OR R8 R1 R9 memory here 12 is already XOR R10 R1 R11 here by then 1 Solution 2 Stall 12 for one cycle bubble Control Hazards Program code I1 I2 I3 I4 I5 Branch to 19 if R6 is Greater than or Equal to Zero SUB R4 R1 iiil BGEZ R6 19 ADD R1 R2 R3 Here we gure out we should actually go to 19 15 I4 l3l 9 OR R8 R1 R9 XOR R10 R1 R11 I Mem r 19 Bubble Bbble 13 I Mem r 1 Next cycle Dealing with Control Hazards Solution 1 Predict taken If branch is taken pay the penalty Solution 2 Resolve branches early Onestage bubble if we can know the outcome by the end of ID stage Solution 3 Delayed branches Instruction in the branch delay slot executes regardless of branch outcome Solution 4 Predict branches We will get to this Delayed Branches Need help from the compiler Suppose 11 is right before 12 which is a branch and 11 is right before 12 in program order 1f 11 and 12 do not have data dependences move 11 into 12 s delay slot There other ways to try to ll the delay slot But if they all fail we put a NOP in there Assignments Reading Assignment Review all of A1 through A5 If anything not familiar read it Homework 1 is posted on the web httpwwwccgatecheduclassesAY2004cs4290spring Due Friday next week 1232004 Kinds of Exceptions 2 Terminating Execution can not continue after this Eg unde ned instruction power failure etc Resumable Execution can continue later Eg breakpoint over ows etc Terminating exceptions easier for us don t have to worry about how to continue Kinds of Exceptions l Synchronous Tied to a particular instruction Eg diVidebyzero breakpoint etc Asynchronous Not tied to a particular instruction Eg timer interrupts DMA interrupts etc Asynchronous easier for us can nish What we started in the pipeline Exception Handling Timer Interrupt Async Resurnable 14 13 12 11 Reg ID Mem 39 I I When it arrives Next cycle H1 is the rst instruction of the exception handler Exception Handling DividebyZero Sync Resumable Say 13 triggers the exception Jump to handler before 13 executes 15 l4 I3 12 11 Reg ID Mem ll Ir H1 Bubble Bbble Bubble 12 Next cycle Regan I3 triggers the exception
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'