TP-calcul-parallele/BE/04_n-corps/n-corps.md

# Exercice 4 : problème aux N-corps

Ce fichier fait partie du rendu évalué pour le BE de Calcul parallèle.

## Question 1

Déterminer quels calculs peuvent être parallélisés et quelles communications mettre en place dans le code séquentiel suivant. Proposer une réécriture parallèle avectransmission de messages de ce code.

```
variables : force[1,...,N], data[1,...,N]
for t in 1, nb_steps do
  for i in 1, N do
    force[i] = 0
    for j in 1, N do
      force[i] = force[i] + interaction(data[i], data[j])
    end for
  end for
  for i in 1, N do
    data[i] = update(data[i], force[i])
  end for
end for
```

### Réponse Q2

On suppose que l'on possède K processus, tels que N divise K.
Par exemple K = 2N.

```C
variables (globales) : K, N, ratio
variables (locales)  : ik, force[1,...,ratio]
variables            : data[1,...,N]

// data est à la fois globale et locale car on le communique entre les processus

ratio = K / N

// Chaque processus k va s'occuper de `ratio` corps
// par exemple si `ratio` = 2
// processus 0 -> corps 0 + corps 1
// processus 1 -> corps 2 + corps 3
// ...

// Chaque processus doit connaitre `data`
// (seul le process 0 connait `data` au début)
// -> Broadcast data from 0 to all

// cette boucle n'est pas parallélisable
// on a besoin de t-1 pour calculer t
for t in 1, nb_steps do 

  ik = 0

  // cette boucle est parralélisable
  // dans le code on va "split" `N` par paquets de `ratio`
  for i in 1, N do
    if je_mocuppe_de_ce_corps(i, N, K) // on peut split de cette manière
      
      // on reset les forces
      force[ik] = 0

      // on calcule la force totale des corps qu'on s'occupe
      for j in 1, N do
        force[ik] = force[ik] + interaction(data[i], data[j])
      end for
      
      // on update notre `data` local
      data[i] = update(data[i], force[ik])
      ik++

    end if
  end for

  // une fois chaque `data` updaté localement (dans chaque processus)
  // il faut rassembler toutes ces infos
  // -> All_Gather des data locaux
  // on obtient un `data` synchronisé entre tous les processus,
  // comme lors du premier broadcast

end for
```

## Question 2

Proposer une version parallèle du code suivant.

```
variables : force[1,...,N], data[1,...,N]
for t in 1, nb_steps do
  for i in 1, N do
    force[i] = 0
  end for
  for i in 1, N do
    for j in 1, i-1 do
      f = interaction(data[i],data[j])
      force[i] = force[i] + f
      force[j] = force[j] - f
    end for
  end for
  for i in 1, N do
    data[i] = update(data[i], force[i])
  end for
end for
```

### Réponse Q2


```C
variables (globales) : force[1,...,N], data[1,...,N]

// Chaque processus doit connaitre `data`
// (seul le process 0 connait `data` au début)
// -> Broadcast data from 0 to all

// cette boucle n'est pas parallélisable
// on a besoin de t-1 pour calculer t
for t in 1, nb_steps do

  // on calcul les forces (plus efficacement)
  // on effectue N(N-1)/2 appels à `interaction`
  for i in 1, N do
    if je_mocuppe_de_ce_corps(i, N, K) // je m'occupe de cette "colonne"

      // on reset les forces
      force[i] = 0

      // on calcule la force totale des corps qu'on s'occupe
      for j in 1, i-1 do
        f = interaction(data[i],data[j])
        force[i] = force[i] + f
        force[j] = force[j] - f
      end for

      // on reduce les forces que l'on a calculé pour chaque corps
      // -> All_reduce

      // on update notre `data` local
      data[i] = update(data[i], force[i])
    end if
  end for

  // une fois chaque `data` updaté localement (dans chaque processus)
  // il faut rassembler toutes ces infos
  // -> All_Gather des data locaux
  // on obtient un `data` synchronisé entre tous les processus,
  // comme lors du premier broadcast

end for
```

## Question 3

Quels sont les inconvénients de cette version ?
Proposer une solution pour les atténuer.

### Réponse Q3

L'inconvénient de cette version est que l'on doit désormais répartir des calculs "en triangle". En effet puisque l'on ne calcul aucune redondance de interaction, on effectue les calculs suivants:

|   | 0 | 1 | 2 | 3 |
|:-:|:-:|:-:|:-:|:-:|
| 0 |   | x | x | x |
| 1 |   |   | x | x |
| 2 |   |   |   | x |
| 3 |   |   |   |   |

On doit alors effectuer $\frac{N(N-1)}2$ calculs, ce qui est plus compliqué à répartir sur $K = \frac{N}{ratio}$ processus. La manière naïve que j'ai utilisé pour paralléliser le code Question 2 est sous optimal puisque la chaque de calcul entre chaque processus n'est pas égal.

Une manière plus efficace serait, un peu comme dans openMP, de créer des tasks pour chaque calcul de `interaction` et de répartir uniformément ces tasks entre chaque processus.