Implementations of Parallel Trie and Measurement of their Performance
Team Members: Sam Wang, Jake Wen
In this project, we plan to implement versions of parallel trie data structure with different programming models including Cuda and OpenMPI as well as with the lock-free variant. Also, we plan to bechmark their performances by measuring throughput and scalability.
The evolution of large-scale, data-intensive applications in domains such as distributed databases, real-time content retrieval, and networking has magnified the need for efficient data storage and retrieval systems. Tries, especially Patricia tries, have emerged as a favorable data structure for their ability to facilitate rapid searches, insertions, and deletions.
However, a significant challenge lies in the synchronization overhead when tries are adapted to distributed systems. Traditional lock-based synchronization mechanisms introduce bottlenecks that impair system scalability and degrade performance. This project proposes the research and implementation of a lock-free distributed trie (alternatively, a distributed Patricia trie), leveraging non-blocking synchronization methods to mitigate the issues associated with locks when exploiting distributed computing.
The key component of the application is the concurrent operations on the trie data structure, which includes node insertion, deletion, and search operations that correspond to database update, remove, and query functions. The structure of the Patricia trie itself inherently benefits from parallelism—updates to different parts of the trie can occur independently without interference if no common prefixes are involved. This will be exploited in our distributing approach that partitions the trie based on distinct key values and communicates them among different work node with OpenMPI. ` The proposed lock-free approach will likely benefit from parallelism in several aspects:
Lastly, we plan to explore CUDA to accelerates bulk lookups and inserts conducted on a trie data structure. leveraging CUDA to implement trie data structures presents a transformative opportunity for accelerating bulk operations. This parallelism is particularly beneficial for applications involving large-scale data, like big data analytics, where millions of keys may need to be inserted or looked up in the trie concurrently.
The main challenges in this project includes:
1) We need to correctly implement the locks on the data structure such that the critical sections are protected. Otherwise, concurrent lookups or insertions may lead to a corrupted data structure. 2) Lock-free trie is challenging to implement because we would need to understand the underlying machine instructions and apply complex techniques to ensure atomicity. 3) Achieving a linear speedup is hard because the trie does not provide good spacial locality for memory accessing. We would also need to do research to form a good strategy of diving the workload among processes. A trie can usually be skewed in a application setting, demanding careful load balance techniques to scale. 4) Since the data structure can evolve dynamically over updates including insertions and deletions, we need to implement rebalancing mechanisms to distribute work among processes.
Plan to Achieve:
We expect to successfully implement the following:
Hope to Achieve:
We also hope to achieve:
Demo:
We plan to demonstrate our outcomes in speedup graphs and also graphs on other metrics that shed light into the improvement of scalability and capacity of data the system can hold.
Analysis Projects:
Lock-Free Mechanism Evaluation: How effective are lock-free mechanisms in reducing the overhead associated with synchronization in distributed systems, specifically in the context of trie operations? We will compare the performance of lock-free tries against traditional lock-based approaches to understand the trade-offs in complexity and performance.
CUDA Acceleration Analysis: To what extent does CUDA acceleration improve the performance of bulk operations in the trie data structure? We will benchmark the CUDA-implemented trie against its CPU counterparts to quantify the performance gains in terms of throughput and latency.
Load Balancing Effectiveness: How do different strategies for load balancing affect the performance and scalability of distributed tries? We will explore various techniques for partitioning the trie among different nodes and measure their impact on the system’s overall efficiency.
Memory Access Patterns and Optimization: How do trie data structures’ memory access patterns influence performance, and what optimizations can mitigate any negative impacts? This analysis will include looking at spatial and temporal locality, as well as the effects of hardware cache utilization.
We will implement the trie data structure in C++ and develop the benchmark scripts in Python. Experiments will be conducted on GHC machines. If time permnits, we will also experiment on PSC machines because it can easily scale from 1 core to 256 cores allowing for more comprehensive study into the performance of the data structure when scaling to larger systems.
April 26 - April 28: Final Exam for Other Courses, No Schedule
Over the past two weeks, our team has concentrated on developing sequential and course-grained lock algorithms for the Radix Trie and Patricia Trie. While a plain parallel prefix trie can easily be implemented, a Paricia trie incorporates more involved mechanisms that convert string into bits and have circular references to save sapce and handle all unicode characters. Due to this complication, we struggled with implementing even the correct sequential Patricia trie. After several failed attempts to implement the patricia trie, we turned to first implement a Radix Trie which is a simplified version of Patricia trie. To make things easier, we decided to constrain our problem to solve within ASCII characters, which free ourselves from the bit conversions. While the Radix Trie met all correctness tests, we keep encountering issues with the Patricia Trie and are currently debugging these errors. This setback slows down our progress so that we did not finish implementing the fine-grained and lock-free variants in our original schedule.
As outlined in our future proposal, we aim to complete the Patricia Trie implementation within this week. Success in this endeavor will allow us to develop parallel algorithms for both trie types. Conversely, should complications arise, our efforts will pivot towards refining the Radix Trie, especially considering its structural complexity compared to the binary node limit in the Patricia Trie, which could pose challenges in parallel processing when using a large number of threads. One of our biggest concerns is that we couldn’t find or generate a suitable problem size that helps us understand how much speedup we get from the distribute Radix tries.
Before our final presentation, our objectives include completing the coarse-grained lock, fine-grained lock, and lock-free versions of the Radix Trie. While parallel implementations of the Patricia Trie remain a secondary goal, our final report and presentation will feature speed-up, cache-miss, and storage efficiency graphs to illustrate our findings and optimizations.