Time-Optimal 2D Convolution on Mesh-Connected SIMD Computers with Bounded Number of PEs

Jian LU  Taiichi YUASA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.8   pp.1021-1030
Publication Date: 1996/08/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Architectures, Algorithms and Networks for Massively Parallel Computing)
Category: Algorithms
Keyword: 
data-parallel algorithm,  data-distribution,  SIMD mesh,  convolution,  image processing.,  

Full Text: PDF>>
Buy this Article




Summary: 
2D (two-dimensional) convolution is a basic operation in image processing and requires intensive computation. Although the SIMD model is considered suitable for 2D convolution, previous 2D convolution algorithms on the SIMD model assume unbounded number of PEs (Processing Elements) available, which we call unbounded case. Unbounded case could not be satisfied on real computers. In this paper, time-optimal data-parallel 2D convolution is studied on mesh-connected SIMD computers with bounded number of PEs. Because the optimal computation complexity is not difficult to achieve, the main concern of this paper is how to achieve optimal communication complexity. Firstly the lower bound computation complexity is analyzed. Then the lower bound communication complexities are analyzed under two typical data-distribution strategies: block-mapping and cyclic-mapping. Based on the analysis result, an optimal algorithm is presented under the block-mapping. The algorithm achieves the lower bound complexity both in computation and in communication.