程序与编译器的组合优化方法

ResponsiblePointer

UsageCompileraliasanalysislimitsoptimizationsDeveloperknowsApp–tellcompiler!Avoidpointingtosamememoryaddresswith2differentpointersUsearraynotationwhenpossibleAvoidpointerarithmeticifpossibleDataIssuesPointerDisambiguation-Oafile.c(Windows) -fno-aliasfile.c(Linux)Allpointersinfile.careassumednottoalias-Owfile.c(Windows) Not(yet)onLinuxAssumenoaliasingwithinfunctions(ie,pointerargumentsareunique)-Qrestrictfile.c(Windows) -restrict(Linux)RestrictQualifier:Enablespointerdisambiguation-Zafile.c(Windows) -ansi(Linux)EnforcestrictANSIcompilance(requiresthatpointerstodifferentdatatypesarenotaliased)DataIssuesHighLevelOptimizationsAvailableatO3PrefetchLoopinterchangeUnrollingCacheblocking

Unroll-and-jamScalarreplacementRedundantzero-tripeliminationDatadependenceanalysisReuseanalysisLooprecoveryCanonicalexpressionsLoopfusionLoopdistributionLoopreversalLoopskewingLooppeelingScalarexpansionRegisterblockingHLO4DataPrefetchingfori=1,Mforj=1,NA[j,i]=B[0,j]+B[0,j+1]end_forend_forfori=1,Mforj=1,NA[j,i]=B[0,j]+B[0,j+1]if(mod(j,8)==0)lfetch.nta(A[j+d,i])if(i==1)lfetch.nt1(B[0,j+d])end_forend_for

Addingprefetchinginstructionsusingselectiveprefetching.Worksforarray,pointers,Cstructure,C/C++parameters

Goal:toissueoneprefetchinstructionpercachelineItaniumcachelinesareL1:32B,L2:64B,L3:64BItanium2cachelinesareL1:64B,L2:128B,L3:128B-O3doesthisforyou

“LettheCompilerdothework!”HLOLoopInterchangeNote:c[i][j]termisconstantininnerloopInterchangetoallowunitstridememoryaccessDemoHLO

for(i=0;i<NUM;i++){for(j=0;j<NUM;j++){for(k=0;k<NUM;k++){c[i][j]=c[i][j]+a[i][k]*b[k][j];}}}ConsecutivememoryindexFastInnerloopindexLab:MatrixwithLoopInterchange,-O2UnitStridememoryaccess

C/C++Example–FortranoppositebN-10bN-1jbN-1N-1b10b11b12b13b1jb1N-1b00b01b02b03b0jb0N-1bNon-unitstrideddataaccessaN-10aN-1N-1ai0ai1ai2ai3aiN-1a10a11a12a13a1N-1a00a01a02a03a0N-1akjkiincrementingKgets

nonconsecutive

memoryelementsUnitstrideddataaccessincrementingKgets

consecutive

memoryelementsHLOLoopafterinterchangeNote:a[i][k]termisconstantininnerloopTwoloads,oneStore,oneFMA:F/M=.33,Unitstride

for(i=0;i<NUM;i++){for(k=0;k<NUM;k++){for(j=0;j<NUM;j++){c[i][j]=c[i][j]+a[i][k]*b[k][j];}}}HLODemoLab:MatrixwithLoopInterchange,-O3UnitStridememoryaccess(C/C++)AllUnitstrideddataaccessaN-10aN-1N-1ai0ai1ai2ai3aiN-1a10a11a12a13a1N-1a00a01a02a03a0N-1kakibN-10bN-1N-1bk0bk1bk2bk3bkN-1b10b11b12b13b1N-1b00b01b02b03b0N-1jjbkFastestincrementedindexConsecutivememoryaccessNextfastestloopindex

ConsecutivememoryindexHLOLoopUnrollingN=1025M=5DOI=1,NDOJ=1,MA(J,I)=B(J,I)+C(J,I)*DENDDOENDDOII=IMOD(N,4)DOI=1,IIDOJ=1,MA(J,I)=B(J,I)+C(J,I)*DENDDOENDDODOI=II,N,4DOJ=1,MA(J,I)=B(J,I)+C(J,I)*DA(J,I+1)=B(J,I+1)+C(J,I+1)*DA(J,I+2)=B(J,I+2)+C(J,I+2)*DA(J,I+3)=B(J,I+3)+C(J,I+3)*DENDDOENDDO

UnrollOuterloopby4Preconditioningloop

UnrolllargestloopsIfloopsizeknowncaneliminatepreconditioningloopbychoosingnumberoftimestounrollHLODemoLab:MatrixwithLoopUnrollingby2LoopUnrolling-CandidatesIftripcountislowandknownatcompiletimeitmaymakesensetoFullyunrollPoorCandidates:(similarissuesforSWPorvectorizer)Lowtripcountloops–for(j=0;j<N;j++):N=4atruntimeFatloops–loopbodyalreadyhaslotsofcomputationtakingplaceLoopscontainingprocedurecallsLoopswithbranchesHLOLoopUnrolling-BenefitsBenefitsperformmorecomputationsperloopiterationReducestheeffectofloopoverheadCanincreaseFloatingpointtomemoryaccessratio(F/M)CostsRegisterpressureCodebloatHLOAllloopsunrolledby4resultsin(periteration) 32Loads,16stores,64FMA:F/M=1.33LoopUnrolling-Example

for(i=0;i<NUM;i=i+2){for(k=0;k<NUM;k=k+2){for(j=0;j<NUM;j++){ c[i][j]=c[i][j]+a[i][k]*b[k][j]; c[i+1][j