c - 实现 Cannon 的算法

Question

背景

我必须执行 Cannon's Algorithm这是一种并行算法，用于乘以维度为正方形的矩阵，维度可以被处理器数量的平方根整除。我写的这段代码运行得很好，但在生活中运行而不会崩溃只是故事的一半。它不会正确地将 A x B 乘以新矩阵 C。这是代码，请帮助我并引导我帮助我解决我做错的事情。很明显，这是家庭作业。

代码

void shift_left(datatype** mat, int s, int row, int n, int amount) {
    datatype* temp_buffer = malloc(sizeof(datatype) * n);
    for(int col = 0; col < n; col++) {
        datatype temp = mat[row][(col+amount)%s];
        temp_buffer[(col+amount)%s] = mat[row][col];
        temp_buffer[col] = temp;
    }
    memcpy(mat[row], temp_buffer, n);
    free(temp_buffer);
}

void shift_up(datatype** mat, int s, int col, int n, int amount) {
    datatype* temp_buffer = malloc(sizeof(datatype) * n);
    for(int row = 0; row < n; row++) {
        datatype temp = mat[(row+amount)%s][col];
        temp_buffer[(row+amount)%s] = mat[row][col];
        temp_buffer[row] = temp;
    }
    memcpy(&mat[0][col], temp_buffer, n);
    free(temp_buffer);
}

void cannon_mul(int p_sqrt,datatype** a, datatype** b, datatype** c, int n) {
    /* 2D matrices and n^2 sized only!*/
    int i = 0, j = 0, k = 0;
    int s = p_sqrt;
    for(i = 0; i < (s-1); i++) {
        shift_left(a, s, i, s-1, i); // Skew matrix a
    }
    for (i = 0; i < (s-1); i++) {
        shift_up(b, s, i, s-1, i); // Skew matrix b
    }
    for(k = 0; k < (s-1); k++) {
        for(i = 0; i < (s-1); i++) {
            for(j = 0; j < (s-1); j++) {
                c[i][j] += a[i][j]*b[i][j];
                shift_left(a, s, i, s-1, 1);
                shift_up(b, s, i, s-1, 1);  
            }                       
        }
    }  
}

我认为哪里出了问题？

我的预感是移位错误或者我遗漏了算法的重要部分。我原来的 shift 函数没有使用临时缓冲区，所以这次我想使用临时缓冲区，但这并没有什么区别。如果有帮助，我可以显示一些示例输出，但结果不甚至与期望的结果相差甚远。好消息它运行得很快:)

结果

1.48 0.14 9.47 8.99 8.06 0.06 6.68 1.04 4.44 7.50
7.26 8.87 2.21 6.27 2.12 7.91 0.65 5.24 0.45 4.94
0.47 4.13 1.87 2.25 6.83 1.52 6.41 9.14 9.22 8.91
7.34 2.70 6.78 2.78 3.51 4.95 5.27 0.85 9.51 6.82
0.28 6.73 0.70 8.88 7.14 9.09 2.36 5.38 6.43 9.00
7.13 6.71 6.92 9.81 5.13 9.35 7.50 5.16 4.68 3.62
1.30 6.26 4.55 4.27 0.51 2.23 3.19 8.75 6.57 9.07
7.49 6.41 1.04 7.78 7.16 2.78 2.25 6.23 9.42 0.32
3.21 3.60 2.04 2.93 4.29 3.88 2.78 8.01 4.57 6.47
7.52 3.77 0.63 5.97 7.32 4.90 9.63 4.90 8.46 1.90   

用我的代码将上面的矩阵与自身相乘产生:

2.20 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
50.81 0.00 0.00 0.00 0.00 87.51 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

顺序程序产生这个结果:

163.41 212.17 144.32 227.10 251.03 205.60 245.63 277.33 368.99 334.11
257.85 230.82 203.60 314.08 246.02 240.12 228.37 197.90 264.38 228.24
234.13 272.10 110.75 294.84 263.16 242.07 209.54 316.13 339.23 260.51
185.33 215.59 192.26 283.31 270.80 208.38 265.08 291.49 312.24 319.73
313.23 301.95 182.04 348.11 283.20 337.49 266.54 284.57 355.28 281.07
293.25 323.29 281.35 393.92 325.24 313.62 313.48 342.95 418.37 401.91
255.88 238.25 122.17 254.52 243.58 204.49 217.69 273.03 314.89 214.45
219.26 239.07 200.18 309.98 262.21 242.68 190.02 245.85 297.96 308.56
209.03 213.11 126.24 266.48 233.88 199.33 193.28 228.92 277.50 202.27
210.31 264.67 227.59 337.79 261.40 250.35 225.77 295.00 331.92 352.17

重要的是要注意我正在展示我的程序的相关部分，如果您觉得我需要展示更多请这样做，我将提供更多代码。最后，为什么作业标签不见了？

编辑

一个人指出缓冲区太小并且缺少 sizeof 是一个愚蠢的错误，现在已更正。我试过了，我得到了相同的结果，所以显然问题与此无关。希望在 2 天内我可以开赏金来吸引一些人至少给我一个问题所在的线索。这是一个我似乎无法调试的错误，我必须承认这个算法的理解是零到零。我依赖的网络资源对增加我的理解作用甚微。

编辑2

尝试使用 calloc 来零分配缓冲区，但它不会改变结果。很奇怪，但谢谢你的建议；我忘了内存没有分配归零。

编辑3

我试过这个:

void shift_left(datatype** mat, int s, int row, int n, int amount) {

    datatype* temp_buffer = calloc(n, sizeof(datatype) * n);
    for(int col = 0; col < n; col++) {
        /* temp_buffer[(col+amount)%s] = mat[row][col];
        temp_buffer[col] =  mat[row][(col+amount)%s]; */
        temp_buffer[(col+amount)%s] = 0;
        temp_buffer[col] =  0;
    }
    memcpy(mat[row], temp_buffer, sizeof(datatype) * n);
    //free(temp_buffer); 

}

void shift_up(datatype** mat, int s, int col, int n, int amount) {
    datatype* temp_buffer = calloc(n, sizeof(datatype) * n);
    for(int row = 0; row < n; row++) {
      /* temp_buffer[(row+amount)%s] = mat[row][col];
      temp_buffer[row] = mat[(row+amount)%s][col]; */
      temp_buffer[(row+amount)%s] = 0;
      temp_buffer[row] = 0;
    }
    memcpy(&mat[0][col], temp_buffer, sizeof(datatype) * n);
    free(temp_buffer); 
}

令人惊讶的是，结果是一样的。自从我注释了代码并将其替换为零后，它什么时候应该打印全零。我猜 memcpy 不工作。

编辑4

我已经确认 memcpy 是罪魁祸首。但是为什么我不知道我被难住了，如果它有助于 datatype is just an alias for double 教授出于某种奇怪的原因写道，因为它确实无助于使代码更具可读性。

但如果我确实自己解决了它，我会很乐意展示我的问题的解决方案。

Answer 1

副本太小。

// memcpy(mat[row], temp_buffer, n);
memcpy(mat[row], temp_buffer, n * sizeof(datatype) );

同样适用于 memcpy(&mat[0][col], temp_buffer, n);