| Title | : | Concurrent Implementation of Treaps and Impact of Locking Objects |
| Speaker | : | Praveen Kumar Alapati (IITM) |
| Details | : | Fri, 4 Aug, 2017 3:30 PM @ Alan M Turing Semina |
| Abstract: | : | Importance of scalable and efficient concurrent data structures is increasing with growth in the area of multi-core and multi-processors. The ease of performing concurrent operations is heavily dependent on the type of data structure. For example, concurrent operations on data structures like linked lists and hash tables are easier than performing them on structures like binary search trees (BSTs) and AVL trees. Most frequently used data structures in sequential context are BSTs and its variations. Simple and efficient algorithms to perform basic operations, such as insert(), delete(), and contains(), on concurrent binary search trees are useful for developers, that require a concurrent tree-like structure.
We propose algorithms to perform operations concurrently on treaps in a shared memory multi-core and multi-processor environment. Concurrent treaps hold the advantage of nodes priority for maintaining height of treaps. Concurrent treaps make use of logical ordering and physical ordering of nodes’ keys, and pessimistic locking mechanism to achieve synchronization. We observe that our concurrent treap implementations scale well as compared to the state-of-the-art implementations. We also study the impact of different locking objects on throughput of concurrent treaps. Our experimental results show that the concurrent treap implementation that uses AtomicInteger locking object provides better throughput and utilizes less memory footprint. |
