Split and Shift Methodology on Cellular Processor Arrays: Area Saving versus Time Penalty

This paper addresses the so-called split and shift methodology. This methodology deals with the implementation of kernels of sizes that go above the physically implemented resources (local connections and weighting circuits) on synchronous cellular processor arrays (CPA), including the realization of large neighborhood operations and/or the reduction of the available hardware in order to drop the area consumption. Two main goals are pursued in the development of the methodology, namely: (1) minimum penalty at processing time and (2) absolutely no penalty at functional level. The paper presents different techniques and guidelines for the methodology application and introduces a Figure of Merit to evaluate them by relating area gains with time penalty. This, along with a kernel shape analysis, led us to propose more adequate configurations of weighting circuits and to justify the classical choice of North-East-West-South connectivity. To validate the methodology, we realize several estimates over actual physical implementations, and we propose the realization over CPAs of the spin filters, scale invariant feature transform and speeded-up robust features algorithms. A more in-depth trade-off analysis is realized over the implementation of the pixel level snakes algorithm. Copyright © 2012 John Wiley & Sons, Ltd.

keywords: Cellular processor arrays, Cellular non-linear networks, Large neighborhood kernels, Area-time trade-off, Scale Invariant Feature Transform (SIFT), Speeded-Up Robust Features (SURF)