c - 优化嵌套循环

Question

我们有一个任务，我们得到了一个效率非常低的程序，我们必须优化代码以使其运行得更快。我已经让他们中的大多数人运行得非常快，除了这两个，这让我非常烦恼，因为它们是非常简单的功能。一种基本上将二维数组中的所有值设置为相同的值，另一种基本上交换两个二维数组的值。这就是问题所在。它们占用的时间最多，但由于它们非常简单，我无法弄清楚如何在不破坏功能的情况下减少它们。而且我知道让他们跑得更快是可能的，因为类的其他学生已经获得了可笑的加速。有问题的两个是:

fSetArray(int rows, int cols, float val)
{
    int i, j;
    F2D *out;
    out = fMallocHandle(rows, cols);

    for(i=0; i<rows; i++)
    for(j=0; j<cols; j++)
        subsref(out,i,j) = val;

    return out;

}

唯一重要的部分是那里的两个循环。基本上，我们有一个具有一定宽度(行)和一定高度(列)的二维数组，我们将所有值设置为 val。但是我看不到消除其中一个循环的方法(这将是加速它的最佳方法)。除非我遗漏了一些明显的东西。如果 cols 和 rows 是相同的数字，这会容易得多。

另一个功能是:

fDeepCopy(F2D* in)
{
    int i, j;
    F2D* out;
    int rows, cols;

    rows = in->height;
    cols = in->width;

    out = fMallocHandle(rows, cols);

    for(i=0; i<rows; i++)
    for(j=0; j<cols; j++)
        subsref(out,i,j) = subsref(in,i,j);

    return out;
}

out 数组总是比 in 数组大，所以我们不必担心溢出等问题。这个函数基本上只是交换两个数组的值，但是再一次，因为它太简单了，我不能让它进一步减少。

在任何人说并行化之前，由于样本大小和服务器，创建线程所需的开销实际上会减慢程序的速度。我试过了。因为这两个函数太短了，所以不值得创建线程只在一个并行之后杀死它们。

但是作为引用，从技术上讲，这是一个 OpenMP 项目，我们应该使用并行化，但是对于这两个功能，这样做实际上会减慢整个程序的速度。我已经用一个并行的 for 循环来检查它。

编辑:感谢所有给我想法的人!我现在已经启动并运行并全速运行!

Answer 1

一种优化是循环展开。有时管道需要停止，因为围绕获取索引、更新索引以及将其存储回内存中存在大量事件。这可能是您的多线程实现做得不好的主要原因，所有线程可能都在争夺对索引的访问权。

如果您想重新尝试多线程实现，请让每个线程根据线程数知道它的“偏移量”，并让每个线程处理通过模除法发现的不同余数

thread 0 works on i*rows+j % (thread count) = 0
thread 1 works on i*rows+j % (thread count) = 1
(and so on)

如果您不想重新尝试多线程实现，仍然有一些技术可以提高性能。有时，即使是单个线程也会在索引变量上不必要地停顿(因为它会导致处理器管道的使用效率低下)。要尝试修复此类问题，请将索引增加一个特定数字并在循环内调用该方法的次数。

fDeepCopy(F2D* in)
{
    int i, j;
    F2D* out;
    int rows, cols;

    rows = in->height;
    cols = in->width;

    out = fMallocHandle(rows, cols);

    for(i=0; i<rows; i++) {
      // rewrite to ensure we don't walk off "4 long" pads
      int j = 0;
      int pads = (cols / 4)*4;
      for(; j < pads; j = j + 4) {
        subsref(out,i,j) = subsref(in,i,j);
        subsref(out,i,j+1) = subsref(in,i,j+1);
        subsref(out,i,j+2) = subsref(in,i,j+2);
        subsref(out,i,j+3) = subsref(in,i,j+3);
      }
      // process the remainders
      for(; j < pads; j++) {
        subsref(out,i,j) = subsref(in,i,j);
      }
    }
    return out;
}

现在CPU设计师越来越好了，所以是 关键 你实际分析你的运行以确定 CPU 是否已经为你做了这样的优化，或者这样的技术实际上可能会减慢你的代码。

最后，您还可以 leverage SSE extensions ，在正确的条件下，它可以对存储在 MMX 寄存器中的多个值执行相同的操作。例如，您可以使用汇编内联将两组四个 32 位单精度浮点数打包到 MMX 寄存器中，并一次执行四个浮点的批量加法。

所以，看起来像

vec_res.x = v1.x + v2.x;
vec_res.y = v1.y + v2.y;
vec_res.z = v1.z + v2.z;
vec_res.w = v1.w + v2.w;

这将需要 8 次内存查找、4 次加法和 4 次存储(16 次操作未优化)可能会替换为

movaps xmm0, [v1]          ;xmm0 = v1.w | v1.z | v1.y | v1.x 
addps xmm0, [v2]           ;xmm0 = v1.w+v2.w | v1.z+v2.z | v1.y+v2.y | v1.x+v2.x               
movaps [vec_res], xmm0

只需要三个操作，未优化。

再次，关键是分析，因此您可以检测瓶颈，然后调整您的代码以使它们处于可接受的最低性能范围内。