High Performance Data Structures for Multicore Environments
Authors: Giuliano Laccetti (University of Naples Federico II), Marco Lapegna (University of Naples Federico II)
Abstract: Heap-based priority queues are common dynamical data structures used in several fields, ranging from operating systems to scientific applications. However, the rise of new multicore CPUs introduced new challenges in the process of design of these data structures: in addition to traditional requirements like correctness and progress, the scalability is of paramount importance. It is a common opinion that these two 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 paper we introduce a loosely coordinated 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 only among a small number of cores, so as to improve performance without completely losing the features of the data structure.
Two-page extended abstract: pdf