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 and progress, the scalability is of paramount importance. It is a common opinion that these demands are partially in conflict each other, so that it is necessary to relax the requirements about a behavior identical to the corresponding sequential data structures. In this work 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 step-by-step redistribution, sharing information only among the cores connected in a virtual mesh.
High Performance Data Structure for Multicore Environments / Laccetti, Giuliano; Lapegna, Marco. - (2015). (Intervento presentato al convegno SC15: International Conference for High Performance Computing, Networking, STorage and Analysis tenutosi a Austin, TX (USA) nel 14-20/11/2015).
High Performance Data Structure for Multicore Environments
LACCETTI, GIULIANO;LAPEGNA, MARCO
2015
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 and progress, the scalability is of paramount importance. It is a common opinion that these demands are partially in conflict each other, so that it is necessary to relax the requirements about a behavior identical to the corresponding sequential data structures. In this work 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 step-by-step redistribution, sharing information only among the cores connected in a virtual mesh.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
