Memory Hierarchy Aware Parallel Priority Based Data Structures

With the proliferation of multicore and manycore architectures, memory hierarchy plays an important role in realizing expected performance of memory intensive scientific applications. A vast majority of scientific applications require a priority based data structure to discriminate among available data elements, for instance, a priority based data structure is imperative for extracting the earliest events in a discrete event simulation, identifying urgent tasks in a parallel scheduler, or exploring most promising sub-problems in a state-space search. Traditional priority based data structures are tree-based that makes them cache unfriendly due to the exponentially increasing distance between parent and child nodes. Fine grained largescale applications further cause excessive contention among competing processors due to frequent updates. In this dissertation we propose a priority based data structure that adapts to the memory hierarchy of the underlying computer system. The top priority items are aggregated and kept into a working subset of data items that is readily accessible for processing.