Correct and Efficient Bounded FIFO Queues

Nhat Minh Lê 1 Adrien Guatto 1 Albert Cohen 1 Antoniu Pop 1
1 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : Bounded single-producer single-consumer FIFO queues are one of the simplest concurrent data-structure, and they do not require more than sequential consistency for correct operation. Still, sequential consistency is an unrealistic hypothesis on shared-memory multiprocessors, and enforcing it through memory barriers induces significant performance and energy overhead. This paper revisits the optimization and correctness proof of bounded FIFO queues in the context of weak memory consistency, building upon the recent axiomatic formalization of the C11 memory model. We validate the portability and performance of our proven implementation over 3 processor architectures with diverse hardware memory models, including ARM and PowerPC. Comparison with state-of-the-art implementations demonstrate consistent improvements for a wide range of buffer and batch sizes.
Type de document :
Communication dans un congrès
SBAC-PAD 2013 : International Symposium on Computer Architecture and High Performance Computing, Oct 2013, Porto de Galinhas, Brazil. IEEE, 2013
Liste complète des métadonnées


https://hal.inria.fr/hal-00911893
Contributeur : Albert Cohen <>
Soumis le : dimanche 1 décembre 2013 - 01:38:11
Dernière modification le : mercredi 28 septembre 2016 - 14:02:12
Document(s) archivé(s) le : lundi 3 mars 2014 - 20:46:01

Fichier

sbac13.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00911893, version 1

Collections

Citation

Nhat Minh Lê, Adrien Guatto, Albert Cohen, Antoniu Pop. Correct and Efficient Bounded FIFO Queues. SBAC-PAD 2013 : International Symposium on Computer Architecture and High Performance Computing, Oct 2013, Porto de Galinhas, Brazil. IEEE, 2013. <hal-00911893>

Partager

Métriques

Consultations de
la notice

297

Téléchargements du document

231