Paper Info
Title
Algorithms for Search Trees on Message-Passing Architectures
Abstract
In this paper we describe a new algorithm for maintaining a balanced search tree on a message-passing MIMD architecture; the algorithm is particularly well suited for implementation on a small number of processors. We introduce a (2B驴2, 2B) search tree that uses a bidirectional ring of O(log n) processors to store n entries. Update operations use a bottom-up node-splitting scheme, which performs significantly better than top-down search tree algorithms. The bottom-up algorithm requires many fewer messages and results in less blocking due to synchronization than top-down 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.
Year
DOI
Venue
1996
10.1109/71.485500
IEEE Trans. Parallel Distrib. Syst.
Keywords
Field
DocType
bottom-up node-splitting scheme,search tree,bidirectional ring,n entry,bottom-up algorithm,message-passing mimd architecture,linear array,top-down search tree algorithm,search trees,new algorithm,cost ratio,balanced search tree,log n,message-passing architectures,top-down algorithm,dictionaries,bottom up,algorithms,computational modeling,abstract data types,message passing,computer architecture,parallel algorithms,ratios,computer science,top down,algorithm design and analysis,throughput
Query throughput,Binary logarithm,Synchronization,Search algorithm,Parallel algorithm,Computer science,Parallel computing,Algorithm,Ternary search tree,Message passing,Search tree,Distributed computing
Journal
Volume
Issue
ISSN
7
2
1045-9219
Citations 
PageRank 
References 
3
0.52
11
Authors
4
Name
Order
Citations
PageRank
Adrian Colbrook1403114.95
Eric A. Brewer27129907.87
Chrysanthos Dellarocas32458341.20
William E. Weihl42614903.11