Analysis of Data Flow for SIMD (Single Instruction Multiple Data) Systems.

Abstract

Starting with an exact definition of classes of SIMD (single instruction, multiple data) systems, a general approach to obtaining lower time bounds by data flow analysis is presented. Several interconnection schemes, such as the square net, the perfect shuffle, the infinite binary tree, etc. are analyzed with respect to their data transfer possibilities. For some types of computational problems the data dependencies are analyzed in a quantitative way. From both types of analysis, lower time bounds result for many combinations of SIMD systems and computational problems, for example, omega(log N) for on-line quadtree-net systems and the computation of Voronoi diagrams for N planar points, omega(N) for off-line diagonal-net systems and the two-dimensional discrete Fourier transform, and omega(square root of N) for off- or on-line Illiac-net systems and sorting of N items. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1983
Accession Number
ADA133248

Entities

People

  • Reinhard Klette

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Central Processing Units
  • Coding
  • Computational Processes
  • Computations
  • Data Analysis
  • Data Processing
  • Data Transmission
  • Digital Image Processing
  • Discrete Fourier Transforms
  • Image Processing
  • Instruction Set Architecture
  • Parallel Computing
  • Parallel Processing
  • Trees (Data Structures)
  • Two Dimensional
  • Universities

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.