为什么这个链式矩阵乘法代码会返回分段错误？

Question

我正在编写一个程序来执行链式矩阵乘法，行数和列数是大于 1000 的随机数。该程序对 10 个维度都大于 1000 的矩阵执行链式矩阵乘法。这些维度是使用 srand() 动态分配的。使用 OpenMP，程序在 4 个线程上运行

但是，每当我运行它时，它都会被编译但在执行时，它会返回错误“分段错误（核心已转储）”

我该如何解决这个问题？

这是代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#include <omp.h>

void matrix_chain_multiply(int *p, int n, int num_threads) {
    // Allocate memory for matrix chain and auxiliary arrays
    int **m = (int **)calloc(n, sizeof(int *));
    int **s = (int **)calloc(n, sizeof(int *));
    if (m == NULL || s == NULL) {
        printf("Error: memory allocation failed\n");
        exit(1);
    }
    for (int i = 0; i < n; i++) {
        m[i] = (int *)calloc(n, sizeof(int));
        s[i] = (int *)calloc(n, sizeof(int));
        if (m[i] == NULL || s[i] == NULL) {
            printf("Error: memory allocation failed\n");
            exit(1);
        }
    }

    // Set the number of threads
    omp_set_num_threads(num_threads);

    // Compute the matrix chain product using dynamic programming
    for (int l = 2; l <= n; l++) {
        #pragma omp parallel for schedule(dynamic)
        for (int i = 1; i <= n - l + 1; i++) {
            int j = i + l - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++) {
                int q = m[i][k] + m[k+1][j] + p[(i-1)*2] * p[k*2+1] * p[j*2+1];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }

    // Free memory
    for (int i = 0; i < n; i++) {
        free(m[i]);
        free(s[i]);
    }
    free(m);
    free(s);
}

int main() {
    int n = 10; // number of matrices
    int num_threads = 4; // number of threads to use
    int *p = (int *)malloc(sizeof(int) * (n+1) * 2);
    if (p == NULL) {
        printf("Error: memory allocation failed\n");
        exit(1);
    }
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        p[i*2] = rand() % 1001 + 1000; // rows
        p[i*2+1] = rand() % 1001 + 1000; // columns
    }

    double start_time = omp_get_wtime();
    matrix_chain_multiply(p, n, num_threads);
    double end_time = omp_get_wtime();
    double time = end_time - start_time;
    printf("Time: %f\n", time);

    // Free memory
    free(p);

    return 0;
}

Answer 1

1. 越界访问您的数组

   m

   其中

   k == 9

   因为

   m

   是一个

   9

   x

   9

   数组：

int q = m[i][k] + m[k+1][j] + p[(i-1)*2] * p[k*2+1] * p[j*2+1];

所以也许循环应该是

for (int k = i; k < j - 1; k++)

？

2. 有符号整数溢出：

$ gcc -g3 -fsanitize=undefined 1.c
$ ./a.out
1.c:34:57: runtime error: signed integer overflow: 3572439 * 1615 cannot be represented in type 'int'
Segmentation fault

有问题的行是：

int q = m[i][k] + m[k+1][j] + p[(i-1)*2] * p[k*2+1] * p[j*2+1];

使用较小的数字或较大的类型（例如 long）。如果您更改所有 sizeof 以使用变量而不是类型，那么这会更容易。例如：

    long *p = malloc((n+1) * 2 * sizeof *p);

3. 使用

   n = 10

   ，您使用上面的行分配了 22 个元素，但随后初始化了其中的 20 个：

    for (int i = 0; i < n; i++) {
        p[i*2] = rand() % 1001 + 1000; // rows
        p[i*2+1] = rand() % 1001 + 1000; // columns
    }