| Title | : | Concurrent Binary Search Tree with Fatnodes |
| Speaker | : | Praveen Kumar Alapati (IITM) |
| Details | : | Wed, 14 Mar, 2018 3:00 PM @ A M Turing Hall |
| 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 introduce a concurrent binary search tree with fatnodes (FatCBST) and present algorithms to perform basic operations on it. Unlike a simple node with single value, a fatnode consists of a set of values. FatCBST concept allows a thread to perform update operations on an existing fatnode without changing the tree structure, making it less disruptive to other threads' operations. Fatnodes help to take advantage of the spatial locality in the cache hierarchy and also reduce the height of the concurrent binary search tree. FatCBST implementation allows multiple threads to perform update operations on the same existing fatnode at the same time. Experimental results show that the FatCBST implementation outperforms all the existing implementations for low contention workloads as well as larger set sizes. FatCBST also provides high performance-per-watt values as compared to the state-of-the-art implementations. |
