Synchronisation (multitâches)

Résumé

En programmation concurrente, la synchronisation se réfère à deux concepts distincts mais liés : la synchronisation de processus et la synchronisation de données. La synchronisation de processus est un mécanisme qui vise à bloquer l'exécution de certains processus à des points précis de leur flux d'exécution, de manière que tous les processus se rejoignent à des étapes relais données, tel que prévu par le programmeur. La synchronisation de données, elle, est un mécanisme qui vise à conserver la cohérence des données telles que vues par différents processus, dans un environnement multitâche. Initialement, la notion de synchronisation est apparue pour la synchronisation de données. Ces problèmes dits « de synchronisation » et même plus généralement ceux de communication inter-processus dont ils dépendent, rendent pratiquement toujours la programmation concurrente plus difficile. Certaines méthodes de programmation, appelées synchronisation non-bloquante, cherchent à éviter d'utiliser

Source officielle

https://fr.wikipedia.org/wiki/Synchronisation_(multit%C3%A2ches)

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (83)

Publications associées

Chargement

Personnes associées (22)

Personnes associées

Chargement

Unités associées (13)

Unités associées

Chargement

Concepts associés (28)

Concepts associés

Chargement

Cours associés (14)

Multiprocessors are a core component in all types of computing infrastructure, from phones to datacenters. This course will build on the prerequisites of processor design and concurrency to introduce the essential technologies required to combine multiple processing elements into a single computer.

With the advent of multiprocessors, it becomes crucial to master the underlying algorithmics of concurrency. The objective of this course is to study the foundations of concurrent algorithms and in particular the techniques that enable the construction of robust such algorithms.

Hardware compilation is the process of transforming specialized hardware description languages into circuit descriptions, which are iteratively refined, detailed and optimized. The course presents algorithms, tools and methods for hardware compilation and logic synthesis.

Afficher plus

Cours associés

Chargement

Séances de cours associées (22)

Afficher plus

Séances de cours associées

Chargement

In this paper we address the problem of encoding complex concurrency control in reconfigurable systems. Such systems can be often reconfigured, either statically, or dynamically, in order to adapt to new requirements and a changing environment. We therefore take a declarative approach and introduce a set of high-level programming abstractions which allow the programmer to easily express complex synchronization constraints in multithreaded programs. The constructs are based on our model of role-based synchronization (RBS) which assumes attaching roles to concurrent threads and expressing a synchronization policy between the roles. The model is illustrated by describing an experimental implementation of our language as a design pattern library in OCaml. Finally, we also sketch a small application of a web access server that we have implemented using the RBS design pattern.

Springer2005

Chargement

The increased number of cores integrated on a chip has brought about a number of challenges. Concerns about the scalability of cache coherence protocols have urged both researchers and practitioners to explore alternative programming models, where cache coherence is not a given. Message passing, traditionally used in distributed systems, has surfaced as an appealing alternative to shared memory, commonly used in multiprocessor systems. In this thesis, we study how basic communication and synchronization primitives on manycore processors can be improved, with an accent on taking advantage of message passing. We do this in two different contexts: (i) message passing is the only means of communication and (ii) it coexists with traditional cache-coherent shared memory. In the first part of the thesis, we analytically and experimentally study collective communication on a message-passing manycore processor. First, we devise broadcast algorithms for the Intel SCC, an experimental manycore platform without coherent caches. Our ideas are captured by OC-Bcast (on-chip broadcast), a tree-based broadcast algorithm. Two versions of OC-Bcast are presented: One for synchronous communication, suitable for use in high-performance libraries implementing the Message Passing Interface (MPI), and another for asynchronous communication, for use in distributed algorithms and general-purpose software. Both OC-Bcast flavors are based on one-sided communication and significantly outperform (by up to 3x) state-of-the-art two-sided algorithms. Next, we conceive an analytical communication model for the SCC. By expressing the latency and throughput of different broadcast algorithms through this model, we reveal that the advantage of OC-Bcast comes from greatly reducing the number of off-chip memory accesses on the critical path. The second part of the thesis focuses on lock-based synchronization. We start by introducing the concept of hybrid mutual exclusion algorithms, which rely both on cache-coherent shared memory and message passing. The hybrid algorithms we present, HybLock and HybComb, are shown to significantly outperform (by even 4x) their shared-memory-only counterparts, when used to implement concurrent counters, stacks and queues on a hybrid Tilera TILE-Gx processor. The advantage of our hybrid algorithms comes from the fact that their most critical parts rely on message passing, thereby avoiding the overhead of the cache coherence protocol. Still, we take advantage of shared memory, as shared state makes the implementation of certain mechanisms much more straightforward. Next, we try to profit from these insights even on processors without hardware support for message passing. Taking two classic x86 processors from Intel and AMD, we come up with cache-aware optimizations that improve the performance of executing contended critical sections by as much as 6x.

EPFL2015

Chargement

In this paper we discuss the problem of synchronization in ZooKeeper, a fault-tolerant distributed coordination framework. One of the key features of ZooKeeper is to move away from blocking API such as locks, in order to avoid problems with slow or faulty clients. Instead, it provides an event like synchronization mechanism, allowing clients to be notified upon state change on the server. However, such a mechanism leads to very inecient implementation of synchronization objects such as queues or barriers. We propose a new solution to this problem. The solution is to handle a sequence of client operations completely on the server. This means that the client implements the required sequence of operations as a single request, which is sent to the server for execution via a generic API. We present a prototype that shares some of the concepts of ZooKeeper but, contrary to ZooKeeper, allows a very efficient implementation of synchronization objects. The solution requires a deterministic multi-threaded server, which we implement thanks to a coroutine mechanism. Experiments show the signicant gain in eciency of our solution on producer-consumer queues and synchronization barriers.

2012

Chargement

EPFL2015