{ "cells": [ { "cell_type": "markdown", "id": "1969134f", "metadata": {}, "source": [ "# TP2 MPI \n", "## M1 informatique, Université d'Orléans 2024/2025" ] }, { "cell_type": "markdown", "id": "f573667b", "metadata": {}, "source": [ "L'objectif de ce TP est d'implémenter l'algorithme de Cannon pour la multiplication de matrices paralléle." ] }, { "cell_type": "markdown", "id": "70a66994", "metadata": {}, "source": [ "## 1. Description de l'algorithme de Cannon\n", "\n", "L'algorithme de Cannon réalise le produit de deux matrices $C=A\\times B$ en supposant qu'on travaille à partir d'une grille 2D régulière de processeurs $p\\times p$. Les deux matrices sont de taille $n\\times n$ et l'algorithme de Cannon est basé sur un découpage des matrices $A$ et $B$ en blocs $A_{ij}$ (respectivement $B_{ij}$) de taille $\\frac{n}{p}\\times\\frac{n}{p}$ (on supposera que $n$ est divisible par $p$).\n", "\n", "Les deux étapes de l'agorithme sont les suivantes\n", "\n", "### 1.1 Phase initiale\n", "\n", "Les matrices sont réparties sur les processeurs tel que le bloc\n", " $A_{ij}$ (respectivement $B_{ij}$) soit sur le processeur identifié\n", " par le couple $(i,j)$ sur la grille de processeurs. La première\n", " étape consiste à redistribuer la matrice de façon à effectuer un\n", " décalage circulaire des blocs $A_{ij}$ de $i$ positions à gauche et\n", " des blocs $B_{ij}$ de $j$ positions vers le haut.\n", "\n", " Par exemple on doit obtenir cette redistribution pour les matrices $A$ et $B$ découpées en $4\\times 4$ blocs : \n", "\n", "$$\\left(\n", "\\begin{array}{llll}\n", "A_{00} &A_{01} &A_{02} &A_{03}\\\\\n", "A_{10} &A_{11} &A_{12} &A_{13} \\\\\n", "A_{20} &A_{21} &A_{22} &A_{23}\\\\\n", "A_{30} &A_{31} &A_{32} &A_{33} \\\\\n", "\\end{array}\n", "\\right) \\longrightarrow\\left(\n", "\\begin{array}{llll}\n", "A_{00} &A_{01} &A_{02} &A_{03}\\\\\n", "A_{11} &A_{12} &A_{13} &A_{10} \\\\\n", "A_{22} &A_{23} &A_{20} &A_{21}\\\\\n", "A_{33} &A_{30} &A_{31} &A_{32} \\\\\n", "\\end{array}\n", "\\right) $$\n", "\n", "$$\\left(\n", "\\begin{array}{llll}\n", "B_{00} &B_{01} &B_{02} &B_{03}\\\\\n", "B_{10} &B_{11} &B_{12} &B_{13} \\\\\n", "B_{20} &B_{21} &B_{22} &B_{23}\\\\\n", "B_{30} &B_{31} &B_{32} &B_{33} \\\\\n", "\\end{array}\n", "\\right)\\longrightarrow\\left(\n", "\\begin{array}{llll}\n", "B_{00} &B_{11} &B_{22} &B_{33}\\\\\n", "B_{10} &B_{21} &B_{32} &B_{03} \\\\\n", "B_{20} &B_{31} &B_{02} &B_{13}\\\\\n", "B_{30} &B_{01} &B_{12} &B_{23} \\\\\n", "\\end{array}\n", "\\right)$$ \n", "\n", "A partir de cette répartition des blocs des deux matrices, chaque processeur crée un bloc $C_{ij}$ qui va permettre de calculer la matrice $C$ par la somme successive des produits des 2 blocs des matrices $A$ et $B$ stockées par chaque processeur.\n", "\n", "### 1.2 Itérations suivantes\n", "\n", " Chaque processeur identifié par le couple $(i,j)$ sur la grille 2D effectue le produit des deux blocs de $A$\n", " et $B$ qu'il a reçu et les transmet de la manière suivante\n", " \n", " - Les blocs de la matrice $A$ sont transmis selon un shift circulaire à gauche dans la grille de processeurs.\n", " - Les blocs de la matrice $B$ sont transmis selon un shift circulaire vers le haut dans la grille de processeurs.\n", " \n", " Au final chaque processeur $(i,j)$ contient le bloc $C_{ij}=\\sum_{l=0}^{p-1} A_{il}B_{lj}$." ] }, { "cell_type": "markdown", "id": "d53c635c-aae8-4fe8-b7d1-2517f404df2b", "metadata": {}, "source": [ "## 2. Réalisation\n", "### 2.1 Principe général\n", "On va supposer que $n$ est divisible par $p$ avec $p$ tel que le nombre de processus est égal à $ p\\times p$. Les étapes pour la mise en oeuvre sont les suivantes\n", "- Création d'une topologie 2D des processus (MPI\\_Dims\\_create et MPI\\_Cart\\_create) pour être capable d'identifier un processus de rang mpi\\_rank par un couple $(i,j)$ dans une grille 2D.\n", "\n", "- Initialisation sur chaque processus de deux matrices locales $A_{local}$ et $B_{local}$ de taille $\\frac{n}{p}\\times \\frac{n}{p}$ qui correspondent aux blocs $A_{ij}$ et $B_{ij}$ des matrices $A$ et $B$.\n", "- Redistribution des blocs selon l'étape 1 de l'algorithme. Vous pourrez utiliser MPI\\_Cart\\_shift pour déterminer le rang des processeurs source et destination d'un bloc.\n", "- Mise en place de la boucle à partir d'une fonction qui calcule $C_{local} = C_{local} + A_{local}\\times B_{local}$" ] }, { "cell_type": "markdown", "id": "f7184ca0-02d2-4d23-851f-8770192049bb", "metadata": {}, "source": [ "### 2.2 Trame initiale\n", "Vous disposez de la trame initiale ci-dessous. Cette version initiale considère des matrices d'entiers non signés. Vous disposez des fonctions\n", "- generation_mat pour construire une matrice de taille donnée en paramètre\n", "- multiplication_elementaire qui effectue une multiplication de matrices classique en séquentiel.\n", "\n", "Le programme principal est un squelette à compléter avec votre implémentation." ] }, { "cell_type": "code", "execution_count": null, "id": "2326dc64-29f0-4e9b-8c2e-02eb9c6bf65d", "metadata": {}, "outputs": [], "source": [ "int* generation_mat(int taille)\n", "{\n", " int* mat = new int[taille*taille];\n", " for (int i=0; i