面向可重构系统的几个常用算法及其实现技术研究

论文摘要

用硬件实现算法一般可比软件实现快数个数量级,以FPGA为代表的可重构硬件以其速度快、功耗低、编程灵活等优点成为算法硬件加速的首选。随着集成电路技术的发展,FPGA芯片的容量和性能不断提高,其在数字信号处理、计算机技术和科学计算等领域的应用日益广泛。本文以减少计算延迟、优化资源使用、提高吞吐率为目标,基于可重构平台对数字信号处理和科学计算领域使用频率较高的初等函数及其复合函数求值、向量旋转和快速傅利叶变换等算法及其实现方法进行了深入研究,综合了近似算法、表驱动的求值算法、流水线组织与访存调度等优化策略,提出相关创新方法。本文的主要工作包括:1)研究了指数/对数函数的计算方法:对常规CORDIC算法进行压缩,将、通路合而为一,实现了专用求值器,减少了芯片面积开销;提出一个统一的指数/对数函数迭代求值算法,通过设置不同的初值和功能选择信号,仅用、通路便可实现指数或对数函数求值,与CORDIC算法相比可节省1/3以上的面积开销;针对低精度、高速度应用,设计并实现了一个基于近似算法的高速对数变换器,并利用简洁、高效的校正逻辑提高了计算精度。2)研究了基于查找表的函数求值方法,利用二阶minimax多项式对函数逐段逼近,实现了一个高效的多函数查表求值系统。通过合理选择分段策略,兼顾了段地址译码逻辑的复杂性与查找表的存储开销;系数逐一圆整（rounding）、三次逼近减少了系数有限精度引入的方法误差,从而减少了存储开销;采用定/浮点双通路分别计算不同特性的函数,保证了计算精度;预先进行精度控制和中间结果截断,减少了多项式的计算开销;最后合理分配各函数查找表的存储空间,实现了系统集成。3)面向旋转角取值范围广且不可预知以及旋转角数目有限且可预知两类应用,以减少迭代次数和面积开销为目标,提出2S-PCS和FFT CORDIC两种向量旋转算法。充分利用了FPGA片上存储资源,借助查找表辅助计算,在减少了迭代次数的同时保持了常规CORDIC算法扩展因子易于计算和补偿的优点,使其相对乘/加方法更具优势。采用28位数据通路时,与常规CORDIC算法相比,2S-PCS算法的流水线级数约减少38%,面积约减少27.9%,精度提高3位（2进制）左右,显示了算法的优良性能。最后面向两类特殊FFT应用对CORDIC算法进行了优化。4)以基2时分FFT算法为基础,针对浮点FFT处理器中的写后读数据相关,提出几种减少相关的方法,并通过改进运算蝶结构、合理调度FPGA片上RAM访问,设计并实现了一个高吞吐率FFT处理器,每周期可读取两个复操作数,输出两个复计算结果,吞吐率为传统FFT处理器的2倍。此外,还面向点数不固定的应用,设计并实现了一个运算蝶级联的可变长FFT处理器。本文所研究的算法实现方法具有通用性,不仅适用于可重构平台,略作调整也适用于ASIC设计。由于算法粒度较小,更适合与其他操作结合实现更大规模的应用。若对这些算法单独进行硬件加速,则要考虑数据输入/输出等额外开销对性能加速的影响。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景
• 1.1.1 可重构硬件
• 1.1.2 可重构系统
• 1.1.3 可重构硬件加速的难点
• 1.2 选题与研究现状
• 1.2.1 复杂函数求值
• 1.2.2 向量旋转
• 1.2.3 快速傅利叶变换
• 1.3 课题研究内容
• 1.4 论文组织结构
• 第二章 CORDIC 算法原理
• 2.1 旋转模式
• 2.2 定向模式
• 2.3 CORDIC 算法的统一
• 2.4 CORDIC 算法的实现
• 2.5 CORDIC 算法的扩展与优化
• 2.6 本章小结
• 第三章 指数/对数函数求值方法
• 3.1 基于 CORDIC 算法的 专用求值器
• 3.2 统一的指数/对数函数求值算法LnE
• 3.2.1 LnE 指数函数求值算法
• 3.2.2 LnE 对数函数求值算法
• 3.2.3 LnE 算法的区间压缩方法
• 3.2.4 LnE 算法的实现
• 3.3 底2 对数函数高速求值器
• 3.3.1 并行打头“1”检测电路
• 3.3.2 六域误差校正算法的改进
• 3.3.3 误差校正算法精度模拟
• 3.3.4 校正算法的硬件实现
• 3.4 本章小结
• 第四章 基于查找表的复杂函数求值方法
• 4.1 基于查找表的多项式逼近原理
• 4.1.1 区间压缩方法
• 4.1.2 分段与段地址译码方法
• 4.1.3 逐段多项式逼近
• 4.2 一种高效的表驱动的函数求值方法
• 4.2.1 分段方法
• 4.2.2 最佳逼近多项式系数的计算
• 4.2.3 系统参数的确定
• 4.2.4 P25R 函数求值器系统结构
• 4.2.5 多函数集成
• 4.2.6 精度控制与实验仿真
• 4.2.7 系统扩展
• 4.3 本章小结
• 第五章 基于CORDIC 的向量旋转算法
• 5.1 向量旋转操作的两类实现方法
• 5.2 基于CORDIC 的向量旋转算法及其分类
• 5.3 扩展因子预编码的两阶段CORDIC 旋转算法25-PCS
• 5.3.1 SF（Scaling-free CORDIC）算法
• 5.3.2 迭代系数与扩展因子预编码
• 5.3.3 系统结构与流水线划分
• 5.3.4 性能分析与误差模拟
• 5.4 面向FFT 应用的向量旋转算法FFT CORDIC
• 5.4.1 FFT 向量旋转操作描述
• 5.4.2 FFT CORDIC 算法
• 5.5 面向两类特殊FFT 应用的CORDIC 改进算法
• 5.5.1 常规CORDIC 算法迭代周期压缩方法
• 5.5.2 无查找表的FFT CORDIC 算法
• 5.6 本章小结
• 第六章 快速傅里叶变换FFT
• 6.1 基于可编程器件的FFT 处理器现状
• 6.2 离散傅里叶变换及其快速算法原理
• 6.2.1 离散傅里叶变换DFT 及其逆变换IDFT
• 6.2.2 快速傅里叶变换FFT
• 6.3 FFT 运算蝶的硬件实现方法
• 6.3.1 基于CORDIC 实现向量旋转
• 6.3.2 CORDIC 算法的扩展
• 6.3.3 基于CORDIC 算法的基-2 运算蝶的实现
• 6.4 FFT 处理器实现方法对比
• 6.5 可变长FFT 处理器
• 6.5.1 可变长FFT 算法原理
• 6.5.2 可变长FFT 处理器结构
• 6.5.3 可变长FFT 处理器的控制逻辑
• 6.5.4 实验模拟与分析
• 6.6 浮点FFT 实现方法研究
• 6.6.1 FFT 处理器中的RAW 相关
• 6.6.2 高吞吐率浮点FFT 处理器的设计
• 6.7 基于FPGA 的双精度浮点FFT 发展现状
• 6.8 本章小结
• 第七章 结束语
• 7.1 本文研究工作总结
• 7.2 研究展望
• 参考文献
• 致谢
• 作者在学期间取得的学术成果