Two-dimensional convolution on a pyramid computer |
| |
Authors: | Chang JH Ibarra OH Pong T-C Sohn SM |
| |
Affiliation: | Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN; |
| |
Abstract: | An algorithm for convolving a k×k window of weighting coefficients with an n×n image matrix on a pyramid computer of O(n2) processors in time O(logn+k2), excluding the time to load the image matrix, is presented. If k=Ω (√log n), which is typical in practice, the algorithm has a processor-time product O(n 2 k2) which is optimal with respect to the usual sequential algorithm. A feature of the algorithm is that the mechanism for controlling the transmission and distribution of data in each processor is finite state, independent of the values of n and k. Thus, for convolving two {0, 1}-valued matrices using Boolean operations rather than the typical sum and product operations, the processors of the pyramid computer are finite-state |
| |
Keywords: | |
|
|