Algorithms for Search Trees on Message-Passing Architectures

摘要

This paper describes a new algorithm for maintaining a balanced search tree on amessage-passing MIMD architecture; the algorithm is particularly well suited for implementation on a small number of processors. We introduce a search tree that uses a linear array of processors to store n entries. Update operations use a bottom-up node-splitting scheme, which performs better than top-down search tree algorithms. Additionally, for a given cost ratio of computation to communication the value of B may be varied to maximize performance. Implementations on a parallel-architecture simulator are described.