Faculté des sciences

Semantics, performance and language support for transactional memory

Harmanci, Derin Mehmet ; Felber, Pascal (Dir.)

Thèse de doctorat : Université de Neuchâtel, 2012 ; 2261.

The emergence of multi-core architectures suggests that programmers should write concurrent programs for exploiting the continuously increasing computing capacity of the hardware. Currently, the predominant approach to write concurrent programs is to use locks, but using locks for writing correct concurrent programs is difficult. A recent approach to simplify concurrent programming is to... More

Add to personal list
    Résumé

    Avec l’apparition des architectures multi-cœurs, les programmeurs doivent écrire des programmes concurrents pour exploiter pleinement la capacité de calcul de ces architectures. Actuellement, l’écriture des programmes concurrents est, en général, réalisée en utilisant les verrous, mais écrire un programme correct avec cette approche est difficile. Une approche récente pour simplifier la programmation concurrente est d’introduire des blocs transactionnels dans les langages de programmation. De tels blocs de code sont délimités par des éléments spécifiques du langage et s’exécutent de manière transactionnelle (c.à.d. le bloc peut être avorté et reexécuté au besoin). Inclure ces blocs de langage masque au programmeur la synchronisation des données entre fils d’exécution concurrents et, par conséquent, offre une alternative attractive à l’utilisation des verrous.

    Malgré ses avantages, cette approche doit satisfaire les exigences suivantes pour qu’un programmeur soit convaincu d’utiliser des blocs transactionnels: (i) la sémantique du comportement transactionnel doit être simple et claire (ii) la performance d’un code utilisant des blocs transactionnels doit passer à l’échelle par rapport au nombre de fils d’exécutions concurrents (à condition que la charge de travail représentée par le code le permette) et doit en même temps offrir une performance supérieure à celle de l’exécution séquentielle lorsque le code s’exécute sur plusieurs fils d’exécution, et (iii) le support de langage associé aux blocs transactionnels doit être simple à utiliser, tant en termes de syntaxe que d’intéropérabilité avec les autres éléments de langage. Les premières deux conditions doivent être satisfaites par le support d’exécution, nommé Mémoire transactionnelle (MT), qui réalise le comportement transactionnel. Malgré l’existence de nombreuse MTs, il n’y a pas d’approche pour vérifier si elles satisfont ces deux conditions en même temps. De plus, il n’existe que peu de travaux visant à avoir un support de langage riche pour satisfaire la troisième condition. La présente thèse propose des solutions à chacun de ces problèmes à travers deux nouveaux outils: TMunit et TMJava.

    TMunit est l’outil proposé aux programmeurs pour vérifier si une MT satisfait certaines conditions en termes de sémantique et de performance. La possibilité d’expérimenter avec ces deux aspects (sémantiques et performance) des MTs rend TMunit unique pour la conception des MTs. Côté sémantique, TMunit est capable de décrire des scénarios au niveau des opérations transactionnelles, et permet donc de définir des tests détaillés pour vérifier la sémantique des MTs. Côté performance, TMunit permet d’évaluer la performance des MTs en décrivant des scénarios plus complexes où les motifs d’accés aux données partagées peuvent être spécifié. TMunit propose une interface abstraite qui lui permet de stimuler n’importe quelle MT et il est accompagné d’une batterie de test pour que les aspects communs de sémantique et performance des MTs puissent être vérifiés aisément.

    TMJava vise un support de langage riche pour les blocs transactionnel. Il propose une extension pour Java sous forme d’élément de langage transactionnels qui fournissent (i) la synchronisation des données automatisées, (ii) le flot de contrôle transactionnel, et (ii) un traitement des exceptions augmenté. L’atout distinctif de TMJava est le fait qu’il propose l’utilisation des blocs transactionnels non seulement pour la synchronisation des données, mais aussi pour le traitement des exceptions (qui n’est pas abordé par les autres approches existantes). En particulier, TMJava introduit une extension de langage novatrice, Atomic Boxes, qui permet aux programmeurs de traiter les exceptions de manière coordonnée. Cette extension est surtout intéressante pour propager les exceptions parmi tous les fils d’exécution concernés et pour exécuter des actions coordonnées de récupération d’exception à partir d’un état sûr du programme concurrent.
    Summary

    The emergence of multi-core architectures suggests that programmers should write concurrent programs for exploiting the continuously increasing computing capacity of the hardware. Currently, the predominant approach to write concurrent programs is to use locks, but using locks for writing correct concurrent programs is difficult. A recent approach to simplify concurrent programming is to introduce transactional blocks into programming languages. Such code blocks would be demarcated by a specific language construct so that the block executes in a transactional manner (i.e., the block can be aborted and restarted whenever required). Providing these language-level blocks is expected to simplify concurrent program development by hiding data synchronization between concurrent executions from the programmer and, hence, is an appealing alternative to locks.

    Although transactional blocks have advantages over locks, convincing a programmer to use transactional blocks for data synchronization requires the following: (i) the semantics of the transactional behavior should be clear and simple, (ii) the performance of a program using transactional blocks should be scalable with the number of concurrent hardware threads (as long as the workload represented by the program allows it) as well as being better than the sequential execution performance when run on multiple threads, and (iii) the language support should be such that it is easy to use transactional blocks both in terms of syntax and interoperability with other language features. The first two requirements should mostly be met by the run-time support that implements the actual transactional behavior, called Transactional Memory (TM). Although many different TM implementations exist there are no approaches to verify whether these implementations meet both requirements at the same time. Moreover, few studies target rich language support to meet the third requirement. This thesis aims at providing a solution to each of these shortcomings by proposing two tools: TMunit and TMJava.

    TMunit is the tool we propose for programmers to verify whether a TM implementation meets the semantic and performance requirements. The ability of TMunit to experiment with both aspects (semantic and performance aspects) makes it a unique aid for TM de- signers. For the semantics side, TMunit is capable of describing scenarios at the level of individual transactional operations and their interleavings, allowing to design detailed tests to verify semantics of TMs. For the performance side, TMunit, allows us to assess performance of TM implementations by describing complex scenarios (such as stressing a concurrent data structure) where access patterns to shared data can be specified. TMunit has an abstract interface that can bridge any TM and it comes with a test-suite so that common semantic and performance issues of TMs can readily be tested on any TM implementation.

    TMJava aims at providing a rich language support for transactional blocks. To that end, it proposes a language extension to Java in terms of new transactional constructs that support (i) automated data synchronization among concurrent threads, (ii) transactional control flow, and (iii) enhanced exception handling. A notable merit of TMJava is that it proposes to use transactional blocks not only for data synchronization but also for exception handling while most existing language support approaches address only the data synchronization aspect. In particular, TMJava introduces an original extension, Atomic Boxes, that allows programmers to handle exceptions among multiple threads in a coordinated manner. This is particularly useful to propagate exceptions to all concerned threads and to perform coordinated recovery actions at a safe point in the execution of a concurrent program.