3

我正在做一个任务，我转置矩阵以减少矩阵乘法运算的缓存未命中。根据我从几个同学那里了解到的情况，我应该得到 8 倍的提升。但是，我只得到 2 倍……我可能做错了什么？

GitHub 上的完整源代码

void transpose(int size, matrix m) {
    int i, j;
    for (i = 0; i < size; i++) 
        for (j = 0; j < size; j++) 
            std::swap(m.element[i][j], m.element[j][i]);
}

void mm(matrix a, matrix b, matrix result) {
    int i, j, k;
    int size = a.size;
    long long before, after;

    before = wall_clock_time();
    // Do the multiplication
    transpose(size, b); // transpose the matrix to reduce cache miss
    for (i = 0; i < size; i++)
        for (j = 0; j < size; j++) {
            int tmp = 0; // save memory writes
            for(k = 0; k < size; k++)
                tmp += a.element[i][k] * b.element[j][k];
            result.element[i][j] = tmp;
        }
    after = wall_clock_time();
    fprintf(stderr, "Matrix multiplication took %1.2f seconds\n", ((float)(after - before))/1000000000);
}

到目前为止，我做的事情正确吗？

仅供参考：我需要做的下一个优化是使用 SIMD/Intel SSE3

4

2 回答 2

11

到目前为止，我做的事情正确吗？

不，你的转置有问题。在开始担心性能之前，您应该已经看到了这个问题。当您进行任何类型的优化以进行优化时，使用幼稚但次优的实现作为测试总是一个好主意。如果不能产生正确的答案，实现 100 倍加速的优化将毫无价值。

另一个有帮助的优化是通过引用传递。您正在传递副本。事实上，您matrix result可能永远不会出去，因为您正在传递副本。再一次，你应该已经测试过了。

另一个有助于加速的优化是缓存一些指针。这仍然很慢：

for(k = 0; k < size; k++)
    tmp += a.element[i][k] * b.element[j][k];
result.element[i][j] = tmp;

优化器可能会找到解决指针问题的方法，但可能不会。如果您不使用非标准__restrict__关键字告诉编译器您的矩阵不重叠，至少不会。缓存指针，因此您不必执行a.element[i]、b.element[j]和result.element[i]. 告诉编译器这些数组不与__restrict__关键字重叠仍然可能会有所帮助。

附录
查看代码后，需要帮助。先来个小评论。你不是在写 C++。您的代码是带有一点点 C++ 的 C 代码。您使用的是C 标头而不是 C++ 标头，而struct不是class，malloc而不是new，typedef struct而不仅仅是。struct

由于您的struct matrix. 说错了就更惨了！将隐式定义的复制构造函数与包含裸指针的类或结构一起使用是在玩火。m(a, a, a_squared)如果有人打电话求矩阵的平方，你会被烧得很厉害a。如果有人期望对2m(a, a, a)进行就地计算，你会被烧得更糟 。a

从数学上讲，您的代码仅涵盖了矩阵乘法问题的一小部分。如果有人想将 100x1000 矩阵乘以 1000x200 矩阵怎么办？这是完全有效的，但是您的代码无法处理它，因为您的代码仅适用于方阵。另一方面，您的代码将允许某人将 100x100 矩阵乘以 200x200 矩阵，这没有一点意义。

在结构上，您的代码几乎 100% 保证它会因为使用不规则数组而变慢。malloc可以在内存中喷射矩阵的行。如果矩阵在内部表示为连续数组，但访问时就像是 NxM 矩阵一样，您将获得更好的性能。C++ 提供了一些很好的机制来做到这一点。

于 2012-10-03T04:32:43.883 回答
3

如果你的任务意味着你必须转置，那么，当然，你应该更正你的转置过程。就目前而言，它进行了两次转置，根本没有转置。j=loop 不应读取

j=0; j<size; j++

但

j=0; j<i; j++

不需要转置以避免以“错误”顺序处理因子矩阵之一的元素。只需互换 j-loop 和 k-loop。暂且不说任何（其他）性能调整，基本的循环结构应该是：

  for (int i=0; i<size; i++)
  {
    for (int k=0; k<size; k++)
    {
      double tmp = a[i][k];
      for (int j=0; j<size; j++)
      {
        result[i][j] += tmp * b[k][j];
      }
    }
  }
于 2012-10-03T20:43:06.893 回答