2

Buenas, estoy probando el tiempo de ejecución para distintos algoritmos que solucionen el problema de multiplicación de matrices, pero cuando intento para matrices de orden 417 para arriba, el .exe deja de funcionar.

El programa compila sin problemas, pero quisiera saber por qué para valores altos de N ya no corre el programa dado que tambien probare con otros algoritmos que posiblemente me causen dicho problema.

Estoy utilizando C en codeblocks, dejo el código que use:

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

#define N 416

void llenarMat(long mat[][N]);
void multMat(long A[][N] , long B[][N] , long C[][N]);
void mostrarMat(long A[][N]);

int main()
{
    long A[N][N];
    long B[N][N];
    long C[N][N];

    clock_t start_t , end_t;
    double total_t;

    srand(time(NULL));

    llenarMat(A);
    llenarMat(B);

    start_t = clock();
    printf("El metodo empieza, start_t = %ld\n", start_t);
    multMat(A , B , C);
    end_t = clock();
    printf("El metodo termina, end_t = %ld\n", end_t);

    total_t = (double)(end_t - start_t) / CLOCKS_PER_SEC;
    printf("Tiempo total tomado por el CPU: %f\n", total_t);

    /*mostrarMat(A);
    mostrarMat(B);
    mostrarMat(C);*/

    return 0;
}

void llenarMat(long mat[][N])
{
    long i, j;

    for (i = 0 ; i < N ; i++)
    {
        for (j = 0 ; j < N ; j++)
            mat[i][j] = (rand() % 10 )+ 1;
    }
}

void multMat(long A[][N] , long B[][N] , long C[][N])
{
    long i , j , k;
    long sum;

    for(i = 0 ; i < N ; i++)
    {
        for (j = 0 ; j < N ; j++)
        {
            sum = 0;
            for(k = 0 ; k < N ; k++)
            {
                sum = sum + A[i][k] * B[k][j];
            }
            C[i][j] = sum;
        }
    }
}

void mostrarMat(long A[][N])
{
    long i, j;

    for (i = 0 ; i < N ; i++)
    {
        for (j = 0 ; j < N ; j++)
            printf(" %d", A[i][j]);
        printf("\n");
    }
    printf("\n");
}
2
  • Tal y como lo pones parece un problema de memoria, pero harían falta más detalles para confirmar: ¿Qué mensaje de error recibes?¿Si haces debug dónde falla en concreto? Tal y como está formulada ahora mismo la pregunta no se ajusta bien al formato del sitio según el centro de ayuda: "Preguntas en busca de asistencia con la depuración ("¿por qué no funciona este código?") deben incluir cual es el comportamiento deseado, un problema o error específico y el mínimo de código necesario para reproducirlo. Las preguntas sin una clara enunciación del problema no son útiles para otros usuarios."
    – Alvaro Montoro
    el 2 sep. 2016 a las 18:08
  • No tengo compilador de C, pero lo estuve probando en rextester con el compilador C (gcc) y funciona correctamente para N = 416, N = 417 y N = 1000: prueba.c el 2 sep. 2016 a las 19:43

2 respuestas 2

2

Cuando ejecutas un programa existen 3 áreas de memoria, la pila(stack) , datos(data) y monticulo(heap).

Tu problema es el desbordamiento de stack, producido por la declaración de la constante N, ya que estás reservando memoria de manera estática.

Generalmente, el stack tiene 8 MB y es utilizado para guardar el estado de las variables al momento de invocar una función, también almacena la dirección de retorno de la función para luego continuar su ejecución del programa.

Una posible solución, aunque no correcta, es modificar el tipo de la variable por un tipo que ocupe menos espacio en el stack, por ejemplo un entero.

introducir la descripción de la imagen aquí

Esto va a depender de la precisión que necesites para tus cálculos de matrices

La solución correcta a tu problema es utilizar memoria dinámica en lugar de estática haciendo uso de las funciones malloc y calloc.

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

#define N 1000



