Algorithms for Search Trees on Message-Passing Architectures

Abstract

This paper describes 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 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1991
Accession Number
ADA241344

Entities

People

  • Adrian Colbrook
  • Chrysanthos N. Dellarocas
  • Eric A. Brewer
  • William E. Weihl

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • C Programming Language
  • Classification
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Computing System Architectures
  • Databases
  • Information Processing
  • Linear Arrays
  • Military Research
  • Programming Languages
  • Security
  • Simulations
  • Simulators
  • Trees (Data Structures)

Fields of Study

  • Computer science
  • Engineering

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Parallel and Distributed Computing.