计算机与现代化

• 算法分析与设计 • 上一篇    下一篇

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

  

  1. (1.贵州大学计算机科学与技术学院,贵州贵阳550025;
    2.贵州省先进计算与医疗信息服务工程实验室,贵州贵阳550025)
  • 收稿日期:2018-03-13 出版日期:2018-07-05 发布日期:2018-07-05
  • 作者简介:季朋(1992-),男,山西朔州人,贵州大学计算机科学与技术学院、贵州省先进计算与医疗信息服务工程实验室硕士研究生,研究方向:大规模数据管理与分析;李晖(1982-),男,教授,硕士生导师,研究方向:大规模数据管理与分析;陈梅(1964-),女,教授,硕士生导师,研究方向:大规模数据管理与分析;戴震宇(1985-),男,实验师,硕士,研究方向:大规模数据管理与分析。
  • 基金资助:
    国家自然科学基金资助项目(61462012,61562010,U1531246);贵州大学研究生创新基金资助项目(2017081);贵州省数据分析与云服务创新团队项目([2015]53);贵州省科技厅科技计划项目(LH[2016]7427)

DoFFT:AFastFourierTransformMethodBasedonDistributedDatabase

  1. (1.CollegeofComputerScienceandTechnology,GuizhouUniversity,Guiyang550025,China;
    2.GuizhouEngineeringLabforACMIS,Guiyang550025,China)
  • Received:2018-03-13 Online:2018-07-05 Published:2018-07-05

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

关键词: 分布式数据库, 快速傅里叶变换, 并行, 数据分布, 代价模型

Abstract: FastFouriertransformhasawiderangeofapplicationsinastronomy.Forexample,pulsarsignalsoftenrequirecoherentdeclerprocessingbasedonfastFouriertransforms.Asthesignaldataisusuallystoredinthedatabase,andexecutingfastFouriertransformalgorithmoutsideofdatabaseaftergettingdatafromthedatabasewillhavealotofI/Oandnetworkoverheadandthusseriouslyaffecttheoverallperformance.Tosolvethisproblem,thispaperdesignsaDoFFT(DatabaseoptimizedFFT)algorithmwhichcanexecuteandoptimizefastFouriertransformsinparallelintheformofuser-definedfunctions(UDF).Inaddition,differentloadofeachnodeinthedatabaseclusterandunevendistributionofdatamaysometimesleadtoinefficientimplementation,DoFFTmethodbasedontheCPU,I/O,networkandtransmissionrates,andothercosts,redistributesdatatofurtheroptimizetheparallelexecutionoffastFouriertransform.TheexperimentalresultsshowthattheperformanceofDoFFTalgorithmisimprovedeffectivelywiththeoptimizationbasedondataredistribution.

Key words: distributeddatabase, fastFouriertransform, parallel, datadistribution, costmodel

中图分类号: