Laderman的3x3矩阵乘法，只有23次乘法，值得吗？(Laderman's 3x3 m

取两个3×3的矩阵乘积A*B=C 。 天真，这需要使用27米乘标准算法 。 如果一个人是聪明的，你可以做到这一点只用23次乘法， 通过Laderman于1973年发现的结果 。 该技术涉及节能的中间步骤，并将它们以正确的方式合并。

现在，让我们解决语言和类型，说C ++与元素double 。 如果Laderman算法是硬编码与简约的双循环中，我们可以期待一个现代化的编译器的性能，以排挤的算法的区别是什么？

说明这个问题：这是一个编程网站，并提出问题，在时间紧迫的内循环的最佳实践的背景下; 过早的优化，这是不是。 在实现技巧有很大的欢迎，因为评论。

Answer 1:

关键是掌握你的平台上的指令集。 这取决于你的平台上。 有几种技术，当你往往需要最大可能的性能，你的编译器会与分析工具，其中一些优化提示的建成，对于最好的细粒度操作看汇编输出，看看是否有任何改善在该级别为好。

同时指令多数据指令并行地对若干操作数执行相同的操作。 所以，你可以采取

double a,b,c,d;
double w = d + a; 
double x = a + b;
double y = b + c;
double z = c + d;

而代之以

double256 dabc = pack256(d, a, b, c);
double256 abcd = pack256(a, b, c, d);
double256 wxyz = dabc + abcd;

所以，当值被装入寄存器，它们被装入一个256位宽的寄存器256位宽的寄存器一些虚构的平台。

浮点是一个重要的考虑因素，一些的DSP可以在整数显著更快的工作。 GPU的往往是浮点很大，但也有一些是在2倍单精度更快。 这个问题的3x3的情况下，可以放入一个CUDA线程，所以你可以同时串流这些计算的256。

选择你的平台，阅读文档，实施多种不同的方法和轮廓他们。

Answer 2:

时间测试：

我跑的时间测试自己，结果出乎我的意料（所以为什么我问的第一个地方的问题）。 这样做的缺点是，一个标准下编译laderman是〜225％的速度，但随着-03优化标志是慢50％！ 我不得不随机元素每次过程中添加到基质-O3标志或完全优化掉的简单乘法，编译器，取零的时间时钟精度内。 由于laderman算法是一个痛苦的检查/仔细检查我会后下面的完整代码后人。

规格：Ubuntu的12.04，戴尔T1600预知，GCC。 按照定时差异百分比：

• g++ [2.22, 2.23, 2.27]
• g++ -O3 [-0.48, -0.49, -0.48]
• g++ -funroll-loops -O3 [-0.48, -0.48, -0.47]

与Laderman实现沿基准测试代码：

#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstdlib>
using namespace std;

void simple_mul(const double a[3][3], 
        const double b[3][3],
        double c[3][3]) {
  int i,j,m,n;
  for(i=0;i<3;i++) {
    for(j=0;j<3;j++) {
      c[i][j] = 0;
      for(m=0;m<3;m++) 
    c[i][j] += a[i][m]*b[m][j];
    }
  }
}

void laderman_mul(const double a[3][3], 
           const double b[3][3],
           double c[3][3]) {

   double m[24]; // not off by one, just wanted to match the index from the paper

   m[1 ]= (a[0][0]+a[0][1]+a[0][2]-a[1][0]-a[1][1]-a[2][1]-a[2][2])*b[1][1];
   m[2 ]= (a[0][0]-a[1][0])*(-b[0][1]+b[1][1]);
   m[3 ]= a[1][1]*(-b[0][0]+b[0][1]+b[1][0]-b[1][1]-b[1][2]-b[2][0]+b[2][2]);
   m[4 ]= (-a[0][0]+a[1][0]+a[1][1])*(b[0][0]-b[0][1]+b[1][1]);
   m[5 ]= (a[1][0]+a[1][1])*(-b[0][0]+b[0][1]);
   m[6 ]= a[0][0]*b[0][0];
   m[7 ]= (-a[0][0]+a[2][0]+a[2][1])*(b[0][0]-b[0][2]+b[1][2]);
   m[8 ]= (-a[0][0]+a[2][0])*(b[0][2]-b[1][2]);
   m[9 ]= (a[2][0]+a[2][1])*(-b[0][0]+b[0][2]);
   m[10]= (a[0][0]+a[0][1]+a[0][2]-a[1][1]-a[1][2]-a[2][0]-a[2][1])*b[1][2];
   m[11]= a[2][1]*(-b[0][0]+b[0][2]+b[1][0]-b[1][1]-b[1][2]-b[2][0]+b[2][1]);
   m[12]= (-a[0][2]+a[2][1]+a[2][2])*(b[1][1]+b[2][0]-b[2][1]);
   m[13]= (a[0][2]-a[2][2])*(b[1][1]-b[2][1]);
   m[14]= a[0][2]*b[2][0];
   m[15]= (a[2][1]+a[2][2])*(-b[2][0]+b[2][1]);
   m[16]= (-a[0][2]+a[1][1]+a[1][2])*(b[1][2]+b[2][0]-b[2][2]);
   m[17]= (a[0][2]-a[1][2])*(b[1][2]-b[2][2]);
   m[18]= (a[1][1]+a[1][2])*(-b[2][0]+b[2][2]);
   m[19]= a[0][1]*b[1][0];
   m[20]= a[1][2]*b[2][1];
   m[21]= a[1][0]*b[0][2];
   m[22]= a[2][0]*b[0][1];
   m[23]= a[2][2]*b[2][2];

  c[0][0] = m[6]+m[14]+m[19];
  c[0][1] = m[1]+m[4]+m[5]+m[6]+m[12]+m[14]+m[15];
  c[0][2] = m[6]+m[7]+m[9]+m[10]+m[14]+m[16]+m[18];
  c[1][0] = m[2]+m[3]+m[4]+m[6]+m[14]+m[16]+m[17];
  c[1][1] = m[2]+m[4]+m[5]+m[6]+m[20];
  c[1][2] = m[14]+m[16]+m[17]+m[18]+m[21];
  c[2][0] = m[6]+m[7]+m[8]+m[11]+m[12]+m[13]+m[14];
  c[2][1] = m[12]+m[13]+m[14]+m[15]+m[22];
  c[2][2] = m[6]+m[7]+m[8]+m[9]+m[23];    
}

int main() {
  int N = 1000000000;
  double A[3][3], C[3][3];
  std::clock_t t0,t1;
  timespec tm0, tm1;

  A[0][0] = 3/5.; A[0][1] = 1/5.; A[0][2] = 2/5.;
  A[1][0] = 3/7.; A[1][1] = 1/7.; A[1][2] = 3/7.;
  A[2][0] = 1/3.; A[2][1] = 1/3.; A[2][2] = 1/3.;

  t0 = std::clock();
  for(int i=0;i<N;i++) {
    // A[0][0] = double(rand())/RAND_MAX; // Keep this in for -O3
    simple_mul(A,A,C);
  }
  t1 = std::clock();
  double tdiff_simple = (t1-t0)/1000.;

  cout << C[0][0] << ' ' << C[0][1] << ' ' << C[0][2] << endl;
  cout << C[1][0] << ' ' << C[1][1] << ' ' << C[1][2] << endl;
  cout << C[2][0] << ' ' << C[2][1] << ' ' << C[2][2] << endl;
  cout << tdiff_simple << endl;
  cout << endl;

  t0 = std::clock();
  for(int i=0;i<N;i++) {
    // A[0][0] = double(rand())/RAND_MAX; // Keep this in for -O3
    laderman_mul(A,A,C);
  }
  t1 = std::clock();
  double tdiff_laderman = (t1-t0)/1000.;

  cout << C[0][0] << ' ' << C[0][1] << ' ' << C[0][2] << endl;
  cout << C[1][0] << ' ' << C[1][1] << ' ' << C[1][2] << endl;
  cout << C[2][0] << ' ' << C[2][1] << ' ' << C[2][2] << endl;
  cout << tdiff_laderman << endl;
  cout << endl;

  double speedup = (tdiff_simple-tdiff_laderman)/tdiff_laderman;
  cout << "Approximate speedup: " << speedup << endl;

  return 0;
}

Answer 3:

我预计主要性能问题将内存延迟。 甲double[9]通常为72个字节。 这已经是一个平凡的金额，你用他们三个。

Answer 4:

虽然提到C ++的问题，我实现3×3矩阵乘法C =在C＃（.NET 4.5）A * B和进行了一些基本的定时测试在我的64位Windows 7机优化。 10,000,000乘法大约花了

1. 0.556秒有一个天真的实现和
2. 0.874秒从对方的回答中laderman代码。

有趣的是，laderman代码比用简单的方式慢。 我没有用探查调查，但我想额外的拨款比一些额外的乘法更加昂贵。

看来目前的编译器有足够的智慧做这些优化对我们来说，这是很好的。 下面是我用，您的关注天真的代码：

    public static Matrix3D operator *(Matrix3D a, Matrix3D b)
    {
        double c11 = a.M11 * b.M11 + a.M12 * b.M21 + a.M13 * b.M31;
        double c12 = a.M11 * b.M12 + a.M12 * b.M22 + a.M13 * b.M32;
        double c13 = a.M11 * b.M13 + a.M12 * b.M23 + a.M13 * b.M33;
        double c21 = a.M21 * b.M11 + a.M22 * b.M21 + a.M23 * b.M31;
        double c22 = a.M21 * b.M12 + a.M22 * b.M22 + a.M23 * b.M32;
        double c23 = a.M21 * b.M13 + a.M22 * b.M23 + a.M23 * b.M33;
        double c31 = a.M31 * b.M11 + a.M32 * b.M21 + a.M33 * b.M31;
        double c32 = a.M31 * b.M12 + a.M32 * b.M22 + a.M33 * b.M32;
        double c33 = a.M31 * b.M13 + a.M32 * b.M23 + a.M33 * b.M33;
        return new Matrix3D(
            c11, c12, c13,
            c21, c22, c23,
            c31, c32, c33);
    }

其中的Matrix3D是不可变的结构（只读双字段）。

最棘手的事情是要拿出一个有效的基准，在那里你衡量你的代码，而不是什么编译器做了与你的代码（调试器吨多余的东西，或者没有实际代码优化，因为从来没有使用的结果）。 我通常尝试“触摸”的结果，使得编译器不能除去被测代码（例如检查相等矩阵元素与89038.8989384并抛出，如果相等）。 然而，在最后，我甚至不知道，如果编译器黑客这种比较的方式进行:)

文章来源: Laderman's 3x3 matrix multiplication with only 23 multiplications, is it worth it?