loading...
Creating a Forest of Binary Search Trees for a Multiprocessor System
Bialystok, Poland September 13-September 17
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/PARELEC.2006.27International Symposium on Parallel C ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Suri Pushpa, Kurukshetra University, India
Prasad Vinod, Majan University College, Sultanate of Oman
Carsten Maple, University of Luton, United Kingdom
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
Usage of this product signifies your acceptance of the Terms of Use.