Implementation of binary search tree with fine-grained locking and lock-free methods

This is the final project of 15-418/618: Parallel Computer Architecture and Programming, Fall 2021. The team members are: Ye Lu, Sean Zhou

Project proposal

You can find our project proposal here

You can find our milestone report here

You can find our final report here

You can find our raw benchmark data and diagrams presented in the final report here in google sheet

Project progress

✅ 11.3 - 11.8: paper reading and implementation decisions discussion

✅ 11.9 - 11.15: implementation of fine-grained locking BST

✅ 11.16 - 11.21: implementation of lock-free BST

✅ 11.22 - 11.25: Implement harness program and design workloads (Sean)

✅ 11.26 - 11.29: Preliminary correctness test with harness program (Ye)

✅ 11.30 - 12.2: Benchmark on fine grained lock BST and optimization (Sean)

✅ 12.3 - 12.5: Benchmark on lock-free BST and optimization (Ye)

✅ 12.6 - 12.9: writing final report and prepare for poster session (Ye, Sean)