C++性能优化系列——矩阵转置(三)内存填充避免缓存抖动

Love The Way You Lie 2023-03-06 05:18 6阅读 0赞

在上一篇博客 [C++性能优化系列——矩阵转置(二)循环分块优化缓存访问][C] 中通过循环分块方法，分析并优化了缓存的访问，使性能得到提升。同时通过VTune抓包分析了代码执行情况。看起来Cache命中情况很好。可实际缓存真的没有优化空间了吗？也不见得。  
本篇根据《深入理解计算机系统》中缓存篇介绍的映射规则，在缓存映射方面做进一步优化。以分块优化版本为Base，通过对pSource数据进行内存填充处理，使pSource的访问内存映射不集中在一个缓存组中，避免缓存抖动问题。  
优化后执行情况：  
1024 \* 1024 二维矩阵转置耗时 0.367188 ms

## 内存映射模式分析 ##

《深入理解计算机系统》这本书中已经对缓存的映射关系说的非常清楚了，有兴趣同学可以详细阅读书中具体章节。（这里感触比较深，书中几页纸就把问题说的非常清楚了，极其不建议把时间耗费在阅读网上各种几千几万阅读量的博客上，博客质量真是无力吐槽）。  
在此主要说明测试环境内存与L1 D-Cache的映射。  
L1 D-Cache参数：32k，8路组映射，缓存行（Cache Line）64Bytes。L1 D-Cache中一共存在（32k / (8 \* 64Byte）= 64 组。  
因此，当以一定间隔访问内存时，理论上间隔 为（64组 \* 64 Byte = 4k ）的内存跨度时，对应的内存会映射到同一个缓存组中。当访问内存时，超过8个分散的数据都映射到同一个组中，按照缓存的局部性原则，之前加载进缓存的数据会被新的数据替换。即缓存抖动问题。  
Base版本的实现是以 128 \* 128 分块，在内层访问块内数据。pSource的行维度为1024，因此即便是以128进行分块，内存访问的总跨度也达到了128K，按照之前分析的规则，在一个块内访问一列数据时，每4个元素会映射到同一个组中，即有32个元素的内存会映射到相同的缓存组，因此会发生缓存抖动。  
解决缓存抖动问题常用的方法是内存填充，即增加pSource行的维度，这样访问逻辑上同一列的元素时，实际内存位置不会映射在相同的缓存组。对于最优的内存填充方案，目前本人还没来得及查阅相关文献。代码中是通过取若干组数据实验出的最优填充值。

## 代码实现 ##

矩阵尺寸相关宏定义，其中增加了内存填充后的pSource的行的维度NREALCOL

#define NREALCOL 1152
    #define NROW 1024
    #define NCOL 1024
    #define NSLICE NROW*NCOL
    #define REPEAT 1024
    #define BLOCK 128

代码实现如下：

void PaddingTranspose(unsigned char* pSource, unsigned char* pTarget)
    	{ 
    		//Target 连续访问行
    		//PaddingTranspose Time (ms) 0.367188
    		clock_t begin = clock();
    		int nbC = NCOL / BLOCK, nbR = NROW / BLOCK;
    		for (int i = 0; i < REPEAT; ++i)
    		{ 
    			for (int ibr = 0; ibr < nbR; ++ibr)
    			{ 
    				for (int ibc = 0; ibc < nbC; ++ibc)
    				{ 
    					for (int irow = 0; irow < BLOCK; ++irow)
    					{ 
    						for (int icol = 0; icol < BLOCK; ++icol)
    						{ 
    							pTarget[(ibr * BLOCK + irow) * NROW + icol] = pSource[(ibc * BLOCK + icol) * NREALCOL + irow];
    						}
    					}
    				}
    			}
    
    		}
    		clock_t end = clock();
    		std::cout << "PaddingTranspose 1024 Time " << (end - begin) << std::endl;
    		std::cout << "PaddingTranspose Time (ms) " << ((float)(end - begin)) / (float)REPEAT << std::endl;
    	}

代码执行耗时：

PaddingTranspose Time (ms) 0.367188

与Base版本耗时 0.605469 对比，执行速度快了1.65倍。

## VTune分析 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70]  
可以看到整体执行情况非常不错，没显示明显的性能瓶颈  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 1]  
和Base版本相比较，原来L2 Cache Miss指标降下来了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 2]  
热点代码CPI达到了0.257，与理想值0.25已经非常接近了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 3]  
查看热点代码的反汇编，汇编指令的CPI也基本在0.25左右。可以看到通过内存填充，程序执行已经达到了一个比较理想的状态。

## 结论 ##

当以一定间隔访问内存时，一定要注意访问内存的间隔是否为2的整数幂，特定间隔访问内存往往会导致缓存抖动问题。通过理论分析与内存填充，可以有效的分析与解决缓存抖动问题，带来意想不到的性能提升。

[C]: https://blog.csdn.net/yan31415/article/details/107709063
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70]: /images/20230208/5273692539764ac6aa821c71060013bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 1]: /images/20230208/12489ed9250d4a01b91589e0561410ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 2]: /images/20230208/891b8d68d4fc4d5f8e7566ce45a5cc0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 3]: /images/20230208/3b984ec02bef47faad33563dc5b73a52.png