DARPA/ONR Quarterly Report.

Abstract

Consider an array of Processing Elements (PEs), connected by a 2- dimensional grid network, and holding at most one operand of an expression in each PE. Suppose that each PE is allowed, in any one parallel step, to receive one item of data from any of its 4 immediate neighbors, and to transmit one datum, as well. How can an associative operator, such as addition, combine all the operands, using as little time for communication as possible? An expression using such a single operator is termed a uniform expression. When the total number of communication links used is the measure of goodness, this problem becomes a Steiner Tree problem, in the Manhattan Distance metric. When the measure is minimizing the parallel time to completion, a method for solving this problem is given which is optimal to within an additive constant of 2 time- steps. The method has applications when the operands are matrices, spread over an array of PEUs, as well. Some lower bounds for this problem, in more general networks, are also proven.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 30, 1992
Accession Number
ADA257722

Entities

People

  • John Reif

Organizations

  • Duke University

Tags

Communities of Interest

  • Autonomy
  • Energy and Power Technologies
  • Engineered Resilient Systems

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Coding
  • Computations
  • Computer Programming
  • Computer Science
  • Data Compression
  • Equations
  • Fluid Mechanics
  • Geometry
  • Image Compression
  • Language
  • Molecular Dynamics
  • Simulations
  • Students
  • Three Dimensional
  • Two Dimensional

Readers

  • Graph Algorithms and Convex Optimization.
  • Regression Analysis.