题目：基于GPU并行计算的FFT扩频捕获算法研究与实现

图形处理单元（GPU）除了完成传统的图像处理工作外，越来越多地被用到一些通用处理领域。与CPU不同，GPU拥有数量庞大的高度并行工作的处理内核，所以非常适合处理具有并行特点的任务。在CPU-GPU异构平台上，对任务分工，让具有并行特点的部分在GPU上处理，而将其它部分在CPU上处理，这对于发挥GPU资源，减轻CPU负载，提高任务处理性能，有着重要意义。FFT算法本身具有高度的分治特性，非常适合于并行处理，当数据规模较大时，可有效提高计算效率。基于FFT的扩频捕获算法对时效性和灵活性要求较高，更加适合于采用并行计算实现。

本论文首先研究和改进FFT算法，并在CPU上串行实现；然后研究FFT算法并行特点，制定并优化基于GPU实现的并行计算方案，并采用两大主流并行计算模型CUDA和OpenCL实现；最后将基于GPU并行计算实现的FFT算法应用到基于FFT的扩频捕获算法之中。

本论文采用基-4 DIT-FFT算法，分析并验证其优势；阐明该FFT算法倒位序优化的串并行算法；将该FFT算法内所有同址蝶形单元用数据间距，旋转因子组别和组内位置三个独立的变量唯一表示，并以此三个独立变量为变化因子，通过三层迭代实现FFT串行算法，通过与蝶形运算级数和GPU线程ID唯一对应实现FFT并行算法。

对于该FFT算法的GPU并行实现，本文从FFT算法蝶形运算不同级串行，同级所有蝶形可并行的基本特点出发，深入研究GPU并行执行单元调度机制，存储空间带宽特点，内置指令优化等，制定出详细且高效的FFT算法GPU并行实现方案。并以此方案分别采用CUDA和OpenCL实现并行FFT算法和FFT扩频捕获算法。