Topic 6a Basic BackBack End Optimization Instruction Selection Instruction scheduling Register allocation 2008 4 15 course cpeg421 08s Topic6a ppt 1 ABET Outcome Ability to apply knowledge of basic code generation techniques e g Instruction scheduling register allocation to solve code generation problems An ability to identify formulate and solve loops scheduling problems using software pipelining techniques Ability to analyze the basic algorithms on the above techniques and conduct experiments to show their effectiveness Ability to use a modern compiler development platform and tools for the practice of above A Knowledge on contemporary issues on this topic 2008 4 15 course cpeg421 08s Topic6a ppt 2 Reading List 1 K D Cooper L Torczon Engineering a Compiler Chapter 12 2 Dragon Book Chapter 10 1 10 4 2008 4 15 course cpeg421 08s Topic6a ppt 3 A Short Tour on Data Dependence 2008 4 15 course cpeg421 08s Topic6a ppt 4 Basic Concept and Motivation Data dependence between 2 accesses The same memory location Exist an execution path between them At least one of them is a write Three types of data dependencies Dependence graphs Things are not simple when dealing with loops 2008 4 15 course cpeg421 08s Topic6a ppt 5 Data Dependencies There is a data dependence between statements Si and Sj if and only if Both statements access the same memory location and at least one of the statements writes into it and There is a feasible run time execution path from Si to Sj 2008 4 15 course cpeg421 08s Topic6a ppt 6 Types of Data Dependencies Flow true Dependencies write read x 4 y x 1 Output Dependencies write write o x 4 x y 1 0 Anti dependencies read write 1 y x 1 x 4 2008 4 15 1 course cpeg421 08s Topic6a ppt 7 An Example of Data Dependencies 1 2 3 4 5 6 x y p z x y 4 6 x 2 y p z p Flow Output Anti 2008 4 15 x 4 y 6 p x 2 z y p y p course cpeg421 08s Topic6a ppt x z 8 Data Dependence Graph DDG Forms a data dependence graph between statements nodes statements edges dependence relation type label 2008 4 15 course cpeg421 08s Topic6a ppt 9 Data Dependence Graph S1 Example 1 S2 S1 A 0 S3 S2 B A S3 C A D S4 S4 D 2 Sx Sy flow dependence 2008 4 15 course cpeg421 08s Topic6a ppt 10 Data Dependence Graph Example 2 S1 A 0 S2 B A S3 A B 1 S4 C A S1 S2 S3 S4 2008 4 15 course cpeg421 08s Topic6a ppt 11 Should we consider input dependence X X 2008 4 15 Is the reading of the same X important Well it may be if we intend to group the 2 reads together for cache optimization course cpeg421 08s Topic6a ppt 12 Applications of Data Dependence Graph register allocation instruction scheduling loop scheduling vectorization parallelization memory hierarchy optimization 2008 4 15 course cpeg421 08s Topic6a ppt 13 Data Dependence in Loops Problem How to extend the concept to loops s1 do i 1 5 s2 x a 1 s3 a x 2 s4 end do 2008 4 15 s2 1 s3 s2 s3 s3 s2 next iteration course cpeg421 08s Topic6a ppt 14 Reordering Transformation A reordering transformation is any program transformation that merely changes the order of execution of the code without adding or deleting any executions of any statements A reordering transformation preserves a dependence if it preserves the relative execution order of the source and sink of that dependence 2008 4 15 course cpeg421 08s Topic6a ppt 15 Reordering Transformations Con t Instruction Scheduling Loop restructuring Exploiting Parallelism Analyze array references to determine whether two iterations access the same memory location Iterations I1 and I2 can be safely executed in parallel if there is no data dependency between them 2008 4 15 course cpeg421 08s Topic6a ppt 16 Reordering Transformation using DDG Given a correct data dependence graph any order based optimization that does not change the dependences of a program is guaranteed not to change the results of the program 2008 4 15 course cpeg421 08s Topic6a ppt 17 Instruction Scheduling Motivation Modern processors can overlap the execution of multiple independent instructions through pipelining and multiple functional units Instruction scheduling can improve the performance of a program by placing independent target instructions in parallel or adjacent positions 2008 4 15 course cpeg421 08s Topic6a ppt 18 Instruction scheduling con t Original Code Instruction Schedular Reordered Code Assume all instructions are essential i e we have finished optimizing the IR Instruction scheduling attempts to reorder the codes for maximum instruction level parallelism ILP It is one of the instruction level optimizations Instruction scheduling IS is NP complete so heuristics must be used 2008 4 15 course cpeg421 08s Topic6a ppt 19 Instruction scheduling A Simple Example time a 1 x a 1 x b 2 y c 3 z b 2 y c 3 z Since all three instructions are independent we can execute them in parallel assuming adequate hardware processing resources 2008 4 15 course cpeg421 08s Topic6a ppt 20 Hardware Parallelism Three forms of parallelism are found in modern hardware pipelining superscalar processing multiprocessing Of these the first two forms are commonly exploited by instruction scheduling 2008 4 15 course cpeg421 08s Topic6a ppt 21 Pipelining Superscalar Processing Pipelining Decompose an instruction s execution into a sequence of stages so that multiple instruction executions can be overlapped It has the same principle as the assembly line Superscalar Processing Multiple instructions proceed simultaneously through the same pipeline stages This is accomplished by adding more hardware for parallel execution of stages and for dispatching instructions to them 2008 4 15 course cpeg421 08s Topic6a ppt 22 A Classic FiveFive Stage Pipeline IF RF EX ME WB instruction fetch decode and register fetch execute on ALU memory access write back to register file time 2008 4 15 course cpeg421 08s Topic6a ppt 23 Pipeline Illustration IF RF EX ME WB IF RF EX ME WB IF RF EX ME WB IF RF EX ME WB IF time RF EX ME The standard Von Neumann model IF RF EX ME WB IF RF EX ME WB IF RF EX ME WB IF RF EX ME WB IF RF EX ME time 2008 4 15 In a given cycle each instruction is in a different stage but every stage is active WB The pipeline is full here course cpeg421 08s Topic6a ppt 24 WB Parallelism in a pipeline Example i1 i2 i3 i4 add add lw add r1 r3 r4 r5 r1 r3 0 r1 r3 Assume r2 r1 Register instruction 1 cycle Memory instruction 3 cycle r4 Consider two possible instruction schedules permutations Schedule S1 completion time 6 cycles i1 i2 i3 i4 2 Idle Cycles Schedule S2 completion time 5 cycles i1