Convolution on mesh connected multicomputers |
| |
Authors: | Ranka S. Sahni S. |
| |
Affiliation: | Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN; |
| |
Abstract: | An efficient parallel algorithm is presented for convolution on a mesh-connected computer with wraparound. The algorithm does not require a broadcast feature for data values, as assumed by previously proposed algorithms. As a result, the algorithm is applicable to both SIMD and MIMD meshes. For an N×N image and a M×M template, the previous algorithms take O (M2q) time on an N×N mesh-connected multicomputer (q is the number of bits in each entry of the convolution matrix). The algorithms have complexity O(M2r), where r=max {number of bits in an image entry, number of bits in a template entry}. In addition to not requiring a broadcast capability, these algorithms are faster for binary images |
| |
Keywords: | |
|
|