程序的循环优化方法

AgendaIntroductionWhoCares?DefinitionLoopDependenceandRemovalDependencyIdentificationLabSummaryIntroductionLoopsmustmeetcertaincriteria…IterationIndependenceMemoryDisambiguationHighLoopCountEtc…WhoCares实现真正的并行:OpenMPAutoParallelization…显式的指令级并行ILP(InstructionLevelParallelism)StreamingSIMD(MMX,SSE,SSE2,…)SoftwarePipeliningonIntel®Itanium™ProcessorRemoveDependenciesfortheOut-of-OrderCoreMoreInstructionsruninparallelonIntelItanium-Processor自动编译器并行HighLevelOptimizationsDefinitioninta[MAX];for(J=0;J<MAX;J++){ a[J]=b[J];}LoopIndependence:IterationYofaloopisindependentofwhenorwhetheriterationXhappens图例OpenMP:TrueParallelismSIMD:VectorizationSWP:SoftwarePipeliningOOO:Out-of-OrderCoreILP:InstructionLevelParallelismGreen:BenefitsfromconceptYellow:SomeBenefitsfromConceptRed:NoBenefitfromConceptAgendaDefinitionWhoCares?LoopDependenceandRemovalDataDependenciesRemovingDependenciesDataAmbiguityandtheCompilerDependencyRemovalLabSummaryFlowDependencyReadAfterWriteCross-IterationFlowDependence:Variableswrittenthenreadindifferentiterationsfor(J=1;J<MAX;J++){ A[J]=A[J-1];} A[1]=A[0];

A[2]=A[1];Anti-DependencyWriteAfterReadCross-IterationAnti-Dependence:Variableswrittenthenreadindifferentiterationsfor(J=1;J<MAX;J++){ A[J]=A[J+1];}

A[1]=A[2]; A[2]=A[3];OutputDependencyWriteAfterWriteCross-IterationOutputDependence:Variableswrittenthenwrittenagaininadifferentiterationfor(J=1;J<MAX;J++){ A[J]=B[J]; A[J+1]=C[J];} A[1]=B[1];

A[2]=C[1];

A[2]=B[1]; A[3]=C[1];IntraIterationDependencyDependencywithinaniterationHurtsILPMaybeautomaticallyremovedbycompilerK=1;for(J=1;J<MAX;J++){ A[J]=A[J]+1; B[K]=A[K]+1; K=K+2;} A[1]=A[1]+1; B[1]=A[1]+1;for(J=1;J<MAX;J++){ A[J]=A[0]+J;}RemoveDependenciesBestChoiceRequirementfortrueParallelismNotalldependenciescanberemovedfor(J=1;J<MAX;J++){ A[J]=A[J-1]+1;}for(J=1;J<MAX;J+=2){ A[J]=A[J-1]+B[J]; A[J+1]=A[J-1]+(B[J]+B[J+1]);}IncreasingILP,withoutremovingdependenciesGood:UnrollLoopMakesurethecompilercan’tordidn’tdothisforyouCompilershouldnotapplycommonsub-expressioneliminationAlsonoticethatifthisisfloatingpointdata-precisioncouldbealteredfor(J=1;J<MAX;J++){ A[J]=A[J-1]+B[J];}InductionVariablesInductionvariablesareincrementedoneachtripthroughtheloopFixbyreplacingincrementexpressionswithpurefunctionofloopindexi1=0;

i2=0;

for(J=0,J<MAX,J++){

i1=i1+1;

B(i1)=…i2=i2+J;

A(i2)=…

}for(J=0,J<MAX,J++){

B(J)=...

A((J**2+J)/2)=...

}ReductionsReductionscollapsearraydatatoscalardataviaassociativeoperations:

TakeadvantageofassociativityandcomputepartialsumsorlocalmaximuminprivatestorageNext,combinepartialresultsintosharedresult,takingcaretosynchronizeaccessfor(J=0;J<MAX;J++)

sum=sum+c[J];DataAmbiguityandtheCompilervoidfunc(int*a,int*b){ for(J=0;J<MAX;J++){ a[J]=b[J]; }}Aretheloopiterationsindependent?TheC++compilerhasnoideaNochanceforoptimization-InordertorunerrorfreethecompilerassumesthataandboverlapFunctionCallsfor(J=0;J<MAX;J++){ compute(a[J],b[J]); a[J][1]=sin(b[J]);}GenerallyfunctioncallsinhibitILPExceptions:TranscendentalsIPOcompilesFunctionCallswithStateManyroutinesmaintainstateacrosscalls:MemoryallocationPseudo-randomnumbergeneratorsI/OroutinesGraphicslibrariesThird-partylibrariesParallelaccesstosuchroutinesisunsafeunlesssynchronizedCheckdocumentationforspecificfunctionstodeterminethread-safetyfor(J=MAX-1;J>=0;J--){<...>compute(J,...)<...>}ASimpleTestReversetheloop