From LaBRI - Laboratoire Bordelais de Recherche en Informatique

Theses: 2013JohnenMilani

Mémoire Transactionnelle fortement concurrente

Problématique générale

La dissipation thermique empêchant la progression des fréquences d'horloge, les architectures multi-coeurs, dans lesquelles plusieurs coeurs (unités de calcul) sont gravés sur une même puce, est actuellement la seule technique permettant d'augmenter la puissance de calcul. La programmation concurrente est indispensable lorsque l'on souhaite bénéficier des architectures multi-coeurs.

Le paradigme de programmation concurrente basé sur les verrous est le plus répandu à ce jour, mais demande de l'expertise pour éviter des situations de blocage tout en garantissant une bonne exploitation du parallélisme possible grâce à l'architecture sous-jacente. La complexité provient de la synchronisation des fils d'exécution (threads) concurrents qui doivent accéder une partie commune de la mémoire partagée. Sans cette synchronisation, les accès concurrents pourraient laisser la mémoire dans un état non-cohérent et ainsi générer des résultats incorrects ou provoquer dans le pire des cas des défaillances du logiciel. Le changement de masse des architectures et le fait que la plupart de programmeurs ne sont pas experts en programmation concurrente demande de repenser les abstractions pour la programmation concurrente. La mémoire transactionnelle proposée par M. Herlihy et Moss [1] est considérée un des paradigmes de programmation concurrente parmi les plus prometteuses. Elle commence à être intégré dans les nouveaux processeurs. La mémoire transactionnelle doit permettre de traduire de façon quasi-automatique du code séquentiel (qui ne comporte qu'un thread) en code concurrent. En particulier, en utilisant la notion de transaction bien connue dans les bases de données, le programmeur doit spécifier quels sont les blocs de code qui doivent être exécutés comme des transactions (comme une opération indivisible) et la mémoire transactionnelle est censée prendre en charge la synchronisation des accès concurrents en garantissant le progrès du calcul et la cohérence de la mémoire. Par exemple, on peut synchroniser les accès à une queue en encapsulant le code séquentiel pour insérer/récupérer un élément dans/de la queue dans une transaction. Chacune de ces opérations sera alors exécutée à l'aide d'une transaction et la mémoire transactionnelle garantira la cohérence de la queue même à front d'opérations concurrentes.

Objectifs de la thèse

Depuis la présentation du paradigme de mémoire transactionnelle, plusieurs algorithmes ont été proposés pour l'implémenter, e.g. [2,3]. Ces algorithmes ont des propriétés différentes et dans la plupart des cas ont été évalués au moyen de simulations. Aucun algorithme a des performances supérieures aux autres pour tout workload et en générale, il est difficile de comparer les résultats des simulations parce que trop dépendantes de la plateforme utilisée et des optimisations appliquées au code.

Le but de cette thèse est de contribuer à établir les fondements théoriques du calcul transactionnel. En particulier, on souhaite donner des modèles pour évaluer et comparer la complexité/les performances des mémoires transactionnelles et comprendre comment les techniques algorithmiques utilisées impactent sur ces derniers.

Les questions qu'on souhaite adresser sont du type:

  1. M. Herlihy, J. Eliot B. Moss: Transactional Memory: Architectural Support for Lock-Free Data Structures. ISCA 1993: 289-300
  2. D. Dice, O. Shalev, and N. Shavit. Transactional Locking II. Proc. of the 20th International Symposium on Distributed Computing (DISC 2006), pages 194-208, Stockholm, Sweden, September 2006.
  3. Y. Afek, A. Matveev, N. Shavit. Pessimistic Software Lock-Elision. To appear in Proc. of the 26th International Symposium on Distributed Computing (DISC 2012), 2012.
Récupéré sur http://www.labri.u-bordeaux.fr/index.php?n=Theses.2013JohnenMilani
Page mise à jour le 22/10/2012 à 08:56