DoFFT:AFastFourierTransformMethodBasedonDistributedDatabase

doi:10.3969/j.issn.1006-2475.2018.06.005

Abstract

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

CLC Number:

TP311.13

JIPeng1,2,LIHui1,2,CHENMei1,2,DAIZhen-yu1,2. DoFFT:AFastFourierTransformMethodBasedonDistributedDatabase[J]. Computer and Modernization, 2018, 0(06): 19-.

References

［1］CochranW,CooleyJ,FavinD,etal.WhatisthefastFouriertransform?［J］.ProceedingsoftheIEEE,1967,15(10):1664-1674.
［2］刘东亮,DemorestP,南仁东.基于CUDA的相干消色散算法实现与测试［J］.科学技术与工程,2010,10(8):1947-1950.
［3］徐永华,李纪云,张颖倩,等.相干消色散脉冲星观测系统的研究［J］.天文研究与技术,2015,12(4):480-486.
［4］CarageaGC,GarciaalvaradoC,PetropoulosM,etal.Totaloperatorstaterecall—Cost-effectivereuseofresultsinGreenplumDatabase［C］//IEEEInternationalConferenceonDataEngineeringWorkshops.2013:44-49.
［5］AntovaL,El-HelwA,SolimanMA,etal.OptimizingqueriesoverpartitionedtablesinMPPsystems［C］//Proceedingsof2014ACMSIGMODInternationalConferenceonManagementofData.2014:373-384.
［6］丁顺英.基于并行结构的FFT算法的软硬件设计与实现［D］.哈尔滨:哈尔滨工业大学,2012.
［7］ChengLong,LiTao.Efficientdataredistributiontospeedupbigdataanalyticsinlargesystems［C］//IEEEInternationalConferenceonHighPerformanceComputing.2017:91-100.
［8］PolychroniouO,SenR,RossKA.Trackjoin:Distributedjoinswithminimalnetworktraffic［C］//Proceedingsof2014ACMSIGMODInternationalConferenceonManagementofData.20141483-1494.
［9］zsuMT,ValduriezP.Distributeddatabasesystems:Wherearewenow?［J］.Computer,2002,24(8):68-78.
［10］RothnieJB,GoodmanN.Asurveyofresearchanddevelopmentindistributeddatabasemanagement［C］//InternationalConferenceonVeryLargeDataBases.1977:48-62.
［11］〖ZK(＃〗YuCT,ChangCC.Distributedqueryprocessing［J］.ACMComputingSurveys,1989,16(4):399-433.
［12］DewittDJ,GrayJ.Paralleldatabasesystems:Thefutureofdatabaseprocessingorapassingfad?［J］.ACMSigmodRecord,1990,19(4):104-112.
［13］Garcia-AlvaradoC,RaghavanV,NarayananS,etal.AutomaticdataplacementinMPPdatabases［C］//IEEEInternationalConferenceonDataEngineeringWorkshops.2012:322-327.
［14］ShenYuxia.DistributedstoragesystemmodeldesigninInternetofthingsbasedonhashdistribution［J］.InternationalJournalofSecurity&Networks,2017,12(3):141..
［15］CurinoC,JonesEPC,MaddenS,etal.Workload-awaredatabasemonitoringandconsolidation［C］//ACMSIGMODInternationalConferenceonManagementofData.2011:313-324.
［16］GroeP,MayN,LehnerW.AStudyofPartitioningandParallelUDFExecutionwiththeSAPHANADatabase［EB/OL］.https://www.researchgate.net/publication/266660040_A_study_of_partitioning_and_parallel_UDF_execution_with_the_SAP_HANA_database,2018-03-13.
［17］TaboadaJM,AraujoMG,BasteiroFO,etal.MLFMA-FFTparallelalgorithmforthesolutionofextremelylargeproblemsinelectromagnetics［J］.ProgressinElectromagneticsResearch.2010,101(2):350-363.
［18］ChuE,GeorgeA.FFTalgorithmsandtheiradaptationtoparallelprocessing［J］.LinearAlgebra&ItsApplications,1998,284(1):95-124.

[1]	ZHANG Hao-yang, YIN Zi-ming, LE Jun-yi, SHEN Da-cong, SHU Yi-jun, YANG Zi-yi, . 3D-SPRNet: Segmentation Model of Gallbladder Cancer Based on Parallel Decoder and Double Attention Mechanism [J]. Computer and Modernization, 2023, 0(12): 59-66.
[2]	WANG Xin, WU Jun-hui, . FPGA-based Interactive Control System for Molecular Dynamics Simulation [J]. Computer and Modernization, 2022, 0(09): 25-31.
[3]	WANG Zhe, WANG Long-da, LIU GANG, WANG Xing-cheng, WANG Zhong-jun, BAO Lu-jie. Improved Immune Particle Swarm Optimization Algorithm for Automatic Parallel Parking Based on Cubic Spline Interpolation#br# [J]. Computer and Modernization, 2022, 0(02): 7-12.
[4]	GUO Cheng, ZHANG Wan-da, WANG Bo, WANG Jia-fu. Particle Swarm Optimization Algorithm Based on Multigroup Parallel Cooperation [J]. Computer and Modernization, 2022, 0(01): 33-40.
[5]	WANG Hao-chang, SUN Meng-ran, ZHAO Tie-jun. Low-resource Neural Machine Translation Based on ELMO [J]. Computer and Modernization, 2021, 0(07): 38-42.
[6]	DENG Bin-tao, XU Sheng-chao. A Differential Evolution K-mediods Clustering Algorithm Based on Dynamic Gemini Population [J]. Computer and Modernization, 2021, 0(07): 54-59.
[7]	GE Bin, CHEN Gang, FANG Rui, LIAO Zhong-zhi. A Novel Hyper Chaotic Image Encryption Algorithm Using Four Directional Diffusion Based on Matrix [J]. Computer and Modernization, 2021, 0(06): 113-119.
[8]	HAN Can-can, LI Zhi-hua, XU Rui. Method of Nonparallel Speech Denoising Based on CycleGAN [J]. Computer and Modernization, 2021, 0(02): 73-77.
[9]	ZHENG Tao, LIU Meng-chi, FENG Jia-mei. RDF Stream Data Query Based on Apache Flink [J]. Computer and Modernization, 2020, 0(11): 47-55.
[10]	ZHAO Qian-wen. JPS Jump Parallel Vertex Sampling Method Based on Online Social Network [J]. Computer and Modernization, 2020, 0(07): 55-60.
[11]	TANG Zhi-bin1,2， ZENG Xue-wen1,2， CHEN Xiao1,2 . Multi-core Parallelism Packet Classification Algorithm Based on Dimensions Decomposition [J]. Computer and Modernization, 2020, 0(02): 1-.
[12]	XIANG Wu-ming, LI Xue-wei. A CUDA-based Cascade Pumping Station Scheduling Algorithm [J]. Computer and Modernization, 2018, 0(11): 60-.
[13]	LI Han1, HU Ming-xiao2, GONG Zhi-hong3, FAN Bing-jun3. Massive Spatial Data Parallel Processing Technology for Vector Tiles [J]. Computer and Modernization, 2018, 0(09): 32-.
[14]	LIHang，ZANGLie，GANLu. ApplicationofLoadBalancingTechnologyinParallelSymbolExecution [J]. Computer and Modernization, 2018, 0(07): 86-.
[15]	ZHAO Bo-ying， XIAO Peng， ZHANG Li. Hybrid Programming of MPI and OpenMP Based on Docker [J]. Computer and Modernization, 2018, 0(05): 60-.