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 sizeN₁ ×N₂. The first is a linear array ofN₁ +N₂ – 1 processors and takesO(N₁N₂) steps. The second is anN₁ ×N₂ rectangular array of processors and takesO(N₁ +N₂) steps, and the third is a hexagonal array which usesN₁N₂ + (N₂ – 1)(N₁ +N₂ – 1) processors andO(N₁ +N₂) 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.