写出网站建设的基本流程,晋城市公共事业建设局网站,贸易公司网站建设,欢迎进入中国建设银行网站引言编译器里的循环优化有两个重要的目标#xff0c;一是提高局部性#xff0c;二是提高并行性#xff0c;loop tiling是提高数据局部性最重要的优化之一#xff0c;是传统编译器和深度编译器考虑的重中之重#xff0c;我们今天来看看如何做loop tiling#xff08;循环分…引言编译器里的循环优化有两个重要的目标一是提高局部性二是提高并行性loop tiling是提高数据局部性最重要的优化之一是传统编译器和深度编译器考虑的重中之重我们今天来看看如何做loop tiling循环分块aka cache blocking。loop tiling的basic idea很简单就是一个cache line现在被用过以后后面什么时候还会被用但是按循环默认的执行方式可能到下次再被用到的时候已经被evict了。于是我们就把循环怎么重排一下使得一个cache line在被evict之前就被再次使用。在该文中我们讨论一个简单的tiling方法以及通过计算cache miss来估算tiling的作用。例程一我们从一个简单的例子看起为了更好的可读性我们使用Fortran语法column majorDO I 1, NDO J 1, MA(I) A(I) B(J) END DO
END DO首先我们分析一下该循环的重用模式reuse pattern可以看到A(I)在每一轮J循环中被重用、B(J)在每一轮I循环中会被重用。当前由于I是外层循环所以当B(J)在J层循环中的跨度太大时无法fit in the cache则在被下一次I重用时数据已被清出缓存。譬如我们假设M和N是很大的数大数组所以对于每一轮I循环等到B(M)被访问时B(1)、B(2)等已经被清出缓存了。分析完了重用模式我们现在计算cache miss。假设每个cache line能容纳b个数组元素associativity是fully associative则可计算出A的cache miss次数是N/bB的cache miss次数是N*M/b。现在我们来看看什么是tiling以及如何通过做tiling减少cache miss。我们先考虑tile J层循环将B的访问模式变成如下令tile size为TT一般是b的倍数也足够小可以认为N,M b,TT的取值应该使得当B(T)被访问时B(1)也依然还在缓存中I1: B(1), B(2), B(3) ... B(T)
I2: B(1), B(2), B(3) ... B(T)
I3: B(1), B(2), B(3) ... B(T)
...
IN: B(1), B(2), B(3) ... B(T)I1: B(T1), B(T2), B(T3) ... B(2T)
I2: B(T1), B(T2), B(T3) ... B(2T)
I3: B(T1), B(T2), B(T3) ... B(2T)
...
IN: B(T1), B(T2), B(T3) ... B(2T)小灯泡tile的本质当总的数据量无法fit in cache的时候把数据分成一个一个tile让每一个tile的数据fit in the cache。所以tiling一般从最内层循环开始tile外层循环的话一个tile就包括整个内层循环这样的tile太大。此时循环变成DO J 1, M, TDO I 1, NDO jj J, min(JT-1, M)A(I) A(I) B(jj)END DOEND DO
END DO注意当我们tile J层循环的时候tile以后J层循环就跑到了外层loop interchange这样又会影响A的缓存命中率。该变换又称为strip-mine-and-interchange。我们可以计算此时A的cache miss次数是(M/T) * (N/b)B的cache miss次数是T/b * M/T M/b每一轮J层循环miss一次所以总共的cache miss是MN/(bT) M/btile之前是N/bN*M/b。所以在M和N的大小也相当的情况下做tiling大约能将cache miss缩小T倍。思考题1为什么分块以后还要交换循环I和J循环交换是否总是可行的那要是我们选择tile I层循环呢我们看看会发生什么。要tile I层循环首先将I、J循环调换DO J 1, MDO I 1, NA(I) A(I) B(J) END DO
END DO依然假设tile sizeT访问模式将变为J1: A(1) B(1), A(2) B(1), A(3) B(1) ... A(T) B(1)
J2: A(1) B(2), A(2) B(2), A(3) B(2) ... A(T) B(2)
...
JM: A(1) B(M), A(2) B(M), A(3) B(M) ... A(T) B(M)J1: A(T1) B(1), A(T2) B(1), A(T3) B(1) ... A(2T) B(1)
J2: A(T1) B(2), A(T2) B(2), A(T3) B(2) ... A(2T) B(2)
...
JM:A(T1) B(M), A(T2) B(M), A(T3) B(M) ... A(2T) B(M)
...此时循环变成DO I 1, N, TDO J 1, MDO ii I, min(IT-1, N)A(ii) A(ii) B(J)END DOEND DO
END DO此时A的cache miss次数是T/b * N/TB的cache miss次数是M/b*(N/T)加起来就是(MN)/(bT)N/b而tile J层循环得到的cache miss是(MN)* (bT)M/b所以对于该循环到底应该tile I层循环还是J层循环更好其实取决于M和N的相当大小。思考题2是否可以既tile I层循环也tile J层循环如果可以这样做是否具有更好的局部性例程二DO J 1, MDO I 1, ND(I) D(I) B(I, J)END DO
END DO注fortran是column major layoutB(I, J)是访问二维数组相当于C语言中的B[I][J]。不管是column major还是row major不影响tiling的原理。注对于多维数组我们在计算cache miss时假设数据的存储是连续的。该循环的cache miss是M*N/b M*N/bD和B的miss都是M*N/b。还是用之前的strip-mine-and-interchange方法来tile内层循环IDO I 1, N, TDO J 1, MDO ii I, min(IT-1, N)D(ii) D(ii) B(ii, J)END DOEND DO
END DOtiling loop I 之后的cache miss是N/T * T/b T/b * M * N/TJ层循环每一轮一开始都会miss B N/b NM/b。再考虑tile J层循环需要首先调换I、J层循环DO J 1, M, TDO I 1, NDO jj J, min(JT-1, M)D(I) D(I) B(I, jj)END DOEND DO
END DO此时的cache miss是N/b * M/T T*(N/b)*M/T NM/(bT) MN/b。跟tiling I循环相比由于M一般远大于T所以会有更高的cache miss。造成这个区别的本质原因在于D(I)在J层的重用没有被exploited。例程三我们再来看一个更有趣的例子矩阵转置。DO J 1, NDO I 1, NA(I, J) B(J, I)ENDDO
ENDDO这个例子之所以有趣是因为无论是否做交换I、J循环交换是合法的cache miss都是N*N/b N*N。下面是交换I、J循环后的情况DO I 1, NDO J 1, NA(I, J) B(J, I)ENDDO
ENDDO如果I是内层循环则A的miss是N*N/b而B每次都是miss所以一共miss N*N次。如果J是内层循环则是A每次都是miss而B miss N*N/b次。不管哪种情况都有一个没有achieve locality。那有什么办法让A和B都能achieve locality吗答案是可以请看如下的tilingDO I 1, N, TDO J 1, N, TDO ii I, min(IT-1, N)DO jj J, min(JT-1, N)A(ii, jj) B(jj, ii)ENDDOENDDOENDDO
ENDDO这里的精髓在于tiling不仅可以利用temporal locality也能用上spatial locality。对于A(ii, jj)虽然最内层循环是jj没有locality但是当内层循环jj完了以后开始下一轮ii的时候因为tiling使得A(ii, jj)、A(ii, jj1)依然会在缓存于是这时的A(ii1, jj)、A(ii1, jj1)等就能命中缓存spatial locality。下面是各层cache miss的breakdown外层的cache miss包含了内层的loop/cache missesABjjTT/biiT * T/bT/b * TJT * T/b * N/T NT/bT/b * T * N/T NT/bINT/b * N/T N*N/bNT/b * N/T N*N/b总结 循环分块的本质是在外层循环挖掘内层的temporal和spatial reuse。基本的方法是strip-mine-and-interchange。以下是takeaway循环分块是什么如何做对于不同的循环层分块有什么不同的结果如何计算cache miss想了解更复杂的循环如何做tiling譬如经典的矩阵乘法以及tiling的合法性请看本系列第二讲https://zhuanlan.zhihu.com/p/301905385zhuanlan.zhihu.com
