Author(s):
1. A.M. Dogar:
Bahauddin Zakariya University,Multan,Pakistan
2. M.A. Khan:
COMSATS Institute of Information Technology, Sahiwal, Pakistan
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.
Page(s):
409-416
DOI:
DOI not available
Published:
Journal: Pakistan Journal of Science, Volume: 69, Issue: 4, Year: 2017
Keywords:
Lockfree
,
Atomic Instructions
,
Tree Insertion
,
Binary Search Tree
References:
References are not available for this document.
Citations
Citations are not available for this document.