
Accession Number : ADA133248
Title : Analysis of Data Flow for SIMD (Single Instruction Multiple Data) Systems.
Descriptive Note : Technical rept.,
Corporate Author : MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH
Personal Author(s) : Klette,Reinhard
PDF Url : ADA133248
Report Date : Mar 1983
Pagination or Media Count : 70
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 online quadtreenet systems and the computation of Voronoi diagrams for N planar points, omega(N) for offline diagonalnet systems and the twodimensional discrete Fourier transform, and omega(square root of N) for off or online Illiacnet systems and sorting of N items. (Author)
Descriptors : *Parallel processing, *Data processing, *Computations, *Computer architecture, Accumulators, Problem solving, Information transfer, Two dimensional, Discrete fourier transforms
Subject Categories : Numerical Mathematics
Computer Hardware
Distribution Statement : APPROVED FOR PUBLIC RELEASE