Tengo un código de multiplicación de matriz que se ve así:

for(i = 0; i < dimension; i++)
    for(j = 0; j < dimension; j++)
        for(k = 0; k < dimension; k++)
            C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j];

Aquí, el tamaño de la matriz está representado pordimension. Ahora, si el tamaño de las matrices es 2000, se tarda 147 segundos en ejecutar este código, mientras que si el tamaño de las matrices es 2048, se tarda 447 segundos. Entonces, mientras que la diferencia en el no. de multiplicaciones es (2048 * 2048 * 2048) / (2000 * 2000 * 2000) = 1.073, la diferencia en los tiempos es 447/147 = 3. ¿Alguien puede explicar por qué sucede esto? Esperaba que escalara linealmente, lo que no sucede. No estoy tratando de hacer el código de multiplicación matricial más rápido, simplemente estoy tratando de entender por qué sucede.

Especificaciones: nodo AMD Opteron de doble núcleo (2.2GHz), 2G RAM, gcc v 4.5.0

Program compilado comogcc -O3 simple.c

Yo también ejecuté esto en el compilador icc de Intel, y vi resultados similares.

EDITAR

omo se sugirió en los comentarios / respuestas, ejecuté el código con dimension = 2060 y toma 145 segundos.

Aquí está el programa completo:

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

/* change dimension size as needed */
const int dimension = 2048;
struct timeval tv; 

double timestamp()
{
        double t;
        gettimeofday(&tv, NULL);
        t = tv.tv_sec + (tv.tv_usec/1000000.0);
        return t;
}

int main(int argc, char *argv[])
{
        int i, j, k;
        double *A, *B, *C, start, end;

        A = (double*)malloc(dimension*dimension*sizeof(double));
        B = (double*)malloc(dimension*dimension*sizeof(double));
        C = (double*)malloc(dimension*dimension*sizeof(double));

        srand(292);

        for(i = 0; i < dimension; i++)
                for(j = 0; j < dimension; j++)
                {   
                        A[dimension*i+j] = (rand()/(RAND_MAX + 1.0));
                        B[dimension*i+j] = (rand()/(RAND_MAX + 1.0));
                        C[dimension*i+j] = 0.0;
                }   

        start = timestamp();
        for(i = 0; i < dimension; i++)
                for(j = 0; j < dimension; j++)
                        for(k = 0; k < dimension; k++)
                                C[dimension*i+j] += A[dimension*i+k] *
                                        B[dimension*k+j];

        end = timestamp();
        printf("\nsecs:%f\n", end-start);

        free(A);
        free(B);
        free(C);

        return 0;
}