Cache Blocking Techniques
文章来源：Cache Blocking Techniques (intel.cn)
文章作者：Amanda K Sharp
Overview
一类重要的算法更改涉及分块数据结构以适应缓存。通过组织数据内存访问，可以用一个大得多的数据集的一个小子集加载缓存。接下来的想法是在缓存中处理这个数据块。通过在缓存中使用/重用这些数据，我们减少了访问内存的需要(减少内存带宽压力)。
Topic
分块是一种著名的优化技术，可以帮助避免许多应用程序中的内存带宽瓶颈。分块背后的关键思想是利用应用程序中固有的数据重用，确保数据在多个用途之间保持在缓存中。分块可以在1-D、2-D或3-D空间数据结构上执行。一些迭代应用程序可以进一步受益于多次迭代的分块(通常称为时间分块)，以进一步缓解带宽瓶颈。就代码更改而言，分块通常涉及循环分割和交换的组合。在大多数应用程序代码中，通过对分块因子进行一些参数化，对源进行正确的更改，用户可以最好地执行分块。
Original Source
| for (body1 = 0; body1 < NBODIES; body1 ++) {
for (body2=0; body2 < NBODIES; body2++) {
OUT[body1] += compute(body1, body2);
}
}
|
在本例中，数据(body2)来自内存。假设NBODIES很大，我们将无法在缓存中重用。此应用程序受内存带宽限制。应用程序将以内存到CPU的速度运行，而不是最佳速度。
Modified Source (with 1-D blocking):
| for (body2 = 0; body2 < NBODIES; body2 += BLOCK) {
for (body1=0; body1 < NBODIES; body1 ++) {
for (body22=0; body22 < BLOCK; body22 ++) {
OUT[body1] += compute(body1, body2 + body22);
}
}
}
|
在修改后的代码中，数据(body22)在缓存中被保留和重用，从而获得更好的性能。
例如，上面的代码片段显示了一个分块NBody代码的示例。有两个循环(body1和body2)遍历所有主体。顶部的原始代码流经内部循环中的整个主体集，并且必须在每次迭代中从内存中加载body2值。底部的分块代码是通过将body2循环分解为一个迭代多个BLOCK中的body的外部循环和一个迭代BLOCK中的元素的内部body22循环，并交织body1和body2循环来获得的。这段代码在body1循环的多次迭代中重用了一组BLOCK body2值。如果BLOCK被选中，使得这组值适合缓存，内存流量就会降低一个BLOCK的因子。
以下是来自OpenMP*版本的NBody基准测试的相关代码片段(使用CHUNK_SIZE因子进行分块应用)。
在这种情况下，循环展开-阻塞转换被表示为一个pragma，并由编译器完成。在这种情况下，研究-opt-report的输出可以确认编译器确实为你的循环执行了展开阻塞优化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #define CHUNK_SIZE 8192
#pragma omp parallel private(body_start_index)
for(body_start_index = 0; body_start_index < global_number_of_bodies; body_start_index += CHUNK_SIZE) {
int i;
int body_end_index = body_start_index + CHUNK_SIZE;
#pragma omp for private(i) schedule(guided)
#pragma unroll_and_jam (4)
for(i=starting_index; i<ending_index; i++) {
int j;
TYPE acc_x_0 = 0, acc_y_0 = 0, acc_z_0 = 0;
for(j=body_start_index; j<body_end_index; j+=1) {
TYPE delta_x_0 = Input_Position_X[(j+0)] - Input_Position_X[i];
TYPE delta_y_0 = Input_Position_Y[(j+0)] - Input_Position_Y[i];
TYPE delta_z_0 = Input_Position_Z[(j+0)] - Input_Position_Z[i];
TYPE gamma_0 = delta_x_0*delta_x_0 + delta_y_0*delta_y_0 + delta_z_0*delta_z_0 + epsilon_sqr;
TYPE s_0 = Mass[j+0]/(gamma_0 * SQRT(gamma_0));
acc_x_0 += s_0*delta_x_0;
acc_y_0 += s_0*delta_y_0;
acc_z_0 += s_0*delta_z_0;
}
Output_Acceleration[3*(i+0)+0] += acc_x_0;
Output_Acceleration[3*(i+0)+1] += acc_y_0;
Output_Acceleration[3*(i+0)+2] += acc_z_0;
}
}
|
下面是Fortran中的一个矩阵乘法代码示例，其中用户执行高级块展开-分块转换(在修改版本中)，涉及本地复制数组以获得最佳性能。
Fortran Source Example:
| do j=1,N
do k = 1,N
do i = 1,N
c(i,j) = c(i,j) + a(i,k) * b(k,j)
end do
end do
end do
|
Modified Fortran Source:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| do JJ = 1, N, TJ
do KK = 1, N, TK
do jjj = 1,min(tj,N-jj+1)
do kkk = 1, min(tk,N-kk+1)
p(kkk,jjj-1+1) = B(kk+kkk-1, jj+jjj-1)
end do
end do
do II = 1, N, TI
do iii = 1,
min(ti,N-ii+1)
do kkk = 1, min(tk,N-kk+1)
Q(kkk,iii) = A(ii+iii-1, kk+kkk-1)
end do
end do
do J = 1, min(tj,N-jj+1), 4
do I = 1, min(ti,N-ii+1), 2
t1 = 0 ; t2 = 0 ; t5 = 0 ; t6 = 0 ; t9 = 0 ; t10 = 0 ; t13 =0 ; t14 = 0
do K = 1,min(TK,N-kk+1)
qi = Q(K,I) ; qi1 = Q(K,I+1)
t1 = t1+qi*P(K,J) ; t2 = t2+ qi1*P(K,J)
t5 = t5+ qi*P(K,J+1) ; t6 = t6+ qi1*P(K,J+1)
t9 = t9+ qi*P(K,J+2) ; t10 = t10+ qi1*P(K,J+2)
t13 = t13+ qi*P(K,J+3); t14 = t14+qi1*P(K,J+3)
end do
c(i+ii-1,j+jj-1) = c(i+ii-1,j+jj-1) +t1 ; c(i+1+ii-1,j+jj-1) = c(i+1+ii-1,j+jj-1) + t2
c(i+ii-1,j+1+jj-1) = c(i+ii-1,j+1+jj-1) + t5 ; c(i+1+ii-1,j+1+jj-1) = c(i+1+ii-1,j+1+jj-1) + t6
c(i+ii-1,j+2+jj-1) = c(i+ii-1,j+2+jj-1) + t9 ; c(i+1+ii-1,j+2+jj-1) = c(i+1+ii-1,j+2+jj-1) + t10
c(i+ii-1,j+3+jj-1) = c(i+ii-1,j+3+jj-1) + t13 ; c(i+1+ii-1,j+3+jj-1) = c(i+1+ii-1,j+3+jj-1) + t14
end do
end do
end do
end do
end do
|
Take Aways
缓存分块是一种重新安排数据访问的技术，将数据子集(块)拉入缓存，并对这个块进行操作，以避免不得不重复从主存中获取数据。正如上面的示例所示，可以以这种方式手动分块循环数据以重用缓存。
对于性能关键的循环，其中性能分析表明内存带宽限制，而-opt-report显示编译器没有以最佳方式分块循环，您可以考虑手动展开循环，以便更好地分块数据以实现缓存重用。
NEXT STEPS
您必须从头到尾阅读本指南，使用内置的超链接来指导您在Intel®Xeon处理器上成功地移植和调优应用程序。本指南中提供的路径反映了获得最佳应用程序性能所需的步骤。