高性能计算-探究循环分块优化(2-1)

1. 目标：分析循环分块优化技术，并分析cache 命中情况

假设每个cacheline可以存储b个数据元素。

2. 源代码分析

for( int i=0;i<N;i++)
{
	for(int j=0;j<M;j++)
	{
		A[i] += B[j];
	}
}

cache miss分析：

对A总访问次数为 NM，每次访存加载一个cacheline 可以加载b个元素，并且连续访问，该cacheline所有元素在依次被访问前不会被替换掉，共需访存加载cacheline N/b次，每次加载都有一次miss，所以A共有N/b次miss；对B共访问 NM次，当M足够大时，cache无法装载整个数组B，内层一次循环需访存M/b次，N个循环共访存加载cacaheline NM/b次，每加载一次cacheline有一次miss，所以B在全部循环中 miss NM/b。总共 N/b + NM/b次 miss。

3. 循环分块优化

原理：源码中对B的访问miss过高，B cacheline被反复加载，考虑提高B cacheline 加载一次的利用效率，可考虑每加载一次，完成相应所有A元素的访问，假设L1 cache可以满足 A所有元素 cacheline 遍历和 若干组 B cacheline 的计算需求；加载 B cacheline 组的数量不应太大，假设里面包含了 T 个元素应有 T=nb , T,b << M,N。保证访问B[T-1]时，B[0]仍在 cache 中。

代码思路：对高miss 数据的访问索引分块，作为最外层循环控制变量，并在最内层循环控制块内循环。

for(int j=0;j<M;j+=T)
{
	for(int i=0;i<N;i++)
	{
		for(int t=0;t<T;t++)
			A[i] += B[i]; 
	}
}

cache miss分析：

A元素索引i的访问在内2层循环，每次循环共访问N次，每次访问一个cacheline有一个misss，所以每次循环有N/b个不命中，由于j是分块访问，共有 M/b个循环，所以A元素miss为 N/b *(M/T)；B元素的访问最内层循环每次循环有 T/b个miss，T的取值为b的倍数并且不能太大，当访问B[T-1]时B[0]仍在cache中，对于第二层i的遍历，此时B[j]元素都在cache中，不影响第三层B元素 miss 数量，共有 M/T 次循环，所有B元素miss为 T/b *(M/T) = M/b。总共 MN/bT + M/b 次 miss。

4. 对比总结

分块前后AB全部miss比为（N/b+MN/b）/ (MN/bT + M/b) ，当MN足够大时，计算极限得 T。

分块后 A的miss增加，B的miss减少，总misss数为原来的 1/T。