2025-11-20T07:07:14.857348

Adaptive Hybrid FFT: A Novel Pipeline and Memory-Based Architecture for Radix-$2^k$ FFT in Large Size Processing

Zhao, Xiao, Wang et al.

In the field of digital signal processing, the fast Fourier transform (FFT) is a fundamental algorithm, with its processors being implemented using either the pipelined architecture, well-known for high-throughput applications but weak in hardware utilization, or the memory-based architecture, designed for area-constrained scenarios but failing to meet stringent throughput requirements. Therefore, we propose an adaptive hybrid FFT, which leverages the strengths of both pipelined and memory-based architectures. In this paper, we propose an adaptive hybrid FFT processor that combines the advantages of both architectures, and it has the following features. First, a set of radix-$2^k$ multi-path delay commutators (MDC) units are developed to support high-performance large-size processing. Second, a conflict-free memory access scheme is formulated to ensure a continuous data flow without data contention. Third, We demonstrate the existence of a series of bit-dimension permutations for reordering input data, satisfying the generalized constraints of variable-length, high-radix, and any level of parallelism for wide adaptivity. Furthermore, the proposed FFT processor has been implemented on a field-programmable gate array (FPGA). As a result, the proposed work outperforms conventional memory-based FFT processors by requiring fewer computation cycles. It achieves higher hardware utilization than pipelined FFT architectures, making it suitable for highly demanding applications.

academic

Adaptive Hybrid FFT: A Novel Pipeline and Memory-Based Architecture for Radix- $2^k$ FFT in Large Size Processing

基本信息

论文ID: 2501.01259
标题: Adaptive Hybrid FFT: A Novel Pipeline and Memory-Based Architecture for Radix- $2^k$ FFT in Large Size Processing
作者: Fangyu Zhao, Chunhua Xiao, Zhiguo Wang, Xiaohua Du, Bo Dong
分类: cs.AR (计算机架构)
发表时间/会议: 已提交IEEE，2025年1月
论文链接: https://arxiv.org/abs/2501.01259

摘要

在数字信号处理领域，快速傅里叶变换(FFT)是一个基础算法。其处理器实现通常采用两种架构：流水线架构(适用于高吞吐量应用但硬件利用率低)和基于内存的架构(适用于面积受限场景但无法满足严格的吞吐量要求)。本文提出了一种自适应混合FFT架构，结合了两种架构的优势。该架构具有以下特点：开发了一组radix- $2^k$ 多路径延迟交换器(MDC)单元以支持高性能大规模处理；制定了无冲突内存访问方案确保连续数据流；证明了一系列位维度排列的存在性，满足可变长度、高基数和任意并行度的广泛适应性要求。

研究背景与动机

问题定义

核心问题：传统FFT处理器架构存在固有缺陷
- 流水线架构：高吞吐量但硬件利用率低，在小规模FFT操作时大量硬件闲置
- 基于内存的架构：硬件利用率高但计算周期增加，影响实时处理性能
问题重要性：
- FFT在无线通信、图像处理、雷达信号处理等领域广泛应用
- 大规模数据处理需求不断增长，需要既高效又灵活的FFT处理器
- 现有架构无法同时满足高吞吐量和高硬件利用率要求
现有方法局限性：
- 流水线架构在处理小规模FFT时硬件利用率可低至15%
- 基于内存的架构需要多次迭代，增加了计算延迟
- 现有冲突避免方案主要局限于radix-2算法，不支持高基数计算
研究动机：
- 结合两种架构优势，实现自适应重配置
- 支持大规模FFT处理(最大512K点)
- 提高硬件利用率同时保证高吞吐量

核心贡献

提出自适应混合FFT处理器架构：支持流水线和基于内存两种模式，可处理最大512K点的FFT
开发radix- $2^k$ 多路径延迟交换器(MDC)：支持radix- $2^5$ 算法，显著减少计算阶段数
设计无冲突内存访问技术：实现完全就地内存变换的连续流FFT计算
构建通用位排列方法：适应不同FFT长度、基数和并行度的硬件约束

