基于多核结构的SIX-STEP FFT算法的研究和实现

摘要

在许多科学研究、技术应用领域以及其他相关场合，傅里叶变换常常用于上述问题的简化和求解。傅里叶分析是信号分析的最基本方法，而离散傅里叶变换是傅里叶分析的核心，离散傅里叶变换在数字信号处理、图片处理以及许多科学技术领域都有着广泛的应用。但其具有计算量大，时间复杂度高等缺点，这就极大地限制了傅里叶变换在实际中的应用、难以实时地处理问题，因此引出了快速傅里叶变换(FFT)这一概念。
　　快速傅里叶变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换天然的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进而获得的。对于大量的输入数据N，快速傅里叶变换时间复杂度仍然很高，随着多核CPU技术的日益普及，基于多核的并行计算的研究深入，使得基于多核模型的并行FFT计算成为可能。可根据FFT算法自身的并行性，灵活地分解蝶形运算，通过对探究任务数据的分配和嵌套关系对算法加以优化，合理地分配线程实现多核CPU的并行执行，极大地提高了FFT的计算效率，所以，多核并行系统常被应用于加速快速傅里叶变换的计算。
　　随后许多专家和学者围绕着FFT算法进行研究，并提出了多种FFT算法的优化方案，其中一种叫Six-step FFT的算法得到了普遍的关注，它的出现较之前的FFT算法大大地降低了所需的硬件成本。
　　六步快速傅里叶变换对一般FFT算法的时间复杂度并没有提升，或者说并没有在数学领域有新的突破，但确根据计算机结构的特性、提出一种改进的任务分解方式，以及任务映射方案。
　　但是Six-step FFT算法原有的任务映射方案却没有发挥出FFT算法内在的并行性。本文针对基于并行结构FFT算法和Six-step FFT算法进行分析和总结。在Six-step FFT算法之上提出一种改进的映射方案，并在多核处理器结构上进行了实施和大量数据分析。

目录

封面

中文摘要

英文摘要

目录

第1章 绪 论

1.1 课题研究背景

1.1.1傅里叶变换(Fourier Transform)的研究背景

1.1.2六步快速傅里叶变换（Six-step FFT）的研究背景

1.2 多核结构概述

1.2.1 多核处理器特点

1.2.2并行计算机的发展历程

1.2.3 并行计算机系统的体系结构

1.2.4 基于多核结构的并行计算

1.3 多核系统任务映射的研究现状

1.4论文的主要研究内容

1.5论文的创新点

1.6论文的结构

第2章Six-step FFT算法到多核的映射

2.1 引言

2.2 基于并行计算模型的FFT算法

2.2.1 负载平衡下的FFT映射方案

2.2.2 并行模型下的FFT算法线程同步

2.2.3基于并行模型的FFT算法分析

2.3基于并行计算模型的Six-step FFT算法

2.3.1 Six-step FFT算法的定义

2.3.1基于并行模型的six-step FFT映射方案

2.3.2基于并行模型的six-step FFT算法分析

第3章改进的Six-step FFT算法到多核的映射

3.1 引言

3.2改进的映射方案下的Six-step FFT算法

3.3改进方案下Six-step FFT算法的实现

第4章 仿真平台的介绍及映射结果分析

4.1 仿真平台介绍

4.2 仿真平台搭建

4.3Six-step FFT映射算法性能评估分析

4.3.1 两种映射算法的运行速度分析

4.3.2 两种映射算法的功耗分析

结论

参考文献

声明

致谢