钟旭阳 ，徐 云

（1.中国科学技术大学 计算机科学与技术学院，安徽 合肥230026；2.安徽省高性能计算重点实验室，安徽 合肥230026）

0 引言

快速傅里叶变换（Fast Fourier Transform，FFT）是实现离散傅里叶变换及其逆变换的算法。FFT使用分而治之的主要思想，其主要目的是将一个复杂的大问题分解成多个简单的小问题，然后分别解决这些小问题[1]。FFT在科学计算领域具有极其重要的地位[2]。利用FFT能够在计算离散傅里叶变换时大大减少所需要的乘法次数，并且FFT点数规模越大，FFT算法所能够节省的计算量就越显著，因此FFT广泛应用于数据信号处理、地震预报、石油勘探等领域。

已有的FFT分布式计算方法大多基于MapReduce批处理系统[1，3-5]，其中 FFT计算作为一个整体，在某一个转换操作中直接计算来自上一个操作的整个输出数据，忽视了FFT计算特性的同时，还需要等待较长时间才能延迟得到处理结果。目前并未有成熟的、基于流粒度的对FFT的流处理分布式算法并行优化相关研究。且现如今Flink分布式流处理框架大都用于社交网络等领域中简单的数据项统计应用，对于FFT此类耗时大、数据量大的科学计算问题并不适用，因此需要对Flink相关的机制进行应用和改造，使得其符合FFT计算的要求。

在Flink流处理框架中设计实现良好的FFT算法并行化流程及优化，不仅可以将FFT计算中的源数据流的特征表现得非常突出，推动了FFT计算在高精度、大宽带和实时性的要求上更进一步；而且为传统科学计算任务在大数据时代背景下，提供了一种基于分布式流处理平台的并行流程新思路。……