Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision 		Révision précédente
Prochaine révision Les deux révisions suivantes
fr:research:bsp [2018/03/29 16:31]
apeiron [Résumé] 		fr:research:bsp [2018/03/29 16:36]
apeiron
Ligne 13: Ligne 13:
 Dans [[fr:​research:​fi-while|cet article]], j'ai montré que les langages impératifs usuels sont non seulement Turing-complets mais aussi algorithmiquement complets. Cela a été fait en prouvant qu'un langage impératif minimal While est **algorithmiquement équivalent** aux ASMs de Gurevich. Ainsi, nous avons While ≃ ASM, ce qui signifie plus précisément que les exécutions des deux modèles de calcul sont les mêmes, à variables fraîches et dilatation temporelle près. Donc nous avons While ≃ Algo, ce qui montre que tout langage de programmation contenant les commandes de While est algorithmiquement complet (pour les algorithmes séquentiels). Dans [[fr:​research:​fi-while|cet article]], j'ai montré que les langages impératifs usuels sont non seulement Turing-complets mais aussi algorithmiquement complets. Cela a été fait en prouvant qu'un langage impératif minimal While est **algorithmiquement équivalent** aux ASMs de Gurevich. Ainsi, nous avons While ≃ ASM, ce qui signifie plus précisément que les exécutions des deux modèles de calcul sont les mêmes, à variables fraîches et dilatation temporelle près. Donc nous avons While ≃ Algo, ce qui montre que tout langage de programmation contenant les commandes de While est algorithmiquement complet (pour les algorithmes séquentiels).
  
-Dans le contexte HPC (High Performance Computing), un résultat similaire paraît difficile à obtenir. Le problème principal est le manque de définition pour ce qu'est formellement un calcul HPC, ou dit autrement, la communauté HPC manque d'une définition consensuelle de ce qu'est la classe des algorithmes HPC. Utiliser un **modèle pont(**(Voir l'​article de Valiant : A Bridging Model for Parallel Computation)) peut être vu comme un premier pas dans cette direction, qui fournit un pont conceptuel entre l'​implémentation physique de la machine, et l'​abstraction possible pour le programmeur. Cela simplifie également la tâche de la conception d'​algorithme,​ leur programmation,​ et assure une meilleure portabilité d'un système à l'​autre. Et, plus important encore, cela permet de raisonner sur le coût même des algorithmes.+Dans le contexte HPC (High Performance Computing), un résultat similaire paraît difficile à obtenir. Le problème principal est le manque de définition pour ce qu'est formellement un calcul HPC, ou dit autrement, la communauté HPC manque d'une définition consensuelle de ce qu'est la classe des algorithmes HPC. Utiliser un **modèle pont**((Voir l'​article de Valiant : A Bridging Model for Parallel Computation)) peut être vu comme un premier pas dans cette direction, qui fournit un pont conceptuel entre l'​implémentation physique de la machine, et l'​abstraction possible pour le programmeur. Cela simplifie également la tâche de la conception d'​algorithme,​ leur programmation,​ et assure une meilleure portabilité d'un système à l'​autre. Et, plus important encore, cela permet de raisonner sur le coût même des algorithmes.
  
 Plus précisément,​ BSP (Bulk Synchronous Parallelism) est un modèle de programmation parallèle consistant en la séquentialisation de **super-étapes** divisées en trois phases : Plus précisément,​ BSP (Bulk Synchronous Parallelism) est un modèle de programmation parallèle consistant en la séquentialisation de **super-étapes** divisées en trois phases :
Ligne 20: Ligne 20:
   - Enfin, une barrière de synchronisation a lieu quand les communications sont terminées, et rend les données échangées disponibles aux mémoires locales des processeurs.   - Enfin, une barrière de synchronisation a lieu quand les communications sont terminées, et rend les données échangées disponibles aux mémoires locales des processeurs.
  
-Le but est de rendre les programmes simples à écrire, indépendants des architectures,​ et que les performances d'un programme sur une architecture donné soit prévisible. Pour cela, les algorithmes BSP sont associés à un modèle de coût : +Le but est de rendre les programmes simples à écrire, indépendants des architectures,​ et que les performances d'un programme sur une architecture donné soit prévisible. Pour cela, les algorithmes BSP sont associés à un modèle de coût : le coût (en temps) d'une super-étape est w + h×g + l, où w est le nombre maximum de calculs fait par un processeur durant la super-étape,​ h est le nombre maximum de messages envoyés ou reçus, g mesure la perméabilité du réseau et l est le coût de la barrière de synchronisation.