程序循环优化方法10

1、提升循环级并行IntelCopyright 2002 Intel Corporation1AgendaIntroductionWho Cares?DefinitionLoop Dependence and RemovalDependency Identification LabSummary2IntroductionLoops must meet certain criteriaIteration IndependenceMemory DisambiguationHigh Loop CountEtc3Who Cares实现真正的并行:OpenMPAuto Parallelization显式的指

2、令级并行 ILP (Instruction Level Parallelism)Streaming SIMD (MMX, SSE, SSE2, )Software Pipelining on Intel Itanium ProcessorRemove Dependencies for the Out-of-Order CoreMore Instructions run in parallel on Intel Itanium-Processor自动编译器并行High Level Optimizations4Definitionint aMAX;for (J=0;JMAX;J+) aJ = bJ

3、;Loop Independence: Iteration Y of a loop is independent of when or whether iteration X happens5图例OpenMP: True ParallelismSIMD: VectorizationSWP: Software PipeliningOOO: Out-of-Order Core ILP: Instruction Level Parallelism Green: Benefits from concept Yellow: Some Benefits from Concept Red: No Benef

4、it from Concept 6AgendaDefinitionWho Cares?Loop Dependence and RemovalData DependenciesRemoving DependenciesData Ambiguity and the CompilerDependency Removal LabSummary7Flow DependencyRead After WriteCross-Iteration Flow Dependence: Variables written then read in different iterationsfor (J=1; JMAX;

5、J+) AJ=AJ-1;A1=A0;A2=A1;8Anti-DependencyWrite After ReadCross-Iteration Anti-Dependence: Variables written then read in different iterationsfor (J=1; JMAX; J+) AJ=AJ+1; A1=A2;A2=A3;9Output DependencyWrite After WriteCross-Iteration Output Dependence: Variables written then written again in a differe

6、nt iterationfor (J=1; JMAX; J+) AJ=BJ;AJ+1=CJ;A1=B1;A2=C1;A2=B1;A3=C1;10IntraIteration DependencyDependency within an iterationHurts ILPMay be automatically removed by compilerK = 1;for (J=1; JMAX; J+) AJ=AJ + 1;BK=AK + 1;K = K + 2; A1 = A1 + 1;B1= A1 + 1;11for (J=1; JMAX; J+) AJ= A0 + J;Remove Depe

7、ndenciesBest ChoiceRequirement for true ParallelismNot all dependencies can be removedfor (J=1; JMAX; J+) AJ=AJ-1 + 1;12for (J=1;JMAX;J+=2) AJ=AJ-1 + BJ;AJ+1=AJ-1 + (BJ + BJ+1);Increasing ILP, without removing dependencies Good: Unroll LoopMake sure the compiler cant or didnt do this for youCompiler

8、 should not apply common sub-expression elimination Also notice that if this is floating point data - precision could be alteredfor (J=1;JMAX;J+) AJ =AJ-1 + BJ;13Induction VariablesInduction variables are incremented on each trip through the loopFix by replacing increment expressions with pure funct

9、ion of loop indexi1 = 0;i2 = 0;for(J=0,JMAX,J+) i1 = i1 + 1; B(i1) = i2 = i2 + J; A(i2) = for(J=0,JMAX,J+) B(J) = . A(J*2 + J)/2)= .14ReductionsReductions collapse array data to scalar data via associative operations:Take advantage of associativity and compute partial sums or local maximum in privat

10、e storageNext, combine partial results into shared result, taking care to synchronize accessfor (J=0; JMAX; J+) sum = sum + cJ;15Data Ambiguity and the Compilervoid func(int *a, int *b) for (J=0;JMAX;J+) aJ = bJ;Are the loop iterations independent?The C+ compiler has no ideaNo chance for optimizatio

11、n - In order to run error free the compiler assumes that a and b overlap16Function Callsfor (J=0;J=0;J-) compute(J,.) A Simple TestReverse the loop order and rerun in serialIf results are unchanged, the loop is Independent*for(J=0;JMAX;J+) compute(J,.) *Exception: Loops with induction variablesReverse19SummaryLoop Independence: Loop Iterations are independent of each other.Explained its importanceILP and Para