如何优化矩阵乘法(matmul)代码,以便在单个处理器内核上快速运行

我正在研究并行编程概念,并尝试在单核上优化矩阵乘法示例。 到目前为止我提出的最快的实现如下:

/* This routine performs a dgemm operation * C := C + A * B * where A, B, and C are lda-by-lda matrices stored in column-major format. * On exit, A and B maintain their input values. */ void square_dgemm (int n, double* A, double* B, double* C) { /* For each row i of A */ for (int i = 0; i < n; ++i) /* For each column j of B */ for (int j = 0; j < n; ++j) { /* Compute C(i,j) */ double cij = C[i+j*n]; for( int k = 0; k < n; k++ ) cij += A[i+k*n] * B[k+j*n]; C[i+j*n] = cij; } } 

结果如下。 如何减少循环并提高性能

 login4.stampede(72)$ tail -f job-naive.stdout Size: 480 Mflop/s: 1818.89 Percentage: 18.95 Size: 511 Mflop/s: 2291.73 Percentage: 23.87 Size: 512 Mflop/s: 937.061 Percentage: 9.76 Size: 639 Mflop/s: 293.434 Percentage: 3.06 Size: 640 Mflop/s: 270.238 Percentage: 2.81 Size: 767 Mflop/s: 240.209 Percentage: 2.50 Size: 768 Mflop/s: 242.118 Percentage: 2.52 Size: 769 Mflop/s: 240.173 Percentage: 2.50 Average percentage of Peak = 22.0802 Grade = 33.1204 

我的C很生锈,我不知道优化器已经在做什么,但是这里……

由于几乎所有的时间都花在做点产品上,所以让我优化一下; 你可以从那里建造。

 double* pa = &A[i]; double* pb = &B[j*n]; double* pc = &C[i+j*n]; for( int k = 0; k < n; k++ ) { *pc += *pa++ * *pb; pb += n; } 

您的代码可能花费更多时间在下标算术上。 我的代码使用+=8+=(n<<3) ,效率更高。 (注意:一个double需要8个字节。)

其他优化:

如果你知道n的值,你可以“展开”至少最里面的循环。 这消除了for的开销。

即使你只知道n是偶数,你也可以迭代n / 2次,在每次迭代中加倍代码。 这会将开销减少一半(约)。

我没有检查矩阵乘法是否可以在行主要与列主要顺序中更好地完成。 +=8+=(n<<3)快; 这将是外环的一个小改进。

另一种“展开”的方法是在同一个内循环中做两个点积。 (我想我变得太复杂甚至无法解释。)

如今,CPU是“超标量”。 这意味着他们可以在某种程度上同时做多件事。 但这并不意味着必须连续完成的事情可以通过这种方式进行优化。 在同一循环中执行两个独立的点产品可能会为超大规模提供更多机会。

有很多方法可以直接改进。 基本优化是里克詹姆斯写的。 此外,您可以按行重新排列第一个矩阵,按列重新排列第二个矩阵。 然后在你的for()循环中,你总是会做++并且永远不会做+ = n。 与++相比,跳过n的循环要慢得多。

但是大多数优化确实很有效,因为当你使用-O3或-O4标志时,一个好的编译器会为你做这些。 它将展开循环,重用寄存器,执行逻辑运算而不是乘法等。如果需要,它甚至会改变for ifor j循环的顺序。

您的代码的核心问题是,当您有NxN矩阵时,使用3个循环强制您执行O(N^3)运算。 这很慢。 我认为最先进的算法只做~ O(N^2.37)操作( 链接在这里 )。 对于大型矩阵(比如说N = 5000),这是一个强大的优化。 您可以轻松实现Strassen算法,这将为您提供~N ^ 2.87改进或与Karatsuba算法结合使用,即使对于常规标量优化,也可以加快速度。 不要自己实施任何东西。 下载一个opensource实现。 将矩阵乘以一个巨大的主题与大量研究和非常快速的算法。 使用3个循环不被认为是有效地完成此工作的有效方法。 祝好运