CMSC 411 - A. Sussman (from D. O'Leary) 1Computer Systems ArchitectureCMSC 411Unit 4 – Instruction-level parallelismAlan SussmanOctober 28, 2004CMSC 411 - Alan Sussman 2Administrivia• Read Chapter 3 and Section A.8– in Ch. 3, only 3.1-3.8 and 3.10 required, rest is optionalCMSC 411 - Alan Sussman 3What we already know about pipelining• We need to avoid structural hazards, data hazards and control hazards in order to get optimal performance from the pipeline– Pipeline CPI = Ideal pipeline CPI + Structural stalls + Data hazard stalls + Control stalls• Accomplish this by techniques such as– instruction reordering– hardware modifications to detect branches earlier– compiler approaches to reduce branch delays• Each technique reduces one or more of the stall components of the Pipeline CPICMSC 411 - Alan Sussman 4What's new in Units 4 & 4b• Some instructions can be executed independently of others. In fact, they could be executed in parallel if there was the hardware to do it• Idea is to take advantage of this instruction level parallelism to do major rearrangements to how compilers generate code (Unit 4b) and how the MIPS (and other modern processors) pipeline executes code (Unit 4)CMSC 411 - Alan Sussman 5New techniques• Hardware– dynamic pipeline scheduling• with scoreboarding• with register renaming (Tomasulo)– dynamic branch prediction– issuing multiple instructions per cycle– speculation– dynamic memory disambiguation• Software (compiler)– loop unrolling – compiler dependence analysis– software pipelining and trace scheduling– compiler speculationCMSC 411 - Alan Sussman 6Data dependences (background)• If 2 instructions are parallel, can execute simultaneously in pipeline without stalls– assuming no structural hazards• If 2 instructions are dependent, must be executed in order, but may sometimes be partially overlappedCMSC 411 - A. Sussman (from D. O'Leary) 2CMSC 411 - Alan Sussman 7Data dependences (cont.)• Instruction j is data dependent on instruction i if either– instruction i produces a result that may be used by instruction j, or– instruction j is data dependent on instruction k, and instruction k is data dependent on instruction I(transitivity)• Dependence implies a chain of one or more data hazards between the 2 instructions– potentially causing a pipelined processor to stall• Dependences are properties of programs– and whether one causes a stall depends on the properties of the pipeline organizationCMSC 411 - Alan Sussman 8Data dependences (cont.)• A dependence– indicates the possibility of a hazard– determines the order results must be produced– sets an upper bound on available parallelism• Ways to overcome dependences– maintain the dependence, but avoid the hazard (schedule the code – hardware or software)– eliminate the dependence – by transforming the code (software)CMSC 411 - Alan Sussman 9Name dependences• When 2 instructions use the same register or memory location (harder to detect), called a name, but no flow of data between them• 2 types– antidependence between instruction i and instruction jwhen j writes a register or memory location that i reads– output dependence occurs when i and j write the same register or memory location• In both cases, the instructions can execute at the same time, or be reordered, if the name is changed so the instructions don’t conflict– statically by compiler or dynamically by hardware (usually only for registers – why?)CMSC 411 - Alan Sussman 10Hazards• True data dependences correspond to RAW data hazards• Output dependences correspond to WAW hazards• Antidependences correspond to WAR hazardsCMSC 411 - Alan Sussman 11Control dependences• To determine the ordering of an instruction, j, with respect to a branch instruction so that it is executed in correct program order, and only when it should be– e.g., the statements in then part of an ifstatement are control dependent on the branchCMSC 411 - Alan Sussman 12Control dependences (cont.)• 2 constraints from control dependences– an instruction control dependent on a branch cannot be moved before the branch so that its execution is no longer controlled by the branch– an instruction not control dependent on a branch cannot be moved after the branch so that its execution is controlled by the branch• But, can violate control dependences if don’t affect the correctness of the program– by preserving exception behavior and data flow– implemented by control hazard detection that causes control stalls, which can be reduced by various techniques (e.g., delayed branch)CMSC 411 - A. Sussman (from D. O'Leary) 3CMSC 411 - Alan Sussman 13Dynamic pipeline scheduling• A hardware technique that can do a good job of scheduling, since it has perfect information about hazards• Basic idea is to start each instruction as early as possible• Means have to deal with instructions that complete out-of-order• There is a lot to keep track of, and two main schemes to do the bookkeeping– scoreboard method– Tomasulo's methodCMSC 411 - Alan Sussman 14Scoreboard method• Origins: CDC 6600, late 1960s• Scoreboard controls the progress of each instruction to ensure that hazards such as RAW, etc. are avoided• ID basic pipeline stage split into 2 stages– Issue – decode instructions, check for structural hazards– Read operands – wait until no data hazards, then read operands• Distinguish when instruction begins execution and when completes execution – in between it is in execution• All instructions pass through issue stage in order, but can stall or bypass each other in second stage– so can get WAR hazards when instructions execute out of order– to have multiple instructions in EX stage simultaneously, use multiple functional units, or pipelined units, or both – equivalent for purposes of pipeline controlComputer Systems ArchitectureCMSC 411Unit 4 – Instruction-level parallelismAlan SussmanNovember 9, 2004CMSC 411 - Alan Sussman 16Administrivia• HW #5 (Unit 4) out soon• Project posted – due Dec. 3– Linux lab account info emailed – let us know if you didn’t get it– questions?• Midterm returned Thursday (we hope)CMSC 411 - Alan Sussman 17Last time• Data dependences– instruction i produces a result used, directly or transitively, by instruction j– true dependences in program may cause stalls from data (RAW) hazards• Name