Loop Scheduling and Software Pipelining 2008 04 24 course cpeg421 08s Topic 7 ppt 1 Reading List Slides Topic 7 and 7a Other papers as assigned in class or homework 2008 04 24 course cpeg421 08s Topic 7 ppt 2 ABET Outcome Ability to apply knowledge of basic code generation techniques e g Loop scheduling e g software pipelining techniques 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 04 24 course cpeg421 08s Topic 7 ppt 3 Outline Brief overview Problem formulation of the modulo scheduling problem Solution methods Summary 2008 04 24 course cpeg421 08s Topic 7 ppt 4 General Compiler Framework Source Inter Procedural Optimization IPA Loop Nest Optimization LNO ME Global Optimization OPT Innermost Loop scheduling BE CG Global inst scheduling Reg alloc Good IPO Good LNO Good global optimization Good integration of IPO LNO OPT Smooth information passing between FE and CG Complete and flexible support of inner loop scheduling SWP instruction scheduling and register allocation Arch Models Local inst scheduling Executable 2008 04 24 course cpeg421 08s Topic 7 ppt 5 Questions How to formulate the loop scheduling problem How to model it How to solve it 2008 04 24 course cpeg421 08s Topic 7 ppt 6 Questions cont d Instruction scheduling for code without loops a review Dependence graphs may become cyclic So critical path length is less obvious Is it becoming harder What new insights are required to formulate and solve it 2008 04 24 course cpeg421 08s Topic 7 ppt 7 Challenges of Loop Scheduling A DDG With Cycles Right strategy 2008 04 24 course cpeg421 08s Topic 7 ppt 8 Observations Execution of good loops tend to be regular and repetitive a pattern may appear This gives cyclic scheduling problem a new twist How to efficiently derive a pattern 2008 04 24 course cpeg421 08s Topic 7 ppt 9 Problem Formulation I Given a weighted dependence graph derive a schedule which is time optimal under a machine model M Def A schedule S of a loop L is time optimal if among all legal schedules of L no other schedule that is faster than S Note There may be more than one time optimal schedule 2008 04 24 course cpeg421 08s Topic 7 ppt 10 A Short Tour on Data Dependence Graphs for Loops 2008 04 24 course cpeg421 08s Topic 7 ppt 11 Basic Concept and Motivation Data dependence between 2 accesses The same memory location Exist an execution path between them One of them is a write Three types of data dependence Dependence graphs Things are not simple when dealing with loops 2008 04 24 course cpeg421 08s Topic 7 ppt 12 Types of Data Dependence X Flow dependence X X Anti dependence 1 X X Output dependence 0 X 2008 04 24 course cpeg421 08s Topic 7 ppt 13 Data Dependence Example 1 S1 A 0 S2 B A S3 C A D S4 D 2 S1 S2 S3 S4 Sx Sy Sy depends on Sx 2008 04 24 course cpeg421 08s Topic 7 ppt 14 Data Dependence Con d Example 2 S1 S1 A 0 S2 B A S3 A B 1 S4 C A S2 S3 S4 S1 0 S3 Output dep S2 1 S3 anti dep 2008 04 24 course cpeg421 08s Topic 7 ppt 15 Should we consider input dependence X X 2008 04 24 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 Topic 7 ppt 16 Subscript Variables Extension of def use chains to employ a more precise treatment of arrays especially in iterative loops DO I 1 N A I 1 X I 1 B I X I A I 5 ENDDO 2008 04 24 course cpeg421 08s Topic 7 ppt 17 Dependence Graph Con d Applications register allocation instruction scheduling loop scheduling vectorization parallelization memory hierarchy optimization 2008 04 24 course cpeg421 08s Topic 7 ppt 18 Data Dependence in Loops An Example Find the dependence relations due to the array X in the program below 1 for I 2 to 9 do 2 X I Y I Z I 3 A I X I 1 1 4 end for Solution To find the data dependence relations in a simple loop we can unroll the loop and see which statement instances depend on which others I 2 2 3 2008 04 24 X 2 Y 2 Z 2 A 2 X 1 1 I 3 I 4 X 3 Y 3 Z 3 A 3 X 2 1 X 4 Y 4 Z 4 A 4 X 3 1 course cpeg421 08s Topic 7 ppt 19 Data Dependence in Loops Con d In our example there is a loop carried lexically forward flow dependence relation S2 1 Dependence distance 1 S3 Data dependence graph for statements in a loop Loop carried vs loop independent Lexical forward vs lexical backward 2008 04 24 course cpeg421 08s Topic 7 ppt 20 An Example for i 0 to N 1 do a a i a i 1 R i b b i a i c i 1 c c i b i 1 end iterations II b c 2008 04 24 Note We use a token here to represent a flow dependence of distance 1 time a time i 0 0 a 1 b 2 c i 1 i 2 i 3 a 3 b 4 c a So iteration interval II 2 Assume each operation takes 1 cycle and there is only one addition unit course cpeg421 08s Topic 7 ppt 21 Software Pipeline Concept Software Pipeline is a technique that reduces the execution time of important loops by interweaving operations from many iterations to optimize the use of resources stf fadds ldf cmp bg sub 0 2008 04 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 course cpeg421 08s Topic 7 ppt time 22 The Structrure of the SWP code prologue a 0 a 1 R 0 pattern prologue for i 0 to N 2 do b i a i c i 1 a i 1 a i R i 1 c i b i 1 bi ci a i 1 end epilogue epilogue b N 1 a N 1 c N 2 c N 1 b N 1 1 2008 04 24 course cpeg421 08s Topic 7 ppt 23 Software Pipeline Cont d What limits the speed of a loop Data dependencies recurrence initiation interval rec mii Processor resources resource initiation interval res mii Initiation interval stf fadds ldf cmp bg sub 0 1 2008 04 24 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 course cpeg421 08s Topic 7 ppt time 24 Previous Approaches Approach I Operational Emulate the loop execution under the …