TOWARDS AN EFFICIENT PARALLEL BINARY SEARCH TREE USING LOCK-FREE INSERTION

Abstract

Binary Search Tree (BST) was widely used in a large number of applications in order to search data in an efficient manner. On the modern multi-core systems, the implementation of parallel Binary Search Tree (BST) was unable to achieve maximum performance due to a high cost of locking mechanism, which was inevitable since the deployment of multiple parallel threads require locks to be implemented. This paper proposed a parallel lock-free BST which allowed for parallel insertion of data. Our proposed approach used atomic instructions like Compare, Swap, Fetch and Add to implement mutual exclusion and lock avoidance. The proposed implementation outperformed the sequential and the existing lock-based parallel binary search tree implementation. The proposed implementation of the parallel BST was evaluated on different platforms like Intel Xeon and Intel Core i5 processor based systems. The proposed approach achieved up to 12% performance improvement over the parallel lock-based implementation.