I began my work by reading research in fine-grained locking and lock-free binary trees. In particular, I spent a lot of time with Bouge et al’s paper, “Concurrent Rebalancing of AVL trees,” which provided a proof that rebalancing may be done separately from individual insert or delete operations. This eliminates a bottleneck that I experienced in early iterations of the tree, as performing rotations for every update would require locks for all imbalanced nodes and their children, children’s children, etc. Drawing on my research, I have implemented a fine-grained locking AVL tree with support for search, contains, insert, and delete operations. The AVL tree allows for lock-free search and contains operations. I have performed basic tests to ensure correctness for search, insert. and delete, but need to do more rigorous testing for performance and edge cases.
I believe I will be able to produce all my deliverables. My proposal stated that I planned to implement a locking and lock-free AVL implementation, and compare their performance in different cases and ratios of insert-delete. The deliverables include the implementations, tests, and data. I am on track with my original plan. Rather than beginning with lock-free AVL implementations, I began with the fine-grained implementation, as this research came easier to me at first, especially since I didn’t have a single-threaded implementation at the beginning of this project. In my original plan, I intended to spend two weeks on each implementation; I will keep to this timeline. I am slightly behind in collecting performance data for my implementations, but this did not take long in previous class assignments and I can collect both implementations’ data at once.
I will create test cases for different ratios of insert and delete, and collect data for both implementations for these cases. I will show graphs of the performance of both implementations, and identify and analyze trends in the data. Since this is a data structure, it is difficult to show an interactive demo.
A major challenge at this point is time: since I am working alone, maintaining balance (LOL) with other classes during finals will be difficult, but I believe I am on track and have a solid plan to finish. I also need to focus on developing more rigorous testing.
For this project, I will implement a lock-free concurrent AVL tree and several approaches to AVL trees with locks. I will then measure the performance of these implementations in different situations (such as algorithms that use insertion and deletion with different frequencies). If I have extra time, I will implement an application using AVL trees, such as a simple searching game.
Self-balancing binary search trees (BSTs) represent a fundamental data structure widely used across various applications to efficiently organize and search data. Among these, AVL trees stand out for their ability to maintain balance, ensuring good performance for insertion, deletion, and search operations. However, in scenarios where multiple threads concurrently access and modify the tree within a shared memory environment, traditional locking mechanisms introduce overhead that can impede scalability and performance.
This project aims to investigate different implementations of parallel AVL trees, exploring both locked and lock-free variants, to address the challenges posed by concurrent access. The primary focus is on devising efficient methods to maintain the integrity and balance of the AVL tree while enabling concurrent operations without the need for locks.
In the context of parallel computing, synchronization primitives such as locks are typically employed to prevent data corruption resulting from race conditions. However, the inherent contention for locks can lead to thread stalls and decreased parallelism, limiting scalability. By exploring lock-free techniques, which eliminate the need for explicit synchronization, this project seeks to mitigate these performance bottlenecks and unlock the full potential of parallelism in AVL tree operations.
The investigation will encompass various aspects, including the design, implementation, and evaluation of parallel AVL tree algorithms. I will compare the performance characteristics of lock-based and lock-free AVL tree implementations under different workloads and levels of concurrency. Through rigorous experimentation and benchmarking, insights will be gained into the trade-offs between synchronization overhead and scalability, guiding the selection of the most suitable approach for specific use cases.
In addition to evaluating standalone AVL tree implementations, the project may extend its scope to examine their integration within higher-level data structures and algorithms. For instance, investigating the feasibility of incorporating lock-free AVL trees into container classes like those found in the C++ Standard Template Library (STL) could yield practical insights into real-world applicability and performance benefits.
Developing efficient parallel AVL tree implementations, both with and without locks, poses several significant challenges. First, ensuring thread safety while maximizing concurrency requires intricate synchronization mechanisms, adding complexity to the codebase. Secondly, managing contention among threads accessing the tree concurrently demands careful consideration to prevent bottlenecks and scalability issues. Additionally, achieving a balance between minimizing memory overhead and maintaining data consistency further complicates the design process. Moreover, the performance of parallel AVL trees can be influenced by factors such as cache coherence effects and memory access patterns, necessitating thorough performance analysis under diverse workloads. Finally, creating situations to fully show the differences between situations may prove to be a challenge.
The primary goal of this project is to investigate and compare different implementations of parallel AVL trees, specifically focusing on variants with and without locks, with the following objectives and deliverables:
I chose C++ as the primary programming platform for this project because of its high performance and quality documentation. I hope to use C++ to develop highly optimized implementations of parallel AVL trees, explore both lock-based and lock-free synchronization mechanisms effectively, and analyze performance comprehensively. I will develop and benchmark my implementation on GHC machines, and may also use PSC machines for higher processor counts or heavier test cases.