CMSC411 Study Sheet MIPS commands DADDI it s EX and it goes straight across holds it s reg until the X stage What is mem struct stall it s when mem is being used in another instruction and the second instruction must wait L D load it s EX and it holds it s register until the M stage SUB D FPA and it holds it s register until the end of X stage RAW hazards example below In this case f9 isn t unlocked until the M stage but is read in the D MUL D F9 F9 F9 MUL D F2 F9 F2 When this happens there is a stall on the second command add on 2 clock cycles to the D command so that the correct reg is definitely read X can overlap D cannot overlap CH 3 all memory stuff from App B CH 2 content by tomasulo paper also DEPENDANCES APP A FPPLP static handling of control hazards Dependances they exist within the hardware and could possibly cause 1 Data dependence Two instructions are data dependent if one uses the result of the other or if one uses the result of an instruction that depends on the other data dependences chain to create more dependences 2 Antidependence This is when an instruction reads a register that the next instruction writes to The execution order of these instructions must be preserved so that the first instruction does not read the incorrect value 3 Output dependence this is when two instructions write to the same register The ordering must be preserved to ensure the last thing written to the register is the last instruction Executing data dependences simultaneously would cause a FPPLP machine to stall so that overlap does not happen When an instruction is stalled the dest Instruction is stalled by the latency of the SOURCE instruction This also causes all other instructions behind to stall Data Hazards 1 RAW instruction two tries to read before instruction one writes to the register getting the old 2 WAR This hazard does not occur in FPPLP because reads are early and writes are late It incorrect value corresponds to antidependence 3 WAW The second instruction writes to a register before the first instruction writes to that register so the register s final value is the first write not the second write This only happens in pipelines that write in more than one stage or don t stall all instructions This hazard corresponds to output dependence Control dependencies hazards dependencies for jumps They are in if statements a set of instructions will be control dependent on an instruction that jumps and instructions before that determine that jump Control hazards are when the jump is evaluated before the instructions before it that may change the outcome of the jump and cause an incorrect execution Superscalar issuing multiple instructions simultaneously Speculation dynamic handling of control hazards Pipelining overlapping instruction execution RSIC reduced instruction set computer MIPS is a kind of RSIC architecture 5 instruction items 1 F Fetch instruction fetches the current program counter instruction from memory updates the program counter 2 D Decode instruction decodes instruction and READS REGISTERS FROM SOURCE REGS Equality comparison and branch happen here Happens in parallel with reading 3 X Execute instruction ALU operates on operands in previous cycle 4 M Memory Access reads from memory here or writes to a register 5 W Write writes the result into the register file whether that s memory or ALU Latency The number of stages after entering stage X that a result is produced 1 The latency of integer ALU is 0 while store and loads are 1 because they need the M cycle FP addition has 4 cycles so Latency 3 while multiplication has latency 6 7 cycles and division has latency 24 25 cycles Two main approaches to pipelining 1 Compiler based static approach FPPLP 2 Hardware based dynamic approach Tomasulo a CPI maximize this ideal CPI Struct stalls Data stalls Control stalls Dynamic Scheduling Rearrange order of instructions to reduce stalls while maintaining data flow 1 This is good because it handles cases where the dependencies are not known at compile time and also the compiler doesn t know about the microarchitecture 2 However it makes the hardware much more complex and complicates exceptions 3 It means out of order execution and completion in a safe way but creates possibility for WAR and WAW hazards 4 Tomasulo s Approach a Tracks when operands are available b c Register renaming is provided by Reservation Stations which contain the instruction the Introduces register renaming in hardware reduces WAW WAR hazards buffered operand values and the number of the reservation station providing the operand values d Result values broadcast on the Common Data Bus e Only the last output actually updates the register file when that reg file is renamed f As instructions are issued the register names are updated with reservation station numbers g There may be more reservation stations than registers Tomasulo s Algorithm 3 steps 1 Issue Get next instruction from queue Issue instruction to reservation station if avail With operands if available If not stall instruction 2 Execute when operands available store in res station Issue instruction 3 Write Write into store buffers and RSes through CDB
View Full Document
Unlocking...