Tim's Home

My Project Proposal

My Project Milestone

I will implement both a locked lazy splay tree and a lock-free lazy splay tree to compare their performance on multi-core CPU platforms.

A splay tree is a self-balancing and caching binary search tree, which moves each element to the root after a search is performed on it. This data structure comes with powerful amortized cost guarantees, but it is not suited for parallel use due to contention for the root, which causes a large part of the computation to be sequential. To make splay trees amenable to parallelization, one splays (the act of moving a node after moving it) nodes not to the root but near enough to the root to reap the benefits of caching the value you searched for while not having massive contention for the root node. This is lazy splaying.

Despite the relaxation of the data structure to make it possible to parallelize effectively, the lazy splay tree will still be difficult to parallelize due to the difficulty of implementing fine grain locks and the even greater difficulty in implementing lock free data structures. On top of that, the data accessed has no guarantee of being local, and the communication involved when splaying nodes could be large. This also isn't the type of application which can benefit from SIMD execution, as the operations cannot always be performed in parallel. At best, the execution would be extremely divergent. I don't believe the system will pose a significant challenge, as it will be a standard multi-core CPU. The challenge comes mostly from the splay tree, less so from the machine I will implement it on.

I will begin coding from scratch. As a reference for the lock-free implementation, I plan to use this 2017 thesis by Sachiko Sueki at UNLV. I am not yet sure which locking splay tree algorithm I plan to use, but I will attempt to follow the trail of research that this 2015 thesis by Jaya Sedai leads me down. It would be useful if I could continue to use the computers at the Pittsburgh Supercomputing Center, as they would allow me to test scaling with large CPU count machines.


Extra Mile:

The use of multi-cored CPU machines is appropriate for this workload, as using a machine with few powerful cores fits the common use cases of splay trees, which often involve searching for elements to perform some sort of computation. That is, in practice, splay trees are used by low core count compute intensive

Week 1 (Nov 2 to Nov 9):

Week 2 (Nov 9 to Nov 16): Week 3 (Nov 16 to Nov 22): Week 4 (Thanksgiving Week, Nov 22 to Nov 29): Week 5 (Nov 29 to Dec 6): Last Days (Dec 6 to Dec 9):