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

Адаптивная гибридная БПФ: новая конвейерная и основанная на памяти архитектура для БПФ основания-2k2^k при обработке больших объёмов данных

Основная информация

  • ID статьи: 2501.01259
  • Название: Adaptive Hybrid FFT: A Novel Pipeline and Memory-Based Architecture for Radix-2k2^k FFT in Large Size Processing
  • Авторы: Fangyu Zhao, Chunhua Xiao, Zhiguo Wang, Xiaohua Du, Bo Dong
  • Категория: cs.AR (компьютерная архитектура)
  • Время публикации/конференция: Подано в IEEE, январь 2025
  • Ссылка на статью: https://arxiv.org/abs/2501.01259

Аннотация

В области цифровой обработки сигналов быстрое преобразование Фурье (БПФ) является фундаментальным алгоритмом. Реализация его на процессорах обычно использует две архитектуры: конвейерную архитектуру (подходит для приложений с высокой пропускной способностью, но с низкой утилизацией аппаратного обеспечения) и архитектуру на основе памяти (подходит для сценариев с ограниченной площадью, но не может удовлетворить строгие требования пропускной способности). В данной статье предлагается адаптивная гибридная архитектура БПФ, сочетающая преимущества обеих архитектур. Архитектура характеризуется следующими особенностями: разработан набор модулей многопутевого задержанного коммутатора (MDC) основания-2k2^k для поддержки высокопроизводительной обработки больших объёмов данных; разработана схема доступа к памяти без конфликтов для обеспечения непрерывного потока данных; доказано существование ряда перестановок битовых размерностей, удовлетворяющих широким требованиям адаптивности для переменной длины, высокого основания и произвольной степени параллелизма.

Исследовательский контекст и мотивация

Определение проблемы

  1. Основная проблема: традиционные архитектуры процессоров БПФ имеют врождённые недостатки
    • Конвейерная архитектура: высокая пропускная способность, но низкая утилизация аппаратного обеспечения; при малых операциях БПФ большая часть аппаратного обеспечения остаётся неиспользованной
    • Архитектура на основе памяти: высокая утилизация аппаратного обеспечения, но увеличенный вычислительный цикл, влияющий на производительность обработки в реальном времени
  2. Важность проблемы:
    • БПФ широко применяется в беспроводной связи, обработке изображений, обработке сигналов радара и других областях
    • Растущие требования к обработке больших объёмов данных требуют эффективного и гибкого процессора БПФ
    • Существующие архитектуры не могут одновременно удовлетворить требования высокой пропускной способности и высокой утилизации аппаратного обеспечения
  3. Ограничения существующих методов:
    • Утилизация аппаратного обеспечения конвейерной архитектуры при обработке малых БПФ может быть всего 15%
    • Архитектура на основе памяти требует множественных итераций, увеличивая задержку вычисления
    • Существующие схемы избежания конфликтов в основном ограничены алгоритмом основания-2, не поддерживают вычисления высокого основания
  4. Исследовательская мотивация:
    • Объединить преимущества обеих архитектур, реализовать адаптивную переконфигурацию
    • Поддерживать обработку больших БПФ (максимум 512K точек)
    • Повысить утилизацию аппаратного обеспечения при сохранении высокой пропускной способности

Основные вклады

  1. Предложена адаптивная гибридная архитектура процессора БПФ: поддерживает конвейерный и основанный на памяти режимы, может обрабатывать БПФ до 512K точек
  2. Разработан многопутевой задержанный коммутатор (MDC) основания-2k2^k: поддерживает алгоритм основания-252^5, значительно снижает количество вычислительных этапов
  3. Разработана технология доступа к памяти без конфликтов: реализует непрерывный поток вычисления БПФ с полной трансформацией на месте
  4. Построен универсальный метод перестановки битов: адаптируется к различным длинам БПФ, основаниям и степеням параллелизма аппаратных ограничений

Подробное описание методов

Определение задачи

Разработать переконфигурируемый процессор БПФ, способный:

  • Входные данные: последовательность из N комплексных чисел (N = 2^n, максимум 512K)
  • Выходные данные: соответствующее представление в частотной области
  • Ограничения: поддерживать алгоритм основания-2k2^k (k≤5), настраиваемая степень параллелизма P, реализация доступа к памяти без конфликтов

Архитектура модели

1. Проектирование архитектуры верхнего уровня

Входные данные → Модуль переупорядочения данных → Основной процессор БПФ → Выходные данные
              ↑                                    ↑
         Группа банков памяти          Группа модулей MDC
         Генератор адресов             (P параллельных)
         Схема переупорядочения ветвей
         Схема переупорядочения

