The mapping of two-dimensional array processors to one-dimensional processors (Q1079955)

We consider the case of a two-dimensional wavefront array processor where only one wavefront appears at any time. We show that in such a situation, this two-dimensional wavefront processor can be mapped to a linear array processor if the wavefronts never backtrack. The mapping will not increase the number of registers in each processor element. Two examples, the spoken word recognition problem and the longest common subsequence problem, are given to demonstrate the feasibility of this method.