Ceci est une ancienne révision du document !
Ce travail a démarré fin 2016, et a été réalisé en collaboration avec Frédéric Gava, maître de conférences à l'Université Paris-Est Créteil. Bien qu'il n'ait pas été financé par contrat, j'ai été affilié au Laboratoire d’Algorithmique, Complexité et Logique pendant que j'exerçais mon activité de chercheur bénévole.
Versions
rapport technique disponible sur HAL
Résumé
La thèse de Gurevich énonce que l'ensemble des algorithmes séquentiels sont capturés par ses trois postulats. De plus, il a prouvé que ces trois postulats définissent le même ensemble que ses Abstract State Machines. Ainsi, nous avons que ASM = Algo. Cela montre que l'approche axiomatique des postulats est équivalente à l'approche opérationnelle des ASMs.
Dans 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 pont1) 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 :
- Chaque processeur effectue des calculs locaux, en n'utilisant que les valeurs stockées dans sa propre mémoire.
- Puis les processeurs envoient ou reçoivent des données.
- 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 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.