Systolic arrays for multidimensional discrete transforms

An active area of research in supercomputing is concerned with mapping certain finite sums, such as discrete Fourier transforms, onto arrays of processors. This paper presents systolic mapping techniques that exploit the parallelism inherent in discrete Fourier transforms. It is established that, for anM-dimensional signal, parallel executions of such transforms are closely related to mappings of an (M + 1)-dimensional finite vector space into itself. Three examples of such parallel schemes are then described for the discrete Fourier transform of a two-dimensional finite extent sequence of sizeN1 ×N2. The first is a linear array ofN1 +N2 - 1 processors and takesO(N1N2) steps. The second is anN1 ×N2 rectangular array of processors and takesO(N1 +N2) steps, and the third is a hexagonal array which usesN1N2 + (N2 - 1)(N1 +N2 - 1) processors andO(N1 +N2) steps. All three mappings are optimal in that they achieve asymptotically the highest speedup possible over the sequential execution of the same transform, and can easily be generalized to higher dimensions.