Explication des algorithmes parallèles embarrassants

Dans la programmation parallèle, un algorithme parallèle embarrassant est celui qui ne nécessite aucune communication ou dépendance entre les processus. Contrairement aux problèmes informatiques distribués qui nécessitent une communication entre les tâches, en particulier sur les résultats intermédiaires, des algorithmes parallèles embarrassants sont faciles à exécuter sur des fermes de serveurs qui ne disposent pas de l'infrastructure spéciale utilisée dans un véritable cluster de superordinateurs.

En raison de la nature des algorithmes parallèles embarrassants, ils sont bien adaptés aux grandes plates-formes distribuées basées sur Internet et ne souffrent pas de ralentissement parallèle. Le contraire des problèmes parallèles embarrassants sont des problèmes intrinsèquement sériels, qui ne peuvent pas du tout être parallélisés.

Le cas idéal des algorithmes parallèles embarrassants peut être résumé comme suit:

  • Tous les sous-problèmes ou tâches sont définis avant le début des calculs.
  • Toutes les sous-solutions sont stockées dans des emplacements mémoire indépendants (variables, éléments de tableau).
  • Ainsi, le calcul des sous-solutions est totalement indépendant.
  • Si les calculs nécessitent une communication initiale ou finale, nous l'appelons presque parallèlement de manière embarrassante.

Beaucoup peuvent se demander l'étymologie du terme «embarrassant». Dans ce cas, embarrassant n'a rien à voir avec l'embarras; en fait, cela signifie une surabondance - faisant référence ici à des problèmes de parallélisation qui sont «d'une simplicité embarrassante».

Un exemple courant d'un problème parallèle embarrassant est le rendu vidéo 3D géré par une unité de traitement graphique, où chaque image ou pixel peut être traité sans interdépendance. D'autres exemples seraient un logiciel de pliage de protéines qui peut fonctionner sur n'importe quel ordinateur, chaque machine effectuant une petite partie du travail, la génération de tous les sous-ensembles, des nombres aléatoires et des simulations de Monte Carlo.