存储系统对于程序执行时间有显著影响。处理器由于访存导致的暂停时间受到失效率和失效代价的影响。众所周知,为了弥补CPU与内存两者之间的性能差异,就在CPU内部引入了CPU cache,也称高速缓存。CPU cache通常分为大小不等的三级缓存,分别是L1 cache、L2 cache和L3 cache。如图1所示。
▲ 图1 三级cache
许多软件优化技术通过重用cache中的数据来大幅度提高处理器性能,通过改善程序的时间局部性来提升访问效率。换言之,不要频繁替换cache中的数据。
处理数组时,如果能将数组元素按照访问顺序存放在存储器中,则能够获得性能上的好处。但是,假设同时处理多个数组,一些数组按行访问,一些数组按列访问。按行存储(称为行优先)或者按列存储(称为列优先)数组都不能解决问题,这是因为在程序的每个循环体中行访问和列访问同时会被使用到。因而,分块算法针对子矩阵(submatrice)或者数据块来进行操作,并不针对数组中完整的一行或一列进行操作。它的目标是,在替换之前对已在cache中的数据进行尽可能多的访问,这就是说,提高程序的时间局部性以减少cache失效。例如,在数值计算库Lapack的DGEMM中的内层循环中
for (int j = ; j < n; ++j) {
double cij = C[i+j*n]; /* cij = C[i][j] */
for( int k = ; k < n; k++ ) {
cij += A[i+k*n] * B[k+j*n]; /* cij += A[i][k]*B[k][j] */
C[i+j*n] = cij; /* C[i][j] = cij */
}
}
▲ 图3 DGEMM的cache分块版本。假设数组C初始化为0。函数doblock 以普通的DGEMM为基础,增加了新参数来描述BLOCKSIZE大小的子矩阵的起始位置。
图4给出使用分块思想对三个数组进行访问的示例。仅对于容量失效来说,需要访问的内存数据字总数为
。(相比未分块前)这个数据得到了改善,原因在于参数
。由此可见,分块思想挖掘出程序的时间局部性和空间局部性,比如数组A的访问得益于空间局部性,而数组B的访问得益于时间局部性。
▲ 图4 数组C、A和B的访问(BLOCKSIZE =3)。注意,与图2 相比,访问的元素数量变少
图5中给出了采用cache分块对未优化DGEMM性能的影响。矩阵规模最大时,未优化程序的性能折半。采用cache分块的版本,即使矩阵规模达到960x960=3232阵规模性能也仅仅降低了不到10%。
▲ 图5 未优化DGEMM与 cache 分块 DGEMM的性能比较,矩阵维度从32x32增加至960x960
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有