DoFFT:一种基于分布式数据库的快速傅里叶变换方法

DoFFT: A Fast Fourier Transform Method Based on Distributed Database

快速傅里叶变换在天文学中有着广泛的应用。例如,脉冲星信号通常需要基于快速傅里叶变换进行相干消色散处理。由于信号数据通常存储在数据库中,而将数据从数据库取出后再由外部程序进行快速傅里叶变换处理将产生大量I/O和网络开销进而严重影响整体处理性能。针对此问题,本文设计一种用户自定义函数(UDF)形式的可在分布式数据库中并行执行和优化快速傅里叶变换的算法DoFFT(Database optimized FFT)。此外,针对数据库集群中每台机器负载不同、数据分布不均匀等有时会导致执行效率低下的问题,DoFFT方法基于CPU、I/O,网络与传输速率等的代价,对涉及的数据进行数据重分布处理,以进一步优化快速傅里叶变换的并行执行。实验结果表明,采用基于数据重分布的优化后,DoFFT算法的性能得到了有效提升。

Fast Fourier transform has a wide range of applications in astronomy. For example,pulsar signals often require coherent decler processing based on fast Fourier transforms. As the signal data is usually stored in the database,and executing fast Fourier transform algorithm outside of database after getting data from the database will have a lot of I/O and network overhead and thus seriously affect the overall performance. To solve this problem,this paper designs a DoFFT（Database optimized FFT）algorithm which can execute and optimize fast Fourier transforms in parallel in the form of user-defined functions（UDF）. In addition,different load of each node in the database cluster and uneven distribution of data may sometimes lead to inefficient implementation,DoFFT method based on the CPU,I/O,network and transmission rates,and other costs,redistributes data to further optimize the parallel execution of fast Fourier transform. The experimental results show that the performance of DoFFT algorithm is improved effectively with the optimization based on data redistribution.