2. Подробное описание ключевых компонентов

Модуль многопутевого задержанного коммутатора (MDC):

  • Поддерживает вычисления смешанного основания-252^5/24/23/22
  • Использует модифицированный алгоритм основания-252^5, классифицирующий коэффициенты поворота на:
    • Константы (C): предварительно сохранены в ПЗУ
    • Нетривиальные (NT): требуют комплексного умножителя
    • Тривиальные (T): простые операции ±1, ±j

Стратегия переупорядочения данных: Основана на перестановке битовых размерностей, реализует трёхуровневое преобразование: σNs,k,P=σN,3s,k,P∘σN,2s,k,P∘σN,1s,k,P\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}

где:

  • σN,1s,k,P\sigma^{s,k,P}_{N,1}: последовательная перестановка битовых размерностей
  • σN,2s,k,P\sigma^{s,k,P}_{N,2}: обмен параллельными ветвями
  • σN,3s,k,P\sigma^{s,k,P}_{N,3}: точная регулировка индекса

3. Схема доступа к памяти без конфликтов

Конвейерный режим:

  • Использует чередующийся режим адресации: естественный порядок и обратный порядок
  • Соотношение адресов чтения-записи: σWi=σRi−1\sigma^i_W = \sigma^{i-1}_R
  • Гарантирует непрерывный поток данных без конфликтов

Режим на основе памяти:

  • Вводит дополнительную перестановку σ~N,1s,k,P\tilde{\sigma}^{s,k,P}_{N,1} для хранения на месте
  • Применяется для обработки больших объёмов при N ∈ (2^{2k}, 2^{3k}]

Технические инновации

  1. Унифицированная архитектура основания-2k2^k: реализует повторное использование аппаратного обеспечения через модифицированный алгоритм, один набор аппаратного обеспечения поддерживает несколько оснований
  2. Возможность адаптивной переконфигурации: динамически выбирает режим работы в зависимости от размера БПФ и требований производительности
  3. Универсальная теория перестановки битов: расширяет существующие методы, поддерживает произвольное основание, длину и степень параллелизма
  4. Оптимизированный режим доступа к памяти: разрабатывает специализированные стратегии доступа без конфликтов для различных режимов

Экспериментальная установка

Аппаратная платформа

  • FPGA: Xilinx Virtex UltraScale+ VCU118 (xcvu9p-flga2104-2L-e)
  • Инструменты разработки: Chisel HDL, Xilinx Vivado 2019.2
  • Реализация памяти:
    • Хранилище данных: Ultra RAMs (URAMs), каждая память 256K адресов × 32 бита
    • Хранилище коэффициентов поворота: Block RAMs (BRAMs)

Показатели оценки

  1. Утилизация аппаратного обеспечения: средняя доля активных модулей бабочки
  2. Количество вычислительных циклов: количество тактовых циклов, необходимых для завершения БПФ
  3. Время обработки: количество итераций × количество циклов на итерацию
  4. Потребление ресурсов: использование ресурсов DSP48E2, LUT, FF и других

Методы сравнения

  1. Архитектура на основе памяти: Tsai'11, Kaya'23, Wang'20
  2. Конвейерная архитектура: Garrido'13

Результаты экспериментов

Основные результаты

1. Сравнение с архитектурой на основе памяти

АрхитектураОснованиеДлина БПФСтепень параллелизмаКоличество итерацийСнижение времени обработки
Tsai'11основание-2³64~4K2⌈n/3⌉70%+
Kaya'23основание-22K~16K2⌈n/2⌉70%+
Wang'20основание-2³32~32K4⌈n/3⌉70%+
Данная работаоснование-2⁵32~512K8⌈n/5⌉базовая

2. Сравнение с конвейерной архитектурой

КонфигурацияДлина БПФСредняя утилизация аппаратного обеспеченияМасштаб улучшения
Garrido'13 (P=1)2K~512K75%-
Garrido'13 (P=1)64~1K40%-
Garrido'13 (P=1)2~3215%-
Данная работа (P=1)2K~512K75%эквивалентно
Данная работа (P=2)64~1K80%2x
Данная работа (P=4)2~3260%4x

3. Результаты реализации на FPGA (N=512K, P=1)

  • DSP48E2: 45,365 единиц
  • LUT: 76,183 единицы
  • FF: 1,500 единиц
  • Block RAMs: 444 единицы
  • Ultra RAMs: 768 единиц
  • Рабочая частота: 196.8 МГц

