一种高性能超长点数浮点FFT加速器设计 - 王谛, 石嵩, 吴铁彬, 刘亮, 谭弘兵, 郝子宇, 过锋, 李宏亮.pdf
免费下载
计 算 机 研 究 与 发 展
DOI
:
１０．７５４４∕issn１０００Ｇ１２３９．２０２１．２０２１００６９
JournalofCom
p
uterResearchandDevelo
p
ment ５８
(
６
):
１１９２ １２０３
,
２０２１
收稿日期
:
２０２１
－
０１
－
２０
;
修回日期
:
２０２１
－
０４
－
２３
基金项目
:“
核高基
”
国家科技重大专项基金项目
(
２０１８ZX０１０２８Ｇ１０２
)
Thisworkwassu
pp
ortedb
y
theNationalScienceandTechnolo
gy
Ma
j
orPro
j
ectsofHe
g
ao
j
i
(
２０１８ZX０１０２８Ｇ１０２
)
．
通信作者
:
李宏亮
(
hon
g
lian
g
li＠２６３．net
)
一种高性能超长点数浮点
FFT
加速器设计
王
谛
石
嵩
吴 铁 彬
刘
亮
谭 弘 兵
郝 子 宇
过
锋
李 宏 亮
(
江南计算技术研究所
江苏无锡
２１４０８３
)
(
wan
g
di
_
csarch＠１２６．com
)
A Hi
g
hPerformanceAcceleratorDesi
g
nforUltraＧLon
g
PointFloatin
g
ＧPointFFT
Wan
g
Di
,
ShiSon
g
,
WuTiebin
,
LiuLian
g
,
TanHon
g
bin
g
,
HaoZi
y
u
,
GuoFen
g
,
andLiHon
g
lian
g
(
Jian
g
nanInstituteo
f
Com
p
utin
g
Technolo
gy
,
Wuxi
,
Jian
g
su
２１４０８３
)
Abstract FastFouriertransform
(
FFT
)
p
la
y
sake
y
rolein di
g
italsi
g
nal
p
rocessin
g
．Withthe
increasin
g
demand ofhi
g
h
p
erformance ultraＧlon
g p
ointFFT
,
di
g
italsi
g
nal
p
rocessor
(
DSP
)
is
becomin
g
moreandmoredifficulttomeetthedemand
,
sointe
g
ratedFFTacceleratorshavebecomean
im
p
ortantdevelo
p
menttrend．Inordertosu
pp
ortultraＧlon
gp
ointFFT
,
this
p
a
p
erextendsthetwoＧ
dimensional decom
p
osition al
g
orithm of FFT to multiＧdimensional
,
and we
p
ro
p
ose a hi
g
h
p
erformanceultraＧlon
gp
ointFFTacceleratorarchitecturewhichcanbeinte
g
ratedintoDSP．Inthis
architecture
,
threeＧdimensionaltrans
p
ositiono
p
erationisrealizedb
y
usin
g
collisionＧfreeaddressin
g
methodwith
p
rimenumbermemor
y
banks
;
efficienttwiddlefactor
g
enerationisrealizedb
y
recursive
al
g
orithm
;
FFTo
p
erationcircuitisrefinedb
y
usin
g
sin
g
le
p
recisionfloatin
g
Ｇ
p
ointfuseddot
p
roduct
andfusedaddＧsubtracto
p
eration．Finall
y
,
this
p
a
p
errealizesthesin
g
le
p
recisionfloatin
g
Ｇ
p
ointFFT
calculationwithin４G
p
oints．Thes
y
nthesisresultshowsthatthe
p
ro
p
osedFFTacceleratorcanrunat
afre
q
uenc
y
ofmorethan１GHzandits
p
erformancecanreach６４０Gflo
p
∕s
,
whichhasbeen
g
reatl
y
im
p
rovedintermsof
p
ointsand
p
erformancecom
p
aredwiththeexistin
g
research．
Ke
y
words fast Fouriertransform
(
FFT
);
multiＧdimensionaldecom
p
osition al
g
orithm
;
threeＧ
dimensionaltrans
p
ositiono
p
eration
;
twiddlefactor
g
eneration
;
accelerator
摘
要
快速傅里叶变换
(
fastFouriertransform
,
FFT
)
在数字 信号 处 理中 占 据核 心 地位
．
随着 高 性能
超长点数
FFT
需求的增长
,
数字信号处理器
(
di
g
italsi
g
nal
p
rocessor
,
DSP
)
的计算 能力越 来越难 以满
足需求
,
集成
FFT
加速器成为重要的发展趋势
．
为了支持 超长点 数
FFT
,
将
２
维分解 算法推 广到多 维
,
提出一种可集成于
DSP
的高性能超长 点数
FFT
加速器 结构
．
该结 构 通过 基 于素 数 个存 储 体的 无 冲突
体编址方法实现了
３
维转置运算
;
通过递推算法实现了高效铰链因子生成
;
使用单精度浮点二项融合点
积运算和融合加 减运算
,
对
FFT
运算电路进行了精细化设计
．
实现了对
４G
点数单精度浮点
FFT
计算
的支持
．
综合结果表明
:
FFT
加速器运行频率能够达到
１GHz
以上
,
性能达到
６４０Gflo
p
∕s．
在支持的点数
和性能方面都较已有研究成果取得大幅提升
．
关键词
快速傅里叶变换
;
多维分解算法
;
３
维转置运算
;
铰链因子生成
;
加速器
中图法 分类号
TP３３２
离 散 傅 里 叶 变 换
(
discreteFouriertransform
,
DFT
)
作为时 域和 频域 转换 的 基 本 运 算
,
在 数 字 信
号处理中占据核心地位
[
１
]
,
应用领域十分广泛
．
快速
傅 里 叶 变 换
[
２
]
(
fastFouriertransform
,
FFT
)
是
DFT
的快速算法
,
FFT
的提出促进了数字信号处理
的发展
,
被评选为
２０
世纪科学和工程界最具影响力
的十大 算 法之 一
[
３
]
．
随着 高 速采 样 和实 时 信号 处 理
技术 的 发展
,
高 性 能 超长 点数
FFT
的 需 求 迅 速 增
长
[
４
]
．
由于
FFT
的 算 法 复杂 度为
O
(
N
l
g
N
),
FFT
和以
FFT
为 基 础 的各 类时 频 变 换 算法 的计 算 占
比愈发凸显
．
例如
,
在国际大科学 工程
———
平方公 里
阵列
(
s
q
uarekilometerarra
y
,
SKA
)
射电 望 远镜 项
目中
,
FFT
的计算占比达
４０％
[
５
]
．
目前已有
FFT
计
算架构 的 最 大 吞 吐 率 能 达 到
１００GS∕s
量 级
[
６
]
,
并
且吞吐率需求以指数 级 速度 增 长
,
大概 每
５
年增 长
１０
倍
[
７
]
．
数十年来发展出数字信号处理器
(
di
g
italsi
g
nal
p
rocessor
,
DSP
)、
现场可 编 程 门 阵 列
(
field
p
ro
g
raＧ
mmable
g
atearra
y
,
FPGA
)
和专用集成电路
(
a
pp
liＧ
cations
p
ecificinte
g
ratedcircuit
,
ASIC
)
等 多 种 数
字信号处理平 台
．DSP
具有 强 大的 运 算 能 力 和 良 好
的可编程性
,
在 满 足 性能 需求 的 条 件 下
,
DSP
是 构
建数字信号处 理 系 统 的 首 选 器 件
．
但 受 到 指 令 串 行
执行和处理 器 寻 址 模 式 的 限 制
,
传 统
DSP
的
FFT
运算能力低于
FPGA
和
ASIC
实现
[
８
]
．
“
通用核心
＋
加速器
”
的结构在获得通用处理器
可编程性和灵活性的同时又能提升特定应用的性能
与功耗效率
,
是未来处理器发展的重要方向
．
为了提
高
DSP
的
FFT
处理能力
,
在
DSP
中集成
FFT
加速
器成 为 必 然 选 择
,
已 有 大 量 理 论 研 究
[
９
]
和 实 际 产
品
[
１０
]
出现
．
现有 研究 成果 存在
２
点 不 足
:
１
)
与
DSP
核心相比
,
FFT
加速器的峰 值性能 没有体 现出明 显
优势
;
２
)
对于超长点数
FFT
的支持能力有限
．
本文针对集成于
DSP
的
FFT
加速器开展研 究
工作
．
注 意 到 将
FFT
的
２
维 分 解 算 法 推 广 到 多 维
后
,
可以将每一维 的 点数 控 制在
１６
个点 以 内
,
从而
能 用 固 定 的 小 点 数
FFT
实 现 几 乎 任 意 长 度 的
FFT
,
本文在此基础上提出面向超长点数
FFT
的多
维分解算法
．
针对
FFT
多维分解算法中的 转置和 铰
链因子生成这
２
种核 心 运算 开 展研 究
,
提出 了 素数
体片上
３
维转置存储器结构解决访存带宽利用率低
的问题
,
提出了铰链因 子 递推 生 成算 法 解决 坐 标旋
转数字计算机
(
coordinaterotationaldi
g
italcom
p
uter
,
CORDIC
)
算法 迭 代 计算 周期 长 的 问 题
．
最 后
,
对 每
一维处理中的小点数
FFT
进行了精细化 电路设 计
．
本文设计的
FFT
加 速 器 能够 实现 最长
４G
点 数 的
单精度浮点
FFT
计算
,
运行频率能够达到
１GHz
以
上
,
性能达到
６４０Gflo
p
∕s．
在点数和性能方面都较已
有研究成果取得大幅提升
．
１
相关研究
经过数十年的研究
,
FFT
算法发展了许多种类
．
根据 运 算 形 式 的 不 同 可 以 将
FFT
分 为 时 间 抽 选
(
decimationintime
,
DIT
)
和频 率 抽选
(
decimation
infre
q
uenc
y
,
DIF
)
．
根据 基本 蝶 形运 算 单元 的 粒度
则可以将
FFT
分为基
２
、
基
４
、
基
８
、
基
１６
、
多基和素
数基等
．
与此 同 时
,
大 量 的 流 水 化 和 并行 化
FFT
实
现结构也被提出
,
例如阵列并行结构
、
单路延时置换
(
sin
g
leＧ
p
athdela
y
commutator
,
SDC
)
结构
、
单路延
时反馈
(
sin
g
leＧ
p
athdela
y
feedback
,
SDF
)
结 构
、
多
路延时 置换
(
multiＧ
p
athdela
y
commutator
,
MDC
)
结 构 和 多 通 路 延 时 反 馈
(
multiＧ
p
ath dela
y
feedback
,
MDF
)
结构等
[
９
]
．
许多研究针 对 基 本 运 算 单 元 进 行 精 细 化 设 计
．
例如
,
采用基
２
２
算法
[
１
]
,
对偶序号使用基
２
算法
,
对
奇序号使用基
４
算法
,
减少运算量
;
采用不同实现方
式的 乘 法 器
[
１１
]
获 得 较 小 的 开 销
;
以
CORDIC
算 法
为基础
,
将复数乘法与 旋 转因 子 求值 统 一到 一 个迭
代运算中
[
１２
]
,
减 少 蝶 形 运 算 复 杂 度
;
通 过 运 算过 程
中的动态位 宽 调 整
[
１３
]
,
减 少 资 源 开 销 和功 耗
;
采 用
二项融合点 积
(
fuseddot
p
roduct
,
FDP
)
运 算 和 融
合加 减
(
fusedaddＧsubtract
,
FAS
)
运算
[
１４
]
,
实现高
效的浮点复数运算
．
这些研究在小点数
FFT
计算中
普遍取得明显 的优 势
,
然而
,
提升 长 点 数
FFT
计 算
效率需要超出基本运算单元的范畴进行考虑
．
对于长点数
FFT
,
计算 的中间 结果无 法全部 存
储 在 芯 片 内 部
．Wino
g
rad
傅 里 叶 变 换 算 法
[
１５
]
(
Wino
g
radFouriertransform al
g
orithm
,
WFTA
)
利用旋转因子特性对
FFT
进行分解
,
使用规模较小
的
２
维
FFT
模 拟 实 现 规 模 较 大 的 一 维
FFT
,
是 一
种高效且资源占用相对较少的
FFT
实现方 法
．
在处
理器
[
１６Ｇ１７
]
和
FPGA
[
４
,
１８
]
上 对 长 点 数
FFT
的 实 现 普
遍采用了这种
２
维分解算法
．
长点数
FFT
加速 器 的研 究 大 多 在
２
维 分 解 算
法基础上进 行 改 进
．Yan
g
等 人
[
１９
]
采 用 一 种 支 持 基
２
、
基
４
、
基
８
、
基
１６
可重构运算单元
,
实现
FFT
运算
中 蝶 形 运 算 单 元 的 灵 活 配 置
,
达 到 最 佳 的 能 效
．
３９１１
王
谛等
:
一种高性能超长点数浮点
FFT
加速器设计
of 12
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论