void llenarMat(long *a);
void multMat(long *a , long *b , long *c);
void mostrarMat(long *a);

int main()
{

    long *A;
    long *B;
    long *C;
    A = malloc (N*N*sizeof(long));
    B = malloc (N*N*sizeof(long));
    C = malloc (N*N*sizeof(long));

    clock_t start_t , end_t;
    double total_t;

    srand(time(NULL));

    llenarMat(A);
    llenarMat(B);
    llenarMat(C);


    start_t = clock();
    printf("El metodo empieza, start_t = %ld\n", start_t);
    multMat(A, B , C);
    end_t = clock();
    printf("El metodo termina, end_t = %ld\n", end_t);

    total_t = (double)(end_t - start_t) / CLOCKS_PER_SEC;
    printf("Tiempo total tomado por el CPU: %f\n", total_t);


    return 0;
}

void llenarMat(long *v)
{
    long i, j;

    for (i = 0 ; i < N ; i++)
    {
        for (j = 0 ; j < N ; j++)
            v[i* N+j] = (rand() % 10 )+ 1;
    }
}



void multMat(long *a, long *b , long *c)
{
    int i, j, k;

    for (i = 0; i < N; i++){
        for (j = 0; j < N; j++){
            for (k = 0; k < N; k++){
                c[i*N + j] += a[ i*N +k ] * b[k * N + j];
            }

        }

    }
}

void mostrarMat(long *v)
{
    int i, j;

    for (i = 0; i < N; i++){
        printf("\n");
        for (j = 0; j < N; j++){
            printf(" %d \t", (int) v[i * N + j]);
        }
    }
}

Salida con N = 1000

introducir la descripción de la imagen aquí

Salida con N = 1500

introducir la descripción de la imagen aquí

Saludos !

-1

El problema es el tamaño de pila disponible.

En mi máquina no falla con N=417 pero sí falla con N=1000, obtengo una violación de segmento.

Pero funciona bien si aumento el tamaño de la pila con el siguiente código (para un sistema Linux) :

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include <sys/resource.h>

#define N 1000

void llenarMat(long mat[][N]);
void multMat(long A[][N] , long B[][N] , long C[][N]);
void mostrarMat(long A[][N]);


// Devuelve 0 si tiene exito. 
// No hace nada si se pide un tamaño menor al actual
int aumentaTamPila(const rlim_t tamPilaBytes)
{
    struct rlimit rl;
    int result;

    result = getrlimit(RLIMIT_STACK, &rl);
    if (result == 0)
    {
        if (rl.rlim_cur < tamPilaBytes)
        {
            rl.rlim_cur = tamPilaBytes;
            return setrlimit(RLIMIT_STACK, &rl);
        }
    }

    return 0;
}

int testMatrices()
{
  // Poner aquí el código del main de la pregunta
}

int main()
{
  aumentaTamPila( 1024*1024*1024 ); // 1Gib de pila
  testMatrices();
}

// Poner el resto del código de la pregunta.

Nótese que he puesto el código original en la función testMatrices, no en el main. Es muy importante que las variables A, B y C no estén en el main porque C tiene que reservar espacio en la pila para A, B y C al empezar main, antes de que se ejecute el código de main, y entonces todavía no se ha ejecutado el aumento de tamaño de pila.

En otros sistemas, por ejemplo en MAC, es posible especificar el tamaño de pila al compilar. Imagino que en esos sistemas sí sería posible poner A, B y C en el main.

En linux se obtiene una violación de segmento porque la pila está separada del montón (heap) y nunca puede una operación sobre la pila sobrescribir en el montón; un intento de usar más memoria en la pila de la disponible provoca un cierre del programa de forma predecible. En otros sistemas, como en el desastroso ETCS de Toyota, pila y montón comparten el mismo espacio y la pila puede llegar a escribir en el montón provocando que el programa siga ejecutando de forma impredecible.

Cuestión aparte. Usa %ld para printf de long, no %d.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.