Why does this code for chain matrix multiplication return a segmentation fault?

Question

I was writing a program to execute chain matrix multiplication for number of rows and columns being random numbers greater than 1000. The program performs chain matrix multiplication for 10 matrices all having dimensions greater than 1000. These dimensions are assigned dynamically using srand(). Using OpenMP, the program is running on 4 threads

However, whenever I run it its getting compiled but upon execution, it returns the error, 'Segmentation fault (core dumped)'

How do I fix this?

This is the code

#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. Out of bounds access to your array m where k == 9 as m is a nxn array with n = 10:

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

so maybe the loop should be for (int k = i; k < j - 1; k++)?

2. Signed integer overflow:

$ 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

where the line in question is:

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

Use smaller numbers or bigger type (for example long). If you change all your sizeof to use variables rather types then this is easier. For example:

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

3. With n = 10 you allocate 22 elements with the line above but later initialize 20 of them:

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

4. matrix_chain_multiple() doesn't make much sense to me. You pass in the input matrix p calculate m and s which you then free.