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 17:08]
apeiron [Résumé] 		fr:research:bsp [2018/03/29 17:15]
apeiron
Ligne 3: Ligne 3:
 ====== Versions ====== ====== Versions ======
  
-{{ :​fr:​research:​bsp-asm.pdf |rapport technique}} disponible sur [[https://​hal.archives-ouvertes.fr/​hal-01717647|HAL]]+**An ASM Thesis for BSP** (Yoann Marquer, Frédéric Gava), le {{ :​fr:​research:​bsp-asm.pdf |premier ​rapport technique}}, est disponible sur [[https://​hal.archives-ouvertes.fr/​hal-01717647|HAL]]. 
 + 
 +**Algorithmic ​ Completeness of BSP Languages** (Yoann Marquer, Frédéric Gava), le {{ :​fr:​research:​bsp-while.pdf |second rapport technique}},​ est disponible sur [[https://​hal.archives-ouvertes.fr/​hal-01742406|HAL]]. 
  
-{{ :​fr:​research:​bsp-while.pdf |rapport technique}} 
  
 ====== Résumé ====== ====== Résumé ======
Ligne 30: Ligne 32:
 Puis nous avons étendu le modèle de calcul ASM à des p-uplet de processeurs en appliquant le même programme ASM en même temps à chaque processeur durant les phases de calcul, et durant les phases de communication en supposant l'​existence d'une fonction de communication abstraite (afin que le résultat ne dépende pas d'une implémentation particulière des communications). Nous avons prouvé que cette extension ASM-BSP est bien la contrepartie opérationnelle des algorithmes BSP définis de manière axiomatique,​ c'est à dire que ASM-BSP = Algo-BSP. Puis nous avons étendu le modèle de calcul ASM à des p-uplet de processeurs en appliquant le même programme ASM en même temps à chaque processeur durant les phases de calcul, et durant les phases de communication en supposant l'​existence d'une fonction de communication abstraite (afin que le résultat ne dépende pas d'une implémentation particulière des communications). Nous avons prouvé que cette extension ASM-BSP est bien la contrepartie opérationnelle des algorithmes BSP définis de manière axiomatique,​ c'est à dire que ASM-BSP = Algo-BSP.
  
 +Comme dans [[fr:​research:​fi-while|mon article sur While]] nous pensons qu'un langage impératif est plus pratique qu'une simple fonction de transition pour déterminer des classe en temps ou en espace, ou tout simplement pour être comparé à des langages de programmation plus usuels. Ainsi, nous avons défini dans le deuxième rapport technique la sémantique opérationnelle d'un langage impératif minimal While-BSP travaillant sur des p-uplets de processeurs. Enfin, nous avons prouvé que While-BSP et ASM-BSP pouvaient se simuler l'un l'​autre d'un point de vue algorithmique:​ While-BSP ≃ ASM-BSP.
 +
 +De ces deux rapports techniques, nous pouvons donc déduire que While-BSP ≃ Algo-BSP, et donc que notre langage impératif minimal est bien algorithmiquement complet (pour les algorithmes BSP).