On Mapping Cube Graphs on VLSI Array and Tree Architectures.

Abstract

We formalize a model of array architectures suitable for VLSI implementation. A formal model of an arbitrarily structured tree machine is also presented. A mathematical framework is developed to transform cube graphs, which are data-flow descriptions of certain matrix computations, onto the array and tree models. All published algorithms for these computations can be obtained using the mathematical framework. In addition, novel linear-array algorithms for matrix multiplication are obtained. More importantly, the algorithms obtained for the tree model are of special significance. Besides their novelty, the independence of the tree algorithms from a specific inter-processor communication geometry make them robust to hardware faults as opposed to algorithms that are based on specific interconnection requirements. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1983
Accession Number
ADA139306

Entities

People

  • I. V. Ramakrishnan
  • P. J. Varman

Organizations

  • University of Maryland

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Arrays
  • Computations
  • Computer Science
  • Computers
  • Computing System Architectures
  • Electrical Engineering
  • Engineering
  • Geometry
  • Governments
  • Host Computers
  • Linear Arrays
  • Maryland
  • National Governments
  • United States
  • United States Government
  • Universities

Fields of Study

  • Computer science
  • Engineering

Readers

  • Computational Linguistics
  • Operations Research
  • Parallel and Distributed Computing.