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

Responsible Pointer UsageCompiler alias analysis limits optimizationsCompiler alias analysis limits optimizationsDeveloper knows App Developer knows App tell compiler!tell compiler!Avoid pointing to same memory address with Avoid pointing to same memory address with 2 different pointers2 different pointersUse array notation when possibleUse array notation when possibleAvoid pointer arithmetic if possibleAvoid pointer arithmetic if possibleData IssuesData IssuesPointer Disambiguation-Oa file.c(Windows)-Oa file.c(Windows)-fno-alias file.c(Linux)-fno-alias file.c(Linux)All pointers in file.c are assumed not to aliasAll pointers in file.c are assumed not to alias-Ow file.c(Windows)-Ow file.c(Windows)Not(yet)on LinuxNot(yet)on Linux Assume no aliasing within functions(ie,pointer Assume no aliasing within functions(ie,pointer arguments are unique)arguments are unique)-Qrestrict file.c(Windows)Qrestrict file.c(Windows)-restrict(Linux)-restrict(Linux)Restrict Qualifier:Enables pointer disambiguationRestrict Qualifier:Enables pointer disambiguation-Za file.c(Windows)-Za file.c(Windows)-ansi(Linux)-ansi(Linux)Enforce strict ANSI compilance(requires that pointers to Enforce strict ANSI compilance(requires that pointers to different data types are not aliased)different data types are not aliased)Data IssuesData IssuesHigh Level Optimizations Available at O3Available at O3 Prefetch Prefetch Loop interchangeLoop interchange UnrollingUnrolling Cache blockingCache blocking Unroll-and-jam Unroll-and-jam Scalar replacementScalar replacement Redundant zero-trip Redundant zero-trip eliminationelimination Data dependence Data dependence analysisanalysis Reuse analysisReuse analysis Loop recoveryLoop recovery Canonical expressionsCanonical expressions Loop fusionLoop fusion Loop distributionLoop distribution Loop reversalLoop reversal Loop skewingLoop skewing Loop peelingLoop peeling Scalar expansionScalar expansion Register blockingRegister blockingHLOHLO4 4Data Prefetchingfor i=1,M for j=1,N Aj,i=B0,j +B0,j+1 end_forend_forfor i=1,M for j=1,N Aj,i=B0,j +B0,j+1 if(mod(j,8)=0)lfetch.nta(Aj+d,i)if(i=1)lfetch.nt1(B0,j+d)end_forend_for Adding prefetching instructions using selective prefetching.Works for array,pointers,C structure,C/C+parameters Goal:to issue one prefetch instruction per cache line Itanium cache lines are L1:32B,L2:64B,L3:64B Itanium 2 cache lines are L1:64B,L2:128B,L3:128B-O3 does this for you“Let the Compiler do the work!”HLOHLOLoop InterchangeNote:cij term is constant in inner loopNote:cij term is constant in inner loopInterchange to allow unit stride memory Interchange to allow unit stride memory accessaccessDemoHLOHLO for(i=0;iNUM;i+)for(j=0;jNUM;j+)for(k=0;kNUM;k+)cij=cij+aik*bkj;Consecutive memory indexFast Inner loop indexLab:Matrix with Loop Interchange,-O2Lab:Matrix with Loop Interchange,-O2Unit Stride memory accessC/C+Example C/C+Example Fortran opposite Fortran oppositebN-10bN-10bN-1jbN-1jbN-1N-1bN-1N-1b10b10 b11b11 b12b12 b13b13b1jb1jb1N-1b1N-1b00b00 b01b01 b02b02 b03b03b0jb0jb0N-1b0N-1bNon-unit strided data accessaN-10aN-10aN-1N-1aN-1N-1ai0ai0ai1ai1ai2ai2ai3ai3aiN-1aiN-1a10a10a11a11a12a12 a13a13a1N-1a1N-1a00a00 a01a01 a02a02 a03a03a0N-1a0N-1akjkiincrementing K gets non consecutive memory elementsUnit strided data accessincrementing K gets consecutive memory elementsHLOHLOLoop after interchange Note:aik term is constant in inner loopNote:aik term is constant in inner loop Two loads,one Store,one FMA:F/M=.33,Unit Two loads,one Store,one FMA:F/M=.33,Unit stridestride for(i=0;iNUM;i+)for(k=0;kNUM;k+)for(j=0;jNUM;j+)cij=cij+aik*bkj;HLOHLODemoLab:Matrix with Loop Interchange,-O3Lab:Matrix with Loop Interchange,-O3Unit Stride memory access(C/C+)All Unit strided data accessaN-10aN-10aN-1N-1aN-1N-1ai0ai0ai1ai1ai2ai2ai3ai3aiN-1aiN-1a10a10a11a11a12a12 a13a13a1N-1a1N-1a00a00 a01a01 a02a02 a03a03a0N-1a0N-1kakibN-10bN-10bN-1N-1bN-1N-1bk0bk0 bk1bk1 bk2bk2 bk3bk3bkN-1bkN-1b10b10 b11b11 b12b12 b13b13b1N-1b1N-1b00b00 b01b01 b02b02 b03b03b0N-1b0N-1j jbkFastest incremented indexConsecutive memory accessNext fastest loop indexConsecutive memory indexHLOHLOLoop UnrollingN=1025M=5DO I=1,N DO J=1,M A(J,I)=B(J,I)+C(J,I)*D ENDDOENDDOII=IMOD(N,4)DO I=1,II DO J=1,M A(J,I)=B(J,I)+C(J,I)*D ENDDOENDDODO I=II,N,4 DO J=1,M A(J,I)=B(J,I)+C(J,I)*D A(J,I+1)=B(J,I+1)+C(J,I+1)*D A(J,I+2)=B(J,I+2)+C(J,I+2)*D A(J,I+3)=B(J,I+3)+C(J,I+3)*D ENDDOENDDO Unroll Outer loop by 4Preconditioning loop Unroll largest loops If loop size known can eliminate preconditioning loop by choosing number of times to unrollHLOHLODemoLab:Matrix with Loop Unrolling by 2Lab:Matrix with Loop Unrolling by 2Loop Unrolling-CandidatesIf trip count is low and known at compile time it If trip count is low and known at compile time it may make sense to may make sense to FullyFully unroll unrollPoor Candidates:(similar issues for SWP or Poor Candidates:(similar issues for SWP or vectorizer)vectorizer)Low trip count loops Low trip count loops for(j=0;j N;j+):N=4 at for(j=0;j N;j+):N=4 at runtimeruntime Fat loops Fat loops loop body already has lots of loop body already has lots of computation taking placecomputation taking place Loops containing procedure callsLoops containing procedure calls Loops with branchesLoops with branchesHLOHLOLoop Unrolling-BenefitsBenefitsperform more computations per loop perform more computations per loop iterationiterationReduces the effect of loop overheadReduces the effect of loop overheadCan increase Floating point to memory Can increase Floating point to memory access ratio(F/M)access ratio(F/M)CostsRegister pressureRegister pressureCode bloatCode bloatHLOHLOAll loops unrolled by 4 results in(per All loops unrolled by 4 results in(per iteration)iteration)32 Loads,16 stores,64 FMA:F/M=1.3332 Loads,16 stores,64 FMA:F/M=1.33Loop Unrolling-Example-Example for(i=0;iNUM;i=i+2)for(k=0;kNUM;k=k+2)for(j=0;jNUM;j+)cij=cij+aik*bkj;ci+1j=ci+1j+ai+1k*bkj;cij=cij+aik+1*bk+1j;ci+1j=ci+1j+ai+1k+1*bk+1j;Loop invariantHLOHLOLabDemo Lab:Matrix with Loop Unrolling by 4Demo Lab:Matrix with Loop Unrolling by 41313Cache Blockingfor i=1,1000 for j=1,1000 for k=1,1000 Ai,j,k=Ai,j,k +Bi,k,j end_for end_forend_forfor v=1,1000,20 for u=1,1000,20 for k=v,v+19 for j=u,u+19 for i=1,1000 Ai,j,k=Ai,j,k +Bi,k,j end_for end_for end_for end_forend_forWhen all arrays in loop do not fit in cacheEffective for huge out-of-core memory applicationsEffective for large out-of-cache applicationsWork on“neighborhoods”of data and keep these neighborhoods in cacheHelps reduce TLB&Cache missesHLOHLO