Performing out-of-core FFTs on parallel disk syste

DartmouthCollegeComputerScienceTechnicalReportPCS-TR96-294(RevisedAugust1997)PerformingOut-of-CoreFFTsonParallelDiskSystemsThomasH.CormenDavidM.NicolyDartmouthCollegeDepartmentofComputerScienceAbstractTheFastFourierTransform(FFT)playsakeyroleinmanyareasofcomputationalscienceandengineering.Althoughmostone-dimensionalFFTproblemscanbeentirelysolvedentirelyinmainmemory,someimportantclassesofapplicationsrequireout-of-coretechniques.Forthese,useofparallelI/Osystemscanimproveperformanceconsiderably.Thispapershowshowtoperformone-dimensionalFFTsusingaparalleldisksystemwithindependentdiskaccesses.Wepresentbothanalyticalandexperimentalresultsforperformingout-of-coreFFTsintwoways:usingtraditionalvirtualmemorywithdemandpaging,andusingaprovablyasymptoticallyoptimalalgorithmfortheParallelDiskModel(PDM)ofVitterandShriver.WhenrunonaDEC2100serverwithalargememoryandeightparalleldisks,theoptimalalgorithmforthePDMrunsupto144.7timesfasterthanin-coremethodsunderdemandpaging.Moreover,evenincludingI/Ocosts,thenormalizedtimesfortheoptimalPDMalgorithmarecompetitive,orbetterthan,thoseforin-coremethodsevenwhentheyrunentirelyinmemory.1IntroductionFourieranalysisplaysapivotalroleinmanybranchesofscienceandengineering.TheFouriertransform’sinputisanN-vectorofcomplexnumbers,representingsomediscretizedfunction.TheFourierrepresentationofthisfunctionisasumofNweightedsineandcosinefunctionswithspecicfrequencies.Computingthecoecientsoftheconstituentfunctionsyieldsagreatdealofinformationaboutthefunction.Well-knownFastFourierTransform(FFT)techniquesaccomplishthecomputationin(NlgN)operations.SincethemoderndiscoveryoftheFFTbyCooleyandTukeyin1965[CT65],aprofusionofFFTmethodshavebeendeveloped,primarilytooptimizeitfordierenttypesofcomputerarchitecturessuchasvectorandparallelmachines(e.g.,seeVanLoan[Van92]).TheworkwepresenthereSupportedinpartbyfundsfromDartmouthCollegeandinpartbytheNationalScienceFoundationundergrantsCCR-9308667andCCR-9625894.yThisresearchwassupportedinpartbyNSFgrantsCCR-9201195andNCR-9527163,anditwasalsosupportedinpartbyNASAContractNAS1-19480totheInstituteforComputerApplicationsinScienceandEngineering.1continuesinthatvein,lookingatwaysoforganizinganFFTcomputationtotakeadvantageofparallelI/Osystems.Ofcourse,suchanendeavorisusefulonlyiftheinputvectoristoolargetotinthemainmemoryofacomputer;inmostusesoftheFFT,theinputvectorwilltincore.Somecriticalapplicationsrequireextremelylargeone-dimensionalFFTs,particularlywhenthesubjectfunctionexhibitscriticalphenomenaatvastlydierenttimescalesandhighresolutionisrequired.Onesuchapplicationisseismicanalysis[Cla85],whereanout-of-coreone-dimensionalFFTisnecessary(aspartofahigherdimensionalFFT)evenwhenthecomputermemoryhas16gigabytesofavailableRAM[Rut96].Anotherapplicationisintheareaofradioastronomy.TheHigh-SpeedDataAcquisitionandVeryLargeFFTsProjectatCaltech1usesFFTstosup-portsearchingforfast(millisecondperiod)pulsars.TheprojectcurrentlyrequiresFFTswith10gigapoints,anditdesiresFFTswithupto64gigapoints.Yetanotherapplicationisforintegermultiplicationofverylargenumbers[CF94],whichisakeycomponentinthemostmodernmethodsofsearchingforMersenneprimenumbers.FFTsareusedinmanywaystomanipulatedatasets,suchasconvolution/deconvolution,correlation/auto-correlation,ltering,andpowerspectrumes-timation[PFTV88].Anytimethedatasetisverylargeandaccuracyisessential,verylargeFFTsarerequired.Thecontributionofthepresentpaperistopresentanout-of-coreFFTalgorithmthatexploitsparallelI/Oandtoassessitsperformance.ThealgorithmisavariantofonethatwassketchedbyVitterandShriver[VS94],andwhichachievesthelowerboundoncomplexityprovenbyAggarwalandVitter[AV88].Inparticular,weshowhowecientout-of-corepermutationroutinescanbeusedthroughouttheFFTcomputation.Weassessperformancebycomparisonwithdemandpaging;weshowanalyticallyandexperimentallythatwell-knownin-coreFFTalgorithmsrunslowlyoncethedatasetsizeexceedsavailablein-corememory.Usingonlyasingle-disksystem,weobservethatourout-of-coremethodrunsover46timesfasterthandemandpaging;witheightdisksweobserveuptotwoordersofmagnitudeimprovementusingourtechnique.Theremainderofthispaperisorganizedasfollows.Section2summarizessomeFFTmethodsforin-corecomputation,andSection3discussespublishedout-of-coreFFTmethodsforsingle-disksystems.Section4demonstrateswhyconventionaldemand-pagedin-coreFFTalgorithmsperformbadlywhentheproblemsizeexceedsthephysicalmemory.InSection5,wedenetheParallelDiskModel(PDM).Section6describesourout-of-corealgorithm.Section7presentsandanalyzesrunningtimesforourFFTimplementationontwodierentDECAlpha-baseduniprocessorsystems.Finally,wesummarizeinSection8.2In-coreFFTsThissectionreviewsFouriertransformsandoutlinessomewell-knownFFTmethodsforin-corecomputation.ForfurtherbackgroundontheFFT,seeanyofthetexts[CLR90,Nus82,Van92].DiscreteFouriertransformsFouriertransformsarebasedoncomplexrootsofunity.TheprincipalNthrootofunityisacomplexnumber!N=e2i=N,wherei=p1.Foranyrealnumberu,eiu=cos(u)+isin(u).Givenavectora=(a0;a1;:::;aN1),whereNisapowerof2,theDiscreteFourierTransform1See