Kahn Process Networks as Concurrent Data Structures: Lock Freedom, Parallelism, Relaxation in Shared Memory

Nhat Minh Lê 1
1 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Résumé : La thèse porte sur les réseaux de Kahn, un modèle de concurrence simple et expressif proposé par Gilles Kahn dans les années 70, et leur implémentation sur des architectures modernes, multi-cœurs et à mémoire partagée. Dans un réseau de Kahn, le programmeur décrit un programme parallèle comme un ensemble de processus et de canaux communi- cants, chaque canal reliant exactement un processus producteur à un consommateur. Nous nous concentrons ici sur les aspects algorithmiques et les choix de conception liés à l’implémentation, avec en vue deux paramètres clefs : les garanties non bloquantes (lock freedom) et la mémoire relâchée. Le développement d’algorithmes non bloquants efficaces s’inscrit dans une optique de gestion des ressources (importante pour les systèmes embarqués) et de garantie de performance sur les plateformes à ordonnancement irrégulier, telles que les machines virtuelles ou les processeurs graphiques programmables. Un travail complémentaire sur les modèles de mémoire relâchée vient compléter cette ap- proche théorique par un prolongement plus pratique dans le monde des architectures à mémoire partagée contemporaines. Nous présentons un nouvel algorithme non bloquant pour l’interprétation de réseaux de Kahn. Celui-ci est parallèle sur les accès disjoints : il permet à plusieurs processeurs (ou plusieurs threads) de travailler simultanément sur un même réseau de Kahn partagé, tout en exploitant le parallélisme inhérent aux processus indépendants. Il offre dans le même temps des garanties de progrès global non bloquant, c’est-à-dire en mémoire bornée et en présence de retards sur les processeurs. L’ensemble forme, à notre connaissance, le premier système complètement non bloquant de cette envergure. Il met en œuvre une pa- lette cohérente de concepts et de techniques classiques de programmation non bloquante (recyclage de la mémoire, mises à jour complexes avec assistance, etc.), et incorpore des idées et optimisations spécifiques aux réseaux de Kahn. Nous discutons également d’une variante bloquante destinée au calcul haute performance, avec des résultats expérimentaux encourageants.
Type de document :
Thèse
Programming Languages [cs.PL]. Ecole normale supérieure - ENS PARIS, 2016. English
Liste complète des métadonnées

Littérature citée [42 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01684181
Contributeur : Albert Cohen <>
Soumis le : lundi 15 janvier 2018 - 12:02:19
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : samedi 5 mai 2018 - 20:09:04

Fichier

nml-thesis.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : tel-01684181, version 1

Collections

Citation

Nhat Minh Lê. Kahn Process Networks as Concurrent Data Structures: Lock Freedom, Parallelism, Relaxation in Shared Memory. Programming Languages [cs.PL]. Ecole normale supérieure - ENS PARIS, 2016. English. 〈tel-01684181〉

Partager

Métriques

Consultations de la notice

92

Téléchargements de fichiers

31