How to calculate a multiplication of matrices with several processes acting simultaneously?

Question

I want to divide the matrix so that each process calculates a slice of matrix multiplication simultaneously. At the moment my code does the multiplication, but the processes are not working at the same time.

int k;
int process[num_proc];

for(k=0; k < num_proc; k++){
        process[k] = fork(); 
    
        if(process[k] == 0)
            exit(0);
        multiplica_matriz(k); 
        wait(NULL); 
    }

Note that I pass an integer value to the multiplica_matrix(int) function that is used to calculate the start and end of the matrix slice in which the process will act.

void multiplica_matriz(int proc_id){
    int i, j, k;
    int inicio_da_leitura, final_da_leitura;

    //marcação do início e do fim de onde o processo vai na matriz
    float passo = ceil((float)tam/num_proc);
    inicio_da_leitura = proc_id * passo;
    final_da_leitura = (proc_id + 1)* passo - 1;
    if(final_da_leitura > tam){
        final_da_leitura = tam -1;
}

    // multiplicação
    //printf("Inicio %d => Final %d \n", inicio, final );
    for (i = inicio_da_leitura; i <= final_da_leitura; i++)
    {
        for (j = 0; j < tam; j++)
        {
            z[i][j] = 0;
            for ( k = 0; k < tam; k++){
                z[i][j] += x[i][k]*y[k][j];
            }
        }
    }
}

Multiplication is working perfectly, but as the number of processes increases, the running time should fall, but this is not happening because the processes are not running in parallel. What’s happening is that when one stops, the other continues.

How can I trigger the function multiplica_matrix(k) so that each process passes its position (process [num_proc]) to the function simultaneously, causing the processes to do their calculations in parallel in the matrix?

The complete code is below:

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

int **x, **y, **z;
int shm_id;

int tam, num_proc; // tamanho da matriz e quantidade de processos

int **criar_matriz(){
    int *valores, **temp;

    //colocar a matriz na memória compartilhada
    shm_id = shmget(IPC_PRIVATE, 5120, IPC_CREAT | 0660);
    if(shm_id < 0){
        printf("shmget error\n");
    }
    temp = (int*)shmat(shm_id,NULL,0);

    // alocando memória
    valores = (int *)malloc(tam * tam * sizeof(int));

    for (int i = 0; i < tam; i++){
        temp[i] = &(valores[i * tam]);
    }

    //preenche valores
    for(int i=0;i<tam;i++){
        for(int j=0;j<tam;j++){
            temp[i][j] = 2;
        }
    }

    return temp;
}


void imprime_matriz(int **mat){
    int i, j;

    // loop para imprimir
    for (i = 0; i < tam; i++) {
        printf("\n\t| ");
        for (j = 0; j < tam; j++){
            printf("%4d", mat[i][j]);
        }
        printf("    |");
    }
    printf("\n\n");
}

void multiplica_matriz(int proc_id){
    int i, j, k;
    int inicio_da_leitura, final_da_leitura;

    //marcação do início e do fim de onde o processo vai na matriz
    float passo = ceil((float)tam/num_proc);
    inicio_da_leitura = proc_id * passo;
    final_da_leitura = (proc_id + 1)* passo - 1;
    if(final_da_leitura > tam){
        final_da_leitura = tam -1;
}

    // multiplicação
    //printf("Inicio %d => Final %d \n", inicio, final );
    for (i = inicio_da_leitura; i <= final_da_leitura; i++)
    {
        for (j = 0; j < tam; j++)
        {
            z[i][j] = 0;
            for ( k = 0; k < tam; k++){
                z[i][j] += x[i][k]*y[k][j];
            }
        }
    }
}

int main(int argc, char* argv[]){
    int i,j;

    clock_t inicio;

    inicio = clock(); //inicia a marcação do tempo

    // definindo o tamanho da matriz
    tam = atoi(argv[1]);

    // definindo tamanho da matriz
    num_proc = atoi(argv[2]);

    // Tratamento para evitar que o número de threads
    // seja maior que o tam da matriz
    if(num_proc > tam){
        printf("O número de threads é maior que o tamanho da matriz. Por favor selecione um número menor de threads.\n");
        return 0;
    }

    // alocando matriz
    x = criar_matriz();
    y = criar_matriz();
    z = criar_matriz();

    int k;
    int process[num_proc];

    // Chamo o processo, ele faz o cálculo
    // e então mato para o próximo continuar
    for(k=0;k<num_proc;k++){
        process[k] = fork(); //cria todos os processos

        if(process[k] == 0)
            exit(0);
        multiplica_matriz(k); //todos os processos executam essa parte juntos
        wait(NULL); //bloqueia o processo pai até que os filhos tenham se encerrado
    }

    // imprime as matrizes
    //imprime_matriz(a);
    //imprime_matriz(b);

    clock_t total = clock() - inicio; //termina a marcação do tempo

    //imprime resultado
    //printf("O resultado da multiplicação é: \n");
    imprime_matriz(z);

    //printf("Tempo de execução: %f (s)\n", (double)total/CLOCKS_PER_SEC);

    printf("%f\n", (double)total/CLOCKS_PER_SEC);

    //apaga a memória
    if(shmdt(x) == -1){
        perror("shmdt");
        exit(1);
    }

    if(shmdt(y) == -1){
        perror("shmdt");
        exit(1);
    }

    if(shmdt(z) == -1){
        perror("shmdt");
        exit(1);
    }
    return 0;
}

To execute the code: gcc matrix-Forks. c -o matrix-Forks.exe -lm -w

Answer 1

The following code is an example translated from the book "C++ Concurrency in Action - Second Edition" by author Anthony Williams. Chapter 8 is almost entirely devoted to this problem you described in your question.

template<typename Iterador,typename Func>
void for_each_paralelo(Iterador primeiro, Iterador ultimo, Func f)
{
    unsigned long const tamanho = std::distance(primeiro, ultimo);
    if(!tamanho) return;

    unsigned long const minimo_por_thread=25;
    if(tamanho<(2*minimo_por_thread))
    {
        //Executa o algoritmo na thread atual
        std::for_each(primeiro, ultimo, f);
    }
    else
    {
        Iterador const pivo = primeiro+tamanho/2;
     
        //Processar metade dos dados em uma thread em paralelo recursivamente
        std::future<void> primeira_metade = 
            std::async(&for_each_paralelo<Iterador,Func>, primeiro, pivo, f);
        
        //Processar a outra metade dos dados na thread atual recursivamente
        for_each_paralelo(pivo, ultimo, f);
        
        //Esperar o fim da execução da primeira metade
        primeira_metade.get();
    }
}

This is one of the simplest examples and describes a recursive function that applies a generic function to all elements of a data structure. This example is in section 8.5.1, page 284.

Edit: For the people who are downvote. I know I didn’t answer using pure C and the library the user asked, when someone answers within these parameters my answer will serve as a complement. The person has been unanswered for over a day and tried to help with what I know by proposing algorithms and an alternative implementation. And vc? What are you doing to help?