Mesh-Connected Processor Arrays for the Transitive Closure Problem,

Abstract

The main purpose in this paper is to lay a theoretical foundation for the design of mesh connected processor arrays for the transitive closure program. Using a simple pathalgebraic formulation of the problem and observing its similarity to certain well known smoothing problems that occur digital signal processing, we show how to draw/upon existing techniques from the signal processing literature to derive regular iterative algorithms for determining the transitive closure of the graph. The regular iterative algorithms that are derived using this considerations, are then analyzed and synthesized on mesh-connected processor arrays. Among the vast number of mesh connected processor arrays that can be designed using this unified approach, the systolic arrays reported in the literature for this problem are shown to be special cases. Keywords: Mesh connected processor arrays; Transitive closure problems; Systolic architectures; Matrix multiplication; Array; and Iteration algorithm.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1985
Accession Number
ADA168627

Entities

People

  • Sailesh K. Rao
  • Thomas Kailath
  • Todd Citron

Organizations

  • Stanford University

Tags

Communities of Interest

  • Air Platforms
  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Contracts
  • Digital Signal Processing
  • Electrical Engineering
  • Engineering
  • Equations
  • Filtration
  • Image Processing
  • Information Systems
  • Iterations
  • Scheduling (Production)
  • Security
  • Signal Processing
  • Theoretical Computer Science
  • Universities

Fields of Study

  • Engineering

Readers

  • Integrated Circuit Design and Technology.
  • Linear Algebra
  • Operations Research