4-collectives.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "52e67c2c-18b5-4096-aecf-2ec5eb2ac3d4",
   "metadata": {},
   "source": [
    "# Communications collectives\n",
    "\n",
    "Les communications collectives peuvent faire :\n",
    "\n",
    "* des **déplacements de données**\n",
    "    * `MPI_Bcast`\n",
    "    * `MPI_Scatter`\n",
    "    * `MPI_Gather`, `MPI_Allgather`\n",
    "    * `MPI_Alltoall`\n",
    "* des **calculs collectifs**\n",
    "    * `MPI_Reduce`, `MPI_Allreduce`\n",
    "\n",
    "Chaque appel à ces fonctions doit être fait par\n",
    "**tous les processus d'un même communicateur**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "62e40adf-b44b-4c75-9f30-9bc541575e9e",
   "metadata": {},
   "source": [
    "## Déplacements de données\n",
    "\n",
    "### Diffusion de données avec `MPI_Bcast`\n",
    "\n",
    "Pour envoyer les mêmes informations à tous les processus d'un même\n",
    "communicateur, on utilise une fonction effectuant une **diffusion** :\n",
    "\n",
    "![Figure MPI_Bcast](images/mpi_bcast.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adacc112-9ee2-475d-bc0a-21df41dfffa8",
   "metadata": {},
   "source": [
    "[En **C**](https://www.mpi-forum.org/docs/mpi-4.1/mpi41-report.pdf#section.6.4) :\n",
    "\n",
    "```C\n",
    "// int MPI_Bcast(void *tampon, int compte, MPI_Datatype type,\n",
    "//               int racine, MPI_Comm comm)\n",
    "\n",
    "ierr = MPI_Bcast(&a, 1, MPI_INT, 2, MPI_COMM_WORLD);\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5bb555af-74e9-46ef-b3b1-cbf7e15129f6",
   "metadata": {},
   "source": [
    "[En **Python**](https://mpi4py.readthedocs.io/en/latest/reference/mpi4py.MPI.Comm.html#mpi4py.MPI.Comm.bcast) :\n",
    "\n",
    "```Python\n",
    "# bcast(objet: Any, racine: int = 0) -> Any\n",
    "\n",
    "a = comm.bcast(a, 2)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6254fec-a166-4eed-a17a-18019f4d1bd8",
   "metadata": {},
   "source": [
    "### Distribution de données avec `MPI_Scatter`\n",
    "\n",
    "Pour envoyer une portion des données à chaque\n",
    "processus d'un même communicateur, on utilise\n",
    "une fonction effectuant une **distribution** :\n",
    "\n",
    "![Figure MPI_Scatter](images/mpi_scatter.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b58a4351-f5bf-40b1-929a-d56e9ee065c3",
   "metadata": {},
   "source": [
    "[En **C**](https://www.mpi-forum.org/docs/mpi-4.1/mpi41-report.pdf#section.6.6) :\n",
    "\n",
    "```C\n",
    "// int MPI_Scatter(\n",
    "//     void *envoi, int compte_envoi, MPI_Datatype type_envoi,\n",
    "//     void *recep, int compte_recep, MPI_Datatype type_recep,\n",
    "//     int racine, MPI_Comm comm)\n",
    "\n",
    "ierr = MPI_Scatter( a, 1, MPI_INT,\n",
    "                   &b, 1, MPI_INT, 2, MPI_COMM_WORLD);\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6fd74f45-f414-4651-9974-c8c74b470677",
   "metadata": {},
   "source": [
    "[En **Python**](https://mpi4py.readthedocs.io/en/latest/reference/mpi4py.MPI.Comm.html#mpi4py.MPI.Comm.scatter) :\n",
    "\n",
    "```Python\n",
    "# scatter(envoi: Sequence[Any] | None, racine: int = 0) -> Any\n",
    "\n",
    "b = comm.scatter(a, 2)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7242e737-c9d8-4210-ab19-ef894ed2414b",
   "metadata": {},
   "source": [
    "### Regroupement de données avec `MPI_Gather`\n",
    "\n",
    "Pour récupérer plusieurs portions de données\n",
    "dans un seul processus d'un communicateur, on\n",
    "utilise une fonction effectuant un **regroupement** :\n",
    "\n",
    "![Figure MPI_Gather](images/mpi_gather.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88e3f8b9-6001-4453-a866-59ef3fb7545f",
   "metadata": {},
   "source": [
    "[En **C**](https://www.mpi-forum.org/docs/mpi-4.1/mpi41-report.pdf#section.6.5) :\n",
    "\n",
    "```C\n",
    "// int MPI_Gather(\n",
    "//     void *envoi, int compte_envoi, MPI_Datatype type_envoi,\n",
    "//     void *recep, int compte_recep, MPI_Datatype type_recep,\n",
    "//     int racine, MPI_Comm comm)\n",
    "\n",
    "ierr = MPI_Gather(&a, 1, MPI_INT,\n",
    "                   b, 1, MPI_INT, 2, MPI_COMM_WORLD);\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7a6cd00-0ec9-4afa-9e6f-ed43ff50ef3b",
   "metadata": {},
   "source": [
    "[En **Python**](https://mpi4py.readthedocs.io/en/latest/reference/mpi4py.MPI.Comm.html#mpi4py.MPI.Comm.gather) :\n",
    "\n",
    "```Python\n",
    "# gather(envoi: Any, racine: int = 0) -> list[Any] | None\n",
    "\n",
    "b = comm.gather(a, 2)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "321dd480-724b-4261-9c87-efd2591f7439",
   "metadata": {},
   "source": [
    "### Regroupement à tous avec `MPI_Allgather`\n",
    "\n",
    "C'est l'équivalent de `MPI_Gather` + `MPI_Bcast`,\n",
    "mais en plus efficace :\n",
    "\n",
    "![Figure MPI_Allgather](images/mpi_allgather.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d50e117b-3d33-40e2-a1f8-ba8825471c05",
   "metadata": {},
   "source": [
    "[En **C**](https://www.mpi-forum.org/docs/mpi-4.1/mpi41-report.pdf#section.6.7) :\n",
    "\n",
    "```C\n",
    "// int MPI_Allgather(\n",
    "//     void *envoi, int compte_envoi, MPI_Datatype type_envoi,\n",
    "//     void *recep, int compte_recep, MPI_Datatype type_recep,\n",
    "//     MPI_Comm comm)\n",
    "\n",
    "ierr = MPI_Allgather(&a, 1, MPI_INT,\n",
    "                      b, 1, MPI_INT, MPI_COMM_WORLD);\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07b7b72a-17d2-413d-b8a1-fa5bee599e02",
   "metadata": {},
   "source": [
    "[En **Python**](https://mpi4py.readthedocs.io/en/latest/reference/mpi4py.MPI.Comm.html#mpi4py.MPI.Comm.allgather) :\n",
    "\n",
    "```Python\n",
    "# allgather(envoi: Any) -> list[Any]\n",
    "\n",
    "b = comm.allgather(a)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5724389a-680a-44ca-8776-a1b3b01ab7e2",
   "metadata": {},
   "source": [
    "### Transposition globale avec `MPI_Alltoall`\n",
    "\n",
    "C'est l'équivalent de `MPI_Scatter` * `MPI_Gather`,\n",
    "mais en plus efficace :\n",
    "\n",
    "![Figure MPI_Alltoall](images/mpi_alltoall.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2e6f727-8b46-4a04-92e5-738b609989a0",
   "metadata": {},
   "source": [
    "[En **C**](https://www.mpi-forum.org/docs/mpi-4.1/mpi41-report.pdf#section.6.8) :\n",
    "\n",
    "```C\n",
    "// int MPI_Alltoall(\n",
    "//     void *envoi, int compte_envoi, MPI_Datatype type_envoi,\n",
    "//     void *recep, int compte_recep, MPI_Datatype type_recep,\n",
    "//     MPI_Comm comm)\n",
    "\n",
    "ierr = MPI_Alltoall(a, 1, MPI_INT,\n",
    "                    b, 1, MPI_INT, MPI_COMM_WORLD);\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98bf10fa-85de-4aad-baa8-5034e55e87e4",
   "metadata": {},
   "source": [
    "[En **Python**](https://mpi4py.readthedocs.io/en/latest/reference/mpi4py.MPI.Comm.html#mpi4py.MPI.Comm.alltoall) :\n",
    "\n",
    "```Python\n",
    "# alltoall(envoi: Sequence[Any]) -> list[Any]\n",
    "\n",
    "b = comm.alltoall(a)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f692ce2-2b93-4d98-90d7-770c42194d32",
   "metadata": {},
   "source": [
    "## Calculs collectifs\n",
    "\n",
    "### Opérations de réduction\n",
    "\n",
    "C'est l'équivalent d'un `MPI_Gather` avec une boucle effectuant une\n",
    "opération de réduction. Voici quelques opérations de réduction :"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13b3c7bb-b360-484e-83c7-0a0fd976a34f",
   "metadata": {},
   "source": [
    "Opération             | Constante MPI | Op([3, 5])\n",
    "----------------------|---------------|-----------\n",
    "Maximum               | `MPI_MAX`     | 5\n",
    "Minimum               | `MPI_MIN`     | 3\n",
    "Somme                 | `MPI_SUM`     | 8\n",
    "Produit               | `MPI_PROD`    | 15\n",
    "_ET_ logique          | `MPI_LAND`    | Vrai\n",
    "_OU_ logique          | `MPI_LOR`     | Vrai\n",
    "_OU exclusif_ logique | `MPI_LXOR`    | Faux\n",
    "_ET_ binaire          | `MPI_BAND`    | 1 (001 = 011 & 101)\n",
    "_OU_ binaire          | `MPI_BOR`     | 7 (111 = 011 \\| 101)\n",
    "_OU exclusif_ binaire | `MPI_BXOR`    | 6 (110 = 011 ^ 101)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c69323a-8f71-4002-ab83-b84bb3b3cda4",
   "metadata": {},
   "source": [
    "### Réduction avec `MPI_Reduce`\n",
    "\n",
    "Voici un exemple de réduction effectuant une somme :\n",
    "\n",
    "![Figure MPI_Reduce](images/mpi_reduce.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d37767c-ae8c-4c48-8136-630b23a758d1",
   "metadata": {},
   "source": [
    "[En **C**](https://www.mpi-forum.org/docs/mpi-4.1/mpi41-report.pdf#subsection.6.9.1) :\n",
    "\n",
    "```C\n",
    "// int MPI_Reduce(\n",
    "//     void *envoi, void *recep, int compte, MPI_Datatype type,\n",
    "//     MPI_Op op, int racine, MPI_Comm comm)\n",
    "\n",
    "ierr = MPI_Reduce(&a, &b, 1, MPI_INT,\n",
    "                  MPI_SUM, 2, MPI_COMM_WORLD);\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f61ea7f9-bab2-41ad-bd86-935121248dbe",
   "metadata": {},
   "source": [
    "[En **Python**](https://mpi4py.readthedocs.io/en/latest/reference/mpi4py.MPI.Comm.html#mpi4py.MPI.Comm.reduce) :\n",
    "\n",
    "```Python\n",
    "# reduce(envoi: Any, op: Op=SUM, racine: int = 0) -> Any | None\n",
    "\n",
    "b = comm.reduce(a, MPI.SUM, 2)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af055858-a980-4077-81c5-11e2997ed3d4",
   "metadata": {},
   "source": [
    "### Réduction et diffusion avec `MPI_Allreduce`\n",
    "\n",
    "C'est l'équivalent de `MPI_Reduce` + `MPI_Bcast`,\n",
    "mais en plus efficace :\n",
    "\n",
    "![Figure MPI_Allreduce](images/mpi_allreduce.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ce781ab-c1a5-4a62-b9f8-cd5c039e0f0a",
   "metadata": {},
   "source": [
    "[En **C**](https://www.mpi-forum.org/docs/mpi-4.1/mpi41-report.pdf#subsection.6.9.6) :\n",
    "\n",
    "```C\n",
    "// int MPI_Allreduce(\n",
    "//     void *envoi, void *recep, int compte, MPI_Datatype type,\n",
    "//     MPI_Op op, MPI_Comm comm)\n",
    "\n",
    "ierr = MPI_Allreduce(&a, &b, 1, MPI_INT,\n",
    "                     MPI_SUM, MPI_COMM_WORLD);\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f23cf72c-4e33-458e-95b2-0e492a8b7dca",
   "metadata": {},
   "source": [
    "[En **Python**](https://mpi4py.readthedocs.io/en/latest/reference/mpi4py.MPI.Comm.html#mpi4py.MPI.Comm.allreduce) :\n",
    "\n",
    "```Python\n",
    "# allreduce(envoi: Any, op: Op=SUM) -> Any\n",
    "\n",
    "b = comm.allreduce(a, MPI.SUM)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d9ac9ed-8122-4304-aed5-348623078e2c",
   "metadata": {},
   "source": [
    "## Division de l'espace de travail\n",
    "\n",
    "* La stratégie la plus triviale consiste à diviser l'espace de\n",
    "  travail en portions plus ou moins égales selon une dimension.\n",
    "* Puisque la taille `N` d'une dimension n'est pas nécessairement\n",
    "  un multiple de `size`, on ne peut pas faire une division entière\n",
    "  de `N` par `size` pour définir une taille unique de portion.\n",
    "  On risquerait alors d'oublier des éléments à calculer.\n",
    "* Par contre, on peut intégrer `rank` et `rank + 1` dans le calcul\n",
    "  des bornes inférieure et supérieure d'une portion de calcul,\n",
    "  ce qui permet de gagner en résolution lors de la division entière\n",
    "  tout en assurant le calcul global de `0` à `N - 1`, inclusivement :"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfb2f7fd-6870-4c54-8228-689f636398b5",
   "metadata": {},
   "source": [
    "En **C** :\n",
    "\n",
    "```C\n",
    "int debut = rank * N / size;\n",
    "int fin = (rank + 1) * N / size\n",
    "```\n",
    "\n",
    "En **Python** :\n",
    "\n",
    "```Python\n",
    "debut = rank * N // size\n",
    "fin = (rank + 1) * N // size\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a862974-9e6f-49fb-9d06-d7ca073cc544",
   "metadata": {},
   "source": [
    "* Pour `rank == 0`, `debut` vaudra effectivement `0`\n",
    "* La `fin` de `rank` est le `debut` de `rank + 1`\n",
    "* Pour `rank == size - 1`, `fin` vaudra effectivement `N`\n",
    "* Les itérations se font dans l'intervalle : `debut` <= `k` < `fin`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ceb94aaa-b702-4490-a433-adeb4964d90c",
   "metadata": {},
   "source": [
    "### Exemple - Intégration par la méthode des rectangles\n",
    "Pour la fonction suivante :\n",
    "\n",
    "$$f(x) = \\sin^2(x) \\ \\mathrm{e}^{-x}$$\n",
    "\n",
    "On souhaite calculer en parallèle une approximation de l'intégrale\n",
    "$I$ de cette fonction dans l'intervalle allant de $0$ à $\\pi$ :\n",
    "\n",
    "$$I = \\int_{0}^{\\pi} \\sin^2(x) \\ \\mathrm{e}^{-x} \\mathrm{d}x\n",
    "    = 2(1 - \\mathrm{e}^{-\\pi}) / 5$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8743ecd-5427-46e9-b488-c3ea24f55ea8",
   "metadata": {},
   "source": [
    "Pour ce faire, on calcule et additionne l'aire de $N$\n",
    "rectangles de largeur $\\Delta{}x = \\pi / N$ et d'abscisse\n",
    "$x_k = k\\Delta{}x$, où $k$ varie de $0$ à $N - 1$ :\n",
    "\n",
    "$$I \\approx \\Sigma_{k=0}^{N-1} \\sin^2(x_k) \\ \\mathrm{e}^{-x_k} \\Delta{}x$$\n",
    "$$I \\approx \\Sigma_{k=0}^{N-1} \\sin^2(k\\Delta{}x) \\ \\mathrm{e}^{-k\\Delta{}x} \\Delta{}x$$\n",
    "\n",
    "![Intégration par la méthode des rectangles, avec N = 10 rectangles](images/integration-rectangles.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c30751dd-805d-499f-9e59-d999c594fe6b",
   "metadata": {},
   "source": [
    "Un **code séquentiel** en C aurait l'allure suivante :\n",
    "\n",
    "```C\n",
    "double integrale(int N)\n",
    "{\n",
    "    int k;\n",
    "    int debut = 0;\n",
    "    int fin = N;\n",
    "    double somme = 0.0;\n",
    "    const double dx = M_PI / N;\n",
    "\n",
    "    for (k = debut; k < fin; k++) {\n",
    "        double sinCarre = sin(k * dx) * sin(k * dx);\n",
    "        somme += sinCarre * exp(-k * dx) * dx;\n",
    "    }\n",
    "\n",
    "    return somme;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bee048b7-9873-4589-9b11-aa70bd5aba95",
   "metadata": {},
   "source": [
    "Le même **code en parallèle avec MPI** aurait l'allure suivante :\n",
    "\n",
    "```C\n",
    "double integrale(int N, int rank, int size)\n",
    "{\n",
    "    int k;\n",
    "    int debut = rank * N / size;\n",
    "    int fin = (rank + 1) * N / size;\n",
    "    double somme = 0.0, somme_locale = 0.0;\n",
    "    const double dx = M_PI / N;\n",
    "\n",
    "    for (k = debut; k < fin; k++) {\n",
    "        double sinCarre = sin(k * dx) * sin(k * dx);\n",
    "        somme_locale += sinCarre * exp(-k * dx) * dx;\n",
    "    }\n",
    "\n",
    "    MPI_Allreduce(&somme_locale, &somme, 1, MPI_DOUBLE,\n",
    "                  MPI_SUM, MPI_COMM_WORLD);\n",
    "\n",
    "    return somme;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f5724a2-026b-4978-92e8-ebff195fe989",
   "metadata": {},
   "source": [
    "### Exercice #4 - Approximation de pi\n",
    "\n",
    "Étant donné :\n",
    "\n",
    "$$\\pi = 4 \\times \\frac{\\pi}{4} = 4 \\times \\arctan(1)$$\n",
    "\n",
    "Et étant donné\n",
    "[l'expansion de Taylor](https://fr.wikipedia.org/wiki/S%C3%A9rie_de_Taylor) :\n",
    "\n",
    "$$\\arctan(1) = \\Sigma_{k=0}^{\\infty} \\frac{(-1)^k}{2k + 1}$$\n",
    "\n",
    "Il est donc possible d'approximer $\\pi$ au moyen de $n$ termes :\n",
    "\n",
    "$$\\pi \\approx 4 \\times \\Sigma_{k=0}^{n - 1} \\frac{(-1)^k}{2k + 1}$$\n",
    "\n",
    "Avec :\n",
    "\n",
    "$$4 \\times (-1)^k = 4 \\times (1 - 2 \\times (k \\bmod 2)) = 4 - 8 \\times (k \\bmod 2)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b540ab8-2a29-41d3-a529-3a741f42cd93",
   "metadata": {},
   "source": [
    "* Dans le dossier `exercices`, éditez le fichier\n",
    "  `pi_collect.c` (ou `pi_collect.py`)\n",
    "* Utilisez `MPI_Bcast` (ou `bcast`) pour\n",
    "  propager le nombre d’itérations\n",
    "* Utilisez `MPI_Reduce` (ou `reduce`)\n",
    "  pour calculer la somme finale\n",
    "* Exemple d’utilisation de l’exécutable `pi` ou du script Python :\n",
    "\n",
    "```Bash\n",
    "srun -n 4 ./pi < pi_collect.in\n",
    "# OU\n",
    "srun -n 4 python pi_collect.py < pi_collect.in\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7e579bc-a6ff-474e-9488-be69bce56147",
   "metadata": {},
   "source": [
    "### Exercice #5 - Mesurer le temps écoulé\n",
    "\n",
    "* Éditez `pi_collect.c` (ou `pi_collect.py`)\n",
    "  pour mesurer le temps du calcul parallèle\n",
    "    * Seul le processus 0 devra calculer le temps écoulé\n",
    "\n",
    "En **C** :\n",
    "\n",
    "```C\n",
    "double t1, t2;\n",
    "if (rank == 0) t1 = MPI_Wtime();\n",
    "\n",
    "// Calcul parallèle et communications\n",
    "\n",
    "if (rank == 0) {\n",
    "    t2 = MPI_Wtime();\n",
    "    printf(\"Temps = %.6f sec\\n\", t2 - t1);\n",
    "}\n",
    "```\n",
    "\n",
    "En **Python** :\n",
    "\n",
    "```Python\n",
    "if rank == 0:\n",
    "    t1 = MPI.Wtime()\n",
    "\n",
    "# Calcul parallèle et communications\n",
    "\n",
    "if rank == 0:\n",
    "    t2 = MPI.Wtime()\n",
    "    print(f'Time = {t2 - t1:.6f} sec')\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e0640c7-f122-481e-95e3-4c9e710aac81",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}