这个问题是关于 C++ 优化技术的。我有一个大尺寸的矩阵 vector 乘法，想减少运行时间。我知道有专门的线性代数库，但我实际上想了解一下底层处理器的特性。到目前为止，我正在使用\O2 (Microsoft) 进行编译，并让编译器确认乘法的内部循环是矢量化的。

示例代码是:

#include <stdio.h>
#include <ctime>
#include <iostream>

#define VEC_LENGTH 64
#define ITERATIONS 4000000

void gen_vector_matrix_multiplication(double *vec_result, double *vec_a, double *matrix_B, unsigned int cols_B, unsigned int rows_B)
{
    // initialise result vector
    for (unsigned int i = 0; i < rows_B; i++)
    {
        vec_result[i] = 0;
    }
    // perform multiplication
    for (unsigned int j = 0; j < cols_B; j++)
    {
        const double entry = vec_a[j];
        const int col = j*rows_B;

        for (unsigned int i = 0; i < rows_B; i++)
        {
            vec_result[i] += entry * matrix_B[i + col];
        }
    }
}

int main()
{
    double *vec_a = new double[VEC_LENGTH];
    double *vec_result = new double[VEC_LENGTH];
    double *matrix_B = new double[VEC_LENGTH*VEC_LENGTH];

    // start clock
    clock_t begin = clock();

    // this outer loop is just for test purposes so that the timing becomes meaningful
    for (unsigned int i = 0; i < ITERATIONS; i++)
    {
        gen_vector_matrix_multiplication(vec_result, vec_a, matrix_B, VEC_LENGTH, VEC_LENGTH);
    }

    // stop clock
    double elapsed_time = static_cast<double>(clock() - begin) / CLOCKS_PER_SEC;
    std::cout << elapsed_time/(VEC_LENGTH*VEC_LENGTH) << std::endl;

    delete[] vec_a;
    delete[] vec_result;
    delete[] matrix_B;

    return 1;
}

多次进行乘法以获得可靠的运行时间估计。我测量了多个不同 vector 长度的运行时间(在这个例子中只有一个元素 N，它是 vector 的长度，同时定义了矩阵的大小NxN) 并将测量的运行时间归一化为元素的数量。

您可以看到，对于足够小的 N，每个操作的运行时间是恒定的。但是，在 N=512 之上，运行时会跳起来。蓝色和红色数据点之间的区别是处理器上的负载。如果示例程序几乎单独运行，则运行时间由蓝点表示，而当其他内核繁忙时，时间由红点表示。

我现在有几个与此相关的问题。

• 我假设 N=512 和 N=1024 之间的跳转与我处理器的 L3 缓存大小有关(Ivy Bridge i5 -3570) 哪个应该是 6MB？ 512*512*8byte 大约等于 2MB，1024*1024*8byte 大约等于 8MB。因此矩阵不再适合缓存，因此从 RAM 中获取数据是执行时间较长的原因？
• 运行时间稳定增长到超过此阈值的原因是什么？
• 对于繁忙和空闲处理器的曲线在阈值之上如此不同的原因有什么想法吗？
• 为使用 N>1024 操作优化此乘法例程的合乎逻辑的后续步骤是什么？

我很想听听您的想法。谢谢!

最佳答案

优化此类代码的一个重要方面是处理别名和矢量化，您的帖子表明您已经处理了后者。编译器经常需要一些帮助。在 GCC 5.3.0 上，使用下面的循环大大减少了运行时间。 __restrict__ 限定符告诉编译器不可能存在别名，#pragma GCC ivdep 告诉 GCC 编译器可以对代码进行矢量化。此外，编译器标志也非常重要。我使用 g++ -O3 -march=native -mtune=native matrix_example.cxx 编译了代码。

void gen_vector_matrix_multiplication(double* const __restrict__ vec_result,
                                      const double* const __restrict__ vec_a,
                                      const double* const __restrict__ matrix_B,
                                      const int cols_B,
                                      const int rows_B)
{
    // initialise result vector
#pragma GCC ivdep
    for (int i = 0; i < rows_B; i++)
        vec_result[i] = 0;

    // perform multiplication
    for (int j = 0; j < cols_B; j++)
    {
        const double entry = vec_a[j];
        const int col = j*rows_B;

#pragma GCC ivdep
        for (int i = 0; i < rows_B; i++)
        {
            vec_result[i] += entry * matrix_B[i + col];
        }
    }
}

关于c++ - 矩阵 vector 乘法优化 - 缓存大小，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36597104/