Composable operations on high-performance concurrent collections
Abstract/Contents
- Abstract
- Consider the task of designing the API for a data structure or reusable software component. There is a tension between simplicity and completeness: a simple interface is easier to learn and implement, but a complex interface is likely to include more of the functionality desired by the end user. The fundamental tool for managing this tension is composition. Composition allows complex operations to be built up from a few primitive ones. Much of the art of API design comes in choosing a set of primitives that is both simple and complete. Unfortunately, existing efficient concurrent data structures don't have the ability to safely compose operations. The lack of a generic mechanism for composition leads their APIs to be both more complex and less complete. This thesis presents new algorithms and techniques that allow composability for thread-safe sets and maps, while retaining excellent performance and scalability. First, we use optimistic techniques inspired by software transactional memory (STM) to add lazy copy-on-write to an efficient concurrent binary tree. This enables the collection to provide a linearizable clone operation whose running time is independent of the size of the tree. Second, we introduce transactional predication, a technique that allows STM integration of a concurrent map while bypassing the STM for most memory accesses. This improves the performance and scalability of the resulting transactional map, making it more suitable as a replacement for existing non-composable thread-safe maps. Finally, we explore the coexistence of lock-free algorithms and STM, producing an efficient transactional hash trie that includes lazy copy-on-write. We find that by tailoring the data structure for the STM environment and separately considering the case of non-transactional accesses, we can achieve both full composability and excellent performance and scalability.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2011 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Bronson, Nathan Grasso | |
|---|---|---|
| Associated with | Stanford University, Computer Science Department | |
| Primary advisor | Olukotun, Oyekunle Ayinde | |
| Thesis advisor | Olukotun, Oyekunle Ayinde | |
| Thesis advisor | Engler, Dawson R | |
| Thesis advisor | Kozyrakis, Christoforos, 1974- | |
| Advisor | Engler, Dawson R | |
| Advisor | Kozyrakis, Christoforos, 1974- |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Nathan G. Bronson. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Ph.D. Stanford University 2011 |
| Location | electronic resource |
Access conditions
- Copyright
- © 2011 by Nathan Grasso Bronson
- License
- This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).
Also listed in
Loading usage metrics...