Electronic Thesis/Dissertation
Operating System Support for Shared Hardware Data Structures Open Access
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 HWDS. This thesis proposes operating system (OS) support for HWDSs so applications can share and use a HWDS even when its capacity is less than the data structure's size.The priority queue and map data structures demonstrate the appeal of an OS-HWDS union. A GPS benchmark with real-world data executes 24% faster using a HWDS instead of a software data structure, even though the data structure exceeds the hardware's capacity. Compared to software implementations, a 128-node HWDS achieves over 50% faster mean access time to a 512-node priority queue, and 15% faster mean search time in a 512-node read-mostly map. When sharing a HWDS among four maps of power-of-2 sizes between 64 and 512, a 128-node HWDS achieves 35% faster searches than a splay tree. These performance improvements are made possible by the OS support for HWDSs proposed in this thesis.
- License
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.
Relationships
Items
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
Bloom_gwu_0075A_11634.pdf | 2018-01-16 | Open Access |
|