On considère une matrice carrée réelle A, de taille n × n. On souhaite calculer, en parallèle et en utilisant MPI, la trace de la matrice A, avec Trace(A) = aii . 𝑖=1 𝑛 ∑ Ecrire un programme MPI (en utilisant des communications collectives et de réductions) qui effectue les actions suivantes (2,5 points) : - La machine de rang 0 initialise la matrice A et la distribue sur p machines. On considère cette distribution par lignes et on suppose que n est divisible par p, - Chaque machine calcule la trace locale correspondant à sa portion de la matrice A, - La machine de rang 0 récupère toutes les traces locales pour calculer la trace globale de la matrice

Voici un exemple de programme MPI qui calcule la trace d'une matrice distribuée par lignes :

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

int main(int argc, char** argv) {
    int rank, size, n, p, i, j;
    double *A, *localA, localTrace, globalTrace;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    // Lecture de la taille de la matrice
    if (rank == 0) {
        printf("Entrez la taille de la matrice : ");
        scanf("%d", &n);
    }

    // Broadcast de la taille de la matrice
    MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

    // Calcul de la taille locale de la matrice
    p = n / size;
    localA = (double*) malloc(p * n * sizeof(double));

    // Initialisation de la matrice A sur la machine 0 et distribution par lignes
    if (rank == 0) {
        A = (double*) malloc(n * n * sizeof(double));
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                A[i*n+j] = rand() % 10;
            }
        }
        MPI_Scatter(A, p*n, MPI_DOUBLE, localA, p*n, MPI_DOUBLE, 0, MPI_COMM_WORLD);
        free(A);
    } else {
        MPI_Scatter(NULL, p*n, MPI_DOUBLE, localA, p*n, MPI_DOUBLE, 0, MPI_COMM_WORLD);
    }

    // Calcul de la trace locale
    localTrace = 0.0;
    for (i = 0; i < p; i++) {
        localTrace += localA[i*n+i];
    }

    // Réduction de la trace locale vers la machine 0
    MPI_Reduce(&localTrace, &globalTrace, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

    // Affichage de la trace globale sur la machine 0
    if (rank == 0) {
        printf("Trace globale = %f\n", globalTrace);
    }

    free(localA);
    MPI_Finalize();

    return 0;
}

Explications :

- La machine de rang 0 lit la taille de la matrice et la diffuse à toutes les machines avec la fonction MPI_Bcast.
- Chaque machine calcule sa portion de la matrice A avec la fonction MPI_Scatter. La portion de la matrice est stockée dans un tableau localA de taille p x n.
- Chaque machine calcule sa trace locale en parcourant la diagonale de sa portion de la matrice.
- La trace locale est réduite vers la machine de rang 0 avec la fonction MPI_Reduce et l'opération MPI_SUM qui calcule la somme des traces locales.
- La machine de rang 0 affiche la trace globale.

Notez que nous avons choisi ici de distribuer la matrice par lignes. Il est également possible de la distribuer par colonnes ou par blocs. Le choix de la méthode de distribution dépend de la structure de la matrice et de l'algorithme utilisé.