Algorithme parallèle - Analyse

L'analyse d'un algorithme nous aide à déterminer si l'algorithme est utile ou non. Généralement, un algorithme est analysé en fonction de son temps d'exécution(Time Complexity) et la quantité d'espace (Space Complexity) cela demande.

Étant donné que nous disposons de périphériques de mémoire sophistiqués à un coût raisonnable, l'espace de stockage n'est plus un problème. Par conséquent, la complexité de l'espace n'a pas autant d'importance.

Les algorithmes parallèles sont conçus pour améliorer la vitesse de calcul d'un ordinateur. Pour analyser un algorithme parallèle, nous considérons normalement les paramètres suivants -

• Complexité temporelle (temps d'exécution),
• Nombre total de processeurs utilisés, et
• Coût total.

Complexité temporelle

La principale raison du développement d'algorithmes parallèles était de réduire le temps de calcul d'un algorithme. Ainsi, évaluer le temps d'exécution d'un algorithme est extrêmement important pour analyser son efficacité.

Le temps d'exécution est mesuré sur la base du temps mis par l'algorithme pour résoudre un problème. Le temps total d'exécution est calculé à partir du moment où l'algorithme commence à s'exécuter jusqu'au moment où il s'arrête. Si tous les processeurs ne commencent ou ne terminent pas l'exécution en même temps, alors le temps total d'exécution de l'algorithme est le moment où le premier processeur a commencé son exécution jusqu'au moment où le dernier processeur arrête son exécution.

La complexité temporelle d'un algorithme peut être classée en trois catégories -

• Worst-case complexity - Lorsque le temps requis par un algorithme pour une entrée donnée est maximum.

• Average-case complexity - Lorsque le temps requis par un algorithme pour une entrée donnée est average.

• Best-case complexity - Lorsque le temps requis par un algorithme pour une entrée donnée est minimum.

Analyse asymptotique

La complexité ou l'efficacité d'un algorithme est le nombre d'étapes exécutées par l'algorithme pour obtenir la sortie souhaitée. L'analyse asymptotique est effectuée pour calculer la complexité d'un algorithme dans son analyse théorique. Dans l'analyse asymptotique, une grande longueur d'entrée est utilisée pour calculer la fonction de complexité de l'algorithme.

Note - Asymptoticest une condition dans laquelle une ligne a tendance à rencontrer une courbe, mais elle ne se coupe pas. Ici, la ligne et la courbe sont asymptotiques l'une par rapport à l'autre.

La notation asymptotique est le moyen le plus simple de décrire le temps d'exécution le plus rapide et le plus lent possible pour un algorithme utilisant des limites élevées et des limites basses de vitesse. Pour cela, nous utilisons les notations suivantes -

• Notation Big O
• Notation Omega
• Notation thêta

Notation Big O

En mathématiques, la notation Big O est utilisée pour représenter les caractéristiques asymptotiques des fonctions. Il représente le comportement d'une fonction pour des entrées importantes dans une méthode simple et précise. C'est une méthode de représentation de la limite supérieure du temps d'exécution d'un algorithme. Il représente le temps le plus long que l'algorithme pourrait prendre pour terminer son exécution. La fonction -

f (n) = O (g (n))

ssi il existe des constantes positives c et n₀ tel que f(n) ≤ c * g(n) pour tous n où n ≥ n₀.

Notation Omega

La notation Omega est une méthode de représentation de la limite inférieure du temps d'exécution d'un algorithme. La fonction -

f (n) = Ω (g (n))

ssi il existe des constantes positives c et n₀ tel que f(n) ≥ c * g(n) pour tous n où n ≥ n₀.

Notation thêta

La notation thêta est une méthode de représentation à la fois de la limite inférieure et de la limite supérieure du temps d'exécution d'un algorithme. La fonction -

f (n) = θ (g (n))

ssi il existe des constantes positives c₁, c₂, et n₀ tel que c1 * g (n) ≤ f (n) ≤ c2 * g (n) pour tout n où n ≥ n₀.

Accélération d'un algorithme

La performance d'un algorithme parallèle est déterminée en calculant son speedup. L'accélération est définie comme le rapport entre le temps d'exécution le plus défavorable de l'algorithme séquentiel connu le plus rapide pour un problème particulier et le temps d'exécution le plus défavorable de l'algorithme parallèle.

Nombre de processeurs utilisés

Le nombre de processeurs utilisés est un facteur important dans l'analyse de l'efficacité d'un algorithme parallèle. Le coût d'achat, de maintenance et de fonctionnement des ordinateurs est calculé. Plus le nombre de processeurs utilisés par un algorithme pour résoudre un problème est grand, plus le résultat obtenu devient coûteux.

Coût total

Le coût total d'un algorithme parallèle est le produit de la complexité du temps et du nombre de processeurs utilisés dans cet algorithme particulier.

Coût total = complexité temporelle × nombre de processeurs utilisés

Par conséquent, la efficiency d'un algorithme parallèle est -