Matrix Multiplication Algorithms

Usando o algoritmo com 3 for - algoritmo DOT

for(int i=0; i<N; i++)     // N
	for(int j=0; j<N; j++).  // N
		for(int k=0; k<N; k++) // N

			C[i][j] += A[i][k] * B[k][j]; // nota: assume matriz C inicializada com 0s

Este algoritmo tem tempo de execução $O(N^3)$

Nos tempos de hoje, os algoritmos modernos, focam se mais em como os dados são acedidos e movidos.

Se criarmos a matriz desta maneira os dados serão guardados na memória na zona de dados estáticos.

double c[N][N];
	int main() {}

Se criarmos a matriz desta maneira os dados serão guardados na memória na zona da stack.

int main () {
	double c[N][N];
}

Nestes dois casos, pode não ser possível alocar toda a memória e dará erro.

Melhor criar a matriz desta maneira dentro da main: c = malloc (N * N * sizeof(double))

Código dado na aula para multiplicar matrizes em C:

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

#ifndef size
#define size 512
#endif

double *A, *B, *C;

void alloc() {
    A = (double *) malloc(size*size*sizeof(double));
    B = (double *) malloc(size*size*sizeof(double));
    C = (double *) malloc(size*size*sizeof(double));
}

void init() {
    for(int i=0; i<size; i++) {
        for(int j=0; j<size; j++) {
            A[i*size+j] = rand();
            B[i*size+j] = rand();
        }
    }
}

void mmult() {
    for(int i=0; i<size; i++) {
        for(int j=0; j<size; j++) {
            C[i*size+j] = 0;
            for(int k=0; k<size; k++) {
                C[i*size+j] += A[i*size+k] * B[k*size+j];
            }
        }
    }
}

int main() {
    alloc();
    init();
    mmult();
    printf("%f\\n", C[size/2+5]);
}

A linha que faz o produto escalar é o hot spot.