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.

We have launched "Highly-Reliable Embedded Software Development" Project, held as a part of e-Society Project, supported by Ministry of Education, Culture, Sports, Science and Technology (MEXT), Japan. The aim of this project is to enable the industry to produce highly reliable and advanced software by introducing latest software technologies into embedded software development. In this paper, we introduce the overview of the projects and our activities and results so far.