Différences
Ci-dessous, les différences entre deux révisions de la page.
| Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
|
fr:research:projects [2017/03/29 17:39] apeiron [Caractérisation impérative des algorithmes BSP] |
— (Version actuelle) | ||
|---|---|---|---|
| Ligne 1: | Ligne 1: | ||
| - | Cette page regroupe mes projets de recherche en cours ou prévus dans un futur proche. | ||
| - | |||
| - | ====== Recherche en cours ====== | ||
| - | |||
| - | ===== Caractérisation impérative des algorithmes BSP ===== | ||
| - | |||
| - | Bulk Synchronous Parallelism est un modèle de programmation parallèle consistant en la séquentialisation de \textbf{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 : | ||
| - | $$\text{cost of a superstep} = \max_{\text{processes}}w_i + \max_{\text{processes}}h_i \times g + \ell$$ | ||
| - | où $w_i$ est le temps nécessaire au processeur $i$ pour faire ses calculs locaux, $h_i$ est le nombre de communications envoyées ou reçues par le processeur $i$, $g$ est une mesure de la perméabilité du réseau, et $\ell$ est le coût d'une barrière de synchronisation. | ||
| - | |||
| - | Différents langages de programmation((Comme l'adoption par Google de Pregel et MapReduce, des projets libres de programmation avec de grandes performances comme Apache Hama ou Apache Giraph, des langages spécifiques comme BSML, ou et des implémentations de la BSPLib comme la Paderborn University BSP library ou la Oxford BSP Toolset de Jonathan Hill.)) ont tenté d'implémenter les algorithmes BSP, mais pour l'instant il n'y a pas de définition explicite faisant consensus. | ||
| - | |||
| - | Notre but avec Frédéric Gava, maître de conférences à l'Université Paris-Est Créteil, est de faire un travail similaire à celui de Gurevich pour définir **axiomatiquement** les algorithmes BSP avant de prouver que ces algorithmes peuvent être vus comme une extension naturelle du modèle des ASMs, et enfin de montrer une **équivalence algorithmique** des ces ASMs étendues avec un langage de programmation impératif. Ainsi, ce langage sera caractéristique des algorithmes BSP, et pourra être pris comme définition opérationnelle de ces algorithmes. | ||
| - | ====== Projets de recherche ====== | ||