方法详解

任务定义

设计一个可重配置的FFT处理器，能够：

输入：N点复数序列 (N = 2^n，最大512K)
输出：对应的频域表示
约束：支持radix- $2^k$ (k≤5)算法，可配置并行度P，实现无冲突内存访问

模型架构

1. 顶层架构设计

输入数据 → 数据重排模块 → FFT核心处理器 → 输出数据
         ↑                ↑
    内存银行组        MDC单元组
    地址生成单元      (P个并行)
    并行分支排列电路
    重排电路

2. 关键组件详解

多路径延迟交换器(MDC)单元：

支持radix- $2^5$ /24/23/22混合计算
采用修改的radix- $2^5$ $2^{5}$ 算法，将旋转因子分类为：
- 常数(C)：预存储在ROM中
- 非平凡(NT)：需要复数乘法器
- 平凡(T)：简单的±1, ±j操作

数据重排策略：基于位维度排列实现三级变换： $\sigma^{s,k,P}_N = \sigma^{s,k,P}_{N,3} \circ \sigma^{s,k,P}_{N,2} \circ \sigma^{s,k,P}_{N,1}$

其中：

$\sigma^{s,k,P}_{N,1}$ ：串行位维度排列
$\sigma^{s,k,P}_{N,2}$ ：并行分支交换
$\sigma^{s,k,P}_{N,3}$ ：精细索引调整

3. 无冲突内存访问方案

流水线模式：

使用交错地址模式：自然顺序和反转顺序
读写地址关系： $\sigma^i_W = \sigma^{i-1}_R$
保证连续数据流无冲突

基于内存模式：

引入额外排列 $\tilde{\sigma}^{s,k,P}_{N,1}$ 用于就地存储
适用于N ∈ (2^{2k}, 2^{3k}]的大规模处理

技术创新点

统一的radix- $2^k$ 架构：通过修改算法实现硬件复用，同一套硬件支持多种基数
自适应重配置能力：根据FFT大小和性能需求动态选择工作模式
通用位排列理论：扩展现有方法，支持任意基数、长度和并行度
优化的内存访问模式：针对不同模式设计专门的无冲突访问策略

实验设置

硬件平台

FPGA: Xilinx Virtex UltraScale+ VCU118 (xcvu9p-flga2104-2L-e)
开发工具: Chisel HDL, Xilinx Vivado 2019.2
存储实现:
- 数据存储：Ultra RAMs (URAMs)，每个内存256K地址×32位
- 旋转因子存储：Block RAMs (BRAMs)

评价指标

硬件利用率：活跃蝶形单元的平均比例
计算周期数：完成FFT所需的时钟周期
处理时间：迭代次数 × 每次迭代周期数
资源消耗：DSP48E2、LUT、FF等硬件资源使用量

对比方法

内存型架构：Tsai'11、Kaya'23、Wang'20
流水线架构：Garrido'13

实验结果

主要结果

1. 与内存型架构对比

架构	基数	FFT长度	并行度	迭代次数	处理时间减少
Tsai'11	radix-2³	64~4K	2	⌈n/3⌉	70%+
Kaya'23	radix-2	2K~16K	2	⌈n/2⌉	70%+
Wang'20	radix-2³	32~32K	4	⌈n/3⌉	70%+
本文	radix-2⁵	32~512K	8	⌈n/5⌉	基准

2. 与流水线架构对比

配置	FFT长度	平均硬件利用率	提升幅度
Garrido'13 (P=1)	2K~512K	75%	-
Garrido'13 (P=1)	64~1K	40%	-
Garrido'13 (P=1)	2~32	15%	-
本文 (P=1)	2K~512K	75%	持平
本文 (P=2)	64~1K	80%	2倍
本文 (P=4)	2~32	60%	4倍