International Symposium on Parallel Computing in Electrical Engineering (PARELEC'06)
Creating a Forest of Binary Search Trees for a Multiprocessor System
Bialystok, Poland
September 13-September 17
ISBN: 0-7695-2554-7
In a multiprocessor system, a lock-based scheme is used to ensure consistency and correctness during parallel processing. To manipulate a binary search tree in parallel, a process that modifies the current state of the data structure has to lock a certain portion of the tree. Lock-based schemes result in a longer wait time for the rest of the processes, particularly if a large portion of the tree has been locked. In a concurrent environment, the root of the binary search tree may therefore become a bottleneck, as it is the only entry point for all processes. To reduce the total wait time, it is possible to create and maintain a binary search tree with multiple roots, thereby allowing multiple processors to act upon different trees simultaneously. In this paper, we present static and dynamic methods to create and maintain a binary search tree with multiple roots. Without considerable overhead, a set of connected trees is created that resembles a forest, yet acts as a single binary search tree.
Citation:
Suri Pushpa, Prasad Vinod, Carsten Maple, "Creating a Forest of Binary Search Trees for a Multiprocessor System," parelec, pp.290-295, International Symposium on Parallel Computing in Electrical Engineering (PARELEC'06), 2006