2.1 FFT并行计算
移动健康监护系统、智能生命支持设备在当前得到广泛运用,分析处理实时生命信号是其中的关键技术,直接影响设备仪器的准确性与生物一致性。快速傅立叶变换(FFT)作为数字信号处理的基本工具,在处理速度和功耗方面有着越来越严格的要求。目前并行FFT算法是在分层迭代运算的基础上,通过流水线并行技术或者多线程技术优化实现的。文献[27]通过运用多核多级存储特性,合理划分数据,采取子序列FFT计算和多线程并行逐对计算FFT相结合的方法,提出基数为二的多核多线程并行计算FFT非递归算法。文献[28]提出了一种复数并行FFT实现方法:首先通过局部串行方式完成低阶部分,然后交换低阶部分结果后并行执行高阶部分。通过流水气泡消除技术和数据块重排技术,从而提升了算法实现性能并降低了片上存储需求。这些算法尽管从多线程技术或者硬件技术使一些问题得到优化,但没有改变并行FFT算法分层迭代的基本性质,因此不能取得显著效果。FFT算法是对实时数字信号进行快速分析处理的一个基本方法。文献[29]提出了基于PFFT的以计算为导向的并行FFT(COPF)算法。COPF的数据流方向对应于FFT蝴蝶的拓扑结构,COPF将经典算法中基本蝴蝶结的双处理器合并为一体,减少了每个处理器的通信和平衡工作负载。测试结果表明,COPF比传统的并行FFT更为有效。文献[30]提出用于编码结构化LDPC码的新方法,即基于FFT的并行编码算法,其使用FFT在频域中实现循环卷积。该研究表明,该算法具有比先前提出的编码算法更低的计算复杂度。虽然转换到频域需要在时域中增加一些复杂操作来增加量化点的数量,但由于并行度的增加,编码器的吞吐量大大提高。(https://www.daowen.com)
本书研究运用FFT实现并行卷积运算[16],在传统FFT算法的基础上提出一种新的多项式直接代入FFT算法。针对多核嵌入式实时环境下并行FFT算法进行了研究,以有效提高实时信号处理的速度,提出了一种新的多项式直接代入FFT算法,充分利用多项式奇偶项的不同特点,直接代入数据计算,免去了层层迭代的计算过程,减少了运算过程中的通信,提高了并行性能。对该算法思想,本书在理论进行了严密论证,通过在嵌入式实时平台上运行测试和仿真实验,证实了在数据分段较短的约束条件下,该多项式静态算法较经典的FFT并行算法,在时间复杂度上有一定优势。作者在研究基础上得出结论:多项式直接代入FFT算法能够有效提高并行FFT算法运行速度。