基于多核结构的six-step fft算法的研究和实现

《基于多核结构的six-step fft算法的研究和实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文基于多核结构的SIX-STEPFFT算法的研究和实现RESEARCHANDIMPLEMENTOFSIX-STEPFFTALGORITHMBASEDONMULTI-CORESTRUCTURE李伟哈尔滨工业大学2016年6月国内图书分类号：TP399学校代码：10213国际图书分类号：621.791密级：公开工程硕士学位论文基于多核结构的SIX-STEPFFT算法的研究和实现硕士研究生：李伟冒号导师：王玲教授左侧用黑体4号字,冒号申请学位：工学硕士右侧用宋体4号字，多学科：计算机技术倍行距1.5。所在单位：计算机科学与

2、技术学院答辩日期：2016年6月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP399U.D.C:621.791DissertationfortheMasterDegreeinEngineeringRESEARCHANDIMPLEMENTOFSIX-STEPFFTALGORITHMBASEDONMULTI-CORESTRUCTURECandidate：LiWeiSupervisor：Prof.LingWangAcademicDegreeAppliedfor：MasterofEngineeringSpeciali

3、ty：ComputerTechnologyAffiliation：ComputerScience&TechnologyDateofDefence：June,2016Degree-Conferring-Institution：HarbinInstituteofTechnology哈尔滨工业大学工学硕士学位论文摘要在许多科学研究、技术应用领域以及其他相关场合，傅里叶变换常常用于上述问题的简化和求解。傅里叶分析是信号分析的最基本方法，而离散傅里叶变换是傅里叶分析的核心，离散傅里叶变换在数字信号处理、图片处理以及许多科学技术领域都有着

4、广泛的应用。但其具有计算量大，时间复杂度高等缺点，这就极大地限制了傅里叶变换在实际中的应用、难以实时地处理问题，因此引出了快速傅里叶变换(FFT)这一概念。快速傅里叶变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换天然的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进而获得的。对于大量的输入数据N，快速傅里叶变换时间复杂度仍然很高，随着多核CPU技术的日益普及，基于多核的并行计算的研究深入，使得基于多核模型的并行FFT计算成为可能。可根据FFT算法自身的并行性，灵活地分解蝶形运算，通过对探究任务数据的分配和嵌套关系对算

5、法加以优化，合理地分配线程实现多核CPU的并行执行，极大地提高了FFT的计算效率，所以，多核并行系统常被应用于加速快速傅里叶变换的计算。随后许多专家和学者围绕着FFT算法进行研究，并提出了多种FFT算法的优化方案，其中一种叫Six-stepFFT的算法得到了普遍的关注，它的出现较之前的FFT算法大大地降低了所需的硬件成本。六步快速傅里叶变换对一般FFT算法的时间复杂度并没有提升，或者说并没有在数学领域有新的突破，但确根据计算机结构的特性、提出一种改进的任务分解方式，以及任务映射方案。但是Six-stepFFT算法原有的任务映射

6、方案却没有发挥出FFT算法内在的并行性。本文针对基于并行结构FFT算法和Six-stepFFT算法进行分析和总结。在Six-stepFFT算法之上提出一种改进的映射方案，并在多核处理器结构上进行了实施和大量数据分析。关键词：快速傅里叶变换；任务映射；多核系统-I-哈尔滨工业大学工学硕士学位论文AbstractInmanyscientificresearch,technologicalapplications,andotherrelatedapplications,Fouriertransformisoftenusedtosim

7、plifyandsolvetheaboveproblems.Fourieranalysisisthemostbasicmethodofsignalanalysis,whichisthecoreofthediscreteFouriertransformFourieranalysis,discreteFouriertransformindigitalsignalprocessing,imageprocessing,andmanyscientificandtechnicalfieldshaveawiderangeofapplicat

8、ions.Buthavingalargeamountofcalculationtimehighcomplexityandothershortcomings,whichgreatlylimitstheFouriertransformofthepracticalapplicati