ALGORITHMS FOR SEARCH-TREES ON MESSAGE-PASSING ARCHITECTURES

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.