High Performance Data Structure for Multicore Environments

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