Two Papers on a Tree-Structured Parallel Computer.

Abstract

This report consists of two papers describing various aspects of a new tree-structured parallel computer. The first paper, 'A tree machine for searching problems' by J. L. Bentley and H. T. Kung, describes the basic architecture of the machine. A set of N elements can be maintained on an N-processor version of the machine such that insertions, deletions, queries and updates can all be processed in 2 lg N time units. The queries can be very complex, including problems arising in ordered set manipulation, data bases, and statistics. The machine is pipelined so that M successive operations can be performed in M-1 + 2 lg N time units. The paper studies both the basic machine structure and a VLSI implementation of the machine. The second paper, 'A parallel algorithm for constructing minimum spanning trees' by J. L. Bentley, shows how an (N/lg N)-processor version of the machine can solve the problem of constructing minimum spanning trees in time proportional to N lg N. This algorithm is an improvement over existing algorithms in several ways. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 25, 1979
Accession Number
ADA081933

Entities

People

  • H. T. Kung
  • Jon Louis Bentley

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies
  • Ground and Sea Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computations
  • Computer Architecture
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Computing Devices
  • Computing System Architectures
  • Data Analysis
  • Databases
  • Fabrication
  • Information Science
  • Operations Research
  • Trees (Data Structures)
  • Very Large Scale Integration

Fields of Study

  • Computer science
  • Engineering

Readers

  • Computer Programming and Software Development.
  • Graph Algorithms and Convex Optimization.
  • Operations Research