C++性能优化系列——矩阵转置(二)循环分块优化缓存访问

r囧r小猫 2023-03-03 11:22 6阅读 0赞

在上一篇博客 [C++性能优化系列——矩阵转置(一)访问内存顺序带来的性能差异][C] 中，分析了内存访问行列连续带来的性能差异。本篇以上一篇中写内存行连续的实现方案为Base版本，通过循环分块的优化技巧，进一步优化Base版本中的缓存访问问题。  
优化后执行情况如下：  
1024 \* 1024的二维矩阵，分块优化后耗时 0.605469 ms  
老规矩先上结论：  
通过循环分块方法，计算合理的分块尺寸，将循环逻辑实现为内层循环遍历访问块内数据，可以有效减少Cache Miss。本文中Base版本耗时是优化版本的2.56倍。

## 缓存结构 ##

测试机器CPU Cache结构如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70]

## 缓存访问模式分析 ##

分析一下pSource的L1 D Cache访问模式，由于二维矩阵尺寸为1024 \* 1024，元素大小一个字节，因此pSource是按照间隔为1K读取内存数据。  
最内层内循环执行1024次，L1 Cache一共加载CacheLine1024个，一共需要加载至缓存64 \* 1K = 64K，大于L1 D Cache 32K，因此当前访问模式L1 D Cache无法存下所有需要的内存，即每次内层循环执行pSource都会发生Cache Miss。  
因此，需要一个优化方式，使每次最内层访问都在L1 D Cache中。循环分块是处理这类问题的一种优化手段。本文尝试按照128 \* 128的块尺寸，将二维矩阵分块，内层循环pSource和pTarget都只访问块内数据。  
按照这种分块方式进行内存访问，pSource和pTarget每次加载到缓存的大小为2 \* 128 \* 128 = 32K，刚好可以放在L1缓存中。

## 代码实现 ##

代码中矩阵尺寸的相关定义，增加分块尺寸BLOCK

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

基于Base版本实现，内层循环只访问128 \* 128 的内存块，保证所有数据都在缓存中。  
代码实现

void BlockRowSeqTranspose(unsigned char* pSource, unsigned char* pTarget)
    	{ 
    		//Target 连续访问行
    		//BlockRowSeqTranspose Time (ms) 0.605469
    		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) * NCOL + icol] = pSource[(ibc*BLOCK+icol) * NROW + irow];
    						}
    					}
    				}
    			}
    			
    		}
    		clock_t end = clock();
    		std::cout << "BlockRowSeqTranspose 1024 Time " << (end - begin) << std::endl;
    		std::cout << "BlockRowSeqTranspose Time (ms) " << ((float)(end - begin)) / (float)REPEAT << std::endl;
    	}

执行时间

BlockRowSeqTranspose Time (ms) 0.605469

Base版本执行时间

TargetRowSeqTranspose Time (ms) 1.5498

和之前版本对比执行时间从1.5498加速到0.605469，速度提高2.56倍。可以看到针对L1缓存进行优化后的代码执行速度有明显提升。

## VTune数据分析 ##

将Base版本VTune抓取数据包和分析放在这里，方便对比。

### Base版本 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 1]  
可以看大Base版本内存瓶颈为核心的热点。  
![在这里插入图片描述][20200805143329579.png]  
代码整体CPI为1.164.大于1，通常CPI高于1需要进行优化。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 3]  
具体热点位置，L3 Cache Miss高。这里和之前分析的结果不太一样，之前分析的结果是L1会频繁发生Cache Miss。猜测原因可能是缓存一致性算法在替换L1 Cache时做的一些优化工作，将Miss转移到L3 Cache上了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 4]  
查看反汇编，访问内存的指令CPI都大于1。整体看下来，Base版本的执行情况符合之前分析的预期。

### 优化版本 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 5]

整体性能瓶颈集中在后端，内存瓶颈占比例比较小。  
![在这里插入图片描述][20200805141946528.png]  
优化版本CPI为0.438，小于1。指令执行平均耗时还不错。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 6]

热点代码位置，CPI也在0.4多一点。其中后端（即CPU的执行部分）问题突出。这里主要的问题是c++代码编译器无法做向量化。因为二维矩阵转置逻辑pSource访问内存不连续。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 7]

查看反汇编，汇编指令的CPI也都在0.4左右，没有慢的特别突出的存在。

对比两个版本的执行情况，做了分块优化后，代码在访问内存方面得到了不小的提升。

## 总结 ##

在实现 **按照一定间隔访问内存** 的功能时，要警惕内存的访问模式，尤其是性能敏感的功能。当访问内存间隔过大时，缓存无法将访问的内存全部装载进去。通过循环分块技术，将数据划分成缓存能够全部转载的尺寸，能够有效提高程序的速度。

[C]: https://blog.csdn.net/yan31415/article/details/107611634
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70]: /images/20230208/48351f53dbd2439d8e7feba3bea1cefa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 1]: /images/20230208/5a2004c9109349e894bdbed7ca3774c5.png
[20200805143329579.png]: /images/20230208/69e386c3c0594bada27b556b8783c431.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 2]: /images/20230208/1650823a174e49828fadc79a02263182.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 3]: /images/20230208/373dd9ef20444be5b87e55dd847a9535.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 4]: /images/20230208/9f49c086a0144d989ff04ce82bf30670.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 5]: /images/20230208/e8827b6b291545e78be43e851a4504ce.png
[20200805141946528.png]: /images/20230208/bb24971a1fac44a9ada44fed14c2ee06.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 6]: /images/20230208/8a3c6f6473614d14915fb49761a0b0ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbjMxNDE1_size_16_color_FFFFFF_t_70 7]: /images/20230208/f4328a4f851345c08cad313dd1918990.png