A. Colbrook et al., ALGORITHMS FOR SEARCH-TREES ON MESSAGE-PASSING ARCHITECTURES, IEEE transactions on parallel and distributed systems, 7(2), 1996, pp. 97-108
Citations number
20
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
In this paper we describe a new algorithm for maintaining a balanced s
earch tree on a message-passing MIMD architecture; the algorithm is pa
rticularly well suited for implementation on a small number of process
ors. We introduce a (2(B-2), 2(B)) search tree that uses a bidirection
al ring of O(log n) processors to store n entries. Update operations u
se a bottom-up node-splitting scheme, which performs significantly bet
ter than top-down search tree algorithms. The bottom-up algorithm requ
ires many fewer messages and results in less blocking due to synchroni
zation than top-down algorithms. Additionally, for a given cost ratio
of computation to communication the value of B may be varied to maximi
ze performance. Implementations on a parallel-architecture simulator a
re described.