The use of efficient synchronization mechanisms is crucial for implementing fine grained parallel programs on modern shared cache multi- core architectures. In this paper we study this problem by considering Single-Producer/Single-Consumer (SPSC) coordination using unbounded queues. A novel unbounded SPSC algorithm capable of reducing the row synchronization latency and speeding up Producer-Consumer coordina- tion is presented. The algorithm has been extensively tested on a shared-cache multi-core platform and a sketch proof of correctness is presented. The queues proposed have been used as basic building blocks to implement the FastFlow parallel framework, which has been demonstrated to offer very good performance for fine-grain parallel applications.

An Efficient Unbounded Lock-Free Queue for Multi-core Systems

ALDINUCCI, MARCO;
2012-01-01

Abstract

The use of efficient synchronization mechanisms is crucial for implementing fine grained parallel programs on modern shared cache multi- core architectures. In this paper we study this problem by considering Single-Producer/Single-Consumer (SPSC) coordination using unbounded queues. A novel unbounded SPSC algorithm capable of reducing the row synchronization latency and speeding up Producer-Consumer coordina- tion is presented. The algorithm has been extensively tested on a shared-cache multi-core platform and a sketch proof of correctness is presented. The queues proposed have been used as basic building blocks to implement the FastFlow parallel framework, which has been demonstrated to offer very good performance for fine-grain parallel applications.
2012
18th International Conference on Parallel Processing, Euro-Par 2012
Rhodes, Greece
August 2012
Proceedings of the 18th International Conference on Parallel Processing, Euro-Par 2012;Rhodes Island;27 August 2012through31 August 2012
Springer-Verlag
7484
662
673
9783642328190
http://link.springer.com/chapter/10.1007%2F978-3-642-32820-6_65
Lock-free algorithms; wait-free algorithms; bounded and unbounded SPSC queues; cache-coherent multi-cores.
Marco Aldinucci; Marco Danelutto; Peter Kilpatrick; Massimiliano Meneghin; Massimo Torquati
File in questo prodotto:
File Dimensione Formato  
2012_SPSC_europar.pdf

Accesso riservato

Descrizione: editoriale
Tipo di file: PDF EDITORIALE
Dimensione 261.99 kB
Formato Adobe PDF
261.99 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2012_spsc_europar_author_copy.pdf

Accesso aperto

Descrizione: post-print autore
Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 334.61 kB
Formato Adobe PDF
334.61 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/121343
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 57
  • ???jsp.display-item.citation.isi??? 42
social impact