Loop Scheduling and Software Pipelining 19 1 13 course cpeg421 08s Topic 7 ppt 1 Reading List Slides Topic 7 and 7a Other papers as assigned in class or homework 19 1 13 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 19 1 13 course cpeg421 08s Topic 7 ppt 3 Outline Brief overview Problem formulation of the modulo scheduling problem Solution methods Summary 19 1 13 course cpeg421 08s Topic 7 ppt 4 General Compiler Source Framework 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 19 1 13 course cpeg421 08s Topic 7 ppt 5 Questions How to formulate the loop scheduling problem How to model it How to solve it 19 1 13 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 19 1 13 course cpeg421 08s Topic 7 ppt 7 Challenges of Loop Scheduling A DDG With Cycles Right strategy 19 1 13 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 19 1 13 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 19 1 13 course cpeg421 08s Topic 7 ppt 10 A A Short Short Tour Tour on on Data Data Dependence Dependence Graphs Graphs for for Loops Loops 19 1 13 course cpeg421 08s Topic 7 ppt 11 Basic Basic Concept Concept and and Motivation 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 19 1 13 course cpeg421 08s Topic 7 ppt 12 Types Types of of Data Data Dependence Dependence X Flow dependence X 1 X Anti dependence 0 X Output dependence X X 19 1 13 course cpeg421 08s Topic 7 ppt 13 Data Data Dependence Dependence Example 1 S1 S1 A 0 S2 S2 B A S3 C A D S4 D 2 S3 S4 Sx Sy Sy depends on Sx 19 1 13 course cpeg421 08s Topic 7 ppt 14 Data Data Dependence Dependence Example 2 Con d S1 S1 A 0 S2 B A S3 A B 1 S4 C A S2 S3 S4 S 1 S2 19 1 13 S3 Output dep 1 S3 anti dep 0 course cpeg421 08s Topic 7 ppt 15 Should Should we we consider consider input input dependence dependence X X 19 1 13 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 Subscript Variables 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 19 1 13 course cpeg421 08s Topic 7 ppt 17 Dependence Dependence Graph Graph Con d Applications register allocation instruction scheduling loop scheduling vectorization parallelization memory hierarchy optimization 19 1 13 course cpeg421 08s Topic 7 ppt 18 Data Data Dependence Dependence in in Loops 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 19 1 13 X 2 Y 2 Z 2 A 2 X 1 1 I 3 X 3 Y 3 Z 3 A 3 X 2 1 course cpeg421 08s Topic 7 ppt I 4 X 4 Y 4 Z 4 A 4 X 3 1 19 Data Data Dependence Dependence in in Loops 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 19 1 13 course cpeg421 08s Topic 7 ppt 20 An Example for i 0 to N 1 do iterations a a i a i 1 R i b b i a i c i 1 c c i b i 1 end II b c 19 1 13 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 19 1 13 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 b N 1 a N 1 c N 2 epilogue c N 1 b N 1 1 19 1 13 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 …