The rise of new multicore CPUs introduced new challenges in the process of design of concurrent data structures: in addition to traditional requirements like correctness, linearizability and progress, the scalability is of paramount importance. It is a common opinion that these two demands are partially in conflict each others, so that in these computational environments it is necessary to relax the requirements on the traditional features of the data structures. In this paper we introduce a relaxed approach for the management of heap based priority queues on multicore CPUs, with the aim to realize a tradeoff between efficiency and sequential correctness. The approach is based on a sharing of information among only a small number of cores, so that to improve performance without completely losing the features of the data structure. The results obtained on a numerical algorithm show significant benefits in terms of parallel efficiency.

Relaxing the Correctness Conditions on Concurrent Data Structures for Multicore CPUs. A Numerical Case Study / Laccetti, G.; Lapegna, M.; Mele, V.; Montella, R.. - 10778:(2018), pp. 25-35. (Intervento presentato al convegno International Conference on Parallel Processing and Applied Mathematics) [10.1007/978-3-319-78054-2_3].

Relaxing the Correctness Conditions on Concurrent Data Structures for Multicore CPUs. A Numerical Case Study

Laccetti G.;Lapegna M.;Mele V.;
2018

Abstract

The rise of new multicore CPUs introduced new challenges in the process of design of concurrent data structures: in addition to traditional requirements like correctness, linearizability and progress, the scalability is of paramount importance. It is a common opinion that these two demands are partially in conflict each others, so that in these computational environments it is necessary to relax the requirements on the traditional features of the data structures. In this paper we introduce a relaxed approach for the management of heap based priority queues on multicore CPUs, with the aim to realize a tradeoff between efficiency and sequential correctness. The approach is based on a sharing of information among only a small number of cores, so that to improve performance without completely losing the features of the data structure. The results obtained on a numerical algorithm show significant benefits in terms of parallel efficiency.
2018
978-3-319-78053-5
Relaxing the Correctness Conditions on Concurrent Data Structures for Multicore CPUs. A Numerical Case Study / Laccetti, G.; Lapegna, M.; Mele, V.; Montella, R.. - 10778:(2018), pp. 25-35. (Intervento presentato al convegno International Conference on Parallel Processing and Applied Mathematics) [10.1007/978-3-319-78054-2_3].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11588/717137
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact