C代码优化，流畅的功能

Question

对于一项作业，我们被要求优化描述为“平滑”函数的代码:

平滑函数将源图像 src 作为输入，并在目标图像 dst 中返回平滑结果。这是实现的一部分:

void naive_smooth(int dim, pixel *src, pixel *dst) { 
  int i, j;
  for(i=0; i < dim; i++)
    for(j=0; j < dim; j++)
      dst[RIDX(i,j,dim)] = avg(dim, i, j, src); /* Smooth the (i,j)th pixel */
  return; }

struct pixel 存储红色、绿色和蓝色值(整数)。函数 avg 返回第 (i,j) 个像素周围所有像素的平均值。您的任务是优化平滑(和平均)以尽可能快地运行。 (注意:函数 avg 是一个局部函数，您可以完全摆脱它，以其他方式实现 smooth。)此代码(以及 avg 的实现)位于文件 kernels.c 中。

有人知道我可以如何优化它吗？

Answer 1

您可以通过将矩阵/图像分成正方形 block 并一次平滑一个 block 来执行循环的循环平铺/循环带挖掘。通过这种方式，您可以获得更好的缓存利用率。

考虑当前版本。它遍历图像，一次访问三行，写入中间一行。

a[i-1][0], a[i-1][1], ..., a[i-1][dim-1]
a[i  ][0], a[i  ][1], ..., a[i  ][dim-1]
a[i+1][0], a[i+1][1], ..., a[i+1][dim-1]

当它到达图像的最右侧时，第一列可能会从缓存中丢弃。但是当您移动到下一行时，很快就会需要它们，访问方式如下:

a[i  ][0], a[i  ][1], ..., a[i  ][dim-1]
a[i+1][0], a[i+1][1], ..., a[i+1][dim-1]
a[i+2][0], a[i+2][1], ..., a[i+2][dim-1]

相反，您可以分块处理图像，例如:

a[i  ][B], a[i  ][B+1], ..., a[i  ][B+B-1]
a[i+1][B], a[i+1][B+1], ..., a[i+1][B+B-1]
a[i+2][B], a[i+2][B+1], ..., a[i+2][B+B-1]

其中 B 是图 block 大小。

或者配一张图，更清楚:

000111222
000111222
000111222
333444555
333444555
333444555
666777888
666777888
666777888

这里我们有一张 9x9 的图像，分为 9 个图 block ，编号从 0 到 8，您的目标是以这样的方式编写循环:首先平滑图 block 0 中的所有像素，然后平滑图 block 1 中的所有像素，然后是图 block 2 中的所有像素，等等。顺序并不重要，您甚至可以并行运行每个图 block 。

当然，这对于大图像和相对较大的图 block 来说是有利的，您可以尝试图 block 大小，例如，从横跨一两个缓存行的图 block 行开始。

有关此方法的更多信息，请查看 Loop tiling

---

综上所述，值得注意的是您的编译器应该自行执行此操作。