<jupyter_start><jupyter_text>Calcul réparti et programmation parallèle IntroductionLes entreprises et chercheurs peuvent avoir besoin dans certain cas d'effectuer des opérations complexes, nécessitant des millions ou milliards d'instructions.Quand on parle de gros traitements de données, on utilise souvent deux mesures:- Les MIPS, ou Millions d'Instructions Par Seconde- ou les FLOPS, Floating Point Operations Per Second, ou en français le nombre d'opération sur nombres à virgule par seconde. On parle aussi de MFLOPS (Mega FLOPS, $10^6$ FLOPS), GFLOPS (Giga FLOPS, $10^9$ FLOPS), ou TFLOPS (Terra FLOPS, $10^{12}$ FLOPS).Quelques exemples de traitement demandant beaucoup de puissance instantanée:* La 3D et les jeux, où la puissance de calcul va conditionner la résolution maximale, qualité de l'image, et nombre d'images par seconde:  * En 1998: La playstation 1 proposait 100 MFLOPS  ![La 3D sur playstation en 1998](resources/ff7.jpg)  * En 2018: La playstation 4 pro propose 4.20 TFLOPS (soit 42000 fois plus...)  ![La 3D sur playstation en 2018](resources/horizon-zero-dawn.jpg)* L'intelligence artificielle, nécessitant d'énormes capacité de calcul! Exemple: [YOLOv3](https://youtu.be/MPU2HistivI), nécessitant jusqu'à 150 TFLOPS pour traiter une vidéo 4K en temps réel, soit 37 Playstation 4...  * Analyse de traffic routier en temps réel:  ![YOLOv3](resources/yolov3.png)* De manière générale, toute application aillant pour entrée des données de taille gigantesque: demandez-vous combien quelle puissance il faut à Google pour analyser une seule requête et vous retourner les résultats adéquat. Puis réalisez que google à l'heure actuelle gère [40,000 recherches par seconde](http://www.internetlivestats.com/google-search-statistics/), 3.5 milliard par jour!Or la vitesse d'un processeur, aussi puissant soit-il, reste relativement basse: seulement quelques GFLOPS pour les plus puissants du marché actuel...  Comment fait-on pour aller plus vite?Prenons un exemple tout simple de fonction mathématique: la somme de carrés, définie par:$$\sum_{k=1}^n k^2 = 1^2 + 2^2 + 3^2 + \cdots + n^2$$Rien de bien compliqué pour $n < 10$, mais au delà? Pour $n = 10^9$?<jupyter_code>"""
RIEN A MODIFIER!
---
Tout d'abord, importons quelques libraries et fonctions utiles pour ce TP
N'OUBLIEZ PAS D'EXECUTER TOUTES LES SECTIONS DE CODE, Y COMPRIS CELLE-CI!
"""

# Librarie graphique
import matplotlib.pyplot as plt
%matplotlib inline

# Outils de chronométrage, visible dans tputils.py
from tputils import chronometre<jupyter_output><empty_output><jupyter_text>Implémentons une version naiveCommençons par écrire une fonction résolvant $\sum_{k=1}^n k^2$ de manière naive, en utilisant une boucle simple.Pour rappel, une boucle en python3 peut s'écrire de la manière suivante:```python3for i in range(10):     Itération sur tous les entiers de 0 à 9 (inférieurs à 10)    for i in range(4, 10):     Itération sur les entiers inférieurs à 10 à partir de 4, soit [4, 5, 6, 7, 8, 9]    for i in range(1, 10, 2):     Itération sur les entiers inférieurs à 10 à partir de 1, avec un interval de 2; soit [1, 3, 5, 7, 9]```<jupyter_code>"""
CODE A MODIFIER
Implementez la fonction ci-dessous
"""

def somme_carres(n):
    """
    Calcul de la somme des carrés entre 1 et n
    On veillera à ce que n soit un entier en forcant une conversion via la fonction int()
    """
    # VOTRE CODE ICI!<jupyter_output><empty_output><jupyter_text>Réussi? Bravo, mais nous allons quand même vérifier...La commande `assert` permet de vérifier si une égalité est vrai, et affiche une erreur autrement.```assert  [, ]```Pour chaque mini exercice, vous trouverez une série de tests à executer pour vérifier que votre travail retourne le bon résultat.Habituez-vous à tester **systématiquement** votre travail! Le test fait partie intégrante des bonnes pratiques de la programmation professionnelle, au même titre que la documentation.<jupyter_code>"""
RIEN A MODIFIER!
Executez ce bloc pour vérifier votre fonction
"""
assert somme_carres(1) == 1
assert somme_carres(2) == 5
assert somme_carres(3) == 14
# Les nombres à virgule doivent être converti en entiers
assert somme_carres(3.0) == 14
assert somme_carres(100) == 338350

print("Pas d'erreur? Parfait, votre fonction est probablement juste!")<jupyter_output><empty_output><jupyter_text>Testons maintenant combien de temps il faut pour effectuer $\sum_{k=1}^{10^7} k^2$ en utilisant la fonction `chronometre` importée en début de TP<jupyter_code>"""
RIEN A MODIFIER!
Executez ce bloc pour afficher le temps necessaire pour calculer somme_carres(1e7)
"""
t = chronometre(somme_carres, 1e7)
print("l'execution de somme_carres(1e7) a pris {:0.2f} secondes".format(t))<jupyter_output><empty_output><jupyter_text>Vous pouvez constater que cela prend un certain temps... Nous pourrions essayer de tracer la courbe de l'évolution du temps d'exécution en fonction de la valeur passée en parametre!Pour cela, nous utiliserons la librairie `matplotlib`, très utile en mathématiques.<jupyter_code>"""
CODE A MODIFIER
Tout d'abord, nous créons deux listes:
 - une pour les valeurs d'entrée (en absisse),
 - l'autre pour les temps dr'exécution
"""
N_simple = []
T_simple = []

for n in range(100_000, 1_000_000, 100_000):
    # Pour chaque valeur, ajoute chaque valeur de n dans N_simple
    N_simple.append(n)
    # Pour chaque valeur, chronometre et enregistre le resultat dans T_simple
    # VOTRE CODE ICI!
    T_simple.append(chronometre(somme_carres, n))

# Utilisons matplotlib pour afficher le résultat
plt.plot(N_simple, T_simple, 'rx')
plt.xlabel('Valeur de n')
plt.ylabel('Temps en secondes')
plt.title('Evolution du temps de calcul')
plt.show()<jupyter_output><empty_output><jupyter_text>**QUESTIONS** (éditez cette partie)1) Quelle forme a la courbe? VOTRE REPONSE ICI2) Quelle complexité pour le calcul de cet fonction (en fonction de n) ?VOTRE REPONSE ICI3) Notez le temps d'execution pour n = 500000VOTRE REPONSE ICI4) Quel serait le temps approximatif d'exécution pour $n = 10^7$?VOTRE REPONSE ICI  Partage de tâchesPython (et la plupart des languages de programmation) tourne par default en utilisant un seul processeur. Ce qui veut dire que votre programme ne peut executer qu'une seule tâche à la fois, aussi complexe soit-elle.Or les ordinateurs actuels on souvent plus d'un processeur, ou pour être plus précis, plusieurs coeurs à l'intérieur d'un ou plusieurs processeurs. Chaque coeur peut faire tourner un programme!- Les processeurs d'entrée de gamme ont souvent 2 à 4 coeurs (comme le Core i3 de Intel).- Les processeurs de milieu de gamme peuvent avoir entre 4 et 8 coeurs (Core i5 et i7)- Les processeurs haut de gamme ont souvent 16 coeurs et plus!il existe différent moyens d'executer du code sur plusieurs coeurs! La programmation par ThreadA COMPLETER!!! La programmation par ProcessA COMPLETER!!!  Découpage de notre fonction pour execution répartieDans cet exercice il est question de faire la somme d'un ensemble de valeurs (les carrés) qui peuvent être calculées de manière indépendante.On peut réécrire la formule comme suit:$$\sum_{k=1}^n k^2 = \sum_{k=1}^{\frac{n}2} k^2 + \sum_{k=\frac{n}2+1}^n k^2$$On peut donc calculer la moitié des valeurs et les additionner d'un coté, et faire le calcul de l'autre moitié des valeurs d'un autre coté. Aucun interet réel si on effectue ces opérations l'une après l'autre, mais intuitivement on peut directement imaginer le gain de performance si elles sont effectuées en même temps!Cette stratégie est souvent appelée [Diviser pour Régner](https://fr.wikipedia.org/wiki/Diviser_pour_r%C3%A9gner_%28informatique%29).![illustration](resources/somme_carres.png)<jupyter_code>"""
CODE A MODIFIER
Implémentez la function somme_partielle_carres(debut, fin) qui retourne la somme des carrés de debut à fin.
Veillez à utiliser une boucle comme précédemment
"""

def somme_partielle_carres(debut, fin):
    """
    Calcul de la somme des carrés entre debut et fin
    """
    # VOTRE CODE ICI
"""
RIEN A MODIFIER!
Executez ce bloc pour vérifier votre fonction
"""
assert somme_partielle_carres(1, 3) == 14
assert somme_partielle_carres(1, 100) == 338350
assert somme_partielle_carres(1, 50) + somme_partielle_carres(51, 100) == 338350
from multiprocessing.pool import Pool
pool = Pool()

def somme_rapide(n):
    """
    Calcul de la somme des carrés en utilisant 2 processes en parallèle
    """
    milieu = n // 2
    premier = pool.apply_async(somme_partielle_carres, (1, milieu))
    deuxieme = pool.apply_async(somme_partielle_carres, (milieu + 1, n))
    
    return premier.get() + deuxieme.get()
"""
RIEN A MODIFIER!
Executez ce bloc pour vérifier votre fonction
"""
assert somme_rapide(3) == 14
assert somme_rapide(100) == 338350
# Essayons différentes valeurs de n, et collectons le temps requis pour calculer somme_carres(n)

N_rapide = []
T_rapide = []

for n in range(100_000, 1_000_000, 100_000):
    # Pour chaque valeur, chronometre et enregistre le resultat dans T
    N_rapide.append(n)
    T_rapide.append(chronometre(somme_rapide, n))

# Utilisons matplotlib pour afficher le résultat
plt.plot(N_simple, T_simple, 'rx', label='simple')
plt.plot(N_rapide, T_rapide, 'bx', label='rapide')
plt.xlabel('nombre de valeurs n')
plt.ylabel('Temps en secondes')
plt.title('Evolution du temps de calcul')
plt.legend()
plt.show()<jupyter_output><empty_output><jupyter_text>**QUESTIONS** (A éditer en compléter)1) Que constatez-vous?VOTRE REPONSE ICI2) Pouvons-nous améliorer encore les performances, et comment?VOTRE REPONSE ICI3) Quelles sont les limites de cette technique?VOTRE REPONSE ICI  Un dernier conseil pour aller encore plus loinUne grande partie des problèmes calculatoires appliqués à l'informatique peuvent être résolu *plus vite* en utilisant cette stratégie de parallélisation.Mais il ne faut pas oublier une chose **importante**: souvent la meilleure des optimisations consiste à revoir les postulats de départ, et trouver de meilleures manières d'exprimer un problème!Si nous revenons à notre somme de carrés, il peut être prouvé que cette formule est équivalente:$$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}6$$<jupyter_code>"""
CODE A MODIFIER
Implémentez la formule de calcul de la somme des carrés optimisée
"""

def somme_efficace(n):
    """
    Calcul de la somme des carrés entre 1 et n
    """
    # VOTRE CODE ICI
"""
RIEN A MODIFIER!
Executez ce bloc pour vérifier votre fonction
"""
assert somme_efficace(1) == 1
assert somme_efficace(2) == 5
assert somme_efficace(100) == 338350
"""
RIEN A MODIFIER!
Executez ce bloc pour afficher le temps necessaire pour calculer somme_efficace(1e7)
"""
t = chronometre(somme_efficace, 1e7)
print("l'execution de somme_efficace(1e7) a pris {:0.2f} secondes".format(t))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08448740589274097, 'fraction_numerical': 0.027233014220652475, 'mean_word_length': 5.252178965717606, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 29, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '211219', 'license': 'MIT', 'n_tokens_mistral': 3923, 'n_tokens_neox': 3712, 'n_words': 1352, 'path': 'parallelisme/01-Calcul-Reparti.ipynb', 'repo_name': 'RouquinBlanc/tuto_python', 'size': '10759'}