Algorithmes parallèles et leur complexité

6.1 Algorithmes parallèles.

Les algorithmes parallèles sont conçus pour être exécutés sur des systèmes multiprocesseurs ou multithreads afin d'accélérer les calculs. Ils divisent la tâche en sous-tâches indépendantes qui s'exécutent simultanément. L'analyse de la complexité des algorithmes parallèles nécessite la prise en compte de la complexité temporelle et spatiale, ainsi que des facteurs tels que l'accélération, l'efficacité et la scalabilité.

Concepts de base des algorithmes parallèles

• Parallélisme: Division de la tâche en plusieurs sous-tâches qui peuvent être exécutées simultanément.
• Accélération (Speedup): Rapport du temps d'exécution de l'algorithme séquentiel au temps d'exécution de l'algorithme parallèle.
• Efficacité (Efficiency): Rapport de l'accélération au nombre de processeurs.
• Scalabilité (Scalability): Capacité de l'algorithme parallèle à utiliser efficacement un nombre croissant de processeurs.

Avantages des algorithmes parallèles :

• Accélération de l'exécution: Accomplir les tâches plus rapidement grâce à la parallélisation du travail.
• Utilisation efficace des ressources: Optimisation de l'utilisation des processeurs et des cœurs.
• Résolution de grandes tâches: Capacité de traiter de grands volumes de données et des calculs complexes qui sont impossibles ou très lents sur un processeur unique.

Complexité temporelle des algorithmes parallèles

La complexité temporelle des algorithmes parallèles est mesurée en tenant compte du temps requis pour exécuter toutes les sous-tâches parallèles et la synchronisation entre elles. Elle inclut :

• Complexité temporelle théorique: Temps d'exécution idéal sur un nombre infini de processeurs.
• Complexité temporelle réelle: Temps d'exécution tenant compte des limitations du nombre de processeurs et des coûts de synchronisation.

Complexité spatiale des algorithmes parallèles

La complexité spatiale des algorithmes parallèles considère la quantité de mémoire nécessaire pour stocker les données et le contexte de chaque processus parallèle. Il est également important de prendre en compte les surcoûts de communication entre les processeurs.

6.2 Exemple d'un algorithme parallèle

Tri fusion parallèle (Parallel Merge Sort) :

Divise le tableau en sous-tableaux, les trie en parallèle puis les fusionne.

Complexité temporelle : O(n*log(n)/p), où n est la taille du tableau, p est le nombre de processeurs.

from multiprocessing import Pool

def merge_sort_parallel(arr, num_processes=None):
    if len(arr) <= 1:
        return arr
    if num_processes is None:
        num_processes = Pool()._processes
    with Pool(processes=num_processes) as pool:
        size = len(arr) // 2
        left, right = arr[:size], arr[size:]
        left, right = pool.map(merge_sort_parallel, [left, right])
        return merge(left, right)
            
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
            
# Exemple d'utilisation
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort_parallel(arr)
print(sorted_arr)
            

Mais ce qui nous intéressera, ce n'est pas l'algorithme lui-même, mais l'analyse de son « efficacité ».

6.3 Analyse des algorithmes parallèles

Concepts de base :

1. Analyse de l'accélération (Speedup) :
   • Rapport du temps d'exécution de l'algorithme séquentiel au temps d'exécution de l'algorithme parallèle.
   • Speedup = T_seq / T_par, où T_seq est le temps d'exécution de l'algorithme séquentiel, T_par est le temps d'exécution de l'algorithme parallèle.
2. Efficacité (Efficiency) :
   • Évaluation de l'efficacité de l'utilisation des processeurs.
   • Efficiency = Speedup / P, où P est le nombre de processeurs.
3. Loi d'Amdahl (Amdahl's Law) :
   • Détermine l'accélération maximale que l'on peut atteindre lors de la parallélisation d'une tâche.
   • Speedup_max = 1 / (S + (1 - S) / P), où S est la part séquentielle de la tâche, P est le nombre de processeurs.
4. Loi de Gustafson (Gustafson's Law) :
   • Détermine l'accélération en tenant compte du changement de taille de la tâche lors de l'augmentation du nombre de processeurs.
   • Speedup = P - α * (P - 1), où P est le nombre de processeurs, α est la part séquentielle de la tâche.

6.4 Exemples d'algorithmes parallèles et leur complexité

Exemple 1 : Tri fusion parallèle (Parallel Merge Sort)

Description : Le tri fusion parallèle divise le tableau en sous-tableaux, trie chaque sous-tableau en parallèle, puis fusionne les sous-tableaux triés.

Analyse de complexité :

• Complexité temporelle : O((n log n) / P), où P est le nombre de processeurs.
• Complexité spatiale : O(n) pour le stockage des données intermédiaires.

Exemple 2 : Recherche parallèle dans un tableau (Parallel Search)

Description : La tâche de recherche d'un élément dans un tableau est divisée en plusieurs sous-tâches, chacune exécutée en parallèle sur un processeur distinct.

Analyse de complexité :

• Complexité temporelle : O(n / P), où P est le nombre de processeurs.
• Complexité spatiale : O(1), si le même tableau est utilisé.

Exemple 3 : Multiplication de matrices parallèle (Parallel Matrix Multiplication)

Description : Les matrices sont divisées en blocs, et chaque paire de blocs est multipliée en parallèle sur différents processeurs.

Analyse de complexité :

• Complexité temporelle : O(n^3 / P), où P est le nombre de processeurs.
• Complexité spatiale : O(n^2) pour le stockage des résultats intermédiaires.

6.5 Implémentation des algorithmes parallèles

Outils et bibliothèques :

1. OpenMP :
   • Bibliothèque pour C, C++ et Fortran, offrant des outils pour développer des applications multithreadées.
2. MPI (Message Passing Interface) :
   • Standard pour la programmation parallèle sur des systèmes distribués, supportant l'échange de messages entre processus.
3. CUDA :
   • Plateforme et API de NVIDIA pour développer des programmes parallèles utilisant les processeurs graphiques (GPU).
4. Threading et multiprocessing en Python :
   • Modules pour créer des programmes multithreadés et multiprocesseurs en Python.

Les algorithmes parallèles permettent d'accélérer considérablement les calculs en répartissant les tâches sur plusieurs processeurs ou cœurs. L'analyse de la complexité des algorithmes parallèles inclut l'évaluation de l'accélération, de l'efficacité et l'utilisation des lois d'Amdahl et de Gustafson pour comprendre l'accélération maximale atteignable lors de la parallélisation.

Les algorithmes parallèles trouvent leur application dans divers domaines, de la tri et la recherche à des calculs mathématiques complexes, et nécessitent l'utilisation d'outils spécialisés et de bibliothèques pour leur implémentation.

Important ! Tu n'as pas besoin de te focaliser excessivement sur les algorithmes parallèles. Premièrement, en raison de la loi d'Amdahl, ils ne sont pas aussi efficaces qu'ils en ont l'air. Deuxièmement, les serveurs avec 30 processeurs traitent maintenant 3000 requêtes par minute, et nous avons toujours n tâches pour 1 processeur, et non 1 tâche pour n processeurs.

Troisièmement, les tâches réelles qui nécessitent d'être accélérées grâce au multiprocesseur sont toutes passées sur les GPU (cartes graphiques), et leur code est écrit dans des langages de bas niveau comme le C.