Operating System Support for Shared Hardware Data Structures.

摘要

A fundamental problem in computing is that processors cannot access memory fast enough to stay fully utilized. Architecture features like cache, prefetching, out-of-order execution, and multiprocessing only benefit software with temporal or spatial locality, or instruction-level or task-level parallelism. Software that relies on fine-grained access to data with structural locality, such as pointer-based data structures, derives little benefit from these features. The importance of these data structures motivates a new approach to improve memory performance. A hardware data structure (HWDS) implements a data structure with operations that leverage parallelism and structural locality to reduce data structure access times, but only supports an exclusive data structure small enough to fit the capacity of the HWDS. This thesis proposes operating system (OS) support for HWDSs so that applications can use and share a HWDS even when its capacity is less than the data structure's size.