Overview
The Adaptive Radix Tree (ART) is an efficient in-memory index data structure on modern architectures that beats read-only search trees on lookup performance while at the same time supporting insertion and deletion. We implemented three synchronization protocols for the Adaptive Radix Tree and compared their performance under low and high contention. Our results showed that our optimistic lock coupling implementation scales better than the fine-grained lock coupling and the coarse-grained lock approach under both writer-only low contention scenarios and mixed writer and reader high contention scenarios. The results also suggest that using shared pointers as the memory reclamation method is inefficient in a parallel setting.
This project is developed as part of a final project for the 15-418/618 Parallel Computer Architecture and Programming class.
| Week | Work Item | Work split | Status |
|---|---|---|---|
| 04/16 - 04/21 | Sequential implementation - insert, get | Yuchen | ✅ |
| 04/16 - 04/21 | Sequential implementation - remove | Hang | ✅ |
| 04/22 - 04/24 | Garbage collection and lock implementation | Yuchen | ✅ |
| 04/22 - 04/24 | Benchmark setup | Hang | ✅ |
| 04/25 - 04/30 | LC and OLC implementation - insert, get | Yuchen | ✅ |
| 04/25 - 04/30 | LC and OLC implementation - remove | Hang | ✅ |
| 05/01 - 05/05 | Final report/result collection and analysis | Together | ✅ |
| 05/06 | Poster Session | Together | ✅ |