Administrivia Computer Systems Architecture CMSC 411 Unit 4 Instruction level parallelism Read Chapter 3 and Section A 8 in Ch 3 only 3 1 3 8 and 3 10 required rest is optional Alan Sussman October 28 2004 CMSC 411 Alan Sussman What we already know about pipelining What s new in Units 4 4b We need to avoid structural hazards data hazards and control hazards in order to get optimal performance from the pipeline 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 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 CPI CMSC 411 Alan Sussman 2 3 New techniques CMSC 411 Alan Sussman 4 Data dependences background Hardware dynamic pipeline scheduling with scoreboarding with register renaming Tomasulo If 2 instructions are parallel can execute simultaneously in pipeline without stalls dynamic branch prediction issuing multiple instructions per cycle speculation dynamic memory disambiguation assuming no structural hazards If 2 instructions are dependent must be executed in order but may sometimes be partially overlapped Software compiler loop unrolling compiler dependence analysis software pipelining and trace scheduling compiler speculation CMSC 411 Alan Sussman 5 CMSC 411 A Sussman from D O Leary CMSC 411 Alan Sussman 6 1 Data dependences cont Data dependences cont Instruction j is data dependent on instruction i if either A dependence 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 indicates the possibility of a hazard determines the order results must be produced sets an upper bound on available parallelism Ways to overcome dependences Dependence implies a chain of one or more data hazards between the 2 instructions maintain the dependence but avoid the hazard schedule the code hardware or software eliminate the dependence by transforming the code software 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 organization CMSC 411 Alan Sussman 7 CMSC 411 Alan Sussman 8 Name 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 j when 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 Hazards True data dependences correspond to RAW data hazards Output dependences correspond to WAW hazards Antidependences correspond to WAR hazards statically by compiler or dynamically by hardware usually only for registers why CMSC 411 Alan Sussman 9 10 Control dependences cont Control dependences 2 constraints from control 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 if statement are control dependent on the branch CMSC 411 Alan Sussman CMSC 411 Alan Sussman 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 11 CMSC 411 A Sussman from D O Leary CMSC 411 Alan Sussman 12 2 Dynamic pipeline scheduling Scoreboard method 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 method CMSC 411 Alan Sussman 13 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 control CMSC 411 Alan Sussman 14 Administrivia Computer Systems Architecture CMSC 411 Unit 4 Instruction level parallelism Alan Sussman November 9 2004 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 Last time 16 Last time cont 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 dependences 2 instructions use the same register or memory location but no data flows between them antidependences WAR hazards and output dependences WAW hazards changing name removes the dependence maintain ordering of instructions with respect to conditional branches can only violate them if preserve exception behavior and data flow Dynamic pipeline scheduling idea is to start instructions as early as possible as soon as input data is available scoreboard