Friday, November 13, 2009
Michael Spiegel
Chair: Bill Wulf
Advisor: Paul Reynolds, Andrew Grimshaw, abhi shelat, Steve Boker and Doug Lea
Olsson Hall, Conference Room 236D, 13:00:00
A Ph.D. Proposal
Cache-Conscious Concurrent Data Structures
ABSTRACT
The power wall, the ILP wall, and the memory wall are driving a trend from implicitly parallel architectures towards explicitly parallel architectures. The memory wall has been identified as one of the fundamental challenges to high-performance concurrent computing. A pair of trends in concurrent data structure design have improved scalability at the expense of spatial locality of reference. The first trend is the shift from coarse-grained locking to fine-grained locking and finally to atomic synchronization primitives that operate on one unit of memory at a time. The second trend is the reliance randomization techniques to avoid the global balancing requirements that exist for sorted data structures. It will been shown that the design of cache-conscious, linearizable concurrent data structures has advantageous properties that can be measured across multiple architecture platforms. This dissertation aims to fill the gap in cache conscious concurrent data structures by providing concurrent algorithms that implement an sorted set abstract data type. I will introduce the dense skip tree, a randomized data structure that has been designed to probabilistically exploit spatial locality of reference. The dense skip tree causes fewer cache misses than self-balancing binary search trees by probabilistically aggregating consecutive sequences of keys into contiguous regions of memory. The primary contributions of this thesis will be the simple optimistic skip tree algorithm, the lock-free concurrent skip tree algorithm, and the lock-free concurrent HAT trie algorithm.