二维 DFT 和 DCT 的 Systolic 阵列

超级计算中一个活跃的研究领域是将某些有限和,如离散富里叶变换(DFT)、离散余弦变换(DCT),映射到多处理机阵列上。本文首先通过二维DFT的行列分解算法流程图,给出了计算二维DFT的二种Systolic阵列:一种是由N_1个处理器组成的线性阵列,所花时间步为O(N_1N_2)(设二维DFT为N_1×N_2长的),与行列分解算法在单处理机上顺序执行所花时间相比,加速比为O(N)(设N_1=N_2=N)。这一结果无论是在时间消耗,还是在PE数量上都是目前最优的。另一种是由N_1×N_2个处理器组成的矩形阵列,所需时间为O(N_1+N_2),与行列算法在单处理机上顺序运行所花时间相比,加速比为O(N~2)(这里仍假定N_1=N_2=N)。本文还给出了二维DCT的与二维DFT相似的Systoilc阵列结构。不难将上述阵列推广到多维的情况。

Systolic Arrays for Two Dimensional DFT and DCT

An active area of research in supercomputing is concerned with mapping certain sums, such as discrete Fourier transforms (DFT) and discrete cosine transforms (DCT) to multi-processor arrays. This paper presents two kinds of systolic arrays for 2D-DFT using the flow diagram of row-column de composition algorithm. One is a linear array of N₁ processors (if the DFT is N₁×N₂), and it takes O(N₁N₂)time steps. The speed-up of this array over the sequential implementation of the row-column decomposition algorithm on a single processor is O(N)(IF N₁=N₂=N). This result is currently optimal not only in PE numbers, but a1so in time cost. The other is a rectagular array of N₁×N₂ processors and it takes O(N₁+N₂)steps. The specdup of it over the sequential implementation of the row-cotumn decomposition algorithm on a single processor is O(N²)(IF N= N₁=N₂). At last, the paper gives two systolic arrays of 2D-DCT,which are similar to that of 2D-DFT. Furthermore, these systolic arrays can be easily generalized to multi-dimensional cases.