On the communication complexity of generalized 2-D convolution on array processors
- 1 February 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 38 (2) , 184-194
- https://doi.org/10.1109/12.16495
Abstract
Several parallel convolution algorithms for array processors with N/sup 2/ processing elements (PEs) connected by mesh, hypercube, and shuffle-exchange topologies, respectively, are presented. The computation time complexity is the same for array processors with different interconnection networks. The communication time complexity, however, varies from network to network, and is the main focus. It is shown that by using inter-PE communication networks efficiently, each PE requires only a small local memory, many unnecessary data transmissions are eliminated, and the overall time complexity (including computation and communication) of algorithms is reduced to O(M/sup 2/).Keywords
This publication has 17 references indexed in Scilit:
- Parallel Algorithms for Image Template Matching on Hypercube SIMD ComputersIEEE Transactions on Pattern Analysis and Machine Intelligence, 1987
- A pipeline architecture for computing cumulative hypergeometric distributionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Vector-Reduction Techniques for Arithmetic PipelinesIEEE Transactions on Computers, 1985
- A VLSI Systolic Architecture for Pattern ClusteringPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Algorithms for concurrent processorsPhysics Today, 1984
- Integrated Computer Architectures for Image Processing and Database ManagementComputer, 1983
- On a Class of Multistage Interconnection NetworksIEEE Transactions on Computers, 1980
- The cube-connected-cycles: A versatile network for parallel computationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Fast Boundary Detection: A Generalization and a New AlgorithmIEEE Transactions on Computers, 1977
- Scene Labeling by Relaxation OperationsIEEE Transactions on Systems, Man, and Cybernetics, 1976