Ключевые выводы

  1. Повышение вычислительной эффективности: благодаря алгоритму основания-252^5 количество итераций снижается до ⌈n/5⌉, что на 40% и более меньше, чем традиционные методы
  2. Оптимизация утилизации аппаратного обеспечения: благодаря адаптивной степени параллелизма утилизация аппаратного обеспечения для малых БПФ повышается в 2-4 раза
  3. Повышенная масштабируемость: поддерживает обработку БПФ в широком диапазоне от 32 до 512K точек

Связанные работы

Основные направления исследований

  1. Конвейерная архитектура БПФ: представлена Groginsky & Works (1970), стремится к высокой пропускной способности
  2. Архитектура БПФ на основе памяти: нацелена на снижение аппаратных ресурсов, подходит для приложений с ограниченной площадью
  3. Алгоритмы БПФ высокого основания: алгоритм основания-2k2^k балансирует сложность вычисления и сложность аппаратной реализации

Относительные преимущества данной работы

  1. Слияние архитектур: впервые реализует адаптивное переключение между конвейерной и архитектурой на основе памяти
  2. Расширение основания: поддерживает максимальное основание-252^5, превосходит существующее ограничение основания-232^3
  3. Совершенствование теории: предоставляет универсальную теоретическую базу перестановки битов

Заключение и обсуждение

Основные выводы

  1. Адаптивная гибридная архитектура успешно объединяет преимущества конвейерной и архитектуры на основе памяти
  2. Проектирование MDC основания-252^5 значительно повышает вычислительную эффективность больших БПФ
  3. Универсальный метод перестановки битов обеспечивает теоретическую гарантию для различных конфигураций
  4. Экспериментальная проверка подтверждает значительное улучшение архитектуры в утилизации аппаратного обеспечения и вычислительной эффективности

Ограничения

  1. Ограничение области применения: режим на основе памяти применяется только для N ∈ (2^{2k}, 2^{3k}]
  2. Увеличение сложности аппаратного обеспечения: поддержка нескольких оснований увеличивает сложность логики управления
  3. Отсутствие анализа энергопотребления: не предоставляется детальный анализ сравнения энергопотребления

Будущие направления

  1. Расширить поддержку обработки ещё больших масштабов БПФ
  2. Оптимизировать энергоэффективность
  3. Исследовать применение в ускорителях искусственного интеллекта

Глубокая оценка

Преимущества

  1. Высокая инновационность: впервые предлагает адаптивную гибридную архитектуру БПФ, решает врождённое противоречие традиционных архитектур
  2. Полнота теории: предоставляет полную теоретическую базу перестановки битов с высокой универсальностью
  3. Достаточность экспериментов: от теоретического анализа до реализации на FPGA, проверяет эффективность метода
  4. Высокая практическая ценность: поддерживает БПФ 512K точек, удовлетворяет требования современной обработки больших данных

Недостатки

  1. Увеличение сложности: адаптивный механизм увеличивает сложность проектирования и верификации
  2. Неполнота сравнения: отсутствует сравнение производительности с новейшими коммерческими ядрами БПФ
  3. Отсутствие анализа энергопотребления: энергопотребление является важным фактором в мобильных и встроенных приложениях

Влияние

  1. Академический вклад: предоставляет новую архитектурную парадигму для проектирования процессоров БПФ
  2. Инженерная ценность: может быть непосредственно применена в обработке сигналов базовых станций 5G/6G, радарных системах и других областях
  3. Воспроизводимость: предоставляет подробные параметры проектирования и детали реализации

Применимые сценарии

  1. Высокопроизводительные вычисления: научные вычислительные приложения, требующие обработки больших БПФ
  2. Системы связи: модули обработки сигналов базовых станций 5G/6G
  3. Радарные системы: обработка сигналов в реальном времени и обнаружение целей
  4. Обработка изображений: анализ в частотной области изображений высокого разрешения

Список литературы

Статья цитирует 17 связанных источников, охватывающих алгоритмы БПФ, реализацию на FPGA, оптимизацию доступа к памяти и другие аспекты, обеспечивая прочную теоретическую базу для исследования.

Общая оценка: это высококачественная статья в области компьютерной архитектуры, имеющая важное теоретическое и практическое значение в области проектирования процессоров БПФ. Авторы посредством умелого архитектурного проектирования и строгого теоретического анализа успешно решают врождённые проблемы традиционных архитектур БПФ, предоставляя новые идеи и направления для развития этой области.