c - 矩阵乘法有2种不同的方式(比较时间)

Question

我有一个任务-以默认方式比较2个矩阵乘法，然后在转置第二个矩阵后进行乘法，我们应该指出哪种方法更快。我在下面写了这样的内容，但是time和time2几乎相等。在一种情况下，第一种方法更快，我用相同大小的矩阵运行乘法，在另一种情况下，第二种方法更快。做错了吗？我应该更改代码中的某些内容吗？

clock_t start = clock();

    int sum;
    for(int i=0; i<size; ++i) {
        for(int j=0; j<size; ++j) {
            sum = 0;
            for(int k=0; k<size; ++k) {
                sum = sum + (m1[i][k] * m2[k][j]);
            }
            score[i][j] = sum;
        }
    }

    clock_t end = clock();
    double time = (end-start)/(double)CLOCKS_PER_SEC;

    for(int i=0; i<size; ++i) {
        for(int j=0; j<size; ++j) {
            int temp = m2[i][j];
            m2[i][j] = m2[j][i];
            m2[j][i] = temp;
        }
    }

    clock_t start2 = clock();

    int sum2;
    for(int i=0; i<size; ++i) {
        for(int j=0; j<size; ++j) {
            sum2 = 0;
            for(int k=0; k<size; ++k) {
                sum2 = sum2 + (m1[k][i] * m2[k][j]);
            }
            score[i][j] = sum2;
        }
    }

    clock_t end2 = clock();
    double time2 = (end2-start2)/(double)CLOCKS_PER_SEC;

Answer 1

您的代码和/或理解存在多个严重问题。让我尝试解释一下。

矩阵乘法受到处理器加载值并将其存储到内存的速率的瓶颈。当前大多数体系结构都使用缓存来帮助实现这一点。数据以块的形式从内存移动到缓存，从缓存移动到内存。为了最大程度地利用缓存，您需要确保将使用该块中的所有数据。为此，请确保按顺序访问内存中的数据。

在C语言中，row-major order中指定了多维数组。这意味着最右边的索引在内存中是连续的；即a[i][k]和a[i][k+1]在内存中是连续的。

根据体系结构的不同，处理器等待（不执行任何操作）将数据从RAM移到高速缓存（反之亦然）所花费的时间可能会也可能不会包括在CPU时间中（例如，措施，尽管分辨率很差）。对于这种测量（“微基准”），最好测量并报告所用的CPU和实际（或挂钟）时间。尤其是如果微基准测试在不同的计算机上运行，​​则可以更好地了解更改的实际影响。

会有很多变化，因此通常，您要测量几百次重复（每个重复可能进行一次以上的操作；足够容易测量）所花费的时间，存储每次重复的持续时间，并报告其中位数。为什么选择中位数而不是最小值，最大值？因为总是会出现偶然的毛刺（由于外部事件或某些原因造成的不合理测量），通常会产生比正常情况高得多的值；这使最大值变得无趣，并且使平均值（均值）倾斜，除非将其删除。最小值通常是过度乐观的情况，在此情况下，一切恰好都进行得很顺利。在实践中很少发生，只是出于好奇，没有实际意义。另一方面，中值时间为您提供了一个实用的度量标准：您可以期望测试用例中所有运行的50％所花费的时间不会超过所测量的中值时间。

在POSIXy系统（Linux，Mac，BSD）上，应使用clock()来测量时间。 clock_gettime()格式具有纳秒级精度（1秒= 1,000,000,000纳秒），但是分辨率可能会更小（即时钟每变化1纳秒以上）。我个人使用

#define _POSIX_C_SOURCE 200809L
#include <time.h>

static struct timespec  cpu_start, wall_start;
double                  cpu_seconds, wall_seconds;

void timing_start(void)
{
    clock_gettime(CLOCK_REALTIME, &wall_start);
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &cpu_start);
}

void timing_stop(void)
{
    struct timespec  cpu_end, wall_end;
    clock_gettime(CLOCK_REALTIME, &wall_end);
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &cpu_end);

    wall_seconds = (double)(wall_end.tv_sec - wall_start.tv_sec)
                 + (double)(wall_end.tv_nsec - wall_start.tv_nsec) / 1000000000.0;
    cpu_seconds = (double)(cpu_end.tv_sec - cpu_start.tv_sec)
                + (double)(cpu_end.tv_nsec - cpu_start.tv_nsec) / 1000000000.0;
}

您在操作之前调用struct timespec，在操作之后调用timing_start()；然后，timing_stop()包含占用的CPU时间和cpu_seconds实际的挂钟时间（以秒为单位，请使用例如wall_seconds来打印所有有意义的小数）。

上面的方法在Windows上不起作用，因为Microsoft不希望您的C代码可移植到其他系统。它更喜欢制定自己的“标准”。 （与例如POSIX %.9f相比，或在Windows之外的所有系统上，宽字符支持的状态相比，那些C11“安全” _s() I / O功能变量都是愚蠢的伪装。）

矩阵乘法是

c[r][c] = a[r][0] * b[0][c]
        + a[r][1] * b[1][c]
        :         :
        + a[r][L] * b[L][c]

其中getline()具有a列，而L+1具有b行。

为了使求和循环使用连续的元素，我们需要转置L+1。如果b，则

c[r][c] = a[r][0] * B[c][0]
        + a[r][1] * B[c][1]
        :         :
        + a[r][L] * B[c][L]

注意，B[c][r] = b[r][c]和a在内存中是连续的，但彼此分开（可能彼此“相距很远”）就足够了，以便处理器在这种情况下有效地利用缓存。

OP使用类似于以下伪代码的简单循环来转置B：

For r in rows:
    For c in columns:
        temporary = b[r][c]
        b[r][c] = b[c][r]
        b[c][r] = temporary
    End For
End For

上面的问题是每个元素两次参与交换。例如，如果b有10行和列，则b交换r = 3, c = 5和b[3][5]，但是随后，b[5][3]再次交换r = 5, c = 3和b[5][3]！本质上，双循环最终将矩阵恢复为原始顺序；它不做转置。

请考虑以下条目和实际的转置：

b[0][0] b[0][1] b[0][2]      b[0][0] b[1][0] b[2][0]
b[1][0] b[1][1] b[1][2]  ⇔   b[0][1] b[1][1] b[2][1]
b[2][0] b[2][1] b[2][2]      b[0][2] b[1][2] b[2][2]

对角线条目不交换。您只需要在上三角部分（其中b[3][5]）或下三角部分（其中c > r）进行交换，以交换所有条目，因为每次交换都将一个条目从上三角替换为下三角，反之亦然。

因此，回顾一下：


  做错了吗？


是。您的移调不会执行任何操作。您还不了解为什么要转置第二个矩阵的原因。您的时间测量依赖于低精度的CPU时间，这可能无法反映在RAM和CPU缓存之间移动数据所花费的时间。在第二个测试用例中，使用r > c“转置”（除非不是，因为您交换了每个元素对两次，将它们返回到原来的状态），所以最里面的循环位于最左边的数组索引上，这意味着它计算出错误的结果。 （此外，由于最内层循环的连续迭代访问内存中彼此远离的项，因此它是反优化的：它使用的速度最差的模式。）

以上所有这些听起来可能很刺耳，但完全不是故意的。我不认识你，我也不想评估你。我只是指出此特定答案中的错误，以您目前的理解，仅是希望它可以帮助您以及在类似情况下遇到此问题的任何其他人学习。